机器学习领域中可以看到一些 OI 相关的内容，这篇文章会对这类内容做出列举并科普。部分内容可能需要一定的专业知识，有需要补充的或者错误的内容也请评论区提出。

可计算性

RNN，LSTM，GRU

RNN，LSTM，GRU 的计算能力和一个 DFA 相当。虽然这些模型在计算的中间结果是实数时是图灵完备的，但这样的讨论是无意义的，因为实数是不可存储的，一个实数可以存储无限的信息，可以当作无限大小的内存使用。所以讨论默认在每个参数和计算的中间结果有 \Theta(w) 个位的前提下讨论。

计算的中间结果是可变长的整数，有理数时，这三个模型也是图灵完备的，这里的每个参数就相当于一个可变长内存。

这三个模型表达能力是类似的，下面只讨论 RNN。

考虑表达式求值任务，假设模型每一步的计算的中间结果的量为 n，可以构造一个长度超过 3n+4 的表达式，表达式最左的 3n+4 个字符由左括号和数字和运算符交替，这样模型经过第 3n+4 个字符后因为可存储的信息为 n 个字，一定无法记下前缀的所有信息，故无法保证能计算出正确的表达式的值。在序列长度变长时，模型表现会持续下降。

这些模型弱的原因在于不具备可扩展大小的内存，所以不是图灵完备的。

因此这类神经网络可以处理不同的输入序列长度，且具有和 DFA 相当的可计算性。

证明 RNN 表达能力不弱于 DFA 可以使用一个阶跃的激活函数，n 个计算的中间结果中只有一个位置是 1，其余位置是 0，表示到达了某个状态，这样可以表示任意一个 n 个状态的 DFA。

证明 RNN 表达能力不强于 DFA 是平凡的，固定大小内存的模型可以枚举内存的所有状态做为 DFA 的所有状态，模型一定是在这些状态上转移的一个 DFA。

如果在读取完输入序列被用空字符无限延长，且模型自行决定每步是否停机，且处理序列中第 i 个位置时，模型的所有中间结果的字长变长为 i-bit，则可以做到图灵完备。

Transformer

Transformer 在一些假设下是图灵完备的。

Transformer encoder 无额外空间的处理

Transformer encoder 的计算量和输入的序列长度成正比，处理 n 长度的序列时，总计算量是 O(n^2) 的，所以无法模拟复杂度更高的计算。

Transformer decoder 有额外空间的处理

Transformer decoder 自回归生成输出时，先生成一些中间结果（scratchpads），之后输出一个特殊字符 [sep] 表示中间结果生成完毕，之后输出结果。

假设 Transformer 使用一个合理的位置编码而不是固定的大常数，同时 Transformer 自回归的每一步可以决定是否停机，则 Transformer 是图灵完备的，具体证明细节不在此赘述。

Transformer 自回归生成的中间结果可以做为一个函数式内存，每次计算 attention 可以看作是在进行稠密的内存访问，即访问内存中每一个位置，同时自回归的过程可以进行计算，弥补计算量不足导致无法模拟高复杂度计算的问题。

一般 Transformer 训练的过程中会输入人预先标注的中间结果，测试时 Transformer 会一直输入上一个输出的字符自回归，Transformer 自回归时直接先输出学到的中间结果生成方式生成的中间结果，之后再生成答案。[1]

Transformer + 外部计算模型

因为 Transformer 在进行数值运算时有时会出现计算错误，可以将 Transformer 与外部的计算模型合并为同一个模型来增加正确率。一般这种任务是以自然语言做为输入，Transformer 负责将自然语言翻译为一份形式化的代码，之后用外部计算模型来执行这份代码。

其实 RNN + 外部计算模型可以实现图灵完备，比如人类实际上不是图灵完备的，因为脑容量有限，同时记忆机制是有缺陷的，但是人类加上足量草稿纸可能是图灵完备的，至少计算能力上显著变强了。

这里的外部计算模型都是通过监督学习硬编码到模型内的，模型内的神经网络部分不需要强化学习外部计算模型的性质。

外部计算模型处理数值计算 [2]

OpenAI 使用微调后的 LLM（大型语言模型）来求解小学数学题。

其中红色括号部分是为了提高正确率而标注的计算过程，由硬编码的逻辑以及一个微调后的神经网络生成标注。在测试时会将标注中模型生成的计算结果删除，由一个支持数值计算的外部计算模型重新计算表达式的结果后覆写。这里的覆写实际上不只是对计算出答案的最后一步适用，前面的计算过程中也可以通过覆写算式等号后的结果，在等号后的结果部分不自回归而是输入结果来实现。

外部计算模型可以解释并执行复杂程序 [3]

同样处理的任务是求解小学数学题，不同的是这里 Transformer 学习到的是将自然语言描述的题面翻译为一份 python 代码，之后由外部计算模型（python 解释器）来运行这份代码，运行的结果就是模型的输出。

NTM（神经图灵机），Memory Networks（记忆网络）

NTM，MN 因为无法动态拓展内存，并且训练时一般内存大小是固定的，所以不是图灵完备的。

个人认为 NTM 的问题在于不具备对内存大小的泛化能力，只能在时间维上递归，而不能在内存的维度上递归（神经网络动态加点的问题），而 Transformer 可以通过自回归的函数式内存解决这个问题。

神经网络稀疏化

Transformer 稀疏化

普通的 Transformer 第 i 步计算时需要和前一层中第 1 到第 i-1 步的计算中间结果计算 attention，所以时间复杂度是 O(n^2) 的。

这里实际上时间复杂度需要带上层数以及模型大小这两个参数，不过一般认为这两个都是常数。

Transformer 的 attention 为了高效地并行训练，同层之间没有数据依赖，并且红色的自回归连接是不存在数据依赖的，因为训练时知道序列中每个位置的实际值。这样训练时可以对每一层在 GPU 上并行训练，并且访存友好，因为 GPU 需要输入 \Theta(n) 的内容，并计算出 \Theta(n^2) 的结果。

Transformer 的这个特性导致稀疏化后信息经过多次 attention 传递的深度上限受限，因为每次传递，会导致对应中间结果所在的计算图的层数增加 1。假设 Transformer 每步推理产生 L 层中间结果，这里的贡献经过 attention 传递的次数上限是 \Theta(L)。

Sparse Transformer（分块）

1. 对序列按 \Theta(\sqrt n) 大小分块，计算 attention 时只计算块内的 attention。这样的方法只能计算块内的贡献，无法计算跨块的贡献，贡献最多传递 O(\sqrt n) 步。

2. 对序列按 \Theta(\sqrt n) 大小分块，计算 attention 时计算块内的 attention，同时在每个块中选常数个位置，这些位置对所有其他位置算 attention。这里相当于 OI 中的块内前缀和和块外前缀和的方法，任意两个位置的贡献只需要计算两步 attention，朴素的方法是任意两个位置的贡献只需要计算一步 attention。

3. 对序列跑 \Theta(\sqrt n) 长度的滑动窗口，滑动窗口内部计算 attention。这样任意两个位置的贡献需要计算 \Theta(\sqrt n) 步 attention，因为传递的次数上限是 \Theta(L)，所以实际上贡献最多传递 O(L\sqrt n) 步。

Longformer（滑动窗口，随机化）

1. 对序列跑 W 长度的滑动窗口，滑动窗口内部计算 attention。这样任意两个位置的贡献需要计算 \Theta(n/W) 步 attention，因为传递的次数上限是 \Theta(L)，所以实际上贡献传递 O(LW) 步。

2. 还是滑动窗口，不同的是这里内部计算 attention 使用了一种黑白染色的方法，对一半的位置计算 attention，类似于 CNN 中的空洞卷积。这种方法和上面的滑动窗口方法复杂度没有区别只有常数区别。

3. 对序列开始的常数个位置，计算这些位置和所有其他位置的 attention，之后对滑动窗口内计算 attention，之后对少数位置，计算这些位置和所有其他位置的 attention。（见过另一个版本是对每个位置计算这个位置和少数随机位置的 attention）。

基于线段树的 Transformer 稀疏化

TODO

基于倍增表的 Transformer 稀疏化

TODO

固定结构稀疏化的问题

固定结构的 Transformer 稀疏化存在 attention 访问信息量受限的问题。

如果我们通过稀疏化，想通过将 x 个位置 A_1\cdots A_x 的信息通过计算 attention 汇集到 1 个位置 B 上，之后想通过和 B 计算一次 attention 访问 A_1\cdots A_x 的信息，获得的关于每个 A_i 的信息量会被稀释为原来的 1/x。

固定结构的 Transformer 稀疏化仍然是图灵完备的，大概构造是访问信息后复制一份。

基于强化学习的 Transformer 稀疏化

神经网络在线加删数据

在线加数据

普通的神经网络支持在线加入数据时需要重新训练，如果每加入一组数据都重新训练则代价过大。加入的数据不一定是和之前的数据独立同分布的。

根号重构

根号重构的方法是每加入一批数据后重新训练整个神经网络。

对被加入但是没有训练进神经网络的这部分数据，有两种处理方式，第一种是直接忽略，第二种是训练一个小的神经网络，每次加入数据后重新训练小的神经网络。但是没有已知的有保证的合并两个大小差别较大的神经网络的方法。（？）

块状链表

可以维护根号个数据块，每个数据块内训练一个神经网络，查询时独立在每个小的神经网络上进行查询，合并多个块的贡献可以使用投票的方法，或者训练另一个神经网络来解决合并的问题。如果每次加入的数据是和历史数据独立同分布的，则投票的方法是无偏的，但是无偏其实也没什么用，比如随机选一个块并只考虑这个块的神经网络也是无偏的，但是方差会很大。

在线加删数据

和 OI 不一样的是神经网络不能通过懒惰删除来将删除转换为插入。一个数据会对神经网络的所有节点产生影响，这样的影响很难通过微调之类的方式消除。

块状链表

还是维护根号个数据块，每个数据块内训练一个神经网络，删除一个块的数据后需要重新训练整个块，而且需要保证所有块的大小比例为常数。因此一个块如果被删除了过多数据，则需要和其他块合并。这里对应的数据结构和 OI 中的块状链表是一样的。

可微分数据结构

可微分栈，可微分队列[4]

传统意义上的栈每一步的操作是离散的，也就是说我们每一步要么是入栈一个元素要么是出栈一个元素。

可微分栈尝试将栈的基本操作软化，也就是说每一步可以入栈浮点数个元素或者出栈浮点数个元素。

模型的结构比较简单，每一步 RNN 会决定进行入栈还是出栈操作，以及操作的具体值以及长度（比如入栈 0.6 个 2，出栈 1.3 个元素）。这里为了避免 RNN 对入栈和出栈进行二选一决策，所以直接规定每一步一次进行一次入栈和出栈操作。这次出栈的结果会返回给 RNN，RNN 在进行下一个时刻的决策时会参考这个结果。

出栈时可能会将多个长度和值为浮点数的元素取出，合并这些元素的方法可以线性加权也可以用其他复杂一些的方法。出栈的元素会被提供给 RNN，于是也有从 RNN 反向传播来的梯度。

入栈操作的梯度由这个元素为出栈操作提供的梯度线性加权得到。

于是可以发现这个可微分栈的每一步操作都是可微的，只是梯度有局限，一次出栈操作只能计算被出栈的元素的梯度，无法提供给未被出栈的元素梯度。

可微分队列的设计和可微分栈类似。

将 OI 常见结构做为结构先验的代码生成

基于线段树先验的内存[5]

这篇文章提出了一个可学习的内存结构 HAM，支持 \Theta(\log n) 时间复杂度访问任意一个内存位置，而普通的基于 attention 的内存需要 \Theta(n) 时间复杂度。文中学习了多个任务包括：翻转序列，排序，归并两个排好序的序列，高精度二进制加法，模拟 map < int5 , int5 >，模拟栈，模拟队列，模拟优先队列。

为了完成上述任务，模型需要在时间维上有递归的能力，文章采用了 LSTM + HAM 的方式。

假设输入序列长度为 m，像 NTM 一样，初始先将整个序列嵌入模型的内存中，之后进行 m 步推理，每一步 HAM 会产生一个输入给 LSTM，LSTM 的输出做为模型的输出，同时 LSTM 会提供给 HAM 一个控制向量来指导 HAM 进行更新。每一步推理后 LSTM 和 HAM 的隐藏层都会更新。

假设 HAM 每个节点存储了一个 d 维向量，LSTM 每步推理会产生一个 l 维的控制向量给 HAM。HAM 的基本操作为：

嵌入：\mathbb{N} \rightarrow \mathbb{R}^d，将序列中的一个位置变换为一个 d 维词向量后放到对应的线段树的叶子节点上。

合并：\mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}^d，从线段树的两个儿子的信息中合并出父亲节点的信息。

搜索：\mathbb{R}^d \times \mathbb{R}^l \rightarrow [0,1]，在父亲节点处根据 LSTM 提供的控制向量，选择递归进入左儿子还是右儿子。

写：\mathbb{R}^d \times \mathbb{R}^l \rightarrow \mathbb{R}^d，在叶子节点出根据 LSTM 提供的控制向量，修改叶子节点的值。

HAM 的结构是一棵线段树，初始化方法为依次将序列的每个位置嵌入线段树的叶子节点上，之后自底向上合并信息。

每步推理时，和线段树一样，LSTM 给出了控制向量，从 HAM 的根节点开始，通过搜索操作判断递归到哪个儿子，到达叶节点后，通过写操作修改叶子节点的值，之后回溯递归过程，通过合并操作合并出修改后的信息。

因为这里存在多选一操作（每次递归进入左儿子还是右儿子），所以没有梯度。训练直接使用强化学习中的策略梯度方法。

模型在这些任务上有很高的正确率，并且在大部分任务上有不错的序列长度泛化能力，当序列长度变为原来的 2 至 4 倍时，正确率没有大幅下降。

基于并行加法，乘法器先验的 NTM[6]

这篇文章提出了一种新的神经图灵机 NGPU，文中测试了多个任务包括：高精度二进制加法，高精度二进制乘法，复制序列，翻转序列，复制序列两次，二进制排序。

模型的结构比较简单，设所有序列中最长的一个长度为 n，建立 n 个 GRU 构成的一个序列，定义 CGRU 操作为对常数 W 个 GRU 进行卷积。

初始化时将输入序列做简单变换后嵌入 GRU 序列的每一个位置，在时间维上递归 n 步，每一步对当前序列以 W 为感受野大小做卷积操作，得到下一个时刻的 GRU 序列。在 n 步递归结束后将 GRU 序列经过简单变换依次输出。

这里之所以使用卷积而不是 MLP，其实是故意嵌入了平移不变性方便模型学习，因为在这些任务上序列中每相邻 W 个位置进行的操作都是相同的。

模型的正确率和泛化能力非常好，可以在长度 100 的例子上训练，泛化到长度 2000 的数据下仍然 100\% 正确率。

固定结构的先验的问题

从这两个例子中我们可以看出固定结构先验的问题在于只能处理结构非常特定的任务。他们处理的任务通常人类可以用很简单的代码实现，并且因为使用了具体任务的非常特殊的结构，所以很难拓展到复杂任务上。

线段树是适合模拟排序，栈，队列，优先队列的，难以拓展的问题在于：

1. 先验过强，复杂的任务的动态计算图不局限于自顶向下计算 O(\log n) 层，每一层只能访问常数量的信息，并且只能跳转到两个固定的分支中的一个。该方法只适合学习此类动态特定的计算图，而这些动态计算图一般是人类可以简单写出代码的。

2. 因为只学习了单次操作计算量 O(\log n) 的任务，所以不需要对停机的学习，比如排序只需要执行 n 步后停止即可。

并行加法，乘法器是适合学习加法，乘法，序列复制等操作的，难以拓展的问题在于：

1. 模型的计算图是静态的。

2. 先验过强，甚至无法高效解决稍微复杂一点的表达式求值类任务（如输入是一个有括号，加法，乘法的表达式，输出是表达式的值）。

3. 因为只学习了单次操作计算量 O(n) 的任务，所以不需要对停机的学习，比如加法只需要执行 n 步后停止即可。

其中停机的问题可以像 NTM 那样加入对是否应该停机的学习，但其余问题是本质的。从这里和后面会描述的基于例子的表达式求值任务（局限于表达式树结构），可以看出对通用人工智能的设计一定不能在结构上固定，不然人设计时会利用该结构特性，导致设计出的模型无法拓展到不满足该结构特性的任务上。

组合优化

对 NPC 类问题的组合优化

常见的对 NPC 类问题的组合优化有两种：

1. 直接使用类似 NTM 的神经网络，将问题的输入数据嵌入神经网络，之后执行固定步或让神经网络学习停机，神经网络每一步的输出或者最后的中间结果经过简单变换后做为答案。

2. 使用一个启发式搜索框架，神经网络每一步对当前局面进行评估，来选择递归执行哪一个分支的搜索。

对矩阵乘法的组合优化

有梯度方法

论文地址不记得了。

朴素矩阵乘法需要计算 \Theta(n^3) 个计算的中间结果，并通过这些计算的中间结果的线性组合得到答案矩阵。该文章设计了一种类似于自编码器的结构，尝试减少计算出的中间结果数。

设定超参数 x 表示我们希望使用 x 次乘法解决矩阵乘法问题。之后设计一个 4 层的神经网络结构，第一层为两个输入矩阵，第二层为 2x 个加法的中间结果，第一层和第二层之间是全连接的，边权即为线性组合的权值。第三层为 x 个乘法的中间结果，第二层的每两个点和第三层的一个点连边，运算固定为乘法，这里的乘法实际上是一个激活函数。第四层为输出矩阵，第三层和第四层是全连接的。

由于上述过程处处可微，所以可以直接使用梯度下降进行优化，如果模型学到了高正确率的解，则该解对应一个使用 x 次乘法的矩阵乘法算法。

无梯度方法

AlphaTensor 是一个利用强化学习求解快速矩阵乘法问题的模型。[7]

矩阵乘法的计算过程对应于一个 n^2\times n^2\times n^2 的张量（可以理解为三维数组），C_{i,k}=\sum A_{i,j}\times B_{j,k} 则这个张量的 in+j,jn+k,in+k 位置为 1，其余位置为 0。

矩阵的低秩分解为：一个 n\times n 的矩阵 A 可以分解为两个大小为 n\times k 和 k\times n 的矩阵 B，C，A=B\times C。

推广到三维可以得到张量的低秩分解，即三个 n\times k 的矩阵，图中的 u,v,w 即为分解后的三个矩阵。为了避免无限大的搜索空间，分解后的矩阵每一维限制为 -1,0,1。

模型的每一步操作为：三个矩阵选出同一列，将原张量减去这三个列的积，即A_{i,j,k}\texttt{-=}u_iv_jw_k，最终将张量变为 0。

如果最终通过 x 次操作将张量变为 0，则这里得到了一个秩为 x 的张量分解，每一步操作可以看作是在搜索每个矩阵左边加上一列的具体权值。这里的张量分解对应于一个使用 x 次乘法的矩阵乘法算法。

模型的每一步操作可以看做搜索红色部分的具体边权。问题转换为一个强化学习任务，即最小化将张量变为 0 所需要的操作次数。

AlphaTensor 搜索出的结果不算强，并且距离目前最优时间复杂度 O(n^{2.373}) 很远。

生成 OI 代码

实际上有非常多相关工作，这里只挑几篇比较 OI 的描述。

基于例子

基于例子的代码生成任务指的是先指定一个编程语言，给定一份代码，和这份代码对应的一些测试数据。将测试数据分成测试集和验证集两部分，测试集提供给模型，验证集对模型不可见。模型需要生成一份代码，这份代码可以通过验证集。

因为搜索空间过于巨大，所以基于例子的代码生成任务搜索不到且不应该能搜索到较为复杂的代码（比如你随便洛谷上找一道题）。

HAM

在上文已有描述，学习的任务为翻转序列，排序，归并两个排好序的序列，高精度二进制加法，模拟 map < int5 , int5 >，模拟栈，模拟队列，模拟优先队列。

NGPU

在上文已有描述，学习的任务为高精度二进制加法，高精度二进制乘法，复制序列，翻转序列，复制序列两次，二进制排序。

基于例子的简单程序生成

TODO

基于例子的表达式求值

TODO

基于自然语言题面

基于题面的代码生成任务指的是指定一个编程语言，给定题面的自然语言描述，测试数据对模型不可见，模型需要生成对应这个题面的一份代码，这份代码可以通过测试数据。

个人认为，由于代码生成中存在的复杂结构（递归，动态计算图，无限多选一，硬内存访问），能有效解决代码生成任务的模型接近通用人工智能。

递归：指模拟函数调用。对于图灵完备的神经网络，通用逼近定理在递归的例子上是适用的，但是通用逼近定理不保证神经网络可以通过梯度下降的方法学到复杂递归。

动态计算图：每步计算的计算方式和使用的数据依赖于之前计算产生的结果（参考 if，goto），常见的神经网络方法都是静态计算图，静态计算图模拟动态计算图需要指数级倍的代价，因为动态计算图可以展开为指数级大小的静态计算图，并且没有可以重复利用的部分。

无限多选一，硬内存访问是动态计算图问题的一部分。

基于 AST 先验的 Transformer：TreeGen[9]

该模型尝试将 AST 先验和 Transformer 模型结合。

模型先通过一个叫做 AST Reader 的 Transformer 从自然语言题面生成一棵 AST。语法规则的先验是人为设计的。生成 AST 的模型也是一个 Transformer，需要先通过 self attention 计算每个位置和全局其他位置的贡献。之后的过程可以通过一个分类任务实现，即每一步进行一次分类，分类只需要决定具体使用哪一个语法规则。当到达 AST 的一个叶子节点时，叶子节点上一定是一个终结符，模型需要学习将该终结符填上什么样的具体常数。因为 Transformer 是 seq2seq 的模型，所以这里生成 AST 的过程是在 AST 的 DFS 序上自回归的。

下图中的后面两部分实际上是同一个 Transformer decoder，AST Reader 是前几层，Decoder 是后几层，因为文章声称过度引入 AST 先验会破坏 Transformer 自己学到的结构（类似于语言学家给 Transformer 加了一堆人为设计的先验后发现表现变差），所以只在前几层中引入了 AST 先验。

之后使用传统算法将这棵 AST 的每个位置填上对应的代码。

文章使用了一个有趣的数据集叫做炉石，下面是该数据集上的代码生成的一个例子。

AlphaCode[10]

AlphaCode 的代码生成模型是使用已有的代码生成模型在 Codeforces 代码组成的数据集上微调得到的。

对每道题面模型会生成上百万份代码，之后先通过题面中给出的样例，可以筛选掉 99\% 无法通过样例的代码。

同时训练另一个 Transformer 模型，该模型输入题面中的输入格式，生成对应输入格式的数据，该数据不保证正确。使用这个模型生成的数据可以对程序进行聚类：如果两份代码在所有生成的数据上都得到了同样的计算结果，则认为这两份代码是相同的。这样聚类后，选出 Top-10 的类，在每个类中选择一份代码提交。

个人认为这么做是因为直接生成代码正确率极低，所以加了一些人为设计的传统算法来筛选。并且 Codeforces 的题面虽然可能写的比较奇怪，但是输入格式一般写的正常，所以可以生成比较合理的数据来筛选。

AlphaCode 并没有解决代码生成任务中的任何本质问题，并且通过特殊设计规避了本来必需的强化学习。

ChatGPT[11]

ChatGPT 提出了一个使用人类的反馈来进行强化学习的方法 RLHF，方法是给定一个 prompt，让模型生成针对该 prompt 的一些回答，然后人对这些回答进行排序，这里排序后的结果提供给另一个模型 RM，RM 负责学习每个回答的价值。每个回答的价值可以产生一个策略梯度，用这个策略梯度来对模型做微调。为了增加数据的利用率，他们使用了 PPO 的方法。

人只做排序不直接标出 reward 的原因是:

1. 有很多人，不同人对 reward 的标注可能差别很大。

2. 人很难标注出合适的 reward（比如给你一道题的几份题解，你需要对每一份题解给出 0 到 100 的分，人经常就标个 70 这样的分，很难标出 78 这样更精细的分并且自己认为是准确的）。

本文提出的方法个人认为是很难拓展到复杂程序生成上的，因为将这种方法用于程序生成的本质等价于用策略梯度方法强化学习程序生成任务。

如果将这种方法推广到程序生成任务，则模型需要生成几份代码，或者对给出的代码进行补全（不需要全部补全只需要生成后面几句内容），人对这些代码评分或者给出排序，表示哪一份代码更接近于人认为的正确代码。这种方法可以减少稀疏奖励的问题（写出的代码如果 AC 则获得 1 的奖励，否则获得 0 的奖励），代价是数据需要人来标注很贵。

现在这种模型用于生产的另一个问题是训练和测试是分开进行的，科学家预训练出一个大模型，之后程序员使用这个大模型来辅助自己生成代码。大模型几乎无法利用程序员产生的历史数据来进行学习。

如图，当你和对话模型对话时，Transformer 自回归地生成回答，所以可以利用 attention 机制访问之前生成的中间结果。

但是当你将模型关了并且重新打开，则模型无法利用你上次对话的中间结果，即每次重新开始自回归时之前学习的内容会被清空。

如果模型一直自回归，则理论上可以进行学习（这里实际上是一种元学习，需要模型学到一个如何在自回归过程中进行学习的学习算法才能进行），但是这样所有的历史数据拼起来会产生一个非常长的序列，因此会遇到 Transformer 的 attention 机制的瓶颈。

Transformer 实际上是不能处理长的序列的：

1. 第一个问题是 Transformer 的位置编码，原论文中的方法会将第 y 个位置与第 10000x+y 个位置混淆，如果位置编码是常数则都会遇到这个问题。

2. 第二个问题是平方的计算代价，这个会导致序列过长时计算速度显著下降。并且之前描述过 Transformer 稀疏化方法的问题。

常见的处理方式是记录下你产生的历史数据，使用一个外部的记忆系统（比如一个搜索引擎），每次自回归时，将你提问的内容做为 key 提供给记忆系统，查询出相关内容，再直接将部分相关内容拼接到 prompt 前面，中间加一个分隔符，然后在加了相关内容的 prompt 上做自回归。对记忆系统的学习也可以使用本文提出的 RLHF 的方法，由人来生成希望查找的内容，并对他查找得到的结果做排序。

Reference

引用格式写的很不正规。

[1] https://arxiv.org/pdf/2112.00114.pdf

[2] https://arxiv.org/pdf/2110.14168.pdf

[3] https://arxiv.org/pdf/2211.10435.pdf

[4] https://arxiv.org/pdf/1506.02516.pdf

[5] https://arxiv.org/pdf/1602.03218.pdf

[6] https://arxiv.org/pdf/1511.08228.pdf

[7] https://www.nature.com/articles/s41586-022-05172-4

[9] https://arxiv.org/pdf/1911.09983.pdf

[10] https://www.deepmind.com/blog/competitive-programming-with-alphacode

[11] https://openai.com/blog/chatgpt/