概率图模型结构学习的理论研究

问题描述：问题描述：有向无环图（DAGs，也叫做贝叶斯网络）的结构估计很困难，因为DAGs的搜索空间是组合的，它的规模随节点数呈超指数规模增加。现有的方法依赖于不同的局部启发式算法来加强无环约束，并且不能适用于一般目的的优化。从数据中学习有向无环图（DAGs）是个NP难的问题，因为组合无环约束很难有效实现。同时，DAGs在实际中是个广泛应用的模型，能够应用到生物工程、机器学习以及因果推断方面。基于上述原因，用于学习DAGs的新方法受到广泛关注，这对于机器学习和统计学都是一个重要的课题。
主要研究内容：现有优化方法的弊端在于不能有效达到无环性约束，无约束算法，如梯度下降法，显然不能达到这个约束条件。由于无环性约束是非凸的，不能准确定义投影算子，因此投影方法不能充分解决这一问题。我们需要研究专门的优化方法来有效达到无环性约束。现有的方法包括分支-切割法、动态规划法、A*搜索法、贪心算法、坐标下降法等。目前在不同结构和统计假设的情况下学习DAGs的算法都取得了很大的进步。从现有的所有机器算法中我们可以看出，这些模型的成功之处在于都具有一个封闭的形式、对于现有优化技术来说容易处理。对于无向图来说主要的技术是凸优化。可是DAG学习算法显然不能直接使用这些优化算法，因为它涉及的问题是不易处理的。这就导致了启发式算法的大量应用，总是从优化方法中提取工具，但还是要依靠启发式方法来给算法提速。广泛的来说，现有方法可以分成估计算法和精确算法，后者能够保证返回一个全局最优解。精确算法能够形成一类方法，但它们都是围绕着NP难的组合优化问题，这些方法在计算普遍不容易实现。可以说目前最流行的优化方法都包括局部搜索，也就是边和父节点集都是有序增加，一次只增加一个节点。只要每个节点只有少量的父节点时，这种方法就是有效的。但随着可能的父节点数增加，局部搜索很快不易处理。此外，这种策略非常依赖严格的结构假设，显然这些严格的假设难以达到并且不可能验证。因此，找到能够进行全局搜索的算法也是个关键的研究点。关于DAG学习的文献可以划分为在离散数据上处理和在连续数据上处理。许多方法仅能够在非常特定的数据上有效，因此找到不依赖于特定模型假设的一般方法也是个重要的研究点。最后一点是，现有方法最重要的弊端是它的概念非常复杂，需要相关人员具有非常了解图模型，这些方法还涉及到许多非常强的技巧。因此，如何建立一个能够让不了解图模型的人也能明白的数学模型也至关重要。
参考技术路线：具体地，本课题以贝叶斯网络的结构学习为主要研究内容，以提高贝叶斯学习精度为研究目标，在现有局部启发式算法的基础上，引入数值优化的相关知识，研究能够对DAG结构进行全局最优学习的算法。在已有的外部攻击检测的基础上，结合网络安全等相关知识和公开数据集，验证贝叶斯网络结构学习的实际应用效果，并针对实验结果进行改进。
研究资源：由于目前已有大量的贝叶斯网络学习研究，以及相关数据和构建好的实际应用模型，我们将利用这些公开的数据进行学习，并与实际模型相比较，从而对本项目的算法以及公开发表算法进行评价。比较有名的公开数据集包括：牛津大学的BN Learn（http://www.bnlearn.com/），澳大利亚人工智能协会的ABNMS数据集（http://abnms.org/bnrepo/），以色列希伯来大学的BN Repository（http://www.cs.huji.ac.il/Repository/），NORSYS软件公司的Net library数据集（http://www.norsys.com/netlibrary/），以及HUGIN公司的BN Forum数据集（http://forum.hugin.com/）等。同时还有关于外部攻击的相关数据集，可以用来进行实际验证。
已有研究成果：目前在原有的贝叶斯结构学习算法和现有网络外部攻击检测的基础上，使用了新的结构学习算法在数据集上进行了实验，并取得了98.40%的准确率，相比传统算法只取得了97.38%的准确率。这样的实验结果证明了寻找全局最优解是个有前景的方向，并取得初步的进展。