4 集群機(jī)器學(xué)習(xí)

4.1 弱可學(xué)習(xí)定理

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

4.2 經(jīng)典算法

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

AdaBoost 是Boosting 家族中的基礎(chǔ)算法。Boosting家族中的大部分?jǐn)U展( 算法) 都由它得來(lái),對(duì)AdaBoost 的分析結(jié)論也適用于其它的Boosting。下面簡(jiǎn)要地介紹一下它的思想。

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

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

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

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

5 符號(hào)機(jī)器學(xué)習(xí)

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

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

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

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

6 增強(qiáng)機(jī)器學(xué)習(xí)方法

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

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

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

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

7 總結(jié)

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

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

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