机器学习40讲_42_40_结构学习基于约束与基于评分
你好，我是王天一。
今天我和你分享的主题是结构学习，基于约束与基于评分结构。
学习的任务呢是找到和数据匹配度最高的这种网络结构，它需要同时学习未知图模型的结构还有参数，这也容易理解，连模型的结构都不知道，那参数肯定也是不知道的啊，所以需要一并的来进行学习结构。
学习的任务呢是根据训练数据集找到结构最恰当的这个模型，这无疑比参数学习要复杂的多，也存在着更多的不确定性。
对图模型进行结构学习的目的呢有两个，一个是知识发现，根据因变量的结果来判定自变量之间的依赖关系，另一个则是密度估计估计出数据分布的特性。
据此呢，对新样本进行推断。
那么结构学习的方法有哪些呢？主要有三种，分别是基于约束的学习，基于评分的学习和基于回归的学习。
这三种方法它都可以应用在有向的贝叶斯网络，还有无向的马尔可夫随机场里。
但是在下面的介绍当中呢啊出于简单的考虑，我将以贝叶斯网络为例，基于约束的结构学习，它是将贝叶斯网络视为条件独立性的一个表示。
这和贝叶斯网络的语义呢是非常贴近的。
这种方法。
首先，从数据当中识别出一组条件，独立性作为约束，然后呢尝试找到最符合这些约束的网络结构，基于约束的学习和贝叶斯网络的结构特征密切相关。
但是它缺乏类似于似然函数这样的显示的目标函数啊，我可以把它写成一个明确的表达式的形式啊，没有这种目标函数。
所以呢就不能够直接找到全局的最优结构啊，也就不适用于在概率框架之下来处理这个问题。
基约束的典型算法是SGS算法。
这个名字呢来源于三位设计者的首字母的缩写。
Sgs采用遍历式的方法来判定节点之间是否应该有边存在。
它首先在节点的结合上构造出全连接的无向图。
啊，每两个点之间我都给它连一条边儿，再对图中多余的边做出删减。
具体的做法是怎么样的呢？选出两个节点i和j.那么判断这两个节点在给定其他所有节点的条件之下，是否是条件独立的。
如果说存在的让i和j满足低分离性的这个节点子集，那呢就把这i和j之间的边给它去掉掉。
所有的节点都进行上述的操作之后，就可以删除这个冗余的边得到新的简化的无向图。
上面这个步骤呢只能确定说边的存在性，要形成贝叶斯网络的话，还得给通过审核的每条边儿确定方向。
定向的方法呢是找到所有具有IJK形式，也就是两端的节点互不相连，但都和中间节点相连接的这个节点的三元组，并且判断i和k之间的条件独立性。
那么回忆一下啊，我们概率脱模型当中最基本的三种结构，顺联分联汇联啊，实际上都是具有这样的结构。
找到这个三人组之后啊，当且仅当两端的节点，i和k无论如何都不满足。
低分离性的手就将这个三人组定义成一个汇联的结构啊，也就是i和k两端都指向中间的。
这个j对所有的三人组都进行完上面的检测之后呢，接下来要重复下面的步骤。
如果说三元组具有i指向k,但j和k之间是无向边的情况。
同时呢j又没有指向其他结点的，有向边，那就直接添加一条从j出发到k终止的有向边，j到k如果说i和j之间本身还存在着未确定方向的这个边的话，同时呢还有从i出发，经过其他结点到j的有向路径啊，我可以绕一圈打到j,那么两者之间的无向边就被定向为从i到j过程听起来很复杂啊，当以上步骤重复到没有新的边需要定向的时候，这时呢图模型的结构就完全确定了SGS最大的问题在于运算的复杂度。
它的运算量呢会随着节点数目的增加，以超指数的方式增长啊，比指数形式增长的还快。
所以呢不具备可扩展性。
除了计算问题之外，SGS在可靠性上也存在缺陷。
它在确定高阶的条件独立性的时候，它的可靠性远远不如低阶的独立关系。
那么在SGS算法的基础上呢，还衍伸出了PC算法。
和针对大规模网络的这个增长收缩算法在这儿呢就不赘述了。
和基于约束的学习不同，基于评分的结构学习是把结构学习问题处理成一个模型的选择问题。
这种学习方法将图模型和数据的匹配程度定义出一个评分函数。
再在所有可能结构当中搜索找到评分最高的那个作为结果。
基于平分学习，首要的任务是选择合适的平分函数。
评分函数它决定了数据和结构之间的拟合程度，所以必须要满足评分等价性，还有可分解性。
这两个条件平分等价性指的是独立性关系相同的等价，网络所获得的分数应该相同。
两个网络如果是等价的，那么它的分数也应该是一样。
可分解性呢指的则是平分函数，能够被分解为多个子函数的累加。
每个子函数呢对应着一个局部的结构，而一个局部结构的变化又不会影响到其他局部结构的分数。
这样做呢可以对评分函数的计算加一个简化定义。
评分函数最常见的出发点是信息论。
如果将学习问题看作最优编码问题的话，就可以定义出最小描述长度作为评分函数。
最小描述长度呢借鉴了信息商的概念。
他的目标是找到一个能以最短的编码长度描述训练数据的这样的模型。
计算出的模型长度呢包括两个部分，一部分是用来描述贝叶斯网络本身，它的字节数取决于参数的个数。
另一部分呢是用来描述这个网络所表示的。
数据字节数呢取决于数据在模型之下的似然概率。
网络当中的参数越多，似然概率的表示就越精确，但过拟合的风险也会越大。
两者的折中呢就是模型的复杂性和模型表示样本的准确性之间的平衡。
这样一个老生长谈的问题，除了最小描述长度之外，是指信息量准则和贝叶斯信息量准则，也是基于信息论的评分函数。
它们都是将评分呢表示成模型加数据的一个组合形式，可以看成是给模型之下的对数自然概率。
Lon l添加了和模型参数数目有关的这个正则画项。
那么在赤值信息量准则里，正则画项呢等于参数的数目k乘以一个常数的系数。
而在贝叶斯信息量准则当中，它的正则化项是参数数目，k乘以样本容量n的对数。
那么点击文稿，你可以看到两者的数学表达式和最小描述长度一样啊，这两个指标呢也是越小越好在设计评分函数的时候，如果将模型和数据融合到一起，这时得到的评分函数呢就叫做贝叶斯迪利克雷评分。
这个函数可以写成是对迪利克雷分布的求和。
贝叶斯迪利克雷评分是在已知结构的时候，通过计算样本数据的这个边际自然函数作为评分的依据。
计算时候呢，我假定这个贝叶斯网络的参数服从迪利克雷形式的先验分布，利用自然等价性的约束，也就是等价结构获得的分数相同，可以对贝叶斯迪雷克雷评分做出改进。
这个改进呢就相当于计算模型关于训练数据集的一个后验的概率选好了合适的评分函数之后，接下来就要在假设空间当中搜索这个评分函数上的最优解。
到底哪个模型能得到最高的平分函数啊啊我要去遍历式的地摊式的搜索。
由于评估所有备选结构的分数难以实现，所以在搜索的时候呢，通常都会使用这个启发式的算法，以查找一个次由结构未必是全局的构优贪婪搜以遗传算法进化规划、模拟退伍和蚁群算法。
这各种各样的启发式算法呢都可以应用在最优结构的搜索当中，将贪婪搜索应用。
在结构学习里的时候，需要先初始化一个网络结构，以它为蓝本，每次对一结边进行增加删除，或者是改变方向的操小，直到新结构的平分函数不再降低为止。
要进一步简化运算量呢，还可以对图结构施加额外的约束，以削减这个假设空间的大小。
这相当于呢又引入了一重鲜验。
和前面两位老大哥相比，基于回归的结构学习，至少从资结结构还是个小一。
这类算法的出发点呢是将目标函数表示为图模型参数的一个线性的组合，再对线性模型进行l一或者是l二的正则化处理来控制模型的复杂度。
它的优势在哪儿呢？可以确保目标函数最优解的一个存在性，明确了学习问题的意义。
同时呢也具备了良好的可扩展性。
基于回归的不同方法之间的区别主要在于目标函数的不同。
最直接的方式是将图结构关于数据的这个对数似然定义为目标函数，然后呢使用拉普拉斯先验来简化模型节点之间的独立性，也可以用lesson回归来估计这呢通常被应用于建模连续变量的这个高斯图模型啊，或者说高斯网络当中，他的任务是确定给定节点的马可夫坦。
那么只要线性系数不为零的这些节点呢和目标节点之间都会存在着依赖关系。
将回归模型和评分函数相结合，还可以把最小描述长度表示为参数的线性组合，并对它进行优化，以确定模型的结构。
那么关于这些方法的具体细节呢，在这儿就不做介绍上面。
所介绍的方法呢都是建立在完备观测数据基础上。
如果说模型当中存在着这个演变量，结构学习的难度呢就会大大的增加。
将专门处理演变量的EM算法引入到结构学习当中，得到的就是结构EM算法。
结构EM算法在具有结构和参数两个维度的假设空间内进行搜索。
在每一轮次的搜索当中呢，原始的EM算法是为固定的模型来更新参数。
那么结构EM算法呢就需要同时更新参数和模型。
因为模型本身也不是固定的，更新的方式呢，是让模型的平分函数最大化评分函数的选择是参数。
关于模型后验概率的信息熵。
当然呢也可以使用前面的提到的这个贝叶斯信息量准则呢，或者是最小描述长度这一类指标。
这时候的话就需要让这个评分函数最小化。
今天我以贝叶斯网络为例，和你分享了概率图。
模型当中结构学习的任务包含着以下四个要点。
第一，结构学习的任务呢是找到与数据匹配度最高的网络结构，它需要同时确定图模型的结构，还有参数。
第二，基于约束的结构学习，通过条件独立性的约束来确定贝叶斯网络的结构，需要先后确定边的存在性和边的方向。
第三，基于评分的结构学习，通过数据和结构的匹配度来确定贝斯网络的结构，包括选择评分函数和搜索最优结构两个步骤。
第四，对不完备数据实施结构学习，可以使用结构EM算法。
前面所介绍的方法呢，其实都是频率轴以下的方法，要使用贝斯斯进行结构学习，就得先给所有的备选模型，还有所有的参数都设定出鲜验，再用训练数据去调整这个线验。
显然这类方法要在所有可能的模型当中进行搜索和比较，它的使用性呢是非常差的啊，基本没有办法真在应用场景下去利用它。
那么简化贝叶斯结构学习的方式包括两种，一种叫贝叶斯模型选择，它是直接选择最像的模型啊，就当做真实模型来使用。
另一种呢叫做选择性贝叶斯模型，平均它是预先选定一组模型。
啊，在所有的假设空间里预先选定一组模型，把搜索的范围限定在人为选定的这组模型当中啊，实际上也是挑出一组比较像的啊，从这里面来做出选择。
那么关于贝叶斯结构学习更多的细节啊，你可以查阅资料，了解它的思想和方法，并在这里呢分享你的见解。