Shai Ben-David等人的这篇文章是我对学习能力的不可估量的自由重述。
最近，在哈布雷机器学习中出现的一篇文章遇到了一个尚未解决的数学问题 ，该文章是谢伊·本·戴维（Shay Ben-David）在《自然新闻》同名文章中的翻译。 但是，由于该主题的性质和原始评论的简短性，我对本文的内容仍然完全无法理解。 认识Shai Ben-David，作为出色的著作《理解机器学习：从理论到算法》的作者，我对这个主题很感兴趣，熟悉了这项工作并试图在这里概述要点。
我必须马上说，这篇文章相当复杂，也许我错过了一些要点，但是我的评论要比哈布雷的评论更加完整。
关于PAC学习的几句话
在《自然新闻》的一篇评论中，令我困惑的第一件事是，学习问题本身被呈现为全新的事物。 实际上，这是一个长期且研究相对深入的问题。
不熟悉该问题的人的一些基本概念风险是 -目标变量的实际值和预测值，反映了我们的预测有多错误。 较低的值表示较小的误差。 分类问题的最简单示例是指标函数。 。 对于回归，这将是标准偏差 。 显然，可能会有更复杂的选择。 此概念的另一个名称是损失函数。
平均风险 -整个输入数据空间中的平均风险值。 由于这样的空间通常是无限的（例如，对于真实特征），或者是指数级的（例如，图像大小为1024x1024且像素值为0到255的空间），因此我们无法直接估算此值。 但是，有一些我们现在不讨论的估算此数量的方法。 我们最终希望将此指标最小化。 有时，该指标也称为泛化错误。
经验风险是从整个输入数据空间中选择的某个经验数据集的风险平均值。 通常，我们的机器学习算法会涉及最小化此值。
机器学习的任务是根据可用的经验数据集构建一个解决方案（功能），该数据集将提供最小的平均风险值。
有一种理论可能几乎是正确的学习（大概是正确的正向学习， PAC ）。
PAC训练的机器学习算法的简化定义算法A使用大小为n的经验样本X构造用于恢复目标变量值的某些函数h（如果有任何阈值，则进行PAC训练） 和信心 训练样本n的大小足以使学习到的函数h满足以下条件：平均风险值超过 少于 。
我们可以这样理解：从函数h的平均风险值的角度选择了我们的一些要求之后，我们将知道数据集的大小（显然是从整个空间中随机且随机地选择），因此在学习时我们将达到这些要求。
这种理论可以追溯到上世纪80年代。 但是，它没有提供任何可衡量的指标来反映算法的学习能力。 但是，V。Vapnik和A. Chervonenkis已经开发的统计学习理论 （ VC理论 ）给出了这样的答案。 该理论基于VC维度的数字指标。 VC维是对最大数据大小的组合估计，该算法可以所有可能的方式将其分为两部分。
例子假设我们有一个在n维空间中构建分离超平面的算法。 考虑一维空间：该空间中的两个点始终可以被划分，但是三个点不再可以被划分，这意味着VC = 2。 考虑一个二维空间：三个点总是划分为两个类，但是不能以所有可能的方式将四个点划分为VC = 3。
实际上，可以严格证明n维空间中一类超平面的VC为 。
VC理论的主要定理在一种可能的表述中，证明了以下事实：如果该算法的VC维是有限的，那么它将经过PAC训练。 而且，VC维度是随着经验样本数量的增加，经验风险值收敛到平均风险值的速度有多快的指标。
因此，对机器学习算法本身的机器学习问题进行了比较充分的研究，并具有严格的数学基础。
那么，《自然》杂志的主题是什么？
作者写道，基于各种维度的PAC理论的问题在于它不是通用的。
作者给出了一个有趣的例子，说明了这个问题，其陈述本身就是为了避免将成功表达为PAC学习而设计的。 作者写道：
想象一下，我们有一个展示广告的Internet站点。 将X定义为该网站所有潜在访问者的集合。 从某个广告池中选择广告。 有条件地，假设池中的每个广告都定向到某些类别的用户：体育广告和体育迷等。 任务是准确放置与站点访问者最相关的广告 。
这里的问题是，我们真的不知道将来会访问谁。 总而言之，这种问题的陈述可以描述如下：
具有功能集 超过设定 找到这样的功能 这样就可以衡量未知分布的指标 是最大的。 此外，有必要基于以下一组有限的独立相等分布量来找到这样的函数：
EMX培训
Shai Ben-David和他的同事们介绍了一个新概念-E激发M a X umum（EMX学习），它只是为此类最大化问题提供了学习标准：
对于功能集 ，输入集 和未知的分布 对于任何数量 机能 是 -EMX培训（如果有） ：
毫无疑问，这种学习定义比PAC的概念更为笼统。
那么，连续体和“未解决的数学问题”与它有什么关系呢？
作者证明了以下定理：
EMX营业额 关于 独立于Zermelo-Frenkel公理系统和选择的公理（以下简称ZFC）。
换句话说，使用标准数学公理，在一般情况下，我们既不能证明找到解决EMX学习问题的方法的可能性，也不能证明找到这种解决方案的可能性。
作者还表明，对于EMX学习的一般情况，在EMX可测量性的情况下，没有VC维度（或任何其他维度）是有限的，反之亦然，EMX可学习性将源于其有限性。 更严格地说，他们的公式如下：
有这样一个常数 如果我们假设ZFC的一致性，那么就没有这样的属性 对于一些 $ inline $ m，M> c $ inline $ 对于任何 和功能集 将执行：
- 如果 那是真的 EMX学习的复杂性 不超过M；
- 如果 然后是假的 EMX学习的复杂性 至少m；
相反，对于VC维度，这是正确的，因为对于 相等 它本质上将是VC理论的主要定理的表述。
结论
实际上，这项工作的信息与机器学习的实际问题，甚至与统计学习理论的理论问题都没有什么关系。 在我看来，作品中有两个主要思想：
- EMX学习与哥德尔定理之间的优美联系；
- 对于通用的机器学习问题，创建通用的学习特征（例如VC维度）根本不可行。
同时，我个人完全不喜欢本文的评论翻译中使用的标题“机器学习遇到了未解决的数学问题”。 我认为这是绝对的诱饵，而且，它根本不符合现实。 原始作品并不意味着有人碰到了东西。 机器学习和PAC理论都可以并继续起作用。 需要指出的是，PAC理论不能推广到关于机器学习问题的某些特定陈述，找到了与哥德尔定理的有趣联系，但没有提及关于机器学习遇到的一些未解决的问题。