概率图模型

概率图模型是之前一直搁置的内容，然而躲得过初一躲不过十五，看葫芦书时发现其中有整整一章关于概率图，方才意识到概率图模型的重要性，回过头来重新补上这部分内容。

概率图模型（Probabilistic Graphical Model,PGM），简称图模型，是指一种用图结构来描述多元随机变量之间条件独立关系的概率模型 。给研究高维空间中的概率模型带来了很大的便捷性。

对于一个 维随机向量 ，其联合概率为高维空间中的分布，一般难以直接建模。假设每个变量为离散变量并有 个取值，在不作任何独立假设条件下，则需要 个参数才能表示其概率分布（因为我们需要给出每一组可能的 的概率，共 种可能，由于概率和为1因此在此基础上减1）。不难看出，参数数量是指数级的，这在实际应用中是不可接受的。

一种有效减少参数量的方法是 独立性假设 。将 维随机向量的联合概率分解为 个条件概率的乘积：

其中 表示变量 的取值。如果某些变量之间存在条件独立，其参数量就可以大幅减少。

假设有四个二值变量 ，在不知道这几个变量依赖关系的情况下以用一个联合概率表来记录每一种取值的概率需要 个参数。假设在已知 时 和 独立，即有：

同理：

在已知 和 时 也和 独立，即有：

那么其联合概率 可以分解为：

是 个局部条件概率的乘积。如果分别用 个表格来记录这 个条件概率的话，只需要 个独立参数。

当概率模型中的变量数量比较多时，其条件依赖关系也比较复杂。我们可以使用图结构的方式将概率模型可视化，以一种直观、简单的方式描述随机变量之间的条件独立性的性质，并可以将一个复杂的联合概率模型分解为一些简单条件概率模型的组合。下图给出了上述例子中 个变量之间的条件独立性的图形化描述。

图模型有三个基本问题 ：

很多机器学习模型都可以归结为概率模型，即建模输入和输出之间的条件概率分布。因此，图模型提供了一种新的角度来解释机器学习模型，并且这种角度有很多优点，比如了解不同机器学习模型之间的联系，方便设计新模型等。

图由一组节点和节点之间的边组成。在概率图模型中，每个节点都表示一个随机变或一组随机变量，边表示这些随机变量之间的概率依赖关系 。

常见的概率图模型可以分为两类向图模型和无向图模型。有向图模型的图结构为有向非循环图，如果两个节点之间有连边，表示对于的两个变量为 因果关系 。无向图模型使用无向图来描述变量之间的关系。每条边代表两个变量之间有 概率依赖关系，但是并不一定是因果关系 。

有向图模型，也称贝叶斯网络（Bayesian Network）或信念网络（Belief Network），是指用有向图来表示概率分布的图模型。

贝叶斯网络 ： 对于一个随机向量 和一个有 个节点的有向非循环图 ， 中的每个节点都对应一个随机变量，可以是可观测的变量，隐变量或是未知参数。 中的每个连接 表示两个随机变量 和 之间具有非独立的因果关系。 表示变量 的所有父节点变量集合，每个随机变量的局部条件概率分布（local conditional probability distribution）为 。

若 的联合概率分布可以分解为每个随机变量 的局部条件概率的连乘形式，即：

那么 构成了一个 贝叶斯网络 。

条件独立性 ：在贝叶斯网络中，如果两个节点是直接连接的，它们肯定是非条件独立的直接因果关系。 父节点是“因”，子节点是“果” 。

如果两个节点不是直接连接的，但是它们之间有一条经过其它节点的路径来连接，那么这两个节点之间的条件独立性就比较复杂，例如：

(a)(b)(c)(d)分别代表 间接因果关系、间接果因关系、共因关系、共果关系 。

局部马尔可夫性质 ：对一个更一般的贝叶斯网络，其局部马尔可夫性质为： 每个随机变量在给定父节点的情况下，条件独立于它的非后代节点 。

其中 为 的非后代变量。

一种简单的参数化模型为Sigmoid信念网络。Sigmoid信念网络种变量取值为 ，对于变量 和它的父节点集合 ，条件概率分布表示为：

其中 是Logistic sigmoid函数， 是可学习的参数。假设变量 的父节点数量为 ，如果使用表格来记录条件概率需要 个参数，如果使用参数化模型只需要 个参数。如果对不同的变量的条件概率都共享使用一个参数化模型，其参数数量又可以大幅减少。

值得一提的是Sigmoid信念网络与Logistic回归模型都采用Logistic函数来计算条件概率。如果假设Sigmoid信念网络中只有一个叶子节点，其所有的父节点之间没有连接，且取值为实数，那么sigmoid信念网络的网络结构和Logistic回归模型类似，如图所示。

这两个模型区别在于Logistic回归模型中的 作为一种确定性的参数，而非变量。因此Logistic回归模型只建模条件概率 ，是一种判别模型，而Sigmoid信念网络建模 ，是一种生成模型 。

朴素贝叶斯分类器是一类简单的概率分类器，在强（朴素）独立性假设的条件下运用贝叶斯公式来计算每个类别的后验概率。

给定一个有 维特征的样本 和类别 ，类别的后验概率为：

其中 是概率分布的参数。

朴素贝叶斯分类器中，假设在给定 的情况下 之间条件独立，即 。下图给出了朴素贝叶斯分类器的图形表示。

条件概率分布 可以分解为：

其中 是 的先验概率分布的参数， 是条件概率分布 的参数。若 为连续值， 可以用高斯分布建模。若 为离散值， 可以用多项分布建模。

虽然朴素贝叶斯分类器的条件独立性假设太强，但是在实际应用中，朴素贝叶斯分类器在很多任务上也能得到很好的结果，并且模型简单，可以有效防止过拟合 。

隐马尔科夫模型是一种含有隐变量的马尔可夫过程。下图给出隐马尔可夫模型的图模型表示。

隐马尔可夫模型的联合概率可以分解为：

其中 为输出概率， 为转移概率， 分别表示两类条件概率的参数。

无向图模型，也称为马尔可夫随机场或马尔科夫网络，是一类用无向图来描述一组具有局部马尔可夫性质的随机向量 的联合概率分布的模型。

马尔可夫随机场 ：对于一个随机向量 和一个有 个节点的无向图 （可有循环）， 中节点 表示随机变量 ， 。如果 满足 局部马尔可夫性质，即一个变量 在给定它的邻居的情况下独立于所有其它变量 ：

其中 为变量 的邻居集合， 为除 外其它变量的集合，那么 就构成了一个马尔可夫随机场。

无向图的马尔可夫性 ：无向图中的马尔可夫性可以表示为：

其中 表示除 和 外的其它变量。

上图中由马尔可夫性质可以得到： 和 。

团 ： 由于无向图模型并不提供一个变量的拓扑顺序，因此无法用链式法则对 进行逐一分解 。无向图模型的联合概率一般以全连通子图为单位进行分解。无向图中的一个全连通子图，称为团（Clique），即团内的所有节点之间都连边。在所有团中，如果一个团不能被其它的团包含，这个团就是一个 最大团（Maximal Clique） 。

因子分解 ：无向图中的的联合概率可以分解为一系列定义在最大团上的非负函数的乘积形式。

Hammersley ­Clifford定理 ：如果一个分布 满足无向图 中的局部马尔可夫性质，当且仅当 可以表示为一系列定义在最大团上的非负函数的乘积，即：

上式也称为 吉布斯分布 。其中 为 中的最大团集合， 是定义在团 上的 势能函数 ， 是配分函数（Partition Function），用来将乘积归一化为概率形式。

其中 为随机向量 的取值空间。

无向图模型与有向图模型的一个重要区别是有配分函数 。配分函数的计算复杂度是指数级的，因此在推断和参数学习时都需要重点考虑。

由于势能函数必须为正的，因此我们一般定义为：

其中 为 能量函数 。这里的负号是遵从物理上的习惯，即能量越低意味着概率越高。

因此无向图上定义的概率分布可以表示为：

这种形式的分布又称为 玻尔兹曼分布（Boltzmann Distribution） 。任何一个无向图模型都可以用上式来表示其联合概率。

势能函数一般定义为：

其中函数 为定义在 上的特征向量， 为权重向量。这样联合概率 的对数形式为：

其中 代表所有势能函数中的参数 。这种形式的无向图模型也称为 对数线性模型或最大熵模型 。

如果用对数线性模型来建模条件概率 ，有：

其中 。这种对数线性模型也称为 条件最大熵模型或softmax回归模型 。

条件随机场是一种直接建模条件概率的无向图模型 。

和条件最大熵模型不同，条件随机场建模的条件概率 中， 一般为随机向量，因此需要对 进行因子分解。设条件随机场的最大团集合为 ，条件概率为：

其中 为归一化项。

一个最常用的条件随机场为图(b)中所示的链式结构，其条件概率为：

其中 为状态特征，一般和位置 相关， 为转移特征，一般可以简化为 并使用状态转移矩阵来表示。

无向图模型可以表示有向图模型无法表示的一些依赖关系，比如循环依赖；但它不能表示有向图模型能够表示的某些关系，比如因果关系。

以图(a)中的有向图为例，其联合概率分布可以分解为：

其中 和四个变量都相关。如果要转换为无向图， 需要将这四个变量都归属于一个团中。因此需要将 的三个父节点之间都加上连边，如图(b)所示。这个过程称为 道德化（Moralization） 。转换后的无向图称为 道德图（Moral Graph） 。

在道德化的过程中来有向图的一些独立性会丢失 ，比如上面 在道德图中不再成立。

在图模型中，推断（Inference）是指在观测到部分变量 时，计算其它变量的某个子集 的后验概率 。

假设一个图模型中，除了变量 外，其余变量表示为 。根据贝叶斯公式有：

因此， 图模型的推断问题可以转换为求任意一个变量子集的边际概率分布问题 。

在图模型中用的推断方法可以分为 精确推断 和 近似推断 两类。

以上图为例，假设推断问题为计算后验概率 ，需要计算两个边际概率 和 。

根据条件独立性假设，有：

假设每个变量取 个值，计算上面的边际分布需要 次加法以及 次乘法。

根据乘法的分配律，边际概率 可以写为：

这样计算量可以减少到 次加法和 次乘法。

这种方法是利用 动态规划 的思想，每次消除一个变量，来减少计算边际分布的计算复杂度，称为 变量消除法 。

信念传播（Belief Propagation,BP）算法，也称为和积（Sum-Product）算法或消息传递（Message Passing）算法，是将变量消除法中的和积（Sum-Product） *** 作看作是消息，并保存起来，这样可以节省大量的计算资源。

以上图所示的无向马尔可夫链为例，其联合概率 为：

其中 是定义在团 的势能函数。

第 个变量的边际概率 为：

假设每个变量取 个值，不考虑归一化项，计算上述边际分布需要 次加法以及 次乘法。

根据乘法的分配律际概率 可以通过下面方式进行计算：

其中 定义为变量 向变量 传递的消息， 是关于变量 的函数，可以递归计算：

为变量 向变量 传递的消息，定义为：

边际概率 的计算复杂度减少为 。如果要计算整个序列上所有变量的边际概率，不需要将消息传递的过程重复 次，因为其中每两个相邻节点上的消息是相同的。

信念传播算法也可以推广到具有树结构的图模型上。如果一个有向图满足任意两个变量只有一条路径（忽略方向），且只有一个没有父节点的节点，那么这个有向图为树结构，其中唯一没有父节点的节点称为根节点。如果一个无向图满足任意两个变量只有一条路径，那么这个无向图也为树结构。在树结构的无向图中任意一个节点都可以作为根

能。训练数据集是用于学习的示例的数据集，在机器学习的第七章贝叶斯分类器中写道，只需要通过对训练样本计数，根据贝叶斯网定义的联合概率分布，就可以估计出每个结点的条件概率表。条件概率表是指将多组相关事件发生关系概率进行对比的概率表，通常在三种以上互相关联的条件出现时，需要使用条件概率表。

什么贝叶斯定理、贝叶斯方法、贝叶斯网络这种，外行人一听头就疼，这完全没有乘法分配律乘法结合律来的亲民啊！实际上，他确实不亲民（摊手）

那我们就从如何着手去处理贝叶斯网络为目标， 好好看，好好学 （这是文章基于的框架结构，在此基础上进行了补充说明）。

咱先整抓球，一个不透明的带子，里面有4个除了颜色完全相同的球：2红1绿1蓝。此时你去随手抓，那问你抓到各个颜色球的概率是多少？我想是个正常人都会说：那不50%、25%、25%？这是不论你取多少次，概率θ始终不变的事件，即不随观察结果X的变化而变化。

显然啊！那不然会是什么呢？

这种观点长期统治着人们，或者说，统治着正常人，这叫频率派观点。直到有个叫Thomas Bayes的人出来搅局。

贝叶斯不介绍了，生前民间学术“屌丝”，身后颠覆了概率史啊。这里说一下他最终发表的一篇多年后轰动世界的文章：An essay towards solving a problem in the doctrine of chances（机遇理论中一个问题的解）

回到上面这个问题，袋子里取红球的概率θ是多少？正常人都说50%，贝叶斯说“NO！”。他认为取的红球的概率是个不确定的值，因为其中含有机遇的成分。

是不是不好理解了？那我们换个例子来讲（这个抓球有什么机遇，我也不懂，但大佬都以这些开头，所以咱换个例子）

78泽干了两年程序员，现在想自己创业开个外包公司。这个结果无非“走向人生巅峰”和“欠一屁股债”，要么成功要么失败。现在我们大家来估计一下他成功的概率有多大？你们可能会说：“这谁啊，两年就创业，吓他个鬼，不可能的。成功几率最多5%。”而我对他的为人比较了解，他有想法，有方法，有思路，还有毅力，能吃苦，还有情调，有凝聚力，还为他人着想等，那我就估计他成功的概率有75%以上。

这种不同于最开始的“非黑即白、非0即1”的思考方式，就是贝叶斯式的思考方式。

频率派把需要推断的参数θ看作是固定的未知常数，即概率虽然是未知的，但最起码是确定的一个值，同时，样本X是随机的，即不管球几红几绿，事件的概率θ一定。所以频率派重点研究样本空间，大部分的概率计算都是针对样本X的分布；

贝叶斯派认为参数θ是随机变量，而样本X是固定的。由于样本X固定，所以他们重点研究的是参数θ的分布。

这样，贝叶斯派提出了一个思考问题的固定模式：

先验分布π（θ）+ 样本信息X ==> 后验分布π（θ|x）

这意味着，新观察到的样本信息将修正人们以前对事物的认知。换而言之，在得到新的样本信息前，人们对θ的认知是先验分布π（θ），在得到新的样本信息X后，人们对θ的认知受其影响变为π（θ|x）。

先验信息一般来源于经验和历史资料，比如在S7以前的SKT VS RNG，解说总会根据历年比赛结果进行一个胜负的预判来相应解说。但从S7,S8这两个赛季后，发现韩国队不行了！那么现在你再看SKT VS RNG，可就不一定了不是吗？那是不是就是X影响了π（θ）得到了π（θ|x）。

后验分布π（θ|x）一般也认为是在给定样本X的情况下的θ条件分布，而使π（θ|x）达到最大的值θMD，这个θMD称谓最大后验估计，类似于统计学的极大似然估计。

这里插曲一下，似然和概率，很多人其实都不明白这是啥区别。似然（likelihood）在非正式场合中和概率（probability）几乎相同。但在统计学中完全不同。概率是在特定环境下某件事发生的可能性，也就是结果没有产生之前依据环境所对应的参数来预测某件事情发生的可能性；而似然正好相反，是在确定的结果下去推测产生这个结果的可能环境（参数）。

结果和参数相互对应的时候，似然和概率在数值上是相等的。 了解更多似然，点击这里

当然除了上述思考模式，还有举世闻名的贝叶斯定理。

先回顾几个名词

条件概率（又称后验概率）就是事件A在另外一个事件B已经发生的条件下发生的概率P（A|B）：

自己花几个圆圈就能推导出这个公式了。

联合概率表示两个事件共同发生的概率：

边缘概率（又称先验概率）是某个事件发生的概率。边缘概率是这样得到的：在联合概率中，把最终结果中那些不需要的事件通过合并成它们的全概率从而消去它们（对离散随机变量用求和得全概率，连续随机变量用积分得全概率），这称为边缘化（marginalization），比如A的边缘概率表示为P（A）,B的边缘概率表示为P（B）。

现在考虑问题：P（A|B）是在B发生的情况下A发生的可能性。

（1）首先，B发生之前，对事件A发生的基本概率判断为A的先验概率P（A）；

（2）其次，事件B发生后，我们对事件A发生概率重新评估，称为A的后验概率P（A|B）；

（3）类似，事件A发生前，对B的先验概率P（B）；

（4）事件A发生后，B后验概率P（B|A）。

贝叶斯定理如下：

推导证明如下：

上式两边同时除以P（B），若P（B）非零，变得到贝叶斯定理公式表达式。

上述为传统的贝叶斯公式写法，还有另一种写法，称之为贝叶斯推断。

对条件概率公式进行变形，得到如下形式：

P（A）称为先验概率，P（A|B）为后验概率，而P（B|A）/P（B）称之为可能性函数（likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

贝叶斯推断的含义：我们先预估一个先验概率，然后加入实验结果，看这个实验到底是增强还是削弱了先验概率，由此得到更接近事实后验概率。

这里，可能性函数>1，意味着先验概率被增强，事件A的发生可能性变大；可能性函数=1,意味着B事件无助于判断事件A的可能性；可能性函数<1，意味着先验概率被削弱，事件A的可能性变小。

举例加深理解：

1水果糖问题

两个一模一样的碗，一号碗中有30颗水果糖和10颗巧克力，二号碗有水果糖和巧克力各20颗。现在随机选择一个碗，从中摸出一颗糖，发现时水果糖。请问这个水果糖来自一号碗的概率是多少？

解：我们假定，H1表示碗一，H2表示碗二，有条件已知P（H1）=P（H2），即在取出水果糖之前，这两个碗被选中的概率相同。因此P（H1）=05，此为先验概率。

再假定E表示水果糖，所以问题变为已知E的情况下，来自碗一的概率有多大：求P（H1|E）。我们把这个称为后验概率，即E事件发生后，对P（H1）的修正。

根据条件概率公式，得到

已知：P（H1）=05，P（E|H1）=075，那么求出P（E）就可以得到答案，根据全概率公式（推导根据条件概率公式推就行了）

得到：

将已知带入得P（E）=0625，最后将结果带入原方程，得到P（H1|E）=06，也就是说取出水果糖后，H1事件的可能性得到了增强（P（E|H1）/P（E）=075/0625=12>1）。

贝叶斯公式还有一个最经典也是目前最广泛的应用：拼音纠错，谷歌的拼音检查就是基于贝叶斯方法。

《人工智能：现代方法》作者之一Peter Norvig曾写一篇介绍如何写一个拼写检查的文章（ 原文 ），使用的也是贝叶斯方法。

用户输入一个单词，可能拼写正确，也可能拼写错误。如果把拼写正确的情况记做c，错误记做w，那么拼写检查要做的事情就是：在发生w的情况下，试图推断出c，换而言之，就是已知w，然后在若干个备选方案中，找出可能性最大的那个c，即求P（c|w）的最大值。

由于对于所有备选的c来说，对应的都是同一个w，所以它们的P（w）相同，因此我们只需要最大化P（w|c）P（c）。

其中P（c）表示某个正确的单词出现的“概率”，它可以用“频率”代替。如果我们有一个足够大的文本库，那么这个文本库中每个单词的出现频率，就相当于它的发生概率。某个词的出现频率越高，P（c）就越大。比如在你输入一个错误的单词“tes”的时候，系统更倾向于“tea”，而不是“tee”，因为tea更常见。

当然这其中要是深究，还有更多的可能性，比如说错误字母与正确字母在键盘上的位置，也许你是按错了所以会拼错，但实际上你要拼写的单词就是那个频率低的单词，是不是？在这里，初学，咱先放一放。

P（w|c）表示在试图拼写c的情况下，出现拼写错误w的概率。为了简化问题，假定两个单词在字形上越接近，就越有可能拼错，P（w|c）就越大。举例来说，相差一个字母的拼法，就比相差两个字母的拼法，发生概率越高。你想拼写“july”，错误拼成“julw”的可能性就比错拼成“jullw”高很多。一般把这种问题称为“编辑距离”。

贝叶斯网络（Bayesian Network），又称信念网络（Belief Network），或有向无环图模型，十一中概率图模型。它是一种模拟人类推理过程中因果关系的不确定性处理模型，其网络拓扑结构是一个有向无环图（DAG，direvted acyclic graphical）。

贝叶斯网路中节点表示随机变量，认为有因果关系（或非条件独立）的变量或命题则用剪头来连接。

例如，假设节点E直接影响到节点H，即E-->H，则用从E指向H的箭头建立节点E到节点H的有向弧（E，H），权值（即连接强度）用条件概率P（H|E）来表示。

简而言之，把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖，用圈表示随机变量（random variables），用箭头表示条件依赖（conditional dependencies）。

关于随机变量，这里不同于普通公式中的x，z那种未知数，之前专门研究过，但是参考的网址找不到了。随手记了一些笔记，分享一下（字丑）：

令G=（I,E）表示一个有向无环图（DAG），其中I代表图形中所有的节点的集合，而E代表有向连接线段的集合，且令X=（Xi），i∈I为其有向无环图中某一节点i所代表的随机变量，若节点X的联合概率可以表示成：

则称X为相对于一有向无环图G的贝叶斯网络，其中，pa（i）表示节点i的“因”，也可以理解为“父节点”。

给订如下图所示的一个贝叶斯网络：

由图可知：

（1）x1，x2，，x7的联合分布为：

（2）x1和x2独立（head-to-head）；

（3）x6和x7在x4给订的条件下独立（tail-to-tail）。

根据上图，（1）很好理解，（2、3）所述的条件独立是什么意思呢？其实2、3点是贝叶斯网络中3个结构的其中两种。为了说清楚这个问题，需要引入D-Separation（D-分离）这个概念。

D-Separation是一种用来判断变量是否条件独立的图形化方法。换而言之，对于一个DAG，D-Separation方法可以快速的判断出两个节点之间是否条件独立。

有：P（a，b，c）=P（a） P（b） P（c|a，b）成立，化简如下：

在c未知的条件下，a、b被阻断（blocked），是独立的，称之为head-to-head条件独立，对应本节图1的x1，x2独立。

考虑c未知和已经两种情况：

1、在c未知的时候，有：P（a，b，c）=P（c）P（a|c）P（b|c），此时，无法得出P（a，b）=P（a）P（b），即c未知时，a、b不独立；

2、在c已知的时候，有：P（a，b|c）=P（a，b，c）/ P（c），然后将P（a，b，c）=P（c）P（a|c）P（b|c）带入此式中，得到：P（a，c|c）=P（a，b，c）/ P（c）=P（c）P（a|c）P（b|c）/P（c）=P（a|c）P（b|c），即c已知时，a、b独立。

所以，在c给定的条件下，a、b被blocked，式独立的，称之为tail-to-tail条件独立，对应本节图1中“x6，x7在x4给定的条件下独立”。

分c未知和已知两种情况：

1、c未知时，有：P（a，b，c）=P（a）P（c|a）P（b|c），但无法推出P（a，b）=P（a）P（b），即c未知时，a、b不独立；

2、c已知时，有：P（a，b|c）=P（a，b，c）/ P（c），且根据P（a，c）=P（a）P（c|a）=P（c）P（a|c），可化简得到：

所以在给定c的条件下，a、b被blocked，是独立的，称之为head-to-tail条件独立。

head-to-tail其实就是一个链式网络，在xi给定的条件下，xi+1的分布和x1，x2，，xi-1条件独立。这意味着什么？这说明xi+1的分布状态只和xi有关，和其他变量都无关！通俗一点说，当前状态只跟上一状态有关，跟上上次或上上上上上上上次状态都无关！这种顺次演变的随机过程，就叫做马尔科夫链（Markov chain）。有：

将上述节点推广到节点集，则：对于任意的节点集A,B,C，考察所有通过A中任意节点到B中任意节点的路径，若要求A，B条件独立，则需要所有的路径都被blocked，即满足下列两个前提之一：

A和B的“head-to-tail”和“tail-to-tail”路径都通过C；

A和B的“head-to-head”路径不通过C及C的子孙；

最后举例说明上述D-Separation的3种情况（即贝叶斯网络的3种结构形式）：

Factor Graph是概率图的一种，概率图有多重，最常见的就是Bayesian Network和Markov Random Fields（马尔科夫随机场）。

在概率图中，求某个变量的边缘分布是最常见的问题。这个问题有很多种求解方法，其中之一就是可以把Bayesian Network和Markov Random Fields转换成Factor Graph，然后用sum-product算法求解。

以下图为例：

对于上图，在一个人已经呼吸困难（dyspnoea）的情况下，其抽烟（smoking）的概率是多少？

P（smoking | dyspnoea = yes）= ？

继续推算如下：（这里我就不自己码了，好多箭箭头有点麻烦的，还是用原图简单明了）

对上述推导过程作解释如下：

1第二行：对联合概率关于b，x，c求和（在d=1的条件下），从而消去b，x，c，得到s和d=1的联合概率；

2第三行：最开始，所有变量都在sigma（d=1，b，x，c）的后面，但由于P（s）跟“d=1，b，x，c”都没关系，可以提到式子的最前面。而且P（b|s）和x、c没关系，所以也可以把它提出来，放到sigma（b）后，从而式子的右边剩下sigma（x）和sigma（c）。

（ps：这块看能看明白，至于为什么sigma（x）和sigma（c）不能写在一起，我也，哈哈哈~等之后再来补空挡，这里先记着。）

上图中Variable elimination表示的是变量消除的意思。为此引入因子图的概念。

定义异常的晦涩难懂，你光看着名字你就摸不着头脑，所以咱先通俗来讲，所谓因子图就是对函数进行因式分解得到的一种概率图。一般内含两种节点：变量节点和函数节点。众所周知，一个全局函数通过因式分解能够分解为多个局部函数的乘积，这些局部函数和对应的变量关系就体现在因子图上。

举例说明，现有一全局函数，其因式分解方程为：

其中fA、fB、fC、fD、fE为各函数，表示变量之间的关系，可以是条件概率也可以是其他关系（如Markov Random Fields中的势函数）。

其因子图为：

在因子图中，所有的顶点不是变量节点就是函数节点，边线表示他们之间的函数关系。

提及马尔科夫随机场，就再补充一些概念：

我们知道，有向图模型，称之为贝叶斯网络。但有些情况下，强制对某些节点之间的边增加方向是不合适的。使用没有方向的无向边，形成了无向图模型（Undirected Graphical Model,UGM），又被称为马尔科夫随机场或者马尔科夫网络（MRF or Markov Network）。

回归本文主旨，首先我们举例说明如何把贝叶斯网络（和MRF），以及把马尔科夫链、隐马尔科夫模型转换成因子图，以上图为例，根据各个变量对应的关系，可得：

其对应的因子图为（以下两种皆可）：

有上述例子总结出贝叶斯网络构造因子图的方法：

·贝叶斯网络中的一个因子对应因子图中的一个节点

·贝叶斯网络中的每一个变量在因子图上对应边或者半边

·节点g和边x相连当且仅当变量x出现在因子g中

我把绘图的思考过程写下来，你跟着画一遍就会明白：

1找出已存在的先验概率，图中为P（u）和P（w），那么因子对应节点，所以先画出P（u）和P（w）的节点，就是两个框；然后因子P（u）中出现的变量是u，那么由P（u）节点引出一条边，这条边就是u，同理P（w）引出w边；

2发现因子P（x|u，w）知，x是u和w下的条件概率，故做节点P（x|u，w），然后将边u和w与之相连，并有该节点引出x边；

3有因子P（y|x）和P（z|x）发现基于条件x引出两个变量y和z，那么此时需要将X边拆分成两条边（我猜想这个可能就叫半边，没有专门去查），并分别接入到P（y|x）和P（z|x）节点，再由各自节点对应引出y边与z边，结束作图。

对马尔科夫链转换的因子图和隐马尔科夫模型转换而成的因子图，做法相同。这里等以后专门讲马尔科夫的时候再仔仔细细说。这里把图贴出来给大家了解一下（应该可以很快看明白）：

到这，我们算把因子图讲透了，现在看看维基百科上是这样定义因子图的：将一个具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图。

怎么样，这样直接看定义，你懂吗？

我们已经学会如何画因子图了，下面来思考这样一个问题：如何由联合概率分布求边缘概率分布？

这里给出公式：

对Xk以外的其他变量的概率求和，最终剩下Xk的概率。这就是该定义的原理。你明白了吗？我有点迷糊反正，可能说成话好理解，但是这个公式未免也太模糊了点（f真的万能）。

其实可以这么理解：

如果有：

那么：

就是说把除了xk以外的所有随机变量的概率求出来，这个f就表示一个多项式，是关于f括号里面x的。然后概率上面有一横，表示的是不发生概率。

好吧，其实这块我也没太明白，先埋个坑，以后回来填。

现在假定我们要计算：

同时，f能被分解成如下因子图（看到这里你大概能明白一点我上面说的f是多项式是什么意思了）：

我们都知道乘法分配律：a b + a c = a (b + c)，等号左边两乘一加，等号右边一加一乘，效率不用多说。现在我们就借助分配律的思想，把因子图给分配咯！

怎么看公因子很简单，例如X3是有f1（x1）和f2（x2）通过f3这个函数得来的（即因子图那节所述，P（x3|x1，x2）），而之后的f5需要x3做因子（条件），所以自然左边这个框就成了公因子。

因为变量的边缘概率等于所有与他相连的函数传递过来的消息的乘积，所以计算得到：

观察上述计算过程，可以发现类似于“消息传递”的观点，且总共有两个步骤：

1对于f的分解图，根据左框（蓝色）、右框（红色）所包围的两个box外面的消息传递：

2根据红蓝框为主的两个box内部的消息传递：

看上图消息传递的方向（箭头），根据

我们可以推导出：

这样就将一个概率分布写成了两个因子的乘积，而这两个因子可以继续分解或者通过已知条件得到。这种利用消息传递的观念计算概率的方法就是sum-product算法。基于因子图可以用该算法高效地求出各个变量的边远分布。

sum-product算法，又称belief propagation，有两种消息：

一种是变量（variable）到函数（function）的消息 如下图所示：

此时，

另一种是函数到变量的消息 如下图所示：

此时，

如果因子图是无环图，则一定可以准确地求出任意一个变量的边远分布；如果是有环图，则无法用该算法准确求出边远分布。解决方法有3个：

1、删除贝叶斯网络中的若干边，使其不含有无向环

2、重新构造没有环的贝叶斯网络

3、选择loopy belief propagation算法（sum-product的递归版算法），该算法选择环中某个消息，随机赋初值，然后用sum-product算法，迭代下去，因为环的存在所以一定会达到赋值的消息，然后更新该消息，继续迭代，直至没有消息改变为止。缺点是不能确保收敛。

最后，该算法有个类似的max-product算法，弄懂了sum的，max的几乎完全一样。另这两个算法也能够应用到隐马尔科夫模型（hidden Morkov models）上。至于马尔科夫系列，下个专题咱再见~

在人中，有300个TF结合在核心启动子区域；有1500个结合在基因其他区域，可以调节一系列基因

图示

ChIP-seq:

DNase-seq

ATAC-seq (Assay for transposase- accessiblechromatin using sequencing)

文章原图

Some TFs almost always bind in proximal promoter regions

Others bind to many regions

Position weight matrix (PWM)

Given a collection of genes that are likely to be regulated by the same TFs (or orthologous genes across different species — methods based on phylogenetic footprinting principles), find the TF-binding motifs in common

但是问题是不知道motif是什么，找不到相关的基因，而且如何排除背景干扰

比较保守的非编码区域可能有

Expectation-Maximization

In each iteration, it learns the PWM model and identifies examples of the matrix (sites in the input sequences) 在每一次迭代中，学习一个PWMmodel然后再通过输入的序列进行比对

MEME works by iteratively refining PWMs and identifying sites for each PWM(不同的迭代直到找到一个最合适的PWM)

The intuitive idea is as follows:

Start with a k-mer seed (random or specified)通常是6个

Build a PWM by incorporating some of background frequencies 根据背景生成一个初始的PWM

For every k-mer in the input sequences, identify its probability given the PWM model 计算k-mer在输入序列中给出PWM出现的概率

Calculate a new PWM, based on the weighted frequencies of all k-mers in the input sequences

根据input序列中k-mer出现频率的权重更新PWM

例子1

11

12

13

首先设置model, 然后经历Estep和Mstep,找到合适的PWM

然后将PWM进行极大似然转换并取log

然后看输入序列中出现该motif的概率

人的大多数结合位点都是在内含子和基因间区

Stronger sites are not closer to differentially regulated genes (not necessarily more functional)

Majority of functional sites not conserved

目前很难预测靶基因

核心思想

TF在基因组上的结合其实是一个随机过程，基因组的每个位置其实都有机会结合某个TF，只是概率不一样

peak出现的位置，是TF结合的热点，而peak-calling就是为了找到这些热点。

热点：位置多次被测得的read所覆盖（我们测的是一个细胞群体，read出现次数多，说明该位置被TF结合的几率大）。

read出现多少次算多：假设TF在基因组上的分布没有任何规律，测序得到的read在基因组上的分布也必然是随机的，某个碱基上覆盖的read的数目应该服从二项分布。

当n很大，p很小时，二项分布可以近似用泊松分布替代

\lambda 是泊松分布唯一的参数，n是测序得到的read总数目，l是单个read的长度，s是基因组的大小。

我们可以算出在某个置信概率（如000001）下，随机情况下，某个碱基上可以覆盖的read的数目的最小值，当实际观察到的read数目超过这个值（单侧检验）时，我们认为该碱基是TF的一个结合热点。反过来，针对每一个read数目，我们也可以算出对应的置信概率P。

实际情况由于测序、mapping过程内在的偏好性，以及不同染色质间的差异性，相比全基因组，某些碱基可能内在地会被更多的read所覆盖，这种情况得到的很多peak可能都是假的。

MACS考虑到了这一点，当对某个碱基进行假设检验时，MACS只考虑该碱基附近的染色质区段（如10k），此时，上述公式中n表示附近10k区间内的read数目，s被置为10k。当有对照组实验（Control，相比实验组，没有用抗体捕获TF，或用了一个通用抗体）存在时，利用Control组的数据构建泊松分布，当没有Control时，利用实验组，稍大一点的局部区间（比如50k）的数据构建泊松分布。

read只是跟随着TF一起沉淀下来的DNA fragment的末端，read的位置并不是真实的TF结合的位置。

在peak-calling之前，延伸read是必须的。不同TF大小不一样，对read延伸的长度也理应不同。

我们知道测得的read最终其实会近似地平均分配到正负链上，这样对于一个TF结合热点而言，read在附近正负链上会近似地形成“双峰”。

MACS会以某个window size扫描基因组，统计每个window里面read的富集程度，然后抽取（比如1000个）合适的（read富集程度适中，过少，无法建立模型，过大，可能反映的只是某种偏好性）window作样本，建立“双峰模型”。

最后，两个峰之间的距离就被认为是TF的长度D，每个read将延伸D/2的长度

If we are given a set of ChIP-seq peaks, how to identify motif for the TF— use MEME

To find out what the sequence motif resembles — use TomTom

Use known motif to search peak regions — use FIMO

Study common biological pathways or functions of potential target genes of the TF — use GREAT

刘晓乐实验室ChIP-seq数据分析流程

定义：包括一个有向无环图（DAG）和一个条件概率表集合。DAG中每一个节点表示一个随机变量，可以是可直接观测变量或隐藏变量，而有向边表示随机变量间的条件依赖；条件概率表中的每一个元素对应DAG中唯一的节点，存储此节点对于其所有直接前驱节点的联合条件概率

性质：每一个节点在其直接前驱节点的值制定后，这个节点条件独立于其所有非直接前驱前辈节点

类似Markov过程，贝叶斯网络可以看做是Markov链的非线性扩展。这条特性的重要意义在于明确了贝叶斯网络可以方便计算联合概率分布。

通过基因表达来推测网络

经典文章

主要过程

分析过程要给已经构建的相关性矩阵取逆

当样本很小时无法进行转换要使用lasso算法

关键在于如何确定公式中的lamada

这样不需要所有节点之间都有边

贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能性，如给定样本属于一个特定类的概率。

朴素贝叶斯分类[2]假定了一个属性值对给定类的影响独立于其它属性的值，这一假定称作类条件独立。

设定数据样本用一个 n 维特征向量X={x1，x2，，xn}表示，分别描述对n 个属性A1，A2，，An样本的 n 个度量。假定有m个类 C1，C2，，Cm 。给定一个未知的数据样本 X（即没有类标号），朴素贝叶斯分类分类法将预测 X 属于具有最高后验概率（条件 X 下）的类，当且仅当P(Ci | X)> P(Cj | X)，1≤j≤m，j≠i 这样，最大化P(Ci | X)。其中P(Ci | X)最大类Ci 称为最大后验假定，其原理为贝叶斯定理：

公式(1)

由于P(X) 对于所有类为常数，只需要P(X | Ci)P(Ci)最大即可。并据此对P(Ci| X)最大化。否则，最大化P(X | Ci)P(Ci)。如果给定具有许多属性的数据集，计算P(X | Ci)P(Ci)的开销可能非常大。为降低计算P(X| Ci )的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系，这样，

公式(2)

概率，可以由训练样本估值：

(1) 如果Ak是分类属性，则P(xk|Ci)=sik/si其中sik是Ak上具有值xk的类Ci的训练样本数，而si是Ci中的训练样本数。

(2) 如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而

公式(3)

其中，给定类Ci的训练样本属性Ak的值， 是属性Ak的高斯密度函数，而 分别为平均值和标准差。

朴素贝叶斯分类算法(以下称为NBC)具有最小的出错率。然而，实践中并非如此，这是由于对其应用假定（如类条件独立性）的不确定性，以及缺乏可用的概率数据造成的。主要表现为：

①不同的检测属性之间可能存在依赖关系，如protocol_type，src_bytes和dst_bytes三种属性之间总会存在一定的联系；

②当连续值属性分布是多态时，可能产生很明显的问题。在这种情况下，考虑分类问题涉及更加广泛，或者我们在做数据分析时应该考虑另一种数据分析。

后一种方法我们将在以下章节详细讨论。

3 朴素贝叶斯的改进：核密度估计

核密度估计是一种普便的朴素贝叶斯方法，主要解决由每个连续值属性设为高斯分布所产生的问题，正如上一节所提到的。在[3]文中，作者认为连续属性值更多是以核密度估计而不是高斯估计。

朴素贝叶斯核密度估计分类算法（以下称K-NBC）十分类似如NBC，除了在计算连续属性的概率 时：NBC是使用高斯密度函数来评估该属性，而K-NBC正如它的名字所说得一样，使用高斯核密度函数来评估属性。它的标准核密度公式为

公式(4)

其中h=σ 称为核密度的带宽，K=g（x,0,1） ，定义为非负函数。这样公式（4）变形为公式（5）

公式(5)

在K-NBC中采用高斯核密度为数据分析，这是因为高斯密度有着更理想的曲线特点。图1说明了实际数据的概率分布更接近高斯核密度曲线。

图1 两种不同的概率密度对事务中数据的评估，其中黑线代表高斯密度，虚线为核估计密度并有两个不同值的带宽朴素贝叶斯算法在计算μc和σc时，只需要存储观测值xk的和以及他们的平方和，这对一个正态分布来说是已经足够了。而核密度在训练过程中需要存储每一个连续属性的值（在学习过程中，对名词性属性只需要存储它在样本中的频率值，这一点和朴素贝叶斯算法一样）。而为事例分类时，在计算连续值属性的概率 时，朴素贝叶斯算法只需要评估g一次，而核密度估计算法需要对每个c类中属性X每一个观察值进行n次评估，这就增加计算存储空间和时间复杂度，表1中对比了两种方法的时间复杂度和内存需求空间。

4 实验研究与结果分析

本节的目标是评价我们提出核密度评估分类算法对入侵审计数据分类的效果，主要从整体检测率、检测率和误检率上来分析。

表1 在给定n条训练事务和m个检测属性条件下，

NBC和K-NBC的算法复杂度

朴素贝叶斯 核密度

时间 空间 时间 空间

具有n条事务的训练数据 O(nm) O(m) O(nm) O(nm)

具有q条事务的测试数据 O(qm) O(qnm)

41 实验建立

在实验中，我们使用NBC与K-NBC进行比较。另观察表1两种算法的复杂度，可得知有效的减少检测属性，可以提高他们的运算速度，同时删除不相关的检测属性还有可以提高分类效率，本文将在下一节详细介绍对称不确定方法[4]如何对入侵审计数据的预处理。我们也会在实验中进行对比分析。

我们使用WEKA来进行本次实验。采用 KDDCUP99[5]中的数据作为入侵检测分类器的训练样本集和测试样本集，其中每个记录由41个离散或连续的属性(如：持续时间，协议类型等)来描述，并标有其所属的类型(如：正常或具体的攻击类型)。所有数据分类23类，在这里我们把这些类网络行为分为5大类网络行为（Normal、DOS、U2R、R2L、Probe）。

在实验中，由于KDDCUP99有500多万条记录，为了处理的方便，我们均匀从kddcupdatagz 中按照五类网络行为抽取了5万条数据作为训练样本集，并把他们分成5组，每组数据为10000条，其中normal数据占据整组数据中的985%，这一点符合真实环境中正常数据远远大于入侵数据的比例。我们首

先检测一组数据中只有同类的入侵的情况，共4组数据（DOS中的neptune，Proble中的Satan，U2R中的buffer_ overflow，R2l中的guess_passwd），再检测一组数据中有各种类型入侵数据的情况。待分类器得到良好的训练后，再从KDD99数据中抽取5组数据作为测试样本，分别代表Noraml-DOS，Normal-Probe，Normal-U2R，Normal-R2L，最后一组为混后型数据，每组数据为1万条。

42 数据的预处理

由于朴素贝叶斯有个假定，即假定所有待测属性对给定类的影响独立于其他属性的值，然而现实中的数据不总是如此。因此，本文引入对称不确定理论来对数据进行预处理，删除数据中不相关的属性。

对称不确定理论是基于信息概念论，首先我们先了解一下信息理论念，属性X的熵为：

公式(6)

给定一个观察变量Y，变量X的熵为:

公式(7)

P(xi )是变量X所有值的先验概率，P(xi|yi )是给定观察值Y，X的后验概率。这些随着X熵的降低反映在条件Y下，X额外的信息，我们称之为信息增益，

公式(8)

按照这个方法，如果IG(X|Y)＞IG(X|Y)，那么属性Y比起属性Z来，与属性X相关性更强。

定理：对两个随机变量来说，它们之间的信息增益是对称的。即

公式(9)

对测量属性之间相关性的方法来说，对称性是一种比较理想的特性。但是在计算有很多值的属性的信息增益时，结果会出现偏差。而且为了确保他们之间可以比较，必须使这些值离散化，同样也会引起偏差。因此我们引入对称不确定性，

公式(10)

通过以下两个步骤来选择好的属性：

①计算出所有被测属性与class的SU值，并把它们按降序方式排列；

②根据设定的阈值删除不相关的属性。

最后决定一个最优阈值δ，这里我们通过分析NBC和K-NBC计算结果来取值。

43 实验结果及分析

在试验中，以记录正确分类的百分比作为分类效率的评估标准，表2为两种算法的分类效率。

表2 对应相同入侵类型数据进行检测的结果

数据集

算法 DOS

(neptune) Proble

(satan) R2L

( guess_passwd) U2R

(buffer_overflow)

检测率 误检率 整体检测率 检测率 误检率 整体检测率 检测率 误检率 整体检测率 检测率 误检率 整体检测率

NBC 995 02 9979 983 01 9984 973 08 992 95 18 9821

K-NBC 995 02 9996 983 0 9996 973 02 9981 71 01 9976

SU+NBC 995 0 9996 983 01 9985 98 07 9924 9 11 9884

SU+K-NBC 995 0 9996 983 0 9996 987 02 9976 85 01 9981

根据表2四组不同类别的入侵检测结果，我们从以下三个方面分析：

（1）整体检测率。K-NBC的整体检测率要比NBC高，这是因为K-NBC在对normal这一类数据的检测率要比NBC高，而normal这一类数据又占整个检测数据集数的95%以上，这也说明了在上一节提到的normal类的数据分布曲线更加接近核密度曲线。

（2）检测率。在对DOS和PROBLE这两组数据检测结果，两个算法的检测率都相同，这是因为这两类入侵行为在实现入侵中占绝大部分，而且这一类数据更容易检测，所以两种算法的检测效果比较接近；针对 R2L检测，从表2可以看到，在没有进行数据预处理之前，两者的的检测率相同，但经过数据预处理后的两个算法的检测率都有了提高，而K-NBC的效率比NBC更好点；而对U2R的检测结果，K-NBC就比NBC差一点，经过数据预处理后，K-NBC的检测率有一定的提高，但还是比NBC的效果差一些。

（3）误检率。在DOS和Proble这两种组数据的误检率相同，在其他两组数据的中，K-NBC的误检率都比NBC的低。

根据表3的结果分析，我们也可以看到的检测结果与表2的分组检测的结果比较类似，并且从综合角度来说，K-NBC检测效果要比NBC的好。在这里，我们也发现，两种算法对R2L和U2L这两类入侵的检测效果要比DOS和Proble这两类入侵的差。这主要是因为这两类入侵属于入侵行为的稀有类，检测难度也相应加大。在KDD99竞赛中，冠军方法对这两类的检测效果也是最差的。但我们可以看到NBC对这种稀有类的入侵行为检测更为准确一点，这应该是稀有类的分布更接近正态分布。

从上述各方面综合分析，我们可以证明K-NBC作为的入侵检测分类算法的是有其优越性的。

表3 对混合入侵类型数据进行检测的结果

数据集

算法 整体检测 分类检测

Normal Dos Proble R2L U2R

检测率 误检率 检测率 误检率 检测率 误检率 检测率 误检率 检测率 误检率 检测率 误检率

NBC 9814 18 982 08 998 0 998 0 90 0 867 18

K-NBC 9978 02 998 23 998 0 998 0 96 0 733 01

SU+NBC 9799 20 98 08 998 0 998 0 90 0 867 19

SU+K-NBC 9979 02 998 19 998 0 998 0 96 0 80 01

5 结论

在本文中，我们用高斯核密度函数代替朴素贝叶斯中的高斯函数，建立K-NBC分类器，对入侵行为进行检测，另我们使用对称不确定方法来删除检测数据的中与类不相关的属性，从而进一步改进核密度朴素贝叶斯的分类效率，实验表明，对预处理后的审计数据，再结合K-NBC来检测，可以达到更好的分类效果，具有很好的实用性。同时我们也注意到，由于入侵检测的数据中的入侵行为一般为稀有类，特别是对R2L和U2R这两类数据进行检测时，NBC有着比较理想的结果，所以在下一步工作中，我们看是否能把NBC和K－NBC这两种分类模型和优点联合起来，并利用对称不确定理论来删除检测数据与类相关的属性中的冗余属性，进一步提高入侵检测效率。

贝叶斯网络又称信度网络，是Bayes方法的扩展，是目前不确定知识表达和推理领域最有效的理论模型之一。从1988年由Pearl提出后，已经成为近几年来研究的热点。一个贝叶斯网络是一个有向无环图(Directed Acyclic Graph,DAG),由代表变量节点及连接这些节点有向边构成。节点代表随机变量，节点间的有向边代表了节点间的互相关系(由父节点指向其子节点)，用条件概率进行表达关系强度，没有父节点的用先验概率进行信息表达。节点变量可以是任何问题的抽象，如：测试值，观测现象，意见征询等。适用于表达和分析不确定性和概率性的事件，应用于有条件地依赖多种控制因素的决策，可以从不完全、不精确或不确定的知识或信息中做出推理。

贝叶斯网络即先验概率和条件概率简化全联合概率分布。减少模型包含的条件概率数量，简化了贝叶斯方法的学习与预测联合概率分布：即先验概率和条件概率，朴素贝叶斯算法的假设条件是各个事件相互独立，然后利用贝叶斯定理，做概率的计算，于是这个算法的核心就是就是这个贝叶斯定理的运用了。