机器学习之贝叶斯分类与集成学习

贝叶斯分类

贝叶斯决策论

    贝叶斯决策论是在概率框架下实施决策的基本方法。 对分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。
    估计后验概率：
      （1）给定x，可通过直接建模P(c|x)来预测c，这样得到的是“判别式模型”
      （2）先对联合概率分布P(x,c)建模，然后由此获得P(c│x)，这样得到的是“生成式模型”

极大似然估计

• 估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。
• 概率模型的训练过程就是参数估计过程，极大似然估计是根据数据采样来估计概率分布参数的经典方法，其试图在θ所有可能的取值中，找到一个能使数据出现的“可能性”最大的值。

朴素贝叶斯分类器

    朴素贝叶斯分类器的训练过程就是基于训练集D来估计类先验概率P(c)，并为每个属性估计条件 概率P(x_i |c)。为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”，常用“拉普拉斯修正”。

半朴素贝叶斯分类器

    半朴素贝叶斯分类器的基本思想是适当考虑一部分属性间的相互信赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。

独依赖估计(ODE)：假设每个属性在类别之外最多仅依赖于一个其他属性

SPODE(Super-Parent ODE)方法：假设所有属性都依赖于同一个属性，称为“超父”，然后通过交叉验证等模型选择方法来确定超父属性

AODE(Averaged One-Dependent Estimator)：尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果。AODE无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，并且易于实现增量学习。

贝叶斯网

    贝叶斯网亦称“信念网”，它借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布。

结构
    贝叶斯网结构有效地表达了属性间的条件独立性。为了分析有向图中变量间的条件独立性，可使用“有向分离”将有向图转变为无向图，由此产生的无向图称为“道德图”，父节点相连的过程称为“道德化”。

学习
    贝叶斯网学习的首要任务就是根据训练数据集找出结构最“恰当”的贝叶斯网，“评分搜索”是求解这一问题的常用方法。

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

    “最小描述长度”(MDL)准侧：选择综合编码长度（包括描述网络和编码数据）最短的贝叶斯网

    从所有可能的网络结构空间搜索近似最优贝叶斯网结构的策略：
      （1）贪心法，例如从某个网络结构出发，每次调整一条边（增加、删除或调整方向），直到评分函数值不再降低为止
      （2）通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构

推断

• 查询：通过一些属性变量的观测值来推测其他属性变量的取值
• 推断：通过已知变量观测值来推测待查询变量的过程
• 证据：已知变量的观测值
• 吉布斯采样：先随机产生一个与证据E=e一致的样本q^0 作为初始点，然后每步从当前样本出发产生下一个样本

EM算法

EM(Expectation-Maximization)算法是常用的估计参数隐变量的利器，其是一种迭代式的方法

基本思想：若参数θ已知，则可根据训练数据推断出最优隐变量Z的值(E步)；反之，若Z的值已知，则可方便地对参数θ做极大似然估计(M步)

隐变量估计问题也可通过梯度下降等优化算法求解，但由于求和的项数随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；EM算法则可看做是一种非梯度优方法

集成学习

个体与集成

    集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统、基于委员会的学习等。

同质集成：集成中只包含同类型的个体学习器
同质集成中的个体学习器亦称为“基学习器”，相应的学习算法称为“基学习算法”

异质集成：集成中的个体学习器由不同的学习算法生成
异质集成中的个体学习器称为“组件学习器”或直接称为个体学习器

    根据个体学习器的生成方式，目前的集成学习方法可分为两大类：
      （1）个体学习期间存在强依赖关系、必须串行生成的序列化方法
      （2）个体学习器间不存在强依赖关系、可同时生成的并行化方法

Boosting

    Boosting是一族可将弱学习器提升为强学习器的算法

工作机制：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合

重赋权法：在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重

重采样发：在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练

重启动：在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出急促学习器，从而使得学习过程可以持续到预设的T轮完成

    【Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成】

Bagging与随机森林

Bagging
    Bagging是并行式集成学习方法的代表，它直接基于自助采样法

    基本流程：先通过自助采样法采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合

    结果判定：Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法. 若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定结果

    Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显

随机森林

    随机森林是Bagging的一个扩展变体，其以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择

    随机森林对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）不同，随机森林中基学习器可通过个体学习器之间差异度的增加而进一步提升

    随机森林的训练效率常优于Bagging，因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，在选择划分属性时要对节点的所有属性进行考察，而随机森林使用的“随机型”决策树则只需考察一个属性子集

结合策略

平均法

• 简单平均法
• 加权平均法
  【一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法】

投票法

• 绝对多数投票法：若某标记得票过半数，则预测为该标记；否则拒绝预测
• 相对多数投票法：预测为得票最多的标记，若同时有多个标记过得最高票，则从中随机选取一个
• 加权投票法

在不允许拒绝预测的任务中，绝对多数、相对多数投票法统称为“多数投票法”
若基学习器的类型不同，则其类概率值不能直接进行比较，在此种情形下， 通常可将类概率输出转化为类标记输出然后再投票

学习法

    学习法是通过另一个学习器进行结合

    个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器

    Stacking：先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器，在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记
【将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（MLR）作为次级学习算法效果较好，在MLR中使用不同的属性集更佳】

多样性

误差-分歧分解
    个体学习器准确性越高、多样性越大，则集成越好

多样性度量
    多样性度量是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度

多样性增强

• 数据样本扰动（决策树、神经网络等）
• 输入属性扰动
• 输出表示扰动（翻转法、输出调制法、ECOC法）
• 算法参数扰动（负相关法）