《统计学习方法》阅读笔记——第4章-朴素贝叶斯法

统计学习方法笔记——第4章-朴素贝叶斯法

朴素贝叶斯(naive Baye)法

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法，与贝叶斯估计(Bayesian estimation)是不同的概念。

1. 先基于特征条件独立假设，学习输入输出的联合概率分布$P(X,Y)$（是一种生成方法）；
   1. 计算先验概率$P(Y)$和条件概率$P(X|Y)$；
   2. 根据给定的实例，利用贝叶斯公式计算$P(X,Y)=P(Y)P(X|Y)$；
2. 然后基于此模型，对给定的输入$x$，利用贝叶斯定理求出后验概率最大的输出$y$。
   1. 根据$P(X,Y)$，利用贝叶斯公式计算输入的$P(Y|X)=\frac{P(X,Y)}{P(X)}$；
   2. 取最大的$y$为输入的类别：$y=\arg maxP(Y|X)$。

接下来介绍朴素贝叶斯方法中如何求解$P(X|Y),P(X)$ .

生成式模型generative models和判别式模型discriminative models

判别式模型

给定$\mathbf{x}$ ，直接建模$P(c|\mathbf{x})$来预测$c$，如决策树、BP神经网络、支持向量机等；

生成式模型

先对联合概率$P(\mathbf{x},c)$建模，然后再由此推导得出 $P(c\mid \mathbf{x})$，公式如下： $$P(c\mid \mathbf{x})=\frac{P(\mathbf{x},c)}{P(\mathbf{x})}$$ 联合概率很难求，通过贝叶斯定理求解，转化后公式为： $$P(c\mid \mathbf{x})=\frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})}$$

朴素贝叶斯基本方法

朴素贝叶斯基于属性条件独立性假设从而简单建模$P(x|c)$。

朴素贝叶斯法的基本假设是条件独立性。假设每个特征相互独立，则有后验概率为： $$P(c\mid \mathbf{x})=\frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})}=\frac{P(c)}{P(\mathbf{x})}\prod _{i=1}^{d}P(x_i|c)$$ 其中，$d$ 为属性数目，$x_i$ 为$\mathbf{x}$在第$i$个属性上的取值。

由于这一假设，模型包含的条件概率的数量大为减少，朴素贝叶斯法的学习与预测大为简化。因而朴素贝叶斯法高效，且易于实现。其缺点是分类的性能不一定很高。

朴素贝叶斯将后验概率最大的类作为$x$的输出： $$h^{\ast }(x)=\underset{c\in \mathcal{Y}}{argmax}P(c|\mathbf{x})=\underset{c\in \mathcal{Y}}{argmax}\frac{P(c)}{P(\mathbf{x})}\prod _{i=1}^{d}P(x_i|c)$$ 由于对所有类别来说$P(\mathbf{x})$都相同，略去，因此，最终求得$c^{\prime }$使得下式$h_{nb}$最大。 $$h_{nb}(\mathbf{x})=\underset{c\in \mathcal{Y}}{\arg max}P(c)\prod _{i=1}^{d}P(x_i|c)$$

接下来的问题是如何求解$P(x_i|c)$，可以用极大似然估计和贝叶斯估计等方法。

后验概率最大化的含义

朴素贝叶斯法的后验概率最大化等价于0-1损失函数时的期望风险最小化。

证明

朴素贝叶斯法的参数估计

在朴素贝叶斯法中，学习意味着估计$P(c)$和$P(x_i|c)$，可以用极大似然估计法、贝叶斯估计法估计相应的概率。

极大似然估计

极大似然估计的目的，就是为了找到似然最大时所对应的参数。

计算先验分布$P(c)$

类先验概率$P(c)$表达了样本空间中各类样本所占的比例。根据大数定律（用频率近似估计概率），当训练集包含充足的独立同分布样本时$P(c)$可通过各类样本出现的频率来进行估计： $$\begin{array}{}\text{(1)}& P(c)=& \frac{|D_c|}{|D|}=\frac{\sum _{i=1}^{N}I(y_i=c)}{N},\text{(2)}& I\mathrm{为}\mathrm{指}\mathrm{示}\mathrm{函}\mathrm{数},I(y_i=c)=& \{\begin{array}{ll}1,& y_i=c\\ 0,& y_i\ne c\end{array}\end{array}$$ 其中，$D_c$表示训练集$D$中类别标记为$c$的样本集合， $|D_c|$表示集合$|D_c|$的样本总数。

计算条件概率分布$P(x_i|c)$

如果属性$i$为连续属性，先假设符合某种分布（比如，正态分布），利用某种方法估计分布的参数（比如极大似然估计-正态分布-需要求解均值、方差）。假设不同的分布，模型性能可能不同。

贝叶斯估计

因为$P(c)$和$P(\mathbf{x}|c)$是连乘的，如果$|D_c|=0$，即某个属性值在训练集中没有与某个类同时出现过，其他属性携带的信息被训练集中未出现的属性值"抹去'。因此，用极大似然估计可能会出现所要估计的概率值为0的情况。

解决这一问题的方法是采用贝叶斯估计。贝叶斯估计中用以下方法计算先验分布和条件概率分布。

计算先验分布$P(c)$

在估计概率值时通常要进行"平滑"(smoothing)，下式中$\lambda \ge 0$。等价于在随机变量各个取值的频数上赋予一个正数$\lambda >0$。令$N$表示训练集$D$中可能的类别，则： $$\hat{P}(c)=\frac{|D_c|+\lambda }{|D|+K\lambda }$$

当$\lambda =1$，称为"拉普拉斯修正"(Laplacian correction)，（拉普拉斯平滑）常用；

当$\lambda =0$，就是极大似然估计。

计算条件概率分布$P(x_i|c)$

如果属性$i$为离散属性，仍然使用大数定律求解$P(x_i|c)$；同样有拉普拉斯修正后的公式为： $$\hat{P}(x_i|c)=\frac{|D_{c,x_i}|+\lambda }{|D_c|+N_i\lambda }$$ 其中$N_i$表示第$i$个属性可能的取值数。

习题

习题4.1

题目

用极大似然估计法推出朴素贝叶斯法中的概率估计公式(4.8)及公式 (4.9)。

公式(4.8)： $$P(Y=c_k)=\frac{\sum _{i=1}^{N}I(y_i=c_k)}{N},k=1,2,3...K$$ 公式 (4.9)： $$\begin{array}{}\text{(3)}& P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum _{i=1}^{N}I(y_i=c_k)},\text{(4)}& j=1,2,....n,l=1,2,...S_j,k=1,2,3...K\end{array}$$

解

极大似然估计步骤回顾

极大似然估计的一般流程：

1. 写出随机变量的概率分布函数；
2. 写出似然函数；
3. 对似然函数取对数，得到对数似然函数，并进行化简；
4. 对参数进行求导，并令导数等于0；
5. 求解似然函数方程，得到参数的值。

似然与概率

假设X是一个离散型的随机变量，它的概率分布p取决于参数θ，那么它的似然函数定义为： $$L(\theta \mid x)=p_{\theta }(x)=P_{\theta }(X=x)=P(X=x\mid \theta )=P(X=x;\theta )$$ 表示基于给定的X=x，认为参数Θ=θ的似然（可信度），它的值则等于基于给定的参数Θ=θ，预测出现X=x的概率（可信度）。

推导公式(4.8)

1. 根据朴素贝叶斯法的前提假设，$Y=y_1,y_2,\dots ,y_N$满足独立同分布。假设$P(Y=c_k)$概率为$p$（也为求的参数），其中$c_k$在随机变量$Y$中出现的次数${\displaystyle m=\sum _{i=1}^{N}I(y_i=c_k)}$，则概率为$P(Y|p)=p^m(1-p{)}^{N-m}$；

2. 似然函数为：$L(p|Y)=P(Y|p)=p^m(1-p{)}^{N-m}$。

3. 对似然函数取对数，得到对数似然函数为： $$\begin{array}{}\text{(5)}& \log L(p|Y)=& \log p^m(1-p{)}^{N-m}\text{(6)}& =& m\log p+(N-m)\log (1-p)\end{array}$$

4. 对参数$p$求导，并求解导数为0时的$p$值： $$\begin{array}{}\text{(7)}& \hat{p}=& \arg \underset{p}{max}\log L(p|Y)\text{(8)}& =& \arg \underset{p}{max}m\log p+(N-m)\log (1-p)\text{(9)}& \frac{\partial \log L(p|Y)}{\partial p}=& [\frac{m}{p}-\frac{N-m}{1-p}]=0\end{array}$$

5. 求得： $$\begin{array}{}\text{(10)}& P(Y=c_k)=p=\frac{m}{N}\end{array}$$

推导公式(4.9)

1. 与上述证明类似，此时在条件$Y=c_k$下，随机变量$X$满足条件独立性，假设$P(X^{(j)}=a_{jl}|Y=c_k)$概率为$p$，其中$c_k$在随机变量$Y$中出现的次数${\displaystyle m=\sum _{i=1}^{N}I(y_i=c_k)}$，$y=c_k$和$x^{(j)}=a_{jl}$同时出现的次数${\displaystyle q=\sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}$，则概率为$P(X,Y|p)=p^q(1-p{)}^{m-q}$；

2. 似然函数为：$L(p|X,Y)=P(X,Y|p)=p^q(1-p{)}^{m-q}$；

3. 对似然函数取对数，得到对数似然函数为： $$\begin{array}{}\text{(11)}& \log L(p|X,Y)=& \log p^q(1-p{)}^{m-q}\text{(12)}& =& q\log p+(m-q)\log (1-p)\end{array}$$

4. 对参数$p$求导，并求解导数为0时的$p$值： $$\begin{array}{}\text{(13)}& \hat{p}=& \arg \underset{p}{max}\log L(p|X,Y)\text{(14)}& =& \arg \underset{p}{max}q\log p+(m-q)\log (1-p)\text{(15)}& \frac{\partial \log L(p|X,Y)}{\partial p}=& [\frac{q}{p}-\frac{m-q}{1-p}]=0\end{array}$$

5. 求得： $$\begin{array}{}\text{(16)}& P(X^{(j)}=a_{jl}|Y=c_k)=p=\frac{q}{m}\end{array}$$

习题4.2

题目

用贝叶斯估计法推出朴素贝叶斯法中的概率估计公式(4.10)及公式(4.11)。

公式(4.10)： $$\begin{array}{}\text{(17)}& P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda }{\sum _{i=1}^{N}I(y_i=c_k)+S_j\lambda },\text{(18)}& j=1,2,....n,l=1,2,...S_j,k=1,2,3...K\end{array}$$ 公式(4.11)： $$P_{\lambda }(Y=c_k)=\frac{\sum _{i=1}^{N}I(y_i=c_k)+\lambda }{N+K\lambda },k=1,2,3...K$$

解

贝叶斯估计一般流程回顾

贝叶斯估计（最大后验估计）的一般步骤：

1. 确定参数$\theta$的先验概率$p(\theta )$；
2. 根据样本集$D=\{x_1,x_2,\dots ,x_n\}$，计算似然函数$P(D|\theta )$：${\displaystyle P(D|\theta )=\prod _{i=1}^{n}P(x_i|D)}$；
3. 利用贝叶斯公式，写出后验概率最大化公式：$\underset{\theta }{\arg max}P(\theta |D)=\underset{\theta }{\arg max}\frac{P(D|\theta )P(\theta )}{{\displaystyle \underset{\mathrm{\Theta }}{\int }P(D|\theta )P(\theta )d\theta }}=\underset{\theta }{\arg max}P(D|\theta )P(\theta )$；
4. 利用求导，得到后验概率最大时的参数取值。

推导公式(4.10)

1. 根据朴素贝叶斯法的基本方法，训练数据集$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$，假设：

   1. 随机变量$Y$出现$y=c_k$的次数为$m_k$，即${\displaystyle m_k=\sum _{i=1}^{N}I(y_i=c_k)}$，可知${\displaystyle \sum _{k=1}^K{m}_k=N}$（$y$总共有$N$个）；

   2. 假设随机变量$P_{\lambda }(Y=c_k)=u_k$服从参数为$\lambda$的Dirichlet分布：

   

   为什么假设$Y=c_k$的概率服从Dirichlet分布？

   答：原因如下：

   1. 首先，根据PRML第B.4章节，Dirichlet分布是Beta分布的推广。Beta分布是二项式分布的共轭分布，Dirichlet分布是多项式分布的共轭分布。Dirichlet分布可以看作是“分布的分布”；
   2. 又因为，Beta分布与Dirichlet分布都是先验共轭的，意味着先验概率和后验概率属于同一个分布。 当假设为Beta分布或者Dirichlet分布时，通过获得大量的观测数据，进行数据分布的调整，使得计算出来的概率越来越接近真实值。
   3. 因此，对于一个概率未知的事件，Beta分布或Dirichlet分布能作为表示该事件发生的概率的概率分布。

   根据假设(2)和Dirichlet分布的定义，可得先验概率为： $${\displaystyle P(u)=P(u_1,u_2,\dots ,u_K)=C(\lambda )\prod _{k=1}^K{u}_k^{\lambda -1}}$$

2. 得到似然函数：由$P_{\lambda }(Y=c_k)=u_k$，记$m=(m_1,m_2,\dots ,m_K{)}^T$，可得似然函数为 $$P(m|u)=u_1^{m_1}\cdot u_2^{m_2}\cdots u_K^{m_K}=\prod _{k=1}^K{u}_k^{m_k}$$

3. 得到似然函数：结合贝叶斯公式，求$u$的后验概率分布，可得 $$\begin{array}{}\text{(19)}& P(u|m)=& \frac{P(m|u)P(u)}{P(m)}\text{(20)}& P(u|m,\lambda )& \propto P(m|u)P(u|\lambda )\propto \prod _{k=1}^K{u}_k^{\lambda +m_k-1}\end{array}$$ 上式表明，后验概率分布$P(u|m,\lambda )$也服从Dirichlet分布。

4. 得到随机变量$u$的期望：根据后验概率分布$P(u|m,\lambda )$和假设(1)，求随机变量$u$的期望，可得： $$\begin{array}{rl}E(u_k)& =\frac{{\alpha }_k}{{\displaystyle \sum _{k=1}^K{\alpha }_k}}\\ & =\frac{\lambda +m_k}{{\displaystyle \sum _{k=1}^K(\lambda +m_k)}}\\ & =\frac{\lambda +m_k}{{\displaystyle \sum _{k=1}^K\lambda +\sum _{k=1}^K{m}_k}}(\because \sum _{k=1}^K{m}_k=N)\\ & =\frac{\lambda +m_k}{{\displaystyle K\lambda +N}}(\because m_k=\sum _{i=1}^{N}I(y_i=c_k))\\ & =\frac{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)+\lambda }}{N+K\lambda }\end{array}$$ 随机变量$u_k$取$u_k$的期望，可得 ${\displaystyle P_{\lambda }(Y=c_k)=\frac{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)+\lambda }}{N+K\lambda }}$。

推导公式(4.11)

与上述推导同理，此时有：

1. 假设：

   1. 出现$x^{(j)}=a_{jl},y=c_k$的次数为$m_l$，即${\displaystyle m_l=\sum _{i=1}^{N}I(x^{(j)}=a_{jl},y=c_k)}$，可知${\displaystyle \sum _{k=1}^{S_j}{m}_l=\sum _{i=1}^{N}I(y_i=c_k)}$（总共$\sum _{i=1}^{N}I(y_i=c_k)$个）；

   2. 假设随机变量$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=u_l$服从参数为$\lambda$的Dirichlet分布;

   根据假设(2)和Dirichlet分布的定义，可得先验概率为： $${\displaystyle P(u)=P(u_1,u_2,\dots ,u_{S_j})=C(\lambda )\prod _{l=1}^{S_j}{u}_l^{\lambda -1}}$$

2. 得到似然函数：由$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=u_l$，记$m=(m_1,m_2,\dots ,m_K{)}^T$，可得似然函数为： $$P(m|u)=u_1^{m_1}\cdot u_2^{m_2}\cdots u_{S_j}^{m_{S_j}}=\prod _{l=1}^{S_j}{u}_l^{m_l}$$

3. 得到后验概率分布：得到似然函数：结合贝叶斯公式，求$u$的后验概率分布，可得 $$\begin{array}{}\text{(21)}& P(u|m)=& \frac{P(m|u)P(u)}{P(m)}\text{(22)}& P(u|m,\lambda )& \propto P(m|u)P(u|\lambda )\propto \prod _{l=1}^{S_j}{u}_l^{\lambda +m_l-1}\end{array}$$ 表明，后验概率分布$P(u|m,\lambda )$也服从Dirichlet分布。

4. 得到随机变量$u$的期望：根据后验概率分布$P(u|m,\lambda )$和假设(1)，求随机变量$u$的期望，可得： $$\begin{array}{rl}E(u_l)& =\frac{{\alpha }_l}{{\displaystyle \sum _{l=1}^{S_j}{\alpha }_l}}\\ & =\frac{\lambda +m_l}{{\displaystyle \sum _{l=1}^{S_j}(\lambda +m_l)}}\\ & =\frac{\lambda +m_l}{{\displaystyle \sum _{l=1}^{S_j}\lambda +\sum _{l=1}^{S_j}{m}_l}}(\because \sum _{l=1}^{S_j}{m}_l=\sum _{i=1}^{N}I(y_i=c_k))\\ & =\frac{\lambda +m_l}{{\displaystyle S_j\lambda +\sum _{i=1}^{N}I(y_i=c_k)}}(\because m_l=\sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k))\\ & =\frac{{\displaystyle \sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda }}{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)+S_j\lambda }}\end{array}$$

   随机变量$u_l$取$u_l$的期望，可得 ${\displaystyle P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=\frac{{\displaystyle \sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda }}{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)+S_j\lambda }}}$。

参考资料

【For非数学专业】通俗理解似然函数、概率、极大似然估计和对数似然

李航 统计学习方法 第2版

DataWhale资料-第4章 朴素贝叶斯法 (datawhalechina.github.io)