第5课 机器学习的几个经典理论和定理

在机器学习领域存在诸多经典理论与核心定理它们对于深刻理解机器学习的内在特性与本质规律具有重要的指导意义。5.1 PAC学习理论在利用机器学习方法解决具体问题时模型选择、训练样本规模确定以及学习算法收敛速度等关键环节往往依赖经验判断或反复实验。然而经验决策与多次试验不仅成本较高结论也缺乏可靠保障。因此人们希望建立一套理论体系用于分析问题难度、刻画模型表达能力、为学习算法提供理论保证并指导机器学习模型与算法的设计这便是计算学习理论。作为机器学习的理论基础计算学习理论中最基本的内容便是可能近似正确PAC学习理论。机器学习中的一个核心问题是期望错误与经验错误之间的差异这一差异被称为泛化误差它是衡量模型泛化能力的关键指标。其中经验错误是模型在训练集上的平均误差反映模型对已有观测数据的拟合程度期望错误则是模型在整体数据分布上的期望误差即对所有潜在新样本的预测误差的均值。泛化误差刻画了二者之间的差距用于衡量模型 f 能否有效泛化到未知数据。根据大数定律当训练集大小趋向于无穷大时泛化错误趋于0即经验风险趋近于期望风险。由于我们不知道真实的数据分布也不知道真实的目标函数。因此期望从有限的训练样本上学习到一个期望错误为0的函数是不切实际的。因此需要降低对学习算法能力的期望只要求学习算法可以以一定的概率学习到一个近似正确的假设即PAC学习概率近似正确学习。一个PAC可学习的算法是指该学习算法能够在多项式时间内从合理数量的训练数据中学习到一个近似正确的。PAC学习可以分为两部分近似正确一个假设是近似正确的是指其在泛化错误小于一个界限。一般为0~1/2之间的数如果较大说明模型不能用来作为正确的预测。可能一个学习算法有可能以1~δ的概率学习到这样一个近似正确的假设。PAC学习可以以下面公式计算所需要的样本数量。其中为假设空间机器学习中由可能的函数构成的集合表示输入样本到输出样本的所有映射关系从上面公式可以看出模型越复杂即假设空间越大模型的泛化能力越差。要想达到相同的泛化能力越复杂的模型需要的样本数量越多。因此为了提高模型的泛化能力通常需要进行正则化来限制模型复杂度。PAC学习理论可以帮助分析一个机器学习方法在什么条件下可以学习到一个近似正确的分类器。从上式可以看出如果希望模型的假设空间越大泛化模型越小其需要的样本数量越多。5.2 没有免费午餐定理没有免费午餐定理由 Wolpert 与 Macerday 在最优化理论框架下提出。该定理严格证明在有限搜索空间内不存在某一迭代式最优化算法能够对所有问题均表现最优。若某一算法在部分问题上效果显著则必然存在另一类问题其性能甚至弱于纯随机搜索。这表明算法的优劣无法脱离具体问题孤立评判任何算法均存在适用边界必须遵循具体问题具体分析的原则。这一定理同样适用于机器学习领域其核心结论为不存在能够适配所有领域与任务的通用机器学习算法。5.3 奥卡姆剃刀原理奥卡姆剃刀原理由 14 世纪逻辑学家奥卡姆的威廉提出其核心思想可概括为“如无必要勿增实体”。这一思想与机器学习中的正则化理念高度契合简单的模型往往具备更强的泛化能力。若两个模型在性能上相近应优先选择结构更简单的模型。因此在机器学习的优化准则中常通过引入参数正则化约束模型复杂度从而避免过拟合。奥卡姆剃刀的一种严格形式化表述是最小描述长度原则对于给定数据集最优模型∈ℱ应能实现对数据的最佳压缩即实现最短的编码长度。最小描述长度原则同样可从贝叶斯学习的角度进行阐释。模型在数据集上的对数后验概率可表示为​​​​​​​其中−log () 和−log (|) 可以分别看作模型的编码长度和在该模型下数据集的编码长度。也就是说我们不但要使得模型可以编码数据集也要使得模型尽可能简单。5.4 丑小鸭定理丑小鸭定理由日本学者渡边慧提出其核心论断是“丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大”。这一结论乍看之下与日常直觉相悖甚至显得反常识但从理论层面深入剖析其内在逻辑严密且极具启发性。该定理的本质在于揭示一个深刻的事实世界上并不存在绝对客观、统一的相似性评判标准所有相似性度量都带有主观性与场景依赖性。若仅从直观的外部特征出发例如体型、毛色、外貌形态等维度进行比较丑小鸭与白天鹅的差异显然会大于两只外观相近的白天鹅这也是我们直觉判断的来源。但一旦切换评判视角从基因溯源、物种归属、发育阶段等内在本质维度考量结论便会完全不同丑小鸭本是白天鹅的幼崽它与父母在遗传本质上高度同源二者之间的差异反而会小于其父母与其他无亲缘关系的白天鹅之间的差异。这一定理对机器学习同样具有重要指导意义特征的选择直接决定了样本间的相似度与距离度量不存在普适的 “最优特征”脱离任务目标空谈样本相似性没有意义模型最终学到的相似关系本质上是由人为设定的特征、距离函数与优化目标共同决定的。5.5 归纳偏置在机器学习领域绝大多数学习算法在对未知问题进行学习和预测时并非完全依赖数据本身的信息而是会对学习任务的潜在规律、数据分布或模型特性做出一些合理的预设与简化这些隐含的假设或前提条件就被称为归纳偏置。归纳偏置是算法从有限的训练样本中泛化到无限未知样本的核心依据——若无这些预设算法将无法从海量杂乱的数据中提炼出有效规律也无法完成对未知样本的预测本质上是算法对“如何学习”的一种隐性引导。归纳偏置并非随意设定而是基于任务场景、数据特性或领域经验总结而来其合理性直接影响算法的泛化能力与学习效率。不同的学习算法因解决的任务类型不同会对应不同的归纳偏置以下结合两个经典算法举例说明在最近邻分类器中核心的归纳偏置是假设在高维特征空间中距离相近的样本即处于同一个小的局部区域内的样本其类别标签也高度一致。也就是说算法默认“近朱者赤近墨者黑”认为局部区域内的大部分样本同属一类。基于这一假设最近邻分类器在对未知样本进行分类时会通过寻找其周围距离最近的已知训练样本将这些样本的类别作为未知样本的预测类别这一假设也决定了该算法对局部数据分布的敏感性。而在朴素贝叶斯分类器中最关键的归纳偏置是特征条件独立性假设。该假设认为在给定目标类别标签的前提下样本的各个特征之间是相互独立的不存在相互影响、相互关联的关系。这一假设极大地简化了贝叶斯公式的计算复杂度——原本需要计算多个特征联合条件概率的复杂问题可拆解为多个单一特征条件概率的乘积使得算法在数据量有限、特征维度较高的场景下也能高效完成学习与预测。尽管在实际应用中完全的特征独立性往往并不成立但这一归纳偏置带来的计算便利性让朴素贝叶斯分类器在文本分类、垃圾邮件识别等场景中依然表现出色。简言之归纳偏置是机器学习算法的“先验知识”它既是算法泛化能力的来源也决定了算法的适用范围——当算法的归纳偏置与实际问题的规律相匹配时算法能快速学习到有效特征泛化效果更好反之若归纳偏置与问题本质不符则可能导致算法学习失效或泛化性能变差。