{"raw_statement":[{"iden":"background","content":"# 1.前言\n\n哥德尔机 [1] 是由 LSTM 之父 Jürgen Schmidhuber 提出的一种可学习的通用问题求解器。本文将对该模型进行描述与讨论，并且说明这个模型拥有许多重要的性质，这些性质是我们认为通用人工智能所必需的。\n\n# 2.相关概念\n\n## 学习\n\n学习指模型对模型自身的参数（同一个模型在参数不同时有不同的行为）进行修改。用于对自己进行修改的方法叫做学习算法。\n\n## 元学习\n\n元学习指模型拥有通过学习修改自己的学习算法的能力。有大量证据指示人类拥有比较强的元学习的能力。\n\n### 元学习分层\n\n不可学习的方法没有学习能力，比如解决 OI 题的程序，坦克世界的固定线路看到人就停车的脚本等。\n\n常见的机器学习方法，比如朴素的神经网络方法没有元学习能力，因为学习算法是不可学习的梯度下降算法。支持向量机没有元学习能力，因为学习算法是确定的，等。\n\n专门设计了元学习特性的神经网络有元学习能力，但是没有元元学习能力，也就是说不能对学习自己学习算法的算法进行学习。\n\n假设你想设计一种学习算法：\n\n初始时，你想让你的算法可学习，于是设计了初始的学习算法。\n\n然后你想让你的初始学习算法可学习，于是设计了元学习算法。\n\n然后你想让你的元学习算法可学习，于是设计了元元学习算法。\n\n这样每一步你都必须设计新的学习算法，用于之前的学习算法的学习。设计第 $i$ 层的学习算法时，这个学习算法可以优化前 $i-1$ 层，但是对第 $i$ 层的优化需要第 $i+1$ 层后的方法。分层不是必需的，这里分层是人为设计的，因为你人为设计了分层结构，所以你需要设计无限层的元学习算法。\n\n一直这样递归下去可以发现现有机器学习方法的一个问题：因为不能人工设计无限层的元学习算法，所以在某一层之后一定不可学习。这样会导致人工设计可以一直让模型变强，因为设计了第 $i$ 层元学习的模型不会比只设计了前 $i-1$ 层元学习的模型弱，但是这个过程永不收敛。这样的模型不具备一种**不可改进性**，即在给定足量的计算资源下，这个模型是最优的。\n\n哥德尔机以及类似的构造尝试将所有层级的元学习用同一个东西去泛化，将任意层的元学习问题变成一层普通的学习问题。要实现这样的功能，我们需要一个足够强的优化器。弱的优化器，比如梯度下降的神经网络，面临的问题是无法使用梯度下降去优化模型梯度下降的过程，也就是说无法直接用学习算法去处理元学习层面的优化。于是元学习特性需要人为设计，也就是说需要设计优化元学习任务的优化器，而这样会导致该优化器无法用已设计好的方法优化，需要继续设计新的对应的优化算法。这样分层的元学习需要无限的设计，是神经网络方法最大的问题之一。\n\n### 不分层元学习/无限层元学习\n\n哥德尔机没有元学习分层的设计，因为其架构会将所有优化问题用同样的方法优化，并且该优化方法可以优化自身，所以哥德尔机拥有不分层的元学习能力，或者可以叫做无限层元学习的能力。在给定足量的计算资源下，哥德尔机不弱于任何其它可计算的机器学习模型。\n\n实际上存在一些元学习算法是递归的，即存在一种元学习算法，第 $i$ 层可以对前 $i-1$ 层进行优化，且对任意 $i$，这个算法都是相同的，所以只需要有限的人为设计。我们认为这类方法是有一些问题的，不如不分层的元学习算法，这里不展开讨论。\n\n元学习和学习实际上不可区分，这个会在后续进行讨论。\n\n## 强化学习\n\n模型与环境交互并优化由环境提供的奖励。\n\n### 马尔可夫决策过程\n\n时间被分为一些离散的时间步，模型每个时刻从环境中获取输入信息（包括环境提供的奖励），并能从有限种对环境的操作中选一部分执行，环境由这一时刻的状态以及模型采取的操作计算出环境下一时刻的状态。\n\n## 通用人工智能/完全人工智能/人工广义智能\n\n这些词语是 Artificial General Intelligence 的中文翻译，该词语代表一个可以在各个领域达到人类顶尖水平甚至超越的人工智能模型。\n\n通用人工智能**没有准确的定义**，不同人对通用人工智能应该有什么样的能力看法不同。\n\n## 自编程/自修改/自进步\n\n这三个词语指模型的一种能力，有这种能力的模型可以通过修改自己来提升自己的表现。一般提升表现指可以在监督学习任务中通过更多的数据，或在强化学习任务中获得更大的预期奖励。\n\n## 自指\n\n一个模型是完全自指的，表示某个模型可以在内部描述自己的所有性质。虽然人类不是一个完全自指的模型，但是人类可以描述关于自己的部分性质。\n\n自指常用于构建悖论，如：\n\n1. \"这句话是错的\" 是对的还是错的？\n\n2. 罗素悖论：一个理发师只给不理自己头发的人理发，那这个理发师是否给自己理发？\n\n3. 停机问题：一个图灵机如果判定出自己停机，则不停机。\n\n4. 哥德尔不完备性定理。\n\n哥德尔机是一个可以完全自指的模型。哥德尔机的作者认为 \"意识\" 的本质是自指，即模型可以意识到自己的存在。哥德尔机的学习算法可以完全自指，也就是说可以用学习算法处理学习算法的学习，甚至完全覆写掉初始的学习算法。\n\n## 可计算性\n\n程序在不限制空间并且不限制字长时，能在有限时间内完成处理的问题是可计算的问题所构成的集合。\n\n## 图灵机\n\n本文中我们直接把 图灵机 当成 C++ 语言写成的代码，不限制空间并且不限制字长。\n\n### 通用图灵机\n\n用 C++ 语言显然可以模拟执行 C++ 语言。假设我们写出了一份 C++ 语言代码 A，用于执行任何其它 C++ 语言写出的代码。则当我们想执行 C++ 代码 B 时，可以将 B 做为 A 的输入，并执行 A。这样的代码 A 叫做 通用图灵机。\n\n## 不可区分性\n\n有许多人类设计的分层结构是不可区分的，如：\n\n1. 数据与程序不可区分：这里我们顺便解释中文房间悖论。中文房间指给定一个黑箱，将一个不会中文的人和一个翻译器一起放入。在房间外的人向内部提供中文文章，内部的人将文章输入翻译器后直接得到翻译后的结果，并将结果输出，此时从外部看来，无法判定内部的人是否会中文。这个悖论实际上等价于：现在有一个通用图灵机，以及一份通用人工智能的代码。如果我们将通用图灵机看做模型（程序），将通用人工智能看做数据进行执行（对于通用图灵机而言，一个图灵机的程序可以是数据，并且做为数据的程序可以被执行），则这里可以认为这个通用图灵机在给定数据下是一个通用人工智能。也就是说我们可以将非平凡的部分：通用人工智能，在程序和数据两边任意转移，但必须在某一边解决这个本质问题。\n\n2. 监督学习的数据和模型的先验（初始引入的知识）不可区分，强化学习的人类知识和模型的 reward 不可区分：监督学习模型的 loss 函数可以内嵌任意复杂的信息，包括数据集中的所有信息，这种情况下模型的 loss 是模型的先验的一部分。强化学习模型 reward 函数可以内嵌任意复杂的信息，包括关于环境的先验，以及人类知识。如 AlphaGo 算法中使用了 MCTS 搜索算法做为探索先验，这样的先验（搜索）就是一种人类知识。\n\n3. 模型关于自己的先验与模型关于环境的先验不可区分：这个在后续会进行讨论。\n\n4. 学习和元学习不可区分：假设模型分为学习算法和模型主体部分，学习算法经过学习后被修改了，则这里可以看做是元学习。但如果将整个模型做为一个整体来看待，学习实际上改变了模型的一些参数，是普通的学习。从学习和元学习不可区分也可以看出对元学习人为分层是不自然的，应该将元学习的优化视为普通学习处理。\n\n由于不可区分性，一般来说我们用功能而不是具体的结构来衡量模型的能力。比如对于中文房间悖论，可以认为一个有翻译器的人类就是懂得中文的，因为和懂得中文的人表现一致，一个没有翻译器的人类是不懂得中文的。\n\n同理，由于不可区分性，对于“理解”和“意识”的讨论都是无意义的，因为我们用功能而不是具体的结构来衡量模型的能力。\n\n# 3.简介\n\n几乎所有已知的用于解决问题的算法（包括证明搜索器，监督学习，强化学习等）都在元学习方面有欠缺，理由在元学习分层中有描述。人类需要一直不断地设计新的更好的算法（有更多层元学习的算法），并且提供计算资源对这些算法进行测试。\n\n如何才能消除人类的必要性？为了方便描述，我们定义了学习，学习指模型对模型自身的参数进行修改。对自己进行修改的方法叫做学习算法。最简单的想法就是让机器可以进行任意复杂的学习，也就是说学习方法需要足够强，比如从所有可计算的程序中选出一个最高效的学习算法，利用这个学习算法修改自己。\n\n为了解决这个问题，作者设计了一类最优的，完全自指的，通用的问题求解器——哥德尔机。哥德尔机与一个部分可观测的环境交互，并且原则上可以无限制地修改自身（学习），唯一的限制是哥德尔机自己的可计算性。哥德尔机的初始算法有能力完全重写自己，这样的重写能力保证哥德尔机是全局最优的。\n\n## 哥德尔机的结构\n\n哥德尔机主要包含公理系统、证明搜索程序、行为程序、目标函数。\n\n# 4.环境和形式化目标\n\n模型的环境处在一个人为设计的硬件中，该硬件可以是通用图灵机，空间有限的图灵机，或抽象的电子计算机。模型是单例的，只有唯一一个同时存在。模型的生命包含一些离散的时间步：$1,2,\\dots$，模型的生命在 $T$ 时刻结束，这个时刻可能对模型而言不可见。任何一个时变的变量 $Q$ 在 $t$ 时刻的值可以记作 $Q(t)$。\n\n每一步时间我们的硬件执行一个基本操作，改变硬件的状态 $s$，为不失一般性，$s\\in \\mathcal S \\in B^*$，$B^*$ 表示所有可能的二进制串。每一步时间环境状态可能发生变化，环境状态用 $Env$ 表示，$Env\\in \\mathcal E$，$\\mathcal E$ 表示考虑的环境的集合，这个会在后续进行讨论。硬件有硬编码的转移方程：$F:\\mathcal S\\times \\mathcal E \\rightarrow \\mathcal S$。对任何 $t>1$，$s(t)=F(s(t-1),Env(t-1))$ 表示当前 $t-1$ 个时刻都结束后，$t$ 时刻还没开始时硬件的状态。\n$Env(t)$ 表示 $t$ 时刻的环境，由 $s(t-1)$ 中描述环境变化的变量与环境交互得到，如果环境是随机的，则这里按对应概率进行采样。\n\n定义四个特殊的变量：$time,x,y,p$：\n\n1. $time$ 表示当前时刻。\n2. $x$ 表示环境对哥德尔机的输入，对任意 $t>1$，$x(t)\\neq x(t-1)$ 可能发生当且仅当哥德尔机输出了一个特定字符串，表示向环境请求输入。这样就可以避免每个时刻只有常数的计算资源，导致不能对输入完全观测（比如复制整个输入所需的计算资源比每个时刻的计算资源多）。\n3. $y$ 表示哥德尔机对环境的输出，$y(t)$ 表示一个二进制串。输出可能对环境产生影响，比如输出一个控制指令，指令操作环境中的一个机器人，或者指令打开电视机。\n4. $p(1)$ 表示最初哥德尔机的软件，也就是根据环境输入计算出对环境输出的计算过程。初始的 $p(1)$ 可以用一个图灵机表示，所以不是最优的。\n\n每一个时刻 $1\\le t\\le T$ 模型的目标是最大化预期回报。对于一个确定的 $s$ 和 $Env$，奖励函数可以写做：$u(s,Env):\\mathcal S\\times \\mathcal E\\rightarrow \\mathcal R$，$u(s,Env)=E_{\\mu} \\bigg [\\sum _{\\tau=time} ^T  r(\\tau)\\bigg | s,Env \\bigg ]$，其中 $\\mathcal R$ 表示实数，$r(t)$ 表示 $t$ 时刻获得的实数表示的奖励。$E_{\\mu}\\big(\\cdot \\big|\\cdot\\big)$ 表示条件期望，其中 $\\mu$ 表示所有可能的环境。\n\n这里需要注意到 $s$ 表示的也是模型的内环境，因为硬件行为完全由模型决定，$Env$ 表示外部环境，$time=time(s)$ 表示 $s$ 状态所在时刻。\n\n可以同时修改奖励函数使得模型倾向于选择更低方差的改进。绝大部分计算机科学的问题都可以用这个设计形式化。\n\n# 5.哥德尔机的基本思想\n\n为了让我们的硬件变成一个有自指能力的哥德尔机，需要设计对应的软件（也就是可运行代码） $p$，该软件需要有修改自己的能力。初始的代码 $p(1)$ 有一个目前不是最优的问题求解器 $e(1)$，用于和环境交互，这个问题求解器可以是任何传统的强化学习算法，同时还有一个通用的证明搜索器，证明搜索器持续地搜索二元组 (程序，证明） 直到对一个 程序 A，搜索到了一个 证明 B，表明：将搜索到的这个程序 A 直接用于修改 $p$ 后得到的程序的预期回报比修改前的 $p$ 更大。之后模型会使用 程序 A 对 $p$ 进行修改，这个修改不止对 $e$ 有效，同时可能影响到 $p$ 中的证明搜索器。\n\n## 自修改公理\n\n在 $t_1$ 时刻，我们使用搜索到的程序 A 来修改 $s(t_1)$ 当且仅当搜索到了证明 B，表示：$u[A(s(t_1)),Env(t_1)]>u[s(t_1),Env(t_1)]$。硬件状态 $s$ 包含了软件 $p$，用 $A(s(t_1))$ 表示用程序 A 对 $t_1$ 时刻的模型的软件进行学习。\n\n哥德尔机还需要引入大量其它的公理才能变得足够强，比如关于环境的公理，以及概率相关的公理。我们使用 $\\mathcal A$ 来表示一个足够强的哥德尔机的公理系统。\n\n## 哥德尔不完备定理\n\n我们说一个公理系统是一致的，当且仅当对任意命题 $P$，$P$ 和 非 $P$ 这两个命题不能同时在这个公理系统下被证明。\n\n哥德尔不完备定理指的是：任何一个公理系统，如果是一致的，并且能定义自然数，与自然数的加法，乘法和等于，则一定存在一个命题 $P$，$P$ 和 非 $P$ 在这个公理系统中不可证明。\n\n## 哥德尔机的局限性与优势\n\n哥德尔不完备性定理使得对任意一个足够强的公理系统，一定存在不可证的命题。哥德尔不完备定理不会导致哥德尔机弱，因为如果存在某个对哥德尔机有用的命题，但是这个命题在哥德尔机的公理系统下是不可证的，则对人而言，这个命题在同一个公理系统下也是不可证的，人也无法利用这个命题。\n\n哥德尔机更大的局限性在于，在现实环境中，时间和空间资源是有限的，如果哥德尔机的初始公理设计不够好，会导致即使其拥有极大量资源，也无法搜索出足量有效的自修改程序，导致花费了极大量的资源后还是一个低效的搜索器。\n\n哥德尔机需要引入大量的概率相关的公理，因为有限时间的观测只能产生有限的数据。有限的数据会导致任何证明都不能保证不会和后来的观测数据发生矛盾，所以只能给出证明的置信度，而不能保证证明一定正确。\n\n在一般的环境中，哥德尔机模型难以进行严格控制变量的实验，难以收集独立同分布的数据，难以短时间内发现环境在大时间尺度上的改变，这导致对概率的严格推断难以证明有用的结论，因此哥德尔机加入普通的概率公理可能也证明不出任何有用的东西。\n\n这样的问题导致哥德尔机不像是一个形式系统，不像一个证明搜索器，如果把初始的软件 $p$ 看做是一个模型初始的学习算法，自修改看做是学习，哥德尔机更像是一个程序搜索器。这种情况下，不一致或者过弱的公理系统对应一个不完备的初始学习算法，比如神经网络。\n\n哥德尔机的优势在于，哥德尔机可以对自己的初始算法进行任意的改动，并且现有的其它方法都无法做到这一点，比如神经网络无法学习自己的梯度下降学习法，有元学习的神经网络无法学习自己的元学习算法，搜索器无法学习自己的搜索策略等。这里的本质区别是哥德尔机的学习比这些模型强，强到可以完全复写掉初始的学习算法，而其它模型只能修改初始学习算法的一部分。\n\n# 6.全局最优性定理\n\n## 自修改公理与全局最优\n\n对任何形式化的奖励函数 $u$，假设哥德尔机公理 $\\mathcal A$ 是一致的，则任何自修改公理推出的自修改程序 $p$ 是全局最优的：在执行自修改 $p$ 之前哥德尔机的最大预期回报比执行 $p$ 之后的低。\n\n这里的自修改看上去像是一种贪心算法，每次贪心地向更优的方向改进，为什么是全局最优呢？我们可以证明满足自修改公理的程序 $p$ 是对当前哥德尔机的状态而言，所有可能的程序里最优的一个修改。\n\n证明的思路其实很简单，考虑搜索到 $p$ 后，哥德尔机可以采取的两种方案：\n\n1. 执行自修改程序 $p$。\n\n2. 不执行自修改程序 $p$，继续搜索其它程序执行。\n\n第二种方案考虑到了未来会搜索到的所有程序，而哥德尔机证明了第一种方案比第二种方案优，所以程序 $p$ 是在公理 $\\mathcal A$ 下，所有程序中最优的一个。\n\n在实践中，这里的最优性应该需要考虑搜索到每个程序的期望代价，比如存在一些自修改，效果比 $p$ 更好，但是搜索到这些自修改需要大量时间，或是执行了自修改 $p$ 后模型可以更快地搜索到其它自修改。也正是因为这些原因，所以哥德尔机证明了执行自修改 $p$ 后有更大的预期回报。\n\n## $O()$-最优性\n\n哥德尔机在任何任务上是 $O()$-最优 的，即与可以证明理论最优的解（如果存在）只在计算资源消耗上差常数倍。这是因为哥德尔机的初始算法即可保证搜索所有程序和证明是 $O()$-最优 的，哥德尔机是不可能比初始算法弱的，所以也是 $O()$-最优 的。\n\n$O()$-最优性 不是一个很强的性质，假设有一个问题，这个问题的最优解是 程序 A，则一个 $O()$-最优 的模型只需要花费常数的计算资源代价搜索到 程序 A，并且证明这个程序比之前模型给出的解优，就可以实现 $O()$-最优。比较两个证明搜索器时也是类似的，一个证明搜索器可以花费常数时间搜索到另一个并证明最优。\n\n$O()$-最优 的优化器需要一个极大的常数启动，这样的优化器最开始效果很差，需要搜索极长时间才可以变得足够强。我们认为这个过程和自然中的进化类似，并在后文讨论二者的相关性。\n\n# 7.bias-optimal searcher（给定先验下最优的搜索器）\n\nbias-optimal searcher（给定先验下最优的搜索器）的定义：\n\n给定先验概率 $P(p|r)$ 表示问题 $r$ 应该选取解 $p$ 的概率。\n\n黑盒函数可以在 $t(p,r)$ 的时间内判断问题 $r$ 是否有解 $p$。\n\nbias-optimal searcher 在有限时间 $T$ 内，对任意问题 $r$，如果有解 $p$ 满足 $t(p,r)\\le P(p|r)\\times T$ 则能求出问题的一个解。\n\nnear-bias-optimal searcher 则放宽条件到 $t(p,r)\\le P(p|r)\\times T/n$，$n>1$ 是近似比。bias-optimal searcher 有 Optimal Ordered Problem Solver 等已知的构造，这里不做相关解释。\n\n这里搜索器关心的是如何按给定先验分配计算资源，$p$ 可以是程序，$t$ 是程序运行用时。\n\n哥德尔机只需要使用一个 bias-optimal searcher 做为初始证明搜索器，则是 $O()$-最优 的，因为 bias-optimal searcher 是 $O()$-最优 的。\n\n# 8.哥德尔机的缺陷和相关讨论\n\n## 预测而不是证明\n\n考虑到有限的交互导致对环境认知的不确定性，从有限的与环境交互的历史中，不应该能证明无限长时间内可靠的环境性质。\n\n如果尝试构造一个比原有公理系统强的形式系统并用其进行证明，就无法证明新的形式系统的一致性，只能用有限的经验来支持这个新的形式系统是有用的（例如在发现矛盾前暂时正常使用）。\n\n如果尝试增加对环境的假设，那么加入这个假设可以得到新的形式系统，但这个假设不能用初始的公理系统证明，同上。\n\n从这个角度看，利用证明对环境进行推断，和一般的元学习是类似的。这里的证明其实不如说是一种基于已有数据对未来的预测。\n\n另一方面，形式系统可以证明一些关于无穷的命题，这些命题不能从有限的数据中得到，但可能产生可验证且有用的推论。\n\n如果这样的构造是有用的，初始学习算法应该能构造出这样的形式系统并用其进行证明，但不会认为形式系统是绝对可靠的。\n\n从这个角度看，形式系统和一般的程序是类似的。\n\n## 计算资源限制\n\n哥德尔机考虑的是理想环境，模型存活 $T$ 时间，最优化的是在存活的时间内奖励的和。\n\n### 有限存活时间\n\n有限存活时间会限制模型，导致模型无法到达全局最优。\n\n由于哥德尔机的低效性，从现实的角度看，我们认为目前可以提供的算力不够让哥德尔机优化到足够强，甚至无法搜索到任何一个可证明的改进。\n\n对于存活时间有限的情况，实际上哥德尔机很难在有限的数据下，给出对所有可能的环境在 $T$ 时刻内的收益期望，除非对环境有过强的假设。因为哥德尔机设计的最大预期回报需要对所有可能的环境，求出该环境出现的概率，并且加权计算出期望奖励。可能的环境有限显然是一个过强的假设，因为这会导致模型不图灵完备，退化成一个 DFA。而当可能的环境无限的情况下，无法在有限时间内计算这个期望。\n\n就算写出了满足文中描述特性的哥德尔机的代码，在对环境没有过强的假设下，因为预期回报不可计算，该哥德尔机在有限的计算资源下只会卡在第一步操作上，之后消耗光计算资源。或是有一些修改可以不需要计算预期回报，比如将 `a=a+1` 改写为 `++a`，但在对环境没有过强假设的情况下，哥德尔机很难证明一个稍微复杂的修改是更优的。\n\n### 无限存活时间\n\n无限存活时间会导致奖励函数失效，因为无限长的时间会导致奖励函数 $u(s,Env)=E_{\\mu} \\bigg [\\sum _{\\tau=time} ^\\infty r(\\tau)\\bigg | s,Env \\bigg ]$ 无界。两个期望无穷的预期奖励是不可比较的，这也是为什么已有强化学习方法都会设立奖励衰减因子，因为这样的方法可以让 每个状态的预期奖励 有界。无限存活时间还可能导致每个时刻的奖励 $r(\\tau)$ 也是无界的。\n\n对于存活时间无限的情况，模型实际上不能只优化奖励，还需要优化自己的存活和计算资源，因为如果需要人类提供无限的计算资源，则模型不能脱离人类，无法 \"消除人类的必要性\"。\n\n## 启动低效\n\n如果引入大量概率方面的先验进入公理系统，并且可以让预期回报可计算，哥德尔机还是会面临启动过于低效的问题。\n\n简单设计的通用方法，例如哥德尔机和其它一些 $O()$-最优 的证明搜索方法，通常需要非常长的时间后才能变得足够优。\n\n例如，解决特定任务的最优方法需要 $t$ 时间，但通用方法需要 $a+t\\times b$ 的时间，其中 $a$ 是极大的常数，我们将其定义为：**启动常数**，用于在启动阶段找出这个最优方法，$b$ 是模拟执行这个最优方法的常数代价（这个一般不严重，合理假设下可以做到 $b=1$）。\n\n为了得到实用的通用方法，主要的设计复杂性在于降低启动常数 $a$。\n因此，需要首先构造一个简单的通用方法，允许较大的启动常数 $a$；然后，通过具体设计来降低 $a$。\n\n### 进化\n\n进化是一种自然地生成任意复杂的结构的过程。进化生成的生物也可以通过影响环境从而在环境中生成任意复杂的结构。进化的过程和已知的优化过程区别很大，已知的优化过程都有明确的目的性，如神经网络方法通过梯度下降优化模型的 loss，强化学习方法优化模型的最大预期回报等。进化没有在优化任何预设的目标，可以从两个不同的角度看待进化：\n\n1. 进化是一个在确定规则下沿时间轴演化的动力系统。进化没有任何目的性，但是可以生成任意复杂的结构。在这个角度下，我们可以认为没有智能体，只有一个不断演化的环境，但是环境的演化足够复杂，使得其中可以生成任意复杂的结构，如生命游戏。从一些例子中可以看到进化的复杂性，如：如何才能在宇宙中生成一块会飞的金块？进化先在环境中生成了人类，然后人类制作了旅行者号探测器，里面携带了一块人类制作的纯金的碟片，而这其中人类以及金的生成如果展开来讲也是一个极其复杂的过程。遗传算法之所以不是进化，也是因为遗传算法无法在环境中构建任意复杂的结构，并且遗传算法无法模拟生物之间复杂的交互作用。\n\n2. 进化是智能体不断和环境交互的过程：其中进行计算或和环境交互会减少自己的计算资源，可以从环境中获取计算资源。当智能体计算资源为 $0$ 时死亡，需要优化自己存活时间。智能体和环境的边界不可区分。智能体可以将除了自己以外的其它智能体也视为环境的一部分，对其它智能体的建模，如博弈论之类的方法，是将这些智能体看做是环境中比较容易预测的一部分，并研究这一部分环境相关的特性。从这里可以看出智能体和环境是不可区分的，智能体在环境中的边界是模糊的，例如：人吃环境中的饭，吃下去的饭是否属于人的一部分；人是否是环境中人的种群的一部分；人造出了机器人，机器人是人通过对环境进行操作后得到的，是否属于人的一部分。\n\n人类是经过了极长时间进化后产生的复杂结构，如果将进化看做是生成通用人工智能的方法，则进化像生成一块会飞的金块一样生成通用人工智能：通过先生成人类后生成这些复杂结构。生成人类的过程就是上述的极大的启动常数 $a$，通过对模型引入合适的人为设计的先验，同时不破坏完备性，这样应该可以得到一个只需要较小启动的常数，便可以在绝大部分任务上达到较优的通用人工智能。\n\n### 神经网络不完备\n\n神经网络是对模型引入人为设计的先验，但是破坏了完备性的一个例子。完备性被破坏导致神经网络不能通用地解决所有问题，但是可以以很低的启动常数解决一些特定的问题。\n\n神经网络不完备指的是：\n\n1. 搜索的计算图受限。神经网络搜索的是一类比较静态的计算图，虽然有一些动态的尝试，如 MoE 类的方法，Transformer 稀疏化，外置内存类的方法（类似神经图灵机），但是能搜索到的程序空间依然受限。神经网络虽然是图灵完备的，但是静态计算图会导致计算低效，如使用 Transformer 模型计算乘法需要做很长的自回归，输出乘法的中间结果，而实际上的乘法只需要很小的计算量即可完成。神经网络由于其结构固定，无法通过搜索来对结构进行改进。关于神经网络架构搜索（元学习）相关的内容会在后文讨论。\n\n2. 无法遍历状态空间。常见的梯度下降方法都需要让学习率逐步下降，否则训练无法收敛，这样会导致每次随机初始化后模型只能探索到状态空间中很小的一部分。更好的一种神经网络类方法是随机初始化大量神经网络，将其均训练到收敛，之后用于测试时，对这些神经网络的结果取平均或最大似然。这样可以降低模型的方差，因为可以更广泛地探索状态空间。\n\n3. 元学习能力受限。朴素的神经网络方法基于梯度下降，每一步的学习率确定，没有元学习能力。而有元学习特性的神经网络也只是对梯度下降的参数进行学习，甚至无法比较大地修改自己的学习算法。神经网络方法对已知形式的问题效果不错，因为加入了大量专门解决这类问题的人为设计的 trick。但是元学习对应的问题是未知的，神经网络学习能力受限会导致其无法对这些未知结构的问题进行好的学习，而无法对元学习进行好的学习会导致神经网络能力学习更受限。\n\n现在研究神经网络的算法工程师们希望通过神经网络实现通用人工智能，并且一直在设计更为通用的模型，但是我们认为这样的方式是不合理的。\n\n试想一个 Transformer 模型，为了优化平方代价的 attention，假设实现了一种优秀的 attention 策略，该策略允许我们每次只访问 $O(1)$ 个位置的 attention，就可以获取原本需要 $\\Theta(n)$ 个位置的 attention 才能获得的信息。假设这样的 Transformer 模型学到了正确的硬的内存访问，并且训练和测试不分离，也就是说模型的训练方式也是强的，不局限于梯度下降，不会发生灾难性遗忘，并且可以常数代价模拟任何动态计算图，则这样的模型是通用人工智能。\n\n这个模型中神经网络的部分则会退化为一个 for，因为 Transformer 是一个一直增长的函数式内存，每次只需要做常数规模的计算，并且从内存中取出 $O(1)$ 个位置的信息，并写下 $O(1)$ 的信息，真正的复杂性转移到了该如何设计优秀的 attention 策略，以及如何训练上。\n\n我们认为自动数学证明和自动代码生成是足够复杂的任务，在这两个任务上远远超越人类表现的模型应该可以像哥德尔机一样，探索可能有效的改进，并且通过证明以及自编程来修改自己。\n\n最近神经网络类方法取得了很好的进展，如 AI 绘画，AlphaCode，ChatGPT，DreamerV3 等，以我们的知识，我们认为他们无法通过神经网络实现通用人工智能，因为所有这一切模型的学习算法都是本质性地弱的，并且难以改进。\n\n希望本文中给出的推理有误，他们可以实现通用人工智能，实现无数人梦寐以求的技术。\n\n## 什么是好的？\n\n如果对通用人工智能，可以给出定义和证明特定实现的正确性，则可以用证明搜索器来搜索和使用通用人工智能的实现，这个证明搜索器就是一个通用人工智能的实现，搜索器搜索到通用人工智能所需的时间是一个极大的常数，这个常数是证明搜索器做为通用人工智能的启动常数的一部分。\n\n但在搜索出来之前，并不知道存在某种具体实现是能证明正确性的，这里需要注意，可能能证明存在性，但不能对任意一个实例证明它是存在性的实例。\n\n给出的形式定义也依赖人的经验，不保证正确性；如果形式定义有误，需要人发现和修改，无法 \"消除人类的必要性\"。\n\n基于永久存活的定义中，由于我们对环境特性不够了解，以及判断永久存活需要无限长时间的观测，通用人工智能的存在性和正确性很可能是不可证的，而基于理想环境中优化长期奖励的定义看起来更容易证明。\n\n对于哥德尔机而言，通用人工智能的复杂性转移到了判断什么样的修改在未来对自己有利，也就是 \"什么样的修改是好的？\"，其余部分的设计都是比较平凡的。我们认为哥德尔机的问题也在于没解决这个问题，靠一个初始公理系统去直接证明修改后的模型比修改前的模型能获得更大的预期回报，这样的设计过于低效，甚至不一定正确，因为文章没有给出一个可以计算在所有环境中期望预期回报的公理系统的具体实现。\n\n如果我们知道了如何判断什么是好的，则由全局最优性定理，只需要一个保证完备性的搜索所有可能的程序的证明搜索器（探索机制），再判断修改是不是好的，如果是好的则应用该修改（学习机制），就可以实现通用人工智能。\n\n# 9. Q.A.\n\n1. Q：形式化证明是否在现实世界中有意义？\n\n\tA：有意义，你需要将不确定性以及概率方面的公理，以及现实世界的性质引入哥德尔机。\n\n2. Q：哥德尔机会不会使用一个自毁的自修改？哥德尔机会不会直接通过修改自己的奖励函数获得巨大的奖励？\n\n\tA：哥德尔机只会证明一个自修改会增加当前的奖励函数下的最大预期奖励时才会使用。如果哥德尔机的自修改可能导致自毁，则这里使用了概率相关的公理，模型有概率自毁，有概率获得更大的预期奖励。如果哥德尔机修改了自己的奖励函数，则使用新的奖励函数一定可以增加模型原有的奖励函数下的最大预期奖励。\n\n3. Q：自动证明非常难，哥德尔机该如何工作？\n\n\tA：现在人类工作大量使用自动证明搜索器，因为证明和程序是等价的，所以神经网络也可以看做是一种证明搜索器。这些已有的证明搜索器基本上都不是 $O()$-最优的，他们是设计来处理具体任务的，在具体任务上有较小的启动常数，但是在设计范围外的任务上可能需要无限大的启动常数。\n\n4. Q：\"没有免费的午餐定理\" 是否说明不存在通用的问题求解器？\n\n\tA：不是，\"没有免费的午餐定理\" 构造了一种特殊的问题，这种问题中数据有歧义，通常处理的问题都不会有这样差的性质。这种问题上人类也无法取得好的表现。\n\n# 10.结论\n\n模型的自进步性一直被认为是重要的，如图灵 [2] 发现与其花费极大量的计算资源去设计成千上万个功能性模块，不如直接设计一个人类婴儿，让其在环境中学习，这样的性质就是自进步性 [3]，也就是学习。学习的重要性是显而易见的，随着环境变化，模型如果无法学习，则一定会被环境淘汰。如果通过一直修改人工智能的功能模块来实现通用人工智能，则需要人类永远存活。\n\n之后科学家发现，学习算法的好坏是显著影响模型效果的，神经网络从最初算力要求过大，被支持向量机等模型打败，经过算力以及模型结构，训练 trick 等进步，变成目前最广泛使用的模型。但我们认为神经网络模型的学习算法是本质弱的，通用人工智能需要一个足够强的学习算法。对这个学习算法而言，与其花费极大量计算资源去直接设计这个学习算法，不如直接设计一个通用的元学习。\n\n但是现在人工智能方面的研究反而不追求通用性，很多模型是针对具体任务设计的，无法在其他任务上工作，剩下一些模型虽然可以将任何输入输出内容转化为序列，通过序列预测来通用地解决任务，但这些模型没有足够的元学习能力，无法学习到一个足够复杂的学习算法，因此无法解决非平凡的任务，如程序生成，自动证明等。现在针对通用模型的研究主要都在通过加 trick 的方式提高模型表现，比如使用更高质量的数据，使用人的评价来强化学习（RLHF）等。我们认为这些 trick 对类似哥德尔机的通用人工智能也是有帮助的，可以降低模型的启动常数，但是使用这些 trick 去增强一个不完备的模型（如神经网络）是不合理的，应该先设计出完备的模型，后使用这些 trick 去训练完备的模型。\n\n哥德尔机是一个有不分层元学习设计的模型，是 $O()$-最优 的学习算法，但我们认为哥德尔机的设计并没有完全解决通用人工智能的复杂性，因为其启动常数过高，同时公理系统 $\\mathcal A$ 的设计非平凡但作者未给出。尽管如此，我们依然认为哥德尔机是一个非常有意义的模型，是人工智能的重要里程碑。\n\n不分层的元学习模型虽然不会遇到分层中的那些问题，但是会将复杂性全部转移到学习中。学习不只是需要对我们已有的任务和数据进行学习，还需要对模型学习过程中生成的任意复杂的结构进行学习。解决了学习的问题等价于写出了通用人工智能的代码，而学习的问题在于什么是好的，如果模型可以判断什么是好的，则可以选择对自己有利的修改，逐步变强。\n\n到底什么是好的呢？小编也很想知道。目前我们只有几个比较模糊的设计，并且补全细节后也不能完全解决这个问题。\n\n# 11.摇人\n\n大家如果对相关内容感兴趣，可以加群：756872300 来讨论。\n\n# 12.引用\n\n[1] Jürgen Schmidhuber (2006). Goedel Machines: Self-Referential \nUniversal Problem Solvers Making\nProvably Optimal Self-Improvements https://arxiv.org/pdf/cs/0309048v5.pdf\n\n[2] Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59, 433–460. https://doi.org/10.1093/mind/LIX.236.433\n\n[3] McCarthy, J., Minsky, M. L., Rochester, N. & Shannon, C. E. (1955). A PROPOSAL FOR THE DARTMOUTH SUMMER RESEARCH PROJECT ON ARTIFICIAL INTELLIGENCE http://www-formal.stanford.edu/jmc/history/dartmouth/dartmouth.html ."},{"iden":"statement","content":"由于你不会设计哥德尔机，所以你决定先做一道数据结构题：\n\n给定一个长度为 $n$ 的序列 $a_1\\cdots a_n$。你需要回答 $m$ 个询问，第 $i$ 个询问给定一个区间 $[l_i,r_i]$，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你求出其对 $998244353$ 取模的结果。"},{"iden":"input","content":"第一行两个正整数 $n,m$，含义同题目描述。\n\n接下来一行 $n$ 个正整数描述序列 $a_1\\cdots a_n$。\n\n接下来 $m$ 行，第个 $i$ 行是 $l_i,r_i$，描述第 $i$ 个询问。"},{"iden":"output","content":"输出 $m$ 行，对于每个询问输出询问答案对 $998244353$ 取模的结果。"},{"iden":"note","content":"Idea：ouuan&lk，Solution：ccz181078，Code：ouuan&lk，Data：ouuan&lk\n\n对于 $10\\%$ 的数据，满足 $n,m\\le10$。\n\n对于另外 $10\\%$ 的数据，满足 $n,m\\le1000$。\n\n对于另外 $20\\%$ 的数据，满足 $1\\le a_i\\le1000$。\n\n对于另外 $10\\%$ 的数据，满足对所有 $1\\le i<n$，$l_i\\le l_{i+1}\\le 10^5$ 且 $r_i\\le r_{i+1}\\le 10^5$\n\n对于另外 $20\\%$ 的数据，满足 $1\\le a_i\\le30000$。\n\n对于 $100\\%$ 的数据，满足 $1\\le n,m,a_i\\le 10^5$，$1\\le l_i\\le r_i\\le n$。"}],"translated_statement":null,"sample_group":[["5 3\n2 6 3 15 5\n4 4\n1 3\n2 5","15\n216\n546750"],["6 6\n3332 411 6666 6291 415 7180\n4 6\n1 5\n5 6\n4 4\n1 2\n1 3","889738671\n989336054\n14898500\n6291\n1369452\n867407130"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}