?

賽題背景

計算機能從幾個例子中學習復雜、抽象的任務嗎？

當前的機器學習技術(shù)是需要大量數(shù)據(jù)和脆弱的，他們只能理解他們以前見過的模式。使用當前的方法，一個算法可以通過大量數(shù)據(jù)的曝光中獲得新的技能，但是可以廣泛推廣到許多任務的認知能力仍然是難以捉摸的。這使得創(chuàng)建能夠處理現(xiàn)實世界的可變性和不可預測性的系統(tǒng)非常具有挑戰(zhàn)性，例如家用機器人或自動駕駛汽車。

然而，其他方法，如歸納編程，提供了更人性化的抽象和推理的潛力。抽象與推理語料庫（ARC）提供了一個衡量未知任務人工智能技能習得的基準(benchmark)，其限制條件是只有少數(shù)演示可以學習復雜的任務。人工智能提供了一個快速解決未來問題的機會。Kaggle抽象和推理挑戰(zhàn)邀請您嘗試將未來帶入現(xiàn)在！

本次比賽由Keras神經(jīng)網(wǎng)絡庫的創(chuàng)建者franois Chollet主持。Chollet關(guān)于智力測量的論文提供了ARC基準背后的背景和動機。

在這場比賽中，你將創(chuàng)造一個AI，它可以解決從來沒有見過的推理任務。每個ARC任務包含3-5對訓練輸入和輸出，以及一個測試輸入，您需要使用從訓練示例中學習的模式預測相應的輸出。

如果成功，你將有助于使計算機更接近人類認知，你將打開一扇通向全新人工智能應用程序的大門！

賽題評估

1. 評估指標

比賽采用Top 3的錯誤率作為評價指標。對于測試集中的每個任務，您最多可以為每個測試輸入網(wǎng)格預測3個輸出。每個任務輸出都有一個ground truth。對于給定的任務輸出，如果3個預測輸出中的任何一個包含ground truth，則該任務的誤差為0，否則為1。最終得分是所有任務的平均誤差。

數(shù)學上，對于每個任務,你的算法最多可以進行三次預測, 其中,任務關(guān)于ground truth 的誤差為：

其中,在的時候為0,否則為1，整體的錯誤分數(shù)為：

2. 輸出預測的形式

訓練、評估以及測試輸入數(shù)據(jù)都采用相同的JSON格式。輸入和輸出存儲在2d的python列表中。但是，必須將輸出預測展平為字符串，列表行用|分隔。

例如，輸出[[1,2]，[3,4]]應重新格式化為|12|34|作為預測。每個任務最多可以有3個輸出預測，它們應該用空格分隔。詳見sample.csv。

以下python代碼將2d list pred轉(zhuǎn)換為正確的格式：

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，帶有一個指標，指示您要為該任務預測哪個輸出。大多數(shù)任務只有一個輸出（即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.

數(shù)據(jù)描述

本次競賽目的是創(chuàng)造一個能夠解決抽象推理任務的算法。比賽的形式與以往的比賽有很大的不同，因此請仔細閱讀此信息，并根據(jù)需要參閱補充文件。

在查看任務時，“test-taker”可以訪問演示對（訓練pairs）的輸入和輸出，以及測試pair的輸入。目標是構(gòu)造與測試輸入網(wǎng)格相對應的輸出網(wǎng)格，每個測試輸入使用3次試驗。”構(gòu)建輸出網(wǎng)格”包括選擇輸出網(wǎng)格的高度和寬度，然后用符號（0到9之間的整數(shù)，可視為顏色）填充網(wǎng)格中的每個單元格。只有精確解（所有單元格都符合預期答案）才可以說是正確的。

在抽象和推理語料庫github頁面上可以找到一個附加信息以及一個交互式應用程序來探索本次比賽的目標。強烈建議您下載并瀏覽互動應用程序，這是了解競賽目標的最佳方式。

任務文件以兩種方式存儲：

• training:包含用于培訓的任務文件（400個任務）。使用這些prototype你的算法或訓練你的算法獲得ARC相關(guān)的認知先驗知識。
• 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數(shù)據(jù)集的語言，但是這會產(chǎn)生一些歧義。訓練和評估任務都包含輸入和輸出的訓練和測試對。排行榜將使用100個看不見的測試任務進行評分。測試任務將包含輸入和輸出的訓練對，但您只獲得任務測試輸入。您的算法必須預測測試輸出。對于用于排行榜得分的100個任務，大多數(shù)只有一個測試輸入需要相應的輸出預測，盡管對于少數(shù)任務，您將被要求對兩個測試輸入進行預測。示例中顯示的output_id在sample_submission.csv表示任務id作為測試輸入id。

• training：一個任務文件的文件夾，包含400個任務的訓練數(shù)據(jù)；
• evaluation：一個任務文件的文件夾，包含400個任務，使用這些來做最后算法的評估。
• test：
• 數(shù)據(jù)頁上的test文件夾包含從evaluation文件夾復制的前100個任務，但沒有答案；其目的是為了確保代碼在同步重新運行時正常工作。
• 同步重新運行的test文件夾包含100個（未查看的）任務，用于為模型評分；這些相同的未查看的100個任務用于公共和私有排行榜。您將無權(quán)訪問這些任務，并且在同步重新運行期間將計算您的公共/私人分數(shù)。
• sample_submission.csv：格式正確的示例提交文件；output_id列包含需要預測的任務和測試輸出id；此數(shù)據(jù)頁上的示例提交的output_id列表將與重新運行的筆記本同步不同。

Top1方案解讀

核心解決方案的主要組成部分是一個DSL，它應用了142個一元變換中的4個（基于42個不同的函數(shù)，其中一些函數(shù)有多個變體）。我通過減少重復來有效地枚舉變換，然后通過貪婪地將它們堆疊以適合訓練樣本來組合它們。一切都在C++中實現(xiàn)（沒有依賴關(guān)系）可以并行運行。一個簡單的調(diào)度程序試圖充分利用9小時/16gb的內(nèi)存預算。

1. Transformation的選擇和工程

圖像轉(zhuǎn)化的最重要的幾點：

• Cut(Image) -> list of images
• 嘗試找出一個背景色，并將剩余的像素分割成角連接的組；
• filterCol (image, color) -> image
• 刪除除給定顏色以外的所有顏色（將其設(shè)置為0）;
• colShape (image, color) ?-> image
• 將所有非零像素更改為“color”。
• composeGrowing (list of images) -> image
• 將圖像列表堆疊在一起，將0視為透明。非零像素最少的圖像位于頂部。
• compress (image) -> image
• 提取包含所有非零像素的最小子圖像
• rigid (image, id) ->image
• 進行旋轉(zhuǎn)(0/90/180/270)并且翻轉(zhuǎn)
• pickMax (list of images, id) ?-> image
• 提取具有最大屬性的圖像，例如id=0提取具有最多非零像素的圖像。

我通過手工解決100個訓練任務和100個評估任務，然后提取有用的函數(shù)來構(gòu)造轉(zhuǎn)換。當它看起來合理時進行泛化（比如添加所有旋轉(zhuǎn)，如果我使用其中一個）。我沒有嘗試刪減轉(zhuǎn)換，因為給定的任務似乎不能代表排行榜上需要的任務。

轉(zhuǎn)換堆疊得非常好的，甚至解決了我在手工求解時使用其他轉(zhuǎn)換（模型不可用）的幾個任務。

2. 集成

在最后一個模型中，我運行了4種不同的配置并對預測結(jié)果進行了集成。

我運行轉(zhuǎn)換搜索深度3，深度3增加對角線翻轉(zhuǎn)（乘以兩個對角線翻轉(zhuǎn)），最后運行深度4，直到時間或者內(nèi)存用完為止。根據(jù)以下標準選擇最佳預測，最高標準是最重要的標準：

• 處理了最多的訓練樣本
• 最小深度解決方案
• 以貪婪stacker least堆疊的圖像

3. Tricks

用對角線翻轉(zhuǎn)的任務來增加我的樣本，這是一個簡單的技巧，它給了我明顯更好的分數(shù)。通過根據(jù)一些啟發(fā)式方法重新映射顏色來預處理所有樣本，效果也出奇地好。

我相信我比其他競爭對手的主要優(yōu)勢是我在競爭性編程方面的經(jīng)驗。它允許我快速高效地在C++中編寫大量的圖像轉(zhuǎn)換，這使我可以通過與Python實現(xiàn)或其他不太優(yōu)化的解決方案相比，搜索更多的轉(zhuǎn)換組合。

4. 運行時間

一個讓我的方法運行得更快的自然方法是減少搜索深度。當我用了整整9個小時時，我可以在深度4運行大約一半的問題，而在深度3運行大約快20倍（占用的內(nèi)存少20倍）。在開發(fā)過程中，我會在深度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