朴素贝叶斯法

朴素贝叶斯是一种用先验概率估计后验概率的模型，通过估计先验概率得到样本和类别的近似联合概率，随后通过联合概率分布获得需要的后验概率分布进而实现分类。本次介绍的朴素贝叶斯法主要包括三块：总体思想(将后验概率转换为先验概率)、极大似然估计(使用极大似然法估计先验概率)、贝叶斯估计(使用贝叶斯估计得到先验概率)。

符号说明

设输入空间\(\mathcal{X}\subseteq \mathbf{R}^n\)为\(n\)维向量的集合，输出空间的集合\(\mathcal{Y}=\{c_1,c_2,\cdots,c_K\}\)，则在样本(示例，特征向量)\((\bm{x},y)\)中\(\bm{x}\in \mathcal{X}\)，\(y\in \mathcal{Y}\)。继续定义\(X,Y\)分别是在输入空间\(\mathcal{X}\)和输出空间\(\mathcal{Y}\)上的随机变量，\(P(X,Y)\)表示\(X\)和\(Y\)的联合概率分布，且训练数据集

\[T=\{(\bm{x_1},y_1), (\bm{x_2},y_2),\cdots, (\bm{x_N},y_N)\} \]

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

贝叶斯总体模型

对于一个分类任务，我们可以使用判别方法直接计算样本\(x\)为所有类别的概率，并通过最大的类别概率来获得其类别即：
\begin{equation}
y^{hat} = \mathop\arg\max\limits_{c_k}P(Y=c_k|X=\bm{x}), k=1,2,\cdots,K
\end{equation}
我们也可以通过生成方法估计样本的总体分布并间接获得样本为每个类别的概率即：

\[\begin{align} P(Y=c_k|X=\bm{x})&=\frac{P(X=\bm{x},Y=c_k)}{P(X=\bm{x})}\notag \\ &=\frac{P(Y=c_k)P(X=\bm{x}|Y=c_k)}{P(X=\bm{x})}\notag \\ &=\frac{P(Y=c_k)P(X=\bm{x}|Y=c_k)}{\sum\limits_{i=1}^k P(Y=c_k)P(X=\bm{x}|Y=c_k)}\\ \end{align} \]

这样就基本构成了贝叶斯模型，但仅仅这样是不够的，因为\(P(X=\bm{x}|Y=c_k)\)是很难求得的，\(\bm{x}\)是\(n\)维的向量，其组合太大，若假设在\(\bm{x}\)中，其每维维可取值\(S_j\)，\(j\)代表每一维，\(j=1,2,\cdots,n\)，那么对于一个样本\(\bm{x}\)其预测为\(c_k\)一个类别所含有的参数就为\(\prod\limits_{j=1}^{n}S_j\)，若要得到这个样本的全部类别，那么需要的参数量就是\(K\prod\limits_{j=1}^{n}S_j\)，显然这样做太复杂了，我们需要统计的组合太多，怎么办？

一种简化计算的方式是，假定每个维度的特征之前是互不相关的，虽然这样会损失掉很多原有相关的信息，但是可以大大的减少参数量，如下所示：

\[\begin{align} P(X=\bm{x}|Y=c_k)&=P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\notag \\ &=P(X^{(1)}=x^{(1)}|Y=c_k)P(X^{(2)}=x^{(2)}|Y=c_k)\cdots P(X^{(n)}=x^{(n)}|Y=c_k)\notag \\ &=\prod\limits_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k) \end{align} \]

这样参数量可以由\(K\prod\limits_{j=1}^nS_j\)降低为\(K\sum\limits_{j=1}^nS_j\)，毫无疑问，这无疑是一个巨大的突破，尽管失去了特征之间的相关性信息。
将\((3)\)带入\((2)\)中可得：

\[\begin{align} P(Y=c_k|X=\bm{x})&=\frac{P(Y=c_k)P(X=\bm{x}|Y=c_k)}{\sum\limits_{i=1}^k P(Y=c_k)P(X=\bm{x}|Y=c_k)}\notag \\ &=\frac{P(Y=c_k)\prod\limits_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum\limits_{i=1}^k\{P(Y=c_k)\prod\limits_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)\}} \end{align} \]

对于同一个样本\(\bm{x}\)，其共需要预测\(K\)个类别\(c_1,c_2,\cdots,c_K\)，但从上式可知，无论预测哪个类别，在分母中，会计算所有类别的相关信息，而这对于所有类别都是相同的，所以分母部分可以省略。故最终的模型为：

\[\begin{align} P(Y=c_k|X=\bm{x})&={P(Y=c_k)\prod\limits_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)} \end{align} \]

另外几个需要区分的点是：
先验概率：即通过样本可以统计出来的概率。
后验概率：需要通过转换求取的概率，不能直接统计得到。

极大似然估计

通过贝叶斯模型，我们将一个后验概率通过条件概率公式转换成了求解\(P(X, Y)\)的分布并通过简化版的先验概率(特征独立)来估计分布\(P(X,Y)\)。但是这里面有一个问题没有解决，那就是先验概率\(P(X^{(j)}=x^{(j)}|Y=c_k)\)和\(P(Y=c_k)\)如何求解?
当然一种非常直观的计算方式就是直接统计满足上面条件的样本占总体样本的比例，所以很自然的我们可以得到下面的两个计算式子：

\[\begin{equation} P(Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(y_i=c_k)}{N} \end{equation} \]

\[\begin{equation} P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits_{i=1}^N I(y_i=c_k)} \end{equation} \]

其中\(a_{jl}\)表示第\(j\)个特征的第\(i\)个可能取的值，\(x_i^{(j)}\)表示第\(i\)个样本的第\(j\)个特征的值。
但是为什么可能这样表示呢？我们通过极大似然估计来证明上述两个等式成立。
求\(P(Y=c_k)\)的概率，按照极大似然函数的思想就是求解当\(P(Y=c_k)\)为多少时，可以使得能够最有可能产生这么一群样本。
因此，我们可以假设\(\theta=P(Y=c_k)\)为参数，那么\(1-\theta=P(Y\neq c_k)\)。并且我们已经假设过所有样本是独立同分布产生的，故可以构造如下的似然函数：

\[L(\{\bm{x_1},y_1\},\{\bm{x_2},y_2\},\{\bm{x_N},y_N\};\theta)=\theta^{\sum\limits_{i=1}^N I(y_i=c_k)}(1-\theta)^{N-\sum\limits_{i=1}^NI(y_i=c_k)} \]

两边取自然对数得：

\[\ln L=\sum\limits_{i=1}^N I(y_i=c_k)\ln\theta + (N-\sum\limits_{i=1}^NI(y_i=c_k)) \ln(1-\theta) \]

两边求导

\[\frac{L^{‘}}{L}=\frac{\sum\limits_{i=1}^N I(y_i=c_k)}{\theta} + \frac{\sum\limits_{i=1}^NI(y_i=c_k)-N}{1-\theta} \]

令其为0\(\Rightarrow\)\(\theta=\frac{\sum\limits_{i=1}^{N}I(y_i=c_k)}{N}\)

对于\(P(X^{(j)}=a_{jl}|Y=c_k)\)，我们先对其进行转换：

\[P(X^{(j)}=a_{jl}|Y=c_k)=\frac{P(X^{(j)}=a_{jl},Y=c_k)}{P(Y=c_k)} \]

由于分母已经求出，因此只需再求出分子即可，我们使用相同的思想，将样本分为两部分，第一部分样本满足$$P(X^{(j)}=a_{jl},Y=c_k)$$，第二部分取其补集。同样的，我们让概率参数\(\theta=P(X^{(j)}=a_{jl},Y=c_k)\)，那么\(1-\theta\)=不同时满足上述条件的概率。
根据样本都是独立同分布产生的，我们构造相似的似然函数

\[L(\theta)=\theta^{\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}(1-\theta)^{N-\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)} \]

显然可以求出极大值\(\theta=\frac{\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}{N}\)，所以易得

\[P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits_{i=1}^N I(y_i=c_k)} \]

贝叶斯估计

极大似然估计虽然可以计算出先验概率，但是可能会出现估计参数的概率值为0的情况，即满足\(x_i^{(j)}=a_{jl}\)且\(y_i=c_k\)的样本数量为0。(这通常是不合理的，因为我们得到的样本本就是一个采样，无法保证完全近似全体样本的分布，哪怕概率很小通常也不会设为0)，那么如何避免这种情况？
一种处理方式就是添加系数，如下式：

\[\begin{equation} P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum\limits_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum\limits_{i=1}^N I(y_i=c_k)+S_j\lambda} \end{equation} \]

当\(\lambda=0\)时为极大似然估计，当\(\lambda=1\)时成为拉普拉斯平滑，满足下式：

\[\begin{equation} \begin{cases} P_\lambda(X^{(j)}=a_{jl}|Y=c_k)>0\\ \sum\limits_{i=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)=1 \end{cases} \end{equation} \]

对于第二个式子，相当于把\(j\)维的每一个值分成了一份，公有\(S_j\)份，所有概率最后相加为1。
同样的对\(P(Y=c_k)\)也可以进行改写。

\[\begin{equation} P(Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(y_i=c_k) + \lambda}{N+K\lambda} \end{equation} \]