1. 贝叶斯决策论
首先介绍贝叶斯决策论的定义：
贝叶斯决策论是概率框架下实施决策的基本方法。
首先，根据定义提取两个关键词：概率框架、实施决策
我认为学习一个东西最重要要清楚它是做什么的，前提条件是什么。
根据关键词，我们可知贝叶斯决策论是用来做决策的(通过名字也知道，废话~)，它的前提条件是概率已知。
以分类任务为例，在所有概率都已知的理想情况下，贝叶斯决策论用来基于这些概率来选择最优的类别标记。
下面以多分类任务做具体分析：
目前分类任务有N种可能的类别标记，即$\cal Y={c_1,c_2,…,c_N}$;
$\lambda_{ij}$表示将一个真实标记为$c_j$的样本错误分类为$c_i$标记的损失；
通过后验概率$P(c_i\textbf x)$可获得样本$\textbf x$分类为$c_i$所产生的期望损失，即在样本$\textbf x$上的条件风险：
\[R(c_i|\textbf x)=\sum_{j=1}^N\lambda_{ij}P(c_j|\textbf x) \tag{1-1}\]公式1-1求的是在样本$\textbf x$下分类为$x_i$的条件损失，其实就是遍历所有样本，求取每个样本被分类为类别$c_i$的损失，再求和。
公式1-1求得分类为$c_i$的风险，作为多分类任务，我们的目标就是分类准确，那么反过来说就是降低总体期望损失或者说是总体风险，总体风险公式如下：
\[R(h)=\Bbb E_{x}[R(h(\textbf x)|\textbf x)] \tag{1-2}\]根据公式1-2所示，若单个类别的条件风险$R(h(\textbf x)\mid \textbf x)$最小，那么总体风险$R(h)$也会最小。
其实到此就总结出了贝叶斯判别准则：
\[h^*(\textbf x)={\arg \min}_{c\in\cal Y} R(c|\textbf x) \tag{1-3}\]为最小化总体风险，只需在每个样本上选择能使条件风险$R(c\mid \textbf x)$最小的类别标记，即：
公式1-3中的$h^$称为贝叶斯最优分类器，对应的总体风险$R(h^)$称为贝叶斯风险。
其中$1-R(h^*)$反映了分类器所能达到的最好性能，即通过机器学习方法所学习的模型精度的理论上限，我们称为贝叶斯最优。在深度学习中，判断一个模型欠拟合多一些还是过拟合多一些，主要通过贝叶斯最优和模型在开发集和测试集上的精度。
上述分析针对多分类任务的概述，下面我们再具体一点：
我们增加了当前分类任务的目标：最小化分类错误率
那么我们的$\lambda_{ij}$可设置为0/1损失函数(在支持向量机中涉及到)：
\[\lambda_{ij}= \begin{cases} 0, \quad i=j\\ 1, \quad otherwise \end{cases}\tag{1-4}\]根据公式1-4，我们修改一下公式1-1：
\[R(c|\textbf x)=1-P(c|\textbf x) \tag{1-5}\]呀，是不是变化好多，其实根据公式1-4可知，只有当i=j的时候，$\lambda_{ij}$为0，其余情况下相当于每个类别概率的和。那么样本为所有类别的和为1，我们减去为0的情况，就是条件风险了，具体为公式1-5所示。
进而修改公式1-3，求取贝叶斯最优分类器：
\[h^*(\textbf x)={\arg \min}_{c\in\cal Y} R(c|\textbf x)={\arg \min}_{c\in\cal Y} 1-P(c|\textbf x)={\arg \max}_{c\in\cal Y} P(c|\textbf x) \tag{1-6}\]公式1-6最终推导出，选择后验概率最大的类别标记即为贝叶斯最优分类器。
是不是感觉白推导了那么多，这不就是我们的常识~
既然回到了我们的常识上，那么我们肯定知道后验概率$P(c\mid \textbf x)$一般是木有的！
所以想要通过贝叶斯判定准则(也就是上面那一套)最小化决策风险，那么我们需要求得后验概率$P(c\mid \textbf x)$。
又所以扯了一大顿，回到我们的真实问题：
基于有限的训练样本集尽可能准确的估计后验概率$P(c\mid \textbf x)$
目前把解决上述问题的所有方法分为两种：
-
判别式模型：
给定训练样本$\textbf x$，直接建模$P(c\mid \textbf x)$来预测$c$。
决策树、BP神经网络、支持向量机
-
生成式模型：
先对联合概率分布$P(\textbf x,c)$建模，然后再求得$P(c\mid \textbf x)$。
对判别式模型比较熟悉，因为之前讲的决策树、BP神经网络、支持向量机方法都属于判别式模型，下面，我们针对生成式模型做具体分析：
根据生成式模型的概念，得出如下公式：
\[P(c|\textbf x)=\frac{P(\textbf x,c)}{P(\textbf x)}=\frac{P(c)P(\textbf x|c)}{P(\textbf x)} \tag{1-7}\]根据公式1-7，我们来分析我们需要求解的问题到底是什么。
$P( c )$是类先验概率；$P(\textbf x\mid c)$是样本$x$相对于类别$c$的类条件概率，也叫”似然“（说法很高大上）；$P(\textbf x)$是用于归一化的证据因子(想想也知道它对于所有类都是不变的，因此忽略它)。
因此，我们未知的就是类先验概率$P( c )$与似然$P(\textbf x\mid c)$了。
-
关于类先验概率$P( c )$：
它的直观理解就是某个类别在空间中各个类别中所占的比例；
在训练集充足且样本独立同分布时，我们可以根据各个样本出现的频率进行估计。
因此，，，解决了！(还有似然呢，听这高大上的名字，肯定是大BOSS了)
-
关于似然$P(\textbf x\mid c)$
我们同样按照出现的频率估计，发现与类先验概率不同，同样的方法不成立！
原因是$\textbf x$设计到所有属性的联合值，解释一下，如果每个样本有有d个属性，每个属性都是二值的，那么所有的可能性为$2^d$种，一般情况下，我们的训练集覆盖不了全部的可能性，因此不能通过出现频率估计。
也许某些人说可以通过将未出现的设为0，但是这是不准确的，因为未被观测到和出现概率为0是不一样的。
所以，第一节就是为了引出这个问题，如何求解或者估计似然$P(\textbf x\mid c)$？？？
2. 极大似然估计
上一节我们引出问题：如何求解类条件概率，也就是似然$P(\textbf x\mid c)$。
估计似然的常用策略或者说是方法为：先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。
既然如此，那我们就按照常用方法来哈！
假设似然$P(\textbf x\mid c)$具有确定性的概率分布形式并且被参数向量$\theta_c$唯一确定，那么我们的任务就是利用训练集估计参数$\theta_c$。
问题转换成参数估计，看一下常用的参数估计方法：
- 频率主义学派：参数未知但是确实存在，因此可使用优化似然函数等准则确定参数
- 贝叶斯学派：参数属于为观测的随即变量，其本身也有分布，因此假定参数服从一个先验分布，然后再根据训练集计算参数的后验分布(说实话，不太懂😂)
本节的主题是极大似然估计，它是频率主义学派的方法，简称MLE，是根据数据采样来估计概率分布参数的经典方法。
令$D_c$表示数据集D中的第$c$类样本组成的集合，则参数$\theta_c$对于数据集$D_c$的似然是：
\[P(D_c|\theta_c)=\Pi_{\textbf x\in D_c}P(\textbf x|\theta_c)\tag{2-1}\]对$\theta_c$进行极大似然估计，就是去寻找能够最大化似然$P(D_c\mid \theta_c)$的参数$\hat \theta_c$，即${\arg\max}_{\theta_c}P(D_c\mid \theta_c)$.
直观理解，就是在$\theta_c$的所有取值中，找到能使数据出现概率最大的值。
公式2-1中的连乘操作容易造成下溢，因此我们将其替换成对数似然：
\[\begin{align} LL(\theta_c)&=\log P(D_c|\theta_c)\\ &=\sum_{x\in D_c}logP(\textbf x|\theta_c)\tag{2-2} \end{align}\]那么参数$\theta_c$的极大似然估计$\hat \theta_c$为
\[\hat \theta_c=\arg\max_{\theta_c}LL(\theta_c) \tag{2-3}\]以上都是对离散属性的处理，在连续属性下，假设概率密度函数$p(\textbf x\mid c)\sim\cal N(\mu_c,\sigma_c^2)$，则参数$\mu_c$和$\sigma_c^2$的极大似然估计为：
\[\hat \mu_c=\frac {1}{|D_c|}\sum_{\textbf x\in D_c}\textbf x \tag{2-4}\\ \hat \sigma_c^2=\frac{1}{|D_c|}\sum_{\textbf x\in D_c}(\textbf x-\hat \mu_c)(\textbf x-\hat \mu_c)^T\]通过公式2-4，可以发现在连续情况下，通过极大似然法求得的正态分布均值就是样本均值，方差就是$(\textbf x-\hat \mu_c)(\textbf x-\hat \mu_c)^T$的均值，这显然就是计算均值与方差的流程方法。
上述方法通过假定其具有某种确定的概率性分布，然后对其参数进行估计，虽然这使得求解过程相对简单，但是估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。
在真实的应用中，想要作出更能接近数据分布规律的假设，需要在一定程度上利用关于任务本身的经验知识，我们可以称其为先验知识，不然仅根据我们猜测的概率分布，效果往往并不好。
3. 朴素贝叶斯分类器
问题：通过公式1-7可知，需要估计类条件概率，也就是似然，但是直接从有限的训练样本中估计是不可能的。
原因是：基于有限的样本估计联合概率，在计算上与遭遇组合爆炸的问题，在数据上也会遇到样本稀疏问题，并且随着属性值的增加越严重。怎么理解呢，就是咱们估计的类条件概率，首先需要计算所有属性值的组合问题，这就是很耗费资源的一件事；并且在将属性值的所有组合计算完成后，会发现大部分的属性组合根本没有样本，因此会遇到样本稀疏问题。
于是，方法总比困难多~，朴素贝叶斯分类器采用属性条件独立性假设，即假设所有属性相互独立，每个属性独立的对分类结果产生影响。
在属性条件独立性假设的思想下，我们改写1-7：
\[P(c|\textbf x)=\frac{P(\textbf x,c)}{P(\textbf x)}=\frac{P(c)P(\textbf x|c)}{P(\textbf x)} =\frac{P(c)}{P(\textbf x)}\Pi_{i=1}^dP(x_i|c)\tag{3-1}\]公式1-7中，$d$为属性的数目，$x_i$为在第i个属性上的取值。
因为$P(\textbf x)$对所有样本是一样的，我们根据公式1-7，求解在属性条件独立性假设下的贝叶斯最优分类器，即朴素贝叶斯最优分类器：
\[h_{nb}(\textbf x)=\arg \max_{c\in\cal Y}P(c)\Pi_{i=1}^dP(x_i|c)\tag{3-2}\]公式3-2就是朴素贝叶斯最优分类器的表达式，实际上是公式3-1和1-6的组合。
拥有的核心思想，那么可以推导出朴素贝叶斯分类器的训练过程就是：
根据样本估计类先验概率$P(c)$，并且估计每个属性的类条件概率$P(x_i\mid c)$。
如果$D_c$表示训练集$D$中第$c$类样本组成的集合，那么可容易的估计出类先验概率：
\[P(c)=\frac{|D_c|}{|D|}\tag{3-1}\]类先验概率能够简单求解，下面是类条件概率：
- 针对离散属性而言，令$D_{c,x_i}$表示在$D_c$中第$i$个属性取值为$x_i$的样本组成的集合，那么类条件概率$P(x_i\mid c)$为：
- 针对连续属性而言，可考虑概率密度函数，假定$p(x_i\mid c)\sim \cal N(\mu_{c,i},\sigma_{c,i}^2)$，其中$\mu_{c,i},\sigma_{c,i}^2$分别是第$c$类样本在第$i$个属性上取值的均值和方差，则有：
\(P(x_i|c)=\frac{1}{\sqrt {2\pi}\sigma_{c,i}}\exp(-\frac{(x_i-\mu_{c_i})^2}{2\sigma_{c,i}^2}) \tag{3-3}\) 但是在实际使用中，会出现类先验概率和类条件概率为0的情况，即当某个类别或者某个类别中的某个属性没有出现时，按照公式3-2所示，若有一项为0，那么得到的概率就为0，这显然是不合理的。
因此，需要对估计类先验概率和类条件概率进行修正，方法为：拉普拉斯修正
令$N$表示$D$中可能出现的类别的数量，$N_i$表示第$i$个属性可能的取值数量，得到引入拉普拉斯修正后的$P(c)$和$P(x_i\mid c)$：
\[\hat P(c)=\frac{|D_c|+1}{|D|+N}\\ \hat P(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i} \tag{3-4}\]拉普拉斯修正的好处：
- 避免了因数据集不充分引起的概率估计为0的问题
- 在数据量变大时，修正引入的先验（即$D$和$N_i$）的影响会逐渐变得可忽略，使得估计值逐渐趋向于真实值。
朴素贝叶斯分类的多种使用方式：
- 若对预测速率要求高，则可以提前将所有的类先验概率$P(c)$和类条件概率$P(x_i\mid c)$估计好，在测试时，直接通过查表的方式进行计算判别
- 若任务数据更替频繁，那就进行”懒惰训练”，其实就是上一种方式的相反情况，不提前计算所有概率，在测试时需要使用的时候再进行临时计算。
- 若数据不断增加，则可将上述两种方式结合，提前估计好所有的概率，在数据增加后，对增加的数据所涉及的概率进行增量更新，然后再进行预测。
4. 半朴素贝叶斯分类器
在朴素贝叶斯分类器的引入过程中，由于类条件概率因为组合属性的原因导致很难算(具体看朴素贝叶斯分类器小节开头)，因此提出了”属性条件独立性假设”，但是这个假设在真实的数据集很难成立，因此对属性条件独立性假设进行一定的放松，就提出了”半朴素贝叶斯分类器“。
核心思想：适当考虑一部分属性间的相互依赖信息，这样既不需要计算联合概率(算不出来~)，又不至于彻底忽略了比较强的依赖关系(实际上就是在能够算出来的前提下尽可能考虑属性间的依赖关系)。
思想有了，到底怎么做，下面介绍半朴素贝叶斯分类器最常用的一种策略：独依赖估计，简称ODE
独依赖就是假设每个属性在类别之外最多仅依赖一个其他属性。公式为：
\[P(c|\textbf x)\propto P(c)\Pi_{i=1}^dP(x_i|c,pa_i) \tag{4-1}\]公式4-1中$pa_i$为$x_i$所依赖的属性，称为$x_i$的父属性。若父属性已知，那么就可以用公式3-4求解ODE下的类条件概率。
因此最关键的做法就是如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。
下面列举常见的方法：
-
SPODE(Super-Parent ODE)
假设所有属性都依赖同一个属性，这个被依赖的属性称为超父。
超父属性的选择可以通过交叉验证等模型选择方法。
-
TAN(Tree Augmented naive Bayes)
在最大带权生成树算法的基础上将属性间的依赖关系约简为下图所示。
约简步骤为：
- 计算任意两个属性之间的条件互信息：
- 以属性为节点构建完全图，任意两个节点之间边的权重设为$I(x_i,x_j\mid y)$
- 构建此完全图的最大带权生成树，挑选根变量，将边设置为有向。
- 加入类节点$y$，增加从$y$到每个属性的有向边
-
AODE(Averaged One-Dependent Estimator)
尝试将每个属性作为超父构造SPODE，然后将具有足够训练数据支撑的SPODE集成起来作为最终结果。
基于集成学习机制、更为强大的独依赖分类器
公式为：
公式4-3中，${D}_{x_i}$是在第$i$个属性上取值为$x_i$的集合，$m^`$为阈值常数。公式的后半部分就是公式4-1的原理，前半部分对属性进行了筛选，选择属性相关的数据大于阈值的属性。
在这基础上增加拉普拉斯修正类似公式3-4：
\[\hat P(c)=\frac{|D_{c,x_i}|+1}{|D|+N*N_i}\\ \hat P(x_i|c)=\frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j} \tag{4-4}\]以上就是不同的独依赖估计的实现方法。
现在考虑这样一个问题，我们知道独依赖估计是仅考虑依赖一个属性，那么，能够将一个属性提高为依赖所个属性，来提高模型的准确率呢？
实际上是可以的，但是随着考虑依赖属性个数的增加，估计类条件概率所需样本数量成指数级增加，因此在训练样本非常充分时，能够提高泛化能力，但是在有限样本的情况下，又陷入了高阶联合概率的泥沼。
5. 贝叶斯网
贝叶斯网也称信念网，借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合分布概率。
一个贝叶斯网B由结构G和参数$\Theta$两部分组成，即$B=\left<G,\Theta\right>$.
其中网络结构G是一个有向无环图，其每个节点对应于一个属性，若两个属性有直接依赖关系，则他们通过一条边连接；参数$\Theta$定量描述这种依赖关系，假设属性$x_i$在G中的父节点集为$\pi_i$，则$\Theta$包含每个属性的条件概率表$\theta_{x_i\mid \pi_i}=P_B(x_i\mid \pi_i)$.
结构(介绍)
贝叶斯网结构表达了属性间的条件独立性，它假设每个属性与它的非后裔属性独立。
$B=\left<G,\Theta \right >$将属性$x_1,x_2,\ldots,x_d$的联合概率分布定义为：
\[P_B(x_1,x_2,\ldots,x_d)=\Pi_{i=1}^dP_B(x_i|\pi_i)=\Pi_{i=1}^d\theta_{x_i|\pi_i}\tag{5-1}\]可以理解为属性在给定它的父属性后与其他属性独立。
下面介绍贝叶斯网中三类典型的结构，并加以分析
-
同父结构，在给定$x_1$确定值的情况下，$x_3$与$x_4$相互独立
-
V型结构（冲撞结构），在给定确定值$x_4$的情况下，$x_1$与$x_2$必不独立；在$x_4$的值未知的情况下，$x_1$与$x_2$却是相互独立的
证明如下：
公式5-2所示的独立性称为边际独立性
- 顺序结构，给定$x$的值，$y$与$z$相互独立
下面提出一种分析有向图中变量间的条件独立性的方法，叫做有向分离：
先把有向图转化为无向图：
- 找出有向图中的所有V型结构，然后在V型结构的两个父节点之间加上一条无向边。
- 将所有有向边改为无向边
通过上述步骤产生的无向图称为道德图，令父节点相连的过程即步骤1称为”道德化”
基于道德图能直观、迅速找出变量间的独立性关系
假定道德图中有变量$x,y$和集合$\textbf z={z_j}$，如果变量$x,y$能够被变量$\textbf z$分开，即$x,y$仅通过$\textbf z$，才能成为一个连通分支，那么就成$x,y$被$\textbf z$有向分离。
学习(训练)
上面介绍了贝叶斯网的结构，貌似很有用，通过贝叶斯网我们可以直接计算出每个节点的条件概率，通过简单计数方法即可。
但是问题来了，怎么获取一个训练集的贝叶斯网？
下面介绍一种常用的方法：评分搜索
具体步骤为需要先定义一个评分函数，通过它来判断贝叶斯网和训练集的契合程度，然后基于评分函数来寻找结构最优的贝叶斯网。
因此我们的重点又转移到评分函数，在介绍评分函数之前，先提及一下信息论准则。
信息论准则将学习问题看做一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的编码位数和使用该模型描述数据所需的编码位数。
常用的评分函数通常基于信息论准则，对贝叶斯网而言，模型就是贝叶斯网(无环有向图)，每个贝叶斯网描述了一个在训练集上的概率分布，我们应该使用综合编码长度(描述网络和编码数据)最短的贝叶斯网，这就是最小描述长度（MDL）准则。
给定训练集$D={\textbf x_1,\textbf x_2,\textbf x_3,\ldots,\textbf x_m}$(类别也为属性之一)，贝叶斯网$B=\left<G,\Theta \right>$在$D$上的评分函数为：
\[s(B|D)=f(\theta)|B|-LL(B|D)\tag{5-3}\]在公式5-3中，$\mid B\mid $是贝叶斯网参数个数，$f(\theta)$描述每个参数$\theta$所需的编码位数。
其中$LL(B\mid D)$具体如下：
\[LL(B|D)=\sum_{i=1}^m\log P_B(\textbf x_i)\tag{5-4}\]公式5-4描述的是贝叶斯网的对数似然。
因此，根据上述两式，可以总结出公式5-3的第一项描述的是贝叶斯网B所需的编码位数；第二项计算对应的概率分布$P_B$对$D$描述的有多好。
因此，我们只要找到一个贝叶斯网，是的公式5-3最小即可，转化为一个优化任务。
- 若$f(\theta)=1$，即每个参数仅用1位编码描述，则得到AIC评分函数：
- 若$f(\theta)=\frac{1}{2}\log m$，即每个参数用$\frac{1}{2}\log m$位编码描述，则得到BIC评分函数:
- 若$f(\theta)=0$，则不计算网络的编码长度，则评分函数为负对数似然，学习任务变为极大似然估计：
通过公式5-3可以发现，如果固定网络$G$不变，那么第一项为常数，最小化$s(B\mid D)$等价于对参数$\Theta$的极大似然估计。
根据公式5-1与公式5-4可得，参数$\theta_{x_i\mid \pi_i}$可直接在训练集$D$上通过经验评估获得:
\[\theta_{x_i|\pi_i}=\hat P_D(x_i|\pi_i) \tag{5-7}\]公式5-7中$\hat P_D$是D上的经验分布。因此，最小化评分函数5-3，只需对网络结构进行搜索，候选结构的最优参数可以直接在训练集上计算得到。
然后，从所有的网络结构中搜索最优贝叶斯网结构是一个NP难问题，一般有两种策略解决：
- 贪心法：从某个网络结构出发，每次调整一条边(增加、删除、改变方向)，直到评分函数不在降低为止
- 通过给网络结构施加约束来消减搜索空间，例如将网络结构限定为树形结构。
推断(预测)
通过已知变量值来推断待查询变量的过程称为推断，已知变量观测值称为证据
最理想也是最直接的是通过贝叶斯网定义的联合概率分布来精确计算后验概率，但是这是NP难问题，在网络节点较多、连接稠密时，难以进行精确推断。
因此，我们需要使用近似推断避免NP难问题，即通过降低精度要求，在有限时间内求得近似解。
下面介绍近似推断的一种常用方法：吉布斯采样(一种随机采样方法)
令$\textbf Q={Q_1,Q_2,\ldots,Q_n}$表示待查询变量；
令$\textbf E={E_1,E_2,\ldots,E_k}$表示证据变量，其取值为$\textbf e={e_1,e_2,\ldots,e_k}$.
目标是计算后验概率$P(\textbf Q=\textbf q\mid \textbf E=\textbf e)$，其中$\textbf q={q_1,q_2,\ldots,q_n}$为待查询变量的取值。
如上图所示，吉布斯采样算法先随机产生一个与证据$\textbf E=\textbf e$一致的样本$\textbf q^0$作为初始点，然后每步从当前样本中产生下一个样本。在第t次采样中，算法假设$\textbf q^t=\textbf q^{t-1}$，然后对非证据变量逐个进行采样个改变其取值，采样概率根据贝叶斯网B和其他变量的当前取值（即$\textbf Z=\textbf z$）计算获得.
假定经过$T$次采样得到的与$q$一致的样本共有$n_q$个，则可近似估算出后验概率：
\[P(\textbf Q=\textbf q|\textbf E=\textbf e)\simeq\frac{n_q}{T} \tag{5-8}\]实际上，吉布斯采样的本质实在贝叶斯网所有变量的联合状态空间与证据$\textbf E=\textbf e$一致的子空间中进行随机漫步。每一步仅依赖前一步的状态，即马尔科夫链。无论从什么状态开始，马尔科夫链的第t步状态分布在$t\rightarrow \infty$时必收敛于一个平稳分布。对于吉布斯采样而言，恰好是$P(\textbf Q\mid \textbf E=\textbf e)$。因此在T很大时，吉布斯采样相当于根据$P(\textbf Q\mid \textbf E=\textbf e)$采样，从而保证公式5-8收敛于$P(\textbf Q=\textbf q\mid \textbf E=\textbf e)$
由于马尔科夫链通常需要很长的时间才能趋于平稳分布，因此吉布斯采样算法的收敛速度较慢；并且如果贝叶斯网中存在极端概率0或1，则不能保证马尔科夫链存在平稳分布，此时吉布斯采样才产生错误的估计。
6. EM算法
在之前几节中，我们假设训练样本的所有属性的值都已被观测到，即训练样本是完整的，但是在现实应用中，往往会遇到不完整的训练样本。这种情况下，怎样对模型参数进行估计
我们称未观测变量为隐变量，令$\textbf X$表示已观测变量集，$\textbf Z$表示隐变量集，$\Theta$表示模型参数。
对$\Theta$做极大似然估计，则应最大化对数似然：
\[LL(\Theta|\textbf X,\textbf Z)=\ln P(\textbf X,\textbf Z|\Theta)\tag{6-1}\]在公式6-1中，由于$\textbf Z$是隐变量，因此无法直接求解，不过我们可以通过对$\textbf Z$计算期望，来最大化已观测数据的对数”边际似然”：
\[LL(\Theta|\textbf X)=\ln P(\textbf X|\Theta)=\ln \sum_{\textbf Z}P(\textbf X,\textbf Z|\Theta) \tag{6-2}\]EM算法那是常用的估计参数隐变量的利器，是一种迭代式方法。
基本思想：
- E步：若参数$\Theta$已知，则可根据训练数据推断出最优隐变量$\textbf Z$的值
- M步：若$\textbf Z$已知，则可根据极大似然估计求解参数$\Theta$
根据公式6-2，以初始值$\Theta^0$为起点，迭代执行以下步骤直至收敛：
- 基于$\Theta^0$推断隐变量$\textbf Z$的期望，记为$\textbf Z^t$
- 基于已观测变量$\textbf X$和$\textbf Z$对参数$\Theta$做极大似然估计，记为$\Theta^{t+1}$
以上就是EM算法的原型。
事实上，隐变量估计问题也可通过梯度下降法求解，但是由于求和的项数将随着隐变量的数目以指数上升，会给梯度下降计算带来麻烦；EM算法可以看做是非梯度优化的方法，为坐标下降法。
总结
上文中的第3、4、5小节其实是有关联的，朴素贝叶斯分类器不考虑属性间的依赖关系(结果在一般情况下不错)，贝叶斯网能够能表示任意属性间的依赖性，而半朴素贝叶斯分类器则是介于两者之间，考虑属性间的部分依赖。
至于极大似然估计是一种参数估计方法，在机器学习中经常被用到，EM算法则是一种隐变量估计方法，也是一种常用方法。
上述学习笔记主要参考周志华的《机器学习》一书。
