奥卡姆学习

在计算学习理论中，奥卡姆学习是一种算法学习的模型，学习者的目标是输出所收到的训练数据的简洁表述。这与可能近似正确（PAC）的学习密切相关，其中学习者是根据其对测试集的预测能力进行评估的。奥卡姆学习能力意味着PAC学习，对于各种各样的概念类来说，反过来也是如此。PAC可学习性意味着奥卡姆可学习性。

奥卡姆学习是以奥卡姆剃刀命名的，该剃刀的原则是，在所有其他条件相同的情况下，对观察到的数据，较短的解释应优于较长的解释。奥卡姆学习理论是对这一原则的正式和数学上的论证。Blumer等人首先表明，奥卡姆学习意味着PAC学习，这是计算学习理论中的标准学习模型。换句话说，（输出假说的）简明性意味着预测能力。

一个概念的简洁性{displaystylesize(c)}表示。最短的比特串的长度，它可以代表.奥卡姆学习将学习算法输出的简洁性与它对未见过的数据的预测能力联系起来。{displaystyle{mathcal{H}}是分别包含目标概念和假设的概念类。｝是分别包含目标概念和假设的概念类。那么，对于常数.如果一个奥卡姆算法的运行时间是多项式的，那么它就被称为高效的。

{displaystyle{mathcal{H}}，如果存在有效的奥卡姆算法，则该假设类H是可学习的。｝如果存在一个有效的奥卡姆算法来处理{displaystyle{mathcal{C}}的高效奥卡姆算法。｝奥卡姆和PAC学习之间的关系奥卡姆学习性意味着PAC学习性，正如Blumer等人的以下定理所示。定理（奥卡姆学习意味着PAC学习）设定理（奥卡姆学习意味着PAC学习，cardinality版本）设{displaystyle0<epsilon,delta<1}。{displaystyleL}是一个算法，以便在给定的情况下是一个算法，这样，给定{displaystylem}从一个固定但未知的分布中抽取的样本