在世界上第一臺計算機 ENIAC 剛剛製造出來不久，科學家們就開始關心如何利用計算機實現人工智慧的問題。然而，關於智慧和學習的定義方式以及人工智慧的實現方式在當時卻是眾說紛紜。理論學者們嘗試從更加抽象的角度去理解“機器學習”甚至“學習”的概念。在上一篇節氣推送（立春 | 機器學習中的學習理論）中，小編提到了 Leslie Valiant 在上述研究中做出的奠基性貢獻。
Leslie Gabriel Valiant
人們一般認為關於機器學習數學理論的開山之作是1984年 Leslie Gabriel Valiant 的文章“A Theory of the Learnable”。Valiant 因為機器學習理論和平行計算理論的卓越成就並授予了2010年的圖靈獎，而在這篇工作中他正式初次提出了為機器學習理論奠基的 PAC（Probably Approximately Correct）學習理論。這篇文章中，我們將圍繞 Valiant 的這篇經典文獻展開具體介紹。
文章的第一部分是關於學習（learning）概念的抽象理解。在1984年，可計算性的理論已經被圖靈等計算機科學家透過數學進行了嚴謹的定義，而在 Valiant 認為可學習性應當是與可計算性同等重要的概念，而關鍵的問題就是尋找一個合適的模型：這個模型需要既能夠解釋人類等動物的學習經驗，又能夠幫助製造可以學習的機器。
文章中指出，學習是除去顯式程式設計外其他完成任務的方式。人類所掌握的技能中一部分是可以被顯式表述出來的（例如依照菜譜做菜），而另一部分技能則沒有辦法被顯式的描述出來（如何判斷一張照片裡有沒有貓咪出現）。我們關注的則是這些不能被顯式程式設計的完成任務方式。因此，文章的目標就是設計一種這樣的學習機器，使得它被證明能夠在多項式時間內學習到一個不平凡的、由概念構成的類。事實上，這裡提出的“概念”“類”和“多項式時間”等共同形成了現在廣為採用的標準的 PAC 學習理論的雛形。
作者認為一個學習機器應該包含兩部分：學習協議（learning protocol）和演繹過程（deduction procedure）。其中前者是從世界獲取資訊的方式，這在現在的理解即為收集資料的方式；而後者指的是如何從資訊中獲取概念，這也就是我們現在理解的學習演算法。
在第三部分裡，作者開始討論可學習性（learnability）的問題，即我們在知道什麼是學習之後，又該如何判斷一個問題是不是能夠被學習的呢？由此，作者給出了可學習性的定義，而這個定義最終被完善為 PAC learnable 的定義。通俗地講，可學習就是存在演算法能夠在很短的時間（多項式時間）內以很高的機率出現很少的錯誤。這個概念從直覺上並不難理解。沒有人願意學一輩子習，所以當然要限定時間；由於獲取知識的機率我們並不能保證在學習後成為一個不會犯錯的完人，所以只能希望自己在學習後以很高的機率犯很少的錯誤（考試經常考高分）。當然，學習的效果（學習成功以及犯錯的機率）肯定要是同學習時間正相關的，畢竟我們都知道：“一分耕耘，一分收穫”嘛。
上述概念看著或許並不困難，我們也許會說“這我也能想到”，但其實卻是非常深刻且有開創性的。Valiant 給出了自己對於學習和可學習性的獨到理解，而從那時起機器學習演算法的數學討論基本都是在後者的框架中進行。
在文章之後的幾個部分，作者則給出了具體的類以及學習機器的定義，舉了三種例子並證明了它們都是可學習的。實際上，當時的計算機科學家對於機器學習、人工智慧的可實現性還並沒有太多的信心，因為無論從理論或者實踐上都存在很多消極的證據（有人稱那個年代為人工智慧的寒冬），從理論上一些看上去並不十分複雜的類已經被證明是不可被有效學習的，從實踐上也沒有人知道諸如現在大家習以為常的人臉識別技術到底有沒有希望實現。Valiant 的這些小嚐試也被他認為是對可學習類範圍的一種探索，從這篇文章中我們也可以看到一門學科和技術還在萌芽時從探索中成長的過程。
Valiant 最終被評授予圖靈獎有這篇文章的很大功勞。但他對學習、智慧的探索卻從沒停止，也不只侷限於計算機學科之內，他對於神經科學以及生物的進化也有著濃厚的興趣，就像“A Theory of the Learnable”中一樣，他認為三者在一定程度上具有相似的正規化。2013年他出版的書籍《Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World》中，Valiant 講述了他最新的研究和思考。
偉大的理論和實踐常常會被人忽視它的偉大，因為人們初次瞭解時往往就是在教科書中自然而然地接觸這些概念。例如我們在學習圖靈機的概念時，往往會預設它就是最自然的計算模型和定義方法，而忽視了它廣泛而又深邃的意義。因此，結合其歷史背景，從科學史或學科史的視角出發能夠加深我們對知識本身的理解，也會讓我們在面對未知問題時有更多的想法和勇氣——閱讀經典文獻的意義可能就在於此。
參考文獻：
[1] Valiant L G. A theory of the learnable [J]. Communications of the ACM, 1984, 27(11): 1134-1142.
[2] Mohri M, Rostamizadeh A, Talwalkar A. Foundations of machine learning [M]. MIT press, 2018.
[3] Shalev-Shwartz S, Ben-David S. Understanding machine learning: From theory to algorithms [M]. Cambridge university press, 2014.
[4] Valiant L. Probably approximately correct: nature's algorithms for learning and prospering in a complex world [M]. Basic Books (AZ), 2013.
文字 | 唐靜吾
文中圖片除署名外源自網路
