贝叶斯

相对熵

相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，KL散度等。相对熵可以度量两个随机变量的“距离”。
设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是

一般的，D(pllq）≠D(qllp)，D(pllq)≥0，D(qllp)≥0。

互信息

信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即:
g(D,A)=H(D)-H(D|A)
显然，这即为训练数据集D和特征A的互信息。

贝叶斯公式

朴素贝叶斯

一个特征出现的概率，与其他特征(条件)独立(特征独立性)。其实就是对于给定分类的条件下，特征独立每个特征同等重要(特征均衡性)。

朴素贝叶斯基于各特征之间相互独立，在给定类别为y的情况下，上式可以进一步表示为下式：

由以上两式可以计算出后验概率为：

由于P(X)的大小是固定不变的，因此在比较后验概率时，只比较上式的分子部分即可。

贝叶斯网络

把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。
贝叶斯网络(Bayesian Network)，又称信念网路(belief network)或是有向无环图模型(directed acyclic graphical model ,DAG)，是一种概率图模型，根据概率图的拓扑结构，考察一组随机变量{Xp,x…X.}及其n组条件概率分布(Conditional Probability Distributions, CPD)的性质。

一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系(或非条件独立)。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。每个结点在给定其直接前驱时，条件独立于其非后继。

一个简单的贝叶斯网络

全连接贝叶斯网络

每一对结点之间都有边连接

一个正常的贝叶斯网络

有些边缺失。直观上：x1和x2独立，x6和x7在x4给定的条件下独立。

x1,x2…x7的联合分布：

贝叶斯网络的形式化定义

BN(G,θ)
G：有向无环图；
G的结点：随机变量；
G的边：结点间的有向依赖；
θ：所有条件概率分布的参数集合；
结点X的条件概率: P(Xlparent(X))。
需要多少参数才能确定上述网络呢?
每个结点所需参数的个数：结点的parent数目是M，结点和parent的可取值数目都是K: K^M*(K-1)。

特殊贝叶斯网络——马尔科夫模型

结点形成一条链式网络，称作马尔科夫模型。Xi+1只与Xi有关，与Xi…Xi-1无关。

有D-separation可知，在xi给定的条件下，xi+1的分布和x1 ,x2…xi-1条件独立。即：xi+1的分布状态只和xi有关，和其他变量条件独立，这种顺次演变的随机过程模型，叫做马尔科夫模型。

应用：pLSA主题模型

条件独立的三种类型

通过贝叶斯网络判定独立条件1

根据图模型，得 P(a,b,c) = P© * P(a|c) * P(b|c)，从而，P(a,b,c)/P© = P(a|c) * P(b|c)
而P(a,b|c) = P(a,b,c) / P©，得 P(a,b|c) = P(alc) * P(b|c)。即，在c给定的条件下，a,b被阻断，是条件独立的：tail-to-tail。

通过贝叶斯网络判定独立条件2

P(a,b,c) = P(a) * P(c|a) * P(b|c)
P(a,b|c)
= P(a,b, c) / P©
= P(a) * P(c|a) * P(b|c) / P©
= P(a,c) * P(b|c) / P©
= P(a|c) * P(b|c)

即：在c给定的条件下，a,b被阻断，是条件独立的：head-to-tail。

通过贝叶斯网络判定独立条件3

P(a,b,c) = P(a) * P(b) * P(c|a, b)
∑ P(a,b,c) = ∑ P(a) * P(b) * P(c|a,b)
→ P(a,b) = P(a) * P(b)

即：在c给定的条件下，a,b被阻断，是条件独立的：head-to-head。

D-separation

对于任意的结点集A，B，C，考察所有通过A中任意结点到B中任意结点的路径,
若要求A，B条件独立，则需要所有的路径都被阻断(blocked)，即满足下列两个前提之一:
A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C;
A和B的“head-to-head型”路径不通过C以及C的子孙;
如果A,B不满足.D-separation, 则A,B被称为D-connected。

HMM

隐马尔可夫模型（Hidden Markov Model，HMM），是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别、语音识别、NLP等。

在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

HMM是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个因观测而产生可观测随机序列的过程。隐马尔科夫模型随机生成的状态的序列，称为状态序列。每个状态生成一个观测，由此产生的观测随机序列，称为观测序列。序列的每个位置可看做是一个时刻，空间序列也可以使用该模型：分析DNA。

图中箭头方向则表示不同信息间的关系性，因此可以得知x(t)和x(t-1)有关，而x(t-1)又和x(t-2)有关。
而每个y(t )只和x(t)有关,其中x(t)我们称为隐藏变 量(hidden variable)， 是观察者无法得知的变量。隐性马尔可夫模型常被用来解决有未知条件的数学问题。
假设隐藏状态的值对应到的空间有N个元素，也就是说在时间时，隐藏状态会有N种可能。同样的，t + 1也会有N种可能的值，所以从t到t + 1间的关系会有N2种可能。除了x(t)间的关系外，每组x(t), y(t)间也有对应的关系。
若观察到的y(t)有M种可能的值，则从x(t)到y(t)的输出模型复杂度为O(NM)。 如果y(t)是一 个M维的向量， 则从x(t)到y(t)的输出模型复杂度为O(NM2)。

Markov Blanket

一个结点的Markov Blanket是一个集合，在这个集合中的结点都给定的条件下，该结点
条件独立于其他所有结点。即：一个结点的Markov Blanket是它的parents,children以及spouses。

贝叶斯网络的应用

通过给定的样本数据，建立贝叶斯网络的拓扑结构和结点的条件概率分布参数。这往往需要借助先验
知识和极大似然估计来完成。在贝叶斯网络确定的结点拓扑结构和条件概率分布的前提下，可以使用该网络，对未知数据计算条件概率或后验概率，从而达到诊断、预测或者分类的目的。

贝叶斯网络的构建

依次计算每个变量的D-separation的局部测试结果，综合每个结点得到贝叶斯网络。
算法过程:
选择变量的一个合理顺序: X1,X2,…Xn
对于i=1到n
在网络中添加Xi结点
在X1,X2,…Xi-1中选择Xi的父母，使得:

这种构造方法，显然保证了全局的语义要求：