【数据竞赛】Kaggle ARC Top1方案解读

作者: SW King

Kaggle：Abstraction and Reasoning Challenge Top1方案解读

赛题背景

计算机能从几个例子中学习复杂、抽象的任务吗？

当前的机器学习技术是需要大量数据和脆弱的，他们只能理解他们以前见过的模式。使用当前的方法，一个算法可以通过大量数据的曝光中获得新的技能，但是可以广泛推广到许多任务的认知能力仍然是难以捉摸的。这使得创建能够处理现实世界的可变性和不可预测性的系统非常具有挑战性，例如家用机器人或自动驾驶汽车。

然而，其他方法，如归纳编程，提供了更人性化的抽象和推理的潜力。抽象与推理语料库（ARC）提供了一个衡量未知任务人工智能技能习得的基准(benchmark)，其限制条件是只有少数演示可以学习复杂的任务。人工智能提供了一个快速解决未来问题的机会。Kaggle抽象和推理挑战邀请您尝试将未来带入现在！

本次比赛由Keras神经网络库的创建者franois Chollet主持。Chollet关于智力测量的论文提供了ARC基准背后的背景和动机。

在这场比赛中，你将创造一个AI，它可以解决从来没有见过的推理任务。每个ARC任务包含3-5对训练输入和输出，以及一个测试输入，您需要使用从训练示例中学习的模式预测相应的输出。

如果成功，你将有助于使计算机更接近人类认知，你将打开一扇通向全新人工智能应用程序的大门！

赛题评估

1. 评估指标

比赛采用Top 3的错误率作为评价指标。对于测试集中的每个任务，您最多可以为每个测试输入网格预测3个输出。每个任务输出都有一个ground truth。对于给定的任务输出，如果3个预测输出中的任何一个包含ground truth，则该任务的误差为0，否则为1。最终得分是所有任务的平均误差。

数学上，对于每个任务,你的算法最多可以进行三次预测, 其中,任务关于ground truth 的误差为：

其中,在的时候为0,否则为1，整体的错误分数为：

2. 输出预测的形式

训练、评估以及测试输入数据都采用相同的JSON格式。输入和输出存储在2d的python列表中。但是，必须将输出预测展平为字符串，列表行用|分隔。

例如，输出[[1,2]，[3,4]]应重新格式化为|12|34|作为预测。每个任务最多可以有3个输出预测，它们应该用空格分隔。详见sample.csv。

以下python代码将2d list pred转换为正确的格式：

def flattener(pred):
    str_pred = str([row for row in pred])
    str_pred = str_pred.replace(', ', '')
    str_pred = str_pred.replace('[[', '|')
    str_pred = str_pred.replace('][', '|')
    str_pred = str_pred.replace(']]', '|')
    return str_pred

3. 提交文件

对于测试集中的每个任务输出output_id，您最多可以做出3个预测。output_id是任务的id，带有一个指标，指示您要为该任务预测哪个输出。大多数任务只有一个输出（即0），尽管有些任务有两个必须预测的输出（即0，1）。该文件应包含标头，并具有以下格式：

output_id,output
00576224_0,|32|78| |32|78| |00|00|
...
12997ef3_0,|00000000000|01100000000|11000000000|...
12997ef3_1,|00000000000|01100000000|11000000000|...
etc.

数据描述

本次竞赛目的是创造一个能够解决抽象推理任务的算法。比赛的形式与以往的比赛有很大的不同，因此请仔细阅读此信息，并根据需要参阅补充文件。

在查看任务时，“test-taker”可以访问演示对（训练pairs）的输入和输出，以及测试pair的输入。目标是构造与测试输入网格相对应的输出网格，每个测试输入使用3次试验。”构建输出网格”包括选择输出网格的高度和宽度，然后用符号（0到9之间的整数，可视为颜色）填充网格中的每个单元格。只有精确解（所有单元格都符合预期答案）才可以说是正确的。

在抽象和推理语料库github页面上可以找到一个附加信息以及一个交互式应用程序来探索本次比赛的目标。强烈建议您下载并浏览互动应用程序，这是了解竞赛目标的最佳方式。

任务文件形式

任务文件以两种方式存储：

• training:包含用于培训的任务文件（400个任务）。使用这些prototype你的算法或训练你的算法获得ARC相关的认知先验知识。
• evaluation:包含用于评估的400个任务的任务文件;

任务都是JSON形式存储的，每个JSON文件包含两个field的字典：

• train：描述input/output对，是pairs的list(一般是三个pairs）；
• test：test input/output对，是pairs的list(一般是1 pair);

一个pair是带有两个fields的字典：-“input”：pair的输入“grid”；-“output”：pair的输出“grid”。

一个“grid”是一个0-9之间的长方形矩阵，最小的可能的grid size是1*1，最大的是30 * 30；

注意：对于此次竞赛，我们保留ARC数据集的语言，但是这会产生一些歧义。训练和评估任务都包含输入和输出的训练和测试对。排行榜将使用100个看不见的测试任务进行评分。测试任务将包含输入和输出的训练对，但您只获得任务测试输入。您的算法必须预测测试输出。对于用于排行榜得分的100个任务，大多数只有一个测试输入需要相应的输出预测，尽管对于少数任务，您将被要求对两个测试输入进行预测。示例中显示的output_id在sample_submission.csv表示任务id作为测试输入id。

文件

• training：一个任务文件的文件夹，包含400个任务的训练数据；
• evaluation：一个任务文件的文件夹，包含400个任务，使用这些来做最后算法的评估。
• test：
  • 数据页上的test文件夹包含从evaluation文件夹复制的前100个任务，但没有答案；其目的是为了确保代码在同步重新运行时正常工作。
  • 同步重新运行的test文件夹包含100个（未查看的）任务，用于为模型评分；这些相同的未查看的100个任务用于公共和私有排行榜。您将无权访问这些任务，并且在同步重新运行期间将计算您的公共/私人分数。
• sample_submission.csv：格式正确的示例提交文件；output_id列包含需要预测的任务和测试输出id；此数据页上的示例提交的output_id列表将与重新运行的笔记本同步不同。

Top1方案解读

核心解决方案的主要组成部分是一个DSL，它应用了142个一元变换中的4个（基于42个不同的函数，其中一些函数有多个变体）。我通过减少重复来有效地枚举变换，然后通过贪婪地将它们堆叠以适合训练样本来组合它们。一切都在C++中实现（没有依赖关系）可以并行运行。一个简单的调度程序试图充分利用9小时/16gb的内存预算。

1. Transformation的选择和工程

图像转化的最重要的几点：

• Cut(Image) -> list of images
  • 尝试找出一个背景色，并将剩余的像素分割成角连接的组；
• filterCol (image, color) -> image
  • 删除除给定颜色以外的所有颜色（将其设置为0）;
• colShape (image, color) -> image
  • 将所有非零像素更改为“color”。
• composeGrowing (list of images) -> image
  • 将图像列表堆叠在一起，将0视为透明。非零像素最少的图像位于顶部。
• compress (image) -> image
  • 提取包含所有非零像素的最小子图像
• rigid (image, id) ->image
  • 进行旋转(0/90/180/270)并且翻转
• pickMax (list of images, id) -> image
  • 提取具有最大属性的图像，例如id=0提取具有最多非零像素的图像。

我通过手工解决100个训练任务和100个评估任务，然后提取有用的函数来构造转换。当它看起来合理时进行泛化（比如添加所有旋转，如果我使用其中一个）。我没有尝试删减转换，因为给定的任务似乎不能代表排行榜上需要的任务。

转换堆叠得非常好的，甚至解决了我在手工求解时使用其他转换（模型不可用）的几个任务。

2. 集成

在最后一个模型中，我运行了4种不同的配置并对预测结果进行了集成。

我运行转换搜索深度3，深度3增加对角线翻转（乘以两个对角线翻转），最后运行深度4，直到时间或者内存用完为止。根据以下标准选择最佳预测，最高标准是最重要的标准：

• 处理了最多的训练样本
• 最小深度解决方案
• 以贪婪stacker least堆叠的图像

3. Tricks

用对角线翻转的任务来增加我的样本，这是一个简单的技巧，它给了我明显更好的分数。通过根据一些启发式方法重新映射颜色来预处理所有样本，效果也出奇地好。

我相信我比其他竞争对手的主要优势是我在竞争性编程方面的经验。它允许我快速高效地在C++中编写大量的图像转换，这使我可以通过与Python实现或其他不太优化的解决方案相比，搜索更多的转换组合。

4. 运行时间

一个让我的方法运行得更快的自然方法是减少搜索深度。当我用了整整9个小时时，我可以在深度4运行大约一半的问题，而在深度3运行大约快20倍（占用的内存少20倍）。在开发过程中，我会在深度2上运行，这比深度3快15倍，同时解决评估集上80%的任务。

参考文献

1. https://www.kaggle.com/c/abstraction-and-reasoning-challenge/discussion/154597
2. https://www.kaggle.com/c/abstraction-and-reasoning-challenge/overview