Skip to content

贝叶斯分类器

贝叶斯决策论

叶斯决策论(Bayesian decision theory) 是概率框架下实施决策的基本方法

机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率 \(P(c|x)\)。 有如下两种方式：

  • 判别式模型：直接对 \(P(c|x)\) 建模，比如决策树、BP神经网络、SVM
  • 生成式模型：先对联合概率分布 P(c,x) 建模，再由 \(P(c|x) = \frac{P(x,c)}{P(x)}\) 求得，如贝叶斯分类器
\[ P(c|x) = \frac{P(x,c)}{P(x)} = \frac{P(c)P(x|c)}{P(x)} \]
  • \(P(c)\): 先验概率（prior），表示样本空间中各类样本所占比例，可通过各类样本出现的频率估计（大数定律）
  • \(P(x|c)\): 样本相对于类标记的类条件概率（似然）
  • \(P(x)\): 证据（evidence）因子，与类别无关

极大似然估计（MLE）⭐

估计类条件概率思路：先假设某种概率分布形式，再基于训练样例对参数进行估计

假定关于类别c的条件概率 \(P(x|c)\) 具有确定的概率分布形式，且被参数 \(\theta_c\) 唯一确定，则任务就是利用训练集D来估计参数 \(\theta_c\)

令 \(D_c\) 表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的，则参数 \(\theta_c\)对于数据集 \(D_c\) 的似然是

\[ P(D_c|\theta_c) = \Pi_{x\in D_c}P(x|\theta_c) \]

连乘易造成下溢，使用对数似然：

\[ LL(\theta_c) = \text{log}P(D_c|\theta_c) = \Sigma_{x\in D_c}\text{log}P(x|\theta_c) \]

所以 \(\theta_c\) 的极大似然估计为 \(\hat{\theta}_c = \text{arg max}_{\theta_c} LL(\theta_c)\)

朴素贝叶斯分类器⭐

属性条件独立性假设：
由于所有属性上的联合概率难以从有限训练样本估计获得，所以假设每个属性独立第对分类结果发生影响。基于此假设，P(c|x)可重写为

\[ P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{P(x)}\Pi^d_{i=1}P(x_i|c) \]

先验概率估计：\(P(c) = \frac{|D_c|}{|D|}\)

条件概率 \(P(x_i|c)\)的估计：

  • 对离散属性：\(P(x_i|c) = \frac{|D_{c,x_i}|}{|D_c|}\)， \(D_{c,x_i}\) 表示 \(D_c\) 在第i个属性上取值为 x_i 的样本组成的集合
  • 对连续属性：假定 \(p(x_i|c)~\mathcal{N}(\mu_{c,i}, \sigma^2_{c,i})\)
\[ p(x_i|c) = \frac{1}{\sqrt{2\pi}\sigma_{c,i}}\text{exp}(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}}) \]

拉普拉斯修正

为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”（因为概率连乘）， 在估计概率值时通常要进行"平滑" (smoothing) ，常用"拉普拉斯修正" (Laplacian correctio). 具体来说：
令 N 表示训练集 D 中可能得类别数，\(N_i\) 表示第 i 个属性，则 \(P(c)\) 和 \(P(x_i|c)\) 被修正为

\[ \hat{P}(c) = \frac{|D_c| +1}{|D|+N}，\hat{P}(x_i|c) = \frac{|D_{c,x_i}| +1}{|D_c|+N_i} \]
  • 优点：拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验(prior) 的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值
  • 问题：这里假设了属性值与类别的均匀分布，这是额外引入的bias

实际使用

  • 若对预测速度要求高：预计算所有概率估值，使用时“查表”
  • 若数据更替频繁，不进行任何训练，收到预测请求时再估值（lazy learning）
  • 若数据不断增加：基于现有估值，对新样本涉及的概率估值进行修正（增量学习incremental learning）

半朴素贝叶斯分类器

对属性条件独立性假设进行一定程度的放松，适当考虑一部分属性问的相互依赖信息

  • ODE(One-Dependent Estimator)独依赖估计：假设每个属性在类别外最多仅依赖一个其他属性
    • SPODE(Super-Parent ODE)：设所有属性都依赖于同一属性，称为“超父”，然后通过交叉验证等模型选择方法来确定超父属性
    • TAN(Tree Augment naive Bayes)：以属性间的条件”互信息”(mutual information)为边的权重，构建完全图，再利用最大带权生成树算法，仅保留强相关属性间的依赖性
  • AODE(Averaged One-Dependent Estimator)：尝试将每个属性作为超父构建 SPODE。 将拥有足够训练数据支撑的 SPODE 集成起来作为最终结果

贝叶斯网络✍

  • 贝叶斯网络/信念网，借助有向无环图DAG来刻画属性之间的依赖关系，并使用条件概率表（Conditional Probability Table）来描述属性的联合概率分布
  • 由结构G和参数 \(\Theta\) 两部分构成：\(B=<G,\Theta>\)，若两个属性有直接依赖关系，则它们由一条边连接起来
  • 参数 \(\Theta\) 描述依赖关系：设属性x_i在G中父节点为\(\pi_i\)， 则 \(\Theta\)包含了每个属性的条件概率表 \(\theta_{x_i} = P_B(x_i|\pi_i)\)
  • 概率图模型中的无向图模型：马尔可夫网

结构

叶斯网结构有效地表达了属性间的条件独立立性。给定父结点集，贝叶斯网假设每个属性与它后裔属独立，于是B=将属性 \(x_1,...,x_d\)的联合概率分布定义为

\[ P_B(x_1,x_2,\dots,x_d)=\Pi_{i=1}^dP_B(x_i|\pi_i)=\Pi_{i=1}^{d}\theta_{x_i|\pi_i} \]

三个变量间依赖关系：

alt text

V型结构 \(x_4\)未知，则 \(x_1,x_2\)独立，称为边际独立。在同父结构中 \(x_3,x_4\)和顺序结构中y,z不边际独立，

  • 为了分析有向图中变量间的条件独立性，可使用"有向分离" (D-separation). 我们先把有向图转变为一个无向图（道德图）:

  • 找出所有V型结构，在V型结构的两个父节点之间加上一条无向边（道德化）

  • 将所有有向边改为无向边

若变量x,y能被变量集合z分开（有向分离），即从道德图中将z去除后，x,y分属两个连通分支

alt text

学习

现实应用中我们往往并不知晓网络结构，于是，贝叶斯网学习的首要任务就是根据训练数据集来找出结构最"恰当"的贝叶斯网

  • 可用评分搜索来解决：定义评分函数来评估贝叶斯网与训练数据的契合程度，常用评分函数通常基于信息论准则，比如最小描述长度（MDL）

  • 搜索最优贝叶斯网络结构是NP难问题

推断

贝叶斯网训练好之后就能用来回答"查询" (query)，即通过一些属性变量 的观测值来推测其他属性变量的取值，已知属性变量的观测值称为“证据”。

  • 精确推断：直接根据贝叶斯网定义的联合概率分布来精确计算后验概率（NP-hard）
  • 近似推断：降低精度要求，在有限时间内求得近似解
    • 吉布斯采样

吉布斯采样

alt text

  • 吉布斯采样算法先随机产生一个与证据 \(E=e\) 一致的样本 \(q_0\) 作为初始点
  • 然后每步从当前样本出发产生下一个样本：具体来说，在第t次采样中，算法先假设 \(q^t = q^{t-1}\)，
  • 然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网B和其他变量的当前取值(即 Z= z) 计算获得

  • 假定经T次采样得到的与 q 一致的样本共有 \(n_q\) 个，则可近似估算出后验概

    \[ P(Q=q|E=e)\approx \frac{n_q}{T} \]

吉布斯采用过程是一个马尔科夫链，通常需要很长时间才能趋于平稳分布，因此收敛速度较慢。若贝叶斯网中存在极端概率 "0"或"1" 则不能保证马尔可夫链存在平稳分布，此时吉布斯采样会给出错误的估计结果.

EM算法（期望最大化算法）

未观测到的属性值（变量）为“隐变量”。 EM(Expection-Maximization)算法是常用的估计参数隐变量的利器

令X表示已观测变量集，Z表示隐变量集，\(\Theta\) 表示模型参数，若欲对 \(\Theta\) 做极大似然估计，则应极大化对数似然

\[ LL(\Theta|X,Z) = \text{ln}P(X,Z|\Theta) \]

然而由于Z是隐变量，上式无法直接求解。此时我们可通过对Z计算期望，来最大化已观测数据的对数“边际似然”（marginal likelihood）

\[ LL(\Theta|X) = \text{ln}P(X|\Theta) = \Sigma_Z\text{ln} P(X,Z|\Theta) \]
  • 基本想法：若参数 \(\Theta\) 己知则可根据训练数据推断出最优隐变量Z的值 (E 步) ;反之，若Z的值已知，则可方便地对参数 \(\Theta\) 做极大似然估计(M步)

以初始值 \(\Theta_0\) 为起点，迭代执行以下步骤直至收敛：

  • E步：基于 \(\Theta^t\) 推断隐变量Z的期望，记为 \(Z^t\)
  • M步：基于已观测变量X和 \(Z^t\) 对参数 \(\Theta\) 做极大似然估计，记为 \(\Theta^{t+1}\)

Comments