【AlphaCode】Competition-Level Code Generation with AlphaCode

学习这篇论文之前，先来看个AlphaCode在编程竞赛上的一个应用：
题目链接：Backspace
题意：有一个字符串A，现在将其一个一个输入至B中，在输入一个字符时，如果按下backspace，那么这个字符不会被键入，而且如果B不为空，则B.back()也会被删除，现给出一个字符串C，问能否得到一个B，使得B=C

下面代码是AlphaCode自动生成的题解，可以说相当炸裂！

Paper Link: Competition-Level Code Generation with AlphaCode

自动生成Code系列文章解读：
【Codex】Evaluating Large Language Models Trained on Code

Abstract

编程是非常有用且很常见的解决问题的工具。能协助程序员编程或独立生成程序的研发系统可以使编程更富有创造力和易用性，然而基于AI的编程工具仍具有挑战性。最近的一些大尺寸语言模型在编程上还不错，但只是对一些简单的编程任务。当面对复杂的、未见过的问题【不仅仅是将一些指令翻译为代码这类任务】时，模型效果仍然有限。例如，需要对算法深刻理解的编程竞赛、复杂的语言模型仍然极具挑战性。为了解决这类问题，我们提出了 AlphaCode ，针对哪些需要深度推理的算法问题，可以给出一些不错的答案。我们在CodeForces平台上评估了模型，在超过5000人参加的竞赛中，可以超过54.3%的人。对于取得这么好的结果，我们发现有三个点是很关键的：1）一个大范围的干净的数据集；
2）一个大的可以高效抽样的基于Transformer的架构；
3）一个高效的采样方法，可以根据程序运行结果将候选结果过滤到一个小的结果级。

Introduction

作者对比了之前的 Codex，指出Codex中的问题集只是由一些相对简单的任务组成，答案都比较短，远不同于真实世界中的编程问题。用通用编程语言C++或Python等生成真实的编码往往从问题的描述开始，仍然是一个开放性的问题。生成短的代码片段和完整的程序的差别就类似于命令式和陈述式的解决问题。前者某种程度上将任务直接翻译为代码比较类似，甚至可以降低到只是调用API的程度。相反，生成完整的程序就需要对任务的理解，怎么实现等，需要很强的算法推理能力。
AlphaCode在有超过5000参加的十道竞赛题上的测试结果，平均可以超过54.3%的人；另外，根据作者团队预估，AlphaCode可以取得1238分的成绩，基本可以高于72%的参赛选手。

Datasets

和Codex一样，AlphaCode同样使用了两份数据集。预训练使用GitHub数据，微调使用了CodeContests数据。
GitHub：截止到2021/07/14的数据，包含C++, C#, Go, Java, JavaScript, Lua, PHP, Python, Ruby, Rust, Scala, and TypeScript等语言。清洗策略：过滤掉超过1MB的数据、超过1000字符的行、自动生成的代码等。最后使用了 715.1GB 的数据。
CodeContests：包含两个网站的数据，Codeforces 和 CodeNet

Approach

方法如下图，主要包括4个步骤：

1. 基于一个标准的语言建模目标函数，使用Transformer模型架构在GITHub数据上预训练模型。这个模型可以合理地表征人类编码空间，可以极大地减少搜索量级。
2. 使用带tempering的GOLD目标函数，结合编程竞赛数据集，微调模型。可有进一步降低搜索空间，
3. 给每个编程题目生成一个较大的样本集；
4. 过滤这个样本集，得到一个较小的候选结果集。
   

Model architecture

AlphaCode使用了 encoder-decoder 网络结构，Codex只使用了decoder结构。考虑到问题的描述长度基本上相当于2倍问题解的长度，对编码器使用了1536个tokens，解码器使用了768个tokens。作者团队进一步研究发现，在不降低问题解决率的情况下，较浅的编码器和较深的解码器可以加快训练速度。详细模型结构及参数见下表：

Results

AlphaCode 在十轮竞赛上的表现情况：