AlphaCode: 超越程序员的编程神器

前言

DeepMind 祭出超越近半程序员的编程版“阿尔法狗” AlphaCode，基于 Transformer 的模型，并声称其编写的计算机程序具有竞争力，能与人类普通程序员相媲美。这是继 OpenAI 的 Codex 和 GitHub 的 Copilot之后，将码农距离失业的进程又给推进了一步！当然还有chatGPT！(摘自各大媒体评价)

背景

Codex

• CodeX和GPT-3模型本质上没有区别，训练数据不同，参数权重不同，训练方法不同，用代码数据训练出来的

  • 比如添加了表示不同长度空格的token，这可以减少30%的词典大小
  • CodeX在生成代码时如果生成的token是：‘nclass’, ‘ndef’, ‘n#’, ‘nif’, or ‘nprint’ 时就停止生成
  • pass@k 就是每次生成token时按照softmax概率sample（核采样），pass@1就是每次选择概率最高的那个token

• CodeX尝试了从头训练和基于 GPT-3 的参数 fine-tuning，结果发现基于 GPT-3 的参数 fine-tuning 并没有取得效果上的提升，但基于 GPT-3 的参数 fine-tuing 可以收敛的更快，因此，论文中都采用的是这种训练策略。

• CodeX是在Github的159GB的代码文本上无监督的训练的，论文造了一个和HumanEval数据集格式一致的Supervised Fine-Tuning 数据集，在这个数据集上fine-tuning后的模型是CodeX-S

• 局限性

  • CodeX已经看过了数量惊人的代码，但是只能写出比较简单的代码，基本上是在背代码和代码组合
  • Docstrings 很长时，代码质量下降（AlphaCode做的事）
  • 和数学相关的代码写的很不好

AlphaCode

• 作者介绍说，大规模语言模型已经证明了其生成代码的惊人能力，比如Codex，但是这些模型在解决更复杂、更难理解、需要深入推理的问题时仍表现欠佳，这些问题深入需要理解算法，而不是单纯的翻译

  • Codex论文中使用的问题大多由简单的任务描述和简短的解决方案组成，远没有实际编程复杂
  • 生成简短的代码片段通常相当于将任务规范直接“翻译”为代码
  • 生成代码通常依赖于理解任务并找出完成任务的方法，这需要更深入的算法推理

• 为了解决这个问题，DeepMind推出了AlphaCode，这是一个代码生成模型，它可以为这些需要更深入推理的问题创建新的解决方案

  • 解决这些问题需要理解复杂的自然语言描述，对以前看不见的问题进行推理，掌握广泛的算法和数据结构，以及100+行code

• 在Codeforces平台上，模拟评估中，AlphaCode在参与人数超过5000人的比赛中平均排名前54.3%

• 作者指出，实现如此优异成绩的三个重要因素是：

  • 训练数据足够大且质量高
  • Transformer 预训练模型能够将训练数据中涵盖的知识编码到模型中
  • Sampling & Evaluation 的海量试错机制（先生成海量可能的答案，再一步步缩小搜索空间）

想要解决的问题

编程竞赛

• AlphaCode 参加的是一个名为 Codeforces 的在线编程平台，题目比较像 ACM ICPC 或者信息学奥林匹克竞赛

• Codeforces 上的题目五花八门，但是都需要参赛者编程求解

  • 每个题目有描述，有输入样例，有正确的输出样例，即test cases
  • 如果提交的程序能够将所有test cases都跑出正确的结果，那么就算该题通过
  • 一道题只有10次试错机会

• 编程比赛中解决问题一般需要三个步骤：

  • 阅读并理解跨越多个段落的自然语言描述

    • 与问题无关的叙事背景、所需解决方案的描述、输入和输出格式，以及一个或多个示例输入/输出对

  • 想出有效的算法来解决这个问题

    • 需要对问题进行理解和推理，以及对算法和数据结构的深入理解
    • 能够在问题指定的输入大小和时间限制内运行完成

  • 代码实现

    • 考虑到执行时间的限制，参赛者可以在example tests上测试代码，多次调试、修复和重新运行候选提交

评估

• AlphaCode使用的度量方式是“每个问题的样本数k中选择n个进行提交”，表示为n@k

  • 区别于codex中的pass@k，将提交数量限制为𝑛 模拟错误提交的惩罚
  • 固定k这对于比较不同的评估很重要，因为我们发现效果随着样本数量的增加而增加

数据集

预训练阶段帮助模型学习良好的代码表示并流畅地生成代码，而微调阶段帮助模型适应目标竞争编程领域

• 预训练数据集：GitHub的开源代码

  • 取自2021年7月14日前的数据
  • 代码语言：C++、C#、Go、Java、JavaScript、Lua、PHP、Python、Ruby、Rust、Scala和TypeScrip
  • 过滤掉了所有大于1MB或行长度超过1000个字符的文件
  • 删除了同一文件的重复项，忽略空格
  • 数据集大小715GB

• 微调数据集：CodeContest

  • 包括从Codeforces平台中收集的问题、解决方案和测试案例、现有的其他竞赛数据集

  • 为了防止数据泄露：

    • CodeContest中的所有训练数据使用2021/07/14之前的数据
    • 验证集使用2021/07/15和2021/09/20之间的数据
    • 测试集使用2021/09/21之后发布的问题

  • 数据格式

    • 包括难度等级和标签（例如“贪婪”或“dp”）
    • 包含用C++、Python和Java编写的正确和错误的人工提交。每个问题都包括可以从平台访问的测试用例、问题陈述中的测试用例、比赛结束后的测试用例
    • 

• 假阳性和慢阳性问题

  • 由于测试样例不足导致假阳、正确但不满足时间和内存限制的慢阳

    这两个问题在先前的数据集和程序合成文献中都很常见

  • 

  • 生成额外的测试输入来降低数据集的假阳性率和慢阳性率，这些测试用例是通过改变现有的测试输入生成的

    • 对二进制输入应用位翻转，随机递增或递减整数，以及交换和更改字符串中的字符
    • 改变后的输入通过运行解决方案来验证，并检查所有解决方案是否产生相同的输出

方法

• AlphaCode整体架构如下图所示：

• 基于github的数据进行预训练、在竞赛数据集上微调、生成大量样本、使用示例程序进行过滤和聚类、筛选一小组候选样本评估

模型结构

• AlphaCode选择了基于transformer的编码器+解码器结构

• 为了降低从模型中采样的成本，在多头注意力机制中，使用一组完整的query，但每个关注块共享key和value

  • 
  • 注意力机制，可读以下文章
  • 注意力机制到底在做什么，Q/K/V怎么来的？一文读懂Attention注意力机制
  • The Illustrated Transformer

• 编码器使用1536个token，解码器使用768个token，因为作者发现大部分竞赛问题中题干是code的2倍左右

  • 浅编码器和深解码器可以显著提高训练效率，而不会影响问题解决率

• SentencePiece tokenizer，词表大小8000 tokens

预训练

• github数据上进行预训练

• 损失函数

  • decoder：standard cross-entropy next-token prediction loss
  • encoder：masked language modeling loss

• 基础1B参数模型训练了10^6个steps，batch sizes为256。41B模型很早就停止训练了，原因是资源不足

• 优化器：AdamW

  • 𝛽1 = 0.9, 𝛽2 = 0.999 for {300M, 1B, 3B} models
  • 𝛽2 = 0.95 for {9B, 41B} models
  • 权重衰减（L2正则化）系数0.1（减少过拟合）
  • learning rate：初始10^-4，预训练结束时以余弦方式衰减到10^-5

微调

• CodeContest数据集上进行微调，将问题描述喂给encoder，解题code喂给decoder

• 损失函数（同预训练）

• learning rate：初始10^-5，预训练结束时以余弦方式衰减到10^-6

• Tempering：在softmax层之前，将模型的输出除以标量温度，使token概率分布在训练时人为地更尖锐。作者观察到当𝑇 = 0.2时，训练分布更清晰，有利于避免过拟合

• Value conditioning & prediction：

  • CodeContest包含正确和错误的解决方案
  • 在值调节中，我们将提交是否正确插入到问题描述中，在训练期间添加了一个辅助值预测任务
  • 在采样时，模型始终以正样本为条件

• GOLD（offline RL algorithm，该算法通过重要性加权从非策略性的示范中学习）：它允许模型既从已经分配了高可能性的token中学习，又可以忽略不在其分布中的token（使其能够专注于精度）

大规模采样

• 采样量级100w+
• python样本和c++样本各50%
• 在自然语言提示中随机化问题标签和评级(对随机标签和评级进行调节可以提高性能)
• 基于预测score的均匀采样（未采用核采样或topK采样）

过滤

• AlphaCode 使用编程题目中的test cases，验证这些生成的代码，这个过程会过滤掉99%的错误代码

聚簇

• 使用示例测试进行过滤仍然可以为每个问题留下数千个候选答案，为了解决这个问题，作者使用相同的模型结构训练了一个单独的用于测试用例的生成模型

• 该模型被训练为从问题描述中预测测试用例，使用示例、隐藏和生成的测试用例作为训练数据，训练后，该模型用于为问题创建新的测试用例

• 尽管这些创建的测试用例不能保证有效，不完美甚至无效的测试输入仍然可以用于对采样程序进行分组

• 根据测试用例将模型生成的候选答案进行聚簇，相同类型下选择1个候选提交（总计10个提交）

  • 如果一些代码的生成结果近乎一样，说明这些代码背后的算法或逻辑相似，可被归为一类
  • 从数目较大的类中选出代码去提交，更有胜算

结果

• 作者模拟评估了在Codeforces 10场比赛中取得了平均54.3%的总排名

• 从2021年12月1日到2021年12月28日，我们对所有Codeforces比赛的最佳系统进行了评估，每场比赛有5000多名参与者，共有10场比赛。

CodeContests数据集评估

• CodeContest测试集是竞赛的超集。结果如表5所示，从100万个样本抽取10个提交，可以解决验证集中34.2%的问题。10万个样本抽取10个提交，解决了验证集中31.8%的问题

解决率与数据集、样本数量、模型参数大小的关系

• 放大数据集的大小可以大大提高模型性能，即使只有10个样本可以提交，扩大样本总数也会导致模型求解率的大幅提高

• 图6 ，求解率与样本数量的关系，随样本数量近似对数线性增加，更好、更大的模型具有更高的斜率

  • 对比10@𝑘 和𝑝𝑎𝑠𝑠@𝑘， 随着样本量的增加，𝑝𝑎𝑠𝑠@𝑘斜率增长更快
  • 更大的模型往往具有更好的模型质量，反映为在对数线性比例曲线中，相同数量的样本，解决率更好

• 图7显示了性能随用于训练和采样的计算量的变化情况

  • 随着更充分的训练，求解率也近似对数线性地增加
  • 较大的模型需要更多的计算来绘制每个样本

不同模型结构对采样速度的影响

• 三种不同结构每秒生成的样本数对比图

过滤和聚类

• 过滤一百万个样本中的99%，每个问题仍有数千个样本可供选择。对剩余样本进行聚类，以提高解决率

  • 在没有过滤的情况下随机选择模型样本
  • 从过滤的样本中随机选择
  • 过滤然后使用聚类来选择样本
  • 允许无限次尝试

对比codex

• APPS数据集（Hendrycks等人，2021）共包含10000个编程问题，在训练集和测试集之间平均分配（入门、面试、竞赛）。

小结

摘自官方博客

• 取得相应成绩所采取的策略

• AlphaCode 成功的主要在于这个 Sampling & Evaluation。这个 Sampling & Evaluation 系统有点类似搜索引擎或者推荐引擎。AI拥有存储和制作海量内容的能力，但无法知道人类真正需要什么。最关键的就是如何从海量内容中进行筛选。搜索或推荐引擎一般会对海量内容进行检索，最终呈现给用户的只有几条内容。海量的内容需要经过几大步骤：召回、粗排、精排、重排。其实就是先从海量的内容库中，先粗略筛选出一千篇的内容，再使用更精细的模型对一千篇进行一次次筛选，最终选择出与用户需求最相关的几篇内容

  • 根据编程题目中的描述等信息，使用第一个Transformer模型，生成百万份代码
  • 使用编程题目中的测试样例test cases验证这百万份代码，把不能通过的过滤掉，剩下大约上千份代码
  • 使用第二个Transformer模型，生成一些test cases
  • 使用第3步生成的test cases，对第2步留下的代码进行验证并聚类，如果两份代码得到的结果相同，则分到同一类。经过聚类后，最终留下10类代码

• 参考：cloud.tencent.com/developer/a…

能力与局限性

是否在训练集中复制代码？

• 对于基于大量数据训练的大型语言模型，人们普遍关注的一个问题是，它们可以通过简单地记忆训练集来解决下游问题

• 模型生成的正确解决方案与整个训练数据集（GitHub+CodeContest，忽略空格）之间最长的公共子串，并将这些匹配的长度分布与人类解决方案进行了比较
• 作者发现，尽管模型解决方案的平均最长公共子串略高，模型解决方案和训练数据之间的公共子字符串大多包含用于读取和解析输入数据格式的代码，而不是用于解决问题的关键逻辑

解决方案中死代码的数量

• 解决方案中死代码的数量（即对程序没有影响的代码行），大量的死代码可能表明模型对其生成的内容了解不足

• 使用抽象语法树（ast）删除未使用的函数和类的结果。AlphaCode生成的死代码数量与人类大致相同

  • 抽象语法树（Abstract Syntax Tree，AST），或简称**语法树**（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构

• 表11是模型在使用不同标签在不同问题类型中的解决率
• 随着模型规模的扩大，所有标签的整体解决率都会提高
• 模型在处理位掩码、排序、数学和贪婪算法的问题上相对较好，但在动态编程（DP）和图方面明显较差

对问题描述的敏感性？

• （a） 表明当给出问题的简化描述时，模型以高得多的比例解决问题
• （b） 表明当给定相关但不同的问题时，解决率显著下降
• （c，d，e，g，h）表明，该模型在很大程度上不受看起来不重要的变化的影响（如用同义词替换单词或删除某些类型细节），但对更大的变化（如删除关键部位单词）有更大的响应

损失和解决率的关系

• 在微调过程中，1B模型的早期训练运行约50k步后，验证集语言建模损失开始增加，而训练损失仍在减少。这通常是出现了过拟合，但是解决率却在继续提高

风险和收益

• 良好的代码生成模型有可能对社会产生积极的革命性影响，然而，与大多数技术一样，这些模型可能会使应用程序产生我们需要防范的社会危害

• 提高程序员的生产力，潜在的应用范围有

  • 代码生成、补全、bug检测

  • 高级代码生成模型可以让开发人员在更高的抽象级别上操作，就像现在程序员不再写汇编语言

  • 衍生工具可以使编程更容易实现

  • 完全以自然语言运行的更极端的系统可以使程序员不需要编码知识就可以创建软件

  • 代码生成工具也可能被不良行为者使用

    • 更好的工具可以更容易地创建新版本的恶意软件，提高开发人员生产力的工具也会提高编写恶意代码的开发人员的生产力
    • 竞争性编程代码生成模型可能在编程竞赛或技术面试中给用户带来不公平的优势

• 偏见、公平：

  • 代码生成模型容易再现其训练数据的缺陷和偏差。当对不同的人类数据语料库进行训练时，这些模型可以加强优势代码社区，减弱边缘化代码社区的影响力
  • 还可能导致低质量的代码，使错误永久化或使用过时的API，从而导致性能和安全问题，可能会减少对新库或编程语言的吸收

• 安全：模型可以生成具有可利用漏洞的代码，这些漏洞可以是来自过时代码的无意漏洞，也可以是恶意参与者在训练集中注入的有意漏洞

• 环境影响：与大规模语言模型一样，基于transformer的代码生成模型需要大量的计算能力

• 知识产权：用于训练代码生成模型的大型训练语料库存在知识产权问题

• 高级人工智能风险：长远来看，编码能力可能会导致模型能够自编码和改进自己，从而出现越来越先进的系统

参考资料

1. www.science.org/doi/10.1126…
2. 官网介绍www.deepmind.com/blog/compet…
3. 竞赛网站codeforces.com/contest/162…
4. learn-nlp-with-transformers/2.2-图解transformer.md at main · datawhalechina/learn-nlp-with-transformer
5. The Illustrated Transformer
6. blog.csdn.net/yanguang147…
7. blog.csdn.net/qq_45655136…
8. AlphaCode.pdf