第七章 贝叶斯分类器
第七章 贝叶斯分类器
  7.1 贝叶斯决策论
    贝叶斯决策论（Bayesian decision theory）
      贝叶斯决策论是概率框架下实施决策的基本方法
      对分类任务来说，在所有相关概率都已知的理想情况下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记
    多分类任务
      定义
      任务本质
        公式表示：
      贝叶斯判定准则（Bayes decision rule）
        公式表示：
        条件风险变为：
        此时的贝叶斯最优化分类器变为：
      就是看后验概率是否是直接产生的
      判别式模型（discriminative models）
        决策树、BP神经网络、支持向量机等模型
      生成式模型（generative models）
            似然（likelihood）
            总结
        贝叶斯分类器
  7.2 极大似然估计
    问题来源
      如何估计类条件概率？
      基本策略
        先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计
        具体步骤
    概率模型训练过程就是参数估计过程
    两大学派
      频率主义学派（Frequentist）
        参数虽然未知，但却是客观存在的固定值，因此，可以通过优化似然函数等准则来确定参数值
      贝叶斯学派（Bayesian）
        参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观察到的舒俱来计算参数的后验分布
      极大似然估计(Maximum Likelihood Estimation，简称MLE)
        根据数据采样来估计概率分布参数
        公式表示
          前提假设
          训练集中的样本是独立同分布的
            对数似然(log-likelihood)
              计算机数太小约为0了
              连乘操作易产生下溢
          如何直观理解极大似然估计
          因此估计结果的准确性严重依赖与所假设的概率分布形式是否符合潜在的真实数据分布
  7.3 朴素贝叶斯分类器
    问题来源
      原因
        在计算上会遭遇组合爆炸问题
        在数据上会遭遇样本稀疏问题
        属性数越多，问题越严重
    朴素贝叶斯分类器（naive Bayes classifier）
      属性条件独立性假设（attribute conditional independence assumption）
        即假设所有属性相互独立
        换言之，假设每个属性独立地对分类结果发生影响
        即属性相互独立：
      表达式
          对于离散属性
          对于连续属性
            需要考虑概率密度函数
    西瓜例子
      西瓜数据集3.0
      测试例
      训练朴素贝叶斯分类器
          离散型
          连续型
      结论推测
    如果某个属性取值在训练集上出现的次数为零如何处理？
      问题表征
      因为朴素贝叶斯分类器是连乘式，因此会导致其他属性携带的信息会被某个训练集中未出现的属性值“抹去”
      拉普拉斯修正（Laplacian correction）
  7.4 半朴素贝叶斯分类器
    半朴素贝叶斯分类器（semi-naive Bayes classifiers）
      产生原因
      现实任务中属性条件独立性假设难以成立
      解决方式
        基本思想
        适当考虑一部分属性间的相互依赖信息
        相对于朴素贝叶斯分类器，对属性条件独立性假设进行了一定程度的放松
          贝叶斯分类器（完全联合概率计算）
          朴素贝叶斯分类器（完全独立概率计算）
      基本策略
        独依赖估计（One-Dependent Estimator，简称 ODE）
          基本思想
          假设每个属性在类别之外最多仅依赖于一个其他属性
          公式
      如何确定每个属性的父属性？
        最直接暴力的方式
        假设所有属性都依赖于同一个属性，称为“超父”（super-parent）
        TAN（Tree Augmented naive Bayes）
          原理
          在最大带权生成树（maximum weighted spanning tree）算法的基础上，将属性间的依赖关系整理成树形结果
          步骤
            计算任意两个属性之间的条件互信息（conditional mutual information）
            以属性为结点构建完全图，任意两个结点之间边的权重设为
            构建此完全图的最大带权生成树，挑选根变量，将边置为有向
            加入类别结点y，增加从y到每个属性的有向边
        两种策略
          SPODE（Super-Parent ODE）
            通过交叉验证等模型选择方法来确定超父属性
          AODE(Averaged ODE)
            一种基于集成学习机制、更为强大的独依赖分类器
            尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果
              与朴素贝叶斯分类器同样是“计数”过程
                说明
                  类似 朴素贝叶斯分类器 一样需要进行拉普拉斯修正
                  参数说明
  7.5 贝叶斯网
    概念
      贝叶斯网（Bayesian network）亦称 “信念网”（belief network）
        借助有向无环图（Directed Acyclic Graph，简称DAG）来刻画属性之间的依赖关系
        使用条件概率表（Conditional Probability Table，简称 CPT）来描述属性的联合概率分布
      贝叶斯网
          一个有向无环图，其每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来
    结构
      如何体现？
      贝叶斯网结构有效表达了属性间的条件独立性
      解释
        给定父节点集，贝叶斯网假设每个属性与它的非后裔属性独立
        举例
          上图的几个属性的联合概率分布为
          说明
      典型结构
        同父结构
          给定父节点的取值，则两个子结点条件独立
        顺序结构
          给定中间结点的取值，则前后结点的条件独立
        V型结构
          “冲撞”结构
          若给定子结点的取值，则两个父节点一定不条件独立；若子结点取值完全未知，则两个父节点是条件独立
          这种独立性称为“边际独立性”（marginal independence）
      如何分析有向图中变量间的条件独立性？
        令父节点相连的过程称为道德化（moralization）
        方法
          有向分离（D-separation）
          核心思想
          将有向图转变为一个无向图，产生的无向图称为“道德图”（moral graph）
          孩子的父母应建立牢靠的关系，否则是不道德的
        步骤
          找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无向边
          将所有有向边改为无向边
        举例
          所有的条件独立关系：
    学习
      常用方法
      两种类型
        网络结构
        条件概率
      前面介绍的贝叶斯网络都是假设网络结构已知，但现实中往往不知晓网络结构，因此贝叶斯网络学习的首要任务就是根据训练集找出结构最“恰当”的贝叶斯网
      评分搜索
        评分函数（score function）
          体现的是算法的归纳偏好
          常用评分函数基于信息论准则
            学习目标
            将学习问题看作一个数据压缩任务
            找到一个能以最短编码长度描述训练数据的模型
            综合编码长度
              描述模型自身所需的编码位数
              使用该模型描述数据所需的编码位数
              最小描述长度（Minimal Description Length， 简称MDL）准则
        以此来评估贝叶斯网与训练数据的契合程度，基于这个评分函数来寻找结构最优的贝叶斯网
        最小描述长度准则
          评分函数公式：
            第一项
              计算编码贝叶斯网B所需的编码位数
              统计学习角度：结构风险
            第二项
              计算B所对应的概率分布P对D描述得有多好
              统计学习角度：经验风险
          几种变形
            AIC（Akaike Information Criterion）
            BIC（Bayesian Information Criterion）
            MLE（Maximum Likelihood Estimation ）
          问题转化为：如何找到最合适的网络结构？
            一种是贪心算法，例如从某个网络结构出发，每次调整一条边（增加、删除或调整方向），直到评分函数值不再降低为止
            第二种是通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构
    推断
      精确推断
      近似推断
        确定性推断
          基于近似的变分推理（Variational Inference，简称VI）
        随机性推断
          基于采样的马尔可夫链蒙特卡罗（Markov Chain & Monte Carlo，简称MCMC）
            MH算法（Metropolis-Hasting）
            吉布斯采样（Gibbs sampling）
              本质
                关键点
                  吉布斯采样过程中每一步仅依赖于前一步的状态，这是一个“马尔科夫链”（Markov chain）
              流程
                  参数说明
                  步骤说明
                  结论说明
              注意
                由于马尔科夫链需要一个较长时间才能趋于平稳的分布，因此吉布斯采样算法的收敛速度较慢
                若贝叶斯网中存在极端概率"0"或"1"，则不能保证马尔科夫链存在平稳分布
  7.6 EM算法
    问题的由来
      现实现象中样本所有属性的值并非都已被观测到的，即训练样本是“完整”的
      参数说明
        无法直接求解
    EM算法（Expectation-Maximization，期望最大化算法）
      基本思想
      步骤
            公式表达
      EM算法可以看做是一种非梯度优化算法，能够得到局部最优解