《统计学习方法》第四章：朴素贝叶斯法

模型

条件概率

引入贝叶斯法模型前，首先回顾一下条件概率的基本公式。所谓条件概率，就是在某事件 $B$ 发生的条件下，求另一事件 $A$ 发生的概率，条件概率可以通过下式计算：

$$P(A|B)=\frac{P(AB)}{P(B)}$$

乘法公式

根据条件概率定义，可以得到

$$P(A|B)=\frac{P(AB)}{P(B)}$$

$$P(B|A)=\frac{P(AB)}{P(A)}$$

显然有

$$P(AB)=P(A)P(B|A)=P(B)P(A|B)$$

该式就称为乘法公式。

全概率公式

若将样本空间 $\Omega$ 分割为互不相容的各事件 $B_1,B_2,\cdots B_n$，那么 $A$ 事件的概率就应当是 $A$ 的所有条件概率与相应条件发生概率乘积之和：

$$P(A)=\sum_{i=1}^nP(B_i)P(A|B_i)$$

考虑 $A$ 与 $B$ 为两个事件的情况，利用全概系公式可以将事件 $A$ 发生的概率写为

$$P(A)=P(B)P(A|B)+P(\bar{B})P(A|\bar{B})$$

贝叶斯公式

假设 $Y_1,Y_2,\cdots Y_n$ 是对样本空间的划分，$X$ 为样本空间中的一个事件，那么根据条件概率的定义，有

$$P(Y_i|X)=\frac{P(XY_i)}{P(X)}$$

利用乘法公式，该式可以写为

$$P(Y_i|X)=\frac{P(X|Y_i)P(Y_i)}{P(X)}$$

利用全概率公式，得到

$$P(Y_i|X)=\frac{P(X|Y_i)P(Y_i)}{\sum_{j=1}^nP(X|Y_j)P(Y_j)}$$

该式即为贝叶斯公式。

朴素贝叶斯法模型

假设训练集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ 是由 $P(X,Y)$ 独立同分布产生，其中输入为特征向量，输出为类标记。

先验概率分布为

$$P(Y=c_k),\qquad k=1,2,\cdots,K$$

条件概率分布为

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

对条件概率分布作条件独立性的假设，即认为某特征向量事件的各分量事件相互独立，因此该向量代表事件的发生概率为该向量的各分量概率乘积：

$$\begin{align} P(X=x|Y=c_k)&=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\\ &=\prod_{j=1}^nP(X^{j}=x^{(j)}|Y=c_k) \end{align}$$

朴素贝叶斯法的目的在于通过模型计算输入 $x$ 后的后验概率分布 $P(Y=c_k|X=x)$ 并输出后验概率最大的 $c_k$ 作为 $x$ 的类。

类比推导得到的贝叶斯公式

$$P(Y_i|X)=\frac{P(X|Y_i)P(Y_i)}{\sum_{j=1}^nP(X|Y_j)P(Y_j)}$$

后验概率分布可以表示为

$$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)}$$

代入条件独立性假设，即有

$$P(Y=c_k|X=x)=\frac{\color{orangered}{P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}}{\sum_k P(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)}$$

其中不论 $c_k$ 为何值时，分母部分都是不变的，不影响发生概率大小的比较，因此朴素贝叶斯方法的模型可以表示为

$$y=\arg \max_{c_k}\color{orangered}{P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}$$

策略

损失函数可以表示为

$$\begin{equation} L(Y,f(X))= \begin{cases} 1, &Y\neq f(X)\\ 0, &Y=f(X) \end{cases} \end{equation}$$

期望风险函数为条件期望

$$R_{\mathrm{exp}}(f)=E[L(Y,f(X))]=E_X\sum_{k=1}^K[L(c_k,f(X))]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\neq 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{align}$$

也就是说后验概率最大的情况下期望风险就最小，这正是朴素贝叶斯法决定输出类别的方法。

算法

极大似然估计

使用频率估计概率，先验概率为

$$\color{teal}{P(Y=c_k)}=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}$$

特征向量的第 $j$ 个分量 $x^{(j)}$ 可能取的值构成了集合 $\{a_{j1},a_{j2},\cdots,a_{jS_j}\}$，那么条件概率为

$$\color{steelblue}{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)}$$

算法 4.1

输入：训练集 $T$ 与实例 $x$
输出：$x$ 的类别

计算先验概率 $\color{teal}{P(Y=c_k)}$ 与条件概率 $\color{steelblue}{P(X^{(j)}=a_{jl}|Y=c_k)}$；
应用条件独立性假设，计算 $P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)$；
确定 $x$ 的类别，$y=\arg \max_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)$。

贝叶斯估计

在极大似然估计中可能会出现估计的概率为零，从而导致整个特征向量的估计概率也为零，影响估计结果。贝叶斯估计通过在频数上引入正数 $\lambda$ 从而避免了这种偏差：

$$\color{teal}{P(Y=c_k)}=\frac{\sum_{i=1}^NI(y_i=c_k)+\color{orangered}{\lambda}}{N+\color{orangered}{K\lambda}}$$

$$\color{steelblue}{P_{\lambda}(X^{j}=a_{jl}|Y=c_k)}=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)+\color{orangered}{\lambda}}{\sum_{i=1}^NI(y_i=c_k)+\color{orangered}{S_j\lambda}}$$

若取 $\lambda=0$ 时就是极大似然估计，常取 $\lambda=1$，称为拉普拉斯平滑。

模型