[读书笔记]《西瓜书》第七章贝叶斯分类器

December 9, 2020

6481 29 minutes and 27 seconds

第七章贝叶斯分类器

有了上一篇博文中关于贝叶斯派和频率派的认识之后，我们知道了贝叶斯派的主要两个主要方式，一是推断Inference，二是预测Prediction。而西瓜书中在这一章——贝叶斯分类器中就涉及了这两方面的内容，所以接下来咱们看看西瓜书中都涉及到了哪些内容？

7.1 贝叶斯决策论

贝叶斯决策论（Bayesian decision theory）

贝叶斯决策论是概率框架下实施决策的基本方法

例如：

对分类任务来说，在所有相关概率都已知的理想情况下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记

PS：在前面的贝叶斯线性回归中我们已经感受到了贝叶斯决策论的魅力，可以这么说导致其最近这几年发展远不如概率学派的一个主要原因就是其计算条件过于苛刻并且计算过于复杂~

多分类任务

借助这个例子来讲解其基本原理

定义

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

任务本质

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

公式表示： $$ R(h)=\mathbb{E}_x[R(h(\boldsymbol{x})|\boldsymbol{x})] $$

贝叶斯判定准则（Bayes decision rule）

为最小化总体风险，只需在每个样本上选择哪个能使条件风险 $R(c|\boldsymbol{x})$ 最小的类别标记

公式表示：

$$ h^*(\boldsymbol{x})=\underset{c\in\mathcal{Y}}{\arg\min}R(c|\boldsymbol{x}) $$

$h^*$ 称之为贝叶斯最优化分类器(Bayes optimal classifier)
$R(h^*)$ 称之为贝叶斯风险(Bayes risk)

则 $1-R(h^*)$ 反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

即对每个样本 $\boldsymbol{x}$，若 $h$ 能最小化条件风险 $R(h(\boldsymbol{x})|\boldsymbol{x})$，则总体风险 $R(h)$ 也将被最小化

将 $\lambda_{ij}$ 定义为 $0-1$ 损失函数时 $$ \lambda_{ij} = \begin{cases} & 0, & \quad \text{if} \quad i = j; \\
& 1, & \quad \text{otherwise} \end{cases} $$ 条件风险变为：$R(c|\boldsymbol{x}) = 1-P(c|\boldsymbol{x})$

此时的贝叶斯最优化分类器变为 $$ h^*(\boldsymbol{x})=\underset{c\in\mathcal{Y}}{\arg\max}P(c|\boldsymbol{x}) $$

PS：即对每个样本 $\boldsymbol{x}$ ，选择能使后验概率 $P(c|\boldsymbol{x})$ 最大的类别标记，这个结果有没有老眼熟了~

关键是如何获得后验概率 $P(c|\boldsymbol{x})$

PS：这里引入了新的一种对于机器学习模型的分类方式

判别式模型（discriminative models）

给定 $\boldsymbol{x}$，可通过直接建模 $P(c|\boldsymbol{x})$ 来预测 $c$

例如：

决策树、BP神经网络、支持向量机等模型

生成式模型（generative models）

通过联合概率分布 $P(\boldsymbol{x},c)$ 建模，然后再由此获取 $P(c|\boldsymbol{x})$

借助贝叶斯定理我们能有如下公式： $$ P(c|\boldsymbol{x})=\frac{P(\boldsymbol{x}, c)}{P(\boldsymbol{x})}=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})} $$

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

总结：

对于给定的样本 $\boldsymbol{x}$，证据因子 $P(\boldsymbol{x})$ 与类标记无关

借助贝叶斯公式，估计 $P(c|\boldsymbol{x})$ 的问题就转化为如何基于训练数据 $D$ 来估计先验 $P(c)$ 和似然 $P(\boldsymbol{x}|c)$

对于类条件概率 $P(\boldsymbol{x}|c)$，由于它涉及关于 $\boldsymbol{x}$ 所有属性的联合概率，因此直接使用频率来估计 $P(\boldsymbol{x}|c)$ 显然是不行，因为“未被观测到”和“出现概率为零”是不同的

例如：

贝叶斯分类器

7.2 极大似然估计

问题来源

如何估计类条件概率（似然）—— $P(\boldsymbol{x}|c)$ ？

基本策略

先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计
具体步骤
- 记关于类别 $c$ 的类条件概率为 $P(\boldsymbol{x}|c)$
- 假设 $P(\boldsymbol{x}|c)$ 具有确定的形式并且被参数向量 $\theta_c$ 唯一确定
- 利用训练集 $D$ 估计参数 $\theta_c$

概率模型训练过程就是参数估计过程

两大学派

PS：这一部分在前一篇博文中做了详细的整理

频率主义学派（Frequentist）

核心想法：

参数虽然未知，但却是客观存在的固定值，因此，可以通过优化似然函数等准则来确定参数值

贝叶斯学派（Bayesian）

核心想法：

参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观察到的舒俱来计算参数的后验分布

极大似然估计(Maximum Likelihood Estimation，简称MLE)

本质：

根据数据采样来估计概率分布参数

前提假设：

训练集中的样本是独立同分布的

因此估计结果的准确性严重依赖与所假设的概率分布形式是否符合潜在的真实数据分布

公式表示：

$$ P(D_c|\boldsymbol{\theta}_c) = \prod_{\boldsymbol{x} \in D_c} P(\boldsymbol{x}|\boldsymbol{\theta}_c) $$

$D_c$ 表示训练集中第 $c$ 类样本组成的集合
表示参数 $\boldsymbol{\theta}_c$ 对于数据集 $D_c$ 的似然

对数似然（log-likelihood）：

连乘操作易产生下溢（引入的原因） $$ LL(\theta_c) = \sum_{\boldsymbol{x} \in D_c} \log P(\boldsymbol{x}|\boldsymbol{\theta}_c) $$

此时的参数 $\boldsymbol{\theta}_c$ 的极大似然估计 $\hat{\boldsymbol{\theta}}_c$ $$ \hat{\boldsymbol{\theta}}_c= \underset{\theta_c}{\arg\max}LL(\boldsymbol{\theta}_c) $$

如何直观理解极大似然估计?

极大似然估计是试图在 $\theta_c$ 所有可能的取值中，找到一个能使数据出现的可能性最大的值

PS：结合西瓜书和花书，我们其实可以明白一件事，并不是说MLE和MAP就是区分频率派和贝叶斯派的方法，而在两者的计算过程中都会引入MLE的方式~

7.3 朴素贝叶斯分类器

问题来源

基于贝叶斯公式来估计后验概率 $P(c|\boldsymbol{x})$ 的相当困难

原因

类条件概率 $P(\boldsymbol{x}|c)$ 是所有属性上的联合概率，难以从有限的训练样本直接估计得到
在计算上会遭遇组合爆炸问题
在数据上会遭遇样本稀疏问题

属性数越多，问题越严重

朴素贝叶斯分类器（naive Bayes classifier）

假设前提

属性条件独立性假设（attribute conditional independence assumption）

即假设所有属性相互独立
换言之，假设每个属性独立地对分类结果发生影响

核心内容

此时的后验概率公式可以写为 $$ P(c|\boldsymbol{x})=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})}=\frac{P(c)}{P(\boldsymbol{x})}\prod_{i=1}^d P(x_i|c) $$

$d$ 为属性个数
$x_i$ 为属性取值

即属性相互独立： $$ P(\boldsymbol{x}|c)=\prod_{i=1}^dP(x_i|c) $$ 对于所有类别来说 $P(\boldsymbol{x})$ 相同，因此基于贝叶斯判定准则有 $$ h_{nb}(\boldsymbol{x})=\underset{c \in \mathcal{Y}}{\arg\max}P(c)\prod_{i=1}^dP(x_i|c) $$

PS：看似公式很难，但是其实本质很简单~

西瓜书中是这么说的：

朴素贝叶斯分类器的训练过程就是基于训练集 $D$ 来估计类先验概率 $P(c)$ ，并为每个属性估计类条件概率 $P(x_i|c)$

其实公式看着复杂，但是借助书中的例子很容易就看明白了~

类先验概率

$$ P(c)=\frac{|D_c|}{|D|} $$

其中 $D_c$ 表示训练集 $D$ 中第 $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)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp\left( - \frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2} \right) $$ $\mu_{c,i}$ 和 $\sigma_{c,i}^2$ 分别是第 $c$ 类样本在第 $i$ 个属性上取值的均值和方差

并且假设 $p(x_i|c)\sim \mathcal{N}(\mu_{c,i},\sigma_{c,i}^2)$

PS：这里的假设高斯分布并不是绝对的，分布的选取是源自于背景知识的，通常选取高斯分布是因为高斯分布是普遍现象，而且如果选取其他分布，你可能也会产生疑问为啥会选取这个分布？

西瓜例子（其实结合例子看，就会发现这个其实很简单）

西瓜数据集3.0

假设测试例

训练朴素贝叶斯分类器

估计类先验概率 $P(c)$

$P(好瓜 = 是) = \frac{8}{17} \approx 0.471$
$P(好瓜=否) = \frac{9}{17} \approx 0.529$

估计每个属性的类条件概率 $P(x_i|c)$

离散型

连续型

结论推测

如果某个属性取值在训练集上出现的次数为零如何处理？

因为朴素贝叶斯分类器是连乘式，因此会导致其他属性携带的信息会被某个训练集中未出现的属性值“抹去”

前面其实已经提到了，“未被观测到”和“出现概率为零”是不同的，所以需要引入平滑处理

拉普拉斯修正（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}$

7.4 半朴素贝叶斯分类器

半朴素贝叶斯分类器（semi-naive Bayes classifiers）

核心问题：

现实任务中属性条件独立性假设难以成立

解决方式：

适当考虑一部分属性间的相互依赖信息

相对于朴素贝叶斯分类器，对属性条件独立性假设进行了一定程度的放松

贝叶斯分类器（完全联合概率计算）
朴素贝叶斯分类器（完全独立概率计算）

基本策略：

独依赖估计（One-Dependent Estimator，简称 ODE）

基本思想：假设每个属性在类别之外最多仅依赖于一个其他属性

公式 $$ P(c|\boldsymbol{x}) \propto P(c)\prod_{i=1}^dP(x_i|c,pa_i) $$ 其中 $pa_i$ 为属性 $x_i$ 所依赖的属性，称为 $x_i$ 的父属性

基本形式

PS：其实这里不借助西瓜书的内容展开，也能想到关键性问题，如何确定每个属性的父属性呢？

如何确定每个属性的父属性？

最直接暴力的方式：

假设所有属性都依赖于同一个属性，称为“超父”（super-parent）

两种策略：

SPODE（Super-Parent ODE）：

通过交叉验证等模型选择方法来确定超父属性

AODE（Averaged ODE）：

一种基于集成学习机制、更为强大的独依赖分类器

尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果 $$ P(c|\boldsymbol{x}) \propto \sum_{ \underset{|D_{x_i}| \ge m'}{i=1} }^d P(c,x_i)\prod_{j=1}^dP(x_j|c,x_i) $$ $D_{x_i}$ 是在第 $i$ 个属性上取值为 $x_i$ 的样本的集合，$m'$ 为人为设定的阈值常数（常用30）

与朴素贝叶斯分类器同样是“计数”过程

类先验概率 $$ \hat{P}(c,x_i) = \frac{|D_{c,x_i}| + 1}{|D| + N \times N_i} $$ 类条件概率 $$ \hat{P}(x_j|c,x_i) = \frac{|D_{c,x_i,x_j}| + 1}{|D_c,x_i| + N_j} $$

类似朴素贝叶斯分类器一样需要进行拉普拉斯修正

参数说明

$N$ 是 $D$ 中可能的类别数
$N_i$ 是第 $i$ 个属性可能的取值数
$D_{c,x_i}$ 是类别为 $c$ 且在第 $i$ 个属性上取值为 $x_i$ 的样本集合
$D_{c,x_i,x_j}$ 是类别为 $c$ 且在第 $i$ 个和第 $j$ 个属性上取值分别为 $x_i$ 和 $x_j$ 的样本集合

TAN（Tree Augmented naive Bayes）：

在最大带权生成树（maximum weighted spanning tree）算法的基础上，将属性间的依赖关系整理成树形结果
步骤
- 计算任意两个属性之间的条件互信息（conditional mutual information）
$$ I(x_i,x_j|y)=\sum_{x_i,xj;c \in \mathcal{Y}} P(x_i,x_j|c)\log \frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)} $$

PS：决策树铺垫中虽然没有提及，但是相互熵即KL散度也涉及到了互信息
- 以属性为结点构建完全图，任意两个结点之间边的权重设为
- 构建此完全图的最大带权生成树，挑选根变量，将边置为有向
- 加入类别结点 $y$ ，增加从 $y$ 到每个属性的有向边
条件互信息 $\mathbf{I}(x_i,x_j|y)$ 刻画了属性 $x_i$ 和 $x_j$ 在已知类别情况下的相关性，因此，通过最大生成树算法，TAN 实际上仅保留了强相关属性之间的依赖性

7.5 贝叶斯网

概念

贝叶斯网（Bayesian network）亦称 “信念网”（belief network）

借助有向无环图（Directed Acyclic Graph，简称DAG）来刻画属性之间的依赖关系
使用条件概率表（Conditional Probability Table，简称 CPT）来描述属性的联合概率分布

贝叶斯网定义为 $B=<G,\Theta>$

结构 $G$ ：一个有向无环图，其每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来
参数 $\Theta$：参数 $\Theta$ 定量描述这种依赖关系，假设属性 $x_i$ 在 $G$ 中的父节点为 $\pi_i$，则 $\Theta$ 包含了每个属性的条件概率表 $\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)$

如何体现属性间的关系？

贝叶斯网结构有效表达了属性间的条件独立性

解释

给定父节点集，贝叶斯网假设每个属性与它的非后裔属性独立

$B=<G,\Theta>$ 将属性 $x_1,x_2,…,x_d$ 的联合概率分布定义为 $P_B(x_1,x_2,…,x_d)=\prod_{i=1}^dP_B(x_i|\pi_i)=\prod_{i=1}^d\theta_{x_i|\pi_i}$

举例

$$ P(x_1,x_2,x_3,x_4,x_5) = P(x_1)P(x_2)P(x_3|x_1)P(x_4|x_1,x_2)P(x_5|x_2) $$ 说明

$x_3$ 和 $x_4$ 在给定 $x_1$ 的取值时独立，记为 $x_3 \bot x_4 | x_1$
$x_4$ 和 $x_5$ 在给定 $x_2$ 的取值时独立，记为 $x_4 \bot x_5 | x_2$
上图的几个属性的联合概率分布为

典型结构

同父结构

给定父节点的取值，则两个子结点条件独立

顺序结构

给定中间结点的取值，则前后结点的条件独立

V型结构

“冲撞”结构
若给定子结点的取值，则两个父节点一定不条件独立；若子结点取值完全未知，则两个父节点是条件独立
这种独立性称为“边际独立性”（marginal independence）

如何分析有向图中变量间的条件独立性？

方法

将有向图转变为一个无向图，产生的无向图称为“道德图”（moral graph）——有向分离（D-separation）
孩子的父母应建立牢靠的关系，否则是不道德的

步骤

找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无向边——令父节点相连的过程称为道德化（moralization）
将所有有向边改为无向边

举例

所有的条件独立关系：$x_3 \bot x_4 | x_1,x_4 \bot x_5 | x_2,x_3 \bot x_2 | x_1,x_3 \bot x_5 | x_1,x_3 \bot x_5 | x_2$

学习

两种类型的学习任务

网络结构
条件概率

前面介绍的贝叶斯网络都是假设网络结构已知，但现实中往往不知晓网络结构，因此贝叶斯网络学习的首要任务就是根据训练集找出结构最“恰当”的贝叶斯网

评分搜索

评分函数（score function）

体现的是算法的归纳偏好
常用评分函数基于信息论准则
- 将学习问题看作一个数据压缩任务
- 找到一个能以最短编码长度描述训练数据的模型

以此来评估贝叶斯网与训练数据的契合程度，基于这个评分函数来寻找结构最优的贝叶斯网

这里所说的最短编码长度是一种：综合编码长度

描述模型自身所需的编码位数

使用该模型描述数据所需的编码位数

又称最小描述长度（Minimal Description Length，简称MDL）准则

最小描述长度准则

评分函数公式： $$ s(B|D)=f(\theta)|B|-LL(B|D) $$

$|B|$ 是贝叶斯网的参数个数
$f(\theta)$ 表示描述每个参数 $\theta$ 所需的编码位数

这是第一项：计算编码贝叶斯网 $B$ 所需的编码位数

统计学习角度：结构风险

贝叶斯网 $B$ 的对数似然：$LL(B|D)=\sum_{i=1}^m \log P_B(\boldsymbol{x}_i)$

这是第二项：计算 $B$ 所对应的概率分布 $P$ 对 $D$ 描述得有多好

统计学习角度：经验风险

几种变形

AIC（Akaike Information Criterion）
- $f(\theta)=1$，即每个参数用1编码位描述
- $\text{AIC}(B|D)=|B|-LL(B|D)$
BIC（Bayesian Information Criterion）
- $f(\theta)=\frac{1}{2}\log m$，即每个参数用 $\frac{1}{2}\log m$ 编码位描述
- $\text{BIC}(B|D)=\frac{1}{2}\log m |B| - LL(B|D)$
MLE（Maximum Likelihood Estimation ）
- $f(\theta)=0$，即不计算对网络进行编码的长度
- $\text{MLE}(B|D)=-LL(B|D)$

若网络结构 $G$ 固定

评分函数 $s(B|D)$ 第一项为常数
最小化 $s(B|D)$ 等价于对参数 $\Theta$ 的极大似然估计
参数 $\theta_{x_i|\pi_i}$ 能直接在训练数据 $D$ 上通过经验估计获得

问题转化为：如何找到最合适的网络结构？

一种是贪心算法，例如从某个网络结构出发，每次调整一条边（增加、删除或调整方向），直到评分函数值不再降低为止

第二种是通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构

推断

分类结构

精确推断
近似推断
- 确定性推断
  - 基于近似的变分推理（Variational Inference，简称VI）
- 随机性推断
  - 基于采样的马尔可夫链蒙特卡罗（Markov Chain & Monte Carlo，简称MCMC）
    - MH算法（Metropolis-Hasting）
    - 吉布斯采样（Gibbs sampling）

吉布斯采样（Gibbs sampling）

本质

吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据 $\boldsymbol{E}=\boldsymbol{e}$ 一致的子空间进行“随机漫步”（random walk）

关键信息点：

吉布斯采样过程中每一步仅依赖于前一步的状态，这是一个“马尔科夫链”（Markov chain）

对于吉布斯采样来说，马尔科夫链在 $t\rightarrow\infty$ 时收敛的平稳分布恰好是 $P(\boldsymbol{Q}|\boldsymbol{E}=\boldsymbol{e})$

流程

参数说明
- $\boldsymbol{Q}=\{Q_1,Q_2,…Q_n\}$ 表示待查询变量
- $\boldsymbol{E}=\{E_1,E_2,…,E_n\}$ 表示证据变量
- $\boldsymbol{e}=\{e_1,e_2,…,e_k\}$ 表示证据变量的取值
- $\boldsymbol{q}^t$ 表示第 $t$ 次待查询变量的取值 $\boldsymbol{q}=\{q_1,q_2,…,q_n\}$
步骤说明
- 先随机产生一个与证据 $\boldsymbol{E}=\boldsymbol{e}$ 一致的样本 $\boldsymbol{q}^0$ 作为起始点，然后每步从当前样本出发产生下一个样本
- 具体来说，在第 $t$ 次采样中，算法先假设 $\boldsymbol{q}^t=\boldsymbol{q}^{t-1}$，然后对非证据变量逐个进行采样改变其取值
- 采样概率根据贝叶斯 $B$ 和其他变量的当前取值（即 $\boldsymbol{Z}=z$）计算获得
结论说明
- 假定经过 $T$ 次采样得到的与 $\boldsymbol{q}$ 一致的样本共有 $n_q$ 个，则可以近似估算出后验概率
- $P(\boldsymbol{{Q=q|E=e}}) \simeq \frac{n_q}{T}$

注意

由于马尔科夫链需要一个较长时间才能趋于平稳的分布，因此吉布斯采样算法的收敛速度较慢
若贝叶斯网中存在极端概率"0"或"1"，则不能保证马尔科夫链存在平稳分布

7.6 EM算法

问题的由来

现实现象中样本所有属性的值并非都已被观测到的，即训练样本是“完整”的

引入了部分可观测的知识点~