7,129
个编辑
更改
→推理复杂度与近似算法
1990年，Cooper在斯坦福大学研究大规模生物信息学应用时，证明了贝叶斯网络中的精确推理是[[NP-hard]]<ref>
1990年，Cooper在斯坦福大学研究大规模生物信息学应用时，证明了贝叶斯网络中的精确推理是[[NP-hard]]<ref>
{{cite journal | first = Gregory F. | last = Cooper | name-list-style = vanc | title = The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks | url = https://stat.duke.edu/~sayan/npcomplete.pdf | journal = Artificial Intelligence | volume = 42 | issue = 2–3 | date = 1990 | pages = 393–405 | doi = 10.1016/0004-3702(90)90060-d }}
{{cite journal | first = Gregory F. | last = Cooper | title = The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks | url = https://stat.duke.edu/~sayan/npcomplete.pdf | journal = Artificial Intelligence | volume = 42 | issue = 2–3 | date = 1990 | pages = 393–405 | doi = 10.1016/0004-3702(90)90060-d }}
</ref>（NP难问题，NP 是指非确定性多项式 non-deterministic polynomial）。这个结果促进了近似算法的研究，目的是开发出一种易于处理的近似方法来进行概率推理。1993年，Dagum 和 Luby 证明了贝叶斯网络中近似概率推理复杂度的两个令人惊讶的结果。<ref>
</ref>（NP难问题，NP 是指非确定性多项式 non-deterministic polynomial）。这个结果促进了近似算法的研究，目的是开发出一种易于处理的近似方法来进行概率推理。1993年，Dagum 和 Luby 证明了贝叶斯网络中近似概率推理复杂度的两个令人惊讶的结果。<ref>
{{cite journal | vauthors = Dagum P, Luby M | author-link1 = Paul Dagum | author-link2 = Michael Luby | title = Approximating probabilistic inference in Bayesian belief networks is NP-hard | journal = Artificial Intelligence | volume = 60 | issue = 1 | date = 1993 | pages = 141–153 | doi = 10.1016/0004-3702(93)90036-b | citeseerx = 10.1.1.333.1586 }}
{{cite journal | vauthors = Dagum P, Luby M | title = Approximating probabilistic inference in Bayesian belief networks is NP-hard | journal = Artificial Intelligence | volume = 60 | issue = 1 | date = 1993 | pages = 141–153 | doi = 10.1016/0004-3702(93)90036-b | citeseerx = 10.1.1.333.1586 }}
</ref>首先，他们证明了任何易于处理的确定性近似概率推断算法的绝对误差都不可能小于1/2。其次，他们证明了没有任何易于处理的随机化的近似概率推断算法可以在置信度大于1 / 2的情况下，误差小于1 / 2。
</ref>首先，他们证明了任何易于处理的确定性近似概率推断算法的绝对误差都不可能小于1/2。其次，他们证明了没有任何易于处理的随机化的近似概率推断算法可以在置信度大于1 / 2的情况下，误差小于1 / 2。
实际上，这些复杂性结果表明，虽然贝叶斯网络在人工智能和机器学习应用中是一种强大的表示，但它们在大型实际应用中需要对拓扑结构施加约束(如朴素贝叶斯网络)或对条件概率施加约束。'''<font color="#ff8000">有界方差算法 Bounded variance algorithm </font>'''<ref>{{cite journal | vauthors = Dagum P, Luby M | author-link1 = Paul Dagum | author-link2 = Michael Luby | title = An optimal approximation algorithm for Bayesian inference | url = http://icsi.berkeley.edu/~luby/PAPERS/bayesian.ps | journal = Artificial Intelligence | volume = 93 | issue = 1–2 | date = 1997 | pages = 1–27 | doi = 10.1016/s0004-3702(97)00013-1 | citeseerx = 10.1.1.36.7946 | access-date = 2015-12-19 | archive-url = https://web.archive.org/web/20170706064354/http://www1.icsi.berkeley.edu/~luby/PAPERS/bayesian.ps | archive-date = 2017-07-06 | url-status = dead }}</ref>是贝叶斯网络中第一个被证明在保证误差的情况下还能进行快速近似概率推理的算法。这个强大的算法需要对贝叶斯网络的条件概率进行细微的限制，使其处于[0 + 1/p(n), 1 - ''p''(''n'')]的区间内 ，其中''p''(''n'')是网络中节点数n的任意多项式。
实际上，这些复杂性结果表明，虽然贝叶斯网络在人工智能和机器学习应用中是一种强大的表示，但它们在大型实际应用中需要对拓扑结构施加约束(如朴素贝叶斯网络)或对条件概率施加约束。'''<font color="#ff8000">有界方差算法 Bounded variance algorithm </font>'''<ref>{{cite journal | vauthors = Dagum P, Luby M | author-link1 = Paul Dagum | author-link2 = Michael Luby | title = An optimal approximation algorithm for Bayesian inference | url = http://icsi.berkeley.edu/~luby/PAPERS/bayesian.ps | journal = Artificial Intelligence | volume = 93 | issue = 1–2 | date = 1997 | pages = 1–27 | doi = 10.1016/s0004-3702(97)00013-1 | citeseerx = 10.1.1.36.7946 | access-date = 2015-12-19 | archive-url = https://web.archive.org/web/20170706064354/http://www1.icsi.berkeley.edu/~luby/PAPERS/bayesian.ps | archive-date = 2017-07-06 | url-status = dead }}</ref>是贝叶斯网络中第一个被证明在保证误差的情况下还能进行快速近似概率推理的算法。这个强大的算法需要对贝叶斯网络的条件概率进行细微的限制，使其处于[0 + 1/p(n), 1 - ''p''(''n'')]的区间内 ，其中''p''(''n'')是网络中节点数n的任意多项式。
==软件==
==软件==