此笔记位置已失效,请从目录继续阅读。
全书导读
这本书逐式补写周志华《机器学习》的数学细节。适合带着模型定义和公式编号查找:先辨认公式在处理的对象,再回到它依赖的抽样假设、目标函数、约束或独立性。
全书主线
先弄清如何衡量预测,再看模型怎样把拟合目标写成可求解的式子。无标签数据要再增加分布或相似性假设。计算学习理论说明经验结果在什么条件下可以推广,概率图模型与强化学习则分别扩展到变量依赖和序列行动。
序
序言把本书定位为可按需查阅的公式伴读。王斌从使用工具和理解模型原理两种学习任务出发,建议读者亲手做推导并将遇到的障碍与解法记录下来。
序将重做推导作为理解模型原理的一种方法,见用公式推导检查理解。
原书依据 · 1 处
前 言
谢文睿说明了这套公式笔记如何从个人学习记录发展为 Datawhale 开源协作成果。全书沿用周志华《机器学习》的章节与编号,补写省去的步骤,也给难理解的式子提供直观解析。超出常见本科数学范围的工具可从附注进入。
前言说明本书分别补充推导和解析,编号与主教材对应,见按公式编号补足推导。
原书依据 · 1 处
第1章 绪论
学习器从训练样本得到一个假设,即输入到预测标签的映射。式(1.1)在训练集外按样本概率和学习器输出假设的概率计错。式(1.2)把所有真实标记函数放进同一求和:有限二分类空间有 2 的样本数次方个标记函数,每个固定点正反标签各占一半,于是各学习器对这些目标的总误差一致。实际任务里的目标通常带有结构,模型选择的依据正来自这种结构。
式(1.2)将平均错误化为每个待测点上的错配计数,见无免费午餐依赖均匀目标。
原书依据 · 1 处
第2章 模型评估与选择
模型得分可用不同阈值转成标签。ROC 随阈值降低记录误报与命中比例,曲线面积 AUC 也可以用正负样本对的排序衡量。原书用含同分的八个样本说明两种计算为何一致。需要判断错误是否高于某个基准时,式(2.27)及附注使用二项检验,回答抽样波动是否足以解释观测差异。平方误差分解则换了一个问题,分析重复训练时的波动、平均预测偏离与标签噪声各有多大。它与第 8 章对多个预测器求平均的效果相关。
原书用带同分正负样本的阈值扫描和梯形求面积说明 AUC,见ROC同分应同步入列。
式(2.21)让每个逆序正负对贡献一,同分对贡献一半,见AUC给同分半分。
式(2.27)的勘误固定原假设边界概率,并在离散计数上找阈值,见二项尾概率确定拒绝线。
式(2.41)展开平方项,解析说明独立与零均值在交叉项中的作用,见偏差方差分解有条件。
第2章附注 二项分布参数检验
在固定次数的独立试验中,事件计数服从二项分布。附注从右尾入手,把整个原假设区间上的第一类错误控制转成边界参数上的一个计算。计数阈值只能取整数,因而可达到的检验水平是离散的。它给上一节的勘误提供了推导依据。
二项检验附注解释右尾概率随真实发生概率单调增加,见复合假设的最坏边界。
原书依据 · 1 处
第3章 线性模型
线性模型用加权输入和截距产生打分。本章先对平方误差求导,算出一元回归参数,再用矩阵表示多维输入的残差与梯度。若输出要解释为二分类概率,用逻辑函数把打分压进零到一,再从伯努利模型推出负对数似然。
线性判别分析同样构造投影方向,但目标是让不同类的中心远、同一类的点近。比较两个散度可得到广义特征方程。多类时先把总体散度拆成类内与类间两部分,再用矩阵的迹比较多个投影方向。
式(3.5)至(3.7)先消去截距,再把斜率写成中心化向量的内积之比,见最小二乘可先中心化。
式(3.10)把逐个参数的残差加权求和写成矩阵乘法,见矩阵梯度回传残差。
式(3.27)把两个标签分支写进同一个负对数似然,式(3.30)给梯度,见逻辑损失来自伯努利似然。
式(3.32)及(3.37)至(3.39)把均值间隔与类内投影散度写成广义特征问题,见判别投影考虑类内散度。
式(3.43)按总体均值与各类均值展开外积,后续用迹度量多方向散度,见总散度分解为组内组间。
第4章 决策树
树的内部节点用一个输入条件把训练样本分组。标签混杂用熵或基尼描述,子组按样本数加权后衡量整个划分。信息增益是分组前后平均熵的差。CART 用二分搜索,示例通过纹理是否清晰生成根节点。连续特征只需比较相邻观测值的中点所产生的分组。
式(4.1)的极值推导比较均匀类别比例与单一类别的边界分布,见标签均匀时熵最大。
式(4.2)将划分后各组熵按组占比加权,再从划分前的熵扣除,见分裂收益按样本数加权。
式(4.6)之后的西瓜样例按是否等于候选取值计算子节点加权基尼,见CART按二分搜索基尼。
式(4.7)与(4.8)先生成阈值候选,再对每种二分计算信息增益,见阈值只需考察相邻中点。
第4章附注 互信息与 CART 回归树
知道特征取值之后,标签的不确定性会随所在分组不同而变化。按组概率对这份不确定性取平均就是条件熵,这让树的信息增益具有互信息解释。连续标签没有现成的类别纯度,CART 回归树转而用组内平方误差评分,每个叶子输出本组标签均值。
互信息附注先定义条件熵,再用先验熵与条件熵之差度量不确定性减少,见条件熵是分组后的平均熵。
CART 回归树附注用子区域均值和组内平方误差共同选择切分,见回归树叶值是组内均值。
第5章 神经网络
感知机把线性得分过阈值转为标签,只有分错的样本推动边界移动。多层网络的连接处在不同位置,同一参数可能通过多条路径影响损失。反向传播从输出误差逐层返回,累加各路径贡献后才更新权重和阈值。
后半章转向会生成随机状态的玻尔兹曼机。能量给配置相对权重,限制层内连边后,固定一层即可独立地更新另一层。对比散度从观察数据出发做短程重构,以重构统计量近似模型项,避免枚举全部状态。
式(5.2)将误分类输入方向与标签残差相乘,推得单样本更新,见感知机按误分类更新。
式(5.10)到(5.15)把误差对输出端及隐层输入的导数展开,见反传累积所有下游贡献。
式(5.20)分别对所有连接和所有节点求和,见玻尔兹曼机能量来自边点。
式(5.22)和(5.23)把给定另一层后的联合条件概率分解为乘积,见受限连接使层内条件独立。
式(5.24)由观测数据与短链重构的可见隐藏统计量之差得到,见对比散度近似模型期望。
第5章附注 数据集的线性可分
可分性是对数据在当前特征空间的几何判断。若一张超平面能把全部正样本和负样本分到规定的两侧,当前样本集线性可分。该定义说明了感知机的目标,也为下一章讨论线性 SVM 的硬间隔条件提供前提。
附注明确了一个超平面正确分开两类样本的条件,见线性可分取决于特征空间。
原书依据 · 1 处
第6章 支持向量机
支持向量机寻找间隔较宽的分隔面。其拉格朗日对偶将权重展开成训练样本的加权和,训练点只通过内积出现。互补松弛决定哪些样本能够贡献非零系数。允许松弛后,惩罚系数成为对偶变量上限;将间隔换成允许小残差的双侧带,就能处理回归。
本章末尾的核线性判别是第 3 章的延伸。它仍比较投影后的类间与类内散度,只把特征空间里的投影和类均值重新表达成核矩阵。
式(6.9)至(6.11)由拉格朗日函数的驻点消去权重和截距,见SVM对偶用训练点内积。
式(6.13)让间隔富余与约束乘子的乘积为零,见支持向量由互补约束选出。
式(6.35)至(6.41)在每条样本的间隔约束中加入松弛量并导出盒约束,见软间隔对偶的乘子有上限。
式(6.52)从两个方向的松弛约束推出对应的互补关系,见回归容忍带外才收费。
式(6.60)至(6.70)把特征空间均值与散度投影改写成核矩阵,见核判别在样本系数中求解。
第6章附注 KKT 条件
带约束最优化除了检查梯度,还要检查可行性及对应乘子的取值。互补松弛表示,某个不等式尚有松弛就不能由非零乘子限制最优点。SVM 的对偶推导利用这些条件将乘子取值与训练点在间隔中的位置联系起来。
附注列驻点、原始可行、乘子符号与互补松弛条件,见KKT是约束最优的检查。
原书依据 · 1 处
第7章 贝叶斯分类器
贝叶斯决策把每种标签判断的代价按后验概率取平均,零一损失时选择后验最大的类。若用多元高斯建立类条件密度,可从该类样本估计均值和协方差。若用离散计数,给取值加伪计数可以平滑从未观察到的事件,书中用 Dirichlet 共轭先验说明其来源。
结尾用小型概率依赖结构说明给定中间节点后如何分解联合分布,并引入含潜变量的完整数据似然。后续聚类和概率图模型会通过 EM 处理这类未观测量。
式(7.5)至(7.6)把条件风险化为分错的条件概率,见零一损失下选后验最大类。
式(7.12)与(7.13)先确定均值,再用中心化外积估计协方差,见高斯极大似然协方差除以n。
式(7.19)到(7.25)把计数加一解释为对称 Dirichlet 先验下的平滑,见拉普拉斯修正是后验均值。
式(7.27)及后续图示通过给定父节点或中间节点简化条件分布,见条件独立可简化边缘求和。
式(7.34)定义同时包括观测与未观测变量的对数似然,并引出 EM,见完整数据似然含隐变量。
第7章附注 贝叶斯估计及离散分布先验
离散类别分布描述一次多类别试验。若其概率向量本身未知,可先用 Dirichlet 分布表达不确定性,再把类别计数加到先验参数。得到后验后,最大后验、中位数和均值都能给出一个数字,但对应不同的读出规则。上一节加一平滑使用的是特定先验下的均值。
贝叶斯估计附注分别定义后验众数、中位数及均值,见后验可有不同点估计。
附注从伯努利的两个类别扩展到多个取值,并给出类别概率,见类别分布描述一次多选一。
附注给出概率单纯形上的密度和全一参数对应均匀分布的情形,见Dirichlet分布约束概率和。
第8章 集成学习
多模型表决能否改善分类取决于单体错误水平以及错误相关程度。AdaBoost 通过加性分数叠加基学习器,用指数损失把低间隔样本的训练权重调高,并按新学习器的加权错误率设置票权。Bagging 改用重复抽样;每条样本可交给没抽过它的成员做包外预测。
成员组合时,数值预测可直接加权,分类可比较票数或分数。对于加权平均与平方误差,成员预测围绕集成的分歧能精确解释平均单体误差与集成误差之差。这给多数投票中“错误要有差异”的直觉补上了一个可算的回归版本。
式(8.1)至(8.3)以二项计数推导多数投票失误的概率上界,见多数表决依赖错误独立。
式(8.5)至(8.8)对固定输入的指数风险求导,得到后验赔率,见指数损失最优是半对数胜算。
式(8.9)至(8.11)按分类器答对与答错两种情况对票权求最优值,见AdaBoost票权由误差决定。
式(8.12)至(8.19)用现有集成的指数损失重写下一轮目标,见提升重加权来自间隔。
式(8.20)和(8.21)对没有抽到该样本的成员投票并估计误差,见包外投票逐样本筛选模型。
式(8.22)至(8.26)区分回归平均、权重和带拒绝的类别投票,见组合规则区分分数与标签。
式(8.27)至(8.36)展开平方并用加权预测偏差和为零,见集成分歧抵消平均平方误差。
第9章 聚类
聚类结果的类别名称可重新排列,外部评价因此比较样本对是否同簇。Jaccard、FMI 和 Rand 对四类样本对的计数使用不同分母;没有参照时还可测簇内平均距离。对于高斯混合,每个簇代表一个生成成分。训练使用责任度在成分之间软分配样本,再按分摊结果更新三个参数族,延续第 7 章对隐变量的处理。
式(9.5)至(9.7)以预测划分与参照划分的四类样本对统计一致性,见聚类外部指标数样本对。
式(9.8)用样本对个数归一簇内距离,见簇内平均距离按无序对数归一。
式(9.33)至(9.38)用成分后验权重更新高斯均值、协方差与混合权重,见混合模型责任度是软计数。
第10章 降维与度量学习
最近邻预测依赖邻居与目标点有相近的类别分布。距离空间的结构因此会直接影响预测。经典多维缩放从平方距离恢复中心化内积,PCA 则从坐标寻找保留方差最多的正交方向;两者都可用特征分解求坐标或方向。
核 PCA 通过核矩阵间接计算高维空间的内积。局部线性嵌入将需要保留的东西换成局部重构权重,先在原空间用邻居重构样本,再找一套在低维中也尽量遵循这些关系的坐标。
式(10.1)与(10.2)把近邻的标签分布与待预测点的分布相乘,见近邻上界要求局部后验接近。
式(10.3)至(10.10)利用中心化后 Gram 矩阵行列和为零消去范数,见距离双中心化恢复内积。
式(10.14)与(10.17)把正交低维重构误差转成散度矩阵特征问题,见PCA重构与方差相通。
式(10.24)将特征空间投影方向展开在训练样本张成的空间,见核主成分在Gram矩阵求解。
式(10.28)与(10.31)先解邻居权重,再在低维空间保持同一组权重,见LLE保留局部重构关系。
第11章 特征选择与稀疏学习
特征选择保留已有输入中的一部分,可以按属性子集对标签熵的减少量预先筛选,也可以把稀疏要求直接写进模型目标。平方 L2 惩罚倾向于缩小系数,L1 可让部分系数恰好为零。近端梯度先走一个光滑损失的梯度步,再对所得坐标做软阈值。
稀疏表示把选择对象从原始特征换成字典中的基向量。固定字典时找能重构样本的稀疏系数,固定系数时更新字典。两次条件优化交替运行。
式(11.1)和(11.2)按属性子集的取值组合计算标签熵的下降,见信息增益可以评价属性子集。
式(11.5)至(11.7)对比无惩罚、平方 L2 和 L1 的回归目标,见L1惩罚允许精确零系数。
式(11.10)至(11.14)将光滑项的局部二次近似与不可微惩罚分开,见近端梯度等于逐坐标软阈值。
式(11.15)至(11.18)分解稀疏编码与字典更新两个子问题,见字典学习交替更新编码与基。
第12章 计算学习理论
经验误差是在样本上数错,总体误差则要对抽样分布取期望。独立样本的浓缩不等式先给固定模型界;模型由数据选择时,要让界同时对整个候选类成立。有限类可直接用并集界,知道真规律可被类表示时还可利用零训练错,更一般的任务则比较所学结果与类中总体最优的超额风险。
无限类不能直接按函数数目加总。增长函数只数样本上的可实现标记,VC 维限制它的增长。Rademacher 复杂度改问模型类能贴合多少随机符号,用独立副本和对称性把这个量接到经验与总体的差。算法稳定性从训练过程本身入手,比较删掉一个样本前后预测损失的变化。
式(12.1)至(12.3)分别定义分布错误、样本错误和两个假设的分歧,见经验误差估计总体错分率。
式(12.4)用凸函数的弦说明期望与函数交换时的不等式方向,见凸变换抬高平均值。
式(12.5)按独立随机变量的取值区间约束经验均值的尾部,见有界均值服从集中界。
式(12.7)以替换一个样本所能造成的最大变化控制集中,见有界差控制一般统计量。
式(12.9)至(12.14)把有限假设类里碰巧零训练错的概率合并,见一致学习靠并集界排除坏假设。
式(12.15)至(12.20)从固定假设的双侧误差界推进到整个有限假设类,见统一误差界承接选模。
式(12.21)至(12.29)通过增长函数、VC 维和组合上界处理无限类,见增长函数只数可实现标记。
式(12.30)至(12.34)分别比较经验最优与总体最优的误差,见经验最优的超额风险至多两倍偏差。
式(12.36)至(12.41)用标签相关性替代分类错误,再将标签换为独立随机符号,见随机符号衡量可拟合噪声。
式(12.42)至(12.46)引入独立同分布样本、对称符号与有界差,见鬼样本把总体差变成可对称差。
式(12.52)至(12.53)以增长函数的对数约束分类器族的随机标签拟合,见离散标记数约束随机相关。
式(12.57)至(12.60)比较删样前后模型的损失,并给出经验及留一估计的泛化界,见稳定算法限制单样本影响。
第13章 半监督学习
无标签点可提供输入分布或邻接结构。若每类对应一个高斯成分,有标签点按已知成分计入,无标签点按责任度分配。半监督 SVM 用低密度边界的假设联合选择分隔面和未标记点的标签。
图方法显式表示相似度。固定种子的标签后,选未标记分数使相似邻居间的差尽量小。也可迭代传播,把邻居消息和原种子分数混合。图关系合理时能传递信息,如果一个区域没有标记来源或桥接了本不相似的群体,传播结果会受影响。
式(13.1)至(13.8)分别写有标签与无标签样本似然以及成分参数更新,见半监督混合兼用软硬归属。
式(13.9)在软间隔目标中引入未标记样本及其待定标记,见半监督SVM同时选择标签。
式(13.12)到(13.17)将图能量化为度矩阵减邻接矩阵的二次型,见图拉普拉斯惩罚邻点标签差。
式(13.20)给出规范化相似矩阵迭代的极限,见标签传播保留种子反馈。
第14章 概率图模型
概率图通过局部因子表示联合分布。有向的隐马尔可夫模型将时序依赖归入状态转移与观测发射,无向模型用团势函数表达相容程度并归一化。边缘推断可以消去暂不需要的变量,树上把消元结果沿边传递并复用。
直接计算太昂贵时可用采样或变分近似。Metropolis–Hastings 通过可逆转移让目标分布保持平稳,变分方法则选一个简单分布,通过增大下界来缩小它与后验的差距。EM 的 E 步使用当前后验,均值场对近似族施加分块约束。主题模型的未知主题和概率向量把这些问题汇到同一个例子。
式(14.1)把初态、状态转移和各时刻观测全部纳入联合概率,见隐马尔可夫联合按时间分解。
式(14.2)至(14.10)把势函数乘积、能量表达和局部马尔可夫性质联系起来,见团势函数经配分函数归一。
式(14.14)至(14.20)从逐变量求和发展到树上的消息传递,见变量消元把局部和缓存为消息。
式(14.22)以样本函数值的平均近似分布期望,见采样均值替代期望积分。
式(14.26)至(14.28)把一步转移拆成提议和接受,再用细致平衡选择接受率,见MH用正反流量确定接受率。
式(14.29)至(14.34)先边缘化隐变量,再用任意代理分布展开边缘对数似然,见证据分成下界与后验差距。
式(14.35)至(14.40)用分块乘积限制代理分布并推出单块最优更新,见均值场逐块更新近似后验。
式(14.41)至(14.44)列文档主题、主题词分布及观测词的联合与后验,见主题模型有两层概率向量。
第15章 规则学习
规则筛选既要提高覆盖集合的纯度,也要留住足够样本。FOIL 增益按保留正例数对比例提升加权,似然比统计量比较规则覆盖前后的标签比例。另一条线索是逻辑规则如何推导与逆向构造:归结移去互补文字,逆操作恢复候选前提;内构、互构等规则压缩或共享前件,一阶逻辑还需要统一代换。
式(15.2)与(15.3)分别用似然比和保留正例加权对数增益评价规则,见规则增益兼顾纯度和覆盖。
式(15.6)至(15.9)、(15.14)及(15.16)给出删除、归结和带代换的逆操作,见逆归结补回消去的文字。
式(15.10)至(15.13)写出吸收、辨识、内构与互构四种操作,见规则构造复用部分前件。
第16章 强化学习
多臂赌博机先从不断到来的奖赏估计单个动作的价值,样本均值可用一次残差更新;softmax 用温度平衡尝试和偏好。转向一般序列时,一个动作同时改变即时奖赏与未来状态。价值递推将两者分开,状态值还要按策略平均首步动作。
掌握旧策略的动作值后可以贪心改进策略;没有转移模型时,SARSA 用实际下一动作的估计值和即时回报构成更新目标。这是从完整期望递推转为一次样本更新的做法。
式(16.2)与(16.3)把此前回报和改写为旧均值乘次数,见样本均值可递推更新。
式(16.4)定义动作分值经温度缩放后的 softmax,见温度调节动作概率比。
式(16.7)至(16.10)把有限平均回报与折扣回报拆为首步和剩余价值,见价值递推按首次转移拆分。
式(16.14)和(16.16)用动作最大值和反复代入证明策略价值不下降,见贪心改进比较旧策略动作值。
式(16.31)用一次转移及下一动作的当前估计组成更新目标,见SARSA用实际下一动作自举。
跨章综合
概率模型允许把未观测的对象留在式子里,再求和或求条件期望。第 7 章以完整数据似然引入这套思路,第 9 章把成分后验用作聚类的软计数,第 13 章给已标记点使用确定归属,第 14 章再用证据下界解释 EM 与近似后验之间的联系。
从同一份训练材料挑选模型,会改变所需的误差论证。第 2 章的二项检验要求判错计数来自可视作独立、等概率的试验。第 12 章的统一界则容许先在有限候选类比较训练误差,再对中选者作概率控制。集成中的包外估计用训练某个成员时漏抽的样本构造该成员可用的评估,仍需留意依据包外结果反复调参。
公式也常通过一次重写降低计算成本。不同类的均值与散布变成核矩阵,就可避免显式构造特征空间。图模型的边缘和变成局部消息,就可复用中间计算。L1 近端目标拆成逐坐标问题,就可单独阈值化。这些重写依赖的条件分别是内积表示、图结构和可分目标。
发散与实践
读者延伸。比较同分组的 ROC 和成对 AUC,可检查分类评估实现是否依赖同分样本的输入顺序。对照软阈值的解析值、子梯度和目标值,可检查稀疏求解器是否正确处理零点边界。两张实践卡已准备输入与验收条件,实验待执行。