什么是大概正确的学习理论?

Leonard Kelley拥有物理学学士学位，辅修数学。他热爱学术世界，并努力不断探索。

进化论是一种永不停息的理论，它激发出与许多世界观相冲突的新思想。它的成功是不可否认的，它的一些经久不衰的奥秘也是不可否认的。生物究竟是如何做出维持自身和进化所需的改变的呢?进化的变化需要多长时间才能开始?突变通常是讨论这些问题的关键，但对于哈佛大学的计算机科学家莱斯利·Valiant来说，他想要一个不同的解释。因此，他提出了生态算法和可能-近似-正确(PAC)理论。尽管如此，我希望你能从一个新的角度来看待进化:一个像我们一样在学习的系统。

理解如何使用算法学习

重要的是要区分，大多数生命形式似乎主要是根据非数学模型来学习的，有时是反复试验，有时是错误的概念。这是一个生命形式的能力，以应付生活交给他们决定他们的生存能力。但是，真的有一种数学推导的方法来描述这种学习能力吗?对于Valiant来说，这肯定是可以的，而且通过计算机科学，我们可以收集到一些见解。正如他所说，“我们必须问问，计算机已经教会了我们关于自己的什么东西。(英勇2-3)

Valiant通过分析计算机如何运行并将其扩展到生命形式，希望证明一种生态算法的思想:一种算法，赋予人们从周围环境中获取知识的能力，以努力适应它们。人类很擅长执行生态算法，利用自然资源并将其扩展到我们的目的。我们推广并最大化我们的生态算法能力，但是我们怎么能描述通过算法的过程?我们能用数学来计算吗?(4 - 6)

生态算法是如何暗示PAC情况的，它只是简单地把我们的生态算法根据我们的情况修改它们?尽管有一些假设。首先，我们想当然地认为，生命形式通过对环境做出反应的生态机制来适应环境。这些适应在本质上可以是心理上的，也可以是遗传的，因为“生态算法的定义足够广泛，以至于它们包含了任何机械过程”，这是丘奇-图灵假设的结果(任何机械过程都可以通过算法或计算进行推广)(7-8)。

电脑的东西

这就是这个生态算法工作的基础。图灵和他的机器学习理论至今仍有影响力。人工智能的研究一直以识别机器学习为主导，从大量数据中识别模式，从而获得预测能力，但没有理论。嗯，听起来很熟悉，不是吗?学习算法显然不仅限于此，而且迄今为止大多数算法都没有得到普遍应用。许多人依赖于他们的环境来实现实用性，这就是生态算法在有目的地转向时有用的地方来环境。我们就像一台机器，基于过去的经验开发模式，而不考虑它为什么有效，只关心它背后的效用(8-9)。

现在，应该很清楚，我们已经讨论了一个生态算法的属性，但我们也应该小心行事。我们对我们的生态算法有期望，包括能够定义它，使它不是一个宽泛的。我们希望这些理论适用于无理论的，复杂的，混沌的。另一方面，我们不能让它太窄，以至于在应用中不切实际。最后，它必须是生物学性质的，以解释进化特征，如基因表达和环境适应。我们必须有能力看到“有许多可能的世界”，我们不能“假设它们都是一样的”，也不能把自己固定在一个轨道上(9,13)。

图灵在20世纪30年代的时候也暗示了这一点，他指出，计算是可能的，但不可能显示出具体的步骤所有给定类型的计算。使用生态算法，我们需要在很短的时间内完成这些计算，所以有理由认为对每一步逐个进行计算是困难的，如果不是不可能的话。我们最好使用图灵机来检验这一点，图灵机演示了给定情况下的逐步计算。它应该给出一个合理的答案，人们可以假设外推并制造一个通用图灵机，可以做任何(机械)过程所需的。但图灵机的一个有趣之处在于，“并不是所有定义良好的数学问题都可以机械地解决”，这是许多高等数学学生可以证明的。机器试图把计算分解成有限的步骤，但随着它不断地尝试，最终它可以接近无限步。这就是所谓的停止问题(Valiant 24-5, Frenkel)。

如果我们的集合被完全表达，那么我们就可以看到这些问题的所在并识别它们，但图灵表明这是不可能的图灵机仍然存在。那么，一种不同的机制能帮助我们吗?当然，这取决于他们的设置和方法。所有这些都有助于我们评估真实世界场景的计算，并根据我们的模型得出可能和不可能的结论。现在，值得一提的是，图灵机在建模现实场景方面的记录是很好的。当然，其他模型也不错，但图灵机效果最好。正是这种健壮性让我们有信心利用图灵机来帮助我们(Valiant 25-8)。

然而，计算建模有被称为计算复杂性的限制。它在本质上可以是数学的，就像建模指数增长或对数衰减。它可以是模拟情况所需的有限步骤的数量，甚至是运行模拟的计算机的数量。它甚至可以是情况的可行性，因为机器将处理“每一步的确定性”计算，这些计算建立在先前的步骤之上。早早起床，你就会忘记工作的有效性。那么随机寻找解决方案呢?它可以工作，但是这样的机器将具有与运行相关的“有限概率多项式”时间，不像我们与已知过程相关的标准多项式时间。甚至有一个“边界量子多项式”时间，这显然是基于量子图灵机(谁知道如何建造一个)。这些方法中的任何一个都是等价的，可以用一种方法代替另一种方法吗?目前未知(英勇31-5，戴维斯)。

泛化似乎是许多学习方法的基础(非学术性的)。如果你遇到了伤害你的情况，那么如果任何类似的事情再次出现，你就会变得谨慎。正是通过这种初始情况，我们才能指定并缩小学科范围。但这是如何归纳的呢?我如何吸取过去的经验，并利用它们来提醒我还没有经历过的事情?如果我推断，这比1要花更多的时间所以从归纳法上看，某些事情至少在某些时候发生了。但当我们考虑一个错误的起点时，另一个问题就出现了。很多时候，我们开始时会遇到问题，我们最初的方法是错误的，把其他事情都抛在一边。我需要知道多少才能将误差减小到函数级别?(勇敢的59-60)

对于Variant来说，归纳过程有效的关键在于两个方面。一种是不变性假设，即从一个地方到另一个地方的问题应该相对相同。即使世界发生了变化，它也应该有效地改变变化所影响的一切，而让其他事情保持不变。它让我有信心去新的地方。另一个关键是可学习的规律性假设，我用来做出判断的标准保持一致。任何这样没有应用的标准都是无用的，应该被抛弃。我从中得到规律(61-2)。

但错误会突然出现，这只是科学过程的一部分。它们不能完全消除，但我们肯定可以把它们的影响降到最低，使我们的答案可能是正确的。例如，拥有一个大的样本量可以最小化数据给我们的噪声，使我们的工作大致正确。我们交流的速度也会影响它，因为我们打了很多快速的电话，没有足够的时间。通过将输入变成二进制，我们可以限制选择，从而限制可能出现的错误选择，因此有了PAC学习方法(Valiant 65-7, Kun)。

生物学遇到学习能力

生物学确实像计算机一样有一些网络扩展。例如，人类的蛋白质表达网络有2万个基因。我们的DNA告诉它们如何制造以及制造多少。但这是怎么开始的呢?生态算法会改变这个网络吗?它们也可以用来描述神经元的行为吗?对它们来说，从过去(无论是祖先还是我们自己的)中学习并适应新环境是有道理的。我们能坐在学习的实际模型上吗?(Valiant 6-7, Frenkel)

图灵和冯·纽曼认为生物学和计算机之间的联系不仅仅是表面的。但他们都意识到，逻辑数学不足以谈论“对思维或生活的计算描述”。常识和计算之间的战场没有太多的共同点(看到我在那里做了什么吗?)

达尔文的进化论有两个核心思想:变异和自然选择。已经发现了大量的证据，但问题也存在。DNA和生物体的外部变化之间有什么联系?这是一种单向的变化还是两者之间的来回变化?达尔文不知道DNA，所以他甚至不知道如何解释DNA。即使是计算机，在给定模拟自然的参数时，也无法做到这一点。大多数计算机模拟显示，进化需要我们存在时间的100万倍才能创造出我们。正如Variant所说，“还没有人证明任何版本的变异和选择可以定量地解释我们在地球上看到的东西。”根据模型，这太低效了(Valiant 16, Frenkel, Davis)

然而，达尔文的工作确实暗示了需要一种生态解决方案。一个生命形式所做的一切与现实有关的事情，包括物理、化学等等不可以通过自然选择来描述。基因并没有密切关注所有这些事情，但显然它们确实会对这些事情做出反应。而且，计算机模型无法预测哪怕是极精确的结果，这暗示了一个缺失的因素。这并不奇怪，因为其中涉及的复杂性。我们需要的是接近正确的，非常准确的，几乎是蛮力的东西。我们必须接受数据，并以一种可能的、大约的、正确的方式对其采取行动(Valiant 16-20)。

DNA似乎是进化变化的基础层，有超过2万个蛋白质需要激活。但我们的DNA并不总是在飞行员的位置上，因为有时它会受到我们存在之前父母的生活选择、环境因素等的影响。但这并不意味着PAC学习应该被改变，因为这仍然在进化的范围内(91-2)。

我们PAC论点的一个关键的微妙之处是，一个目标，一个目标，是这个的目标。进化，如果要遵循PAC模式，也必须有一个明确的目标。很多人会说这是适者生存，把一个人的基因传递下去，但这是我们的目标还是副产品而是生活?如果它能让我们表现得比期望的更好，我们可以用几种不同的方式来模拟表现。有了一个基于生态算法的理想函数，我们可以这样做，并通过给定环境和物种可能发生的概率来建模性能。听起来很简单，对吧?(戴维斯，费尔德曼，Valiant 93-6)

数学的时间

最后，让我们(抽象地)讨论一下这里可能发生的一些计算。我们首先定义一个可以被进化算法理想化的函数。我们可以说，“进化的过程对应于学习算法收敛到进化目标的原因。”这里的数学是布尔的，因为我想定义x₁，…，x_n作为蛋白质的浓度p₁，…，p_n．它是二进制的，要么开要么关。我们的函数就是f_n(x₁，…，x_n) = x₁，或…，或x_n，其中解决方案将取决于给定的情况。那么，是否存在一种达尔文机制，让这个函数在任何情况下都能自然地优化?丰富:自然选择，选择，习惯，等等。我们可以将整体性能定义为Perf_f(g,D) = f(x)g(x)D(x)，其中f是理想函数，g是我们的基因组，D是我们当前的条件，在集合x上。通过使f(x)和g(x)布尔(+/-1)，我们可以说f(x)g(x) = 1的输出都同意，如果不同意= -1。如果我们把性能方程看成一个分数，那么它可以是一个从-1到1的数。我们有数学模型的标准，各位。我们可以用它来评估特定环境下的基因组，并量化其有用性或不足(Valiant 100-104, Kun)。

但是他们怎么样了?完整的机制是什么?这仍然未知，而且令人沮丧。人们希望对计算机科学的进一步研究能够产生更多的比较，但这还没有成为现实。但谁知道呢，可能破解密码的人可能已经在PAC学习并使用这些生态算法来找到解决方案……

作品的引用

戴维斯,欧内斯特。”回顾大概正确．”Cs.nyu.edu．纽约大学。2019年3月8日。

费尔德曼,马库斯。“大概是正确的书评。”Ams.org。美国数学学会，第61卷第10期。2019年3月8日。

弗伦克尔,爱德华。“进化，被计算加速。”Nytimes.com．《纽约时报》2013年9月30日2019年3月8日。

杰里米•库恩。"大概是正确的——学习的形式理论"Jeremykun.com．2014年1月2日。2019年3月8日。

勇敢的,莱斯利。大概是正确的。Basic Books，纽约，2013年。打印，2- 9,13,16 - 20,24 -8。31- 5,57 - 62,65 - 7,91 - 6,100 -4。

©2020 Leonard Kelley