WEKO3
アイテム
{"_buckets": {"deposit": "a809929b-3d26-4dc0-a733-6a7416e2df26"}, "_deposit": {"created_by": 13, "id": "9360", "owners": [13], "pid": {"revision_id": 0, "type": "depid", "value": "9360"}, "status": "published"}, "_oai": {"id": "oai:uec.repo.nii.ac.jp:00009360", "sets": ["6"]}, "author_link": ["25516", "25517"], "item_10001_biblio_info_7": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2017-01", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "312", "bibliographicPageStart": "294", "bibliographicVolumeNumber": "80", "bibliographic_titles": [{}, {"bibliographic_title": "International Journal of Approximate Reasoning", "bibliographic_titleLang": "en"}]}]}, "item_10001_description_5": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The junction tree algorithm is currently the most popular algorithm for exact inference on Bayesian networks. To improve the time complexity of the junction tree algorithm, we need to find a triangulation with the optimal total table size. For this purpose, Ottosen and Vomlel have proposed a depth-first search (DFS) algorithm. They also introduced several techniques to improve the DFS algorithm, including dynamic clique maintenance and coalescing map pruning. Nevertheless, the efficiency and scalability of that algorithm leave much room for improvement. First, the dynamic clique maintenance allows to recompute some cliques. Second, in the worst case, the DFS algorithm explores the search space of all elimination orders, which has size n!, where n is the number of variables in the Bayesian network. To mitigate these problems, we propose an extended depth-first search (EDFS) algorithm. The new EDFS algorithm introduces the following two techniques as improvements to the DFS algorithm: (1) a new dynamic clique maintenance algorithm that computes only those cliques that contain a new edge, and (2) a new pruning rule, called pivot clique pruning. The new dynamic clique maintenance algorithm explores a smaller search space and runs faster than the Ottosen and Vomlel approach. This improvement can decrease the overhead cost of the DFS algorithm, and the pivot clique pruning reduces the size of the search space by a factor of O(n2). Our empirical results show that our proposed algorithm finds an optimal triangulation markedly faster than the state-of-the-art algorithm does.", "subitem_description_type": "Abstract"}]}, "item_10001_publisher_8": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Elsevier"}]}, "item_10001_relation_14": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isVersionOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1016/j.ijar.2016.09.012", "subitem_relation_type_select": "DOI"}}]}, "item_10001_relation_17": {"attribute_name": "関連サイト", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1016/j.ijar.2016.09.012", "subitem_relation_type_select": "DOI"}}]}, "item_10001_rights_15": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "© 2017 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ "}]}, "item_10001_source_id_9": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0888613X", "subitem_source_identifier_type": "ISSN"}]}, "item_10001_version_type_20": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Li, Chao", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "25516", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Ueno, Maomi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "25517", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2019-09-25"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "An extended depth-first search algorithm for optimal triangulation of Bayesian networks.pdf", "filesize": [{"value": "1.3 MB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 1300000.0, "url": {"label": "An extended depth-first search algorithm for optimal triangulation of Bayesian networks", "url": "https://uec.repo.nii.ac.jp/record/9360/files/An extended depth-first search algorithm for optimal triangulation of Bayesian networks.pdf"}, "version_id": "becc50bc-e5f1-4ca6-a4f5-f1df438bb728"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Bayesian network", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "probabilistic inference", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "optimal triangulation", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "dynamic clique maintenance", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "An extended depth-first search algorithm for optimal triangulation of Bayesian networks", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "An extended depth-first search algorithm for optimal triangulation of Bayesian networks", "subitem_title_language": "en"}]}, "item_type_id": "10001", "owner": "13", "path": ["6"], "permalink_uri": "https://uec.repo.nii.ac.jp/records/9360", "pubdate": {"attribute_name": "公開日", "attribute_value": "2019-09-25"}, "publish_date": "2019-09-25", "publish_status": "0", "recid": "9360", "relation": {}, "relation_version_is_last": true, "title": ["An extended depth-first search algorithm for optimal triangulation of Bayesian networks"], "weko_shared_id": -1}
An extended depth-first search algorithm for optimal triangulation of Bayesian networks
https://uec.repo.nii.ac.jp/records/9360
https://uec.repo.nii.ac.jp/records/93608bdc5116-a09d-4981-9a59-dbc52d50fc8f
名前 / ファイル | ライセンス | アクション |
---|---|---|
An extended depth-first search algorithm for optimal triangulation of Bayesian networks (1.3 MB)
|
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2019-09-25 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | An extended depth-first search algorithm for optimal triangulation of Bayesian networks | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Bayesian network | |||||
キーワード | ||||||
言語 | en | |||||
主題 | probabilistic inference | |||||
キーワード | ||||||
言語 | en | |||||
主題 | optimal triangulation | |||||
キーワード | ||||||
言語 | en | |||||
主題 | dynamic clique maintenance | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | journal article | |||||
著者 |
Li, Chao
× Li, Chao× Ueno, Maomi |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | The junction tree algorithm is currently the most popular algorithm for exact inference on Bayesian networks. To improve the time complexity of the junction tree algorithm, we need to find a triangulation with the optimal total table size. For this purpose, Ottosen and Vomlel have proposed a depth-first search (DFS) algorithm. They also introduced several techniques to improve the DFS algorithm, including dynamic clique maintenance and coalescing map pruning. Nevertheless, the efficiency and scalability of that algorithm leave much room for improvement. First, the dynamic clique maintenance allows to recompute some cliques. Second, in the worst case, the DFS algorithm explores the search space of all elimination orders, which has size n!, where n is the number of variables in the Bayesian network. To mitigate these problems, we propose an extended depth-first search (EDFS) algorithm. The new EDFS algorithm introduces the following two techniques as improvements to the DFS algorithm: (1) a new dynamic clique maintenance algorithm that computes only those cliques that contain a new edge, and (2) a new pruning rule, called pivot clique pruning. The new dynamic clique maintenance algorithm explores a smaller search space and runs faster than the Ottosen and Vomlel approach. This improvement can decrease the overhead cost of the DFS algorithm, and the pivot clique pruning reduces the size of the search space by a factor of O(n2). Our empirical results show that our proposed algorithm finds an optimal triangulation markedly faster than the state-of-the-art algorithm does. | |||||
書誌情報 |
en : International Journal of Approximate Reasoning 巻 80, p. 294-312, 発行日 2017-01 |
|||||
出版者 | ||||||
出版者 | Elsevier | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0888613X | |||||
DOI | ||||||
関連タイプ | isVersionOf | |||||
識別子タイプ | DOI | |||||
関連識別子 | 10.1016/j.ijar.2016.09.012 | |||||
権利 | ||||||
権利情報 | © 2017 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ | |||||
関連サイト | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1016/j.ijar.2016.09.012 | |||||
著者版フラグ | ||||||
出版タイプ | AM | |||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa |