贝叶斯决策论

在相关概率已知的情况下，贝叶斯决策论考虑如何基于这些概率和误判损失选择最优的类别标记。

假设有N中可能的类别标记${c_1,c_2,c_3,…,c_N}, \lambda_{ij}$是将一个真实标记为$c_j$的样本误分类为i产生的损失。推出来样本x分类为$c_i$所产生的期望损失：

$R(c_i \mid x)=\sum\limits_{j=1}^N \lambda_{ij}P(c_j \mid x)$

显然对每个样本x，若能最小化条件风险$R(h(x)\mid x)$，即在每个样本上选择那个使条件风险$R(c\mid x)$最小的类别标记，总体风险R(h)也将最小化。

$h^{*}(x)=arg_{c in y}\min R(c\mid x)$

此时$h^$称为贝叶斯最优分类器，与之对应的总体风险$R(h^)$称为贝叶斯风险。$1-R(h^*)$反映了分类器能达到的理论上限。

若目标是最小化分类错误率，则误判损失$\lambda_{ij}$可写为：$\lambda_{ij} =0 if i==j else 1$

此时的条件风险：$R(c \mid x)=1-P(c \mid x)$，于是最小化分类错误率的贝叶斯最优分类器为$h^*(x)=arg_{c \in y}\max P(c \mid x)$

这里有两种策略估计后验概率$P(c \mid x)$：

给定x，直接建模$P(c \mid x)$预测c，这种判别式模型，之前介绍的决策树、神经网络、SVM都可行
对联合分布P(x,c)建模，之后获得$P(c \mid x)$，这种生成式建模 $P(c \mid x)=\frac{P(c)P(x \mid c)}{P()x}$

上式，其中$P(c)$是累先验概率，也就是预估概率；$P(x \mid c)$是样本x相对于类标记c的类条件概率，也称为似然likelihood；$P(x)$是用于归一化的证据因子。对于给定样本x，证据因子$P(x)$与类标记无关。

类先验概率$P(c)$表达了样本空间中各类样本所占的比例；当训练集中包含充足的独立同分布样本时，$P(c)$可通过各类样本出现的频率估计。

极大似然估计

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

具体到上节的类条件概率上，记关于类别c的类条件概率为$P(x \mid c)$，假定$P(x \mid c)$具有确定的形式并且被参数向量$\theta_c$唯一确定，则我们的任务就是利用训练集D估计参数$\theta_c$。此时我们记$P(x \mid c)$为$P(x \mid \theta_c)$

朴素贝叶斯分类器

基于贝叶斯公式来估计后验概率$P(c \mid x)$的主要困难在于累条件概率$P(x \mid c)$是所有属性上的联合概率，难以从有限的训练样本直接估计得到。

为了避开这个障碍，朴素贝叶斯分类采用属性条件独立性假设：对已知类别假设所有的属性相互独立。

$P(c \mid x)=\frac{P(c)P(x \mid c)}{P(x)}=\frac{P(c)}{P(x)}\prod\limits_{i=1}^dP(x_i \mid c)$

其中d为属性数目，$x_i$为x在第i个属性上的取值。

由于对所有的类别来讲$P(x)$相同，因此贝叶斯判定准则有$h_{nb}=arg\max\limits_{c \in y}P(c)\prod\limits_{i=1}^dP(x_i \mid c)$

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

小例子

令$D_c$表示训练集D中第c类样本组成的集合，若有充足的独立同分布样本，则可以容易的估计出类先验概率：$P(c)=\frac{\mid D_c \mid}{\mid D \mid}$

对离散属性而言，令$D_{c,x_i}$表示$D_c$中在第i个属性上取值为$x_i$的样本组成的集合，则条件概率$P(x_i \mid c)$可以估计为：$P(x_i \mid c)=\frac{\mid D_{c,x_i} \mid}{\mid D_c \mid}$

对于连续属性，假定$p(x_i \mid c) \sim N(\mu_{c,i},\theta_{c,i}^2)$,其中$\mu_{c,i}$和$\theta_{c,i}^2$分别是第c类样本在第i个属性上取指的均值和方差。$p(x_i \mid c)=\frac{exp^({-\frac{(x_i-\mu_{c,i})^2}{2\theta_{c,i}^2}})}{\sqrt{2\pi}\theta_{c,i}}$

拉普拉斯修正

如果某个属性在训练集中没有与某个类同时出现过，则直接使用上式判别将出现问题。具体表现在连乘过程中，一个变量为0，则整个式子都为0.为了避免这种情况的发生，使用拉普拉丝修正：$\hat{P(c)}=\frac{\mid D_c \mid+1}{\mid D \mid+N}$，条件概率修正为$\hat{P}(x_i \mid c)=\frac{\mid D_{c,x_i} \mid+1}{\mid D_c \mid+N_i}$

半朴素贝叶斯

放宽朴素贝叶斯分类中对属性条件独立性的要求，使得贝叶斯更加的普适性，人们在朴素贝叶斯的基础上提出了半朴素贝叶斯。

半朴素贝叶斯适当的考虑一部分属性间的相互依赖关系，从而不至于彻底忽略比较强的属性依赖；但是为了避免问题陷入到复杂的联合概率计算中，一般会对属性依赖的数量有要求。

假定只能最多一个依赖关系，也就是”独依赖估计”：$P(c\mid x) \propto P(c)\prod\limits_{i=1}^dP(x_i \mid c,pa_i) $

其中$pa_i$为属性$x_i$所依赖的属性，称为$x_i$的父属性。若每个属性的父属性都已知，则可直接使用之前的公式求解；否则我们需要确定每个属性的父属性。

上图是朴素贝叶斯（独、无依赖立）以及两种常见的半贝叶斯（独依赖）：SPODE（SUper Parent ODE）和TAN（Tree Augmented naive Bayes）

SPODE中有一个超属性，属性如果有依赖，则都依赖到此属性上面；

TAN则是在最大带权生成树算法基础上通过转换将依赖结构化简。

AODE（Averaged One Dependent Estimator）尝试将每个属性作为超父来构建SPODE，然后将那些有足够训练数据支撑的SPODE继承起来作为最终结果。

贝叶斯网

贝叶斯网B由结构G和参数$\Theta$两部分组成，即$B=\langle F,\Theta \rangle$。网络结构G是一个有向无环图，每个节点对应一个属性，若两个属性有直接的依赖关系，则由一条边连接起来；参数$\Theta$定量的描述依赖关系。例如属性$x_i$在G中的父节点集为$\pi_i$，则$\Theta$包含了每个属性的条件概率表$\theta_{x_i \mid \pi_i}=P_B(x_i \mid \pi_i)$

贝叶斯网有效的表达了属性间的条件独立性。给定父节点集合，贝叶斯网假设每个属性与它的非后裔属性独立。

学习

正常情况下，我们并不知晓网络结构，需要通过学习方法建立或匹配上适当的网络结构。

评分搜索：定义评分函数来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。

EM算法

对于不完整的训练样本，或者说是未观测的变量，学名是隐变量：令X表示已观测变量集，Z表示隐变量集，$\Theta$表示模型参数

对$\Theta$做极大似然估计，则最大化对数似然$LL(\Theta \mid X,Z)=ln P(X,Z\mid \Theta)$

无法直接求解的隐变量，通过对Z计算期望，最大化已观测数据的对数“边际似然”

EM算法是常用的估计参数隐变量的迭代方法：

（E）若参数$\Theta$已知，则可根据训练数据推断出最优隐变量Z的值

（M）反之做Z值已知，可方便的对参数$\Theta$做极大似然估计

以初始值$\Theta^0$迭代步骤：

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