機器學習簡史
最近學習的重點不在機器學習上面,但是現代的學科就是這么奇妙,錯綜復雜,玩著玩著,你發現又回到了人工智能這一塊。所以干脆好好整理下當下令很多 人如癡如醉,但又不容易入門的機器學習。一來給大多數還沒有入門的人一點宏觀概念,二來讓我自己以后找解決辦法的時候更有頭緒。故此文不是給想快速上手的 工程師的菜單,更像一篇娓娓道來的武俠小說,看看人工智能世界的先驅們是如何開宗創派的。
一、從人工智能說起
機器學習屬于人工智能的一塊,先簡要回顧一下。關于什么是“智能”,就問題多多了。這涉及到其它諸如意識(consciousness)、自我 (self)、心靈(mind)(包括無意識的精神(unconscious_mind))等等問題。人唯一了解的智能是人本身的智能,這是普遍認同的觀 點。但是我們對我們自身智能的理解都非常有限,對構成人的智能的必要元素也了解有限,所以就很難定義什么是“人工”制造的“智能”了。因此人工智能的研究 往往涉及對人的智能本身的研究。其它關于動物或其它人造系統的智能也普遍被認為是人工智能相關的研究課題。下圖展示了人工智能的發展路線:
在20世紀40年代和50年代,來自不同領域(數學,心理學,工程學,經濟學和政治學)的一批科學家開始探討制造人工大腦的可能性。1956年,人工智能被確立為一門學科。
IBM 702:第一代AI研究者使用的電腦.
最初的人工智能研究是30年代末到50年代初的一系列科學進展交匯的產物。神經學研究發現大腦是由神經元組成的電子網絡,其激勵電平只存在“有”和 “無”兩種狀態,不存在中間狀態。維納的控制論描述了電子網絡的控制和穩定性。克勞德·香農提出的信息論則描述了數字信號(即高低電平代表的二進制信 號)。圖靈的計算理論證明數字信號足以描述任何形式的計算。這些密切相關的想法暗示了構建電子大腦的可能性。這一階段的工作包括一些機器人的研發,例如 W。Grey Walter的“烏龜(turtles)”,還有“約翰霍普金斯獸”(Johns Hopkins Beast)。這些機器并未使用計算機,數字電路和符號推理;控制它們的是純粹的模擬電路。
Walter Pitts和Warren McCulloch分析了理想化的人工神經元網絡,并且指出了它們進行簡單邏輯運算的機制。他們是最早描述所謂“神經網絡”的學者。馬文·閔斯基是他們的 學生,當時是一名24歲的研究生。1951年他與Dean Edmonds一道建造了第一臺神經網絡機,稱為SNARC。在接下來的五十年中,閔斯基是AI領域最重要的領導者和創新者之一。
1951 年,Christopher Strachey使用曼徹斯特大學的Ferranti Mark 1機器寫出了一個西洋跳棋(checkers)程序;Dietrich Prinz則寫出了一個國際象棋程序。[31]Arthur Samuel在五十年代中期和六十年代初開發的西洋棋程序的棋力已經可以挑戰具有相當水平的業余愛好者。游戲AI一直被認為是評價AI進展的一種標準。
1950 年,圖靈發表了一篇劃時代的論文,文中預言了創造出具有真正智能的機器的可能性。由于注意到“智能”這一概念難以確切定義,他提出了著名的圖靈測試:如果 一臺機器能夠與人類展開對話(通過電傳設備)而不能被辨別出其機器身份,那么稱這臺機器具有智能。這一簡化使得圖靈能夠令人信服地說明“思考的機器”是可 能的。論文中還回答了對這一假說的各種常見質疑。圖靈測試是人工智能哲學方面第一個嚴肅的提案。
50年代中期,隨著數字計算機的興起,一些科學家直覺地感到可以進行數字操作的機器也應當可以進行符號操作,而符號操作可能是人類思維的本質。這是創造智能機器的一條新路。
1955年,Newell和(后來榮獲諾貝爾獎的)Simon在J. C. Shaw的協助下開發了“邏輯理論家(Logic Theorist)”。這個程序能夠證明《數學原理》中前52個定理中的38個,其中某些證明比原著更加新穎和精巧。Simon認為他們已經“解決了神秘 的心/身問題,解釋了物質構成的系統如何獲得心靈的性質。”(這一斷言的哲學立場后來被John Searle稱為“強人工智能”,即機器可以像人一樣具有思想。)
1956年達特矛斯會議的組織者是Marvin Minsky,John McCarthy和另兩位資深科學家Claude Shannon以及Nathan Rochester,后者來自IBM。會議提出的斷言之一是“學習或者智能的任何其他特性的每一個方面都應能被精確地加以描述,使得機器可以對其進行模 擬。”與會者包括Ray Solomonoff,Oliver Selfridge,Trenchard More,Arthur Samuel,Newell和Simon,他們中的每一位都將在AI研究的第一個十年中作出重要貢獻。會上紐厄爾和西蒙討論了“邏輯理論家”,而 McCarthy則說服與會者接受“人工智能”一詞作為本領域的名稱。1956年達特矛斯會議上AI的名稱和任務得以確定,同時出現了最初的成就和最早的 一批研究者,因此這一事件被廣泛承認為AI誕生的標志。
現如今AI世界已經枝繁葉茂,被認為最廣泛的綜合學科,也是未來最有希望的學科的之一。
涉及學科
- 哲學和認知科學
- 數學
- 心理學
- 計算機科學
- 控制論
- 決定論
- 不確定性原理
研究范疇
- 自然語言處理(NLP; Natural Language Processing)
- 知識表現(Knowledge Representation)
- 智能搜索(Intelligent Search)
- 推理
- 規劃(Planning)
- 機器學習(Machine Learning)
- 增強式學習(Reinforcement Learning)
- 知識獲取
- 感知問題
- 模式識別
- 邏輯程序設計
- 軟計算(Soft Computing)
- 不精確和不確定的管理
- 人工生命(Artificial Life)
- 人工神經網絡(Artificial Neural Network)
- 復雜系統
- 遺傳算法
- 資料挖掘(Data Mining)
- 模糊控制
上面列舉了一下維基上面的解釋,可以說現代工程上的很多問題,都可以從上述研究范疇找到解決方案。可以想見,在未來人工智能發展會經歷以下幾個階段:
應用階段(1980年至今):在這一階段里,人工智能技術在軍事、工業和醫學等領域中的應用顯示出了它具有明顯的經濟效益潛力。適合人們投資的這一新天地浮出了水面。
融合階段(2010—2020年):
- 在某些城市,立法機關將主要采用人工智能專家系統來制定新的法律。
- 人們可以用語言來操縱和控制智能化計算機、互聯網、收音機、電視機和移動電話,遠程醫療和遠程保健等遠程服務變得更為完善。
- 智能化計算機和互聯網在教育中扮演了重要角色,遠程教育十分普及。
- 隨著信息技術、生物技術和納米技術的發展,人工智能科學逐漸完善。
- 許多植入了芯片的人體組成了人體通信網絡(以后甚至可以不用植入任何芯片)。比如,將微型超級計算機植入人腦,人們就可通過植入的芯片直接進行通信。
- 量子計算機和DNA計算機會有更大發展,能夠提高智能化水平的新型材料會不斷問世。
- 抗病毒程序可以防止各種非自然因素引發災難。(H7N9大家小心 )
- 隨著人工智能的加速發展,新制定的法律不僅可以用來更好地保護人類健康,而且能大幅度提高全社會的文明水準。比如,法律可以保護人們免受電磁煙霧 的侵害,可以規范家用機器人的使用,可以更加有效地保護數據,可以禁止計算機合成技術在一些文化和藝術方面的應用(比如禁止合成電視名人),可以禁止編寫 具有自我保護意識的計算機程序。
自我發展階段(2020—2030年):
- 智能化計算機和互聯網既能自我修復,也能自行進行科學研究,還能自己生產產品。
- 一些新型材料的出現,促使智能化向更高層次發展。
- 用可植入芯片實現人類、計算機和鯨目動物之間的直接通信,在以后的發展中甚至不用植入芯片也可實現此項功能。
- 制定“機器人法”等新的法律來約束機器人的行為,使人們不受機器人的侵害。
- 高水準的智能化技術可以使火星表面環境適合人類居住和發展。
升華階段(2030—2040年):
信息化的世界進一步發展成全息模式的世界。(參見Ingress——現實虛擬化游戲)
人工智能系統可從環境中采集全息信息,身處某地的人們可以更容易地了解和知曉其他地方的情況。
人們對一些目前無法解釋的自然現象會有更清楚的認識和更完善的解釋,并將這些全新的知識應用在醫療、保健和安全等領域。
人工智能可以模仿人類的智能,因此會出現有關法律來規范這些行為。
二、機器學習的由來
從人工智能的角度我們不難發現,當今機器學習世界的很多方法都是從其中延伸出來的。但同時,它也自己獨特的一面。機器學習是 近20多年興起的一門多領域交叉學科,涉及概率論、統計學、逼近論、凸分析、算法復雜度理論等多門學科。機器學習理論主要是設計和分析一些讓計算機可以自 動“學習”的算法。機器學習算法是一類從數據中自動分析獲得規律,并利用規律對未知數據進行預測的算法。因為學習算法中涉及了大量的統計學理論,機器學習 與統計推斷學聯系尤為密切,也被稱為統計學習理論。算法設計方面,機器學習理論關注可以實現的,行之有效的學習算法。很多推論問題屬于無程序可循難度,所 以部分的機器學習研究是開發容易處理的近似算法。
機器學習可以分成下面幾種類別:
- 監督學習從給定的訓練數據集中學習出一個函數,當新的數據到來時,可以根據這個函數預測結果。監督學習的訓練集要求是包括輸入和輸出,也可以說是特征和目標。訓練集中的目標是由人標注的。常見的監督學習算法包括回歸分析和統計分類。
- 無監督學習與監督學習相比,訓練集沒有人為標注的結果。常見的無監督學習算法有聚類。
- 半監督學習介于監督學習與無監督學習之間。
- 增強學習通過觀察來學習做成如何的動作。每個動作都會對環境有所影響,學習對象根據觀察到的周圍環境的反饋來做出判斷。
機 器學習是人工智能研究發展到一定階段的必然產物。從 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在著
名的《人工智能手冊》中,則把機器學習技術劃分為四大類,即“機械學習”、“示教學習”、“類比學習”、“歸納學習”。
1.機械學習也稱為“死記硬背式學習”,就是把外界輸入的信息全部記下來,在需要的時候原封不動地取出來使用,這實際上沒有進行真正的學習;
2.示教學習和類比學習實際上類似于R.S. Michalski等人所說的“從指令中學習”和“通過觀察和發現學習”;
3.歸納學習類似于“從例子中學習”,即從訓練例中歸納出學習結果。20 世紀80 年代以來,被研究得最多、應用最廣的是“從例子中學習”(也就是廣義的歸納學習),它涵蓋了監督學習(例如分類、回歸)、非監督學習(例如聚類)等眾多內容。
下 面我們對這方面主流技術的演進做一個簡單的回顧。在 20 世紀 90 年代中期之前,“從例子中學習”的一大主流技術是歸納邏輯程序設計(Inductive Logic Programming),這實際上是機器學習和邏輯程序設計的交叉。它使用 1 階邏輯來進行知識表示,通過修改和擴充邏輯表達式(例如Prolog表達式)來完成對數據的歸納。這一技術占據主流地位與整個人工智能領域的發展歷程是分 不開的。如前所述,人工智能在 20 世紀 50 年代到 80 年代經歷了“推理期”和“知識期”,在“推理期”中 人們基于邏輯知識表示、通過演繹技術獲得了很多成果,而在知識期中人們基于邏輯知識表示、通過領域知識獲取來實現專家系統,因此,邏輯知識表示很自然地受 到青睞,而歸納邏輯程序設計技術也自然成為機器學習的一大主流。歸納邏輯程序設計技術的一大優點是它具有很強的知識表示能力,可以較容易地表示出復雜數據 和復雜的數據關系。尤為重要的是,領域知識通常可以方便地寫成邏輯表達式,因此,歸納邏輯程序設計技術不僅可以方便地利用領域知識指導學習,還可以通過學 習對領域知識進行精化和增強,甚至可以從數據中學習出領域知識。事實上,機器學習在 20 世紀80 年代正是被視為“解決知識工程瓶頸問題的關鍵”而走到人工智能主舞臺的聚光燈下的,歸納邏輯程序設計的一些良好特性對此無疑居功至偉。S.H. Muggleton主編的書對 90年代中期之前歸納邏輯程序設計方面的研究工作做了總結。然而,歸納邏輯程序設計技術也有其局限,最嚴重的問題是由于其表示能力很強,學習過程所面臨的 假設空間太大,對規模稍大的問題就很難進行有效的學習,只能解決一些“玩具問題”。因此,在 90 年代中期后,歸納程序設計技術方面的研究相對陷入了低谷。
20 世紀 90 年代中期之前,“從例子中學習”的另一大主流技術是基于神經網絡的連接主義學習。連接主義學習技術在 20 世紀 50 年代曾經歷了一個大發展時期,但因為早期的很多人工智能研究者對符號表示有特別的偏愛,例如H. Simon曾說人工智能就是研究“對智能行為的符號化建模”, 因此當時連接主義的研究并沒有被納入主流人工智能的范疇。同時,連接主義學習自身也遇到了極大的問題,M. Minsky和S. Papert在1969 年指出,(當時的)神經網絡只能用于線性分類,對哪怕“異或”這么簡單的問題都做不了。于是,連接主義學習在此后近 15 年的時間內陷入了停滯期。直到1983 年,J.J. Hopfield利用神經網絡求解TSP問題獲得了成功,才使得連接主義重新受到人們的關注。1986 年,D.E. Rumelhart和J.L. McClelland主編了著名的《并行分布處理—認知微結構的探索》一書,對PDP小組的研究工作進行了總結,轟動 一時。特別是D.E. Rumelhart、G.E. Hinton和R.J. Williams重新發明了著名的BP算法,產生了非常大的影響。該算法可以說是最成功的神經網絡學習算法,在當時迅速成為最流行的算法,并在很多應用中 都取得了極大的成功。與歸納邏輯程序設計技術相比,連接主義學習技術基于“屬性-值”的表示形式(也就是用一個特征向量來表示一個事物;這實際上是命題邏 輯表示形式),學習過程所面臨的假設空間遠小于歸納邏輯程序設計所面臨的空間,而且由于有BP這樣有效的學習算法,使得它可以解決很多實際問題。事實上, 即使在今天,BP仍然是在實際工程應用中被用得最多、最成功的算法之一。然而,連接主義學習技術也有其局限,一個常被人詬病的問題是其“試錯性”。簡單地 說,在此類技術中有大量的經驗參數需要設置,例如神經網絡的隱層結點數、學習率等,夸張一點說,參數設置上差之毫厘,學習結果可能謬以千里。在實際工程應 用中,人們可以通過調試來確定較好的參數設置,但對機器學習研究者來說,對此顯然是難以滿意的。
20 世紀 90 年代中期,統計學習粉墨登場并迅速獨占鰲頭。其實早在 20世紀 6、70年代就已經有統計學習方面的研究工作,統計學習理論[9]在那個時期也已經打下了基礎,例如V.N. Vapnik早在1963 年就提出了“支持向量”的概念,他和A.J. Chervonenkis在 1968 年提出了VC維,在 1974年提出了結構風險最小化原則等,但直到 90 年代中期統計學習才開始成為機器學習的主流技術。這一方面是由于有效的支持向量機算法在 90 年代才由B.E. Boser、I. Guyon和V.N. Vapnik提出,而其優越的性能也是到 90 年代中期才在T. Joachims等人對文本分類的研究中顯現出來;另一方面,正是在連接主義學習技術的局限性凸顯出來之后,人們才把目光轉向了統計學習。事實上統計學習 與連接主義學習有著密切的聯系,例如RBF神經網絡其實就是一種很常用的支持向量機。在支持向量機被普遍接受后,支持向量機中用到的核(kernel)技 巧被人們用到了機器學習的幾乎每一個角落中,“核方法”也逐漸成為機器學習的一種基本技巧。但其實這并不是一種新技術,例如Mercer定理是在 1909年發表的,核技巧也早已被很多人使用過,即使只考慮機器學習領域,至少T. Poggio在 1975 年就使用過多項式核。如果仔細審視統計學習理論,就可以發現其中的絕大多數想法在以往機器學習的研究中都出現過,例如結構風險最小化原則實際上就是對以往 機器學習研究中經常用到的最小描述長度原則的另一個說法。但是,統計學習理論把這些有用的片段整合在同一個理論框架之下,從而為人們研制出泛化能力f有理 論保證的算法奠定了基礎,與連接主義學習的“試錯法”相比,這是一個極大的進步。然而,統計學習也有其局限,例如,雖然理論上來說,通過把原始空間利用核 技巧轉化到一個新的特征空間,再困難的問題也可以容易地得到解決,但如何選擇合適的核映射,卻仍然有濃重的經驗色彩。另一方面,統計學習技術與連接主義學 習技術一樣是基于“屬性-值”表示形式,難以有效地表示出復雜數據和復雜的數據關系,不僅難以利用領域知識,而且學習結果還具有“黑箱性”。此外,傳統的 統計學習技術往往因為要確保統計性質或簡化問題而做出一些假設,但很多假設在真實世界其實是難以成立的。如何克服上述缺陷,正是很多學者正在關注的問題。
科 學和真理必然是建立在爭論和證明之上。機器學習世界也分了多個門派。所謂的machine learning community,現在至少包含了兩個有著完全不同的文化、完全不同的價值觀的群體,稱為machine learning “communities”也許更合適一些。
第一個community,是把機器學習看作人工智能分支的一個群體,這群人的主體是計算機科學家。
現 在的“機器學習研究者”可能很少有人讀過1983年出的“Machine Learning: An Artificial Intelligence Approach”這本書。這本書的出版標志著機器學習成為人工智能中一個獨立的領域。它其實是一部集早期機器學習研究之大成的文集,收羅了若干先賢(例 如Herbert Simon,那位把諾貝爾獎、圖靈獎以及各種各樣和他相關的獎幾乎拿遍了的科學天才)的大作,主編是Ryszard S. Michalski(此君已去世多年了,他可算是機器學習的奠基人之一)、Jaime G. Carbonell(此君曾是Springer的LNAI的總編)、Tom Mitchell(此君是CMU機器學習系首任系主任、著名教材的作者,機器學習界沒人不知道他吧)。Machine Learning雜志的創刊,正是這群人努力的結果。這本書值得一讀。雖然技術手段早就日新月異了,但有一些深刻的思想現在并沒有過時。各個學科領域總有 不少東西,換了新裝之后又粉墨登場,現在熱火朝天的transfer learning,其實就是learning by analogy的升級版。
人 工智能的研究從以“推理”為重點到以“知識”為重點,再到以“學習”為重點,是有一條自然、清晰的脈絡。人工智能出身的機器學習研究者,絕大部分 是把機器學習作為實現人工智能的一個途徑,正如1983年的書名那樣。他們關注的是人工智能中的問題,希望以機器學習為手段,但具體采用什么樣的學習手 段,是基于統計的、代數的、還是邏輯的、幾何的,他們并不care。
這群人可能對統計學習目前dominating的地位未必滿意。靠統計 學習是不可能解決人工智能中大部分問題的,如果統計學習壓制了對其他手段的研 究,可能不是好事。這群人往往也不care在文章里show自己的數學水平,甚至可能是以簡化表達自己的思想為榮。人工智能問題不是數學問題,甚至未必是 依靠數學能夠解決的問題。人工智能中許多事情的難處,往往在于我們不知道困難的本質在哪里,不知道“問題”在哪里。一旦“問題”清楚了,解決起來可能并不 困難。
第二個community,是把機器學習看作“應用統計學”的一個群體,這群人的主體是統計學家。
和純數學相比,統計學不太“干凈”,不少數學家甚至拒絕承認統計學是數學。但如果和人工智能相比,統計學就太干凈了,統計學研究的問題是清楚的,不象人工智能那樣,連問題到底在哪里都不知道。在相當長時間里,統計學家和機器學習一直保持著距離。
慢 慢地,不少統計學家逐漸意識到,統計學本來就該面向應用,而機器學習天生就是一個很好的切入點。因為機器學習雖然用到各種各樣的數學,但要分析大 量數據中蘊涵的規律,統計學是必不可少的。統計學出身的機器學習研究者,絕大部分是把機器學習當作應用統計學。他們關注的是如何把統計學中的理論和方法變 成可以在計算機上有效實現的算法,至于這樣的算法對人工智能中的什么問題有用,他們并不care。
這群人可能對人工智能毫無興趣,在他們眼中,機器學習就是統計學習,是統計學比較偏向應用的一個分支,充其量是統計學與計算機科學的交叉。這群人對統計學習之外的學習手段往往是排斥的,這很自然,基于代數的、邏輯的、幾何的學習,很難納入統計學的范疇。
兩 個群體的文化和價值觀完全不同。第一個群體認為好的工作,第二個群體可能覺得沒有技術含量,但第一個群體可能恰恰認為,簡單的才好,正因為很好地 抓住了問題本質,所以問題變得容易解決。第二個群體欣賞的工作,第一個群體可能覺得是故弄玄虛,看不出他想解決什么人工智能問題,根本就不是在搞人工智 能、搞計算機,但別人本來也沒說自己是在“搞人工智能”、“搞計算機”,本來就不是在為人工智能做研究。
三、SVM與Deep Learning之爭
現如今在機器學習世界最火爆的可以算是統計學習,而在統計學習領域最熱門非deep learning和SVM(support vector machine)莫屬了。
神經網絡(Neural Network)與支持向量機(Support Vector Machines,SVM)是統計學習的代表方法。
可以認為神經網絡與支持向量機都源自于感知機(Perceptron)。感知機是由Rosenblatt發明的線性分類模型(1958年)。感知機對線性分類有效,但現實中的分類問題通常是非線性的。
神 經網絡與支持向量機(包含核方法)都是非線性分類模型。1986年,Rummelhart與McClelland發明了神經網絡的學習算法Back Propagation。后來,Vapnik等人于1992年提出了支持向量機。神經網絡是多層(通常是三層)的非線性模型,支持向量機利用核技巧把非線 性問題轉換成線性問題。
神經網絡與支持向量機一直處于“競爭”關系。
Scholkopf是Vapnik的大弟子,支持向量機 與核方法研究的領軍人物。據Scholkopf說,Vapnik當初發明支持向量機就是想’干掉’神經網絡(He wanted to kill Neural Network)。支持向量機確實很有效,一段時間支持向量機一派占了上風。
近年來,神經網絡一派的大師Hinton又提出 了神經網絡的Deep Learning算法(2006年),使神經網絡的能力大大提高,可與支持向量機一比。Deep Learning假設神經網絡是多層的,首先用Restricted Boltzmann Machine(非監督學習)學習網絡的結構,然后再通過Back Propagation(監督學習)學習網絡的權值。關于Deep Learning的命名,Hinton曾開玩笑地說: I want to call SVM shallow learning. (注:shallow 有膚淺的意思)。其實Deep Learning本身的意思是深層學習,因為它假設神經網絡有多層。
(1)Deep Learning
deep learning本身算是machine learning的一個分支,簡單可以理解為neural network的發展。大約二三十年前,neural network曾經是ML領域特別火熱的一個方向,但是后來確慢慢淡出了,原因包括以下幾個方面:
1,比較容易過訓練,參數比較難tune;
2,訓練速度比較慢,在層次比較少(小于等于3)的情況下效果并不比其它方法更優;
deep learning與傳統的神經網絡之間有相同的地方也有很多不同。
二 者的相同在于deep learning采用了神經網絡相似的分層結構,系統由包括輸入層、隱層(多層)、輸出層組成的多層網絡,只有相鄰層節點之間有連接,同一層以及跨層節點 之間相互無連接,每一層可以看作是一個logistic regression模型;這種分層結構,是比較接近人類大腦的結構的。
而為了克 服神經網絡訓練中的問題,DL采用了與神經網絡很不同的訓練機制。傳統神經網絡中,采用的是back propagation的方式進行,簡單來講就是采用迭代的算法來訓練整個網絡,隨機設定初值,計算當前網絡的輸出,然后根據當前輸出和label之間的 差去改變前面各層的參數,直到收斂(整體是一個梯度下降法)。而deep learning整體上是一個layer-wise的訓練機制。這樣做的原因是因為,如果采用back propagation的機制,對于一個deep network(7層以上),殘差傳播到最前面的層已經變得太小,出現所謂的gradient diffusion。
2, 基于第一步得到的各層參數進一步fine-tune整個多層模型的參數,這一步是一個有監督訓練過程;第一步類似神經網絡的隨機初始化初值過程,由于DL 的第一步不是隨機初始化,而是通過學習輸入數據的結構得到的,因而這個初值更接近全局最優,從而能夠取得更好的效果;所以deep learning效果好很大程度上歸功于第一步的feature learning過程。
總之,deep learning能夠得到更好地表示數據的feature,同時由于模型的層次、參數很多,capacity足夠,因此,模型有能力表示大規模數據,所以 對于圖像、語音這種特征不明顯(需要手工設計且很多沒有直觀物理含義)的問題,能夠在大規模訓練數據上取得更好的效果。此外,從模式識別特征和分類器的角 度,deep learning框架將feature和分類器結合到一個框架中,用數據去學習feature,在使用中減少了手工設計feature的巨大工作量(這是 目前工業界工程師付出努力最多的方面),因此,不僅僅效果可以更好,而且,使用起來也有很多方便之處,因此,是十分值得關注的一套框架,每個做ML的人都 應該關注了解一下。
關于deep learning的更多知識和總結,大家可以參考前面的文章。機器學習前沿熱點–Deep Learning
⑴線性核函數K(x,y)=x·y;
⑵多項式核函數K(x,y)=[(x·y)+1]d;
⑶徑向基函數K(x,y)=exp(-|x-y|^2/d^2)
⑷二層神經網絡核函數K(x,y)=tanh(a(x·y)+b).
SVM有如下主要幾個特點:
(1)非線性映射是SVM方法的理論基礎,SVM利用內積核函數代替向高維空間的非線性映射;
(2)對特征空間劃分的最優超平面是SVM的目標,最大化分類邊際的思想是SVM方法的核心;
(3)支持向量是SVM的訓練結果,在SVM分類決策中起決定作用的是支持向量。
(4)SVM 是一種有堅實理論基礎的新穎的小樣本學習方法。它基本上不涉及概率測度及大數定律等,因此不同于現有的統計方法。從本質上看,它避開了從歸納到演繹的傳統過程,實現了高效的從訓練樣本到預報樣本的“轉導推理”,大大簡化了通常的分類和回歸等問題。
(5)SVM 的最終決策函數只由少數的支持向量所確定,計算的復雜性取決于支持向量的數目,而不是樣本空間的維數,這在某種意義上避免了“維數災難”。維基百科上面有關維數災難的介紹請見此。
(6)少數支持向量決定了最終結果,這不但可以幫助我們抓住關鍵樣本、“剔除”大量冗余樣本,而且注定了該方法不但算法簡單,而且具有較好的“魯棒”性。這種“魯棒”性主要體現在:
①增、刪非支持向量樣本對模型沒有影響;
②支持向量樣本集具有一定的魯棒性;
③有些成功的應用中,SVM 方法對核的選取不敏感
兩個不足:
(1) SVM算法對大規模訓練樣本難以實施
由 于SVM是借助二次規劃來求解支持向量,而求解二次規劃將涉及m階矩陣的計算(m為樣本的個數),當m數目很大時該矩陣的存儲和計算將耗費大量的機器內存 和運算時間。針對以上問題的主要改進有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、張學工的 CSVM以及O.L.Mangasarian等的SOR算法
(2) 用SVM解決多分類問題存在困難
經典的支持向量機算法只 給出了二類分類的算法,而在數據挖掘的實際應用中,一般要解決多類的分類問題。可以通過多個二類支持向量機的組合來解決。主要有一對多組合模式、一對一組 合模式和SVM決策樹;再就是通過構造多個分類器的組合來解決。主要原理是克服SVM固有的缺點,結合其他算法的優勢,解決多類問題的分類精度。如:與粗 集理論結合,形成一種優勢互補的多類問題的組合分類器。
ps:其實整個機器學習的算法與數學上的運籌學,凸規劃等知識密不可分,如果想真的想徹底掌握算法中的數學原理,建議有時間的朋友可以看看這本書Convex Optimization – Boyd and Vandenberghe,如果已經看過的朋友也歡迎將你的感受寫下來,發表到十一城,大家一起學習!
參考鏈接:
http://zh.wikipedia.org/wiki/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD%E7%9A%84%E5%8E%86%E5%8F%B2
http://jssfxzx.blog.163.com/blog/static/6071057200692634829141/
http://zh.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0
http://hi.baidu.com/giqguarzqdbadpq/item/8d41e5160121a3ff65eabf8d
http://blog.sina.com.cn/s/blog_7ad48fee0100vz2f.html
http://baike.baidu.com/view/960509.htm
文獻:
機器學習與數據挖掘-周志華-南京大學計算機軟件新技術國家重點實驗室
本文轉載自:十一城elevencitys.com