PR学习笔记 #2 贝叶斯分类器

在 IR学习笔记 #4 概率模型 中曾提到朴素贝叶斯（Naive Bayes）的应用，这里正式学到。贝叶斯分类器基于概率论的原理，是最经典的分类算法之一。其解决的核心点在于根据已有概率信息，对未知事物发生结果的概率计算。

朴素贝叶斯 | Naive Bayes

概率论中有许多易混淆的数学表述，这里列举：

• 条件概率公式：\(\begin{aligned} P(A \mid B)=\frac{P(A B)}{P(B)}\end{aligned}\)
• 概率乘法公式：\(P(A B)=P(A \mid B) P(B)\)
• 全概率公式：\(\begin{aligned} P(A)=\sum_{i=1}^{n} P\left(A B_{i}\right)=\sum_{i=1}^{n} P\left(A \mid B_{i}\right) P\left(B_{i}\right)\end{aligned}\)
• 贝叶斯公式：\(\begin{aligned} P\left( B_i\mid A \right) =\frac{P\left( AB_i \right)}{P\left( A \right)}=\frac{P\left( A\mid B_i \right) P\left( B_i \right)}{\sum_{i=1}^n{P\left( A\mid B_i \right) P\left( B_i \right)}}\end{aligned}\)

算法原理

下面引入训练集的定义： \[ D=\left\{ x^{\left( i \right)},i=1,2,\cdots ,m \right\} ,\quad C=\left\{ x^{(i)}\in \omega ^{\left( j \right)},\;j=1,2,\cdots ,N \right\} \]

• \(m\) 代表训练集中样本点的数量；
• \(x^{(i)}\) 代表第 \(i\) 个样本点，是一个 \(n\) 维向量，\(n\) 代表特征数；
• \(N\) 代表类别数，所有训练集中样本点被显式地标注；
• 样本向量展开为 $x^{( i )}={ A_1=a_{i1},A_2=a_{i2},,A_n=a_{in} } $。

贝叶斯分类器要解决的问题就是，利用上述数据集，将一个新的测试样例 $x={ A_1=a_{1},A_2=a_{2},,A_n=a_{n} } $ 归为 \(N\) 中的某一类。在这个基础上，我们有如下定义：

• 先验概率：\(P\left( \omega ^{\left( j \right)} \right)\)，表示对任意未知测试样例，将其归为类别 \(\omega ^{\left( j \right)}\) 的概率，常用训练集中类别 \(\omega ^{\left( j \right)}\) 占 \(m\) 的比例估计。满足 \(\sum_{j=1}^N{P\left( \omega ^{\left( j \right)} \right)}=1\)。
• 后验概率：\(P\left( \omega ^{\left( j \right)} \mid x \right)\)，表示对已知特征测试样例，将其归为类别 \(\omega ^{\left( j \right)}\) 的概率，就是贝叶斯分类器所要求的。满足 \(\sum_{j=1}^N{P\left( \omega ^{\left( j \right)}\mid x \right)}=1\)。
• 似然概率：\(P\left( x \mid \omega ^{\left( j \right)} \right)\)，表示在类别 \(\omega ^{\left( j \right)}\) 中，出现属性等同于测试样例的训练样例的概率，可用训练集类别 \(\omega ^{\left( j \right)}\) 中含 \(x\) 的比例估计。

于是，利用贝叶斯公式导出： \[ P\left( \omega ^{\left( j \right)} \mid x \right) =\frac{P\left( x \mid \omega ^{\left( j \right)} \right) P\left( \omega ^{\left( j \right)} \right)}{P\left( x \right)}=\frac{P\left( x \mid \omega ^{\left( j \right)} \right) P\left( \omega ^{\left( j \right)} \right)}{\sum_{i=1}^N{P\left( x \mid \omega ^{\left( i \right)} \right) P\left( \omega ^{\left( i \right)} \right)}} \]

似然概率

前文提到，在计算 \(P(x \mid \omega ^{\left( j \right)})\) 时，我们可用训练集类别 \(\omega ^{\left( j \right)}\) 中含 \(x\) 的比例估计。然而，这样做会遇到一个问题：当类别 \(\omega ^{\left( j \right)}\) 中不存在 \(x\) 样本点的时候，如果将概率视作 0，那么结果则必为 0，显然不符合要求。

而上述这种情况经常会发生在多属性的样本分类中，因此，我们改用： \[ P\left(x \mid \omega ^{\left( j \right)}\right)=\prod_{k=1}^n{P\left(A_k=a_k \mid \omega ^{\left( j \right)}\right)} \] 其中，\(P\left(A_k=a_k \mid \omega ^{\left( j \right)}\right)\) 表示在类别 \(\omega ^{\left( j \right)}\) 中，第 \(k\) 个属性值时 \(a_k\) 的样本出现的概率。

此处采用连乘的形式，是基于所有属性相互独立的假设（这正是「朴素」的由来），否则应当使用概率乘法公式，即：$P( A_1A_2A_3 ) =P( A_1 ) P( A_2 A_1 ) P( A_3 A_1A_2 ) $。

对于 \(P\left(A_k=a_k \mid \omega ^{\left( j \right)}\right)\) 的求法，则须分两种情况来讨论：

1. \(A_k\) 是离散属性，直接用 \(a_k\) 在类别中的比例估计即可。如果依然发生了零频问题，则需要考虑使用折扣法、插值法、退避法等进行平滑处理。

2. \(A_k\) 是连续属性，通常我们假设 \(A_k\) 在类别中是符合均值为 \(\mu\)，标准差为 \(\sigma\) 的正态分布（详见：PR学习笔记 #3 概率密度：参数估计），则用其概率密度函数的值估计其概率： \[ P(A_k=a_k \mid \omega ^{\left( j \right)})=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(a_k-\mu )^2}{2\sigma ^2}} \]

决策理论

有了后验概率，现在则需要考虑决策问题。

最小错误率分类

在贝叶斯分类器中，在我们计算出所有类别的后验概率之后，若有： \[ P\left( \omega ^{\left( j \right)} \mid x \right) =\max \left\{ P\left( \omega ^{\left( 1 \right)} \mid x \right) ,P\left( \omega ^{\left( 2 \right)} \mid x \right) ,\cdots ,P\left( \omega ^{\left( N \right)} \mid x \right) \right\} \] 则认为 \(x\in \omega ^{\left( j \right)}\)，这是基于最小化错误率的思想。当选择了类别 \(\omega ^{\left( j \right)}\)，错误分类的概率就是 \(x\notin \omega ^{\left( j \right)}\) 的概率： \[ P(\mathrm{error} \mid x)=1-\underset{j=1,\cdots ,N}{\max}\left\{ P\left( \omega ^{\left( j \right)} \mid x \right) \right\} \]

当然，这时在固定测试样本为 \(x\) 的情况下，如果要求对所有不同的 \(x\) 取值的平均错误率 \(P(\mathrm{error})\)，则需要对整个特征空间进行加权求和。

此外，按照最小错误率来分类时，我们只需要比较出后验概率最大的一类就行，因此在计算过程中只需比较分子部分 \(P\left( x \mid \omega ^{\left( j \right)} \right) P\left( \omega ^{\left( j \right)} \right)\) 的大小即可。

最小风险分类

但在实际分类情形中，我们还应当考虑每次决策的代价——譬如将患者诊断为阴性的代价要远大于将正常人诊断为阳性。为此，我们补充如下定义：

• 决策：\(\alpha_i\)，表示将测试样例 \(x\) 分到类别 \(\omega ^{\left(i\right)}\)。
• 代价：\(\lambda _{ij}=\lambda \left( \alpha _i \mid \omega _j \right)\)，表示将真实类别 \(\omega ^{\left(j\right)}\) 中的样本分到预测类别 \(\omega ^{\left(i\right)}\) 的代价，当 \(i=j\) 时代价显然较小，其他时候代价较大。在决策分类的离散情况下，通常需要事先绘制代价矩阵 \(\lambda _{N \times N}\)。

则可以得到下面的条件风险： \[ R\left( \alpha _i \mid x \right) =\mathbb{E}\left[ \lambda _{ij} \mid x \right] =\sum_{j=1}^N{\lambda _{ij}}P\left( \omega _j \mid x \right) \] 如果我们致力于最小化总体风险，则需要定义决策函数（最优分类器）： \[ \alpha \left( x \right) =\underset{i=1,\cdots ,N}{\mathrm{arg}\min}R\left( \alpha _i\mid x \right) \] 此时，在整个特征空间中，对所有不同的 \(x\) 取值，采取决策函数带来的期望风险为： \[ R=\int{R\left( \alpha \left( x \right) \mid x \right)}P\left( x \right) \mathrm{d}x \]

半朴素贝叶斯分类

前文提到，朴素贝叶斯分类中采用了所有属性条件独立的假设，但在现实任务中这个假设往往很难成立。因此，我们对假设进行一定程度的放松，适当考虑部分属性间的相互依赖信息，因此称为「半朴素」。

其中，独依赖估计（One-Dependent Estimator，ODE）是半朴素贝叶斯分类器最常用的一种策略，顾名思议，就是假设每个属性最多仅依赖于一个其他属性。

被依赖的属性称为父属性，用 \(pA_k\) 来表示，则似然概率： \[ P\left( x\mid \omega ^{\left( j \right)} \right) =\prod_{k=1}^n{P\left( A_k=a_k\mid \omega ^{\left( j \right)},pA_k=pa_k \right)} \] 那么，问题的关键就转化为如何确定每个属性的父属性。最直接的做法就是假设所有属性都依赖于同一个父属性，称之为超父（Super-Parent），对应的方法称为 SPODE (Super-Parent ODE)。

此外，还有更为复杂的 TAN (Tree Augmented Naive Bayes)，通过计算所有属性两两之间的条件互信息（Conditional Mutual Information）： \[ I\left( A_i,A_j\mid C \right) =\sum_{A_i,A_j;\omega ^{\left( j \right)}\in C}{P}\left( A_i,A_j\mid \omega ^{\left( j \right)} \right) \log \frac{P\left( A_i,A_j\mid \omega ^{\left( j \right)} \right)}{P\left( A_i\mid \omega ^{\left( j \right)} \right) P\left( A_j\mid \omega ^{\left( j \right)} \right)} \] 绘制出带权无向完全图，任意两个结点之边的权重为 \(I\left( A_i,A_j\mid C \right)\)。再构建此完全图的最大带权生成树，挑选根结点，将边置为有向，就得到了每个属性及其父属性的依赖关系。