用深度学习解决Bongard问题
摘要:?本文介紹了深度學習和Bongard問題,以及如何用深度學習更好的解決Bongard問題。
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張為“測試”圖片。對于訓練圖片來說,它明確的知道自己屬于哪個類,左邊還是右邊。而測試圖片是隨機交換的,它們屬于哪個類是未知的。要解決這個問題就意味著先看“訓練”圖像,然后再決定“測試”圖像屬于哪個類。
圖三展示了這個公式的分類模式。
?
圖3
現在,通過簡化問題描述,我決定使用轉移學習來實際解決問題。它是單點學習的方法之一,其在視覺類比中顯示了很好的效果。首先,要在類似目標問題的示例中多次訓練模型,然后重用該模型的相關參數。
深度神經網絡學習訓練數據的層次化特征表示。如果要在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)。
?
圖7 歸一化和閾值化后的特征映射(原頁面可以水平滾動)
?
圖8 基于特征映射的二值制特征(原網頁該圖片可以水平滾動)
通過這種方式每個圖像都能被CNN描述。我只是用了6-10層的特性,在這些圖層上一共有1050個特征映射,這意味著每個圖像都要用一個長度為1050的二進制向量來描述。
尋找解決問題的分類器
提取到特征后,就可以把它們用于實際的分類問題了?,F在我決定使用最簡單的分類器—一個決策樹。它通常是復雜分類器的一部分,但在這種情況下最簡單的分類器就足夠了。用了這種分類器后,只需要一個特征值就能判斷出圖像屬于左邊還是右邊了。
要想學習這個規則的算法其實很簡單,就是一個簡單的直接搜索。它可以通過舉例來演示:
1)對10個訓練圖像進行特征提取。如上所述,對每個圖像都用一個二元特征向量來表示,該向量從NN角度描述這個圖像。
?
圖9基于CNN特性的二進制描述符
2)對于每個特征,檢查所有10個訓練圖像的值。如果5個左圖像的特征值和5個右圖想的特征值不同,那么它就有可能成為分類器。
3)如果有好幾個分類器,那么就需要一個驗證標準來選擇出其中一個。我們可以通過比較兩個測試圖像的特征值:因為圖像屬于不同類,所以特征值應該是不同的。忽略測試類的精確度,只把它們特征值是否相等用作驗證標準。
4)把通過驗證的分類器應用于測試圖像,以檢查是否能夠正確分類。如果是正確的,問題就被認為是正確解決了。
5)如果沒有發現規則或者沒有規則通過驗證,那么問題就被認為是未解決的。
表1展示了搜索6號問題分類特征的示例(如圖1所示)。所有的特征中,只顯示在左邊圖像和右邊圖像的特征值不同時的特征。只有特性731通過了驗證,且經過測試后發現是正確的。
?
表1:問題6的特性分析
表2顯示了錯誤分類的示例(問題62)。雖然這兩個特性被選為分類器并通過了驗證,但是對測試圖像還是顯示了錯誤的結果。
?
表2:問題62的錯誤分析
如上所示數據可視化以及分類的代碼在github上。
結果分析
把以上算法應用在232個問題上進行運算,結果如下:解決了47個,正確了41個,所以,解決率為20%,正確率為87%。
為了更好地顯示結果,解決了的問題在表3中用不同顏色所示,綠色-正確,紅色-不正確。
?
表3:已解決問題
問題集的不同部分具有不同的復雜性,根據結果可知前幾十個問題比較簡單。如圖10所示,準確性依賴于問題數。
?
圖10 解決問題的正確率,按問題序數排序
表4.顯示了由不同作者設計的問題的準確性。由M.Bongard設計的前100個問題用本文說的算法最容易解決,其余的問題則更具挑戰性。
?
表4:不同作者設計的問題的平均精度
H.Foundalis在他的論文中收集了人們在解決問題1-100時的成績數據。圖11顯示了成績排名前20的正確率。所有的問題都是獨一無二的而且結果也各不相同,這表明,即使是對人類來說,有些問題也是相當具有挑戰性的。
?
圖11 人類求解Bongard問題時的精度
結論
現在一些簡單的深度學習方法對解決Bongard問題非常有用,至少在該問題簡化的分類形式下是這樣的。有趣的是,M.Bongard幾乎在《模式識別》中預測了一些類似的方法。在該實例中,特征空間要通過預先訓練一個神經網絡來對圖像進行分類,使其與問題域中的圖像相似。原始問題的表述包括用自然語言解釋分類規則,這對人們來說是相當容易的,這對于基于手工構造特征與模式檢測器的“經典”算法(如“Phaeco”)來講,似乎也是可能的。但是對于神經網絡來說,具有透明和可解釋的解決方案是一個已知的弱點,因此原始問題對神經網絡可能更具有挑戰性。有幾種方法可以解決這個問題:
創建一個包括圖像和Bongard問題中規則解釋的多模態合成數據集,并將其用于監督學習。但是,產生有意義的謎題本身是很困難的,即使有可能產生,我也不確定遷移學習在該情況下是否仍有效。
CNN可視化方法可以用來解釋解決方案。即通過突出顯示用于分類的像素,并顯示哪些模式是由用于分類的CNN濾波器所表示的。關于是否將視覺解釋和口頭解釋看做是一樣恰當的,值得進一步探討的。
生成式神經網絡架構也可以用于該問題,如變分自編碼器(VAE)或生成式的對抗性網絡(GAN)。在這種情況下,就是“用例子來解釋”。
“我理解不了我創造不出來的東西。”——理查德·費曼
套用這句名言:“我能創造的,我就能理解”。NN會在Bongard問題中生成新的圖像示例,如果生成的圖像捕獲了分類規則所表達的概念,那么它就足以顯示神經網絡對問題的理解。
總的來說,Bongard問題將仍然是機器學習的一個挑戰性的基準。
?
文章原標題《Solving-Bongard-problems-with-deep-learning》
作者:Sergii Kharagorgiev
譯者:奧特曼,審校:袁虎。
原文鏈接
干貨好文,請關注掃描以下二維碼:
總結
以上是生活随笔為你收集整理的用深度学习解决Bongard问题的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 众安每秒3.2万张保单的背后,阿里云输出
- 下一篇: Tensorflow快餐教程(1) -