Naive Bayes 的学习与分类

基本方法

设输入空间 $\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)$ 独立同分布产生


由训练数据集 $T$ 我们便可以得出先验概率分布
$$ P(Y=c_k),\space k=1, 2, \dots, K $$ 以及条件概率分布 $$ P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)}, \dots, X^{(n)}=x^{(n)}|Y=c_k), \space k=1, 2, \dots, K $$ 于是我们便学习到了联合概率分布 $P(X, Y)$


在朴素贝叶斯中我们对条件概率分布作了条件独立性的假设,于是有:
$$ P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)}, \dots, X^{(n)}=x^{(n)}|Y=c_k)=\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k) $$
显然,条件独立性这一假设使得计算变得非常简单,同时,这也会牺牲一定的分类准确率。


在分类时,对于给定的输入 $x$,我们通过已知的模型来计算后验概率分布 $P(Y=c_k|X=x)$,挑选后验概率最大的类别作为 $x$ 的输出,便是朴素贝叶斯法的分类。

接下来我们推导一下如何计算后验概率:

首先,补充一点基础知识,条件概率
$$ P(A|B)=\frac{P(A, B)}{P(B)} $$ 于是我们可以引申出 $$ P(A,B)=P(A|B) \cdot P(B) $$ $$ P(A,B)=P(B|A) \cdot P(A) $$

联立可得,贝叶斯公式的常规形式为
$$ P(A|B)=\frac{P(B|A)P(A)}{P(B)} $$
全概率公式:若事件 $B_1, B_2, \dots, B_n$ 是样本空间 $\Omega$ 的一个划分,则
$$ P(A)=\sum_{i=1}^{n}P(A, B_i) $$ 结合条件概率公式可得 $$ P(A)=\sum_{i=1}^{n}P(A|B_i)P(B_i) $$ 于是,我们可以将其与贝叶斯公式结合得到 $$ P(A|B)=\frac{P(B|A)P(A)}{\sum_{i=1}^{n}P(B|A_i)P(A_i)} $$


同理,我们在求后验概率时便可根据贝叶斯定理进行
$$ P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{i=1}^{k}P(X=x|Y=c_i)P(Y=c_i)} $$ 已知,在朴素贝叶斯中 $$ P(X=x|Y=c_k)=\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k) $$ 代入得 $$ P(Y=c_k|X=x)=\frac{P(Y=c_k)\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)}{\sum_{i=1}^{k}P(Y=c_i)\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_i)}, \space k=1, 2, \dots, K $$


综上,我们的朴素贝叶斯分类器便可以表示为
$$ y=f(x)=\arg \max_{c_k}\frac{P(Y=c_k)\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)}{\sum_{i=1}^{k}P(Y=c_i)\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_i)} $$ 仔细观察可以发现,式子中的分母不受 $c_k$ 的影响,因此该分类器可以简化为 $$ y=f(x)=\arg \max_{c_k}P(Y=c_k)\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k) $$


后验概率最大化的含义

朴素贝叶斯法将实例分到后验概率最大的类别中,这等价于期望风险最小化。

假设我们选择0-1损失函数:
$$ L(Y, f(X)) = \begin{cases} 1, & Y \neq f(X) \\ 0, & Y = f(X) \end{cases} $$ 此时,期望风险函数为 $$ \begin{eqnarray} R_{exp}(f) &=& E_p[L(Y, f(X))]\\ &=&\int_{\mathcal{X}\times\mathcal{Y}}L(y,f(x))P(x,y)dxdy\\ &=&\int_{\mathcal{X}\times\mathcal{Y}}L(y,f(x))P(y|x)P(x)dxdy\\ &=&\int_{\mathcal{X}}[\int_{\mathcal{Y}}L(y,f(x))P(y|x)dy]P(x)dx \end{eqnarray} $$ 要使期望风险最小化,由于每一个 $P(X=x)$ 都是常数,则只需内层积分最小即可。 其中,内层积分 $\int_{\mathcal{Y}}L(y,f(x))P(y|x)dy$ 称为在 $X=x$ 时 $y$ 的条件期望,综上,期望风险最小等价于条件期望最小。 由此取条件期望 $$ R_{exp}(f)=E_x\sum_{k=1}^{K}[L(c_k, f(X))]P(c_k|X) $$ 为了使期望风险最小化,只需对 $X=x$ 逐个极小化,由此得到 $$ \begin{eqnarray} f(x)&=&\arg\min_{y\in\mathcal{Y}}\sum_{k=1}^{K}L(c_k, y)P(c_k|X=x)\\ &=&\arg\min_{y\in\mathcal{Y}}\sum_{k=1}^{K}P(y\not=c_k|X=x)\\ &=&\arg\min_{y\in\mathcal{Y}}(1-P(y=c_k|X=x))\\ &=&\arg\max_{y\in\mathcal{Y}}P(y=c_k|X=x) \end{eqnarray} $$ 这样一来,根据期望风险最小化准则就得到了后验概率最大化准则 $$ f(x)=\arg\max_{c_k}P(c_k|X=x) $$
即朴素贝叶斯法所采取的原理


文中公式较多,难免可能存在一些编辑上或者理解上的错误,望发现后指出。

参考资料:《统计学习方法》李航