第五章神经网络

5.1神经元模型

神经网络中最基本的成分是神经元模型，即“简单单元”。
在“M-P神经元模型“中，神经元接受收到来自n个其他神经元传递过来的输入信号，这些输入信号经过带权重的连接进行传递，神经元接收到的总输入值将于神经元的阈值进行比较比较，然后通过”激活函数“处理以产生神经元的输出。

激活函数有两种：阶跃函数和sigmoid函数。由于阶跃函数具有不连续、不光滑的不太好的性质，所以通常使用sigmoid函数。sigmoid函数可能把在较大的范围内变化的输入值挤压到（0,1）输出范围内，因此有时也称为“挤压函数”(squashing function).

把许多个这样的神经元按一定的层次机构连接起来就得到了神经网络。

5.2感知机和神经网络

感知机(Perceptron)由两层神经元组成。如图5.3，输入层接收外界输入信号后传递给输出层，输出层是M-P神经元，亦称“阈值逻辑单元”(thresold logic unit).
感知机能容易地解决逻辑与、或、非运算。

需注意的是，感知机只有输出层神经元进行激活函数处理，机制拥有一层功能神经元，学习能力有限。上述与、或、非都是线性可分的问题。

要解决非线性可分问题，需要使用多层功能神经元。下图用了两层简单的感知机就解决了异或问题。

但是，更常见的是下图的层级结构。每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接。这样的神经网络结构通常称为“多层前馈神经网络”。(multi-layer feedforward nrural networks).

5.3误差逆传播算法(BP算法)

误差逆传播算法(error BackPropagation,简称BP)是迄今为止最成功的神经网络学习算法。现实任务中使用神经网络时，大多数使用BP算法进行训练。BP算法不仅可用于多层前馈神经网络，还可用于其他类型的神经网络。
BP算法：

输入：d维特征向量
输出：l个输出值
隐层：假定使用q个隐层神经元
假定功能单元均使用Sigmoid函数

对于每个训练样例，BP算法执行以下操作：先将输入示例提供给输入层神经元,然逐层将信号前传，直到产生输入层的结果；然后计算输入层的误差，再将误差逆向传播至隐层神经元，最后根据隐层神经元的误差来对连接权和阈值进行调整，该迭代过程循环进行，直到达到某些停止条件为止。
需注意的是，BP算法的目标是要最小化训练集D上的累计误差

上面所说的“标准BP算法”每次仅针对一个训练样例更新连接权和阈值。如果类似地推导出基于累积误差最小化的更新规则，就得到了累计误差逆传播(accumulated error backpropagation)算法。累积BP算法和标准BP算法都很常用。一般来说，标准BP算法每次更新只针对单个样例，参数更新的非常频繁，而且对不同样例进行更新的结果可能会出现“抵消”现象。故，为了达到同样的累积误差极小点，标准BP算法需要进行更多次数的迭代。累积BP算法直接针对累计误差最小化。它在读取整个训练集D一遍后才对参数进行更新，其参数更新的频率低得多。所以当训练集D比较大时，标准BP算法的效率更好。
由于其强大的表示能力，BP神经网络经常遭遇过拟合，其训练误差持续降低，当测试误差有可能上升。有两种策略可以缓解过拟合：
1. “早停”(early stopping):将数据分成训练集和验证集，训练集用来计算梯度、更新连接权和阈值，验证集用来估计误差，若训练集误差降低但验证集误差升高，则停止训练，同时返回具有最小验证集误差的连接权和阈值。
2. “正则化”(regularization)其基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分。

5.4全局最小和局部最小

我们常会谈到两种“最优”：“局部最小”(local minimum)和”全局最小”(global minimum).对和，若存在>0使得

都有 成立，则 为局部极小解；若对参数空间中的任意 都有 ，则 为全局极小解。
显然，参数空间内梯度为零的点，只要其误差函数值小于邻点的误差函数值，就是局部极小点；可能存在多个局部极小值，但却只会存在一个全局极小值。在参数优化寻优过程中，我们需要找到全局最小。

基于梯度的搜索是使用最广泛的参数寻优方法。在此类方法中，我们从某些初始解出发，迭代寻找最优参数值。每次迭代中，我们先计算误差函数在当前点的梯度，然后根据梯度确定搜索方向。
在现实任务中，人们常采用以下策略来试图“跳出”局部极小，从而进一步接近全局最小:
1. 以多组不同参数值初始化多个神经网络，按标准方法训练后，取其中误差最小的解作为最终参数。
2. 使用“模拟退火”(simulated annealing)技术.模拟退火在每一步都以一定的概率接受比当前解更差的结果，从而有助于“跳出”局部极小。在每步迭代过程中，接受“次优解”的概率要随着时间的推移而逐渐降低，从而保证算法稳定。
3. 使用随机梯度下降。与标准梯度下降精确计算梯度不同，随机梯度下降法在计算时加入了随机因素。于是，即便陷入局部极小点，它计算的梯度仍可能不为零，这样就有机会跳出局部极小继续搜索。

5.5其他常见神经网络

5.5.1RBF网络
RBF(Radial Basis Function,径向基函数)网络是一种单隐层前馈神经网络，它使用径向基函数作为隐层神经元激活函数，而输出层则是对隐层神经元输出的线性组合。假定输入为d维向量x，输出为实值。则RBF网络可表示为：

其中q为隐层神经元个数， 和 分别是第i个隐层神经元所对应的中心和权重。 是径向基函数。

通常采用两步过程来训练RBF网络：第一步，确定神经元中心 ，常用的方式包括随机采样、聚类等；第二步，利用BP算法等来确定参数 和 .
5.5.2ART网络
ART(Adaptive Resonance Theory)自适应谐振理论网络是竞争型学习的代表。
ART比较好地缓解了竞争型学习中的“可塑性-稳定性窘境”(stability plasticity dilemma),可塑性是指神经网络要有学习新知识的能力，而稳定性是指神经网络在学习新知识的同时要保持对旧知识的记忆。这就使得ART一个很重要的优点：可进行增量学习或在线学习。
5.5.3SOM网络
SOM(self-Organizing Map,自组织映射)网络是一种竞争学习型的无监督神经网络。

5.5.4级联相关网络
级联相关网络有两个主要成分：“级联”和“相关”级联是指建立层次连接的层次结构。相关是指通过最大化新神经元的输出与网络误差之间的相关性来训练相关参数。

与一般的前馈神经网络相比，级联相关网络无需设置网络层数、隐层神经元数目。且训练速度较快，但在数据较小时容易陷入过拟合。
5.5.5Elman网络
Elman网络：递归神经网络的代表

网络可以有环形结构，可让使一些神经元的输出反馈回来最为输入
t 时刻网络的输出状态： 由 t 时刻的输入状态和 t-1时刻的网络状态共同决定
5.5.6Boltzmann机
/

5.6深度学习

每个卷积层包含多个特征映射，每个特征映射是一个由多个神经元构成的“平面”，通过一种卷积滤波器提取输入的一种特征
采样层亦称“汇合层”，其作用是基于局部相关性原理进行亚采样，从而在减少数据量的同事保留有用信息
连接层就是传统神经网络对隐层与输出层的全连接.
从另一个角度来理解，深度学习可以理解为进行“特征学习(feature learning)”或“表示学习”(representation learning).

第六章支持向量机(Support Vector Machine)

6.1间隔与支持向量

支持向量机是一种经典的二分类模型，基本模型定义为特征空间中最大间隔的线性分类器，其学习的优化目标便是间隔最大化，因此支持向量机本身可以转化为一个凸二次规划求解的问题。
对于二分类学习，假设现在的数据是线性可分的，这时分类学习最基本的想法就是找到一个合适的超平面，该超平面能够将不同类别的样本分开，类似二维平面使用ax+by+c=0来表示，超平面实际上表示的就是高维的平面，如下图所示：

对数据点进行划分时，易知：当超平面距离与它最近的数据点的间隔越大，分类的鲁棒性越好，即当新的数据点加入时，超平面对这些点的适应性最强，出错的可能性最小。因此需要让所选择的超平面能够最大化这个间隔Gap（如下图所示）， 常用的间隔定义有两种，一种称之为函数间隔，一种为几何间隔，下面将分别介绍这两种间隔，并对SVM为什么会选用几何间隔做了一些阐述。

6.1.1函数间隔Functional margin与几何间隔Geometrical margin

在超平面w*x+b=0确定的情况下，|w*x+b|能够表示点x到距离超平面的远近，而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔(functional margin)的概念。
定义函数间隔（用表示）为：

而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w, b)关于训练数据集T的函数间隔：

但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。
事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离–几何间隔（geometrical margin）的概念。
假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到超平面的距离，如下图所示：

根据平面几何知识，有

其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念)， 是单位向量（一个向量除以它的模称之为单位向量）. 又由于 是超平面上的点满足 ，代入超平面的方程 可得 ，即 随即让此式 的两边同时乘以 再根据 和 即可算出：

为了得到 ,令 乘上对应的类别 y，即可得出几何间隔（用γ表示）：

从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。
通过前面的分析可知：函数间隔不适合用来最大化间隔，因此这里我们要找的最大间隔指的是几何间隔，于是最大间隔分类器的目标函数定义为：

一般地，我们令r^为1（这样做的目的是为了方便推导和目标函数的优化），从而上述目标函数转化为：

显然为了最大化间隔，只需要最大化 ，这就等价于最小化 。于是得到：



这就是支持向量机(Support Vector Machine,简称SVM)基本型。

6.2对偶问题

此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier），定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）：

容易验证，当某个约束条件不满足时，例如 那么显然有 而当所有约束条件都满足时，则最优值为
亦即最初要最小化的量。目标函数变成了：

这里用 表示这个问题的最优值，且和最初的问题是等价的。如果直接求解，那么一上来便得面对w和b两个参数，而 又是不等式约束，这个求解过程不好做。不妨把最小和最大的位置交换一下，变成：

换以后的新问题是原始问题的对偶问题，这个新问题的最优值用来表示。而且有≤，在满足某些条件的情况下，这两者相等，这个时候就可以通过求解对偶问题来间接地求解原始问题.
(1)首先固定，要让 L 关于 w 和 b 最小化，我们分别对w，b求偏导数，即令 ∂L/∂w 和 ∂L/∂b 等于零.

代入到：

得到：

（2）求对α的极大，即是关于对偶问题的最优化问题。经过上面第一个步骤的求w和b，得到的拉格朗日函数式子已经没有了变量w，b，只有。从上面的式子得到：

这样，求出了α。根据 即可求出w，然后通过 可求出b，最终得出分离超平面和分类决策函数。
接触α后，求出w和b即可得到模型

上述过程需要满足KKT条件即

6.3核函数

由于上述的超平面只能解决线性可分的问题，对于线性不可分的问题，例如：异或问题，我们需要使用核函数将其进行推广。一般地，解决线性不可分问题时，常常采用映射的方式，将低维原始空间映射到高维特征空间，使得数据集在高维空间中变得线性可分，从而再使用线性学习器分类。如果原始空间为有限维，即属性数有限，那么总是存在一个高维特征空间使得样本线性可分。若∅代表一个映射，则在特征空间中的划分函数变为：

按照同样的方法，先写出新目标函数的拉格朗日函数，接着写出其对偶问题，求L关于w和b的极大，最后运用SOM求解α。可以得出：
（1）原对偶问题变为：

（2）原分类函数变为：

求解的过程中，只涉及到了高维特征空间中的内积运算，由于特征空间的维数可能会非常大，例如：若原始空间为二维，映射后的特征空间为5维，若原始空间为三维，映射后的特征空间将是19维，之后甚至可能出现无穷维，根本无法进行内积运算了，此时便引出了核函数（Kernel）的概念。
引入核函数后，原来的对偶问题与分类函数则变为：
(1)对偶问题:

(2)分类函数：


由于核函数的构造十分困难，通常我们都是从一些常用的核函数中选择，下面列出了几种常用的核函数：

软间隔与正则化

前面的讨论中，我们主要解决了两个问题：当数据线性可分时，直接使用最大间隔的超平面划分；当数据线性不可分时，则通过核函数将数据映射到高维特征空间，使之线性可分。然而在现实问题中，对于某些情形还是很难处理，例如数据中有噪声的情形，噪声数据（outlier）本身就偏离了正常位置，但是在前面的SVM模型中，我们要求所有的样本数据都必须满足约束，如果不要这些噪声数据还好，当加入这些outlier后导致划分超平面被挤歪了，如下图所示，对支持向量机的泛化性能造成很大的影响。
为了解决这一问题，我们需要允许某一些数据点不满足约束，即可以在一定程度上偏移超平面，同时使得不满足约束的数据点尽可能少，这便引出了“软间隔”支持向量机的概念
* 允许某些数据点不满足约束y(w’x+b)≥1；
* 同时又使得不满足约束的样本尽可能少。
于是优化目标变为：

如同阶跃函数，0/1损失函数虽然表示效果最好，但是数学性质不佳。因此常用其它函数作为“替代损失函数”。

采用hinge损失和“松弛变量”，则变成



通过拉格朗日乘子法得到拉格朗日函数：

分析方法和前面一样，转换为另一个问题之后，我们先让! 针对 、b和 最小化：

得到：

把前后的结果对比一下：

正规化问题
- 正规化可理解为“罚函数法”
- 通过对不希望的结果施以惩罚，使得优化过程趋向于希望目标
- 从贝叶斯估计的角度，则可认为是提供了模型的先验概率

6.5支持向量回归

示意图：

- ε-不敏感损失函数

- 支持向量回归
- 原始问题

- 对偶问题

- 预测

核方法

表示定理：

- 核线性判别分析:
- 学习目标

- 分析后

贝叶斯分类器

7.1贝叶斯决策论(Bayesian decision theory)

贝叶斯决策论考虑的问题是如何基于这些概率和误判损失来选择最优的类别标记。
假设，是将真实标记为误分类为的损失。基于后验概率可获得将样本x分类为所产生的期望损失，即为“条件风险”。

寻找一个判定准则h：X——Y以最小化总体风险

产生了贝叶斯判断准则：最小化总体风险，只需在样本上选择那个能使条件风险 最小的类别标记。

若损失函数λ取0-1损失，则有：

即对于每个样本x，选择其后验概率P（c | x）最大所对应的类标，能使得总体风险函数最小，从而将原问题转化为估计后验概率P（c | x）。一般这里有两种策略来对后验概率进行估计：
1. 判别式模型：直接对 P（c | x）进行建模求解。例我们前面所介绍的决策树、神经网络、SVM都是属于判别式模型。
2. 生成式模型：通过先对联合分布P（x,c）建模，从而进一步求解 P（c | x）。
贝叶斯分类器就属于生成式模型，基于贝叶斯公式对后验概率P（c | x） 进行一项神奇的变换，

对于给定的样本x，P(x)与类标无关，P(c)称为类先验概率，p（x | c ）称为类条件概率。这时估计后验概率P（c | x）就变成为估计类先验概率和类条件概率的问题。对于先验概率和后验概率，
* 先验概率： 根据以往经验和分析得到的概率。
* 后验概率：后验概率是基于新的信息，修正原来的先验概率后所获得的更接近实际情况的概率估计。实际上先验概率就是在没有任何结果出来的情况下估计的概率，而后验概率则是在有一定依据后的重新估计，直观意义上后验概率就是条件概率。
对于类先验概率P(c)，P(c)就是样本空间中各类样本所占的比例，根据大数定理（当样本足够多时，频率趋于稳定等于其概率），这样当训练样本充足时，p(c)可以使用各类出现的频率来代替。因此只剩下类条件概率p（x | c ），它表达的意思是在类别c中出现x的概率，它涉及到属性的联合概率问题，若只有一个离散属性还好，当属性多时采用频率估计起来就十分困难，因此这里一般采用极大似然法进行估计。

极大似然估计

极大似然估计（Maximum Likelihood Estimation，简称MLE），是一种根据数据采样来估计概率分布的经典方法。常用的策略是先假定总体具有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计。运用到类条件概率p（x | c ）中，假设p（x | c ）服从一个参数为θ的分布，问题就变为根据已知的训练样本来估计θ。极大似然法的核心思想就是：估计出的参数使得已知样本出现的概率最大，即使得训练数据的似然最大。

以，贝叶斯分类器的训练过程就是参数估计。总结最大似然法估计参数的过程，一般分为以下四个步骤：
* 1.写出似然函数；
* 2.对似然函数取对数，并整理；
* 3.求导数，令偏导数为0，得到似然方程组；
* 4.解似然方程组，得到所有参数即为所求。
假设样本属性都是连续值，p（x | c ）服从一个多维高斯分布，则通过MLE计算出的参数刚好分别为：

朴素贝叶斯分类器

原始的贝叶斯分类器最大的问题在于联合概率密度函数的估计，首先需要根据经验来假设联合概率分布，其次当属性很多时，训练样本往往覆盖不够，参数的估计会出现很大的偏差。为了避免这个问题，朴素贝叶斯分类器(naive Bayes classifier)采用了“属性条件独立性假设”，即样本数据的所有属性之间相互独立。这样类条件概率p(x | c) 可以改写为：

由于对所有类别来说P（x）相同，因此基于贝叶斯判定准则为：

这就是朴素贝叶斯分类器的表达式。

相比原始贝叶斯分类器，朴素贝叶斯分类器基于单个的属性计算类条件概率更加容易操作，需要注意的是：若某个属性值在训练集中和某个类别没有一起出现过，这样会抹掉其它的属性信息，因为该样本的类条件概率被计算为0。因此在估计概率值时，常常用进行平滑(smoothing)处理，拉普拉斯修正(Laplacian correction)就是其中的一种经典方法，具体计算方法如下：

朴素贝叶斯的主要优点有：
1. 朴素贝叶斯模型发源于古典数学理论，有稳定的分类效率。
2. 对小规模的数据表现很好，能个处理多分类任务，适合增量式训练，尤其是数据量超出内存时，我们可以一批批的去增量训练。
3. 对缺失数据不太敏感，算法也比较简单，常用于文本分类。
朴素贝叶斯的主要缺点有：　　　
* 理论上，朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为朴素贝叶斯模型给定输出类别的情况下,假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。而在属性相关性较小时，朴素贝叶斯性能最为良好。对于这一点，有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。
* 需要知道先验概率，且先验概率很多时候取决于假设，假设的模型可以有很多种，因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。
* 由于我们是通过先验和数据来决定后验的概率从而决定分类，所以分类决策存在一定的错误率。
* 对输入数据的表达形式很敏感。

半朴素贝叶斯分类器(semi-naive Bayes classfiers)

在朴素的分类中，我们假定了各个属性之间的独立，这是为了计算方便，防止过多的属性之间的依赖导致的大量计算。这正是朴素的含义，虽然朴素贝叶斯的分类效果不错，但是属性之间毕竟是有关联的，某个属性依赖于另外的属性，于是就有了半朴素贝叶斯分类器。
为了计算量不至于太大，假定每个属性只依赖另外的一个。这样，更能准确描述真实情况。

确定如何依赖
1.SOPDE方法。这种方法是假定所有的属性都依赖于共同的一个父属性。

2.TAN方法。每个属性依赖的另外的属性由最大带权生成树来确定.
(1)计算任意两个属性之间的条件互信息（conditional mutual information)
（2）构建完全图。以属性为结点构建完全图，任意两个结点之间的边权重重设为
（3）构建此完全图的最大带权生成树，挑选根变量，将边置为有向边
（4）加入类别结点y,增加从y到每个属性的有向边。

AODE
AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制、更为强大的独依赖分类器，与SPODE通过模型选择确定超父属性不同，AODE尝试将每个属性作为超父来构建SPODE。然后将这些具有足够训练数据支持的SPODE集成起来作为最终结果，即：

其中Dxi在第i个属性上取值为xi的样本的集合，m′为阈值或者常数，显然AODE需要估计P(c,xi)和P(xj∣c,xi)于是

其中Ni是第i个属性可能的取值数，Dc,xi是类别为c且在第i个属性上取值为xi的样本的集合，Dc,xi,xj是类别为c且在第i和第j个属性上取值分别为xi和xj的样本的集合。

贝叶斯网

贝叶斯网： 借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表(Conditional Probability Table)来描述属性的联合概率分布。
一个贝叶斯网B由结构G和参数Θ两部分构成，即
网络结构G： 一个有向无环图，其每一个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来。
参数Θ： 描述属性间的直接依赖关系，假设属性xi在G中的父节点集为πi，则Θ包含了每个属性的条件概率表θxi|πi=PB(xi|πi)。
结构
给定父节点集，贝叶斯网假设每个属性与它的非后裔属性独立，则将属性x1,x2,…,xd的联合概率分布定义为

贝叶斯网中三个变量之间的典型依赖关系：

同父结构：x1已知，则x3⊥x4|x1；x1未知，则x3╨x4不成立。
V型结构：x4已知，则x1⊥x2|x4不成立；x4未知，则x1╨x2成立。
顺序结构：x已知，则y⊥z|x成立，但y╨z不成立。
其中，以V型结构为例，边际独立性的验证如下：

学习
贝叶斯网学习的首要任务就是根据训练数据集找出结构最“恰当”的贝叶斯网。“评分搜索”是求解这一问题的常用办法：
定义一个评分函数用于评估贝叶斯网与训练数据的契合程度；
基于评分函数寻找结构最优的贝叶斯网。
常用评分函数通常基于信息论准则，其将学习问题看作一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，其中编码的长度包括描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。
对于贝叶斯网学习而言，模型就为一个贝叶斯网，每个贝叶斯网描述了一个在训练数据上的概率分布，其自由一套编码机制。因此，我们只需选择综合编码长度最短的贝叶斯网。这就是“最小描述长度”准则。
给定训练集D={x1,x2,…,xm}，贝叶斯网 在D上的评分函数为：

其中，|B|是贝叶斯网的参数个数；f(θ)表示描述每个参数θ所需的字节数； 表示贝叶斯网B的对然。
(θ)=1，AIC（Akaike Information Criterion）评分函数：AIC(B|D)=|B|−L(B|D)
f(θ)=1/2logm，BIC(Bayesian Information Criterion)评分函数：BIC(B|D)=logm2|B|−L(B|D)
若贝叶斯网的网络结构G固定，则评分函数第一项的值为固定值。此时，最小化评分函数就是对L(B|D)进行极大似然估计。

其中p^(⋅)是D上的经验分布。
经验分布函数——设x1,x2,…,xn是总体X的一组容量为n的样本观测值，将它们从小到大的顺序重新排列为x∗1,x∗2,…,x∗n，对于任意实数x，定义函数

推断
通过已知变量观测值来推测待查询变量的过程称为“推断”，其中已知变量观测值称为“证据”。在现实应用中，贝叶斯网的近似推断常使用吉布斯采样(Gibbs sampling)来完成。
令Q={Q1,Q2,…,Qn}表示带查询变量，E={E1,E2,…,Ek}为证据变量，已知取值为e={e1,e2,…,ek}。目标是计算后验概率P(Q=q|E=e)，其中q={q1,q2,…,qn}是待查询变量的一组取值。

吉布斯采样算法：

实质上，吉布斯采样是在贝叶斯网所有变量的联合状态与证据E=e一致的子空间中进行“随机漫步”。每一步仅依赖于前一步的状态，这是一个“马尔科夫链”（Markov chain）。在一定条件下，无论从什么初始状态开始，马尔科夫链第t步的状态分布在t→∞时必收敛于一个平稳分布；对于吉布斯采样而言，这个分布恰好为P(Q|E=e) 。但马尔科夫链通常需要很长时间才能趋于平稳分布，因此，吉布斯采样算法的收敛速度较慢。

注：若贝叶斯网中存在极端概率“0”或“1”，则不能保证马尔科夫链存在平稳分布，此时吉布斯采样会给出错误的估计结果。

EM算法

EM（Expectation-Maximization）算法是一种常用的估计参数隐变量的利器，也称为“期望最大算法”，是数据挖掘的十大经典算法之一。EM算法主要应用于训练集样本不完整即存在隐变量时的情形（例如某个属性值未知），通过其独特的“两步走”策略能较好地估计出隐变量的值。

8.1 EM算法思想
EM是一种迭代式的方法，它的基本思想就是：若样本服从的分布参数θ已知，则可以根据已观测到的训练样本推断出隐变量Z的期望值（E步），若Z的值已知则运用最大似然法估计出新的θ值（M步）。重复这个过程直到Z和θ值不再发生变化。
简单来讲：假设我们想估计A和B这两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

EM算法流程

2.2 Jensen不等式
  设f是定义域为实数的函数，如果对于所有的实数x，f(x)的二次导数大于等于0，那么f是凸函数。
  Jensen不等式表述如下：如果f是凸函数，X是随机变量，那么：E[f(X)]≥f(E[X])。当且仅当X是常量时，上式取等号。其中，E[x]表示x的数学期望。
  例如，图2中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。X的期望值就是a和b的中值了，图中可以看到E[f(X)]≥f(E[X])成立。
  注：
  1、Jensen不等式应用于凹函数时，不等号方向反向。当且仅当X是常量时，Jensen不等式等号成立。
  2、关于凸函数，百度百科中是这样解释的——“对于实数集上的凸函数，一般的判别方法是求它的二阶导数，如果其二阶导数在区间上非负，就称为凸函数（向下凸）”。关于函数的凹凸性，百度百科中是这样解释的——“中国数学界关于函数凹凸性定义和国外很多定义是反的。国内教材中的凹凸，是指曲线，而不是指函数，图像的凹凸与直观感受一致，却与函数的凹凸性相反。只要记住“函数的凹凸性与曲线的凹凸性相反”就不会把概念搞乱了”。关于凹凸性这里，确实解释不统一，暂时以函数的二阶导数大于零定义凸函数，此处不会过多影响EM算法的理解，只要能够确定何时E[f(X)]≥f(E[X])或者E[f(X)]≤f(E[X])就可以。