本篇文章是在参考西瓜书、PPT课件、网络上相关博客等资料的基础上整理出的机器学习复习笔记希望能给大家的机器学习复习提供帮助。这篇笔记只是复习的一个参考大家一定要结合书本、PPT来进行复习有些公式的推导最好能够自己演算一遍。由于作者水平有限笔记中难免有些差错欢迎大家评论留言。
完整版跳转

6. 朴素贝叶斯

6.1 条件独立

我们称$X$在给定$Z$的条件下条件独立于$Y$当且仅当$X$的分布在给定$Z$的条件下与$Y$无关。
$$(\forall i,j,k)P(X=x_i|Y=y_j,Z=z_k)=P(X=x_i|Z=z_k)$$
缩写为
$$P(X|Y,Z)=P(X|Z)$$
若$X_1,X_2$在给定$Y$时条件独立那么有
$$\begin{array}{rl}P(X_1,X_2|Y)& =P(X_1|X_2,Y)P(X_2|Y)\\ & =P(X_1|Y)P(X_2|Y)\end{array}$$
一般化若$X_i$与$Y$条件独立那么
$$P(X_1,X_2,\dots ,X_n|Y)=\prod _{i}P(X_i|Y)$$
这是朴素贝叶斯的基础。

6.2 参数估计

相较于没有条件独立性假设的情况朴素贝叶斯分类器所需要估计的参数个数大大减少了具体来看假设每个属性有2个不同取值共有2个类别

• 没有条件独立性假设$2^n$
• 有条件独立性假设$2n$
  朴素贝叶斯分类器需要对任何一个给定的样本$X=<X_1,\dots ,X_n>$计算出它被分类为任何一个类别的概率即
  $$P(Y=y_k|X_1\dots X_n)=\frac{P(Y=y_k){\prod }_{i}P(X_i|Y=y_k)}{{\sum }_{j}P(Y=y_j){\prod }_{i}P(X_i|Y=y_j)}$$
  对于某个给定的分母是恒定的。我们只需要最大化分子也就是
  $$\arg \underset{k}{\max }P(Y=y_k)\prod _{i}P(X_i|Y=y_k)$$
  因而对于一个新的样本$X^{new}=<X_1,\dots ,X_n>$判别规则为
  $$Y^{new}\leftarrow \arg \underset{y_k}{\max }P(Y=y_k)\prod _{i}P(X_i^{new}|Y=y_k)$$
  也就是说当各个属性之间条件独立时考虑最大化各个属性取值时的类别而为了能够从整体上看最大化的情况取了各个属性值上的概率积。
  在朴素贝叶斯中我们需要对两类参数进行估计
• 先验概率${\pi }_k=P(Y=y_k)$
• 条件概率${\theta }_{ijk}=P(X_i=x_{ij}|Y=y_k)$$x_{ij}$表示第$i$个属性的第$j$个属性值
  下面分别采用MLE和MAP的方法对这两类参数进行估计。

使用MLE估计

π ^ k = P ^ ( Y = y k ) = # D { Y = y k } ∣ D ∣ θ ^ i j k = P ^ ( X i = x i j ∣ Y = y k ) = # D { X i = x i j ∧ Y = y k } # D { Y = y k } \begin{aligned} &\hat{\pi}_k=\hat{P}(Y=y_k)=\frac{\#D\{Y=y_k\}}{|D|}\\ &\hat{\theta}_{ijk}=\hat{P}(X_i=x_{ij}|Y=y_k)=\frac{\#D\{X_i=x_{ij}\land Y=y_k\}}{\#D\{Y=y_k\}} \end{aligned} ​π^k​=P^(Y=yk​)=∣D∣#D{Y=yk​}​θ^ijk​=P^(Xi​=xij​∣Y=yk​)=#D{Y=yk​}#D{Xi​=xij​∧Y=yk​}​​
但是如果某个属性值在训练集中没有与某个类同时出现过即$P(X_i|Y=y_k)=0$那么无论该样本的其他属性是什么$P(Y=y_k|X)$都将会被预测成零。这显然是不太合理的可以采用MAP估计来避免这个问题。

使用MAP估计

π ^ k = P ^ ( Y = y k ) = # D { Y = y k } + α k ∣ D ∣ + ∑ m α m θ ^ i j k = P ^ ( X i = x i j ∣ Y = y k ) = # D { X i = x i j ∧ Y = y k } + α k ′ # D { Y = y k } + ∑ m α m ′ \begin{aligned} &\hat{\pi}_k=\hat{P}(Y=y_k)=\frac{\#D\{Y=y_k\}+\alpha_k}{|D|+\sum_m\alpha_m}\\ &\hat{\theta}_{ijk}=\hat{P}(X_i=x_{ij}|Y=y_k)=\frac{\#D\{X_i=x_{ij}\land Y=y_k\}+\alpha_k'}{\#D\{Y=y_k\}+\sum_m\alpha_m'} \end{aligned} ​π^k​=P^(Y=yk​)=∣D∣+∑m​αm​#D{Y=yk​}+αk​​θ^ijk​=P^(Xi​=xij​∣Y=yk​)=#D{Y=yk​}+∑m​αm′​#D{Xi​=xij​∧Y=yk​}+αk′​​​
亦可以采用“拉普拉斯修正”西瓜书即假设先验概率符合均匀分布。

6.3 处理连续属性

修改朴素贝叶斯模型将$P(X_i=x|Y=y_k)$改为其概率密度函数。譬如我们采用高斯分布
$$P(X_i=x|Y=y_k)=\frac{1}{\sqrt{2\pi }{\sigma }_{ik}}{e}^{\frac{-(x-{\mu }_{ik}{)}^2}{2{\sigma }_{ik}^2}}$$
有时候我们假设方差

• 与$Y$无关这时${\sigma }_{ik}={\sigma }_i$
• 与$X_i$无关这时${\sigma }_{ik}={\sigma }_k$
• 与$X_i$和$Y$均无关这时${\sigma }_{ik}=\sigma$

6.4 总结

对于连续属性假设服从高斯分布我们首先要估计它的参数$\mu$$\sigma$利用最大似然进行估计。这里有点类似于概率论里多个随机变量满足独立同分布的情况这时利用极大似然估计得到的$\mu$就是样本的均值$\sigma$就是样本的方差。假设$n$个样本$x_1,x_2,\dots ,x_n$服从独立同分布且满足高斯分布则
$$\begin{array}{rl}\hat{\mu }& =\frac{1}{n}\sum _{i=1}^n{x}_i\\ \hat{\sigma }& =\frac{1}{n}\sum _{i=1}^n(x_i-\hat{\mu }{)}^2\end{array}$$
类似的可以对这里的参数进行估计。

7. 逻辑回归

现在我们考虑一个线性可分的二分类问题。接下来我们构造一个判别式模型即直接学习$P(Y|X)$假定数据满足以下条件

• $X$是实数向量$<X_1,\dots ,X_n>$
• $Y$是布尔向量
• 给定$Y$时$X_i$相互条件独立可以不需要
• $P(X_i|Y=y_k)$符合高斯分布$N({\mu }_{ik},{\sigma }_i)$
• $P(Y)$符合伯努利分布设$\pi =\hat{P}(Y=1)$

给定一个样本$X$其类别为$Y=1$的概率为
$$\begin{array}{rl}P(Y=1|X)& =\frac{P(Y=1)P(X|Y=1)}{P(Y=1)P(X|Y=1)+P(Y=0)P(X|Y=0)}\\ & =\frac{1}{1+\frac{P(Y=0)P(X|Y=0)}{P(Y=1)P(X|Y=1)}}\\ & =\frac{1}{1+\exp (\ln \frac{P(Y=0)P(X|Y=0)}{P(Y=1)P(X|Y=1)})}\\ & =\frac{1}{1+\exp (\ln \frac{1-\pi }{\pi }+{\sum }_i\ln \frac{P(X_i|Y=0)}{P(X_i|Y=1)})}\end{array}$$
又由于各个维度的条件概率均服从高斯分布因此
$$\begin{array}{rl}P(Y=1|X)& =\frac{1}{1+\exp (\ln \frac{1-\pi }{\pi }+{\sum }_i(\frac{{\mu }_{i0}-{\mu }_{i1}}{{\sigma }_i^2}{X}_i+\frac{{\mu }_{i1}^2-{\mu }_{i0}^2}{2{\sigma }_i^2}))}\end{array}$$
令$$w_0=\ln \frac{1-\pi }{\pi }+\sum _i(\frac{{\mu }_{i1}^2-{\mu }_{i0}^2}{2{\sigma }_i^2}),w_i=\frac{{\mu }_{i0}-{\mu }_{i1}}{{\sigma }_i^2}$$则有
$$P(Y=1|X)=\frac{1}{1+\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)}$$
进而有
$$P(Y=0|X)=\frac{\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)}{1+\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)}$$
进而
$$\begin{gathered} \frac{P(Y=0|X)}{P(Y=1|X)}=\exp (w_0+\sum _i{w}_i{X}_i) \\ \ln \frac{P(Y=0|X)}{P(Y=1|X)}=w_0+\sum _i{w}_i{X}_i \end{gathered}$$
所以逻辑回归是线性分类器。

另如果$X_i$不是相互条件独立的但是满足$P(X|Y=y_k)$符合高斯分布$N({\mu }_k,\Sigma )$也可推导出逻辑回归是线性分类器下面是推导过程。
由之前的推导可知
$$\begin{array}{rl}P(Y=1|X)& =\frac{1}{1+\exp (\ln \frac{1-\pi }{\pi }+\ln \frac{P(X|Y=0)}{P(X|Y=1)})}\end{array}$$
由于$$P(X|Y=y_k)$$满足多维高斯分布因此
$$\begin{array}{rl}\ln \frac{P(X|Y=0)}{P(X|Y=1)}& =\frac{1}{2}(X-{\mu }_2{)}^T{\Sigma }^{-1}(X-{\mu }_2)-\frac{1}{2}(X-{\mu }_1{)}^T{\Sigma }^{-1}(X-{\mu }_1)\\ & =\frac{1}{2}(X^T-{\mu }_2^T){\Sigma }^{-1}(X-{\mu }_2)-\frac{1}{2}(X^T-{\mu }_1^T){\Sigma }^{-1}(X-{\mu }_1)\\ & =X^T({\Sigma }^{-1}{\mu }_1-{\Sigma }^{-1}{\mu }_2)+\frac{1}{2}({\mu }_2^T{\Sigma }^{-1}{\mu }_2-{\mu }_1^T{\Sigma }^{-1}{\mu }_1)\end{array}$$
令$$W={\Sigma }^{-1}{\mu }_1-{\Sigma }^{-1}{\mu }_2,b=\frac{1}{2}({\mu }_2^T{\Sigma }^{-1}{\mu }_2-{\mu }_1^T{\Sigma }^{-1}{\mu }_1)+\ln \frac{1-\pi }{\pi }$$则
$$P(Y=1|X)=\frac{1}{1+\exp (W^{T}X+b)}$$
进而有
$$P(Y=0|X)=\frac{\exp (W^{T}X+b)}{1+\exp (W^{T}X+b)}$$
进而
$$\begin{gathered} \frac{P(Y=0|X)}{P(Y=1|X)}=\exp (W^{T}X+b) \\ \ln \frac{P(Y=0|X)}{P(Y=1|X)}=W^{T}X+b \end{gathered}$$
也可以推出逻辑回归是线性分类器。

7.1 拓展更多的类

y ∈ { y 1 , … , y R } y\in \{y_1,\dots,y_R\} y∈{y1​,…,yR​}学习$R-1$类权重参数。
若$k<R$
$$P(Y=y_k|X)=\frac{\exp (w_{k0}+{\sum }_{i=1}^n{w}_{ki}{X}_i)}{1+{\sum }_{j=1}^{R-1}\exp (w_{j0}+{\sum }_{i=1}^n{w}_{ji}{X}_i)}$$
若$k=R$
$$P(Y=y_R|X)=\frac{1}{1+{\sum }_{j=1}^{R-1}\exp (w_{j0}+{\sum }_{i=1}^n{w}_{ji}{X}_i)}$$

7.2 条件最大似然估计(MCLE)

为了让最后求解的结果和课件中保持一致我们对上面的表达形式做出修改
$$\begin{gathered} P(Y=0|X,W)=\frac{1}{1+\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)} \\ P(Y=1|X,W)=\frac{\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)}{1+\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i)} \end{gathered}$$
显然修改之后的形式和之前的式子等价。
条件最大似然
$$W_{MCLE}=\arg \underset{W}{\max }\prod _{l}P(Y^l|W,X^l)$$
现在我们需要选择一个向量$w$来最大化这个条件似然值。
$$\begin{array}{rl}l(W)& =\ln \prod _{l}P(Y^l|X^l,W)=\sum _l\ln P(Y^l|X^l,W)\\ & =\sum _l{Y}^l\ln P(Y^l=1|X^l,W)+(1-Y^l)\ln P(Y^l=0|X^l,W)\\ & =\sum _l{Y}^l\ln \frac{P(Y^l=1|X^l,W)}{P(Y^l=0|X^l,W)}+\ln P(Y^l=0|X^l,W)\\ & =\sum _l{Y}^l(w_0+\sum _{i=1}^n{w}_i{X}_i^l)-\ln (1+\exp (w_0+\sum _{i=1}^n{w}_i{X}_i^l))\end{array}$$
很遗憾它没有解析解。我们需要通过梯度上升法求出近似解也可以先取相反数然后利用梯度下降法求解得到的结果相同。
$$\begin{gathered} \begin{array}{rl}\frac{\partial l(W)}{\partial w_i}& =\sum _l{X}_i^l(Y^l-\frac{\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i^l)}{1+\exp (w_0+{\sum }_{i=1}^n{w}_i{X}_i^l)})\\ & =\sum _i{X}_i^l(Y^l-P(Y^l=1|X^l,W))\end{array} \\ {w}_i\leftarrow w_i+\eta \frac{\partial l(W)}{\partial w_i} \end{gathered}$$

7.3 MAP

MAP相当于增加了一个先验假设$W\backsim N(0,\sigma I)$那么
$$\begin{gathered} W\leftarrow \arg \underset{W}{\max }\ln [P(W)\prod _{l}P(Y^l|X^l,W)] \\ {w}_i\leftarrow w_i-\eta \lambda w_i+\eta \sum _i{X}_i^l(Y^l-P(Y^l=0|X^l,W)) \end{gathered}$$
其中$\lambda >0$$\eta$是学习率。
上式中的正则项其实就是由先验分布得到的正则项前面的负号来自于高斯分布$e$指数上的负号加入正则项可以让$W$中的元素尽量接近于0从而有效避免模型的过拟合。

7.4 补充KL距离

从KL距离的角度可以得出与条件似然估计相似的结果。
假设$p$是$X$和$Y$的真实分布$q$是逻辑回归估计的分布则$p(Y=1|X)$和$p(Y=0|X)$这两个概率值一个为1一个为0且
$$\begin{array}{rl}q(Y=1|X)& =\frac{1}{1+\exp (w^{T}x)}\\ q(Y=0|X)& =1-q(Y=1|X)\end{array}$$
我们计算$p$和$q$的KL距离化简时需要注意到$p$分布的信息熵是0
$$\begin{array}{rl}{D}_{KL}(p(Y)||q(Y))& =\sum _{Y}p(Y)\log \frac{p(Y)}{q(Y)}\\ & =\sum _{Y}p(Y)\log \frac{1}{q(Y)}-\sum _{Y}p(Y)\log \frac{1}{p(Y)}\\ & =-\sum _{Y}p(Y)\log q(Y)\\ & =\sum _l-Y^l\log \frac{1}{1+\exp (w^{T}x)}-(1-Y^l)\log \frac{\exp (w^{T}x)}{1+\exp (w^{T}x)}\end{array}$$
这便是逻辑回归的损失函数。

哈工大机器学习复习笔记一
哈工大机器学习复习笔记二
哈工大机器学习复习笔记三
哈工大机器学习复习笔记四