7 贝叶斯分类器

1. 贝叶斯分类器是一种概率框架下的统计学习分类器，对分类任务而言，假设在相关概率都已知的情况下，贝叶斯分类器考虑如何基于这些概率为样本判定最优的类标。

2. （贝叶斯公式）定理：设试验$E$的样本空间为$S$，$A$为$E$的事件，$B_1,B_2,\cdots ,B_n$为样本空间$S$的一个划分，且$P(A)>0,P(B_i)>0(i=1,2,\cdots ,n)$，则有

$$P(B_i|A)=\frac{P(A|B_i)P(B_i)}{\sum _{j=1}^{n}P(A|B_j)P(B_j)}$$

若将上述定义中样本空间的划分$B_1,B_2,\cdots ,B_n$看作类标，$A$看作一个新的样本，则很容易将条件概率理解为样本$A$属于类标$B_i$的概率。

7.1 贝叶斯决策论

• 机器学习训练模型的过程中，往往我们都试图去优化一个风险函数，因此在概率框架下我们也可以为贝叶斯定义“条件风险”(Conditional Risk)：

$$R(c_i|x)=\sum _{j=1}^N{\lambda }_{ij}P(c_j|x)$$

其中，$R(c_i|x)$表示在样本$x$下选择类标$c_i$的风险，${\lambda }_{ij}$表示将类标$c_j$误判为$c_i$的损失，$P(c_j|x)$表示在样本$x$下类标$c_j$的概率。

• 贝叶斯判定准则(Bayes Decision Rule)：为了最小化总体风险，只需在每个样本上选择那个使得条件风险最小的类标。（我们的任务就是寻找一个判定准则最小化所有样本的条件风险总和）即：

$$h^{\ast }(x)=\arg \underset{c\in \mathcal{Y}}{min}R(c|x)$$

此时，我们称$h^{\ast }$为贝叶斯最优分类器(Bayes Optimal Classifier)，$R(h^{\ast })$为贝叶斯风险(Bayes Risk)。$1-R(h^{\ast })$反映了分类器的期望分类准确率。如果此时的损失函数是0-1损失函数，我们有：

$$R(c|x)=1-P(c|x)$$$$h^{\ast }(x)=\arg \underset{c\in \mathcal{Y}}{max}P(c|x)$$

即对于每个样本x，选择其后验概率$P(c|x)$最大所对应的类标，能使得总体风险函数最小，从而将原问题转化为估计后验概率$P(c|x)$的问题。

• 后验概率的估计策略：一般来说，我们有两种策略可以对后验概率进行估计：

  1. 判别式模型：直接对$P(c|x)$进行建模求解。例我们前面所介绍的决策树、神经网络、SVM都是属于判别式模型。
  2. 生成式模型：通过先对联合分布$P(x,c)$建模，从而进一步求解$P(c|x)$。贝叶斯分类器就属于生成式模型。

• 先验概率和后验概率：当我们基于贝叶斯定理对后验概率中的$P(c|x)$进行变换，有：

$$P(c|x)=\frac{P(x,c)}{P(x)}=\frac{P(x|c)P(c)}{P(x)}$$

其中，$P(c)$为类标$c$的先验(Prior)概率，$P(x|c)$为样本$x$在类标$c$下的条件概率(Class-conditional Probability)，或称作似然(Likelijhood)。$P(x)$是用于归一化的“证据”(Evidence)因子。因此，贝叶斯分类器的核心就是通过先验概率和条件概率来估计后验概率。

• 先验概率： 根据以往经验和分析得到的概率。
• 后验概率：后验概率是基于新的信息，修正原来的先验概率后所获得的更接近实际情况的概率估计。
• （实际上先验概率就是在没有任何结果出来的情况下估计的概率，而后验概率则是在有一定依据后的重新估计，直观意义上后验概率就是条件概率。）

• 实际的处理操作：

  1. 对于类先验概率$P(c)$：其就是样本空间中各类样本所占的比例，根据大数定理，当训练样本充足时，$P(c)$可以使用各类出现的频率来代替。
  2. 对于类条件概率$P(x|c)$，它表达的意思是在类别c中出现x的概率，它涉及到属性的联合概率问题，若只有一个离散属性还好，当属性多时采用频率估计起来就十分困难，因此这里一般采用极大似然法进行估计。

• 一个实际的应用例：拼写检查。（当你不小心输入一个不存在的单词时，搜索引擎会提示你是不是要输入某一个正确的单词）

Google的拼写检查基于贝叶斯方法。用户输入一个单词时，可能拼写正确，也可能拼写错误。如果把拼写正确的情况记做c（代表correct），拼写错误的情况记做w（代表wrong），那么"拼写检查"要做的事情就是：在发生w的情况下，试图推断出c。换言之：已知w，然后在若干个备选方案中，找出可能性最大的那个c，也就是求$P(c\mid w)$的最大值。而根据贝叶斯定理，有：

$$P(c\mid w)=\frac{P(w\mid c)\cdot P(c)}{P(w)}$$

由于对于所有备选的c来说，对应的都是同一个w，所以它们的$P(w)$是相同的，因此我们只要最大化分子即可。其中：

• P( c )表示某个正确的词的出现"概率"，它可以用"频率"代替。如果我们有一个足够大的文本库，那么这个文本库中每个单词的出现频率，就相当于它的发生概率。某个词的出现频率越高，P( c )就越大。比如在你输入一个错误的词“Julw”时，系统更倾向于去猜测你可能想输入的词是“July”，而不是“Jult”，因为“July”更常见。

• P(w|c)表示在试图拼写c的情况下，出现拼写错误w的概率。为了简化问题，假定两个单词在字形上越接近，就有越可能拼错，P(w|c)就越大。举例来说，相差一个字母的拼法，就比相差两个字母的拼法，发生概率更高。你想拼写单词July，那么错误拼成Julw（相差一个字母）的可能性，就比拼成Jullw高（相差两个字母）。

所以，我们比较所有拼写相近的词在文本库中的出现频率，再从中挑出出现频率最高的一个，即是用户最想输入的那个词。

大数定律：是一种描述当试验次数很大时所呈现的概率性质的定律。

大数定理：一般是在大数定律的基础上，经过严格的数学证明而得出的结论。它是概率论中的一个重要定理，描述了独立同分布随机变量序列的均值在概率意义下收敛到其数学期望的现象。

7.2 极大似然估计

使用

1. 极大似然估计(Maximum Likelihood Estimation, MLE)是一种根据数据采样来估计概率分布的经典方法。它是建立在极大似然原理上的一种估计方法。

2. 极大似然原理的直观解释是：在所有可能的概率分布中，我们应该选择那个使得观测数据出现的概率最大的概率分布作为真实分布。如，一个随机试验如有若干个可能的结果A，B，C，... ，若在一次试验中，结果A出现了，那么可以认为实验条件对A的出现有利，也即出现的概率P(A)较大。

3. 极大似然估计的策略：先假定总体具有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计。运用到类条件概率$P(x|c)$中，假设$P(x|c)$服从一个参数为 $\theta$ 的分布，问题就变为根据已知的训练样本来估计 $\theta$ 。极大似然法的核心思想就是：估计出的参数使得已知样本出现的概率最大，即使得训练数据的似然最大。

4. 极大似然估计：

   令$D_c$表示训练集中第c类样本组成的集合，假设这些样本是独立同分布的，则参数$\theta c$对于数据集$D_c$的似然为

$$L(\theta c|D_c)=P(D_c|\theta c)=\prod _{x\in D_c}P(x|\theta c)$$

一般我们使用对数似然函数来简化计算：

$$\begin{array}{rl}LL({\theta }_c)& =\log P(\theta c|D_c)\\ & =\sum _{x\in D_c}\log P(x|\theta c)\end{array}$$

此时，参数$\theta c$的极大似然估计$\widehat{\theta c}$即为：

$$\widehat{\theta c}=\arg \underset{\theta c}{max}LL(\theta c)$$

故，贝叶斯分类器的训练过程就是参数估计。

总结

1. 总结极大似然法估计参数的过程，一般为：

   1. 写出似然函数；
   2. 对似然函数取对数，并整理；
   3. 求导数，令其偏导数为0，得到似然方程组；
   4. 解似然方程组，得到所有参数即为所求。

2. 一个例子：假设样本属性都是连续值，$P(x|c)$服从一个多维高斯分布，则通过MLE计算出的参数分别为：

$$\begin{array}{rl}p(x|c)& \sim N({\mu }_c,{\sigma }_c^2)\\ {\hat{\mu }}_c& =\frac{1}{|D_c|}\sum _{x\in D_c}x\\ {\hat{\sigma }}_c^2& =\frac{1}{|D_c|}\sum _{x\in D_c}(x-{\hat{\mu }}_c)(x-{\hat{\mu }}_c{)}^T\end{array}$$

其中，${\hat{\mu }}_c$为样本均值（向量），${\hat{\sigma }}_c^2$为样本协方差（矩阵）。

上述结果看起来十分合乎实际，但是采用最大似然法估计参数的效果很大程度上依赖于作出的假设是否合理，是否符合潜在的真实数据分布，而这就需要大量的经验知识。

7.3 朴素贝叶斯分类器

• 不难看出：原始的贝叶斯分类器最大的问题在于联合概率密度函数的估计，首先需要根据经验来假设联合概率分布，其次当属性很多时，训练样本往往覆盖不够，参数的估计会出现很大的偏差。

• 为了避免这个问题，朴素贝叶斯分类器(Naive Bayes Classifier)采用了“属性条件独立性假设”，即样本数据的所有属性之间相互独立。在这种情况下，类条件概率（似然）可以改写为

$$P(x\mid c)=\prod _{i=1}^{d}P(x_i\mid c)$$

这样，为每个样本估计类条件概率变成为每个样本的每个属性估计类条件概率：

• 对于离散属性，可以直接统计频率：

$$P(x_i\mid c)=\frac{N_{ic}}{N_c}$$

• 对于连续属性，可以假设属性服从高斯分布（正态分布）：

$$P(x_i\mid c)=\frac{1}{\sqrt{2\pi }{\sigma }_{ic}}\exp (-\frac{(x_i-{\mu }_{ic}{)}^2}{2{\sigma }_{ic}^2})$$

​ 其中${\mu }_{ic}$和${\sigma }_{ic}$分别是类别$c$下属性$i$的均值和方差。

• 平滑处理(Smoothing)：相比原始贝叶斯分类器，朴素贝叶斯分类器基于单个的属性计算类条件概率更加容易操作。然而，若某个属性值在训练集中和某个类别没有一起出现过，这样会抹掉其它的属性信息，因为该样本的类条件概率被计算为0。因此在估计概率值时，常常用进行平滑处理。

其中，拉普拉斯平滑(Laplace Smoothing)是最简单的平滑方法，其实就是在分子上加1，分母加上属性的取值个数：

$$\hat{P}(c)=\frac{N_c+1}{N+|C|}$$$$\hat{P}(x_i\mid c)=\frac{N_{ic}+1}{N_c+|V_i|}$$

其中$|C|$是类别的个数，$|V_i|$是属性$i$的取值个数。

当训练集越大时，拉普拉斯修正引入的影响越来越小。对于贝叶斯分类器，模型的训练就是参数估计，因此可以事先将所有的概率储存好，当有新样本需要判定时，直接查表计算即可。

7.4 半朴素贝叶斯分类器

1. 朴素贝叶斯分类器采用了“属性条件独立性假设”，而在现实任务中这个假设往往很难成立。所以，朴素贝叶斯分类器的一个显著缺点是：当属性之间有相关性时，朴素贝叶斯分类器的性能会下降。

2. 为了解决这个问题，半朴素贝叶斯分类器(Semi-Naive Bayes Classifier)引入了属性选择的概念，即对于每个类别，选择一个属性子集，这个子集中的属性之间是条件独立的，但是属性之间可以有关联。独依赖估计(One-Dependent Estimator, ODE)是半朴素贝叶斯分类器的一种典型方法。

$$P(c\mid x)\propto P(c)\prod _{i=1}^{d}P(x_i\mid c,p{a}_i)$$

其中，$p{a}_i$是属性$x_i$的父属性集合，$P(x_i\mid c,p{a}_i)$是在类别$c$下属性$x_i$的条件概率。那么问题就转化为了如何选择父属性集合$p{a}_i$。

1. 选择父属性集合的方法：

   1. “超父”(Super-Parent)：选择一个属性作为所有属性的父属性，即$p{a}_i=\{x_1,x_2,\cdots ,x_{i-1},x_{i+1},\cdots ,x_d\}$。
   2. "TAN"(Tree Augmented Naive Bayes)：在训练集上构建一个最大权重生成树，树的每个节点是一个属性，树的边表示属性之间的相关性。在预测时，根据生成树的结构计算条件概率。

2. ADOE(Averaged One-Dependent Estimator)：这是一种基于集成学习机制，更为强大的独依赖分类器。ADOE通过随机选择属性子集，构建多个ODE分类器，最后将这些分类器的预测结果进行平均。即：

$$P(c\mid x)\propto \sum _{i=1,|D_{x_i}|\ge m^{\prime }}^{d}P(c,x_i)\prod _{j=1}^{d}P(x_j\mid c,x_i)$$

其中，$D_{x_i}$是在第i个属性上取值为$x_i$的样本的集合，$m^{\prime }$为阈值常数，一般为30。

不难看出，与朴素贝叶斯分类器类似，AODE的训练过程也是“计数”，即在训练数据集上对符合条件的样本进行计数的过程。与朴素贝叶斯分类器相似，AODE无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，并且易于实现增量学习。

7.5 贝叶斯网

1. 贝叶斯网(Bayesian Network)也称作“信念网”，是一种概率图模型，用于描述随机变量之间的依赖关系。贝叶斯网是一个有向无环图(Directed Acyclic Graph, DAG)，其中节点表示随机变量，边表示变量之间的依赖关系。这里，对于离散型的随机变量，可以用条件概率表(Conditional Probability Table, CPT)来表示节点的条件概率分布；对于连续型的随机变量，可以用高斯分布来表示节点的条件概率分布。

2. 贝叶斯网的具体构成：贝叶斯网$B$由结构$G$和参数$\mathrm{\Theta }$两部分构成，即$B=⟨G,\mathrm{\Theta }⟩$。

   1. 节点：表示随机变量，每个节点都有一个条件概率分布。
   2. 边：表示变量之间的依赖关系，即一个节点的条件概率分布依赖于其父节点的取值。
   3. 条件概率表：用于描述节点的条件概率分布，即给定父节点的取值，子节点的取值的概率。

   例：假设节点E直接影响到节点H，即E->H，则用从E指向H的箭头建立结点E到结点H的有向弧(E,H)，权值(即连接强度)用条件概率$P(H\mid E)$来表示。

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

3. 表示：令$G=(L,E)$表示一个有向无环图(DAG)，其中 L 代表图形中所有的节点的集合，而 E 代表有向连接线段的集合，且令$X=\{x_i\mid i\in L\}$为其有向无环图中的某一节点 i 所代表的随机变量，若节点 X 的联合概率可以表示成：

$$p(x)=\prod _{i=1}^{n}p(x_i\mid x_{{\pi }_i})$$

其中$x_{{\pi }_i}$表示节点 X 的父节点集合，即节点 i 的所有父节点的集合，则称X为相对于一有向无环图$G$的贝叶斯网络。

此外，对于任意的随机变量，其联合概率可以由各自的局部概率分布相乘而推出：

$$P(x_1,x_2,\cdots ,x_k)=P(x_k\mid x_1,x_2,\cdots ,x_{k-1})P(x_{k-1}\mid x_1,x_2,\cdots ,x_{k-2})\cdots P(x_2\mid x_1)P(x_1)$$

1. 贝叶斯网络的3种结构形式：

• （前置）D-分离(D-Separation)：$X$和$Y$在给定$Z$的条件下是条件独立的，即$P(X,Y\mid Z)=P(X\mid Z)P(Y\mid Z)$。

• （形式一）Head-to-Head：形如$X$和$Y$都是$Z$的父节点的情况。如图所示。

此时，我们有$P(a,b,c)=P(a)\cdot P(b)\cdot P(c|a,b)$成立。化简得：

$$\sum _{c}P(a,b,c)=\sum _{c}P(a)\cdot P(b)\cdot P(c|a,b)\Rightarrow P(a,b)=P(a)\cdot P(b)$$

即在c未知的条件下，a、b被阻断(blocked)，是独立的，称之为head-to-head条件独立。

• （形式二）Tail-to-Tail：形如$X$和$Y$都是$Z$的子节点的情况。如图所示。

考虑$c$未知和$c$已知的情况。

1. 在c未知的时候，有：$P(a,b,c)=P(c)\cdot P(a|c)\cdot P(b|c)$，此时，没法得出$P(a,b)=P(a)P(b)$，即c未知时，a、b不独立。
2. 在c已知的时候，有：$P(a,b\mid c)=P(a,b,c)/P(c)$，此时，有$P(a,b\mid c)=P(a\mid c)\cdot P(b\mid c)$，即c已知时，a、b独立。

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

• （形式三）Head-to-Tail：即链式的网络结构。还是分为$c$未知和$c$已知的两种情况。

1. 当$c$未知，$P(a,b,c)=P(a)\cdot P(c|a)\cdot P(b|c)$，但无法推出$P(a,b)=P(a)P(b)$，即c未知时，a、b不独立。

2. 当$c$已知，$P(a,b\mid c)=P(a,b,c)/P(c)$，且根据条件概率的有关内容，可以推出$P(a,b\mid c)=P(a\mid c)\cdot P(b\mid c)$，即c已知时，a、b独立。所以，在c给定的条件下，a，b被阻断(blocked)，是独立的，称之为head-to-tail条件独立。

3. 马尔可夫链(Markov Chain)：马尔可夫链是一种特殊的贝叶斯网络，其节点之间的连接是连续的，即$X_1\to X_2\to X_3\to \cdots \to X_n$，且每个节点的状态只与其前一个节点的状态有关，与其它节点无关。这种链式结构的贝叶斯网络称为马尔可夫链。上面的情况，就是马尔可夫链。

4. 贝叶斯网络的实例：

给定如下图所示的贝叶斯网络：

其中，各个单词、表达式表示的含义如下：

• smoking表示吸烟，其概率用P(S)表示，lung Cancer表示的肺癌，一个人在吸烟的情况下得肺癌的概率用P(C|S)表示，X-ray表示需要照医学上的X光，肺癌可能会导致需要照X光，吸烟也有可能会导致需要照X光（所以smoking也是X-ray的一个因），所以，因吸烟且得肺癌而需要照X光的概率用P(X|C,S)表示。
• Bronchitis表示支气管炎，一个人在吸烟的情况下得支气管炎的概率用P(B|S)，dyspnoea表示呼吸困难，支气管炎可能会导致呼吸困难，肺癌也有可能会导致呼吸困难（所以lung Cancer也是dyspnoea的一个因），因吸烟且得了支气管炎导致呼吸困难的概率用P(D|S,B)表示。

Lung Cancer简记为C，Bronchitis简记为B，dyspnoea简记为D，且C = 0表示lung Cancer不发生的概率，C = 1表示lung Cancer发生的概率，B等于0（B不发生）或1（B发生）也类似于C，同样的，D=1表示D发生的概率，D=0表示D不发生的概率，便可得到dyspnoea的一张概率表，如上图的最右下角所示。

对于上图，在一个人已经呼吸困难（dyspnoea）的情况下，其抽烟（smoking）的概率是多少呢？即：P(s|d=1)=? 推导：

解释下上述式子推导过程：

• 第二行：对联合概率关于b,x,c求和（在d=1的条件下），从而消去b,x,c，得到s和d=1的联合概率。
• 第三行：最开始，所有变量都在sigma(d=1,b,x,c)的后面（sigma表示对“求和”的称谓），但由于P(s)和“d=1,b,x,c”都没关系，所以，可以提到式子的最前面。而且P(b|s)和x、c没关系，所以，也可以把它提出来，放到sigma(b)的后面，从而式子的右边剩下sigma(x)和sigma(c)。
• 此外，图中Variable elimination表示的是变量消除的意思。

参考资料

超详细讲解贝叶斯网络(Bayesian network) - USTC丶ZCC - 博客园 (cnblogs.com)

7.6 EM算法

EM算法介绍

期望最大化算法（Expectation Maximization Algorithm, EM）是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计。EM算法主要应用于训练集样本不完整即存在隐变量时的情形（例如某个属性值未知），通过其独特的“两步走”策略能较好地估计出隐变量的值。

EM算法的思想

1. EM算法是一种迭代式的方法，其基本思想是：若样本服从的分布参数 $\theta$ 已知，则可以根据已观测到的训练样本推断出隐变量 $Z$ 的期望值（E步），若 $Z$ 的值已知则运用最大似然法估计出新的 $\theta$ 值（M步）。重复这个过程直到 $Z$ 和 $\theta$ 值不再发生变化。

2. 具体例子：设我们想估计A和B这两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。即：

   • 基于${\mathrm{\Theta }}^t$推断隐变量$Z$的期望，记为$Z^t$；（离散值：取概率的最大值；连续值：计算期望值）
   • 基于已观测变量$X$和$Z^t$对参数作极大似然估计，记作${\mathrm{\Theta }}^{t+1}$；
   • 以上步骤，反复迭代，直到收敛。

EM算法的数学推导

“边际似然”(Marginal Likelihood)：当样本属性已知时，采用极大化对数似然，后对每个参数求偏导计算出参数的值。而当存在隐变量时，由于隐变量的存在，无法直接计算似然函数，此时需要引入边际似然的概念。

$$LL(\mathrm{\Theta }\mid X)=\ln P(X\mid \mathrm{\Theta })=\ln \sum _{Z}P(X,Z\mid \mathrm{\Theta })$$

现在与最大似然不同的只是似然函数式中多了一个未知的变量Z，也就是说我们的目标是找到适合的θ和Z让L(θ)最大，这样我们也可以分别对未知的θ和Z求偏导，再令其等于0。

化简：我们有：

$$\begin{array}{rl}\sum _i\log p(x^i;\theta )& =\sum _i\log \sum _{z^i}p(x^i,z^i;\theta )\\ & =\sum _i\log \sum _{z^i}q(z^i)\frac{p(x^i,z^i;\theta )}{q(z^i)}\\ & \ge \sum _i\sum _{z^i}q(z^i)\log \frac{p(x^i,z^i;\theta )}{q(z^i)}\end{array}$$

其中，因为对数函数是上凸函数，所以在最后一步，使用了Jensen不等式，将上式“和的对数”变为“对数的和”，这样就非常容易求导了。

接着，求解$q_i,\theta$：

$$\begin{array}{rl}\frac{\partial }{\partial \theta }\sum _i\sum _{z^i}q(z^i)\log \frac{p(x^i,z^i;\theta )}{q(z^i)}& =0\\ \frac{\partial }{\partial q(z^i)}\sum _i\sum _{z^i}q(z^i)\log \frac{p(x^i,z^i;\theta )}{q(z^i)}& =0\end{array}$$

通过求解上述两个方程，我们可以得到$q_i,\theta$的迭代公式。

简单的理解：固定θ计算Q的过程就是在建立$L(\theta )$的下界，即通过琴生不等式得到的下界（E步）；固定Q计算θ则是使得下界极大化（M步），从而不断推高边缘似然$L(\theta )$。从而循序渐进地计算出$L(\theta )$取得极大值时隐变量Z的估计值。

EM算法也可以看作一种“坐标下降法”，首先固定一个值，对另外一个值求极值，不断重复直到收敛。

EM算法的流程

这里有不同的版本，互相了解，学习。

版本一：

版本二：