機器學習綜述——機器學習理論基礎與發展脈絡

本文主要參考中科院自動化研究所復雜系統與智能科學實驗室王玨研究員《關于機器學習的討論》，討論機器學習的描述，理論基礎，發展歷史以及研究現狀。

0引言

20世紀90年代初，當時的美國副總統提出了一個重要的計劃——國家信息基本設施計劃(NationalInformation Infrastructure,NII)。這個計劃的技術含義包含了四個方面的內容：

(1)不分時間與地域，可以方便地獲得信息。

(2)不分時間與地域，可以有效地利用信息。

(3)不分時間與地域，可以有效地利用軟硬件資源。

(4)保證信息安全。

本文主要討論解決“信息有效利用”問題，其本質是：如何根據用戶的特定需求從海量數據中建立模型或發現有用的知識。對計算機科學來說，這就是機器學習。

計算機科學，特別是人工智能的研究者一般公認Simon對學習的論述：“如果一個系統能夠通過執行某個過程改進它的性能，這就是學習?！边@是一個相當廣泛的說明, 其要點是“系統”, 它涵蓋了計算系統、控制系統以及人系統等, 對這些不同系統的學習, 顯然屬于不同的科學領域。即使計算系統, 由于目標不同, 也分為了“從有限觀察概括特定問題世界模型的機器學習”、“發現觀測數據中暗含的各種關系的數據分析”,以及“從觀測數據挖掘有用知識的數據挖掘”等不同分支。由于這些分支發展的各種方法的共同目標都是“從大量無序的信息到簡潔有序的知識”,因此,它們都可以理解為Simon 意義下的“過程”,也就都是“學習”。

1 機器學習描述

本文將討論限制在“從有限觀察概括特定問題世界模型的機器學習”與“從有限觀察發現觀測數據中暗含的各種關系的數據分析”的方法上, 并統稱其為機器學習。

我們描述機器學習如下:

令W是給定世界的有限或無限的所有觀測對象的集合, 由于我們觀察能力的限制, 我們只能獲得這個世界的一個有限的子集Q W, 稱為樣本集。機器學習就是根據這個樣本集, 推算這個世界的模型, 使它對這個世界(盡可能地)為真。

這個描述隱含了三個需要解決的問題:

(1) 一致: 假設世界W與樣本集Q有相同的性質。例如,如果學習過程基于統計原理,獨立同分布( i. i. d )就是一類一致條件。

(2) 劃分: 將樣本集放到n維空間,尋找一個定義在這個空間上的決策分界面(等價關系),使得問題決定的不同對象分在不相交的區域。

(3) 泛化: 泛化能力是這個模型對世界為真程度的指標。從有限樣本集合, 計算一個模型,使得這個指標最大(最小)。

這些問題對觀測數據提出了相當嚴厲的條件,首先需要人們根據一致假設采集數據,由此構成機器學習算法需要的樣本集; 其次, 需要尋找一個空間, 表示這個問題; 最后, 模型的泛化指標需要滿足一致假設, 并能夠指導算法設計。這些條件限制了機器學習的應用范圍。

2 機器學習的發展歷史

2.1 機器學習與人工智能

機器學習是人工智能研究的核心內容。它的應用已遍及人工智能的各個分支，如專家系統、自動推理、自然語言理解、模式識別、計算機視覺、智能機器人等領域。

人工智能涉及到諸如意識（consciousness）、自我（self）、心靈（mind）（包括無意識的精神（unconscious_mind））等等問題。人唯一了解的智能是人本身的智能，這是普遍認同的觀點。但是我們對我們自身智能的理解都非常有限，對構成人的智能的必要元素也了解有限，所以就很難定義什么是“人工”制造的“智能”了。因此人工智能的研究往往涉及對人的智能本身的研究。其它關于動物或其它人造系統的智能也普遍被認為是人工智能相關的研究課題。下圖展示了人工智能的發展路線：

機器學習是人工智能研究發展到一定階段的必然產物。從 20 世紀50 年代到 70 年代初，人工智能研究處于“推理期”，人們認為只要給機器賦予邏輯推理能力，機器就能具有智能。這一階段的代表性工作主要有 A. Newell 和 H. Simon 的“邏輯理論家”程序以及此后的“通用問題求解”程序等，這些工作在當時取得了令人振奮的成果。例如，“邏輯理論家”程序在 1952 年證明了著名數學家羅素和懷特海的名著《數學原理》中的 38 條定理，在1963年證明了全部的52 條定理，而且定理 2.85甚至比羅素和懷特海證明得更巧妙。A. Newell和 H. Simon因此獲得了 1975 年圖靈獎。然而，隨著研究向前發展，人們逐漸認識到，僅具有邏輯推理能力是遠遠實現不了人工智能的。E.A. Feigenbaum等人認為，要使機器具有智能，就必須設法使機器擁有知識。在他們的倡導下，20 世紀 70 年代中期開始，人工智能進入了“知識期”。在這一時期，大量專家系統問世，在很多領域做出了巨大貢獻。E.A. Feigenbaum 作為“知識工程”之父在 1994 年獲得了圖靈獎。但是，專家系統面臨“知識工程瓶頸”，簡單地說，就是由人來把知識總結出來再教給計算機是相當困難的。于是，一些學者想到，如果機器自己能夠學習知識該多好！實際上，圖靈在1950年提出圖靈測試的文章中，就已經提到了機器學習的可能，而20世紀50年代其實已經開始有機器學習相關的研究工作，主要集中在基于神經網絡的連接主義學習方面，代表性工作主要有 F. Rosenblatt 的感知機、B. Widrow 的 Adaline 等。在 20 世紀 6、70 年代，多種學習技術得到了初步發展，例如以決策理論為基礎的統計學習技術以及強化學習技術等，代表性工作主要有 A.L. Samuel 的跳棋程序以及 N.J. Nilson 的“學習機器”等，20 多年后紅極一時的統計學習理論的一些重要結果也是在這個時期取得的。在這一時期，基于邏輯或圖結構表示的符號學習技術也開始出現，代表性工作有 P. Winston的“結構學習系統”、R.S. Michalski等人的“基于邏輯的歸納學習系統”、E.B. Hunt 等人的“概念學習系統”等。1980 年夏天，在美國卡內基梅隆大學舉行了第一屆機器學習研討會；同年，《策略分析與信息系統》連出三期機器學習專輯；1983年，Tioga出版社出版了R.S. Michalski、J.G. Carbonell和T.M. Mitchell主編的《機器學習：一種人工智能途徑》，書中匯集了 20 位學者撰寫的 16 篇文章，對當時的機器學習研究工作進行了總結，產生了很大反響；1986 年，《Machine Learning》創刊；1989 年，《Artificial Intelligence》出版了機器學習專輯，刊發了一些當時比較活躍的研究工作，其內容后來出現在J.G. Carbonell主編、MIT出版社 1990 年出版的《機器學習：風范與方法》一書中?？偟膩砜?，20 世紀 80 年代是機器學習成為一個獨立的學科領域并開始快速發展、各種機器學習技術百花齊放的時期。R.S. Michalski等人中把機器學習研究劃分成“從例子中學習”、“在問題求解和規劃中學習”、“通過觀察和發現學習”、“從指令中學習”等范疇；而 E.A. Feigenbaum在著名的《人工智能手冊》中，則把機器學習技術劃分為四大類，即“機械學習”、“示教學習”、“類比學習”、“歸納學習”。

2.2 機器學習的理論基礎

機器學習的科學基礎之一是神經科學, 然而, 對機器學習進展產生重要影響的是以下三個發現, 分別是:

(1) James關于神經元是相互連接的發現。

(2) McCulloch 與Pitts 關于神經元工作方式是“興奮”和“抑制”的發現。

(3) Hebb 的學習律(神經元相互連接強度的變化)。

其中, McCulloch 與Pitts 的發現對近代信息科學產生了巨大的影響。對機器學習, 這項成果給出了近代機器學習的基本模型, 加上指導改變連接神經元之間權值的Hebb學習律,成為目前大多數流行的機器學習算法的基礎。

1954年, Barlow 與Hebb 在研究視覺感知學習時,分別提出了不同假設: Barlow 倡導單細胞學說, 假設從初級階段而來的輸入集中到具有專一性響應特點的單細胞, 并使用這個神經單細胞來表象視覺客體。這個考慮暗示, 神經細胞可能具有較復雜的結構; 而Hebb主張視覺客體是由相互關聯的神經細胞集合體來表象, 并稱其為ensemble。在神經科學的研究中, 盡管這兩個假設均有生物學證據的支持, 但是, 這個爭論至今沒有生物學的定論。這個生物學的現實, 為我們計算機科學家留下了想象的空間, 由于在機器學習中一直存在著兩種相互補充的不同研究路線, 這兩個假設對機器學習研究有重要的啟示作用。

在機器學習劃分的研究中, 基于這兩個假設, 可以清晰地將機器學習發展歷程總結為: 以感知機、BP與SVM 等為一類；以樣條理論、k-近鄰、Madalin e、符號機器學習、集群機器學習與流形機器學習等為另一類。

在McCulloch 與Pitts 模型的基礎上, 1957 年, Rosenblatt 首先提出了感知機算法,這是第一個具有重要學術意義的機器學習算法。這個思想發展的坎坷歷程, 正是機器學習研究發展歷史的真實寫照。感知機算法主要貢獻是: 首先, 借用最簡單的McCulloch與Pitts模型作為神經細胞模型; 然后,根據Hebb集群的考慮, 將多個這樣的神經細胞模型根據特定規則集群起來,形成神經網絡, 并將其轉變為下述機器學習問題: 計算一個超平面, 將在空間上不同類別標號的點劃分到不同區域。在優化理論的基礎上, Rosenblatt 說明, 如果一個樣本集合是線性可分, 則這個算法一定可以以任何精度收斂。由此導致的問題是, 對線性不可分問題如何處理。

1969年,Minsky 與Paper出版了對機器學習研究具有深遠影響的著作Perceptron(《感知機》)。目前, 人們一般的認識是, 由于這本著作中提出了XOR 問題, 從而扼殺了感知機的研究方向。然而, 在這本著作中對機器學習研究提出的基本思想, 至今還是正確的, 其思想的核心是兩條:

(1) 算法能力: 只能解決線性問題的算法是不夠的, 需要能夠解決非線性問題的算法。

(2) 計算復雜性: 只能解決玩具世界問題的算法是沒有意義的, 需要能夠解決實際世界問題的算法。

在1986 年, Rumelhart 等人的BP 算法解決了XOR 問題, 沉寂近二十年的感知機研究方向重新獲得認可,人們自此重新開始關注這個研究方向, 這是Rumelhart等人的重要貢獻。

在20 世紀60 年代的另一個重要研究成果來自Widrow。1960 年,Widrow 推出了Madaline 模型, 在算法上,對線性不可分問題, 其本質是放棄劃分樣本集的決策分界面連續且光滑的條件, 代之分段的平面。從近代的觀點來看, 這項研究與感知機的神經科學假設的主要區別是: 它是確認Barlow 假設中神經細胞具有較復雜結構的思想,由此,將線性模型(例如, 感知機)考慮為神經細胞模型( 而不是簡單的McCulloch與Pitts模型) ,然后, 再基于Hebb 神經元集合體假設, 將這些局部模型集群為對問題世界的表征, 由此解決線性不可分問題。但是, 這項研究遠不如感知機著名, 其原因是: 其一, 盡管Madaline可以解決線性不可分問題, 但是, 其解答可能是平凡的; 其二,Widrow 沒有給出其理論基礎, 事實上,其理論基礎遠比感知機復雜, 直到1990 年, Schapire根據Valiant 的“概率近似正確(PAC)”理論證明了“弱可學習定理”之后, 才真正引起人們的重視。

進一步比較機器學習中兩個不同路線的神經科學啟示是有趣的: 對機器學習來說, 它們最顯著的差別是對神經細胞模型的假設, 例如, 感知機是以最簡單的McCulloch與Pitts 模型作為神經細胞模型, 而Madaline 是以問題世界的局部模型作為神經細胞模型,兩種方法都需要根據Hebb 思想集群。因此, 對機器學習研究, 兩個神經科學的啟示是互補的。但是, 兩者還有區別: 前者強調模型的整體性, 這與Barlow“表征客體的單一細胞論”一致, 因此, 我們稱其為Barlow 路線; 而后者則強調對世界的表征需要多個神經細胞集群, 這與Hebb“表征客體的多細胞論”一致, 我們稱其為Hebb 路線。鑒于整體模型與局部模型之間在計算上有本質差別, 盡管根據Barlow 與Hebb 假設區分機器學習的方法。

在這一節的最后, 將1989 年Carbonell對機器學習以后十年的展望與十年后Diet terich 的展望作一個對比, 可能是有趣的, 我們希望以此說明機器學習研究由于面臨問題的改變所發生的變遷(表1) 。