第4章 朴素贝叶斯法

习题4.1

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

解答：

解答思路：

1. 极大似然估计的一般步骤（详见习题1.1第3步）
2. 证明公式4.8：根据输出空间$\mathcal{Y}$的随机变量$Y$满足独立同分布，列出似然函数，求解概率$P(Y=c_k)$的值；
3. 证明公式4.9：证明同公式4.8。

解答步骤：

第1步：极大似然估计的一般步骤

参考Wiki：https://en.wikipedia.org/wiki/Maximum_likelihood_estimation

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

第2步：证明公式(4.8)

$${\displaystyle P(Y=c_k)=\frac{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)}}{N},k=1,2,\dots ,K}$$

  根据书中第4章的第4.1节朴素贝叶斯法的基本方法：

  设输入空间$\mathcal{X}\subseteq R^n$为$n$维向量的集合，输出空间为类标记集合$\mathcal{Y}=\{c_1,c_2,\dots ,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),\dots ,(x_N,y_N)\}$$

由$P(X,Y)$独立同分布产生。

  根据上述定义，$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)}$，可得似然函数为：

$$\begin{array}{rl}L(p|Y)& =f(Y|p)\\ & =C_N^m{p}^m(1-p{)}^{N-m}\end{array}$$

对似然函数取对数，得到对数似然函数为：

$$\begin{array}{rl}{\displaystyle \log L(p|Y)}& =\log C_N^m{p}^m(1-p{)}^{N-m}\\ & =\log C_N^m+\log (p^m)+\log ((1-p{)}^{N-m})\\ & =\log C_N^m+m\log p+(N-m)\log (1-p)\end{array}$$

求解参数$p$：

$$\begin{array}{rl}\hat{p}& =\underset{p}{\arg max}L(p|Y)\\ & =\underset{p}{\arg max}[\log C_N^m+m\log p+(N-m)\log (1-p)]\end{array}$$

对参数$p$求导，并求解导数为0时的$p$值：

$$\begin{array}{rl}\frac{\partial \log L(p)}{\partial p}& =\frac{m}{p}-\frac{N-m}{1-p}\\ & =\frac{m(1-p)-p(N-m)}{p(1-p)}\\ & =\frac{m-Np}{p(1-p)}=0\end{array}$$

从上式可得，$m-Np=0$，即${\displaystyle P(Y=c_k)=p=\frac{m}{N}}$
综上所述，${\displaystyle P(Y=c_k)=p=\frac{m}{N}=\frac{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)}}{N}}$，公式(4.8)得证。

第3步：证明公式(4.9)

$$\begin{gathered} {\displaystyle P(X^{(j)}=a_{jl}|Y=c_k)=\frac{{\displaystyle \sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}}{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)}}} \\ j=1,2,\dots ,n;l=1,2,\dots ,S_j;k=1,2,\dots ,K \end{gathered}$$

  根据书中第4章朴素贝叶斯法的条件独立性假设：

  朴素贝叶斯法对条件概率分布作了条件独立性的假设。由于这是一个较强的假设，朴素贝叶斯法也由此得名。具体地，条件独立性假设是：

$$\begin{array}{}\text{(4.3)}& \begin{array}{rl}P(X=x|Y=c_k)& =P(X^{(1)}=x^{(1)},\dots ,X^{(n)}=x^{(n)}|Y=c_k)\\ & =\prod _{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)\end{array}\end{array}$$

  根据上述定义，在条件$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)}$，可得似然函数为：

$$\begin{array}{rl}L(p|X,Y)& =f(X,Y|p)\\ & =C_m^q{p}^q(1-p{)}^{m-q}\end{array}$$

与第2步推导过程类似，可求解得到${\displaystyle p=\frac{q}{m}}$
综上所述，${\displaystyle P(X^{(j)}=a_{jl}|Y=c_k)=p=\frac{q}{m}=\frac{{\displaystyle \sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}}{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)}}}$，公式(4.9)得证。

习题4.2

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

解答：

解答思路：

1. 贝叶斯估计的一般步骤（详见习题1.1第4步）；
2. 证明公式4.11：假设概率$P_{\lambda }(Y=c_i)$服从狄利克雷（Dirichlet）分布，根据贝叶斯公式，推导后验概率也服从Dirichlet分布，求参数期望；
3. 证明公式4.10：证明同公式4.11。

解答步骤：

第1步：贝叶斯估计的一般步骤
参考Wiki：https://en.wikipedia.org/wiki/Bayes_estimator

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_n|D)}$
3. 利用贝叶斯公式，求$\theta$的后验概率：${\displaystyle P(\theta |D)=\frac{P(D|\theta )P(\theta )}{{\displaystyle \underset{\mathrm{\Theta }}{\int }P(D|\theta )P(\theta )d\theta }}}$
4. 计算后验概率分布参数$\theta$的期望，并求出贝叶斯估计值：${\displaystyle \hat{\theta }=\underset{\mathrm{\Theta }}{\int }\theta \cdot P(\theta |D)d\theta }$

第2步：证明公式(4.11)

$${\displaystyle P_{\lambda }(Y=c_k)=\frac{{\displaystyle \sum _{i=1}^{N}I(y_i=c_k)+\lambda }}{N+K\lambda },k=1,2,\dots ,K}$$

证明思路：

1. 条件假设：$P_{\lambda }(Y=c_k)=u_k$，且服从参数为$\lambda$的Dirichlet分布；随机变量$Y$出现$y=c_k$的次数为$m_k$；
2. 得到$u$的先验概率$P(u)$；
3. 得到似然函数$P(m|u)$；
4. 根据贝叶斯公式，计算后验概率$P(u|m)$
5. 计算$u$的期望$E(u)$

证明步骤：

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$，随机变量$u_k$服从参数为$\lambda$的Dirichlet分布。

补充说明：

1. 狄利克雷(Dirichlet)分布
     参考PRML（Pattern Recognition and Machine Learning）一书的第2.2.1章节：⽤似然函数(2.34)乘以先验(2.38)，我们得到了参数$\{u_k\}$的后验分布，形式为

$$p(u|D,\alpha )\propto p(D|u)p(u|\alpha )\propto \prod _{k=1}^K{u}_k^{{\alpha }_k+m_k-1}$$

  该书中第B.4章节： 狄利克雷分布是$K$个随机变量$0⩽u_k⩽1$的多变量分布，其中$k=1,2,\dots ,K$，并满足以下约束

$$0⩽u_k⩽1,\sum _{k=1}^K{u}_k=1$$

记$u=(u_1,\dots ,u_K{)}^T,\alpha =({\alpha }_1,\dots ,{\alpha }_K{)}^T$，有

$$\begin{gathered} \text{Dir}(u|\alpha )=C(\alpha )\prod _{k-1}^K{u}_k^{{\alpha }_k-1} \\ E(u_k)=\frac{{\alpha }_k}{{\displaystyle \sum _{k=1}^K{\alpha }_k}} \end{gathered}$$

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

2. 得到先验概率
     根据假设(2)和Dirichlet分布的定义，可得先验概率为

$${\displaystyle P(u)=P(u_1,u_2,\dots ,u_K)=C(\lambda )\prod _{k=1}^K{u}_k^{\lambda -1}}$$

3. 得到似然函数
     记$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}$$

4. 得到后验概率分布
     结合贝叶斯公式，求$u$的后验概率分布，可得

$$P(u|m)=\frac{P(m|u)P(u)}{P(m)}$$

  根据假设(1)，可得

$$P(u|m,\lambda )\propto P(m|u)P(u|\lambda )\propto \prod _{k=1}^K{u}_k^{\lambda +m_k-1}$$

  上式表明，后验概率分布$P(u|m,\lambda )$也服从Dirichlet分布

5. 得到随机变量$u$的期望
     根据后验概率分布$P(u|m,\lambda )$和假设(1)，求随机变量$u$的期望，可得

$$E(u_k)=\frac{{\alpha }_k}{{\displaystyle \sum _{k=1}^K{\alpha }_k}}$$

其中${\alpha }_k=\lambda +m_k$，则

$$\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)得证

第3步：证明公式(4.10)

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

证明思路：

1. 条件假设：$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=u_l$，其中$l=1,2,\dots ,S_j$，且服从参数为$\lambda$的Dirichlet分布；出现$x^{(j)}=a_{jl},y=c_k$的次数为$m_l$；
2. 得到$u$的先验概率$P(u)$；
3. 得到似然函数$P(m|u)$；
4. 根据贝叶斯公式，计算后验概率$P(u|m)$
5. 计算$u$的期望$E(u)$

证明步骤：

1. 条件假设

  根据朴素贝叶斯法的基本方法，训练数据集$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$，假设：
（1）出现$x^{(j)}=a_{jl},y=c_k$的次数为$m_l$，即${\displaystyle m_l=\sum _{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}$，可知${\displaystyle \sum _{l=1}^{S_j}{m}_l=\sum _{i=1}^{N}I(y_i=c_k)}$（总共有${\displaystyle \sum _{i=1}^{N}I(y_i=c_k)}$个）；
（2）$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=u_l$，随机变量$u_l$服从参数为$\lambda$的Dirichlet分布。

2. 得到先验概率
     根据假设(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}}$$

3. 得到似然函数
     记$m=(m_1,m_2,\dots ,m_{S_j}{)}^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}$$

4. 得到后验概率分布
     结合贝叶斯公式，求$u$的后验概率分布，可得

$$P(u|m)=\frac{P(m|u)P(u)}{P(m)}$$

  根据假设(1)，可得

$$P(u|m,\lambda )\propto P(m|u)P(u|\lambda )\propto \prod _{l=1}^{S_j}{u}_l^{\lambda +m_l-1}$$

  上式表明，后验概率分布$P(u|m,\lambda )$也服从Dirichlet分布

5. 得到随机变量$u$的期望
     根据后验概率分布$P(u|m,\lambda )$和假设(1)，求随机变量$u$的期望，可得

$$E(u_k)=\frac{{\alpha }_l}{{\displaystyle \sum _{l=1}^{S_j}{\alpha }_l}}$$

其中${\alpha }_l=\lambda +m_l$，则

$$\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_k$取$u_k$的期望，可得 ${\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 }}}$，公式(4.10)得证。

参考文献

【1】极大似然估计的一般步骤（来源于Wiki百科）：https://en.wikipedia.org/wiki/Maximum_likelihood_estimation
【2】贝叶斯估计的一般步骤（来源于Wiki百科）：https://en.wikipedia.org/wiki/Bayes_estimator