C07. Bayes 分类器
7.1 Bayes 决策论
Bayes 决策论是概率框架下实施决策的基本方法。详细描述还可参考 [^Duda,2003] Ch02
前提条件
- $N$ 种类别标记，即 $\mathcal{Y}={c_1,\cdots,c_N}$
- $\lambda_{ij}$ 是将一个真实标记为 $c_j$ 的样本分类为 $c_i$ 所产生的损失
- 条件风险：$R ( c_i|\text{x} ) =\sum_{j=1}^N \lambda_{ij} P ( c_j|\text{x} )$
- 基于后验概率 $P ( c_i|\text{x} )$ 获得，表示样本 $\text{x}$ 分类为 $c_i$ 所产生的期望损失
优化目标
- 寻找一个判定准则 $h: \mathcal{X}\rightarrow\mathcal{Y}$ 最小化总体风险 $R ( h ) =\mathbb{E}[R ( h ( \text{x} )) |\text{x}]$
- 每个样本上选择使条件风险最小的类别标记，即 $h^{*} ( \text{x} ) =\arg\min_{c\in\mathcal{Y}} R ( c|\text{x} )$
- $h^*$ 称为 Bayes 最优分类器
- $R ( h^* )$ 称为 Bayes 风险
- $1- R ( h^* )$ 反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限
实际案例
- 目标是最小化分类错误率
- 误判损失 $\lambda_{ij}=\begin{cases}0,&&i=j;\1,&&\text{otherwise.}\end{cases}$
- 条件风险 $R ( c|\text{x} ) =1-P ( c|\text{x} )$
- 最小化分类错误率的 Bayes 最优分类器 $h^{*} ( \text{x} ) =\arg\max_{c\in\mathcal{Y}} P ( c|\text{x} )$
- 即对每个样本 $\text{x}$ 选择能使后验概率 $P ( c|\text{x} )$ 最大的类别标记
机器学习基于有限训练样本集估计后验概率的方法
- 判别式模型：给定样本 $\text{x}$，直接建模 $P ( c|\text{x} )$ 预测类别 $c$
- 决策树
- BP 神经网络
- 支持向量机
- 生成式模型：先对联合概率分布 $P ( c,\text{x} )$ 建模，然后再计算 $P ( c|\text{x} )$ 预测类别 $c$
- 类别先验概率 $P ( c )$
- 表达了样本空间中各类样本所占的比例
- 当训练集包含充足的独立同分布样本时，$P ( c )$ 可以通过各类样本出现的频率来进行估计
- 类别条件概率 $P ( \text{x}|c )$，也叫似然函数 ( 参数 $\text{w}$ 的函数 )
- 涉及到关于 $\text{x}$ 的所有属性的联合概率，因此直接根据样本出现的频率来估计不可行
- 估计类别条件概率常常基于参数估计的方法
- 类别条件概率不是参数 $\text{w}$ 的概率，因此它是关于参数的似然函数
- 证据因子 $P ( \text{x} )$，用于归一化后验概率
- 对于给定的样本 $\text{x}$，证据因子与类标记无关
- 类别先验概率 $P ( c )$
$$
P ( c|\text{x} ) =\frac{P ( \text{x},c )}{P ( \text{x} )}=\frac{P ( c ) P ( \text{x}|c )}{P ( \text{x} )}
$$
7.2 极大似然估计
估计类条件概率的常用策略：先假定其具有某种确定的概率分布形式，然后基于训练样本对概率分布的参数进行估计
- 优点：参数化方法使得类条件概率估计变得相对简单
- 缺点：估计结果的正确性严重依赖假设的概率分布形式与真实数据分布之间的相似性，错误的估计会导致谬误的结果
概率模型的训练过程就是参数估计的过程，参数估计的两种方案：
- 频率学派认为参数虽然未知，但是客观存在固定值，通过优化似然函数等准则来确定参数的值
- 极大似然估计就是根据数据采样来估计概率分布参数的经典方法
- Bayes 学派认为参数是未观察到的随机变量，其本身也可以有概率分布，
- 因此可以假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布
极大似然估计 ( Maximum Likelihood Estimation, MLE )
- 前提条件
- $D_c$ 表示训练集 $D$ 中第 $c$ 类样本组成的集合
- 假设样本都是独立同分布的
- $D_c$ 表示训练集 $D$ 中第 $c$ 类样本组成的集合
- 计算过程
- 参数 $\boldsymbol{\theta}c$ 对于数据 $D_c$ 的似然函数 $P ( D_c|\boldsymbol{\theta_c} ) =\prod{\text{x}\in\D_c} P ( \text{x}|\boldsymbol{\lambda}_c )$
- 对 $\boldsymbol{\theta}_c$ 进行极大似然估计，就是去寻找能最大化似然函数 $P ( D_c|\boldsymbol{\theta_c} )$ 的参数值 $\hat{\boldsymbol{\theta}}_c$
- 对数似然函数 $LL ( \boldsymbol{\theta}_c )$
- 参数 $\boldsymbol{\theta}_c$ 的极大似然估计 $\hat{\boldsymbol{\theta}}c=\arg\max{\boldsymbol{\theta}_c} LL ( \boldsymbol{\theta}_c )$
- 参数 $\boldsymbol{\theta}c$ 对于数据 $D_c$ 的似然函数 $P ( D_c|\boldsymbol{\theta_c} ) =\prod{\text{x}\in\D_c} P ( \text{x}|\boldsymbol{\lambda}_c )$
$$
\begin{aligned}
LL ( \boldsymbol{\theta}_c )
&=\ln P ( D_c|\boldsymbol{\theta}c ) \
&=\sum{\text{x}\in D_c}\ln P ( \text{x}|\boldsymbol{\theta}_c )
\end{aligned}
$$
- 实际案例：正态分布
- 概率密度函数 $p ( \text{x}|c ) \sim\mathcal{N} ( \boldsymbol{\mu}_c,\boldsymbol{\sigma}_c^2 )$
- 参数的极大似然估计
- 极大似然估计的正态分布的均值就是样本均值
- 极大似然估计的正态分布的方差就是 $( \text{x}-\hat{\boldsymbol{\mu}}_c ) ( \text{x}-\hat{\boldsymbol{\mu}}_c )^T$ 的均值
$$
\begin{aligned}
\hat{\boldsymbol{\mu}}c&=\frac1{|D_c|}\sum{\text{x}\in D_c} \text{x}\
\hat{\boldsymbol{\sigma}}c^2&=\frac1{|D_c|}\sum{\text{x}\in D_c} ( \text{x}-\hat{\boldsymbol{\mu}}_c ) ( \text{x}-\hat{\boldsymbol{\mu}}_c )^T
\end{aligned}
$$
7.3 朴素 Bayes 分类器
基于 Bayes 公式来估计后验概率 $P ( c|\text{x} )$ 需要面对类条件概率密度 $p ( \text{x}|c )$ 在所有属性上的联合概率很难从有限的训练样本中直接估计得到，因此朴素 Bayes 分类器采用「属性条件独立性假设」来避免求联合概率问题。
基于属性条件独立性假设，后验概率分布表示为
- $d$ 为属性的数目
- $x_i$ 为 $\text{x}$ 在第 $i$ 个属性上的取值
$$
P ( c|\text{x} ) =\frac{P ( c ) P ( \text{x}|c )}{P ( \text{x} )}=\frac{P ( c )}{P ( \text{x} )}\prod_{i=1}^d P ( \text{x}_i|c )
$$
因为所有类别的 $P ( \text{x} )$ 相同，所以朴素 Bayes 分类器的表达式
$$
h_{nb} ( \text{x} ) =\arg\max_{c\in\mathcal{Y}} P ( c ) \prod_{i=1}^d P ( \text{x}_i|c )
$$
朴素 Bayes 分类器的估计过程
- 估计类先验概率 $P ( c ) =\frac{|D_c|}{|D|}$
- 估计每个属性的条件概率 $P ( x_i|c )$
- 离散属性估计 $P ( x_i|c ) =\frac{|D_{c,x_i}|}{|D_c|}$
- 连续属性估计
- 假定 $p ( x_i|c ) \sim\mathcal{N} ( \mu_{c,i},\sigma_{c,i}^2 )$
- 得出 $P ( x_i|c ) =\frac1{\sqrt{2\pi}\sigma_{c,i}}\exp{-\frac{( x_i-\mu_{c,i} )^2}{2\sigma_{c,i}^2}}
- 估计概率时，为了避免出现概率为 0 的情况 ( 训练集中没有出现的属性值 )，可以使用「平滑」技术
- 先验概率平滑 $P ( c ) =\frac{|D_c|+\lambda}{|D|+N\lambda}$
- 每个属性的条件概率平滑 $P ( x_i|c ) =\frac{|D_{c,x_i}|+\lambda}{|D_c|+N_i\lambda}$
- $\lambda=1$ 时就是常用的「Laplace 修正」
7.4 半朴素 Bayes 分类器
基本思想：建模时考虑部分重要的依赖关系，既可避免计算联合概率，又可兼顾部分重要的依赖关系
「独依赖估计」( One-Dependent Estimator, ODE ) 是半朴素 Bayes 分类器常用策略，假设每个属性在类别之外最多仅依赖于一个其他属性
- $pa_i$ 为属性 $x_i$ 所依赖的属性，称为 $x_i$ 的父属性
$$
P ( c|\text{x} ) \propto P ( c ) \prod_{i=1}^d P ( x_i|c,pa_i )
$$
「独依赖估计」的策略 ( Fig 7.1 不同分类器的属性依赖关系 )
- SPODE ( Super-Parent ODE ) ：所有的属性都依赖于同一个属性，被依赖的属性称为「超父」
- TAN ( Tree Augmented Naive Bayes ) ：在最大带权生成树算法的基础上，通过以下步骤将属性间的依赖关系约简为树形结构
- 计算任意两个属性之间的条件互信息
- $I ( x_i,x_j|y ) =\sum_{x_i,x_j;c\in\mathcal{Y}} P ( x_i,x_j|c ) \ln\frac{P ( x_i,x_j|c )}{P ( x_i|c ) P ( x_j|c )}$
- 条件互信息刻画了属性在已知类别情况下的相关性
- 以属性为结点构建完全图，任意两个结点之间边的权重设为条件互信息
- 构建些完全图的最大带权生成树，挑选根变量，将边转为有向
- 加入类别结点 $y$，增加从 $y$ 到每个属性的有向边
- 通过最大生成树算法，TAN 仅保留了强相关属性之间的依赖性
- 计算任意两个属性之间的条件互信息
- AODE ( Averaged One-Dependent Estimator ) ：是基于集成学习机制的独依赖分类器
- 与 SPODE 的区别是 AODE 将每个属性都作为超父来构建 SPODE
- 然后将所有的 SPODE 集成起来作为最终结果
- $D_{x_i}$ 是在第 $i$ 个属性上取值为 $x_i$ 的样本的集合
- $m’$ 为阈值常数
$$
P ( c|\text{x} ) \propto\sum_{\quad i=1\|D_{x_i}|\geq m’}^d P ( c,x_i ) \prod_{j=1}^d P ( x_j|c,x_i )
$$
7.5 Bayes 网
Bayes 网，也叫「信念网」( Belief Network )，借助有向无环图 ( Directed Acyclic Graph, DAG ) 来刻画属性之间的依赖关系，并且使用条件概率表 ( Conditional Probability Table, CPT ) 来描述属性的联合概率分布。
Bayes 网 $B$ 由结构 $G$ 和参数 $\Theta$ 两部分构成，即 $B=\langle G,\Theta\rangle$
- 网络结构 $G$ 是一个有向无环图，其每个结点对应一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来
- 参数 $\Theta$ 定量描述这种依赖关系
- 假设属性 $x_i$ 在 $G$ 中的父结点集为 $\pi_i$，则 $\Theta$ 包含了每个属性的条件概率表 $\theta_{x_i|\pi_i}=P_B ( x_i|\pi_i )$
7.5.1 Bayes 网的结构
Bayes 网的结构有效地表达了属性间的条件独立性。
( Fig 7.3 ) 显示了 Bayes 网中三个变量之间的典型依赖关系
- 「同父」结构
- 当父结点的取值确定后，两个子结点之间条件独立
- 「V 型」结构，也叫「冲撞」结构
- 当子结点的取值确定后，两个父结点之间必定不独立
- 当子结点的取值未定时，两个父结点之间条件独立
- 「顺序」结构
- 当中间结点的取值确定后，前后两个结点之间条件独立
为了分析有向图中变量之间的条件独立性，可以使用「有向分离」技术，将有向图转变为无向图
- 找出有向图中的所有 V 型结构，在 V 型结构的两个父结点之间加上一条无向边
- 令父结点相连的过程称为「道德化」( Moralization )
- 将所有有向边改成无向边
- 产生的无向图称为「道德图」( Moral Graph )
7.5.2 Bayes 网的学习过程
若网络结构已知，即属性间的依赖关系已知，则 Bayes 网的学习过程相对简单
- 对训练样本「计数」，估计出每个结点的条件概率表
现实情况下，不知晓网络结构，因此找出结构「恰当」的 Bayes 网就是首要学习任务
- 「评分搜索」是常用办法
- 定义评分函数，用于评估 Bayes 网与训练数据的契合程度
- 常用评分函数基于信息论准则
- 准则将学习问题看作一个数据压缩任务
- 准则的学习目标是找到一个能以最短编码长度描述训练数据的模型
- 选择综合编码长度 ( 包括描述网络和编码数据 ) 最短的 Bayes 网，这就是「最小描述长度」( Minimal Description Length, MDL ) 准则
- 基于这个评分函数来寻找结构最优的 Bayes 网
- 定义评分函数，用于评估 Bayes 网与训练数据的契合程度
算法过程
- 给定训练集 $D={\text{x}_1,\cdots,\text{x}_m}$
- Bayes 网 $B=\langle G,\Theta\rangle$ 在 $D$ 上的评分函数为
- $s ( B|D ) =f ( \theta ) |B|-LL ( B|D )$
- $|B|$ 是 Bayes 网的参数个数
- $f ( \theta )$ 表示描述每个参数 $\theta$ 所需要的编码位数
- $f ( \theta ) |B|$ 计算编码 $B$ 所需要的编码位数
- $LL ( B|D ) =\sum_{i = 1}^m \ln P_B ( \text{x}_i )$ 是 Bayes 网的对数似然，用于计算 $B$ 所对应的概率分布 $P_B$ 对 $D$ 描述得有多好
- 学习任务就转化为优化任务，即寻找使评分函数 $s ( B|D )$ 最小的 $B$
- 若 $f ( \theta ) =1$，即每个参数使用 1 个编码位描述，则得到 AIC ( Akaike Information Criterion ) 评分函数 $AIC ( B|D ) =|B|-LL ( B|D )$
- 若 $f ( \theta ) =\frac12\ln m$，即每个参数用 $\frac12\ln m$ 个编码位描述，则得到 BIC ( Bayesian Information Criterion ) 评分函数 $BIC ( B|D ) =|B|\frac12\ln m-LL ( B|D )$
- 若 $f ( \theta ) =0$，即不计算对网络进行编码的长度，则评分函数退化为负对数似然，学习任务退化为极大似然估计
- 若 $B=\langle G,\Theta\rangle$ 的网络结构 $G$ 固定，则 $f ( \theta ) |B|$ 为常数，则评分函数退化为负对数似然，学习任务退化为极大似然估计
- 参数 $\theta_{x_i|\pi_i}$ 能够直接在训练数据 $D$ 上通过经验估计获得
- $\theta_{x_i|\pi_i}=\hat{P_D} ( x_i|\pi_i )$
- \hat{P_D} ( \cdot ) $ 是 $D$ 上的经验分布
- 因此，只需要对网络结构进行搜索，就可以最小化评分函数 $s ( B|D )$，而修行结构的最优参数可以直接在训练集上计算得到
- $s ( B|D ) =f ( \theta ) |B|-LL ( B|D )$
- 从所有可能的网络结构空间中搜索最优 Bayes 网络结构是一个 NP-Hard 问题，求解策略
- 贪心法：从某个网络结构出发，每次调整一条边，直到评分函数不再降低为止
- 通过给网络结构施加约束来削减搜索空间
7.5.3 推断
Bayes 网络训练完成后就可以「推断」
- 「推断」即通过已知变量的观测值来推测待查询变量的
- 已知变量观测值称为「证据」
- 理想状况：直接根据 Bayes 网定义的联合概率分布来精确计算后验概率
- 「精确推断」被证明是 NP-Hard 问题，即网络结点较多、连接稠密时，难以进行精确推断
- 现实状况：降低精度要求，在有限时间内求得近似解，即「近似推断」
- 近似推断常常使用「Gibbs 采样」，一种随机采样方法
- Gibbs 采样是在 Bayes 网所有变量的联合状态空间与证据 $E=e$ 一致的子空间中进行「随机漫步」，每一步仅依赖于前一步的状态，这是一个「Markov 链」
- 在一定条件下，无论初始状态为什么，Markov 链经过足够长的迭代必定收敛于一个平稳分布
- 对于 Gibbs 采样来说，这个分布恰好是 $P ( Q|E=e )$
- Gibbs 采样算法的收敛速度较慢
- 近似推断常常使用「Gibbs 采样」，一种随机采样方法
7.6 EM 算法
存在「未观测」变量时，通过「期望最大化」( Expectation Maximization, EM ) 算法对模型参数进行估计
- 基本思想：迭代式的求解参数
- 基于参数 $\Theta$，根据训练数据推断最优隐变量 $\text{Z}$ 的值 ( E 步 )
- 基于隐变量 $\text{Z}$，对参数 $\Theta$ 进行极大似然估计 ( M 步 )
- 反复迭代，直到收敛到局部最优解
- EM 算法是一种非梯度优化方法
- 隐变量估计问题也可通过梯度下降等优化算法求解，但是由于求和的项数将随着隐变量的数目以指数级增长，会给梯度计算带来困难
- 前提条件
- 最大化对数似然 $LL ( \Theta|\text{X,Z} ) =\ln P ( \text{X,Z}|\Theta )$
- $\text{X}$ 表示观测变量集
- $\text{Z}$ 表示隐变量集，即未观测变量
- $\Theta$ 表示模型参数
- 算法求解
- 对 $\text{Z}$ 计算期望来最大化已经观测数据的对数「边际似然」
- $LL ( \Theta|\text{X} ) =\ln P ( \text{X}|\Theta ) =\ln\sum_{\text{Z}}P ( \text{X,Z}|\Theta )$
- 基于参数 $\Theta$ 求解 $\text{Z}$ 的期望
- 以初始值 $\Theta^0$ 为起点
- E 步：基于 $\Theta^t$ 推断隐变量 $\text{Z}$ 的期望，记为 $\text{Z}^t$
- M 步：基于已知观测变量 $\text{X}$ 和 $\text{Z}^t$ 对参数 $\Theta$ 做极大似然估计，记为 $\Theta^{t+1}$
- 基于参数 $\Theta$ 计算隐变量 $\text{Z}$ 的概率分布 $P ( \text{Z|X},\Theta^t )$
- E 步：基于 $\Theta^t$ 推断隐变量分布 $P ( \text{Z|X},\Theta^t )$，并计算对数似然 $LL ( \Theta|\text{X,Z} )$ 关于 $\text{Z}$ 的期望 $Q ( \Theta|\Theta^t ) =\mathbb{E}_{\text{Z|X},\Theta^t} LL ( \Theta|\text{X,Z} )$
- M 步：寻找参数最大化期望似然，即 $\Theta^{t+1}=\arg\max_{\Theta} Q ( \Theta|\Theta^t )$
- 对 $\text{Z}$ 计算期望来最大化已经观测数据的对数「边际似然」
7.7 阅读材料
朴素 Bayes 分类器引入了属性条件独立性假设，虽然在现实情况下很难成立，但是在实际应用中却有相当好的性能
- 对分类任务来说，只需要各个类别的条件概率排序正确，无须精准概率值即可导致正确的分类结果
- 对所有类别来看，如果属性间的依赖影响相同、或者属性间的依赖关系的影响能够相互抵消，则属性条件独立性假设既能降低计算开销，还能避免对性能产生负面影响
根据对属性间的依赖程度，Bayes 分类器形成了一个「谱」
- 朴素 Bayes 分类器不考虑属性间的依赖关系
- Bayes 网能够表示任意属性间的依赖关系
- 半朴素 Bayes 分类器介于上面两者之间
Bayes 分类器与 Bayes 学习的区别
- Bayes 分类器通过最大后验概率进行单点估计
- Bayes 学习则是进行分布估计
Bayes 网为不确定学习和推断提供了基本框架
- 优点
- 强大的表示能力
- 良好的可解释性
- 分类
- 结构学习：NP-Hard 问题
- 关键：评分函数
- 参数学习：较为简单
- 结构学习：NP-Hard 问题
EM 算法是最常见的隐变量估计方法
- 用来学习高斯混合模型
- 用于求解 K 均值聚类算法 ( Ch09 )