首頁 > 科技

MIT微軟為AI量身打造了一套leetcode程式設計題

2021-06-26 15:51:31

豐色 發自 凹非寺量子位 報道 | 公眾號 QbitAI

你見過這種程式設計題目描述方式嗎?

不用自然語言描述,也沒有輸入輸出示例,你所看到的就只有一個Python函數

這是來自MIT、Allen AI和微軟的研究人員提出的一種全新的程式設計題目描述方法

每個題目都由一個簡短的Python函數f定義,目標是找到一個輸入x,使f輸出true。

這樣的題目形式可以讓AI審題更容易,人類程式設計師的理解也不會受到影響。

AI程式設計,道路真是越來越平了啊。

接下來就來詳細看看這個研究吧。

沒有自然語言描述的程式設計題目

再來解釋一下這種描述方法:

題目採用Python函數的形式,參數為答案。

解題的目標是找到使函數輸出為真的輸入x,即滿足f(x)= true的正確答案。

現在請你舉一反三:求解一個有1000個不連續「o」的字元串,用這種新形式如何描述呢?

正確答案:

下面是另外兩道題目的描述示例。

動態規劃—最長單調遞增子序列問題:

經典的漢諾塔(Towers of Hanoi ):

研究人員按此種出題形式囊括了各種程式設計題,提出來一個開源資料集:叫做P3。

該資料集題型非常全面:涉及不同難度、不同領域和不同演算法工具等方面的題目。

有簡單的字元串操作問題;

有經典如漢諾塔和國際象棋(例如,騎士遊歷演算法和N皇后問題變體)等難題;

也有兩人挑戰尋找最佳策略的題型,如井字棋(Tic-Tac-Toe)、石頭剪刀布、珠璣妙算Mastermind等;

還包括來自國際數學奧林匹克競賽(IMO)和國際大學生程式設計競賽(ICPC)的題目,如各種圖論和數論難題。

一共包含208種題型、14萬+的題目,並且還在不斷更新中。

每個題目都提供了至少一種答案。

這套新穎的程式設計挑戰題庫資料集,抓住了程式設計題目的本質,可用於教AI程式設計評估AI的程式設計能力

研究人員表示,這套題可以對AI的程式設計能力進行客觀評估。因為不用檢視答案,就能直接驗證解答的正確性。因此,這種題目不會增加AI學習任何答案偏差的負擔。

希望這個資料集可以開發出新的AI程式設計解決方案

不同AI求解器根據這些題目程式設計的效果如何呢?

研究人員做了一些深入的實驗,開發了基於隨機森林、Transformer和不同類型GPT-3 prompts的AI求解器,它們採用不同參數列舉、自頂向下的方法,使用這個P3資料集來評估效能。

首先,測試這些求解器在這個資料集上利用此前解決題目的方法來解決新題目的自舉效率(bootstrapping efficacy)。

結果發現,增加嘗試次數可以解決新題目。但它們也能通過學習過去的經驗,更快地解決新的難題。

下圖為這些AI求解器在不同嘗試次數下的已解決題目數量:

而在一項小的使用者研究中,21名在Python程式設計方面有不同經驗年限的程式設計師完成了不同難度的30個題目。每個題目最多分配6分鐘的時間來解決。

用這個資料集評估AI與人類程式設計師對程式設計題難度的感知發現:

人類覺得難的題對AI來說也更難,現階段情況下,AI求解器能解決的大多數題都是對人類來說比較簡單的。

上圖表示人類和AI對各種題目的難度打分,按人類分數排序。人類的難度分數通過超出允許的最大解題時間的平均分數來衡量,AI的則是根據解題所需的嘗試次數。

另外,AI用這種形式的題目可以解決了60% 的難題,初學者和有經驗的程式設計師平均分別解決了 76% 和 87% 的難題。

總的來說,利用這個新穎的資料集,通過精心設計的AI求解器,可以大大減少AI程式設計求解所需的嘗試次數、並解出更多的題目。

因此,研究人員希望,這個新的程式設計題庫資料集能支援大家研究和開發新的AI程式設計解決方案,提高AI程式設計的效率和效能。

此前,UC伯克利曾訓練AI刷LeetCode,總共5000道題的測試中,AI能做出15%。

不知道使用這個資料集訓練,AI程式設計的能力又會達到什麼水平呢?

論文地址:https://arxiv.org/abs/2106.05784

開源資料集連結:https://github.com/microsoft/PythonProgrammingPuzzles


IT145.com E-mail:sddin#qq.com