⇧
❮
❯
↻
🍀机器学习🍀 2810字 15分钟

机器学习基础笔记（7）：贝叶斯分类

作者

本文介绍一类概率模型——贝叶斯分类器。

Hyplus目录

0 贝叶斯定理

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

\begin{aligned}
P(B_i \mid A)=\frac{P(A\mid B_i)P(B_i)}{\sum\limits_{j=1}^n P(A\mid B_j)P(B_j)},\ i=1,2,\dots,n
\end{aligned}

1 贝叶斯决策论

贝叶斯决策论（Bayesian Decision Theory）是概率框架下实施决策的基本方法，在分类任务中考虑如何基于各已知概率和误判损失来选择最优的类别标记。本节以多分类任务为例进行介绍，且所有属性均为离散型。

信息理论中的基本概念：

  • 先验（Prior）概率：根据以往经验和分析得到的概率。
  • 后验（Posterior）概率：基于新的信息，修正原来的先验概率后所获得的更接近实际情况的概率估计。

假设有N种可能的类别标记\mathcal{Y}=\{c_1,c_2,\dots,c_N\}，\lambda_{ij}为将一个真实标记为c_j的样本误分类为c_i所产生的损失。基于后验概率P(c_i\mid \mathbf{x})可获得将样本\mathbf{x}分类为c_i所产生的期望损失（Expected Loss），在决策论中常称为在样本\mathbf{x}上的条件风险（Conditional Risk），即

\begin{aligned}
R(c_i\mid \mathbf{x}) = \sum\limits_{j=1}^N \lambda_{ij}P(c_j\mid \mathbf{x})
\end{aligned}

主要任务为寻找一个判定准则h:\mathcal{X}\mapsto \mathcal{Y}以最小化总体风险，其中总体风险可表示为

\begin{aligned}
R(h)=\mathbb{E}_{\mathbf{x}} \left [R(h(\mathbf{x})\mid \mathbf{x})\right]
\end{aligned}

显然，若能最小化条件风险，则总体风险亦将被最小化。因此产生了贝叶斯判定准则（Bayes Decision Rule）：为了最小化总体风险，只需在每个样本上选择那个能使条件风险最小的类标，即

\begin{aligned}
h^*(\mathbf{x})=\underset{c\in\mathcal{Y}}{\arg \min} R(c\mid \mathbf{x})
\end{aligned}

此时，h^*称为贝叶斯最优分类器（Bayes Optimal Classifier），与之对应的总体风险R(h^*)称为贝叶斯风险（Bayes Risk）。1-R(h^*)反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

若损失函数取0-1损失，即\lambda_{ij}=\mathbb{i \ne j}，则有

\begin{aligned}
R(c\mid \mathbf{x})=1-P(c\mid \mathbf{x})\\
h^*(\mathbf{x})=\underset{c\in\mathcal{Y}}{\arg \max} P(c\mid \mathbf{x})
\end{aligned}

即对于每个样本\mathbf{x}，选择其后验概率P(c\mid \mathbf{x})最大所对应的类标，能使得总体风险最小，从而将原问题转化为估计后验概率P(c\mid \mathbf{x})。对此一般有两种策略：

  • 判别式模型（Discriminative Models）：直接对P(c\mid \mathbf{x})进行建模求解。决策树、BP神经网络、SVM均属于判别式模型。
  • 生成式模型（Generative Models）：先对联合分布P(\mathbf{x},c)建模，进一步求解P(c\mid \mathbf{x})=\dfrac{P(\mathbf{x},c)}{P(\mathbf{x})}。贝叶斯分类器属于生成式模型。

基于贝叶斯定理，可将后验概率改写为

\begin{aligned}
P(c\mid \mathbf{x})=\dfrac{P(c)P(\mathbf{x}\mid c)}{P(\mathbf{x})}
\end{aligned}

其中P(c)是类先验概率；P(\mathbf{x}\mid c)是样本\mathbf{x}相对于类标c的类条件概率（Class-conditional Probability），又称为似然（Likelihood）；P(\mathbf{x})是用于归一化的证据（Evidence）因子。由此将估计后验概率转化为如何基于训练数据D来估计先验和似然的问题。

类先验概率P(c)表达了样本空间中各类样本所占的比例，根据大数定理（当样本足够多时，频率趋于稳定等于其概率），当训练样本充足时，P(c)可通过各类样本出现的频率来进行估计。

因此只剩下类条件概率P(\mathbf{x}\mid c)，其意为在类别c中出现\mathbf{x}的概率，涉及到关于\mathbf{x}所有属性的联合概率，当属性过多时根据样本出现的频率来估计会相当困难，因此一般采用极大似然法进行估计。

2 极大似然估计

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。具体地，假设P(\mathbf{x}\mid c)具有确定的形式并且被参数向量\mathbb{\theta}_c唯一确定，则可将任务转化为利用训练集D估计参数\mathbb{\theta}_c。为明确起见，本节中将P(\mathbf{x}\mid c)记为P(\mathbf{x}\mid \mathbb{\theta}_c)。

事实上，概率模型的训练过程就是参数估计（Parameter Estimation）过程。极大似然估计（Maximum Likelihood Estimation，MLE），是一种根据数据采样来估计概率分布的经典方法。核心思想：若估计的参数使得已知样本出现的概率最大，则使得训练数据的似然最大。

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

\begin{aligned}
P(D_c\mid \mathbb{\theta}_c)=\prod\limits_{\mathbf{x}\in D_c}P(\mathbf{x}\mid \mathbb{\theta}_c)
\end{aligned}

上式的连乘操作易造成下溢，通常使用对数似然（Log-Likelihood），即

\begin{aligned}
LL(\mathbb{\theta}_c) &= \log P(D_c\mid \mathbb{\theta}_c)\\
 &= \sum\limits_{\mathbf{x} \in D_c} \log P(\mathbf{x}\mid \mathbb{\theta}_c)
\end{aligned}

此时参数\mathbb{\theta}_c的极大似然估计为

\begin{aligned}
{\hat \mathbb{\theta}}_c = \underset{\mathbb{\theta}_c}{\arg \min} LL(\mathbb{\theta}_c)
\end{aligned}

最大似然法估计参数的4个步骤：

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

例如，在连续属性情形下，假设概率密度函数p(\mathbf{x} \mid c) \sim \mathcal{N} (\mathbf{\mu}_c,\mathbf{\sigma}_c^2)，则参数\mathbf{\mu}_c和\mathbf{\sigma}_c^2的极大似然估计为

\begin{aligned}
{\hat \mathbf{\mu}}_c &=\frac{1}{|D_c|}\sum\limits_{\mathbf{x}\in D_c}\mathbf{x}\\
{\hat \mathbf{\sigma}}_c^2 &= \frac{1}{|D_c|}\sum\limits_{\mathbf{x}\in D_c}(\mathbf{x}-{\hat \mathbf{\mu}}_c)(\mathbf{x}-{\hat \mathbf{\mu}}_c)^\top
\end{aligned}

可见，通过极大似然法得到的正态分布均值就是样本均值，方差就是(\mathbf{x}-{\hat \mathbf{\mu}}_c)(\mathbf{x}-{\hat \mathbf{\mu}}_c)^\top的均值。离散属性情形与之同理。

上述结果看起来十分合乎实际，但是采用最大似然法估计参数的效果很大程度上依赖于作出的假设是否合理、是否符合潜在的真实数据分布。因此在现实应用中，往往更需要大量关于应用任务本身的经验知识，尽可能避免产生误导性的结果。

3 朴素贝叶斯分类器

不难发现，基于贝叶斯定理来估计后验概率的主要困难在于：类条件概率是所有属性上的联合概率，难以从有限的训练样本直接估计而得。为了避开这个障碍，朴素贝叶斯分类器（Naïve Bayes Classifier）采用了属性条件独立性假设（Attribute Conditional Independence Assumption）：对于已知类别，假设所有属性相互独立，即可将类条件概率改写为

\begin{aligned}
P(\mathbf{x}\mid c)=\prod\limits_{i=1}^d P(x_i\mid c)
\end{aligned}

其中d为属性数目，x_i为\mathbf{x}在第i个属性上的取值。据此，可将后验概率改写为

\begin{aligned}
P(c\mid \mathbf{x})=\dfrac{P(c)P(\mathbf{x}\mid c)}{P(\mathbf{x})}=\dfrac{P(c)}{P(\mathbf{x})}\prod\limits_{i=1}^d P(x_i\mid c)
\end{aligned}

易知对所有类别来说P(\mathbf{x})相同，由此可得朴素贝叶斯分类器的表达式：

\begin{aligned}
h_{\text{nb}}(\mathbf{x})=\underset{c\in\mathcal{Y}}{\arg \max} P(c) \prod\limits_{i=1}^d P(x_i\mid c)
\end{aligned}

显然，朴素贝叶斯分类器的训练过程就是基于训练集D来估计类先验概率P(c)，并为每个属性估计条件概率P(x_i\mid c)。

若有充足的独立同分布样本，则可很容易地估计出类先验概率，为

\begin{aligned}
P(c)=\frac{|D_c|}{|D|}
\end{aligned}

对于离散属性，令D_{c,x_i}表示D_c中在第i个属性上取值为x_i的样本组成的集合，则条件概率可估计为

\begin{aligned}
P(x_i\mid c)=\frac{|D_{c,x_i}|}{|D_c|}
\end{aligned}

对于连续属性可考虑概率密度函数，假定p(x_i\mid c)\sim \mathcal{N}(\mu_{c,i},\sigma_{c,i}^2)，其中\mu_{c,i},\sigma_{c,i}^2分别为第c类样本在第i个属性上取值的均值和方差，则有

\begin{aligned}
p(x_i\mid c)=\frac{1}{\sqrt{2\pi} \sigma_{c,i}}\exp \left (-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2} \right )
\end{aligned}

需要注意的是，若某个属性值在训练集中没有与某个类别同时出现过，这会导致其他属性信息被“抹去”，因为该样本的类条件概率被计算为0。因此在估计概率值时常需进行平滑（Smoothing）处理，通常采用拉普拉斯修正（Laplacian Correction）。令N表示训练集D中可能的类别数，N_i表示第i个属性可能的取值数，则类先验概率和条件概率的估计式分别修正为

\begin{aligned}
\hat P(c) &=\frac{|D_c|+1}{|D|+N}\\
\hat P(x_i\mid c) &=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}
\end{aligned}

当训练集越大时，拉普拉斯修正引入的影响越来越小。对于贝叶斯分类器，由于模型的训练就是参数估计，故可事先将所有概率储存起来，这样在进行预测时只需“查表”即可进行判别。若任务数据更替频繁，则可采用懒惰学习（Lazy Learning）方式（见后续篇章），先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。

4 改进模型

针对朴素贝叶斯分类器的诸多缺陷，后续又进行了一系列改进，提出了半朴素贝叶斯分类器（Semi-naïve Bayes Classifier）、贝叶斯网（Bayesian Network）等模型。

WIP

5 EM算法

前述讨论均假设所有属性变量的值均已被观测到，但实际应用中常存在未观测的隐变量（Latent Variable）。令\mathbf{X}表示已观测变量集，\mathbf{Z}表示隐变量集，\mathbf{\Theta}表示模型参数，若欲对\mathbf{\Theta}做极大似然估计，则应最大化对数似然，即

\begin{aligned}
LL(\mathbf{\Theta}\mid \mathbf{X},\mathbf{Z})=\ln P(\mathbf{X},\mathbf{Z}\mid \mathbf{\Theta})
\end{aligned}

然而由于隐变量\mathbf{Z}的存在，上式无法直接求解，此时可通过对\mathbf{Z}计算期望，来最大化已观测数据的对数边际似然（Marginal Likelihood），即

\begin{aligned}
LL(\mathbf{\Theta}\mid \mathbf{X})=\ln P(\mathbf{X}\mid \mathbf{\Theta})=\ln \sum\limits_{\mathbf{Z}}P(\mathbf{X},\mathbf{Z}\mid \mathbf{\Theta})
\end{aligned}

EM（Expectation-Maximization，期望最大化）算法是一种常用的估计参数隐变量的利器，是一种迭代式的方法。基本思路：若参数\mathbf{\Theta}已知，则可根据训练数据推断出最优隐变量\mathbf{Z}的值（E步）；反之，若\mathbf{Z}的值已知，则可方便地堆参数\mathbf{\Theta}做极大似然估计（M步）。

于是，以初始值\mathbf{\Theta}^0为起点，可对上式迭代执行以下步骤直至收敛：

  1. 基于\mathbf{\Theta}^t推断隐变量\mathbf{Z}的期望，记为\mathbf{Z}^t
  2. 基于已观测变量\mathbf{X}和\mathbf{Z}^t对参数\mathbf{\Theta}做极大似然估计，记为\mathbf{\Theta}^{t+1}

以上为EM算法原型。进一步，若不取\mathbf{Z}的期望，而是基于\mathbf{\Theta}^t计算隐变量\mathbf{Z}的概率分布P(\mathbf{Z}\mid \mathbf{X},\mathbf{\Theta}^t)，则可得EM的两个步骤：

  1. E步（Expectation）：以当前参数\mathbf{\Theta}^t推断隐变量分布P(\mathbf{Z}\mid \mathbf{X},\mathbf{\Theta}^t)，并计算对数似然LL(\mathbf{\Theta}\mid \mathbf{X},\mathbf{Z})关于\mathbf{Z}的期望，即
\begin{aligned}
Q(\mathbf{\Theta}\mid \mathbf{\Theta}^t)=\mathbb{E}_{\mathbf{Z}\mid \mathbf{X},\mathbf{\Theta}^t} LL(\mathbf{\Theta}\mid \mathbf{X},\mathbf{Z})
\end{aligned}
  1. M步（Maximization）：寻找参数最大化期望似然，即
\begin{aligned}
\mathcal{\Theta}^{t+1} =\underset{\mathcal{\Theta} }{\arg\max} Q(\mathbf{\Theta}\mid \mathbf{\Theta}^t)
\end{aligned}

事实上，隐变量估计问题也可通过梯度下降等优化算法求解，但由于求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；EM算法可视为用坐标下降法（Coordinate Descent）来最大化对数似然下界的过程。

发表评论