《统计学习方法》阅读笔记——第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}\)。