【西瓜书】 第七章 贝叶斯分类器

本文是周志华老师《机器学习》第七章贝叶斯分类器的学习笔记。　　

贝叶斯和频率学派的区别，一图以蔽之。

贝叶斯决策论　　

一般的形式化描述(来自Pattern Classification):
令${w_1,\dots,w_c}$　表示有限的ｃ个类别集　${\alpha_1,\dots,\alpha_a }$ 表示有限的a中可能采取的行为集，风险函数 $\lambda(\alpha_i|w_j) $　描述了类别状态为$w_j$ 时采取行动$\alpha_i$ 时的风险。　　
特征向量$x$ 表示一个$d$ 维随机变量。令$p(x|w_j) $　表示ｘ的状态条件概率密度函数。那么我们由贝叶斯公式得到：　　

$$P(w_j|x) = \frac{p(x|w_j)P(w_j)}{p(x)}$$

用非正式的英文可表达为：

$$posterior = \frac{likelihood \times prior }{evidence}$$

那么特定模式ｘ下采取行为$\alpha_i$ 的损失就是：　　

$$R(\alpha_i|x) =\sum \lambda(\alpha_i|w_j)P(w_j|x)$$

形式化的来讲，我们就需要找到一种决策规则来最小化总风险，此时就需要我们对所有的$i=1,\dots,a$ 计算条件风险：　　

$$R(\alpha_i|x)=\sum\lambda(\alpha_i|w_i)P(w_j|x)）$$

并选择使条件风险最小的行为。最小化后的总风险值称作贝叶斯风险,它是可获得的最优结果.

极大似然估计　　

对于概率模型分类器来说，我们通常需要通过训练样本来估计参数（先验概率和类条件密度函数）。　　
估计先验通常没有太大问题，但是对于类条件密度函数 $p(x|w_j)$，我们可能会遇到以下两个挑战：　　

1. 训练样本不足，导致数据稀疏　　
2. 特征较多，产生组合爆炸，计算复杂性出问题　　　

为了解决如上问题，我们通常需要通过先验知识讲条件概率密度进行参数化，如假设$p(x|w_i)$ 是一个多元正态分布，这样我们就只需要估计均值和协方差矩阵了。　　
参数估计有两类方法，频率学派的代表方法是极大似然估计，贝叶斯学派的是贝叶斯估计。　　
这里我们主要谈一下极大似然估计：　　
假设我们有c个样本集 $D_1,…,D_c$，每个样本集中含有一类样本，且满足独立同分布。假设每个类条件概率密度 $p(x|w_j)$ 的形式都是已知的，其未知的部分就是具体的参数向量$\theta_j$ 的值，那么确定了参数向量就确定了条件概率密度。　　
那么对于有ｎ个样本的样本集，参数$\theta$ 的似然就是：　　

$$p(D|\theta)=\prod_{k=1}^n p(x_k|\theta)$$

直观的理解就可以把参数向量的极大似然估计当做最符合已有观察样本集的那个。　　
为了方便计算分析，我们通常使用对数似然。另外需要注意的是 $p(D|\theta)$ 和　$p(x|\theta)$ 虽然形式类似，但是前者表示的是一个关于$\theta$ 的函数，而后者则是一个关于以$\theta$ 为参数关于$x$ 的函数。　　
定义对数似然函数：　　

$$l(\theta)\equiv ln\ p(D|\theta)$$

那么我们对参数的估计为：　　

$$\hat{\theta}=arg\ max\ l(\theta)$$

对似然函数

$$l(\theta)=\sum_{k=1}^n ln \ p(x_k|\theta)$$

要求取到最大，那么我们可以通过微分（如果可微）后取零得到一组方程组来解。值得注意的是，这里得到的方程组是最大似然估计值的必要条件,而不是充分条件。　　
最大似然估计(MLE, Maximum Likelihood Estimation)来进行参数估计的准确性依赖于所假设的分布形式是否符合现实，如不符合，很难做出好的判断。　　
除了MLE,还有一种最大后验(MAP, maximum a posteriori)的估计器，也就是求$l(\theta)p(\theta)$ 取最大值的那个参数向量，MLE可以看做MAP的先验概率均匀分布的特例。MAP的缺点在于，对参数空间的任意非线性变换，如旋转变换，都会使得概率密度 $p(\theta)$ 发生变化，从而使估计不再有效。　　　
简单谈一下贝叶斯估计，虽然该方法和极大似然估计的结果往往很相似，在先验保证问题有解的情况下，最大似然估计和贝叶斯估计在训练样本趋于无穷时可以说是等价的。但是其本质有很大不同，极大似然估计是将参数看作是确定而未知的，贝叶斯估计则是将其视作一个随机变量；极大似然估计得到的是一个最佳解答，而贝叶斯估计得到的是许多可行解答的加权平均值。　　

朴素贝叶斯分类器

朴素贝叶斯分类器做了一个属性条件独立性假设,即，每个属性独立地对分类结果产生影响。那么，贝叶斯公式即可写为：

$$P(c|x) = \frac{P(c)P(x|c)}{P(x)}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)$$

判定准则即为：

$$h_{nb}(x)=\underset{c\in C}{\operatorname{argmax}}P(c)\prod_{i=1}^dP(x_i|c)$$

令$D_c$ 表示训练集$D$ 中第$c$ 类样本组合的集合，那就能得到先验概率：

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

同样类条件概率密度就是(离散值)

$$P(x_i|c)=\frac{|D_{c,x_i}|}{D_c}$$

若属性是连续的，则可以用MLE确定参数得到概率密度函数。
为了避免训练集中未出现的属性信息被抹去，我们在估计概率值时通常会做一个平滑。如下是常见的拉普拉斯修正，$N$为类别数，$N_i$是第i个属性的取值可能。

$$\hat{P}(c)=\frac{|D_c|+1}{|D|+N}$$ $$\hat{P}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$$

半朴素贝叶斯分类器

前面提到过朴素贝叶斯采用了属性条件独立假设，但是现实情况中，属性之间很难完全独立。
由此产生了一类学习方法叫做半朴素贝叶斯分类器。这类分类器适当考虑部分属性之间的相互依赖信息，通常采取独依赖估计，也就是假设每个属性在类别之外最多仅依赖一个其他属性。
那么如何来判断属性依赖关系呢？

SPODE

最直接的做法就是假设所有属性都依赖于同一个属性，称为超父(super-parent)，然后通过交叉验证来确定超父属性，这就是SPODE算法。

TAN

TAN(Tree Augmented naive Bayes)算法则是在最大带权生成树算法基础上，将属性依赖关系通过以下步骤约简为树形结构：

1. 计算任意两个属性之间的条件互信息（conditional mutual information）: $$I\left(x_{i}, x_{j} | y\right)=\sum_{x_{i}, x_{j} ; c \in \mathcal{Y}} P\left(x_{i}, x_{j} | c\right) \log \frac{P\left(x_{i}, x_{j} | c\right)}{P\left(x_{i} | c\right) P\left(x_{j} | c\right)}$$
2. 以属性为节点构建完全图，权重为$I(x_i,x_j|y)$
3. 构建此完全图的最大带权生成树，挑选根变量，置边为有向
4. 加入类别节点，增加从类别节点到各个属性的有向边
   TAN实际保留了强相关属性之间的依赖性。

AODE

AODE(Averaged One-Dependent Estimator)算法是一种基于集成学习的更强的独依赖分类器，AODE尝试将每个属性都作为超父来构建SPODE,然后将具有足够训练数据支持的SPODE集成起来作为最终结果。即：

$$P(c|x)\propto \sum_{\underset{|D_{x_i}|\ge m'}{i=1}}P(c,x_i)\prod_{j=1}^{d}P(x_j|c,x_i)$$

这里默认$m’$ 为30.
类似拉普拉斯修正，这里我们就有：

$$\hat{P}_{c,x_i}=\frac{|D_{c,x_i|}+1}{|D|+N_i}$$ $$\hat{P}(x_j|c,x_i)=\frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}$$

贝叶斯网

又称信念网(belief network) ,它借助有向无环图来刻画属性之间的依赖。

结构

贝叶斯网络结构表达属性之间的条件独立性，给定父节点集，贝叶斯网假设每个属性和他的非后裔属性独立，于是就有联合概率分布：

$$P_B(x_1,x_2,\dots,x_d)=\prod_{i=1}{d}P_B(x_i|\pi_i)=\prod_{i=1}{d}\theta_{x_i|\pi_i}$$

这里介绍两个概念，对于三个随机变量 $a,b,c$，

• 条件独立
  若对给定的$a$　的取值 ，$p(b,c|a)=p(b|a)p(c|a)$,我们称之为条件独立
• 边际独立　　
  若 $a$ 的取值完全未知，而$b,c$ 此时相互独立　$p(b,c)=p(b)p(c)$　，我们称之为边际独立　　

  这里补充一下概率论的一些常见误区：　　
  独立性不能导出条件独立性，一个很直观的例子，随机变量Ａ表示硬币１向上的事件，Ｂ表示硬币２向上，显然Ａ和Ｂ是独立的，但是给出随机变量Ｃ表示硬币１，２是否同向，那么对于给定的Ｃ，Ａ和Ｂ显然不是条件独立的。　　

利用贝叶斯分析属性之间条件独立性，可以使用有向分离(d-separation),详见西瓜书p158。

学习

在网络的拓扑结构已知时，我们只需计数来计算每个节点的条件概率表即可，但是现实应用中我们往往不知道网络结构。
“评分搜索“是一种寻找网络结构的常见方法。
常用的评分函数通常给予信息论准则，其中有”最小描述长度“（Minimal Description Length, MDL）准则，指导我们选择综合编码长度最短的贝叶斯网络。
给定训练集$D={x_1,x_2,\dots,x_m}$ ，贝叶斯网络$B=$ 在 $D$ 上的评分函数可以写为：

$$s(B|D)=f(\theta)|B|-LL(B|D)$$

其中 $|B|$ 是贝叶斯网络的参数个数， $f(\theta)$ 表示描述每个参数所需的字节数，而：

$$LL(B|D)=\sum_{i=1}^{m}logP_B(x_i)$$

是贝叶斯网络的似然对数。
当 $f(\theta)=1$,我们得到AIC评分函数，$f(\theta)=1/2log\ m$ 时，我们得到BIC评分函数。

$$BIC(B|D)=\frac{log\ m}{2|B|-LL(B|D)}$$

不难发现，当网络结构固定后，对评分函数的优化就等价于对参数的极大似然估计，因此在最小化评分函数时，我们可以值对网络结构进行搜索，候选结构的最有参数可以直接在训练集上计算得到。
然而，这类搜索是个NP难问题，有两种常用策略能够在有限时间内获取近似解：贪心法——从某个结构出发，每次调整一条边，直到评分函数不再降低；给网络结构施加约束来减小搜索空间。

推断

在训练好贝叶斯网络后，我们通过已知变量来推测待查询变量的过程称作推断（inference），已知变量称为证据（evidence）。
最理想的是通过贝叶斯网的联合概率分布来精确计算，不过这被证明是NP难的（观察贝叶斯网的联合概率分布公式，），此时需要借助近似推断。
我们常用吉布斯采样（Gibbs sampling）。
吉布斯采样　　
需要注意的是，由于马尔科夫链通常需要很长时间才能趋于平稳分布，所以吉布斯采样算法收敛速度较慢。　　　 　

EM算法　　

现实中常常会遇到未观测的变量，称之为隐变量，令 $X$ 表示已观测变量，$Z$ 表示隐变量集，　$\Theta$ 表示模型参数，对模型参数做极大似然估计，则应该最大化对数似然：　　

$$LL(\Theta|X,Z)=lnP(X,Z|\Theta)$$

因为 $Z$ 为隐变量，无法直接求解，因此可通过对隐变量计算期望，来最大化已观测数据的边际似然(marginal likelihood)。　　

$$LL(\Theta|X)=lnP(X|\Theta)=ln\sum_zP(X,z|\Theta)$$

Em算法（Expectation-Maximization），即期望最大化算法常用于估计参数隐变量。基本思想是，若参数 $\Theta$ 已知，则推断出最优隐变量(E步)，若$Z$ 已知，则对参数做极大似然估计(M步)。　　

• E(Expectation):
  以当前参数$\Theta^t$ 推断隐变量分布，$P(ZZ|X,\Theta_t)$，并计算对数似然　$LL(\Theta|X,Z)$　关于$Z$ 的期望，　　 $$Q(\Theta|\Theta^t)=\mathbb{E}_{Z|X,\Theta^t}LL(\Theta|X,Z)$$
• M(Maximization): 　　
  寻找参数最大化期望似然，即　　 $$\Theta^{t+1}=\underset{\Theta}{arg\ max}Q(\theta|\theta^t)$$

期望最大化算法的核心思想就是用已有的数据来递归估计似然函数。　　
广义期望最大化（GEM）算法比EM算法要求要松一些，在算法的Ｍ步只要求参数对似然有所改善，但不要求最优的那个，虽然这使得收敛速度变慢，但是提供了更大的自由度去选择计算更简单的途径。　　

习题与答案 　

7.1 试使用极大似然法估算西瓜数据集3.0中前3个属性的类条件概率。

7.2 试证明：条件独立性假设不成立时，朴素贝叶斯分类器仍有可能产生最优贝叶斯分类器。
条件不独立的那些属性都一致，或者放松一些，同一类的样本的条件不独立的属性一致时，朴素贝叶斯分类器依旧可以是最优贝叶斯分类器。　　
7.3 试编程实现拉普拉斯修正的朴素贝叶斯分类器，并以西瓜数据集3.0为训练集，对p.151“测1”样本进行判别。
部分代码：　　

def calContProbDistrete(data, feature):
    """
    Data - dataframe contain two colunms, the given feature of samples and it label
    """
    prob = pd.DataFrame(0, columns=data['label'].unique(), index=data[feature].unique())
    ni = len(data[feature].unique())
    prob = np.zeros((len(data['label'].unique()), len(data[feature].unique())) )

    for i in data['label'].unique():
        nc = len(data[data['label'] == i]) + ni
        for j in data[feature].unique():
            prob[i,j] = (len(data[data['label']==i][data[feature]==j]) + 1) / nc 

    return prob

所有代码在github上
7.4 实践中使用式（7.5）决定分类类别时，若数据的维数非常高，则概率连乘的结果通常会非常接近于0从而导致下溢。试述防止下溢的可能方案。
加log，变连乘为连加。　　

7.5 试证明：二分类任务中两类数据满足高斯分布且方差相同时，线性判别分析产生贝叶斯最有分类器。
对于线性分类器得判别公式$J=\frac{|w^T(u_1-u_2)|^2}{w^T(\sum_1+\sum_2)w}$ 求最大值也就是求
$\frac{1}{J}$的最小值。这里$\sum_i$代表的协方差矩阵由于特征之间的独立性，是个对角矩阵，那么这里的 $w^T\sum_1w$ 的二次型就可以看作是二范数，那么就有：

$$\frac{1}{J}=\frac{w^T(\sum_1+\sum_2)w}{|w^T(u_1-u_2)|^2}=\sum_i\frac{(1-y_i)|w^T(x_i-u_1)|^2+y_i|w^T(x_i-u_2)|^2}{|w^T(u_1-u_2)|^2}$$

再回到贝叶斯分类器这边，最优贝叶斯分类器也就是使每个样本的后验概率最大（条件风险最小）的分类器，对应线性判别，条件风险越小也就是样本离其所对应的分类中心的距离尽可能小同时分类中心之间的距离尽可能大，也就是 $\sum_i\frac{(1-y_i)|w^T(x_i-u_1)|^2+y_i|w^T(x_i-u_2)|^2}{|w^T(u_1-u_2)|^2}$ 最小。
观察这两个式子，发现它们相同，得证。 　

7.6
略　　
7.7 给定 $d$ 个二值属性的二分类任务，假设对于任何先验概率项的估算至少需要30个样例，则在朴素贝叶斯分类器式（7.15）中估算先验概率项需要60个样例。试估计在AOED式中估算先验概率项所需的样例数。（分别考虑最好和最坏情况）
最好情况：　　
每一类的每个属性都一致，则需要 $30\times 2 = 60$　个样例　　
最坏情况：
需要 $30\times 2 \times d = 60d$ 个样例　　

7.8
7.8