4 集群機器學(xué)習

4.1 弱可學(xué)習定理

1990 年, Schapire 證明了一個有趣的定理: 如果一個概念是弱可學(xué)習的, 充要條件是它是強可學(xué)習的。這個定理的證明是構(gòu)造性的, 證明過程暗示了弱分類器的思想。所謂弱分類器就是比隨機猜想稍好的分類器, 這意味著, 如果我們可以設(shè)計這樣一組弱分類器, 并將它們集群起來, 就可以成為一個強分類器, 這就是集群機器學(xué)習。由于弱分類器包含“比隨機猜想稍好”的條件, 從而, 避免了對Madaline 平凡解的批評。另外, 由于Schapire 定理的證明基于PAC的弱可學(xué)習理論, 因此, 這種方法又具有泛化理論的支持。這樣, 自Widrow 提出Madaline近30 年之后, 人們終于獲得了基于Hebb 路線下的機器學(xué)習算法設(shè)計的理論基礎(chǔ)。這個學(xué)習理念立即獲得人們的廣泛關(guān)注, 其原因不言自明,弱分類器的設(shè)計總比強分類器設(shè)計容易, 特別是對線性不可分問題更是如此。由此,Madaline 與感知機一樣, 成為機器學(xué)習最重要的經(jīng)典。

4.2 經(jīng)典算法

Boosting 是一種用來提高學(xué)習算法準確度的方法, 這種方法通過構(gòu)造一個預(yù)測函數(shù)系列, 然后以一定的方式將它們組合成一個預(yù)測函數(shù), 達到把一弱學(xué)習算法提升為強學(xué)習算法的目的。1989 年Schapire 提出了第一個可證明的多項式時間Boosting 算法, 對這個問題作出了肯定的回答。一年后,Freund 設(shè)計了一個高效得多的通過重取樣或過濾運作的Boosting- by-Majority 算法。這個算法盡管在某種意義上是優(yōu)化的, 但卻有一些實踐上的缺陷。1995 年Freund 和Schapire介紹了通過調(diào)整權(quán)重而運作的AdaBoost 算法解決了早期Boosting算法很多實踐上的困難。

AdaBoost 是Boosting 家族中的基礎(chǔ)算法。Boosting家族中的大部分擴展( 算法) 都由它得來,對AdaBoost 的分析結(jié)論也適用于其它的Boosting。下面簡要地介紹一下它的思想。

AdaBoost 算法的主要思想是給定一弱學(xué)習算法和訓(xùn)練集( x1, y1) , , , ( xn, yn ) 。這里xi 為一向量, yi 對于分類問題為一類別標志, 對于回歸問題為一數(shù)值。初始化時對每一個訓(xùn)練例賦相等的權(quán)重1/ n , 然后用該學(xué)習算法對訓(xùn)練集訓(xùn)練t 輪, 每次訓(xùn)練后, 對訓(xùn)練失敗的訓(xùn)練例賦以較大的權(quán)重, 也就是讓學(xué)習算法在后續(xù)的學(xué)習中集中對比較難的訓(xùn)練例進行學(xué)習, 從而得到一個預(yù)測函數(shù)序列h1, , , ht ,其中hj 也有一定的權(quán)重, 預(yù)測效果好的預(yù)測函數(shù)權(quán)重較大, 反之較小。最終的預(yù)測函數(shù)H 對分類問題采用有權(quán)重的投票方式, 對回歸問題采用加權(quán)平均的方法對新示例進行判別。

Boosting 算法是一種基于其他機器學(xué)習算法之上的用來提高算法精度和性能的方法。當用于回歸分析時, 不需要構(gòu)造一個擬合精度高、預(yù)測能力好的回歸算法, 只要一個效果只比隨機猜測略好的粗糙算法即可, 稱之為基礎(chǔ)算法。通過不斷地調(diào)用這個基礎(chǔ)算法就可以獲得一個擬合和預(yù)測誤差都相當好的組合回歸模型。Boosting 算法可以應(yīng)用于任何的基礎(chǔ)回歸算法, 無論是線性回歸、神經(jīng)網(wǎng)絡(luò)、還是SVM 方法, 都可以有效地提高精度。因此, Boosting可以被視為一種通用的增強基礎(chǔ)算法性能的回歸分析算法。

Bagging(Bootstrap Aggregating) 又被稱為自舉聚合, 是Breiman 提出的與Boosting 相似的技術(shù)。[ 11]Bagging 技術(shù)的主要思想是給定一弱學(xué)習算法和一訓(xùn)練集( x 1, y1), , ( xn , yn ) 。讓該學(xué)習算法訓(xùn)練多輪, 每輪的訓(xùn)練集由從初始的訓(xùn)練集中隨機取出的n 個訓(xùn)練例組成, 初始訓(xùn)練例在某輪訓(xùn)練集中可以出現(xiàn)多次或根本不出現(xiàn)。訓(xùn)練之后可得到一個預(yù)測函數(shù)序列: h1, , , ht , 最終的預(yù)測函數(shù)H 對分類問題采用投票方式, 對回歸問題采用簡單平均。

Bagging 與Boosting 的區(qū)別在于Bagging 的訓(xùn)練集的選擇是隨機的, 各輪訓(xùn)練集之間相互獨立, 而Boosting的訓(xùn)練集的選擇不是獨立的, 各輪訓(xùn)練集的選擇與前面各輪的學(xué)習結(jié)果有關(guān); Bagging 的各個預(yù)測函數(shù)沒有權(quán)重, 可以并行生成, 而Boosting 是有權(quán)重的, 只能依次順序生成; Boosting 往往從一些弱的學(xué)習器開始, 組合形成一個集成學(xué)習器, 從而給出一個好的學(xué)習結(jié)果, 而Bagging學(xué)習效果的好壞往往取決于集成學(xué)習器中每個學(xué)習器的相關(guān)性和各個學(xué)習器的學(xué)習效果。對于神經(jīng)網(wǎng)絡(luò)這類極為耗時的學(xué)習方法, Bagging 可通過并行訓(xùn)練節(jié)省大量時間開銷。

5 符號機器學(xué)習

自1969 年Minsky 出版Perceptron(《感知機》)一書以后, 感知機的研究方向被終止,到1986 年Rumelhart 等發(fā)表BP 算法, 近20 年間, 機器學(xué)習研究者在做什么事情呢? 這段時間正是基于符號處理的人工智能的黃金時期, 由于專家系統(tǒng)研究的推動, 符號機器學(xué)習得到發(fā)展, 事實上, 這類研究方法除了建立在符號的基礎(chǔ)上之外, 從學(xué)習的機理來看, 如果將學(xué)習結(jié)果考慮為規(guī)則, 每個規(guī)則將是一個分類器, 盡管這些分類器中有些不一定滿足弱分類器的條件, 但是, 它應(yīng)該是Hebb 路線的延續(xù)。

符號機器學(xué)習的最大優(yōu)點是歸納的解答與歸納的過程是可解釋的, 換句話說, 數(shù)據(jù)集合中的每個觀測(樣本或?qū)ο?對用戶都是透明的, 它在解答以及計算過程中所扮演的角色, 用戶都是可以顯現(xiàn)了解的。然而, 它的缺陷同樣突出, 就是泛化能力。由于學(xué)習結(jié)果是符號表述, 因此, 只可能取“真”與“假”, 這樣大大減低了對具有一定噪音數(shù)據(jù)的分析能力, 需要其他技術(shù)來補充: 其一, 觀測世界的數(shù)據(jù)到符號域的映射, 其二, 不確定推理機制。但是, 這兩種方法與符號機器學(xué)習方法本身并沒有必然的關(guān)系。

近幾年, 由于數(shù)據(jù)挖掘的提出, 符號機器學(xué)習原理有了新的用途, 這就是符號數(shù)據(jù)分析, 在數(shù)據(jù)挖掘中稱為數(shù)據(jù)描述, 以便與數(shù)據(jù)預(yù)測類型的任務(wù)相區(qū)別(從任務(wù)來說, 這類任務(wù)與機器學(xué)習是一致的)。

與機器學(xué)習的目標不同, 數(shù)據(jù)分析不是以所有用戶具有相同需求為假設(shè), 相反, 強調(diào)不同用戶具有不同的需求。另外, 數(shù)據(jù)分析強調(diào), 分析結(jié)果是為用戶提供可閱讀的參考文本, 決策將依賴人的洞察。如何根據(jù)用戶的特定需求將觀測數(shù)據(jù)集合變換為簡潔的、可為用戶理解的表示成為關(guān)鍵。這是符號機器學(xué)習的另一個可以考慮的應(yīng)用領(lǐng)域。由于符號機器學(xué)習在泛化能力上的欠缺, 這也是它在與基于統(tǒng)計的機器學(xué)習方法競爭中避免遭到淘汰的出路。

6 增強機器學(xué)習方法

增強機器學(xué)習( reinfo rcementlearning )的本質(zhì)是對變化的環(huán)境的適應(yīng)。應(yīng)該說,這是一種“古老”的機器學(xué)習思想.在1948年, Wiener的著作“控制論”中,就討論了這個問題,而在以后的控制理論的研究中,這發(fā)展成為重要的研究課題—— 自適應(yīng)控制。由于控制理論研究這個問題的焦點在于控制品質(zhì),且其使用的數(shù)學(xué)工具是微分方程,因此,對非線性問題,使用計算機進行數(shù)值求解存在著本質(zhì)性的困難。這是這類機器學(xué)習長期未得到計算機科學(xué)家注意的原因。

直到20世紀70年代, Holland在討論進化計算時,需要考慮控制物種群體的染色體數(shù)量,以便淘汰對變化環(huán)境不適應(yīng)的個體,為此,提出使用桶隊算法解決這個問題。桶隊算法在Holland提出的分類器系統(tǒng)中扮演著對變換環(huán)境適應(yīng)的角色。

以后,在20世紀90年代初, Sutton提出將這類機器學(xué)習建立在Markov 過程上,并稱其為增強機器學(xué)習方法。這個方法是根據(jù)環(huán)境變化對系統(tǒng)的刺激,并作為系統(tǒng)輸入,然后,利用基于統(tǒng)計的方法優(yōu)化轉(zhuǎn)移概率,并使系統(tǒng)適應(yīng)新的環(huán)境。

一般地說,增強機器學(xué)習應(yīng)該屬于無教師學(xué)習,但是,如果考慮環(huán)境就是教師,這類機器學(xué)習也可以認為是一類特殊有教師的機器學(xué)習,與一般有教師機器學(xué)習的區(qū)別在于: 教師是環(huán)境,且是變化的環(huán)境。這意味著,不像傳統(tǒng)意義下的有教師學(xué)習,教師教授的知識不是事先給定的,而是采用更靈活方法,在問題求解的過程中獲得的。

7 總結(jié)

本文從機器學(xué)習的起源，發(fā)展依據(jù)，歷史上的重要事件角度討論了機器學(xué)習發(fā)展脈絡(luò)。通過“對神經(jīng)細胞模型假設(shè)的差別”將機器學(xué)習領(lǐng)域劃分為兩大支系——強調(diào)模型的整體性，基于Barlow“表征客體的單一細胞論”的Barlow路線；強調(diào)對世界的表征需要多個神經(jīng)細胞集群，基于Hebb“表征客體的多細胞論”的Hebb路線。這一劃分可以清晰地將機器學(xué)習發(fā)展歷程總結(jié)為：以感知機、BP與SVM等為一類的Barlow路線；以樣條理論、k-緊鄰、Madaline、符號機器學(xué)習，集群機器學(xué)習與流行機器學(xué)習等為一類的Hebb路線。

其中，又重點關(guān)注了目前發(fā)展良好的統(tǒng)計機器學(xué)習與集群學(xué)習。討論了SVM與神經(jīng)網(wǎng)絡(luò)的關(guān)系與優(yōu)缺點，以及將弱學(xué)習算法提升為強學(xué)習算法的Boosting算法。

本文提倡研究者需要重視這樣一個問題：我們探討機器學(xué)習在理念、理論、與技術(shù)上發(fā)展的各種方法所遵循的假設(shè)，是否能夠適應(yīng)當前任務(wù)的需要？如果問題是否定的,那么，我們是修補這些已被普遍認可的理念、理論與方法(打補丁)，以適應(yīng)當前的需要，還是從根本上清理原有假設(shè)，提出新的假設(shè)，從而發(fā)展新的理念、理論和方法？這是一個需要仔細分析已有理論與方法，并權(quán)衡各種利弊才能決定的事情。綜上所述，討論機器學(xué)習發(fā)展脈絡(luò)，以從這個脈絡(luò)發(fā)現(xiàn)有趣的經(jīng)驗和教訓(xùn)，對回答這個問題是重要的，這必須考慮機器學(xué)習發(fā)展的科學(xué)依據(jù)，歷史上的重要事件，以及理論研究中的重要結(jié)論。這就是我們本文的討論集中在動機和理論的原因。