《模式识别与机器学习》的读书笔记

15 分钟读完

全书总评

  • 书本印刷质量:4 星。
    • PDF 打印,非影印版,字迹清楚,图片清晰。
    • 英文版排版更利于阅读,请到这里 2006 年版 下载,文中错误需要修正文件,否则会影响理解。
    • 中文版排版有点紧凑,错误较少,并且译者已经将英文版中的错误进行了修订。但是,译文中也存在少量错误,建议与英文版结合起来。
  • 著作编写质量:4 星。模式识别与机器学习的进阶。
    • 全书内容自洽,数学方面不算太深,具备大学工科数学功底(微积分、线性代数、概率统计)就可以阅读,如果想深入理解还需要补充随机过程、泛函分析、最优化、信息论等,如果还想更深一层还可以补充决策论、测度论、流形几何等理论;再深俺就完全不知道了。
    • 作者以讲清楚 Bayesian 方法的来龙去脉为根本目的,所以全书紧紧围绕在 Bayesian 同志的周围,尽可能以 Bayesian 思想来分析各种模式识别与机器学习中的常用算法,对于已经零散地学习了许多种算法的同学大有裨益。
    • 全局的结构是点到面的风格,以一个二项式拟合的例子一点点铺开,节奏稍慢但是前后连贯,知识容易迁移理解;
  • 著作翻译质量:4 星。
    • 马春鹏免费将自己的翻译稿贡献出来,翻译的质量值得肯定,用词符合专业认知,只是译文的流畅性稍感不足(纯属个人感受)。
    • 缺点:符号的使用不如原文规范。例如:原文都以加粗的罗马字母表示向量,而译文只是以加粗默认的数字字母表示向量,而在印刷中默认的数学字母加粗和未加粗的区别不明显,容易混淆。精读一段时间后,觉得译者提供的符号系统在自己手写公式的时候比较方便,对于印刷的符号系统依然推荐原作者的风格。
  • 读书建议:
    • 前四章是重点,建议先从 1~2 读一遍,再从 1~4 读一遍,对前四章心中有数再看后面的章节会方便很多。
    • 需要手写公式,推不动看不懂不害怕,因为理论推导的细节都被作者跳过了。如果想深入了解,只能去找相关文献。但是如果有了前 4 章的基础,又有很好的机器学习的背景知识,用贝叶斯视角读完全书的可能性还是有的。
    • 需要把公式推导中用到前面的公式的部分抄过来,反复推导前面的公式才能流畅地看后面的内容。
  • 笔记目的:记录重点,方便回忆。

重要的数学符号与公式

建议将下面列出的重要的数学符号与公式找张纸列在上面,方便在后面看到时可以查询。

重要的数学符号

  • x:表示 D 维的向量,表示一个 D 维的数据点;
  • x:表示 N 维的向量,表示 N 个 1 维的数据点;
  • M:表示矩阵;$(w_1,\cdots,w_M)$:表示一个行向量有 M 个元素;w=($w_1,\cdots,w_M)^T$ 表示对应的列向量。
  • $I_M$:表示 M×M 单位阵。
  • x:表示元素;y(x):表示函数;f[y]:表示泛函。
  • g(x)=O(f(x)):表示复杂度。

重要的公式(括号内的是公式的编号)

  • 概率论
    • 期望:(1.33)(1.34)
      • 期望估计:(1.35)
      • 条件期望:(1.36)(1.37)
    • 方差:(1.38)(1.39)(1.40)
    • 协方差:(1.41)(1.42)
    • 高斯分布:(1.46)(1.52)(2.42)(2.43)
  • 信息论
    • 熵:(1.98)
      • 微分熵:(1.103)
      • 条件熵:(1.111)
      • 联合熵:(1.112)
    • 相对熵,KL 散度:(1.113)
    • 互信息:(1.120)(1.121)
  • 概率分布
    • Bernoulli 分布:(2.2)
    • 二项分布:(2.9)
    • Beta 分布:(2.13)
    • 多项式分布:(2.34)
    • Dirichlet 分布:(2.38)
    • Gamma 分布:(2.146)
      • Gamma 函数 (1.141)
    • 学生 t 分布:(2.158)
    • 混合高斯分布:(2.188)(2.193)
    • 指数族分布:(2.194)
      • softmax 函数:(2.213)
      • 共轭先验:(2.229),(2.230)
  • 回归的线性模型
    • 线性基函数模型:(3.1)(3.2)(3.3)
      • 高斯基函数:(3.4)
      • sigmoid 基函数:(3.5)
      • logistic sigmoid 基函数:(3.6)
    • 平方损失函数:(1.90)(3.37)
      • 平方和误差函数:(3.12)(3.26)
        • 正则化最小平方:(3.24)(3.27)
      • 设计矩阵:(3.16)
      • 顺序学习:(3.22)(3.23)
    • 预测分布:(3.57)
  • 分类的线性模型
    • 推广的线性模型:(4.3) 神经网络
    • 整体的网络函数:(5.9)

C01. 绪论

S01. 前言

  • 重点
    • 多项式曲线拟合:这个例子通过不同角度介绍机器学习的常用算法,从而更好地理解贝叶斯估计的思想,也是后面反复讨论的基础。
  • 难点
    • 贝叶斯概率论:最大似然函数、先验概率与后验概率
    • 模型选择与分类决策:模型复杂度控制、模型质量评价和决策评价准则
  • 学习要点
    • 期望与方差,需要补充《概率论》的知识;
    • 参数估计,需要补充《最优化》的知识,也可以参考模式识别书中的理论部分;
    • 模型选择与分类决策,需要补充《模式识别》与《机器学习》方面的基础知识;
    • 本书更适合在对机器学习有了基本认识后,想进一步加深贝叶斯统计学习理解的同学研读。
    • 机器学习的基础建议参考 \【李航, 2012] \【周志华,2018]

S1.1. 基本知识点

  • 训练集 (training set):一个由 N 个数字{$x_1,\cdots,x_N$}组成的大的集合,用来通过训练来调节模型的参数。
  • 目标向量 (target vector):t表示数字的类别,代表对应数字的标签。
  • 学习的结果:表示为一个函数 y(x),它以新 x 为输入,产生 y 为输出,结果与t的形式相同。
    • y 的具体形式是在训练 (training) 阶段被确定的,也被称为学习 (learning) 阶段。
    • 当训练阶段完成后,可以使用新数据集去检验训练的结果,这种数据集称为测试集 (test set)。
    • 泛化 (generalization):正确分类与训练集不同的新样本的能力。
  • 原始输入向量需要被预处理 (pre-processed),变换到新的变量空间,也称为特征抽取 (feature extraction)
  • 有监督学习 (supervised learning)
    • 离散输出学习称为分类 (classification) 问题
    • 连续输出学习称为回归 (regression) 问题
  • 无监督学习 (unsupervised learning)
    • 离散输出学习称为聚类 (clustering) 问题
    • 连续输出学习称为密度估计 (density estimation)
      • 高维空间投影到二维或者三维空间,为了数据可视化 (visualization)
  • 反馈学习(强化学习)(refinforcement learning):本书不关注

S1.2. 例子:多项式曲线拟合

  • 理论基础
    • 概率论提供了数学框架,用来描述不确定性;
    • 决策论提供了合适的标准,用来进行最优的预测。
  • 多项式函数是线性模型,充分讨论在 C03 回归 和 C04 分类。
    • 最小化误差函数 (error function)
      • 常用的是平方误差函数 (square error function),根均方 (root-mean-square, RMS) 误差更方便
    • 多项式的阶数的选择,称为模型对比 (model comparison) 或者模型选择 (model selection) 问题。
    • 过于完美地拟合训练集数据可能会出现过拟合 (over-fitting) 问题。
      • 大量的数据可以避免过拟合问题。
    • 训练数据的数量应该是模型可调节参数的数量的 5 到 10 倍。
    • 最大似然 (maximum likelihood,ML)
      • 寻找模型参数的最小平方法代表了 ML 的一种特殊情形
      • 过拟合问题是 ML 的一种通用属性
      • Bayesian 方法可以自然地解决过拟合问题
      • 控制过拟合的技术有正则化 (regularization) 方法,通过给误差函数增加惩罚项
        • 在统计学中叫做收缩 (shrinkage) 方法
        • 在二次正则项中称为山脊回归 (ridge regression)
        • 在神经网络中称为权值衰减 (weight decay)
        • 过拟合的影响可以通过正则项的λ系数来认识
      • 控制过拟合的技术有验证集 (validation set),也被称为拿出集 (hold-out set),缺点是不能充分利用数据

S1.3. 概率论

  • (建议跟着公式和例子推导一下)
  • 离散随机变量与连续随机变量之间的关系有助于理解概率中的其他概念,例如:期望、方差、熵等等的定义和推导
  • 概率论的两种基本规则(后面会有大量的应用,需要充分理解才能正确的使用)
    • 加和规则 (sum rule)
    • 乘积规则 (product rule)
  • 离散随机变量
    • 概率质量函数 (probability mass function)
    • 联合概率 (joint probability)
      • 利用加和规则得到边缘概率 (marginal probability)
      • 利用乘积规则得到条件概率 (conditional probability)
  • 连续随机变量
    • 概率密度函数 (probability density function)
    • 累积分布函数 (cumulative distribution function)
  • 期望 (expectation):函数的平均值
    • 有限数量的数据集,可以用 求和 的方式估计期望
    • 多变量函数的期望,需要使用下标来表明被平均的是哪个变量
    • 条件分布的条件期望 (conditional expectation)
  • 方差 (variance):度量了函数在均值附近变化性的大小。
    • 协方差 (covariance):度量两个随机变量之间的关系
      • 如果两个随机变量相互独立,则它们的协方差为 0.
  • 经典概率论
    • 概率:就是随机重复事件发生的频率。
  • Bayesian 概率
    • 概率:提供了不确定性的一个定量化描述。
    • 后验概率 ∝ 似然函数 × 先验概率
    • 似然函数
      • 似然函数:由观测数据集 D 来估计,可以被看成参数向量 w 的函数。
      • 频率派认为参数的值是一种固定的数字,可以通过某种形式的“估计”来确定;
        • 广泛使用最大似然估计 (maximum likelihood estimator, MLE) [Duda, 2003] P68
        • 函数的负对数被叫做误差函数,最大化似然函数等价于最小化误差函数
      • Bayesian 派认为参数的不确定性通过概率分布来表达。
        • 取样方法:MCMC(C11)
        • 判别方法:变分贝叶斯 (Variational Bayes) 和期望传播 (Expectation Propagagtion)
  • 高斯分布(Gaussian distribution),也叫正态分布 (normal distribution)。(各种分布的详细情况参考 C02)
    • 控制参数:均值 μ 和方差 σ^2 ,标准差 σ ,精度 β (precision)
      • 期望就是均值 μ
      • 分布的最大值叫众数,与均值恰好相等。
    • 多维向量的高斯分布:均值向量和协方差矩阵
    • 独立地从相同数据点集合中抽取的数据被称为独立同分布 (independent and identically distributed, i.i.d.)
    • 最大似然估计未知的参数 μ 和 σ^2
      • 在给定的数据集下最大化参数的概率 v.s. 在给定参数下最大化数据集的概率。
      • 最大似然的偏移问题是多项式曲线拟合问题中遇到的过拟合问题的核心。
        • 最大似然求得的均值与样本均值相同;
        • 最大似然求得的方差比样本方差要小。
      • 最大化后验概率等价于最小化正则化的平方和误差函数

S1.4. 模型选择

  • 交叉验证 (cross validation) 和留一法 (leave-one-out) 可以解决验证模型时面临的数据不足问题。但是会增加训练成本。
  • 模型表现的度量的信息准则
    • 赤池信息准则 (Akaike information criterion,AIC)
    • 贝叶斯信息准则 (Bayesian information criterion, BIC)
  • 维度灾难
    • 在高维空间中,一个球体的大部分的体积都聚焦在球体表面附近的薄球壳上。(可以推导公式理解)
    • 在高维空间中,大部分的数据都集中在薄球壳上导致数据无法有效区分,称为维度灾难 (curse of dimensionality)
  • 解决方案
    • 真实数据经常被限制在有着较低的有效维度的空间区域中;(通过特征选择降维)
    • 真实数据通常比较光滑(至少局部上比较光滑)(通过局部流形降维)

S1.5. 决策论

  • 决策论:保证在不确定性的情况下做出最优的决策。
    • 从训练数据集中确定输入向量 x 和目标向量 t 的联合分布是推断 (inference) 问题
  • 分类问题的决策
    • 最小化错误分类率
      • 输入空间根据规则切分成不同的区域,这些区域被称为决策区域。
      • 决策区域间的边界叫做决策边界 (decision boundary) 或者决策面 (decision surface)。
    • 最小化期望损失
      • 损失函数 (loss function) 也称为代价函数 (cost function)
        • 目标是最小化整体的损失。
      • 效用函数 (utility function)
        • 目标是最大化整体的效用。
    • 拒绝选项 (reject option):避免做出错误的决策,可以使模型的分类错误率降低。
    • 分类问题的两个阶段
      • 推断 (inference):使用训练数据学习 p(C_k x) 的模型;
      • 决策 (decision):使用后验概率进行最优的分类。
      • 同时解决两个阶段的问题,即把输入直接映射为决策的函数称为判别函数 (discriminant function)
      • 显式或者隐式地对输入以及输出进行建模的方法称为生成式模型 (generative model)
        • 使用后验概率进行决策的理由
          • 最小化风险
          • 拒绝选项
          • 补偿类先验概率
          • 组合模型(参考 C14)
  • 回归问题的损失函数
    • 解决回归问题的三种方法(建议从机器学习参考书中熟悉这三种方法)
      • 先求联合概率密度,再求条件概率密度,最后求条件均值;
      • 先解决条件概率密度的推断问题,再求条件均值;
      • 直接从训练数据中寻找一个回归函数
    • 平方损失函数的一种推广,闵可夫斯基损失函数 (Minkowski loss)

S1.6. 信息论

  • 无噪声编码定理 (noiseless coding theorem):熵是传输一个随机变量状态值所需要的比特位的下界。
    • (推导过程值得理解,没有深入讨论的部分可以跳过)
  • 离散随机变量的熵 (entropy)
    • 最大熵值产生于均匀分布
  • 连续随机变量的熵(微分熵)
    • 具体化一个连续变量需要大量的比特位
    • 最大化微分熵的分布是高斯分布
    • 微分熵可以为负
    • 在给定 x 的情况下,y 的条件熵
  • 相对熵 (relative entropy) 或者 KL 散度 (Kullback-Leibler divergence)(推导过程建议理解)
    • 凸函数和严格凸函数 (strictly convex function),函数的二阶导数处处为正
    • 凹函数和严格凹函数 (strictly concave function)
    • KL 散度是两个分布之间不相似程度的度量。
      • Laplace 近似是用其中一个方便计算的分布去逼近另一个不方便计算的分布。(S4.4)
    • 最小化 KL 散度等价于最大化似然函数。
    • 互信息 (mutual information):表示一个新的观测 y 造成的 x 的不确定性的减小。

S01. 小结

  • 本章对于后面需要的重要概念都进行了说明和推导,方便深入理解后面提及的各种算法。
  • 如果看完本章后感觉充斥着许多新的概念,那么建议先放下,找本更加基础的模式识别与机器学习的书,例如:李航的《统计学习方法》和周志华的《机器学习》等。

C02. 概率分布

S02. 前言

  • 重点
    • 密度估计
      • 充分统计量
    • 高斯分布(建议读者熟悉操作高斯分布)
  • 难点
    • 贝叶斯估计
    • 多元高斯分布
    • 指数族分布
    • 共轭分布
      • 共轭先验分布
      • 超参数
  • 学习要点
    • 密度估计 (density estimation):在给定有限次观测 $x_1,\cdots,x_N$ 的前提下,对随机变量 x 的概率分布 p(x) 建模。
      • 参数密度估计:对控制概率分布的参数进行估计。
        • 最大似然估计:最优化似然函数在确定参数的具体值。
        • 顺序估计:利用充分统计量,在线进行密度估计。
          • 充分统计量 (sufficient statistic):最大似然估计的解只通过一个统计量就可以满足对数据的依赖,这个统计量就是充分统计量。
        • 贝叶斯估计:引入参数的先验分布,再来计算对应后验概率分布。
      • 非参数 (nonparametric) 密度估计:分布的形式依赖于数据集的规模。
        • 直方图:最基本的估计方法,但是在高维度问题中无法应用。
        • 核密度估计:固定区域 V 的大小,统计区域内的数据点个数 K,利用平滑的核函数,从而得到光滑的概率分布模型。
        • K 近邻估计:固定区域内的数据点个数 K,计算区域 V 的大小。不是真实的概率密度模型,因为它在整个空间的积分是发散的。
          • 最近邻估计:默认 K 为 1 时就是最近邻规则。
      • 对比:参数密度估计需要假设准备估计的概率分布是什么,如果估计错误就没办法得到正确的结果;而非参数估计则不需要进行这种假设。(深入了解参考 [Andrew, 2004] C03, [Duda, 2003] C04)
      • 学习方式
        • 离线学习,也叫批量学习。所有数据一次性采集完成后,对所有数据进行学习。
        • 在线学习,也叫顺序学习。数据无法一次性采集得到,需要随着时间片按顺序得到,学习的结果也需要随着时间发生改变。
    • 参数分布 (parametric distribution):少量可调节的参数控制了整个概率分布。
      • 先验分布 (prior):设定的参数的先验分布,参数可以看成先验分布中假想观测的有效观测数。
        • 共轭先验 (conjugate prior):使得后验分布的函数形式与先验概率相同,从而使贝叶斯分析得到简化。
          • Gamma 函数:(P48,习题 1.17)
          • 超参数:控制着参数的概率分布。
        • 无信息先验 (noninformative prior):对先验分布几乎无知,需要寻找一个先验分布,能够对后验分布产生尽可能少的影响。
      • 后验分布 (posterior):加入先验分布信息的概率分布,用于贝叶斯估计需要。
    • 指数族分布 (exponential family):具有指定的指数形式的概率分布的集合。
      • 二项分布与 Beta 分布共轭
      • 多项式分布与 Dirichlet 分布共轭
      • 高斯分布与高斯分布共轭
        • 条件高斯:如果两组变量是联合高斯分布,那么以一组变量为条件,另一组变量同样也是高斯分布。
        • 边缘高斯:如果两组变量是联合高斯分布,那么任何一个变量的边缘分布也是高斯分布。
      • 混合分布 (mixture distribution) 模型:将多个基本概率分布进行线性组合形成的分布。
        • 混合高斯 (mixture of Gaussians):将多个高斯分布进行线性组合形成的分布。每一个高斯概率密度称为混合分布中的一个成分。
        • 学生 t 分布:表现为无限多个同均值不同精度的高斯分布的叠加形成的无限高斯混合模型。比普通高斯分布具有更好的“鲁棒性”。
      • 周期概率分布:用于描述具有周期性质的随机变量。
        • von Mises 分布:也称为环形正态分布 (circular normal)。是高斯分布对于周期变量的推广。

离散分布

S2.1. 二元变量

  • 伯努利分布 (Bernoulli distribution),也称为二项分布 (binomial distribution):
  • Beta 分布是 Bernoulli 分布的共轭分布。

S2.2. 多项式变量

  • “1-of-K”表示法:变量被表示成一个 K 维向量 x,向量中的一个元素 x_k 等于 1,剩余的元素等于 0.
  • Dirichlet 分布是多项式分布的共轭分布。

连续分布

S2.3. 高斯分布

  • 高斯分布,也称为正态分布。
    • 由两个参数控制:均值μ和方差σ^2,或者精度λ=1/σ。
  • 中心极限定理 (central limit theorem):一组随机变量之和的概率分布随着项的数量的增加而逐渐趋向高斯分布。
  • 高斯分布的局限性
    • 多元高斯分布中自由参数的数量随着维数的平方增长。
    • 高斯分布是单峰的,不能很好地描述多峰分布。
  • 高斯分布的贝叶斯推断
    • 一元高斯随机变量
      • 均值未知,方差已知,均值的先验可以选高斯分布。
      • 均值已知,精度未知,精度的先验可以选 Gamma 分布。
      • 均值未知,精度未知,与均值和精度相关的先验分布可以选正态 -Gamma 分布或高斯 -Gamma 分布。
    • 多元高斯随机变量
      • 均值未知,方差已知,均值的先验可以选高斯分布。
      • 均值已知,精度未知,精度的先验可以选 Wishart 分布。
      • 均值未知,精度未知,与均值和精度相关的先验分布可以选正态 -Wishart 分布或高斯 -Wishart 分布。
  • 学生 t 分布 (Student’s t-distribution)
    • 当自由度υ=1 时,t 分布就变成为柯西分布 (Cauchy distribution);
    • 当自由度υ→∞时,t 分布就变成为高斯分布。
    • 学生 t 分布可以通过将无限多个同均值不同精度的高斯分布相加得到,即可以表示成无限的高斯混合模型
    • 学生 t 分布有着比高斯分布更长的“尾巴”,因此具有很好的鲁棒性 (robustness),对于离群点 (outlier) 的出现不像高斯分布那么敏感。
  • 周期变量
    • von Mises 分布:也叫环形正态分布 (circular normal distribution),是高斯分布对于周期变量的推广。
    • 建立周期概率分布的方法
      • 直方图:极坐标被划分成大小固定的箱子。优点是简洁并且灵活。
      • 类似于 von Mises 分布:考察欧几里得空间的高斯分布,在单位圆上做积分,使概率分布的形式相比直方图要复杂。
      • 在实数轴上的任何合法的分布都可以转化成周期分布。持续地把宽度为 2π的敬意映射为周期变量 (0,2π),使概率分布的形式相比于 von Mises 分布更加复杂。
    • 混合高斯模型
      • 混合模型 (mixture distribution):通过将基本的概率分布进行线性组合叠加形成概率模型。
      • 一元混合高斯 (mixture of Gaussians):K 个高斯概率密度的叠加形成混合高斯模型,每个高斯概率密度是混合分布的一个成分。
        • 从贝叶斯的角度,可以把每个高斯概率密度的混合系数看成选择这个成分的先验概率,后验概率可以被称为责任。
        • 利用最大似然法可以用于确定一元混合高斯模型中的各个参数。
      • 多元混合高斯:参数的最大似然解不再有一个封闭形式的解析解。求解方式有以下两种方法
        • 迭代数值优化方法
        • 期望最大化方法

S2.4. 指数族分布

  • 指数族 (exponential family) 分布
    • Bernoulli 分布:转化成指数族分布形式,归一化指数为 Logistic Sigmoid 函数;
    • 一元多项式分布:转化成指数族分布形式,归一化指数为 Softmax 函数;
    • 一元高斯分布:转化成指数族分布形式
  • 最大似然充分统计量:(方案两个概念都很重要,需要真正理解,因为后面会大量出现)
  • 共轭先验:对于给定的概率分布,寻找一个先验使其与似然函数共轭,从而后验分布的函数形式与先验分布相同。
    • 指数族分布中的任何分布,都存在一个共轭先验。
    • 从贝叶斯的角度,参数υ可以看成先验分布中假想观测的有效观测数。
  • 无信息先验 (noninformative prior)
    • 能够对后验分布产生尽可能小的影响。
    • 当先验分布是常数时存在的问题
      • 如果聚会的范围是无界的,那么先验分布无法被正确地归一化。这样的先验分布被称为反常的 (improper)
      • 概率密度分布中变量的非线性变换,使得最初的先验分布经过变换后不再是常数。
    • 先验分布的两个例子
      • 具有平移不变性 (translation invariance) 的概率分布
      • 具有缩放不变性 (scale invariance) 的概率分布

S2.5. 非参数化密度估计

  • (这个不是本书重点,作者描述的不多,深入了解可参考 [Andrew, 2004] C03 和 [Duda, 2003] C04)
  • 概率密度建模的参数化方法
    • 利用数据估计有参数的概率分布的形式
    • 需要确定数据的概率分布形式,如果形式估计错误,那么估计的结果也无法正确。
  • 概率密度建模的非参数化方法
    • 不需要确定数据的概率分布形式
    • 密度估计的直方图方法
      • 一旦直方图被计算出来,数据本身就可以丢弃,适合面对大数据量的情况。
      • 直方图方法也可以应用到数据顺序到达的情况。
    • 非参数概率密度估计的特点
      • 需要确定距离度量,方便计算某个领域内的数据点个数;
      • 为了更好地平衡概率密度的细节,需要注意领域的大小,类似于模型复杂度的确定。
    • 密度估计的通用形式
      • V 是区域 R 的体积
      • K 是区域 R 内数据点的个数
    • 密度估计的核密度方法
      • 固定 V,确定 K
      • 为了得到光滑的模型,选择一个核函数 (kernel function),即 Paren 窗。
      • 不需要进行训练阶段的计算
      • 估计概率密度的计算代价随着数据集的规模线性增长。
    • 密度估计的近邻方法
      • 固定 K,确定 V
      • 解决核方法中核固定的问题
      • K 近邻法得到的模型不是真实的概率密度模型,在整个空间的积分是发散的。
    • 基于树的搜索结构,解决概率密度估计方法需要存储整个训练数据集的问题。

S02. 小结

这章看起来是基础知识的介绍,实际上是对后面知识的梳理。如果这章看完有太多不理解的内容,再次建议先补充统计学习的基础,否则作者不断提到通过贝叶斯角度来理解机器学习的目的就无法实现了。

C03. 回归的线性模型

S03. 前言

  • 重点
    • 线性基函数模型 (S3.1)
    • 贝叶斯线性回归 (S3.3)
    • 二次正则化项 (E3.27)
  • 难点
    • 贝叶斯模型比较 (S3.4)
    • 证据近似 (S3.5)
  • 学习要点
    • 回归问题:在给定 D 维输入变量 x 的情况下,预测一下或者多个连续目标变量 t 的值
    • 线性回归模型:具有可调节的参数,具有线性函数的性质。
      • 输入变量的线性函数:最简单的形式是输入变量的线性函数;
      • 参数的线性函数:将一组输入变量的非线性函数(基函数)进行线性组合
        • 依然具有简单的分析性质;
        • 同时关于输入变量是非线性的。
        • 非线性变换不会消除数据中的重叠,甚至还可能增加重叠的程度或者在原始观测空间中不存在重叠的地方产生出新的重叠。
        • 恰当地选择非线性变换可以让后验概率的建模过程更加简单。

S3.1. 线性基函数模型

  • 线性回归 (linear regression):回归问题的最简单模型是输入变量的线性组合。
    • 基函数 (basis function):输入变量设置为固定的非线性函数。
      • 多项式基函数:x 的幂指数形式。
        • 局限性:输入变量的全局函数,因此对于输入空间中一个区域的改变将会影响所有其他的区域。
        • 样条函数 (spline fuunction):把输入空间切分成若干个区域,然后对于每个区域用不同的多项式函数拟合。
      • 高斯基函数
      • Sigmoid 基函数 +Logistic Sigmoid 函数
      • Fourier 基函数
        • 小波 (wavelet) 基函数
    • 偏置参数 (bias parameter):使得数据中可以存在任意固定的偏置。
      • 定义一个虚“基函数”,简化数学模型。
  • 平方和误差函数 等价于 高斯噪声模型的假设下的最大似然解。
    • 最小平方问题的规范方程 (normal equation)(参考 S1.2.5)
      • 设计矩阵及 Moore-Penrose 伪逆矩阵 (pseudo-inverse matrix)。
      • 偏置补偿了目标值的平均值(在训练集上的)与基函数的值的平均值的加权求和之间的差。
      • 噪声精度的倒数是目标值在回归函数周围的残留方差 (residual variance)
    • 最小平方的几何描述
      • 平方误差函数是 y 和 t 之间的平方欧氏距离。
      • y 是 t 在子空间 S 上的正交投影。
    • 顺序学习、在线学习
      • 随机梯度下降 (stochastic gradient descent) 也被称为顺序梯度下降 (sequential gradient descent)
    • 正则化最小平方
      • 数据相关的误差 $E_D(w)$
      • 正则化项 $E_W(w)$
        • 权向量的各个元素的平方和
        • 正则化项的选择方法,在机器学习的文献中被称为权值衰减 (weight decay)
          • 在顺序学习算法中,权值向零的方向衰减
        • 正则化项的选择方法,在统计学习中称为参数收缩 (parameter shrinkage)
          • 在顺序学习算法中,参数的值向零的方向收缩
        • 更加一般的正则化项
          • q=1 的情形被称为套索 (lasso),性质为:如果 λ 充分大,那么某些系数会变为零,从而产生一个稀疏 (sparse) 模型。
        • 正则化方法通过限制模型的复杂度,使得复杂的模型在有限大小的数据集上进行训练,而不会产生严重的过拟合问题。
          • 使得确定最优的模型复杂度的问题从确定合适的基函数数量的问题转移到了确定正则化系数λ的合适值的问题。
      • λ是正则化系数
  • 多个输出:预测多于 1 个目标变量的数据
    • 对于t的每个分量,引入一个不同的基函数集合,从而多个独立的回归问题;
    • 对目标向量的所有分量使用一组相同的基函数来建模
      • 假设目标向量的条件概率分布是一个各向同性的高斯分布
      • 不同目标变量的回归问题被分解成多个单目标变量的回归问题。

S3.2. 偏置—方差分解

  • 模型复杂度问题
    • 频率学家的角度是偏差—方差折中 (bias-variance trade-off)
  • 平方损失函数展开后得:期望损失 = $ 偏置 ^2$ + 方差 + 噪声 $
    • 平方偏置:表示所有数据集的平均预测与预期的回归函数之间的差异;
    • 方差:度量了对于单独的数据集,模型所给出的解在平均值附近变化的情况
    • 噪声:数据上叠加的常数噪声项。
    • 目标:最小化期望损失,取得最优的平衡的模型
      • 灵活的模型,偏置较小,方差较大。
      • 固定的模型,偏置较大,方差较小。

S3.3. 贝叶斯线性回归

  • 参数分布:引入模型参数 w 的先验概率分布
    • 假定噪声精度参数β为已知常数
    • 参数 w 受精度参数α控制
    • 后验分布关于 w 的最大化 等价于 对平方和误差函数加上一个二次正则化项进行最小化。
  • 预测分布 (predictive distribution):用于通过新的 x 值预测出 t 的值。
  • 等价核(如何理解核方法?)
    • 等价核 (equivalent kernel) 也称为平滑矩阵 (smoother matrix)
      • 线性平滑 (linear smoother):通过对训练集里目标值进行线性组合做预测。
      • 等价核定义了模型的权值,距离 x 较近的数据点可以赋予一个较高的权值,距离 x 较远的数据点可以赋予一个较低的权值。
      • 附近的点预测均值相关性较高,远处的点预测均值相关性较低。
      • 等价核可以表示为非线性函数的向量的内积的形式
    • 用核函数表示线性回归模型的方法
      • 线性基函数模型的后验均值可以解释为核方法,即隐式地定义了一个等价核
      • 直接定义一个局部的核函数,然后在给定观测数据集的条件下,使用这个核函数对新的输入变量 x 做预测,这个框架称为高斯过程 (Gaussian process)

S3.4. 贝叶斯模型比较

  • 如果理解有困难,还可以参考 [Duda, 2003] C09.P392
  • 从贝叶斯的角度考虑模型选择问题
    • 模型证据 (model evidence) 也叫边缘似然 (marginal likelihood)
      • 贝叶斯因子 (Bayes factor) 是两个模型的模型证据的比值
    • 模型有一个参数的情形
      • 第一项表示拟合由最可能参数给出的数据
      • 第二项用于根据模型的复杂度来惩罚模型
    • 模型有 M 个参数的情形
      • 复杂度惩罚项的大小随着模型中可调节参数 M 的数量线性增加
  • 最优评估方式:保留一个独立的测试数据集。

S3.5. 证据近似

  • 因为无法对模型证据中所有的变量完整地求积分,因此使用近似方法。这个框架在统计学中称为经验贝叶斯 (empirical Bayes) 或者第二类最大似然 (type 2 maximum likelihood) 或者推广的最大似然 (generalized maximum likelihood),在机器学习中称为证据近似 (evidence approximation)。
    • 首先对参数 w 求积分,得到边缘似然函数 (marginal likelihood function)
    • 然后通过最大边缘似然函数,确定超参数的值。
  • 最大化对数证据
    • 解析地计算证据函数。然后令其导数为零,得到对于超参数的重新估计方程;
    • 期望最大化 (EM) 算法。
  • 证据函数的计算与最大化(有点难,建议手工推导,看懂图的含义,对于理解贝叶斯模型比较有帮助)

S3.6. 固定基函数的局限性

  • 基函数的数量随着输入空间的维度 D 的增长而呈指数方式增长。(参考 S1.4.)
  • 真实数据集的两个性质
    • 数据向量通常位于一个非线性流形内部,由于输入变量之间的相关性,流形本身的维度小于输入空间的维度
      • 使用局部基函数,基函数只分布在输入空间中包含数据的区域。
        • 径向基函数网络
        • 支持向量机和相关向量机
        • 神经网络使用可调节的基函数,通过调节参数使基函数会按照数据流形发生变化。
      • 目标变量可能只依赖于数据流形中的少量可能的方向。

S03. 小结

这章的标题在许多模式识别与机器学习的书中都见过,但是作者采用贝叶斯和核函数的视角来分析和解释这个模型,使模型的理解难度加大,但是对于知识的扩展和补充也很有裨益。如果对贝叶斯方法了解不足,可以参考 [Duda, 2003] 和 [Andrew, 2004],虽然这些书中的内容并不能减轻阅读这一章的难度,但是至少可以为理解贝叶斯方法打下基础。

C04. 判别的线性模型

S04. 前言

  • 重点
    • 广义的线性模型
    • 概率模型(注意公式的推导)
      • 概率生成式模型 (S4.2)
      • 概率判别式模型 (S4.3)
    • 迭代重加权最小平方
    • Laplace 近似
  • 难点
    • Logistic 回归模型
    • Probit 回归模型
    • 贝叶斯 Logistic 回归模型
    • 迭代重加权最小平方
    • Laplace 近似
  • 学习要点
    • 分类的目标是将输入变量 x 分到 K 个离散的类别 C_k 中的某一类
      • 类别互相不相交,因此每个输入被分到唯一的一个类别中
      • 输入空间被划分为不同的决策区域 (decision region)
      • 决策区域的边界被称为决策边界 (decision boundary) 或者决策面 (decision surface)
    • 分类线性模型:是指决策面是输入向量 x 的线性函数
      • 因此决策面被定义 D 维输入空间中的 (D-1) 维超平面
      • 线性可分:表示这个数据集可以被线性决策面精确分类
    • 解决分类问题的三种不同方法
      • 构造判别函数,直接把向量分到具体的类别中
      • 直接对条件概率分布建模,使用训练集来最优化参数
      • 生成式的方法,对类条件概率密度以及类的先验概率分布建模,然后使用贝叶斯定理计算后验概率分布
    • 广义的线性模型 (generalized linear model, GEM)
      • 在机器学习的文献中,f(.) 称为激活函数 (activation function),它的反函数在统计学中称为链接函数 (link function)

S4.1. 判别函数

  • 二分类问题
    • 线性判别函数最简单的形式是输入向量的线性函数
      • 权向量,偏置阈值
  • 多分类问题
    • 解决方案
      • “1 对 多”,(K-1) 个二元判别函数,每个函数将属于类别 C_k 的类和不属于类别 C_k 的类分开。产生了输入空间中无法分类的区域。
      • “1 对 1”,K(K-1)/2 个二元判别函数,对每一个类别都设置一个判别函数。还会存在输入空间中无法分类的区域。
      • K 类判别函数,由 K 个线性函数组成,x 在哪个类别中结果最大就判定在哪个类别中。
  • 学习线性判别函数的参数的方法
    • 基于最小平方的方法:对于离群点缺少鲁棒性。
    • Fisher 线性判别函数:也叫 LDA(线性判别分析)(参考 [Duda, 2003] P96,\【周志华,2018] P60)
      • 目的:将 D 维输入向量投影到一维空间进行分类
        • 思想:最大化一个函数,让类间差较大,类内差较小。
      • 与最小平方的关系
        • 最小平方方法的目标是使模型的预测尽可能地与目标值接近;
        • 线性判别函数的目标是使输出空间的类别有最大的区分度。
        • 对于二分类问题,线性判别准则可以看成最小平方准则的特例。
    • 感知器算法
      • 广义的线性模型
      • 学习准则是:误差函数最小化
        • 不保证在每个阶段都会减小整体的误差函数;
        • 如果存在一个精确的解,算法保证在有限的步骤内找到。
        • 数据集是线性可分的,也可能出现多个解,具体的解依赖于参数的初始化和数据出现的顺序;
        • 数据集是线性不可分的,算法永远无法收敛。
        • 算法无法提供概率形式的输出,也无法直接推广到多于 2 个类别的情形。

S4. 模型

  • 概率生成式模型:间接方法
    • 分别寻找类条件概率密度的参数和类别先验
    • 使用贝叶斯定理,寻找后验概率
  • 概率判别式模型:直接方法
    • 显式地使用广义线性模型的函数形式
    • 最大化由条件概率分布定义的似然函数
    • 通过最大似然法直接确定参数
    • 通过迭代重加权最小平方
    • 优点:有更少的可调节参数需要确定

S4.2. 概率生成式模型

  • 输入数据是连续值
    • 最大似然解
  • 输入数据是离散值
  • 指数族分布:建立一个更加通用的模型

S4.3. 概率判别式模型

  • 固定基函数:通过一个基函数向量对输入变量进行非线性变换
    • 原始空间中的非线性决策边界在非线性变换后的特征空间中是线性的。
    • logistic 回归:使用最大似然方法来确定 logitstic 回归模型中的参数。(参考 \【周志华,2018] P57,\【李航, 2012] C06)
      • 二分类问题:后验概率由特征变量的线性函数的 logistic sigmoid 函数给出;
      • 多分类问题:后验概率由特征变量的线性函数的 softmax 函数给出;
        • 多类 logistic 回归模型的 Hessian 矩阵是正定的,因此误差函数有唯一解。
    • 迭代重加权最小平方(Iterative reweighted least squares,IRLS)
      • 因为 logistic sigmoid 函数或者 softmax 函数是非线性函数,所以 logistic 回归不再有解析解
      • 误差函数是凸函数,所以存在唯一解;
      • 误差函数需要通过迭代方法得到唯一解;
        • 迭代方法基于 Newton-Raphson 迭代最优化框架
        • 使用对数似然函数的局部干净近似
    • probit 回归
      • 目标变量的条件分布来自于非指数族分布,可以使用逆 probit 函数描述后验概率的函数形式。
    • 标准链接函数
      • 目标变量的条件分布来自于指数族分布,对应的激活函数选择标准链接函数

S4.5. 贝叶斯 Logistic 回归

  • 对于 Logistic 回归,精确的贝叶斯推断是无法处理的,可以考虑使用 Laplace 近似来解决。
    • Laplace 近似
      • 目标是找到定义在一组连续随机变量上的概率密度的高斯近似
      • 可以推广到 M 维空间上连续随机变量的概率密度的高斯近似
      • 近似过程:寻找众数,然后计算众数位置上的 Hessian 矩阵。
      • 主要缺点
        • 以高斯分布为基础,只能直接应用于实值变量;
        • 完全依赖于真实概率分布在变量的某个具体值位置上的性质,无法描述一些重要的全局属性。
      • 还可以对归一化常数进行近似
        • 对证据函数进行近似 (P121)
    • 用于预测值的分布
      • 逆 probit 函数可以表示一个逆 probit 函数与高斯分布的卷积。

S04. 小结

此章内容相对较难,作者试图通过统计学的角度来阐述判别模型,后面的学习中会反复用到本章中提及的概率模型和优化算法,如果无法深入理解也尽量掌握算法的核心思想(即应用的范围)。

C05. 神经网络

S05. 前言

  • 重点
    • 前向传播的神经网络函数
  • 难点
    • Hessian 矩阵的逼近。
  • 学习基础
    • 固定基函数
      • 回归模型:(C03)
      • 分类模型:(C04)
  • 学习要点
    • 可调节基函数
      • 支持向量机:(C07)(选择不同的基函数)
        • 定义一个以训练数据点为中心的基函数集合
        • 在训练过程中从定义的基函数集合中选择一个基函数子集
        • 优点
          • 目标函数是凸函数,虽然训练阶段涉及到非线性优化
          • 相对直接地得到最优问题的解,最优解中基函数的数量远小于训练数据点的数量
      • 相关向量机:(S7.2)
        • 选择固定基函数的一个子集
        • 生成一个相当稀疏的模型
        • 产生概率形式的输出,以训练阶段的非凸优化为代价
      • 神经网络:(C06)(相同的基函数,不同的基函数的参数)
        • 使用参数形式的基函数,参数可以在训练阶段调节
        • 最终模型相当简洁,计算速度更快,可以快速地处理新的数据。
    • 神经网络学习点
      • 神经网络的函数形式
        • 基函数的具体参数
      • 使用最大似然框架确定神经网络参数
        • 非线性最优化问题
        • 如何使用误差反向传播算法取得神经网络参数的导数
          • 如何使用误差反向传播算法取得其他的导数
            • Jacobian 矩阵
            • Hessian 矩阵
      • 神经网络训练的正则化方法,以及方法之间的联系
      • 混合密度网络
        • 对条件概率密度建模
      • 基于贝叶斯观点的神经网络,具体可以参考 [Bishop,1995]

S5.1. 前馈神经网络

  • 前向传播的神经网络函数(熟练地使用这些公式将有助于后面的推导)
  • 多层感知器 (Multilayer Perceptron,MLP) 与感知器模型的区别
    • 多层感知器:也叫神经网络,在隐含单元中使用连续的 sigmoid() 非线性函数。(带有连续的非线性性质)
      • 函数关于参数是可微的。
    • 感知器模型:在输出单元使用阶梯函数 sgn() 这一非线性函数。(带有非连续的非线性性质)
  • 权空间对称性
    • 因为激活函数的对称性导致权空间中解的对称性
      • 这种对称性几乎没有什么实际的用处
    • 对于 M 个隐含单元,任何给定的权向量都是权空间中 $2^M$ 个等价的权向量中的一个。
    • 因为隐含单元的连接有 $M!$ 种可能,所以每个隐含层单元的整体权空间对称性因子是 $M!\times{2^M}$
    • 对于多于两层的网络,$y=\underset{i}{\prod} x_i$,$y$ 是对称性因子总数,$x_i$ 第 $i$ 层隐含单元的对称性因子数。

S5.2. 网络训练

  • 网络训练的本质就是确定参数
    • 确定参数的本质就是基于最优化理论对误差函数求极值。
  • 关键问题是:输出单元的激活函数 $f(\cdot)$ 和 对应的误差函数 $E(\mathbf{w})$
    • 回归问题:$f(\cdot)$ 为恒等函数 $f(\mathbf{x})=\mathbf{x}$ 和 $E(\mathbf{w})$ 为平方和误差函数
      • 一元目标变量:最小化误差函数等价于最大化似然函数
      • 多元目标变量:假设目标变量之间相互独立
    • 分类问题
      • 二元分类问题:$f(\cdot)$ 为 Logistic Sigmoid 函数和 $E(\mathbf{w})$ 为交叉熵误差函数
        • 一个二元分类问题的解决方案
          1. 单一的 Logistic Sigmoid 输出
          2. 使用神经网络,神经网络有两个 Softmax 输出。
        • K 个相互独立的二元分类问题
      • 多元分类问题:$f(\cdot)$ 为 Softmax 函数和 $E(\mathbf{w})$ 为多分类交叉熵误差函数
      • 【注】交叉熵误差函数比平方和误差函数,训练速度更快,泛化能力更强。
  • 参数最优化:(如果你对最优化不熟悉,建议参考 \【袁亚湘, 1997];如果很熟悉,则可以浏览一下)
    • 泰勒展开:局部二次近似
      • 使用梯度信息构成了训练神经网络的基础。
      • 批量最优化算法(一次处理批量的数据)
        • 梯度下降法,也叫最陡峭下降法,最速下降法。权值向量沿着误差函数下降速度最快的方向移动。因为每一步需要处理整个数据集,所以这个算法的实际效果很差,建议使用其他批量最优化算法。
        • 其他批量最优化算法的共同性质:误差函数在每次迭代时总是减小的,除非权向量到达了局部或者全局的最小值。
          • 共轭梯度法
          • 拟牛顿法
      • 在线最优化算法(一次处理一条数据,常用于在线数据处理)
        • 在线梯度下降,也叫顺序梯度下降,随机梯度下降。权向量的更新每次只依赖于一个数据点。
        • 可以更加高效地处理数据中的冗余性。
        • 可以逃离局部极小值点。

S5.3. 误差反向传播

  • 误差反向传播 (Error Backporrogpagation):也叫反传 (backprop),其目的是为了寻找一种高效算法,用于计算前馈神经网络的误差函数 $E(\mathbf{w})$ 的梯度,因此利用局部信息传递的思想,使得信息在神经网络中交替地向前和向后传播。
  • 反向传播方法的两个阶段
    • 计算误差函数关于权值的导数;
      • 为了计算导数而采用的误差在网络中反向传播方法可以应用于许多其他各类的网络;
    • 导数的计算结果用于调整网络的权值。
      • 通过许多最优化方法可以处理调整网络权值的工作。
  • 反向传播方法的重要贡献:为了 高效地 计算误差函数关于权值的导数,从而导致误差在神经网络中反向传播。
  • 误差函数导数的计算,即反向传播算法的流程(建议能够熟练地推导)
    • 对于网络的一个输入向量进行正向传播,找到所有隐含单元和输出单元的激活;
    • 计算所有输出单元的误差;
    • 反射传播输出单元的误差,获得网络中所有隐含单元的误差;
    • 计算导数。
  • 影响反向传播的计算效率的因素
    • 正向传播的计算复杂度(即求和式的计算)+ 激活函数的计算
  • 反向传播的应用(建议不理解就跳过,内容只是帮助深入理解 BP 算法)
    • Jacobian 矩阵的求导
    • Hessian 矩阵的计算
      • Hessian 矩阵的对角化近似,方便求得逆矩阵;
      • Hessian 矩阵的外积近似,即 Levenberg-Marquardt 近似,可以得到一个求解逆矩阵的高效方法;
      • 使用有限差计算 Hessian 矩阵,可以用于检查反向传播算法执行的正确性;
      • Hessian 矩阵的精确计算:利用反向传播算法计算一阶导数的推广,同时也保留了计算一阶导数的许多良好的性质。
      • Hessian 矩阵的快速乘法,不再关注求得 Hessian 矩阵本身,而是某个向量与矩阵的乘积。
  • 神经网络的正则化
    • 寻找相容的高斯先验
      • 第 3 章讨论的正则化项可以表示为权值 $\mathbf{w}$ 上的零均值高斯先验分布的负对数。
      • 第 3 章讨论过的正则化项与神经网络映射的确定缩放性质不相容,所以需要为神经网络寻找相容的高斯先验。
        • 相容性要求两个网络是等价的,差别仅在于权值的线性变换。
          • 第一个网络是使用原始数据训练的;
          • 第二个网络是使用将原始数据经过线性变换后的结果数据训练的。
    • 提早停止网络训练
      • 非线性网络模型的训练对应于误差函数的迭代减小
        • 误差函数是关于训练数据集定义的
        • 误差函数是一个关于迭代次数的不增函数
      • 训练过程可以在验证集误差最小的时候停止
      • 网络的行为可以通过网络的自由度有效数量来定量描述
        • 自由度有效数量开始很小,随着训练过程中的增长,对应的模型复杂度也在持续增长。
        • 自由度有效数量的描述:$\tau\eta$(其中 $\tau$ 是迭代次数,$\eta$ 是学习率参数)
    • 满足不变性 (invariant) 的需要
      • 不变性的分类
        • 平移不变性 (translation invariance):位置的变化不影响结果;
        • 缩放不变性 (scale invariance):尺度的变化不影响结果。
      • 不变性的解决方案
        • 复制训练模式
          • 根据不变性的需要对训练集进行扩展;
          • 相对简单,但是计算开销大
          • 变换后的数据训练:与切线传播方法有密切的关系。
          • 通过添加随机噪声变换数据与 Tikhonov 正则化也有密切的关系。
        • 误差函数的正则化项
          • 惩罚当输入发生改变时,那些输出也发生改变的情况;
          • 保持了数据集的不变性
          • 切线传播 (tangent propagation):使用正则化来让模型对于输入的变换具有不变性
            • 当网络映射函数在每个模式向量的领域内具有变换不变性时,正则化函数等于零。
          • 切线距离 (tangent distance):用来构造基于距离的方法的不变性。
        • 抽取不变特征
          • 无论数据发生怎样的变化都不会影响到特征的稳定性,从而将不变性整合到预处理过程中;
          • 由于训练集中没有包含变换,所以使用外插时不受影响。
          • 寻找符合要求的特征难度较大。
        • 模型对不变性的整合
          • 将不变性整合到神经网络的构建过程中
            • 卷积神经网络
              • 在卷积层,各个单元被组织在一系列平面中,每个平面被称为一个特征地图 (feature map)。
                • 一个特征地图中的每个单元只从图像的一个小的子区域接收输入,且一个特征地图中的所有单元被限制为共享相同的权值。
                  • 构成了输出对于输入图像的平衡和变形的(近似)不变性的基础。
                • 卷积单元的输出构成了网络的下采样层的输入。
                  • 下采样层的单元的响应对于对应的输入空间区域中的图片的微小平移相对不第三。
              • 整合不变性的方法
                • 局部接收场
                • 权值共享
                  • 软权值共享:权值相等的硬限制被解放思想一种形式的正则化,其中权值的分组倾向于取近似的值。
                    • 权值的分组以及每组权值的均值和分组内的取值范围都在学习过程中确定。
                • 下采样
              • 解决了图像的关键性质(距离较近的像素的相关性要远大于距离较远的像素的相关性)
          • 将不变性整合到相关向量机的核函数中

S5.4. 混合密度网络 (mixture density network)

  • 起因
    • 在许多简单的回归问题中,条件概率分布 $p(\mathbf{t}\vert\mathbf{x})$ 假定为高斯分布;
    • 在许多逆问题中,条件概率分布可能是其他类型的分布,还可能是多峰的分布。
  • 方法
    • 为 $p(\mathbf{t}\vert\mathbf{x})$ 使用一个混合模型,模型的混合系数和每个分量的概率分布都是输入向量的一个比较灵活的函数,这就构成了混合密度网络。

S5.5. 贝叶斯神经网络

  • 在贝叶斯方法中,为了进行预测,需要对参数的概率分布进行积分或者求和。
    • 在多层神经网络中,网络函数对于参数值的高度非线性使得精确的贝叶斯方法不再可行。
    • 变分推断方法可以对后验概率的分解进行高斯近似(C10)
    • 最完整的贝叶斯方法是基于拉普拉斯近似的方法。(S5.7)
  • 拉普拉斯近似
    • 后验参数分布
      • 条件概率分布 $p(\mathbf{t}\vert\mathbf{x})$ 假定为高斯分布,使用拉普拉斯近似找到后验概率分布的高斯近似。
    • 超参数最优化
      • 使用拉普拉斯近似可以确定超参数的边缘似然函数,从而对超参数进行点估计。
  • 贝叶斯神经网络用于解决分类问题
    • 二分类问题(通过解决这个问题深入理解拉普拉斯近似在基于贝叶斯方法的神经网络回归模型中的应用)
    • 多分类问题

S05. 小结

如果需要深入了解神经网络,建议参考 [Haykin, 2011]。本书的重点只是引入 Bayes 观点的神经网络。

C06. 核方法

S06. 前言

  • 重点
    • 径向基函数
    • 高斯过程
  • 难点
    • 高斯过程
  • 学习基础
    • Laplace 逼近
    • 线性规划的对偶理论和 Lagrange
  • 学习要点
    • 通过将对偶性的概念应用于回归的非概率模型,引出了核的概念
    • 通过在概率判别式模型中使用核,引出了高斯过程的框架
    • 对偶表示:许多线性参数模型都可以转化为等价的“对偶表示”。
      • 对偶表示中,预测的基础是在训练数据点处计算的核函数的线性组合。
    • 核函数
      • 用特征空间的内积的方式表示核的概念,可以很方便的使用核技巧,或核替换。
      • 核函数的类别
        • 静止核:参数的差值的函数;对于输入空间的平移具有不变性。
        • 同质核:也叫径向基函数,只依赖于参数之间的距离的大小。

S6.1. 对偶表示

  • 对偶理论是研究线性规划中原始问题与对偶问题之间关系的理论。
    • 在线性规划早期发展中最重要的发现是对偶问题,即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题(称为对偶问题)。
    • 两零和对策可表达成线性规划的原始问题和对偶问题。
  • 对偶表示:许多回归的线性模型和分类的线性模型的公式都可以使用对偶表示重写。
    • 使用对偶表示形式,核函数可以自然地产生。
    • 对偶公式可以完全通过核函数来表示。可以隐式地使用高维特征空间,甚至无限维特征空间。
    • 许多线性模型都可以基于 Gram 矩阵实现对偶表示。

S6.2. 构造核

  • 构造合法的核函数的方法
    • 选择一个特征空间映射,通过这个映射寻找对应的核函数;
    • 直接构造核函数
      • 使用简单的核函数作为基本的模块来构造
    • 从概率生成式模型开始构造
      • 可以基于判别式框架使用生成式模型
        • 可以利用生成式模型处理缺失数据
        • 基于隐马尔可夫模型处理长度变化的序列
        • 可以在判别式的任务中充分利用判别式模型的优势
      • Fisher 核
      • Sigmoid 核:与神经网络模型有着表面的相似性
  • 检验构造出的核函数合法的充分必要条件是 Gram 矩阵在所有的集合下都是半正定的。
  • 常用的核函数
    • 多项式核
    • 高斯核
      • 高斯核还可以不局限于欧几里德距离
  • 核函数的输入
    • 符号
    • 实数

S6.3. 径向基函数网络

  • 径向基函数 (Radial Basis Functions)
    • 在基于固定基函数的线性组合的回归模型中,径向基函数是被广泛使用的基函数。
    • 径向基函数中每一个基函数只依赖于样本和中心之间的径向距离。
  • 径向基函数的应用
    • 精确的函数内插:能够精确拟合每个目标值的函数,但是容易对应过拟合的解
    • 输入变量具有噪声时的内插:应用变分法,得到以每个数据点为中心的基函数,这被称为 Nadaraya-Watson 模型。
    • 核密度估计在回归问题中的应用
  • 选择基函数的方法
    • 最简单的方法:使用数据点的一个随机选择的子集
    • 更加系统化的方法:正交最小平方法,这是一个顺序选择的过程
      • 在每一个步骤中,被选择作为基函数的下一个数据点对应于能够最大程度减小平方和误差的数据点
      • 展开系数值的确定是算法的一部分
  • Nadaraya-Watson 模型:以核密度的角度来研究核回归模型(P116 E3.61),也叫核回归 (kernel regression)。

S6.4. 高斯过程

  • 高斯过程:是函数 $y(\mathbf{x})$ 上的一个概率分布,使得在任意点集处计算的函数的值的集合联合起来服从高斯分布。
    • 如果输入变量是二维的情况下,也可以称之为高斯随机场。
    • 如果使用一种合理的方式为函数的值的集合赋予一个联合的概率分布,则可以确定函数 $y(\mathbf{x})$ 为这种分布的随机过程
      • 如果核函数定义为指数核,则函数对应于 Ornstein-Uhlenbeck 过程,用来描述布朗运动。
    • 高斯过程的参数
      • 均值默认取零
      • 协方差由高斯核函数来确定
        • 核函数的唯一的限制是协方差矩阵必须是正定的
    • 两个随机的独立的高斯分布,它们的协方差可以直接相加
  • 高斯过程应用于线性回归问题
    • 在高斯过程回归中,广泛使用的核函数的形式为指数项的二次型 + 常数 + 线性项(P216 E6.63)
    • 预测分布也是高斯分布
    • 与基于基函数的线性回归问题对比
      • 如果基函数的数量比数据点的数量小,那么使用基函数框架的计算效率会更高;
      • 面对无穷多的基函数表达的协方差函数,使用高斯过程才能处理。
    • 超参数的学习基于计算似然函数来完成
      • 通过最大化似然函数的方法进行超参数的点估计
        • 可以使用高效的基于梯度的优化算法(例如:共轭梯度法)来最大化似然函数
    • 自动相关性的确定 (Automatic Relevance Detemination, ARD)
      • 通过最大似然方法进行的参数最优化,能够将不同输入的相对重要性从数据中推断出来,这是高斯过程中的自动相关性确定。
      • ARD 框架很容易整合到 “指数—二次核” 中。
  • 高斯过程应用于分类模型
    • 分类问题
      • 二分类问题,使用 Logistic Sigmoid 函数
      • 多分类问题,使用 Softmax 函数
    • 通过使用一个合适的非线性激活函数,可以将高斯过程的输出进行变换
    • 预测分布无法得到解析解,获得高斯近似的方法
      • 变分推断 (Variational Inference)(S10.5.)
      • 期望传播 (Expectation Propagation)(S10.7.)
      • Laplace 近似(S4.4. 和 S4.5.)
        • 基于 Newton-Raphson 的迭代重加权最小平方(IRLS)算法(S4.3.)
  • 与神经网络的关系(看不懂
    • 在贝叶斯神经网络中,基于无穷多基函数的核函数网络产生的函数分布会趋于高斯过程,但是输出变量也会相互独立
    • 神经网络的优势之一是输出之间共享隐含单元,从而可以互相 “借统计优势”,这个性质在极限状态下的高斯过程中丢失了。

S06. 小结

这章是引入核方法和高斯过程,为下一章的稀疏核机(即 SVM)提供理论铺垫。理解核方法的引入,可以更自然地理解支持向量机的原理。理解高斯过程,可以更好地推导相关向量机。

C07. 稀疏核机

S07. 前言

  • 重点
    • 支持向量机 (Support Vector Machine, SVM)
    • 相关向量机 (Relevance Vector Machine, RVM)
  • 难点
    • 用于分类的 SVM
    • 用于回归的 RVM
  • 学习基础
    • 最优化理论
      • 二次规划
      • 对偶表示
      • Lagrange 函数
      • 松弛变量
    • SVM(支持向量机)
      • 支持向量
      • 边缘
    • Laplace 逼近
      • 高斯过程
    • 迭代重加权最小平方(IRLS)
  • 学习要点
    • SVM 是稀疏核算法,属于决策类算法,不提供后验概率,对新数据的预测只需要依赖于训练数据点上的一个子集上计算的核函数。
    • RVM 也是稀疏核算法,是基于贝叶斯方法的,能够提供后验概率输出的,具有比 SVM 更加稀疏的解的算法。

S7.1. 最大边缘分类器

  • 支持向量机中采用最大边缘解的理论基础
    • 计算学习理论 (Computational Learning Theory)
    • 统计学习理论 (Statistical Learning Theory)
    • 边缘 (Margin):定义为决策边界与任意样本之间的最小距离,决策边界与最近的数据点之间的垂直距离。
      • 决策边界被行为使边缘最大化的那个决策边界。
      • 最优超平面是有着最大边缘的超平面
        • 随着方差的减小,距离超平面较近的点对超平面的控制能力逐渐大于距离较远的点
        • 在极限情况下,超平面会变得与非支持向量的数据点无关
    • SVM 稀疏性的来源:边缘上的点被限制为激活;非边缘上的点限制为未激活。
  • SVM 中重叠数据的分类问题
    • 面对不能线性可分的数据进行精确划分会导致较差的泛化能力
      • 允许部分训练数据点被误分类,从而提高泛化能力
        • 位于正确的边缘边界内部的点或者边缘界上的点
        • 位于正确的边缘边界外部的点
        • 位于决策边界上的点
        • 被错误分类的点
      • 放宽边缘的硬限制,得到一个软边缘 (Soft Margin)
    • 训练 SVM 的方法
      • 限制条件定义一个凸区域,任意局部最优解也是全局最优解
      • 分块方法:将完全的二次规划问题分解为一系列小的二次规划问题
      • 顺序最小化优化 (Sequential Minimal Optimization)
  • 与 Logistic 回归的关系
    • 对于线性不可分的概率分布,用最小化正则化的误差函数可以重新表示 SVM。
    • 采用以下误差函数用来对误分类误差函数的连续近似
      • 铰链误差函数
      • Logistic Sigmoid 误差函数
      • 平方和误差函数
  • 多类 SVM
    • 构建 K 个独立的 SVM,其中第 k 个模型在训练时,使用来自类别 $C_k$ 的数据作为正例,使用剩余的 $K-1$ 个类别的数据作为负例。这被称为“1 对剩余”(one-versus-the-rest) 方法。是应用最广泛的方法。
      • 不同的分类器在不同的任务上训练,无法保证不同分类器产生的实数值具有恰当的尺度。
      • 训练集合不平衡。
    • 在所有可能的类别对之间训练 $\frac{K(K-1)}{2}$ 个不同的二分类 SVM,然后将测试数据点分到具有最高“投票数”的类别中去。这被称为“1 对 1”(one-versus-one)
      • 会导致最终分类的歧义性
      • 对于较大的 K,需要比“1 对剩余”消耗更多的时间
        • 将每对分类器组织成有向无环图,即 DAGSVM。
    • 误差—修正编码,对“1 对 1”方法的推广。
      • 对于错误以及各个分类品质输出的歧义性具有鲁棒性
  • 单一类别的 SVM
    • 解决与概率密度估计相关的无监督学习问题。
      • 不是用来对数据的概率密度建模
      • 只是想找到一个光滑的边界将高密度的区域包围出来
    • 解决方案
      • 将训练数据中的固定比例的数据从原始数据集中分离,同时最大化超平面与原点之间的距离(边缘)
      • 寻找特征空间中包含数据集的比例数据的最小球体。
  • 回归问题的 SVM
    • 在简单的线性回归模型中,最小化一个正则化的误差函数
      • 为了得到稀疏解,二次误差函数被替换为 $\epsilon$—不敏感的函数 ($\epsilon$-insensitive error function),即固定不敏感区域 $\epsilon$ 的宽度
      • 固定位于管道数据点的比例 $\nu$
  • 计算学习理论,也叫统计学习理论
    • 概率近似正确 (Probably Approximately Correct, PAC) 学习框架
      • 目标是数据集的大小与泛化能力之间的关系
      • 提供满足准则所需要的最小数据集规模的界限
    • VC 维度:函数空间复杂度的度量,使得 PAC 框架可以扩展到包含无穷多个函数的空间
    • 在 PAC 框架中推导出的界限为最低标准,严重高估了得到给定泛化能力所需要的数据集的规模。
    • 提升 PAC 界限的紧致程度的方法是 PAC-Bayesian 框架,考虑了空间 F 上的函数的概率分布情况。

S7.2. 相关向量机

相关向量机(Relevance Vector Machine,RVM) 是一个用于回归问题和分类问题的贝叶斯稀疏核方法,会有更加稀疏的模型,在测试集上的计算速度更快,保留了可比的泛化误差。

  • 回归问题的 RVM
    • 回归问题的 RVM 基于的是线性模型(S03),因为先验概率不同,从而产生了稀疏解。
      • RVM 对于每个权参数 $w_i$ 都引入一个单独的超参数 $\alpha_i$,而不是共享的超参数
        • 对于超参数 $\boldsymbol{\alpha}$ 和 $\beta$ 的确定可以使用第二类最大似然法(也叫证据近似)。
          • 令要求解的边缘似然函数的导数等于零,得到超参数的重估计方程;
          • 使用 EM 算法,迭代求解超参数的值。
        • 当算法关于这些超参数最大化模型证据时,大部分都趋于无穷,对应的权参数的后验概率分布就集中在零附近。于是与这些参数相关联的基函数就不再对模型的预测产生作用,等价于被剪枝,从而产生了一个稀疏的模型。
        • 超参数不为零对应的输入变量 $x_n$ 就是相关向量,因为它们是通过自动相关性检测(Automatic Relevance Determination,ARD)的方法得到的。
        • 通过自动相关性检测得到的概率模型的稀疏性的方法是可以应用于任何表示成基函数的可调节线性组合形式的模型上。
    • 对于带有以数据点为中心的基函数的 RVM 进行数据以外的区域外插时,模型会对预测变得起来越确定(即过拟合)。
      • 可以使用高斯过程回归的预测分布来解决,但是计算代价过高。
    • RVM vs SVM
      • RVM:模型更加简洁,处理测试数据的速度加快,稀疏性的增大也没有减小泛化误差。(P244 F7.9)
      • RVM:训练过程涉及到优化一个非凸函数,训练时间也更长。
  • 通过对 RVM 的稀疏性分析得到一个更快的最优化超参数的方法
    • (通过学习算法进一步了解稀疏性的原理,看不懂也不影响)
  • 分类问题的 RVM:将权值的自动相关性确定(P220 S6.4.4.)先验应用到概率线性分类模型(P147 S4.3)
    • 二分类问题:在 RVM 中,模型使用的是 ARD 先验,使用 Laplac 近似后验概率。
      • 初始化超参数向量 $\boldsymbol{\alpha}$;
      • 基于给定的超参数,对后验概率建立一个高斯近似,从而得到了对边缘似然的一个近似
      • 近似后的边缘似然函数的最大化(迭代重加权最小平方,IRLS),又引出了对超参数的重新估计
      • 持续这个过程直到收敛。
    • 多分类问题
      • 使用 Softmax 函数对 K 个线性模型进行组合
      • 使用 Laplace 近似用来最优化超参数
      • 模型和 Hessian 矩阵可以使用 IRLS 算法得到,训练代价相对较大
    • RVM vs SVM
      • RVM 的相关向量倾向于不在决策边界区域内,与 SVM 刚好相反。(P248 F7.12)
      • RVM 做出了概率形式的预测
      • RVM 相对于 SVM 训练时间相对较长
        • RVM 避免了通过交叉验证确定模型复杂度的过程,从而补偿了训练时间的劣势
      • RVM 产生的模型更加稀疏,对于测试点进行预测的计算时间更短

S07. 小结

作者的重点不在描述 SVM,而是描述基于贝叶斯框架和 SVM 模型得到的 RVM,因此作者对于 SVM 的介绍细节较少,如果想先理解 SVM 建议参考 \【周志华,2018] ,有了 SVM 的基础后再理解 RVM 的思想及优缺点会更加容易。

C08. 图模型

使用图形表示概率分布对于分析很有好处,这种概率分布的图形表示被称为概率图模型 (Probabilisticc Graphical Models, PGM)。

  • 概率图模型的优点:
    • 提供了一种简单的方式将概率模型的结构可视化,方便设计新的模型;
    • 通过观察图形,可以更深刻地认识模型的性质,包括:条件独立性质;
    • 高级模型的推断和学习中的复杂计算可以根据图计算来表达,图隐式地承载了背后的数学公式。
  • “图” 的基本元素
    • 结点 (nodes),也被称为端点 (vertices)。
    • 链接 (links),也被称为边 (edges) 或弧 (arcs),用于连接结点。
    • 有向图 (directed graphical):图中的链接有一个特定的方向,使用箭头表示。
      • 有向无环图 (Directed Acyclic Graph, DAG):不能存在有向环 (directed cycle)。在图中不能存在这样的路径:从某个结点开始,沿着链接中箭头的方向运动,结点为起点。
    • 无向图 (undirected graphical): 图中的链接没有箭头,没有方向性质。
    • 全连接图 (fully connected):每对结点之间都存在一个链接。
    • 团块 (clique):图中结点的一个子集,使得在这个子集中的每对结点之间都存在链接,即团块中的结点是全连接的。
      • 最大团块:不可能将图中的任何一个其他的结点包含到这个团块中而不破坏团块的性质。
  • “概率图” 的基本元素
    • 每个结点表示一个随机变量(或一组随机变量)
    • 每条链接表示这些变量之间的概率关系。
    • 概率图描述了在所有随机变量上联合概率分布能够分解为一组因子的乘积的方式
      • 每个因子只依赖于对应的一个子集
    • 有向图模型,也叫贝叶斯网络。用于表达随机变量之间的因果关系。
    • 无向图模型,也叫 Markov 随机场。用于表达随机变量之间的软限制。
    • 因子图 (factor graph):将有向图和无向图转化为因子图,用于求解推断问题。

S08. 前言

  • 重点
    • 贝叶斯网络 \【张连文,2006]
    • Markov 随机场 [Kindermann, 1980]
    • d- 划分
    • 因子图
  • 难点
    • 伦理图:有向图转化为无向图
    • 图模型中的推断
      • 链推断
      • 加和—乘积算法
      • 最大加和算法
  • 学习基础
    • 图论
    • 概率与统计
  • 学习要点

S8.1. 贝叶斯网络

  • 多项式回归(掌握有向概率图模型的表示)
  • 生成式模型(掌握有向概率图模型表示生成式模型的方法)
  • 指数族概率分布(掌握有向概率图模型表示共轭结点对的方法)
    • 离散变量(表达成概率图模型后的观察可得)
      • 对于 M 个变量的任意一个联合概率分布,需要确定的参数的数量为 $K^M-1$ 个,即参数的数量随着变量的数量指数增长。
      • 减少参数数量的方法
        • 删除结点之间链接的方式;
        • 减少模型中独立参数数量,即参数共享 (sharing),也叫参数捆扎 (tying)。
      • 引入参数的 Dirichlet 先验,可以将离散变量上的图模型转化为贝叶斯模型
    • 高斯变量
      • 协方差矩阵的计算
        • 图中不存在链接,表示独立的一元高斯分布组成的集合;
        • 全连接的图,对应于一般的对称协方差矩阵。
      • 超先验 (hyperprior):在超参数上定义一个先验概率分布,后验依然还是高斯分布。不断延伸到任意层次,即层次贝叶斯模型 (hierarchical Bayesian model)。

S8.2. 条件独立

  • 联合概率分布的条件独立性可以直接在图中表示出来,不用进行任何计算。完成这件事的通用框架被称为 “d—划分”(d-separation),其中 “d” 表示 “有向 (directed)”。
  • 图的三个例子(条件独立性的不同解读,需要理解并记忆,方便后面的学习)
  • d—划分
    • 使用条件独立性假设来简化朴素贝叶斯模型的图结构
    • Markov 毯或者 Markov 边界:由父结点、子结点、同父结点组成的结点集合。

S8.3. Markov 随机场

  • Markov 随机场 (Markov Random Field),也叫 Markov 网络(Markov Network),或者无向图模型(Undirected Graphical Model)。包含一组结点,每个结点都对应着一个变量或一组变量,结点之间的链接是无向的(即不含有箭头)。
  • 条件独立性质
    • 联合概率分布可以表示为图中最大团块的势函数 (potential function) 的乘积的形式。$p(\mathbf{x})=\frac{1}{Z}\underset{C}{\prod}\psi_C(\mathbf{x}_C)$
      • $Z$ 被称为划分函数 (partition function),是一个归一化常数。
      • 势函数可以表示为指数的形式 $\psi_C(X_C)=\exp{{-E(X_C)}}$
        • $E(X_C)$ 称为能量函数 (energy function)
        • 指数表示被称为玻尔兹曼分布 (Boltzmann distribution)
        • 联合概率分布定义为势函数的乘积,因此总的能量可以通过将每个团块的能量相加得到。
  • 图像去噪(如果无法理解,直接参考 Markov 随机场的论文)
  • 与有向图之间的关系
    • 伦理 (moralization):使父结点结合在一起。
      • 过程增加了最少的额外链接,保持了最大的条件独立性质
    • 通过伦理过程,将有向图去掉箭头后生成的无向图称为道德图 (moral graph)。
    • 有向图转化为无向图的过程
      • 将图中每个结点的所有父结点之间添加额外的无向链接,然后去掉原始链接的箭头,得到道德图
      • 将道德图的所有团块势函数初始化为 1
      • 拿出原始有向图中所有的条件概率分布因子,将它乘以团块势函数
    • 将有向图转化为无向图是精确推断的重要基础,例如:联合树算法
    • 将无向图转化为有向图用途较少,通常表示归一化限制中出现的问题。
  • 概率分布的 D 图:如果一个概率分布中的所有条件独立性质都通过一个图反映出来,那么这个图被称为概率分布的 D 图,即依赖图 (dependency map)。
    • 因此一个完全非连接的图(不存在链接)是任意概率分布的平凡 D 图。
  • 概率分布的 I 图:如果一个图的每个条件独立性质都可以由一个具体的概率分布满足,那么这个图被称为概率分布的 I 图,即独立图 (independence map)。
    • 一个完全连接的图是任意概率分布的平凡 I 图。
  • 完美图:如果概率分布的每个条件独立性质都可以由图反映出来,那么这个图被称为概率分布的完美图 (perfect map)。
    • 一个完美图既是 I 图,也是 D 图。
  • 链图 (Chain graphs):是一种相容方式的图框架,能够同时包含有向链接和无向链接的图。
    • 依然存在某些概率分布,即使使用链图也无法表达成完美图。

S8.4. 图模型中的推断

  • 图模型中的推断问题:图中的一些结点被限制为观测值,需要利用图结构找到高效的推断算法,计算其他结点中的一个或者多个子集的后验概率分布。
    • 精确推断(S8.4)
      • 一般图的精确推断
    • 近似推断(C10)
  • 链推断(精确推断的基础)
    • 对势函数的求和式进行分组
    • 使用图中局部信息传递的思想,信息采用递归计算的方法
    • 完成了计算边缘概率分布所需要的信息传递,就可以直接得到每个势函数中的所有变量上的联合概率分布。(P277 E8.58)
    • 在无向图中,树的任意一对结点之间有且只有一条路径;因此这样的图没有环。
    • 在有向图中,树拥有一个没有父结点的结点,被称为根,其他所有的结点都有一个父结点。
      • 如果有向图中存在具有多个父结点的结点,但是在任意两个结点仍然只有一条路径,那么称为多树 (polytree)
    • 如果把有向图转化为无向图,经过 “伦理” 步骤后不会增加任何链接,因为所有的结点至多只有一个父结点,从而对应的道德图就是一个无向图。
    • 如果局部信息可以在一种称为树的图中传递,那么推断地执行会更加高效
      • 将有向树或者无向树转化为因子图后还是树
      • 在有向多树的图中,转化后的因子图仍然是树
        • 对于有向多树的图,由于 “伦理” 步骤的存在,转化为无向图会引入环
  • 因子图(用于推导加和—乘积算法)
    • 有向图和无向图都使得若干个变量的一个全局函数能够表示为这些变量的子集上的因子的乘积。
      • 因子图可以显式地表示出这个分解。
      • 在表示变量的结点的基础上,引入额外的结点表示因子本身
      • 因子图也使分解的细节表示得更加清晰。
      • 无向图表示为因子图。对应原始的无向图构造变量结点,对应最大团块构造额外的因子结点,因子被设置为与团块势函数相等
        • 同一个无向图可能存在不同的因子图
      • 有向图表示为因子图。对应原始的有向图构造变量结点,对应条件概率分布构造额外的因子结点,添加上合适的链接
        • 同一个有向图可能存在不同的因子图
    • 因子图由两类不同的结点组成,且所有的链接都位于两类不同的结点之间,因此因子图被称为二分的 (bipartite)
  • 加和—乘积算法 (sum-product algorithm)(计算结点或者结点子集上的局部边缘概率分布)
    • 算法适用于模型中所有的变量都是离散的,因此求边缘概率对应于求和的过程。
    • 算法也适用于线性高斯模型,因此求边缘概率对应于求积分的过程。
    • 假设原始的图是一个无向树或者有向树或者多树,从而对应的因子图有一个树结构。
      • 将原始的图转化为因子图
      • 利用图的结构实现的目标
        • 得到一个高效的精确推断算法来寻找边缘概率
        • 需要求解多个边缘概率的时候,计算可以高效的共享
      • 算法的具体步骤(先推导公式,再看(P284)例子,最后看文字会更容易明白)
        • 对于特定的变量结点,寻找边缘概率
          • 边缘概率通过对所有结点(除特定的变量结点之外)的变量上的联合概率分布进行求和得到
        • 利用因子图的表达式替换掉联合概率分布
        • 交换加和和乘积的顺序,得到一个高效的算法
        • 引入两类信息
          • 一类信息是从因子结点到变量结点的信息
            • 需要求解的边缘概率分布等于所有输入信息的乘积
          • 一类信息是从变量结点到因子结点的信息
            • 所有进入因子结点的其他链接的输入信息的乘积,乘以那个结点关联的因子,然后对所有与输入信息关联的变量进行求和
      • 算法的总结
        • 将变量结点看成因子图的根结点
        • 递归地应用信息传递步骤,直到信息被沿着每个链接传递完毕,并且根结点收到所有相信结点的信息
        • 需要求解的边缘概率分布就可以依据公式 (P282 E8.63) 计算。
  • 最大加和算法 (max-sum algorithm)(寻找概率的最大状态)
    • 图模型的两个常见任务
      1. 找到变量的具有最大概率的一个设置
      2. 找到这个概率的值

      这两个任务可以通过一个算法完成,即最大加和算法,是动态规划在图模型中的应用

    • 最大加和算法在 HMM 模型中的应用是 Viterbi 算法

      (这节文字太多,不容易理解,建议参考 HMM 模型中的 Viterbi 算法介绍 [Rabiner, 1989])

  • 联合树算法 (junction tree algorithm)

    信息传递框架可以被推广到任意的图拓扑结构,得到一个精确的推断步骤。

  • 近似推断
    • 变分 (variational) 方法(C10)
    • 取样 (saampling) 方法,也叫蒙特卡罗 (Monte Carlo) 方法(C11)
    • 循环置信传播 (loopy belief propagation)(有向无环图的近似推断)
      • 等价于加和—乘积算法的一个具体形式。
      • 对于特定类型的误差修正编码的最好解码算法等价于循环转储传播算法。
  • 学习图结构
    • 目标:从数据中推断图的结构
    • 定义
      • 一个所有可能出现的图结构的空间
      • 用于对每个图结构评分的度量

S08. 小结

图模型是模型构建和模型推断的理论基础。

C09. 混合模型的 EM 算法

S09. 前言

  • 重点
    • 用于混合高斯模型的 EM 算法
  • 难点
    • EM 算法的不同视角
  • 学习基础
    • $K$ 均值聚类
    • EM 算法
    • 混合高斯模型(S2.3.)
  • 学习要点
    • 两类隐变量模型
      • 离散的隐变量模型应用于表示混合概率分布
      • 连续的隐变量模型的应用在(C12)介绍
    • 混合模型与 EM 算法的关系
      • 混合模型可以应用于构建复杂的概率分布,还可以应用于数据聚类
      • 数据聚类不利用概率的解决方案:K 均值算法
      • 数据聚类利用概率的解决方案:混合概率模型,即使用隐变量表示混合概率分布的模型。
        • 离散的隐变量表示数据点分配到混合概率分布的具体成分中
        • 模型寻找最大似然估计的一个一般方法:期望最大化(EM)算法
      • EM 算法在混合概率模型的实际应用
        • 采用非形式化的方式介绍 EM 算法在高斯混合分布中的应用
        • 基于隐变量的角度来形式化分析 EM 算法的应用
      • 给出一个一般形式的 EM 算法

S9.1. $K$ 均值聚类

  • $K$ 均值聚类与 EM 算法之间的联系
    • 数据集是由 $D$ 维欧氏空间中的随机变量 $x$ 的 $N$ 次观测组成
    • 目标是将数据集划分为 $K$ 个类别。
      • 聚类内部点之间的距离小于数据点与聚类外部点之间的距离。
      • 二值指示变量 $r_{nk}\in{0,1}$
      • 失真度量 $J=\overset{N}{\underset{n=1}{\sum}}\overset{K}{\underset{k=1}{\sum}}r_{nk}\Vert\mathbf{x}_n-\boldsymbol{\nu}_k\Vert^2$
    • 算法过程
      1. 初始化阶段:设置 $\boldsymbol{\nu}_k$ 的初值
      2. 第一阶段:关于 $r_{nk}$ 最小化 $J$,保持 $\boldsymbol{\nu}_k$ 固定。(相当于 EM 算法中的期望 E 步骤)
      3. 第二阶段:保持 $r_{nk}$ 固定,关于 $\boldsymbol{\nu}_k$ 最小化 $J$ 。(相当于 EM 算法中的最大化 M 步骤)
  • $K$ 均值算法的推广:K 中心点算法
    • 引入更加一般的不相似程度的度量 $\mathcal{V}(\mathbf{x},\mathbf{x}’)$
    • 最小化下面的失真度量 $\tilde{J}=\overset{N}{\underset{n=1}{\sum}}\overset{K}{\underset{k=1}{\sum}}r_{nk}\mathcal{V}(\mathbf{x}_n,\boldsymbol{\nu}_k)$
  • $K$ 均值聚类应用于图像分割
  • $K$ 均值聚类应用于图像压缩
    • 主要是应用于有损数据压缩中

S9.2. 混合高斯

  • 混合高斯模型(S2.3.9.)是高斯分量的简单线性叠加,目标是提供一类比单独的高斯分布描述能力更强的概率模型
  • 使用离散隐变量来描述混合高斯模型 $p(\mathbf{x}\vert\mathbf{z})=\overset{K}{\underset{k=1}{\prod}}\mathcal{N}(\mathbf{x}\vert\boldsymbol{\nu}_k,\boldsymbol{\Sigma}_k)^{z_k}$
    • $z_k$ 是隐变量,用来描述第 k 个高斯分量是否对描述模型有用
    • $\gamma(z_k)$ 是分量 k 对于 “解释” 观测值 x 的 “责任”(responsibility)
  • 最大化混合高斯模型的对数似然函数
    • 存在的问题
      • 最大化混合高斯模型的对数似然函数不是一个具有良好定义的问题,当某个高斯分量 “退化” 到一个具体的数据点时,对数似然函数就会走向于无穷大而无法求得解析解,这是奇异性问题。
      • 对于参数值空间中任意给定的点,都会有 $K!-1$ 个其他的点与之对应,即它们会得出完全相同的概率分布,这是可区分 (identifiability) 问题
    • 解决的办法
      • 基于梯度的优化方法(S5.4.)
      • EM 算法
  • 用于混合高斯模型的 EM 算法(推导算法公式,了解算法思想)
    • 期望最大化(Expectation-Maximization,EM)算法:是寻找带有隐变量模型的最大似然解的方法。
    • 公式中的 $z_{nk}$ 表示 $\mathbf{x}_n$ 数据点对描述第 $k$ 个概率分量的贡献;或者第 $k$ 个概率分量对解释 $\mathbf{x}_n$ 数据点的贡献。
    • EM 算法的过程
      1. 初始化均值、协方差、混合系数;
      2. 在期望 (E) 步骤,使用参数的当前值计算公式给出的后验概率(也被称为 “责任”)
      3. 在最大化 (M) 步骤,利用计算出的概率重新估计均值、协方差和混合系数。
      4. 当对数似然函数的变化量或者参数的变化量低于某个阈值时,算法收敛。
  • EM 算法的形式化分析及其他应用
    • EM 算法估计模型的 MAP(最大后验概率)解
    • EM 算法估计数据集随机缺失的问题的解
      • 数据集随机缺失的混合高斯模型
    • EM 算法与 $K$ 均值的联系
      • $K$ 均值算法对数据点的聚类进行了 “硬” 分配,即每个数据点只属于唯一的聚类;
        • $K$ 均值算法没有估计聚类的协方差,只是估计了聚类的均值。
        • 带有广义的协方差矩阵的硬分配版本的混合高斯模型叫做椭圆 $K$ 均值算法
      • EM 算法对数据点的聚类进行了 “软” 分配,即基于后验概率分布来确定数据点最应该分在哪个聚类中。
      • 在极限的情况下,最大化完整数据对数似然函数的期望等价于最小化公式给出的 $K$ 均值的失真度量 $J$
  • 用于混合 Bernoulli 分布模型的 EM 算法

    (推导公式,理解 EM 算法的构建过程)

    • 由 Bernoulli 分布描述的离散二值变量的混合,也叫隐类别分析。是考虑离散变量上的 Markov 模型的基础。
    • 与混合高斯模型不同的是不存在似然函数趋于无穷大的奇异性
    • 混合 Bernoulli 分布模型可以推广到 $M>2$ 个状态的离散变量多项式分布的情况。
  • 用于贝叶斯线性回归的 EM 算法
    • 贝叶斯线性回归的证据近似问题(S3.5.2.)
      1. 初始化参数 $\alpha$ 和 $\beta$
      2. E 步骤,计算 $\mathbf{w}$ 的后验概率分布,找到完整数据对数似然函数的期望;
      3. M 步骤,关于参数 $\alpha$ 和 $\beta$ 最大化期望,从而重新估计参数 $\alpha$ 和 $\beta$。

S9.4. EM 算法的通用形式

(先推导公式,再依赖具体案例深入理解 EM 算法,后面有广泛的应用。这节看懂了,才代表真正理解 EM 算法了)

  • EM 算法可以看成参数空间中的运算 (P312 F9.14)
    1. 选择某个初始的参数值
    2. E 步骤中,基于固定的参数值,计算隐变量上的后验概率分布,得到了更小的下界
    3. M 步骤,下界被最大化,得到新的参数值
  • EM 算法的扩展
    • 广义 EM 算法 (Generalized EM Algorithm):
      • 改变 E 步骤中完全的最优化为局部最优化
      • 解决 M 步骤中无法计算的问题
        • 在 M 步骤中使用非线性优化策略(例如:共轭梯度算法)
        • 期望条件最大化算法 (Expectation Conditional Maximization Algorithm,ECM):在每个 M 步骤中进行若干具有限制条件的最优化。
      • 增量形式的 EM 算法,收敛速度更快

S09. 小结

混合模型是模型推导的模型基础,EM 算法是模型计算的算法基础。

C10. 近似推断

因为隐变量的数量可能有指数多个,精确计算的代价过高,因此需要借助近似方法。

  • 常用的近似方法
    • 随机近似:Markov Monte Carlo 方法(C11)给定无限的计算资源,可以生成精确的结果,但是在实际应用中多处理小规模数据的问题。
    • 确定近似:基于对后验概率分布的解析近似,无法生成精确的结果,可以应用于大规模数据的问题。
      • 假设后验概率分布可以基于一种特定的方式分解
        • Laplace 近似:基于对概率分布的峰值的局部高斯近似
        • 变分推断(也叫变分贝叶斯),使用了更加全局的准则
        • 期望传播(变分的框架)
      • 假设后验概率分布可以有一个具体的参数形式
        • 高斯分布

S10. 前言

  • 重点
    • 变分在一元高斯分布中的应用
    • 变分在混合高斯模型中的应用
    • 变分在线性回归模型中的应用
    • 局部变分在 Logistic 回归中的应用
  • 难点
    • 变分推断
    • 指数族分布
    • 期望传播
  • 学习基础
    • 泛函分析之变分法
    • 信息论中的 KL 散度
    • 概率分布的共轭分布
    • 混合高斯模型
    • 线性回归模型
    • Logistic 回归模型
  • 学习要点

S10.1. 变分推断

  • 变分推断 变时,泛函的值的变化情况。(附录 D)
    • 限制需要最优化算法搜索的函数的范围
      • 限制近似概率分布的范围的方法
        • 使用参数概率分布来近似,利用非线性最优化方法确定参数的最优值。
        • 假设近似的概率分布可以进行分解(在物理学中的一个近似框架,叫做平均场理论)
          • 恰当地初始化所有的因子
          • 在各个因子上进行循环,每一轮用一个修正后的估计来替换当前的因子
          • 算法保证收敛,因为下界关于每个因子是一个凸函数
    • 在概率推断的应用中,限制条件的形式概率分布是可以分解的函数
    • 限制条件的唯一目的就是为了计算方便
      • 在满足计算方便的条件下,应该尽可能使用丰富的近似概率分布
      • 即使选择高度灵活的概率分布也不会有 “过拟合” 现象,只是会更好地近似真实的后验概率分布。
  • 近似概率分布可分解模型的性质
    • 各个因子的解是相互偶合的
    • 将变分解看成重估计议程,然后在变量之间循环更新这些解,直到满足某个收敛准则。
    • 最小化相反的 KL 散度 KL$(p \Vert q)$ 是期望传播近似推断框架中的目标。
      • 注意两种 KL 散度的区别 (P320 F10.3.)
  • 变分在一元高斯分布中的应用(用于理解变分推断的例子,实际情况上基本不会使用)
  • 模型比较(了解即可)

S10.2. 变分在混合高斯模型中的应用

  • 基本过程
    • 混合高斯模型的似然函数
    • 引入参数上的先验概率分布
    • 为每个参数引入共轭先验分布
    • 变分后验概率分布的最优化涉及到两个阶段之间进行循环,这两个阶段类似于最大似然 EM 算法的 E 步骤和 M 步骤。
  • 隐变量与参数之间的区别
    • 在概率图的方框内部的变量被看作隐变量,因为这类变量的数量随着数据集规模的增大而增大
    • 在概率图的方框外部的变量被看作参数,因为这类变量的数量与数据集的规模无关
    • 从图模型的观点来看,它们之间没有本质的区别
  • 贝叶斯方法与最大似然方法的区别
    • 随着数据量趋向于无穷时,贝叶斯方法就收敛于最大似然方法的 EM 解。
    • 混合高斯模型的变分算法的主要的计算代价来自于 “责任” 的计算,以及加权数据协方差矩阵的计算与求逆。
    • 最大似然方法中遇到的高斯分量 “退化” 产生的奇异性,在贝叶斯方法中不存在
    • 混合高斯模型中数量 K 选得较大时,在贝叶斯方法中不会出现过拟合问题
      • 在确定 K 的最优数量时不需要借助于交叉验证技术
      • 贝叶斯方法自动在模型复杂度和数据拟合之间进行平衡
      • 通过自动相关性确定的方式将贡献比较小的分量的混合系数趋于零,即分量的稀疏性(S7.2.)
  • 变分的下界:方便确定模型的下界,有利于检测模型学习是否收敛
    • 变分的下界还提供了推导变分重估计方程的方法
  • 对于新的观测变量可以得到它的预测概率密度
  • 诱导分解 (induced factorizations):在变分后验分布中假定的分解方式与真实联合概率分布的条件独立性质之间的相互作用产生了诱导分解。

S10.3. 变分在线性回归模型中的应用

  • 变分应用的过程
    • 构建变分分布
    • 构建预测分布
    • 确定变分下界

S10.4. 指数族分布

  • 构建变分分布
  • 推导计算过程
  • 变分信息传递
    • 通过对贝叶斯方法应用于混合高斯模型的推导,得到一些更加普适性的结果
    • 变分推断的过程可以转化为局部信息传递算法

S10.5. 局部变分方法

  • 全局变分方法(S10.1. 和 S10.2.):直接寻找所有随机变量上的完整的后验概率分布的近似
  • 局部变分方法:寻找模型中的单独的变量或者变量组上定义的函数的界限,从而简化最终得到的概率分布。这个局部近似可以应用于多个变量,直到最终得到一个可以处理的近似。
    • 局部变分在 Logistic 回归中的应用

S10. 小结

参考文献

  • [Andrew, 2004] Andrew R.Webb. 统计模式识别 [M]. 电子工业出版社。2004.
  • [Duda, 2003] Duda R O, Peter E Hart, etc. 李宏东等译。模式分类 [M]. 机械工业出版社。2003.
  • [Bishop,1995] Bishop, Christopher M. Neural networks for pattern recognition. Oxford university press, 1995.
  • [Haykin, 2011] Haykin S . 神经网络与机器学习 [M]. 机械工业出版社。2011.
  • \【李航, 2012] 李航著,统计学习方法。 [M]. 清华大学出版社。 2012.
  • \【周志华,2018] 周志华著 机器学习 [M]. 清华大学出版社。2018
  • \【袁亚湘, 1997] 袁亚湘,孙文瑜。最优化理论与方法 [M]. 科学出版社,1997.
  • [Kindermann, 1980] Kindermann, R., & Snell, J. L. (1980). Markov random fields and their applications (Vol. 1).
  • \【张连文,2006] 张连文,and 郭海鹏。贝叶斯网引论。Vol. 11. 科学出版社,2006.
  • [Rabiner, 1989] Rabiner L R. A tutorial on hidden Markov models and selected applications in speech recognition [J]. Proceedings of the IEEE, 1989, 77(2): 257-286.

  • [Borman, 2004] Borman S. The expectation maximization algorithm-a short tutorial [J]. Submitted for publication, 2004, 41.
  • [Charles, 2011] Charles Sutton and Andrew McCallum, An Introduction to Conditional Random Fields [J]. Machine Learning 4.4 (2011): 267-373.
  • [Determined22, 2017] Determined22, http://www.cnblogs.com/Determined22/p/5776791.html , 2017.
  • [Friedman, 2001] Friedman, Jerome H. “Greedy Function Approximation: A Gradient Boosting Machine.” Annals of Statistics, vol. 29, no. 5, 2001, pp. 1189–1232.
  • [Friedman, 2001] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning [M]. New York: Springer series in statistics, 2001.
  • [Goodfellow, 2017] Goodfellow I, Bengio Y, Courville A. 深度学习 [M]. 人民邮电出版社。2017.
  • [Hagan, 2006] Martin T. Hagan. 戴葵等译。神经网络设计 [M]. 2002.
  • [Hyvarinen, 2007] Aapo Hyvarinen, Juha Karhunen. 周宗潭译 独立成分分析 [M]. 电子工业出版社。2007.
  • [Mitchell, 2003] Tom M.Mitchell. 肖华军等译。机器学习 [M]. 机械工业出版社。2003
  • [Rabiner, 1989] Rabiner L R. A tutorial on hidden Markov models and selected applications in speech recognition [J]. Proceedings of the IEEE, 1989, 77(2): 257-286.
  • [Samuel, 2007] Samuel Karlin M.Taylor 著,庄兴无等译。 随机过程初级教程。 [M]. 人民邮电出版社, 2007.
  • [Sutton, 2012] Sutton, Charles, and Andrew McCallum. “An introduction to conditional random fields.” Foundations and Trends® in Machine Learning 4.4 (2012): 267-373.
  • \【苏剑林,2017] 苏剑林,https://spaces.ac.cn/archives/4277 , 2017.
  • \【盛骤,2015] 盛骤等编,概率论与数理统计(第四版)。 [M]. 高等教育出版社。 2015.
  • \【宗成庆,2018] 宗成庆著,统计自然语言处理(第二版)。 [M]. 清华大学出版社。 2018.

符号说明

  • Pxx,代表第 xx 页;
  • Cxx,代表第 xx 章;
  • Sxx,代表第 xx 节;
  • Exx,代表第 xx 公式;
  • Fxx,代表第 xx 图
  • [M],代表图书;
  • [J],代表杂志;