朴素贝叶斯分类器

朴素贝叶斯分类器是基于贝叶斯定理与特征条件独立假设的分类方法。

1. 历史背景

朴素贝叶斯分类器最早的出现时间在 1964 年，由 Mosteller 和 Wallace 第一次应用在文本信息检索领域。

朴素贝叶斯分类器的核心就是贝叶斯定理，而贝叶斯定理最早由托马斯·贝叶斯所发现。

贝叶斯于 1701 年至 1761 年间居住在英国，他出生于赫特福德郡，1719 年至 1722 年间就读于爱丁堡大学，学习逻辑学和神学。

1734 年搬到肯特后，他继承了家族传统并一直担任西恩山教堂的牧师直到 1752 年。

贝叶斯在 30 多岁时只发表了两篇论文，一篇神学领域的，另一篇是数学领域的，并未产生多大影响。作为长老会牧师，他继续过着简朴的生活。

直到贝叶斯去世后，他的朋友理查德·普莱斯收集并发表了贝叶斯有关概率的研究内容。普莱斯非常重视贝叶斯的想法，并对遗留手稿进行编辑、纠正、阐述说明，在 1763 年发表文章“An Essay towards solving X Problem in the Doctine of Chances”。可以说，没有普莱斯的工作，贝叶斯理论将不会闻名于世。

但将贝叶斯理论推广开来，最终成为贝叶斯定理的是法国人拉普拉斯。

补充一点，理论（theory）和定理（theorem）是不同的。前者是一种可验证但尚待证明（或目前在文明的段时间跨度内无法证明）的解释或陈述，后者是由公理证明的结果（被普遍接受为真理的数学逻辑或定律）。

2. 基本原理

假设训练数据集：

$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$

其中，${\displaystyle \mathbf x_i\in \mathcal{X}\subseteq R^n}$ 表示实例的特征向量，$y\in \mathcal{Y}=\{c_1,c_2,\cdots,c_k\}$ 表示实例的类别，也就是标记（label）。给定实例特征向量$\mathbf x$，输出所属的类 $y$ 。

从概率的角度来看，$X$ 是定义在输入空间 $\mathcal{X}$ 上的随机向量，$Y$ 是定义在输出空间 $\mathcal{Y}$ 上的随机变量。$P(X,Y)$ 是 $X$ 和 $Y$ 的联合概率分布。因此，训练数据集就是由 $P(X,Y)$ 独立同分布产生的。

我们再简单回顾一下贝叶斯定理。贝叶斯定理实际是由条件概率和全概率公式得到的。

从两个事件的条件概率开始，在 $y$ 事件已经发生的情况下，事件 $x$ 发生的概率：

$P(x|y)=\frac{P(xy)}{P(y)}$

而在事件 $x$ 已经发生，而 $y$ 事件发生的概率：

$P(y|x)=\frac{P(xy)}{P(x)}$

联立两个公式就可以得到：

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

在机器学习的场景中，$P(x|y)$ 就是当标签是 $y$ 的情况下，特征是 $x$ 的概率。在现实情况中，$P(x|y)$、$P(y)$、$P(x)$ 是可以求得的，这样就可以计算在某个特征的情况下，属于哪个类标签的概率 $P(y|x)$。这就是贝叶斯方程。

$P(x)$ 可以通过全概率公式进一步分解

$\begin{aligned} P(x)&= P(xy)+P(x\overline{y})\\ &= P(x|y)P(y)+P(x|\overline{y})P(\overline{y})\\ \end{aligned}$

如果标签的空间不仅仅分为 $y$ 和 $\overline{y}$，而是多个分割，那就可以得到更一般的贝叶斯公式

（贝叶斯公式）　设 $y_1,y_2,\cdots,y_n$ 是基本空间 $\Omega$ 的一个分割，且它们各自概率 $P(y_1),P(y_2),\cdots,P(y_n)$ 皆已知且为正，又设 $x$ 是 $\Omega$ 中的一个事件，$P(x)>0$，且在诸 $y_i$ 下事件 $x$ 的条件概率 $P(x|y_1),P(x|y_2),\cdots,P(x|y_n)$ 可通过试验等手段获得，则在 $x$ 给定下，事件 $y_k$ 的条件概率为

$P(y_k|x)=\frac{P(x|y_k)P(y_k)}{\sum\limits^n_{i=1}P(x|y_i)P(y_i)},k=1,2,\cdots,n$

上述公式是在一个特征 $x$ 的情况下，如果是多个特征，则需要求这多个特征的条件概率分布。

$P(X=\mathbf{x}|Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,\cdots,K$

条件联合概率分布 $P(X=\mathbf{x}|Y=c_k)$ 有指数级数量的参数，假设 $x^{(j)}$ 可取值有 $N_j$ 个，$j=1,2,\cdots,n$，Y可取值有 $K$ 个，那么参数个数为 $K\prod \limits_{j=1}^nN_j$。如果一个特征空间和类别都是二元的，维度是10，那么需要估计的参数就有2048个，平均每个参数需要100个观测值的话，那就需要20万组数据，随着特征维度的增加，这个值还会随指数增长。

除此之外，如果数据量不够大的情况下，由于数据的稀疏性，很容易统计到某个参数估计为0的情况，这也是不对的。

也就是不同特征组合情况很多，可能很多组合下都没有样本实例，不能简单认为这种可能性就不存在。

朴素贝叶斯在求解条件概率分布时做了一个非常强的假设，条件独立性（conditional independence）。它的意思是在给定的类别下，不同维度特征的取值之间是相互独立的。朴素贝叶斯也因此得名。

$\begin{aligned} P(X=\mathbf{x}|Y=c_k)&=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,\cdots,K\\ &= \prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)\\ \end{aligned}$

朴素贝叶斯法实际上学习到生成数据的机制，所以属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单，但有时会牺牲一定的分类准确率。

将上式带入贝叶斯公式，可以得到后验概率分布 $P(Y=c_k|X=\mathbf{x})$

$P(Y=c_k|X=\mathbf{x})=\frac{P(Y=c_k)\prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum\limits_k P(Y=c_k)\prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)},k=1,2,\cdots,n$

朴素贝叶斯实际是一个概率分类器，求出在不同类别下某一特征的概率分布，找到最大后验概率的类别即可。同时上式中的分母实际就是 $P(X=\mathbf{x})$，可以直接求得，并且由于同一特征分母均相同，可以省略分母，就是只比较分子的大小，选出最大的即可。

$\begin{aligned} \hat{y}&=\arg\max_{c_k}P(Y=c_k|X=\mathbf{x})\\ &= \arg\max_{c_k} \frac{P(Y=c_k)\prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum\limits_k P(Y=c_k)\prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}\\ &= \arg\max_{c_k} P(Y=c_k)\prod \limits_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k) \end{aligned}$

3. 最大化含义

朴素贝叶斯法将实例分到后验概率最大的类。这等价于期望风险最小化。假设损失函数：

${\displaystyle L(Y,f(X))={ \begin{cases} +1&Y\ne f(X)\\ -1&Y=f(X) \end{cases} } }$

式中 $f(X)$ 是分类决策函数。这时，期望风险函数为

$R_{\exp}(f)=E[L(Y,f(X))]$

期望是对联合分布 $P(X,Y)$ 取的。由此取条件期望

$R_{\exp}(f)=E_X\sum^{K}_{k=1}[L(c_k,f(X))]P(c_k|X)$

为了使期望风险最小化，需要对 $X=x$ 逐个极小化，由此得到：

$\begin{aligned} f(x)&=\arg\min_{y\in \mathcal Y}\sum^K_{k=1}L(c_k,y)P(c_k|X=x)\\ &=\arg\min_{y\in \mathcal Y}\sum^K_{k=1}P(y\not ={c_k}|X=x)\\ &=\arg\min_{y\in \mathcal Y}(1-P(y=c_k|X=x))\\ &=\arg\max_{y\in \mathcal Y}P(y=c_k|X=x) \end{aligned}$

这样一来，根据期望风险最小化准则就得到了后验概率最大化准则：

$f(x)=\arg\max_{c_k}P(c_k|X=x)$

4. 参数估计

以上可以知道要对哪些参数需要估计，那么具体如何对参数进行估计？可以用到极大似然估计或者贝叶斯估计。

需要估计的参数有先验概率 $P(Y=c_k)$ 、条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$。

先验概率 $P(Y=c_k)$ 的极大似然估计：

$P(Y=c_k)=\frac{\sum\limits^N_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K$

条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$ 的极大似然估计：

$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits^N_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits^N_{i=1}I(y_i=c_k)}$

式中，$x_i^{(j)}$ 是样本的第 $j$ 个特征，$a_{jl}$ 是 $x^{(j)}$ 可能的取的第 $l$ 个值，$I$ 为指示函数，也就是计数。

用极大似然估计可能会出现所要估计的概率值为 $0$ 的情况，这会影响到后验概率的计算结果，使分类产生偏差。解决方法是采用贝叶斯估计：

$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits^N_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum\limits^N_{i=1}I(y_i=c_k)+S_j\lambda}$

式中，$\lambda \ge 0$ ， $S_j$ 是 $l$ 的最大取值，即第 $j$ 个特征的可选分类数量。

上式相当于在随机变量各个取值的频数上赋予一个正数 $\lambda>0$ 。当 $\lambda=0$ 时就是极大似然估计。当 $\lambda=1$ 时，称为拉普拉斯平滑（Laplacian smoothing）。显然，对于任何 $l=1,2,\cdots,S_j$ ， $k=1,2,\cdots,K$ ，都满足

$P_\lambda(X^{(j)}=a_{jl}|Y=c_k)>0$ $\sum^{S_j}_{l=1}P(X^{(j)}=a_{jl}|Y=c_k)=1$

满足概率的公理化定义，表明条件概率 $P_\lambda(X^{(j)}=a_{jl}|Y=c_k)$ 是一种概率分布。

同样，先验概率的贝叶斯估计是

$P_\lambda(Y=c_k)=\frac{\sum\limits^N_{i=1}I(y_i=c_k)+\lambda}{N+K\lambda},k=1,2,\cdots,K$

5. 算法流程

以下给出朴素贝叶斯的完整算法。有些时候朴素贝叶斯计算会把后验概率映射到对数空间进行计算，这样做的好处是避免值太小以及加快计算速度（avoid underflow and increase speed）。

算法输入： 训练数据集 $T$ 和实例 $\mathbf x$。

$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$

其中 $\mathbf x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$，$x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征，$x_i^{(j)}\in\{a_{j1},a_{j2},\cdots,a_{jS_j}\}$，$a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值，$j=1,2,\cdots,n$，$l=1,2,\cdots,S_j$，$y_i\in\{c_1,c_2,\cdots,c_K\}$

算法输出： 实例 $\mathbf x$ 的分类。

算法流程：

计算先验概率及条件概率 $P(Y=c_k)=\frac{\sum\limits^N_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K$ $P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits^N_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits^N_{i=1}I(y_i=c_k)}$
对于给定的实例 $\mathbf{x}=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T$，计算映射到对数空间的后验概率 $P(Y=c_k|X=\mathbf{x})=\log P(Y=c_k)+\sum_{j=1}^n\log P(X^{(j)}=x^{(j)}|Y=c_k),k=1,2,\cdots,K$
确定实例 $\mathbf{x}$ 的类别 $y=\arg\max_{c_k} P(Y=c_k|X=\mathbf{x})$

参考

1. 机器学习之朴素贝叶斯详解-cnblog
2. Naive Bayes Classifier History-holy python
3. 朴素贝叶斯分类器和一般的贝叶斯分类器有什么区别？-zhihu
4. Naive Bayes and Sentiment Classification - Stanford University

Machine Learning

2021-12-05