概率图

概率图中的节点分为隐含节点和观测节点，边分为有向边和无向边。从概率论的角度，节点对应于随机变量，边对应于随机变量的依赖或相关关系，其中有向边表示单向的依赖，无向边表示相互依赖关系。

概率图模型分为贝叶斯网络（Bayesian Network）和马尔可夫网络（Markov Network）两大类。贝叶斯网络可以用一个有向图结构表示，马尔可夫网络可以表示成一个无向图的网络结构。更详细地说，概率图模型包括了朴素贝叶斯模型、最大熵模型、隐马尔可夫模型、条件随机场、主题模型等，在机器学习的诸多场景中都有着广泛的应用。

马尔可夫网络的联合概率分布

在马尔可夫网络中，联合概率分布的定义为

$P(x) = \frac{1}{Z}\prod_{Q \in C}\varphi_{Q}(X_Q)$

其中$C$为图中最大团所构成的集合，$Z = \sum{x} \prod{Q \in C}\varphi{Q}(X_Q)$为归一化因子，用来保证$P(x)$是被正确定义的概率，$\varphi{Q}$是与团$Q$对应的势函数。势函数是非负的，并且应该在概率较大的变量上取得较大的值，例如指数函数

$\varphi_{Q}(X_Q)=e^{-H_{Q}(x_Q)}$

其中，

$H_Q(x_Q)= \sum_{\mu,v \in Q,\mu \neq v}\alpha_{\mu,v}x_{\mu}x_v+\sum_{v \in Q}\beta_vx_v$

对于图中所有节点$x={x_1,x_2,…,x_n}$所构成的一个子集，如果在这个子集中，任意两点之间都存在边相连，则这个子集中的所有节点构成了一个团。如果在这个子集中加入任意其他节点，都不能构成一个团，则称这样的子集构成了一个最大团。

对于由A，B，C，D四个点构成的四边形无向图，其联合概率分布为：

$P(A,B,C,D)=\frac{1}{Z}e^{-H(A,B,C,D)}$

概率图表示

解释朴素贝叶斯模型原理

朴素贝叶斯模型通过预测指定样本属于特定类别的概率$P(y_i|x)$来预测该样本的所属类别，即

$y = \max_{y_i}P(y_i|x)$

$P(y_i|x)$可以写成

$P(y_i|x) = \frac{P(x|y_i)P(y_i)}{P(x)}$

其中$x= (x_1,x_2,x_3,…,x_n)$为样本对应的特征向量，$P(x)$为样本的先验概率。对于特定的样本x和任意类别$y_i$，$P(x)$的取值均相同，在计算中可以被忽略。假设特征相互独立，$P(y_i)$可以通过训练样本统计得到，后验概率$P(x_j|y_i)$的取值决定了分类的结果。并且任意特征$x_j$都由$y_i$的取值所影响。

解释最大熵模型的原理

信息是指人们对事物理解的不确定性的降低或消除，而熵是不确定性的度量，熵越大，不确定性也就越大。

最大熵原理是概率模型学习的一个准则，指导思想是在满足约束条件的模型集合中选取熵最大的模型，即不确定性最大的模型。

在对训练数据集一无所知的情况下，最大熵模型认为$P(y|x)$是符合均匀分布的。

给定离散随机变量$x$和$y$上的条件概率分布$P(x|y)$，定义在条件概率分布上的条件熵为：

$H(p) = -\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$

其中$\tilde{P}(x)$为样本在训练数据集上的经验分布，即$x$的各个取值在样本中出现的频率统计。

当我们有了训练数据集之后，我们希望从中找到一些规律，从而消除一些不确定性，这时就需要用到特征函数$f(x,y)$。特征函数$f$描述了输入$x$和输出$y$之间的一个规律。为了使学习到的模型能够正确捕捉训练数据集中的特征，我们加入一个约束，使得特征函数$f(x,y)$关于经验分布$\tilde{P}(x,y)$的期望值与关于模型$P(y|x)$和经验分布$\tilde{P}(x)$的期望值相等。

$E_{\tilde{P}}(f) = \sum_{x,y}\tilde{P}(x,y)f(x,y)$ $E_p(f) = \sum_{x,y}\tilde{P}(x)P(y|x)f(x,y)$

综上，给定训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，以及M个特征函数${f_i(x,y),i=1,2,…,M}$，最大熵模型的学习等价于约束最优化问题：

$\max_{p}H(P) = -\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x) \\ s.t., E_{\tilde{P}}(f) = E_p(f), \forall i =1,2,...,M, \\ \sum_{y}P(y|x) = 1$

求解之后可以得到最大熵模型的表达形式为

$P_w(y|x) = \frac{1}{Z}exp(\sum_{i=1}^{M}w_if_i(x,y))$

最终，最大熵模型归结为学习最佳的参数$w$，使得$P_w(y|x)$最大化。

参考资料

《百面机器学习》