研究不可靠的独立性判断器下贝叶斯与马尔可夫网络的结构学习方法
Learning Bayesian and Markov Networks with an Unreliable Oracle
- 利用有界错误的独立性查询，推导网络结构唯一可识别条件
- 马尔可夫网络在路径数少时可容忍指数级错误，贝叶斯网络则不能容忍任何错误
- 提出在结构可识别时的高效学习算法，适用于低复杂度图结构
我们研究在存在一个最多有界错误的条件独立性预言机的情况下，马尔可夫网络和贝叶斯网络的基于约束的结构学习问题。对于马尔可夫网络，我们发现当顶点间无交路径的最大数量较小时，即使错误数量为顶点数的中等指数级，结构仍可唯一识别。然而，对于贝叶斯网络，我们证明即使在常用图参数（如树宽）有界的情况下，也无法容忍任何错误以确保结构始终可识别。最后，我们给出了在结构唯一可识别时的结构学习算法。
原文摘要 · Abstract (English)
We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。