Home

gentlesnow

10 Jun 2019

【西瓜书】 007 贝叶斯分类器

贝叶斯决策论

贝叶斯决策论（Bayesian decision theory）是概率论框架下实施决策的基本方针。 对分类任务来说，在所有相关概率都已知的情况下，贝叶斯决策论考虑如何基于这些概率和误判才选择最优的类别标记。

假设有$N$种可能的类别标记，即$\mathcal{Y} = {c_1, c_2, …, c_N}$，$\lambda_{ij}$是将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失。 基于后验概率$P(c_i|x)$可获得将样本$x$分类为$c_i$所产生的期望损失，即在样本$x$上的“条件风险”（conditional risk）。

\[R(c_i|x) = \sum_{j=1}^{N}{\lambda_{ij}P(c_j|x)}\]

寻找一个判定准则$h: \mathcal{X} -> \mathcal{Y}$，以最小化总体风险

\[R(h) = E_x[R(h(x)|x)]\]

对每个样本$x$，若$h$能最小化风险条件$R(h(x)|x)$，则总体风险$R(h)$也将被最小化。 这就产生了贝叶斯准则： 为最小化总体风险，只需在每个样本上选择那个使条件风险$R(c|x)$最小的类别标记。 即：

\[h^{\ast(x)} = \arg\min_{c \in \mathcal{Y}}{R(c|x)}\]

此时$h^\ast$称为贝叶斯最优分类器（Bayes optimal classifier），与之对应的总体风险$R(h^\ast)$称为贝叶斯风险（Bayes risk）。$1 - R(h^\ast)$反映了分类器所能够达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

若目标最小化分类错误率，则错误率$\lambda_{ij}$可写为：

\[\lambda_{ij} = \left\{\begin{array}{rcl} 0, & if i = j \\ 1, & otherwise,\end{array}\right\]

此时条件风险：

\[R(c|x) = 1 - P(c|x)\]

于是最小化分类错误率的贝叶斯最优分类器为：

\[h^\ast(x) = \arg\min_{c \in \mathcal{Y}}{P(c|x)}\]

即对于每个样本$x$，选择能使后验概率最大的类别标记。

欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率。

机器学习所要的实现的是基于有限的训练样本尽可能的估计出后验概率 $P(c x)$。

大体来说，有两种策略：

  1. 给定 $x$ ，可通过直接建模 $ P(c|x) $ 来预测 $c$ ，这样得到的是“判别式模型”
  2. 先对联合概率分布$P(x, c)$建模，然后在由此获得$P(c|x)$，这样得到的模型是“生成式模型”

决策树、BP神经网络、支持向量机等都可归入判别模型的范畴。

\[P(c|x) = \frac{P(x, c)}{P(x)} = \frac{P(c)P(x|c)}{P(x)}\]
  • $P(c)$是类“先验”（prior）概率
  • $P(x|c)$是样本$x$相对于类标记$c$的类条件概率（class-conditional probability）或称为“似然”（likelihood）
  • $P(x)$是用于归一化的“证据”（evidence）因子

对给定样本$x$，证据因子$P(x)$与类标记无关。 因此估计$P(x|c)$的问题就转化为如何基于训练数据$D$来估计先验$P(c)$和似然$P(x|c)$

  • 类先验概率$P(c)$表达了样本空间中各类样本所占比例，根据大数定律，当训练集包涵充足的独立同分布样本时，$P(c)$可通过各类样本的频率来进行估计。
  • 对类条件概率$P(x|c)$来说，由于它涉及关于$x$所有属性的联合概率，直接跟样本出现的频率来估计将会遇到严重的困难。

极大似然估计

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。

概率模型的训练过程就是参数估计（parameter estimation）过程。

对于参数估计，统计学界的两个学派提供了不同的解决方案：

  1. 频率主义学派（Frequentist）认为参数虽然未知，但却是客观存在的固定值，因此，可通过优化似然函数等准则来确定参数值
  2. 贝叶斯学派（Bayesian）认为参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。

源自频率主义学派的极大似然估计（MLE）是根据数据采样来估计概率分布参数的经典方法。

ml-07-1

这种参数化的方法虽然能使条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。 在现实应用中，欲做出能较好地接近潜在真实分布的假设，往往需在一定程度上利用关于应用任务本身的经验知识，否则仅凭“猜测”来假设概率分布形式，和可能产生误导性的结果。

朴素贝叶斯分类器

贝叶斯公式来估计后验概率的主要困难在于： 类条件概率是所有属性上的联合概率，难以从有限的训练样本直接估计得到。

朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”（attribute conditional independence assumption）： 对已知类别假设所有属性相互独立。 假设每个属性独立的对分类结果发生影响。

ml-07-2

为避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值通常要进行“平滑”（smoothing），常用“拉普拉斯修正”（Laplacian correction）。

$$\hat{P}(c) = \frac{ D_c + 1}{ D + N}$$  
$$\hat{P}(x_i c) = \frac{ D_{c,x_i} + 1}{ D_c + N_i}$$

拉普拉斯修正实质上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习过程中额外引入的关于数据的先验。

拉普拉斯修正避免德银训练集样本不充分而导致概率估计值为零的问题，并且在训练集变大时，修正过程所引入的先验的影响也会主编变得可忽略，使得估计值趋向于实际概率值。

在现实任务中朴素贝叶斯分类器有多种使用方式：

  1. 若任务对预测速度要求较高，则对给定训练集可将朴素贝叶斯分类器涉及的所有概率估值实现计算好存储起来，这样在预测时只需查表即可进行判别
  2. 若任务数据更替频繁，则可采用“懒惰学习”（lazy learning）方式，先不进行任何训练，带收到预测请求时再根据当前数据集进行概率估值
  3. 若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值涉及的概率估值进行技术修正即可实现增量学习

半朴素贝叶斯分类器

人们尝试对属性条件独立性假设进行一定程度的放松，因此产生了一类称为“半朴素贝叶斯分类器”的学习方法。

半朴素贝叶斯分类器的基本思想： 适当考虑一部分属性间相互依赖信息，从而既不需进行完全概率计算，又不至于彻底忽略了比较强的属性依赖关系。

“独依赖估计”（One-Dependent Estimator ODE）是半朴素贝叶斯分类器最常用的一类策略。 所谓“独依赖”就是假设每个属性在类别之外仅依赖于一个其他属性，即

\[P(c|x) \propto P(c) \prod_{i=1}^{d}{P(x_i|c,pa_i)}\]

问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。

  1. SPODE(Super-Parent ODE)方法 假设所有的属性都依赖以同一个属性，称为“超父”（super-parent），然后通过交叉验证等模型选择方法来确定超父属性。
  2. TAN(Tree Augmented naive Bayes)则是在最大带权生成树（maximum weightedspanning tree）算法的基础上通过以下步骤将属性间依赖关系简约成树形结构
    • 计算任意两个属性之间的条件互信息（conditional mutual information） \(I(x_i,x_j|y) = \sum_{x_i,y_i;c\in\mathcal{Y}}{\log{\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}}}\)
    • 以属性为结点构建完全图，任意两个结点之间边的权重设为$I(x_i,x_j y)$
    • 构建此完全图的最大带权生成树，挑选根变量，将边置为有向
    • 加入类别结点y，增加从y到每个属性的有向边
  3. AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制，更为强大的独依赖分类器。 AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果

ml-07-3

于朴素贝叶斯分类器类似，AODE的训练过程也是“计数”，即在训练数据集上对符合条件的样本进行计数的过程。 于朴素贝叶斯分类器相似，AODE无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方式再进行计数，并且易于实现增量学习。

将独依赖假设改为属性间高阶依赖。若训练数据非常充分，泛化性能有可能提升；但在有限样本条件下，则又陷入估计高阶联合概率的泥沼。

贝叶斯网

贝叶斯网（Bayesian network）亦称“信念网”（belief network），它借助有向无环图（Directed Acyclic Graph，DAG）来刻画属性之间的依赖关系，并使用条件概率表（Conditional Probability Table，简称CPT）来描述属性的概率分布。

一个贝叶斯网$\mathcal{B}$由结构$\mathcal{G}$和参数$\Theta$两部分构成，即$\mathcal{B} = <\mathcal{G}, \Theta>$。

  • 网络结构$\mathcal{G}$是一个有向无环图，其每个节点对应一个属性，若两个属性又直接依赖关系，则它们由一条边连接起来
  • 参数$\Theta$定量描述这种依赖关系

假设属性$x_i$在$\mathcal{G}$中的父结点集为$\pi_i$，则$\Theta$包含了每个属性的条件概率表$\theta_{x|\pi_i} = P_B(x_i|\pi_i)$

结构

$\mathcal{B} = <\mathcal{G}, \Theta>$将属性$x_1, x_2, …,x_d$的联合概率分布定义为：

\[P_B(x_1, x_2, ...,x_5) = \prod_{i=1}^{d}{P_B(x_i|\pi_i)} = \prod_{i=1}^{d}{P_B(\theta_{x_i}|\pi_i)}\]

贝叶斯网中三个变量之间的典型依赖关系

  1. 同父结构
  2. V型结构
  3. 顺序结构
  • 在同父结构中，给定父节点，子结点条件独立
  • 在顺序结构中，给定中间节点，两节点条件独立
  • 在V型结构中，给定子结点，父节点必不独立；子结点未知，父节点相互独立

ml-07-4

对变量做积分或求和亦称为“边际化” 这样的独立性称为“边际独立性”。

为了分析有向图中变量的关系，可使用“有向分离”（D-separation）把有向图转变成一个无向图

  1. 找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无向边
  2. 将所有的有向边改为无向边 由此产生的无向图称为“道德图”，令父节点相连的过程称为“道德化”。

学习

若网络结构可知，即属性间的依赖关系已知，则贝叶斯网的学习过程只需对训练样本计数，估计出每个结点的概率表即可。 但在现实中往往不知晓网络结构，贝叶斯网学习的首要任务就是根据训练数据集来找出结构最恰当的贝叶斯网。

先定一个评分函数，以此来评估贝叶斯网与训练函数的契合程度， 然后基于这个评分函数来寻找结果最优的贝叶斯网。 评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好。

推断

EM算法

贝叶斯应用

  1. 中文分词 分词后，得分的假设是基于两词之间是独立的，后词的出现与前词无关
  2. 统计机器翻译 统计机器翻译因为其简单，无需手动添加规则，迅速成为了机器翻译的事实标准。
  3. 贝叶斯图像识别 首先是视觉系统提取图形的边角特征，然后使用这些特征自底向上地激活高层的抽象概念，然后使用一个自顶向下的验证来比较到底哪个概念最佳地解释了观察到的图像。

Til next time,
gentlesnow at 20:24

scribble
‹ ›