对iMMPC算法的理解

本文基于论文《iMMPC: A Local Search Approach for Incremental Bayesian Network StructureLearning》

 Immpc:一种贝叶斯网络结构增量学习的局部搜索方法

目前在机器学习领域中，一个重要的组成部分就是概率图模型，而贝叶斯作为一种典型的概率图模型，在不确定性推理以及挖掘各个变量之间的关系中有着重要的作用，而贝叶斯结构学习是其重要的研究内容之一。本文章研究的就是在增量模式下，一种基于爬山法对贝叶斯结构进行有效学习的方法，节省时间，提高准确度。

一般有三种典型的结构学习方法：1.搜索评分法，缺点：搜索空间超指数，变量数目巨大时很难评价所有的结构。2.基于约束的方法，（基于统计的方法）利用统计方法把数据变量之间的依赖关系建立起来，但是不适合大批量的数据。3.局部搜索，利用统计依赖关系建立初级的结构，再利用启发式搜索完成全部结构的搜索。这个方法可以认为是前面两种方法的结合。而一般的局部搜索方法，在论文中提到：PC(parents_children),MB(makov blanket),这两个都是建立局部父子关系的方法，以及利用启发式搜索：MMPC,MBOR,并利用另一种启发搜索完成全局的结构学习。如上一篇博文中提到的MMHC，结合了MMPC和爬山算法。（详细论文见原文参考文献。） [MMHC:最大最小爬山法，是一种混合学习算法（本地搜索和搜索评分），目的是解决高维度问题，第一步是通过本地搜索方式（MMPC）建立起基本的框架，第二步用贪婪爬山法，对边进行定向。]

对于iMMPC，我的理解是，它在MMPC的基础上做了两步工作，其中一步是TOCO，这一步保存了搜索路径，并且有了一个增量学习的判定指标：通过遍历原来的路径，新数据如果契合路径，那么需要对结构进行改变。（这个判定指标是否可以有更好点的方法?）第二步是RSS，即reduced searchspace.这一步保存了原来学习的几个最优结构，最终在最优结构中重新进行选择，避免低分结构，搜索空间大为减少。

算法如图1所示：

图1

如论文中的图一目了然：

解释一下此图：左边是原来的学习算法，搜索空间很大，右边是新的搜索算法，每次搜索只有4个候选结构，减少了搜索空间。

这其实给我们提供了一些思路：其实从工作上来说，他并没有做很多工作，但是正是这些简单的想法，使得算法的效率大大提高。那么我们的工作可以从哪些方面展开呢？我有如下的一些想法：1.比如我们可以思考，如何建立可行的指标对结构是否需要更新进行判定，此论文中通过搜索路径的契合来判定，我觉得多少有些不是很妥当，（由于路径的搜索本身是局部最优算法，那么路径不一定准确）。2.如果判定到了需要改变，这个改变的方案如何？这个文章始终还是把原来的数据与新增数据进行了融合。能否不融合，只用新数据？进行局部结构的优化？而问题也在于，原来结构是基于原来数据的，抛开原来数据做优化如何保存住原来数据包含的信息？？这应该是今后工作的重点。