《统计学习方法》阅读笔记——第4章-朴素贝叶斯法
统计学习方法笔记——第4章-朴素贝叶斯法
朴素贝叶斯(naive Baye)法
朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法，与贝叶斯估计(Bayesian estimation)是不同的概念。
- 先基于特征条件独立假设，学习输入输出的联合概率分布\(P(X,Y)\)（是一种生成方法）；
- 计算先验概率\(P(Y)\)和条件概率\(P(X|Y)\)；
- 根据给定的实例，利用贝叶斯公式计算\(P(X,Y)=P(Y)P(X|Y)\)；
- 然后基于此模型，对给定的输入\(x\)，利用贝叶斯定理求出后验概率最大的输出\(y\)。
- 根据\(P(X,Y)\)，利用贝叶斯公式计算输入的\(P(Y|X)=\frac{P(X,Y)}{P(X)}\)；
- 取最大的\(y\)为输入的类别：\(y=\arg \max P(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∣\mathbf x)\)，公式如下： \[ P(c∣\mathbf x)=\frac{P(\mathbf x,c)}{P(\mathbf x)} \] 联合概率很难求，通过贝叶斯定理求解，转化后公式为： \[ P(c∣\mathbf x)=\frac{P(c)P(\mathbf x|c)}{P(\mathbf x)} \]
朴素贝叶斯基本方法
朴素贝叶斯基于属性条件独立性假设从而简单建模\(P(x|c)\)。
朴素贝叶斯法的基本假设是条件独立性。假设每个特征相互独立，则有后验概率为： \[ P(c∣\mathbf x)=\frac{P(c)P(\mathbf x|c)}{P(\mathbf x)}=\frac{P(c)}{P(\mathbf x)}\prod_{i=1}^dP(x_i|c) \] 其中，\(d\) 为属性数目，\(x_i\) 为\(\mathbf x\)在第\(i\)个属性上的取值。
由于这一假设，模型包含的条件概率的数量大为减少，朴素贝叶斯法的学习与预测大为简化。因而朴素贝叶斯法高效，且易于实现。其缺点是分类的性能不一定很高。
朴素贝叶斯将后验概率最大的类作为\(x\)的输出： \[ h^*(x)=\mathop{arg max}_{c∈\mathcal Y} P(c|\mathbf x)=\mathop{arg max}_{c∈\mathcal Y}\frac{P(c)}{P(\mathbf x)}\prod_{i=1}^dP(x_i|c) \] 由于对所有类别来说\(P(\mathbf x)\)都相同，略去，因此，最终求得\(c'\)使得下式\(h_{nb}\)最大。 \[ h_{nb}(\mathbf x)=\mathop{\arg \max}_{c∈\mathcal Y}P(c)\prod_{i=1}^dP(x_i|c) \]
接下来的问题是如何求解\(P(x_i|c)\)，可以用极大似然估计和贝叶斯估计等方法。
后验概率最大化的含义
朴素贝叶斯法的后验概率最大化等价于0-1损失函数时的期望风险最小化。
证明
朴素贝叶斯法的参数估计
在朴素贝叶斯法中，学习意味着估计\(P(c)\)和\(P(x_i|c)\)，可以用极大似然估计法、贝叶斯估计法估计相应的概率。
极大似然估计
极大似然估计的目的，就是为了找到似然最大时所对应的参数。
计算先验分布\(P(c)\)
类先验概率\(P(c)\)表达了样本空间中各类样本所占的比例。根据大数定律（用频率近似估计概率），当训练集包含充足的独立同分布样本时\(P(c)\)可通过各类样本出现的频率来进行估计： \[ \begin{align} P(c)=&\frac{|D_c|}{|D|}=\frac{\sum_{i=1}^{N}I(y_i=c)}{N}, \\ I为指示函数,I(y_i=c)= &\left\{ \begin{array}{ll} 1, & \textrm{$y_i=c$}\\ 0, & \textrm{$y_i \neq c$} \end{array} \right. \end{align} \] 其中，\(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 \geq 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 {align} 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)}, \\j=1,2,....n,l=1,2,...S_j,k=1,2,3...K \end {align} \]
解
极大似然估计步骤回顾
- 写出随机变量的概率分布函数；
- 写出似然函数；
- 对似然函数取对数，得到对数似然函数，并进行化简；
- 对参数进行求导，并令导数等于0；
- 求解似然函数方程，得到参数的值。
似然与概率
假设X是一个离散型的随机变量，它的概率分布p取决于参数θ，那么它的似然函数定义为： \[ L(θ∣x)=p_θ(x)=P_θ(X=x)=P(X=x∣θ)=P(X=x;θ) \] 表示基于给定的X=x，认为参数Θ=θ的似然（可信度），它的值则等于基于给定的参数Θ=θ，预测出现X=x的概率（可信度）。
推导公式(4.8)
根据朴素贝叶斯法的前提假设，\(Y={y_1,y_2,\ldots,y_N}\)满足独立同分布。假设\(P(Y=c_k)\)概率为\(p\)（也为求的参数），其中\(c_k\)在随机变量\(Y\)中出现的次数\(\displaystyle m=\sum_{i=1}^NI(y_i=c_k)\)，则概率为\(P(Y|p)=p^m(1-p)^{N-m}\)；
似然函数为：\(L(p|Y)=P(Y|p)=p^m(1-p)^{N-m}\)。
对似然函数取对数，得到对数似然函数为： \[ \begin{align} \log L(p|Y)=&\log p^m(1-p)^{N-m}\\ =&m\log p+(N-m)\log (1-p) \end{align} \]
对参数\(p\)求导，并求解导数为0时的\(p\)值： \[ \begin{align} \hat p=&\arg \max _p\log L(p|Y)\\ =&\arg \max _p m\log p+(N-m)\log (1-p)\\ \frac{∂\log L(p|Y)}{∂p}=&[\frac{m}{p}-\frac{N-m}{1-p}]=0\\ \end{align} \]
求得： \[ \begin{align} P(Y=c_k)=p=\frac{m}{N} \end{align} \]
推导公式(4.9)
与上述证明类似，此时在条件\(Y=c_k\)下，随机变量\(X\)满足条件独立性，假设\(P(X^{(j)}=a_{jl}|Y=c_k)\)概率为\(p\)，其中\(c_k\)在随机变量\(Y\)中出现的次数\(\displaystyle m=\sum_{i=1}^NI(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}\)；
似然函数为：\(L(p|X,Y)=P(X,Y|p)=p^q(1-p)^{m-q}\)；
对似然函数取对数，得到对数似然函数为： \[ \begin{align} \log L(p|X,Y)=&\log p^q(1-p)^{m-q}\\ =&q\log p+(m-q)\log (1-p) \end{align} \]
对参数\(p\)求导，并求解导数为0时的\(p\)值： \[ \begin{align} \hat p=&\arg \max _p\log L(p|X,Y)\\ =&\arg \max _p q\log p+(m-q)\log (1-p)\\ \frac{∂\log L(p|X,Y)}{∂p}=&[\frac{q}{p}-\frac{m-q}{1-p}]=0\\ \end{align} \]
求得： \[ \begin{align} P(X^{(j)}=a_{jl}|Y=c_k)=p=\frac{q}{m} \end{align} \]
习题4.2
题目
用贝叶斯估计法推出朴素贝叶斯法中的概率估计公式(4.10)及公式(4.11)。
公式(4.10)： \[ \begin {align} 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}, \\j=1,2,....n,l=1,2,...S_j,k=1,2,3...K \end {align} \] 公式(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 \]
解
贝叶斯估计一般流程回顾
- 确定参数\(\theta\)的先验概率\(p(\theta)\)；
- 根据样本集\(D=\{ x_1, x_2, \ldots, x_n \}\)，计算似然函数\(P(D|\theta)\)：\(\displaystyle P(D|\theta)=\prod_{i=1}^n P(x_i|D)\)；
- 利用贝叶斯公式，写出后验概率最大化公式：\(\mathop{\arg\max} \limits_{\theta} P(\theta|D)=\mathop{\arg\max} \limits_{\theta} \frac{P(D|\theta)P(\theta)}{\displaystyle \int \limits_\Theta P(D|\theta) P(\theta) d \theta} = \mathop{\arg\max} \limits_{\theta} P(D|\theta)P(\theta)\)；
- 利用求导，得到后验概率最大时的参数取值。
推导公式(4.10)
根据朴素贝叶斯法的基本方法，训练数据集\(T=\{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\}\)，假设：
随机变量\(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\)个）；
假设随机变量\(P_\lambda(Y=c_k)=u_k\)服从参数为\(\lambda\)的Dirichlet分布：
为什么假设\(Y=c_k\)的概率服从Dirichlet分布？
答：原因如下：
- 首先，根据PRML第B.4章节，Dirichlet分布是Beta分布的推广。Beta分布是二项式分布的共轭分布，Dirichlet分布是多项式分布的共轭分布。Dirichlet分布可以看作是“分布的分布”；
- 又因为，Beta分布与Dirichlet分布都是先验共轭的，意味着先验概率和后验概率属于同一个分布。 当假设为Beta分布或者Dirichlet分布时，通过获得大量的观测数据，进行数据分布的调整，使得计算出来的概率越来越接近真实值。
- 因此，对于一个概率未知的事件，Beta分布或Dirichlet分布能作为表示该事件发生的概率的概率分布。
根据假设(2)和Dirichlet分布的定义，可得先验概率为： \[ \displaystyle P(u)=P(u_1,u_2,\ldots,u_K) = C(\lambda) \prod_{k=1}^K u_k^{\lambda - 1} \]
得到似然函数：由\(P_\lambda(Y=c_k)=u_k\)，记\(m=(m_1, m_2, \ldots, 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} \]
得到似然函数：结合贝叶斯公式，求\(u\)的后验概率分布，可得 \[ \begin{align} P(u|m) =& \frac{P(m|u)P(u)}{P(m)}\\ P(u|m,\lambda) &\propto P(m|u)P(u|\lambda) \propto \prod_{k=1}^K u_k^{\lambda+m_k-1} \end{align} \] 上式表明，后验概率分布\(P(u|m,\lambda)\)也服从Dirichlet分布。
得到随机变量\(u\)的期望：根据后验概率分布\(P(u|m,\lambda)\)和假设(1)，求随机变量\(u\)的期望，可得： \[ \begin{aligned} 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} \quad(\because \sum_{k=1}^K m_k = N) \\ &= \frac{\lambda+m_k}{\displaystyle K \lambda + N } \quad (\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{aligned} \] 随机变量\(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)
与上述推导同理，此时有：
假设：
出现\(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)\)个）；
假设随机变量\(P_{\lambda}(X^{(j)}=a_{jl} | Y = c_k)=u_l\)服从参数为\(\lambda\)的Dirichlet分布;
根据假设(2)和Dirichlet分布的定义，可得先验概率为： \[ \displaystyle P(u)=P(u_1,u_2,\ldots,u_{S_j}) = C(\lambda) \prod_{l=1}^{S_j} u_l^{\lambda - 1} \]
得到似然函数：由\(P_{\lambda}(X^{(j)}=a_{jl} | Y = c_k)=u_l\)，记\(m=(m_1, m_2, \ldots, 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} \]
得到后验概率分布：得到似然函数：结合贝叶斯公式，求\(u\)的后验概率分布，可得 \[ \begin{align} P(u|m) =& \frac{P(m|u)P(u)}{P(m)}\\ P(u|m,\lambda)& \propto P(m|u)P(u|\lambda) \propto \prod_{l=1}^{S_j} u_l^{\lambda+m_l-1} \end{align} \] 表明，后验概率分布\(P(u|m,\lambda)\)也服从Dirichlet分布。
得到随机变量\(u\)的期望：根据后验概率分布\(P(u|m,\lambda)\)和假设(1)，求随机变量\(u\)的期望，可得： \[ \begin{aligned} 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} \quad(\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) } \quad (\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{aligned} \]
随机变量\(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}\)。
