用深度學習解決Bongard問題

摘要： 本文介紹了深度學習和Bongard問題，以及如何用深度學習更好的解決Bongard問題。

原文：http://click.aliyun.com/m/43620/

Bongard問題是蘇聯計算機科學家Mikhail Bongard提出的。從20世紀60年代，他致力於研究模式識別，並且設計了100個這樣的謎題，使之成為評判模式識別能力的一個好基準。而且這些謎題對人和演算法都具有挑戰性。舉個簡單例子：

如圖所示，左邊的6張圖片符合某種規則，而右邊的圖片則符合另外一種規則。要解決這個問題，需要了解模式並找出它們各自的規則（即解決方案）。規則：「左邊：三角形，右邊：四邊形」。

這個例子很簡單，幾秒鐘就能搞定，但也有更難的問題，例如：

你可以試著找找規則，測試下自己的模式識別能力，答案請點擊：22，29，37，54。

這些問題在Douglas Hofstadter於1979年出版的《哥德爾，埃舍爾，巴赫—集異璧之大成》一書中出現後更廣為人知。Hofstadter的博士生Harry Foundalis建立了一個自動化系統來解決他的博士研究項目，這個系統稱為「Phaeco」。這個程序不僅能解決Bongard問題，而且是認知視覺模式識別的一種架構。

深度學習和Bongard問題

2006年創建的Phaeco影響非常大，因為它不僅能演示15個問題的解決方案，而且在許多情況下效率比人類還要快。其實它能夠解決更多的問題，但是需要額外的工作來增強特徵提取器或者探測器。

最近人工智慧和ML的研究取得了顯著的進展。卷積神經網路（CNN）實現在GPU上已經贏得了大量的ImageNet競爭，近年來，CNN演算法和體系結構一直在不斷改進。

所以我想，利用深度學習方法能夠幫助解決Bongard問題嗎？Bongard問題激發了我對深度學習的研究，但是由於它是基於簡化的圖像，而深度學習只有很少的生產圖像的類，導致對原始的Bongard問題的答案並不確定。

現在我決定嘗試解決這個問題。

問題的形成和方法

將深度學習方法應用於Bongard問題至少會有兩個問題。

1、這是一次性學習問題。深度學習效果最好的應用都是基於監督學習的。例如，對數百萬張圖片進行訓練並分類。在這種情況下，神經網路顯示出了與人類相似甚至更好的表現。

但是如果僅僅從幾個例子中學習，在「一次性學習」中，機器學習方法在靈活性和性能方面遠不如人類。BPs每個類只有6個例子，這使得很難用演算法解決。

2、這實際上是一個多模式的學習問題。也就是說輸入的是圖像形式，而輸出的是以自然語言描述的分類規則的形式。雖然已經存在一些解決這些問題的方法，但是我沒找到一個明確的解決方案。所以我決定以更簡單的東西開始，以最終擴展到完整的問題公式為目標。

你可以將Bongard問題的解決方案作為一個分類問題，而不是一個對它規則的口頭描述。在這種情況下，12張圖片可以被分成兩組：10張為「訓練」圖片，2張為「測試」圖片。對於訓練圖片來說，它明確的知道自己屬於哪個類，左邊還是右邊。而測試圖片是隨機交換的，它們屬於哪個類是未知的。要解決這個問題就意味著先看「訓練」圖像，然後再決定「測試」圖像屬於哪個類。

圖三展示了這個公式的分類模式。

現在，通過簡化問題描述，我決定使用轉移學習來實際解決問題。它是單點學習的方法之一，其在視覺類比中顯示了很好的效果。首先，要在類似目標問題的示例中多次訓練模型，然後重用該模型的相關參數。

深度神經網路學習訓練數據的層次化特徵表示。如果要在Bongard圖像上訓練一個卷積神經網路，它將先學習不同的幾何形狀的相應特徵，每個特徵可以被看成一個過濾器。如果存在對應的特徵，就會激活對應分類器。

為了訓練一個特徵提取神經網路（NN），我必須創建一個新的數據集而不能用BP的圖像，因為它們太少了而且相似性太少。

合成數據集

為了對特徵提取網路進行訓練，我生成了一組類似於Bongard問題中的圖像的隨機圖像。每幅圖像都包括一個幾何形狀，並在隨機位置，按隨機的比例，隨機的旋轉。如果形狀是閉合的，還可以隨機的填充成黑色。該組總共24個類，示例如下：

我生成了1M圖像的訓練集，以及10K圖像的測試集。圖像鏈接。

神經網路

為了訓練生成的合成圖像的分類器，我是用了一個相對較小的神經網路。它是基於「Darknet Reference」模型的，並因為輸入圖像相對較小而刪除了一些maxpool圖層。它有9個卷積層，架構描述如下所示；

經過8 epochs的數據訓練後，它收斂到了可以接受的精確度：top 1：0.848000，top 2：0.968000。

神經網路輸出處理

為Bongard問題做一個分類器的第一步是將所有12張圖像通過神經網路的正向傳遞。在卷積神經網路中，每一層都有一組具有共享權重的過濾器，每個過濾器的響應形成一個特徵映射。圖6顯示了所有層的特徵圖。輸入圖像位於左側，由左至右依次按層進行處理。

激活映射中的每個值（每個「像素」）都有可能是一個特性。但是這些特徵的值並不意味著輸入圖像的位置、方向、大小和其他參數不變。基於這一特性僅在10個圖像上訓練出的分類器可能找不到一個抽象的分類規則，但是很快就能適應這種分類。

為了使特徵轉換不變，要將每個特徵映射以如下方式變換成單個二進位特徵：1）標準化跨層特徵圖，2）將閾值設置為0.3（圖7），3）如果特徵映射的值高於閾值，則將生成的特性值設為1，否則為0（圖8）。

通過這種方式每個圖像都能被CNN描述。我只是用了6-10層的特性，在這些圖層上一共有1050個特徵映射，這意味著每個圖像都要用一個長度為1050的二進位向量來描述。

尋找解決問題的分類器

提取到特徵後，就可以把它們用於實際的分類問題了。現在我決定使用最簡單的分類器—一個決策樹。它通常是複雜分類器的一部分，但在這種情況下最簡單的分類器就足夠了。用了這種分類器後，只需要一個特徵值就能判斷出圖像屬於左邊還是右邊了。

要想學習這個規則的演算法其實很簡單，就是一個簡單的直接搜索。它可以通過舉例來演示：

1）對10個訓練圖像進行特徵提取。如上所述，對每個圖像都用一個二元特徵向量來表示，該向量從NN角度描述這個圖像。

2）對於每個特徵，檢查所有10個訓練圖像的值。如果5個左圖像的特徵值和5個右圖想的特徵值不同，那麼它就有可能成為分類器。

3）如果有好幾個分類器，那麼就需要一個驗證標準來選擇出其中一個。我們可以通過比較兩個測試圖像的特徵值：因為圖像屬於不同類，所以特徵值應該是不同的。忽略測試類的精確度，只把它們特徵值是否相等用作驗證標準。

4）把通過驗證的分類器應用於測試圖像，以檢查是否能夠正確分類。如果是正確的，問題就被認為是正確解決了。

5）如果沒有發現規則或者沒有規則通過驗證，那麼問題就被認為是未解決的。

表1展示了搜索6號問題分類特徵的示例(如圖1所示)。所有的特徵中，只顯示在左邊圖像和右邊圖像的特徵值不同時的特徵。只有特性731通過了驗證，且經過測試後發現是正確的。

表2顯示了錯誤分類的示例（問題62）。雖然這兩個特性被選為分類器並通過了驗證，但是對測試圖像還是顯示了錯誤的結果。

如上所示數據可視化以及分類的代碼在github上。

結果分析

把以上演算法應用在232個問題上進行運算，結果如下：解決了47個，正確了41個，所以，解決率為20%，正確率為87%。

為了更好地顯示結果，解決了的問題在表3中用不同顏色所示，綠色-正確，紅色-不正確。

問題集的不同部分具有不同的複雜性，根據結果可知前幾十個問題比較簡單。如圖10所示，準確性依賴於問題數。

表4.顯示了由不同作者設計的問題的準確性。由M.Bongard設計的前100個問題用本文說的演算法最容易解決，其餘的問題則更具挑戰性。

H.Foundalis在他的論文中收集了人們在解決問題1-100時的成績數據。圖11顯示了成績排名前20的正確率。所有的問題都是獨一無二的而且結果也各不相同，這表明，即使是對人類來說，有些問題也是相當具有挑戰性的。

結論

現在一些簡單的深度學習方法對解決Bongard問題非常有用，至少在該問題簡化的分類形式下是這樣的。有趣的是，M.Bongard幾乎在《模式識別》中預測了一些類似的方法。在該實例中，特徵空間要通過預先訓練一個神經網路來對圖像進行分類，使其與問題域中的圖像相似。原始問題的表述包括用自然語言解釋分類規則，這對人們來說是相當容易的，這對於基於手工構造特徵與模式檢測器的「經典」演算法（如「Phaeco」）來講，似乎也是可能的。但是對於神經網路來說，具有透明和可解釋的解決方案是一個已知的弱點，因此原始問題對神經網路可能更具有挑戰性。有幾種方法可以解決這個問題：

創建一個包括圖像和Bongard問題中規則解釋的多模態合成數據集，並將其用於監督學習。但是，產生有意義的謎題本身是很困難的，即使有可能產生，我也不確定遷移學習在該情況下是否仍有效。

CNN可視化方法可以用來解釋解決方案。即通過突出顯示用於分類的像素，並顯示哪些模式是由用於分類的CNN濾波器所表示的。關於是否將視覺解釋和口頭解釋看做是一樣恰當的，值得進一步探討的。

生成式神經網路架構也可以用於該問題，如變分自編碼器(VAE)或生成式的對抗性網路(GAN)。在這種情況下，就是「用例子來解釋」。

「我理解不了我創造不出來的東西。」——理查德·費曼

套用這句名言：「我能創造的，我就能理解」。NN會在Bongard問題中生成新的圖像示例，如果生成的圖像捕獲了分類規則所表達的概念，那麼它就足以顯示神經網路對問題的理解。

總的來說，Bongard問題將仍然是機器學習的一個挑戰性的基準。

本文由阿里云云棲社區組織翻譯。

文章原標題《Solving-Bongard-problems-with-deep-learning》

作者：Sergii Kharagorgiev

譯者：奧特曼，審校：袁虎。

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎

推薦閱讀：