《机器学习》：贝叶斯分类器

贝叶斯决策论

贝叶斯判定准则：为最小化总体风险，只需在每个样本上选择那个能使条件风险最小的类别标记

h^*(x)=\arg\min\limits_{c\in\Upsilon}R(c\vert x)

$h^*(x)$ 称为贝叶斯最优分类器，对应的总体风险称为贝叶斯风险

贝叶斯判定准则基于后验概率 $P(c\vert x)$ ，根据贝叶斯定理有

P(c\vert x)=\frac{P(c)P(x\vert c)}{P(x)}

其中 $P(c)$ 可以根据各类样本出现的频率进行估计

估计类条件概率 $P(x\vert c)$ 的常用策略是先假定其具有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计

令 $D_c$ 为训练集 D 中第 c 类样本的集合

\begin{aligned} P(D_c\vert\theta_c)&=\prod\limits_{x\in D_c}P(x\vert\theta_c)\\ L(\theta_c)&=\ln P(D_c\vert\theta_c)=\sum\limits_{x\in D_c}\ln P(x\vert\theta_c)\\ \hat\theta_c&=\arg\max\limits_{\theta_c}L(\theta_c) \end{aligned}

朴素贝叶斯分类器假设所有属性相互独立，则有

\begin{aligned} P(c\vert x)&=\frac{P(c)P(x\vert c)}{P(x)}=\frac{P(c)}{P(x)}\prod\limits_{i=1}^dP(x_i\vert c)\\ h_{nb}(x)&=\arg\max\limits_{c\in\Upsilon}P(c)\prod\limits_{i=1}^dP(x_i\vert c) \end{aligned}

当某个属性值在训练集中没有与某个类同时出现过，即使通过其他属性可以判定为正类，依然会被判为负类，此时需要进行拉普拉斯修正

\begin{aligned} P(c)&=\frac{\vert D_c\vert+1}{\vert D\vert+N}\\ P(x_i\vert c)&=\frac{\vert D_{c,x_i}\vert+1}{\vert D_c\vert+N_i} \end{aligned}

半朴素贝叶斯分类器与朴素贝叶斯不同在于不需要要求属性之间全部相互独立，适当考虑一部分强相关的属性依赖

属性之间的依赖关系可以构建出树或者图，从而使用相关的算法来选择属性依赖

独依赖估计（ODE）是半朴素贝叶斯分类器最常用的一种策略，它假设每个属性在类别之外最多仅依赖于一个其他属性

P(c\vert x)\propto P(c)\prod\limits_{i=1}^dP(x_i\vert c,pa_i)

SPODE 算法假设所有属性都依赖于同一个属性，再通过交叉验证等模型选择方法来确定超父属性

TAN 算法在属性依赖构成的树结构上，使用最大生成树算法，选择强相关的属性依赖

AODE 是一种基于集成学习机制、更为强大的独依赖分类器，它尝试将每个属性都作为超父来构建 SPODE，最后将那些具有足够训练数据支撑的 SPODE 集成起来作为最终结果

贝叶斯网借助 DAG 图来描述属性之间的依赖关系，使用条件概率表来描述属性间的联合概率分布

贝叶斯网中有三种典型的结构，分别是同父结构、V 型结构和顺序结构

使用有向分离来分析贝叶斯网

经过以上处理产生的无向图称为道德图，该过程称为道德化

在道德图中，若节点 x 和 y 能被 z 分开，即去除 z 节点后，x 和 y 属于两个连通分支，则称属性 x 和 y 被 z 有向分离

若网络结构已知，则只需对训练样本计数，估计出每个节点的条件概率即可，因此在学习之前，首先要找到结构最合适的贝叶斯网，使用评分搜索来解决这个问题，定义一个评分函数，评估贝叶斯网和训练集的契合程度，基于这个评分函数来寻找结构最优的贝叶斯网

常用的评分函数基于信息论的准则，寻找一个能与数据契合的长度最短的编码，定义评分函数为以下形式

\begin{aligned} s(B\vert D)&=f(\theta)\vert B\vert-LL(B\vert D)\\ LL(B\vert D)&=\sum\limits_{i=1}^m\log P_B(x_i) \end{aligned}

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

当 $f(\theta)=1$ ，函数称为 AIC 评分函数，当 $f(\theta)={1\over2}\log m$ ，函数称为 BIC 评分函数

直接根据贝叶斯网定义的联合概率分布来精确计算后验概率是一个 NP 难问题，通常使用吉布斯采样来求得近似解

设经过 T 次采样得到与 q 一致的样本共有 $n_q$ 个，则估计后验概率为

P(Q=q\vert E=e)\simeq\frac{n_q}{T}

吉布斯采样的每一步依赖于前一步的状态，这是一个马尔可夫链，在一定条件下，在 $t\rightarrow\infty$ 时必收敛于一个平稳分布

EM 算法用于估计参数隐变量，即在样本属性存在缺失值时进行参数估计

以参数初始值 $\Theta_0$ 为起点，迭代以下步骤直到收敛