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

0引言

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

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

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

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

(4)保證信息安全。

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

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

1 機器學習描述

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

我們描述機器學習如下:

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

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

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

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

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

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

2 機器學習的發(fā)展歷史

2.1 機器學習與人工智能

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

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

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

2.2 機器學習的理論基礎

機器學習的科學基礎之一是神經(jīng)科學, 然而, 對機器學習進展產(chǎn)生重要影響的是以下三個發(fā)現(xiàn), 分別是:

(1) James關于神經(jīng)元是相互連接的發(fā)現(xiàn)。

(2) McCulloch 與Pitts 關于神經(jīng)元工作方式是“興奮”和“抑制”的發(fā)現(xiàn)。

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

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

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

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

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

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

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

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

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

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

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

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