機(jī)器學(xué)習(xí)綜述——機(jī)器學(xué)習(xí)理論基礎(chǔ)與發(fā)展脈絡(luò)

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

0引言

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

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

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

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

(4)保證信息安全。

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

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

1 機(jī)器學(xué)習(xí)描述

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

我們描述機(jī)器學(xué)習(xí)如下:

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

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

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

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

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

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

2 機(jī)器學(xué)習(xí)的發(fā)展歷史

2.1 機(jī)器學(xué)習(xí)與人工智能

機(jī)器學(xué)習(xí)是人工智能研究的核心內(nèi)容。它的應(yīng)用已遍及人工智能的各個(gè)分支，如專家系統(tǒng)、自動(dòng)推理、自然語言理解、模式識別、計(jì)算機(jī)視覺、智能機(jī)器人等領(lǐng)域。

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

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

2.2 機(jī)器學(xué)習(xí)的理論基礎(chǔ)

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

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

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

(3) Hebb 的學(xué)習(xí)律(神經(jīng)元相互連接強(qiáng)度的變化)。

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

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

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

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

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

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

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

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

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

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

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