DanielLaah

《统计学习方法》笔记 (五) - 朴素贝叶斯法


本篇博客为《统计学习方法》笔记系列第5篇, 对应《统计学习方法》中第4章的内容. 主要介绍朴素贝叶斯.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


朴素贝叶斯(naïve Bayes)法是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集,首先基于特征条件独立假设学习输入/输出的联合概率分布;然后基于此模型,对给定的输入$x$,利用贝叶斯定理求出后验概率最大的输出$y$。朴素贝叶斯法实现简单,学习与预测的效率都很高,是一种常用的方法.

一. 朴素贝叶斯法的学习与分类

1.1 基本方法

设输入空间$\mathcal{X}\subseteq R^n$为$n$维向量的集合,输出空间为类标记集合$\mathcal{Y}=\{c_1,c_2,…,c_K\}$。输入为特征向量$x\in \mathcal{X}$,输出为类标记$y\in\mathcal{Y}$。$X$是定义在输入空间$\mathcal{X}$上的随机向量,$Y$是定义在输出空间$\mathcal{Y}$上的随机变量。$P(X,Y)$是$X$和$Y$的联合概率分布。训练数据集
$$T={(x_{1}, y_{1}), (x_{2}, y_{2}),…, (x_{N}, y_{N})}$$
由$P(X,Y)$独立同分布产生.
朴素贝叶斯法通过训练数据集学习联合概率分布$P(X,Y)$。具体地,学习以下先验概率分布及条件概率分布。
先验概率分布:
$$P(Y=c_k), k=1,2,…,K$$
条件概率分布:
$$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_k), k=1,2,…,K$$
于是学习到联合概率分布$P(X,Y)$.
条件概率分布$P(X=x|Y=c_k)$有指数级数量的参数,其估计实际是不可行的。事实上,假设$x^{(j)}$可取值有$S_j$个,$j=1,2,…,n$,$Y$可取值有$K$个,那么参数个数为$K\prod_{j=1}^nS_j $。
朴素贝叶斯法对条件概率分布作了条件独立性的假设。由于这是一个较强的假设,朴素贝叶斯法也由此得名。具体地,条件独立性假设是:
$$\begin{align}
P(X=x|Y=c_k)&=P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_k) \\
\\
& = \prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)
\end{align} \tag{4.3}$$
朴素贝叶斯法实际上学习到生成数据的机制,所以属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单,但有时会牺牲一定的分类准确率。
朴素贝叶斯法分类时,对给定的输入x,通过学习到的模型计算后验概率分布$P(Y=c_k|X=x)$,将后验概率最大的类作为$x$的类输出。后验概率计算根据贝叶斯定理进行:
$$P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{k}P(X=x|Y=c_k)P(Y=c_k)} \tag{4.4}$$
将式(4.3)带入(4.4)有
$$P(Y=c_k|X=x)=\frac{P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{k}P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}, k=1,2,…,K$$
这是朴素贝叶斯法分类的基本公式. 于是, 朴素贝叶斯分类器可表示为
$$y=f(x)=arg\max_{c_k}\frac{P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{k}P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}, k=1,2,…,K \tag{4.6}$$
注意到, 在式(4.6)中分母对于所有$c_k$都是相同的, 所以:
$$y=f(x)=arg\max_{c_k}{P(Y=c_k)\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}\tag{4.7}$$

1.2 后验概率最大化的含义

朴素贝叶斯法将实例分到后验概率最大的类中。这等价于期望风险最小化。假设选择0-1损失函数:
$$
L(Y, f(X))=
\begin{cases}
1, & Y\ne f(X) \\
\\
0, & Y=f(X)
\end{cases}
$$
式中f(X)是分类决策函数。这时,期望风险函数为
$$R_\text{exp}=E\left[L(Y, f(X)\right]$$
期望是对联合分布P(X,Y)取的。由此取条件期望
$$R_\text{exp}(f)=E_X\sum_{k=1}^K\left[L(c_k, f(X)\right]P(c_k|X)$$
为了使期望风险最小化,只需对$X=x$逐个极小化,由此得到:
$$\begin{align}
f(x) & = arg\min_{y\in \mathcal{Y}}\sum_{k=1}^KL(c_k, y)P(c_k|X=x) \\
\\
& = arg\min_{y\in \mathcal{Y}}\sum_{k=1}^KP(y\ne c_k|X=x) \\
\\
& = arg\min_{y\in \mathcal{Y}}\left(1-P(y= c_k|X=x)\right) \\
\\
& = arg\max_{y\in \mathcal{Y}}P(y= c_k|X=x)
\end{align}$$
这样一来,根据期望风险最小化准则就得到了后验概率最大化准则:
$$f(x)=arg\max_{c_k}P(c_k|X=x)$$
即朴素贝叶斯法所采用的原理.

二. 朴素贝叶斯法的参数估计

2.1 极大似然估计

在朴素贝叶斯法中,学习意味着估计$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。可以应用极大似然估计法估计相应的概率。先验概率P(Y=c_k)的极大似然估计是
$$P(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}, k=1,2,…,K \tag{4.8}$$
设第$j$个特征$x^{(j)}$可能取值的集合为$\{a_{j1},a_{j2},…,a_{jS_j}\}$,条件概率$P(x^{(j)}=a_{jl}|Y=c_k)$的极大似然估计是
$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}\tag{4.9}$$
$$j=1,2,…,n; l=1,2,…,S_j; k=1,2,…,K$$
式中,$x_i^{(j)}$是第$i$个样本的第$j$个特征;$a_{jl}$是第$j$个特征可能取的第$l$个值;$I$为指示函数。

2.2 学习与分类算法

下面给出朴素贝叶斯法的学习与分类算法:
输入: 训练数据$T={(x_{1}, y_{1}), (x_{2}, y_{2}),…, (x_{N}, y_{N})}$, 实例$x$
输出: 实例$x$的分类
(1)按照式(4.8), (4.9)计算先验概率及条件概率
(2)对于给定的实例$x=(x^{(1)},x^{(2)},…,x^{(n)})^T$计算
$$P(Y=c_k)\prod_{j=1}^NP(X^{(j)}=x^{(j)}|Y=c_k)$$
(3)按照式(4.7)确定实例$x$的分类
例.

2.3 贝叶斯估计

用极大似然估计可能会出现所要估计的概率值为0的情况。这时会影响到后验概率的计算结果,使分类产生偏差。解决这一问题的方法是采用贝叶斯估计。具体地,条件概率的贝叶斯估计是
$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}\tag{4.10}$$
式中$\lambda\le 0$。等价于在随机变量各个取值的频数上赋予一个正数$\lambda>0$。当$\lambda=0$时就是极大似然估计。常取$\lambda=1$,这时称为拉普拉斯平滑(Laplace smoothing)。显然,对任何$l=1,2,…,S_j,K=1,2,…,K$,有
$$P_\lambda(X^{(j)}=a_{jl}|Y=c_k)>0$$
$$\sum_{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)=1$$
表明式(4.10)确为一种概率分布。同样,先验概率的贝叶斯估计是:
$$P_\lambda(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda}, k=1,2,…,K$$