1、1,機(jī)器學(xué)習(xí)研究進(jìn)展,第九屆中國(guó)機(jī)器學(xué)習(xí)會(huì)議 上海2004年10月,王 玨中國(guó)科學(xué)院自動(dòng)化研究所jue.wang@mail.ia.ac.cn,周志華南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系z(mì)houzh@nju.edu.cn,連接機(jī)器學(xué)習(xí)符號(hào)機(jī)器學(xué)習(xí)遺傳機(jī)器學(xué)習(xí)分析機(jī)器學(xué)習(xí),機(jī)器學(xué)習(xí)研究的變遷,Carbonell(1989)展望,Dietterich(1997)展望,,,,,,？,,統(tǒng)計(jì)機(jī)器學(xué)習(xí)集成機(jī)器學(xué)習(xí)符號(hào)機(jī)器學(xué)習(xí)增強(qiáng)機(jī)

2、器學(xué)習(xí),,,,流形機(jī)器學(xué)習(xí)半監(jiān)督機(jī)器學(xué)習(xí)多實(shí)例機(jī)器學(xué)習(xí)Ranking機(jī)器學(xué)習(xí)數(shù)據(jù)流機(jī)器學(xué)習(xí),應(yīng)用驅(qū)動(dòng)的機(jī)器學(xué)習(xí)研究,,,目前，以“主義”爭(zhēng)霸的時(shí)代已經(jīng)過(guò)去，不同方法解決不同問題。,,,3,對(duì)統(tǒng)計(jì)機(jī)器學(xué)習(xí)的說(shuō)明,Dietterich將感知機(jī)類的連接機(jī)器學(xué)習(xí)分離出來(lái)，并根據(jù)劃分機(jī)理，將其分為兩種類型：統(tǒng)計(jì)機(jī)器學(xué)習(xí)與集成機(jī)器學(xué)習(xí)。這意味著，感知機(jī)類機(jī)器學(xué)習(xí)是重點(diǎn)強(qiáng)調(diào)：表示：非線性問題的線性表示泛化：以泛化能力為基礎(chǔ)的算法設(shè)計(jì),,

3、4,對(duì)增強(qiáng)機(jī)器學(xué)習(xí)的說(shuō)明,“適應(yīng)性”是控制理論中最重要的概念之一，以往在計(jì)算機(jī)科學(xué)中考慮較少1975年，Holland首先將這個(gè)概念引入計(jì)算機(jī)科學(xué)。1990年左右，MIT的Sutton等青年計(jì)算機(jī)科學(xué)家，結(jié)合動(dòng)態(tài)規(guī)劃等問題，統(tǒng)稱其為增強(qiáng)機(jī)器學(xué)習(xí)這樣，遺傳學(xué)習(xí)成為實(shí)現(xiàn)增強(qiáng)機(jī)器學(xué)習(xí)的一種方法,,5,對(duì)符號(hào)機(jī)器學(xué)習(xí)的說(shuō)明,盡管經(jīng)過(guò)十年，符號(hào)機(jī)器學(xué)習(xí)被保留，然而，其目標(biāo)和內(nèi)涵已發(fā)生很大的變化改變泛化目標(biāo)為符號(hào)描述(數(shù)據(jù)挖掘)。這意味著，符

4、號(hào)機(jī)器學(xué)習(xí)已不是與統(tǒng)計(jì)機(jī)器學(xué)習(xí)競(jìng)爭(zhēng)的研究，而是一個(gè)研究目標(biāo)與其不同的研究范式,,6,分析機(jī)器學(xué)習(xí)被放棄,分析機(jī)器學(xué)習(xí)所包含的類比、解釋等問題對(duì)背景知識(shí)有更高的要求，這從表示到學(xué)習(xí)均需要考慮新的理論基礎(chǔ)，在這些理論未出現(xiàn)之前，其淡出機(jī)器學(xué)習(xí)研究的視野是自然的,,7,近幾年的發(fā)展動(dòng)向,由于真實(shí)世界的問題十分困難，現(xiàn)有的理論、方法，甚至理念已不能滿足需要，由此，大量近代數(shù)學(xué)的研究結(jié)果被引入計(jì)算機(jī)科學(xué)，由此，形成新的機(jī)器學(xué)習(xí)范式,8,特點(diǎn),從C

5、arbonell到Dietterich的特點(diǎn)是：在算法設(shè)計(jì)理論上，基礎(chǔ)代替隨意的算法設(shè)計(jì)，具體地說(shuō)，更為強(qiáng)調(diào)機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)應(yīng)用驅(qū)動(dòng)代替理論驅(qū)動(dòng)(認(rèn)知科學(xué)與算法的Open問題)。具體地說(shuō)，從AI中以“學(xué)習(xí)”機(jī)制驅(qū)動(dòng)(智能)”的研究方式，改變?yōu)楦鶕?jù)面臨的實(shí)際問題發(fā)展新的理論與方法,,9,統(tǒng)計(jì)機(jī)器學(xué)習(xí)的要點(diǎn),目前，統(tǒng)計(jì)機(jī)器學(xué)習(xí)的研究主要集中在兩個(gè)要點(diǎn)上：,表示問題,泛化問題,非線性問題在線形空間的表示,對(duì)給定樣本集合， 通過(guò)算法建

6、立模型，對(duì)問題世界為真的程度,,,10,線性表示,計(jì)算：非線性算法一般是NP完全的。認(rèn)識(shí)世界：只有在某個(gè)空間中可以描述為線性的世界，人們才說(shuō)，這個(gè)世界已被認(rèn)識(shí)(將問題變換為另一個(gè)問題)數(shù)學(xué)方法：尋找一個(gè)映射，將非線性問題映射到線性空間，以便其可以線性表述,11,例子---XOR問題,xy0001,例子：XOR問題：,映射：(x,y)?(x,xy,y),線形表示：,12,在機(jī)器學(xué)習(xí)中的方法,尋找具有一般意義的線性空間(方法

7、)目前，機(jī)器學(xué)習(xí)主要采用兩種方法：整體線性，Hilbert空間(核映射)類似分段線性，Madaline或弱分類方法,13,Hilbert空間,Hilbert空間是Von Neumman為量子力學(xué)數(shù)學(xué)基礎(chǔ)提出的一類具有一般意義的線性內(nèi)積空間在機(jī)器學(xué)習(xí)中借助Hilbert空間構(gòu)成特征空間,14,線性不可分機(jī)器學(xué)習(xí)問題,將線性不可分問題變?yōu)榫€性可分問題的關(guān)鍵是尋找一個(gè)映射，將樣本集映射到特征空間，使其在特征空間線性可分這樣，我們只需

8、以感知機(jī)為基礎(chǔ)，研究統(tǒng)計(jì)機(jī)器學(xué)習(xí)問題。,15,困難—特征空間基的選擇,選擇特征空間的基特征空間的基可以采用多項(xiàng)式基或三角函數(shù)基尋找一般的方法描述特征空間存在根本性困難(維數(shù)災(zāi))與神經(jīng)網(wǎng)絡(luò)相比，核函數(shù)的選擇可以借助領(lǐng)域知識(shí)，這是一個(gè)優(yōu)點(diǎn),16,理論描述,是否可以不顯現(xiàn)地描述特征空間，將特征空間上描述變?yōu)闃颖究臻g上的描述？如果不考慮維數(shù)問題，在泛函分析理論上，這是可行的這就是核函數(shù)方法,,泛化能力描述,Duda(1973),Vap

9、nik(1971),18,“泛化誤差界”研究的演變,PAC界(Valiant[1984])VC維界(Blumer[1989])最大邊緣(Shawe-Taylor[1998]),19,最大邊緣(Shawe-Taylor[1998]),M>0，邊緣不能等于零。這意味著，樣本集合必須是可劃分的。邊緣最大，誤差界最小，泛化能力最強(qiáng)。泛化能力可以使用樣本集合的邊緣刻畫。,這個(gè)不等式依賴于邊緣M。貢獻(xiàn)：給出了有幾何直觀的界描述，從而為

10、算法設(shè)計(jì)奠定基礎(chǔ)。,20,研究趨勢(shì),算法的理論研究基本已經(jīng)完成，根據(jù)特定需求的研究可能是必要的目前主要集中在下述兩個(gè)問題上：泛化不等式需要樣本集滿足獨(dú)立同分布，這個(gè)條件太嚴(yán)厲，可以放寬這個(gè)條件？如何根據(jù)領(lǐng)域需求選擇核函數(shù)，有基本原則嗎？,,21,集成機(jī)器學(xué)習(xí)的來(lái)源,神經(jīng)科學(xué)：Hebb神經(jīng)細(xì)胞工作方式數(shù)學(xué)方法：非線性問題的分段化(類似)計(jì)算技術(shù)：Widrow的Madaline模型統(tǒng)計(jì)理論：PAC的弱可學(xué)習(xí)理論,22,Ensem

11、ble(集成),1954年，Hebb使用這個(gè)單詞來(lái)說(shuō)明視覺神經(jīng)細(xì)胞的信息加工方式假設(shè)信息加工是由神經(jīng)集合體來(lái)完成,23,Madaline模型,Widrow的Madaline模型在數(shù)學(xué)上，其本質(zhì)是放棄感知機(jī)對(duì)樣本空間劃分的超平面需要滿足連續(xù)且光滑的條件，代之分段的超平面,24,Schapire的理論,定理：如果一個(gè)概念是弱可學(xué)習(xí)的，充要條件是它是強(qiáng)可學(xué)習(xí)的,這個(gè)定理證明是構(gòu)造性的，派生了弱分類器的概念，即，比隨機(jī)猜想稍好的分類器,這個(gè)

12、定理說(shuō)明： 多個(gè)弱分類器可以集成為一個(gè)強(qiáng)分類器,1990年，Schapire證明了一個(gè)關(guān)鍵定理，由此，奠定了集成機(jī)器學(xué)習(xí)的理論基礎(chǔ),25,問題,集成機(jī)器學(xué)習(xí)的研究還存在著大量未解決的問題，關(guān)于泛化能力的估計(jì)(不等式)還存在問題目前，這類機(jī)器學(xué)習(xí)的理論研究主要是觀察與積累，大量的現(xiàn)象還不能解釋,,符號(hào)機(jī)器學(xué)習(xí),最早的符號(hào)機(jī)器學(xué)習(xí)：Solomonoff的文法歸納方法(1959),,符號(hào)機(jī)器學(xué)習(xí)的主流：Samuel限制機(jī)器學(xué)習(xí)在結(jié)

13、構(gòu)化符號(hào)數(shù)據(jù)集合上(1967)，約簡(jiǎn)算法。,Gold證明，這是不可能的實(shí)現(xiàn)的(1967)。,值得注意的動(dòng)向：文法歸納方法引起人們的重視。,,Hebb路線：每個(gè)規(guī)則可以理解為一個(gè)弱分類器。,27,符號(hào)機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ),符號(hào)機(jī)器學(xué)習(xí)不同于統(tǒng)計(jì)機(jī)器學(xué)習(xí)，劃分樣本集合的等價(jià)關(guān)系是學(xué)習(xí)所得，符號(hào)機(jī)器學(xué)習(xí)是事先定義等價(jià)關(guān)系，學(xué)習(xí)只是在這個(gè)等價(jià)關(guān)系下約簡(jiǎn)樣本集合等價(jià)關(guān)系為：{(x, y) : a(x)=a(y), x, y?U},28,符號(hào)機(jī)

14、器學(xué)習(xí)的泛化問題,一個(gè)無(wú)矛盾規(guī)則越短，其覆蓋對(duì)象越多，因此，符號(hào)機(jī)器學(xué)習(xí)的泛化是以信息長(zhǎng)度描述的。這樣，“最小”樹或規(guī)則集合就是其目標(biāo)函數(shù)兩個(gè)因素影響這個(gè)目標(biāo)：其一，從實(shí)域到符號(hào)域的映射，其二，在符號(hào)域上的約簡(jiǎn)。對(duì)“最小”兩者都是NP完全的。因此，近似算法是必然的但是，只有在符號(hào)域上的約簡(jiǎn)是符號(hào)機(jī)器學(xué)習(xí)特有，因此，其泛化能力受到限制不必與統(tǒng)計(jì)機(jī)器學(xué)習(xí)競(jìng)爭(zhēng)，設(shè)立新目標(biāo),29,數(shù)據(jù)分析與傳統(tǒng)機(jī)器學(xué)習(xí)區(qū)別,傳統(tǒng)機(jī)器學(xué)習(xí)假設(shè)所有用戶有相同

15、的需求，其目標(biāo)函數(shù)確定，而數(shù)據(jù)分析，不同用戶有不同需求，目標(biāo)函數(shù)隨用戶需求而定傳統(tǒng)機(jī)器學(xué)習(xí)是“黑箱”，模型無(wú)須可解釋，但是，數(shù)據(jù)分析必須考慮對(duì)用戶的可讀性傳統(tǒng)機(jī)器學(xué)習(xí)將“例外”考慮為噪音，而數(shù)據(jù)分析則認(rèn)為“例外”可能是更有意義的知識(shí),30,符號(hào)機(jī)器學(xué)習(xí)的特點(diǎn),由于這類機(jī)器學(xué)習(xí)主要處理符號(hào)，因此，如果獲得一個(gè)長(zhǎng)度較短的數(shù)據(jù)集合的描述，可以將其翻譯為人可以閱讀的文本。人通過(guò)閱讀這個(gè)文本就可以了解數(shù)據(jù)集合的內(nèi)容這個(gè)目標(biāo)與泛化能力無(wú)關(guān)，計(jì)

16、算結(jié)果只是給定數(shù)據(jù)集合根據(jù)特定需求的一個(gè)可以被人閱讀的縮影這與傳統(tǒng)數(shù)據(jù)分析的目標(biāo)一致,31,符號(hào)數(shù)據(jù)分析(數(shù)據(jù)挖掘),數(shù)據(jù)分析的主要工具是統(tǒng)計(jì)，“統(tǒng)計(jì)顯現(xiàn)”是分析的主要指標(biāo)符號(hào)數(shù)據(jù)分析，盡管統(tǒng)計(jì)工具是必要的，但是，主要是通過(guò)將符號(hào)數(shù)據(jù)集合約簡(jiǎn)為簡(jiǎn)潔形式,32,符號(hào)機(jī)器學(xué)習(xí)的最新進(jìn)展,Rough sets中的reduct理論是近幾年符號(hào)機(jī)器學(xué)習(xí)最重要的研究結(jié)果之一這個(gè)理論理論可以作為符號(hào)機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)這個(gè)理論可以作為符號(hào)數(shù)據(jù)分

17、析的基礎(chǔ)(數(shù)據(jù)挖掘),33,Reduct與符號(hào)數(shù)據(jù)分析,在任務(wù)上，association rules派生于統(tǒng)計(jì)相關(guān)分析，其方法可以使用reduct理論來(lái)刻畫Reduct具有很多重要的數(shù)學(xué)性質(zhì)，可以保證根據(jù)不同需求識(shí)別不同的例外我們建議，將符號(hào)數(shù)據(jù)分析建立在reduct理論之上,34,什么是outlier/exception,不能被模型(統(tǒng)計(jì)分布、規(guī)則集合等)概括的某些觀察稱為相對(duì)這個(gè)模型的outlier/ exception注釋

18、： 在統(tǒng)計(jì)學(xué)中，這類觀察稱為outlier，在認(rèn)知科學(xué)中，有意義的outlier稱為exception,35,方法,R是給定的reduct，使用R構(gòu)造新信息系統(tǒng)，R是這個(gè)信息系統(tǒng)的Core只要?jiǎng)h除一個(gè)核屬性，必然產(chǎn)生例外，同時(shí)縮短規(guī)則集,36,例外研究的意義,刪除例外，可以使得規(guī)則更為簡(jiǎn)潔，從而突出信息的重點(diǎn)。例外是噪音例外是比可以覆蓋大多數(shù)樣本的規(guī)則更為有趣的知識(shí)對(duì)專家，規(guī)則是“老生常談”，而例外則是應(yīng)該引起注意的事件或

19、知識(shí)例外是新研究與發(fā)現(xiàn)的開始,,37,增強(qiáng)機(jī)器學(xué)習(xí),增強(qiáng)機(jī)器學(xué)習(xí)最早提出是考慮“從變化環(huán)境中”學(xué)習(xí)蘊(yùn)含在環(huán)境中知識(shí)，其本質(zhì)是對(duì)環(huán)境的適應(yīng)開始的動(dòng)機(jī)主要是為了解決機(jī)器人規(guī)劃、避障與在環(huán)境中適應(yīng)的學(xué)習(xí)問題目前，由于網(wǎng)絡(luò)用戶是更為復(fù)雜的環(huán)境，例如，如何使搜索引擎適應(yīng)用戶的需求，成為更為重要的應(yīng)用領(lǐng)域,,38,流形機(jī)器學(xué)習(xí),很多問題的表示方法，使得信息十分稀疏，如何將信息稠密化是一個(gè)困難的問題（“維數(shù)災(zāi)難”），主成分分析是一種方法，但是，

20、只對(duì)線性情況有效流形學(xué)習(xí)是解決上述問題的非線性方法由于流形的本質(zhì)是分段線性化，因此，流形學(xué)習(xí)需要解決計(jì)算開集、設(shè)計(jì)同胚映射等問題,39,半監(jiān)督機(jī)器學(xué)習(xí),在觀測(cè)數(shù)據(jù)中，可能有很多觀測(cè)不能決定其類別標(biāo)號(hào)。這需要根據(jù)數(shù)據(jù)中已知類別標(biāo)號(hào)的樣本與領(lǐng)域知識(shí)來(lái)推測(cè)這些樣本的類別標(biāo)號(hào)，并建立問題世界的模型，這就是半監(jiān)督學(xué)習(xí)這類問題直接來(lái)自于實(shí)際應(yīng)用：例如，大量醫(yī)學(xué)影像，醫(yī)生把每張片子上的每個(gè)病灶都標(biāo)出來(lái)再進(jìn)行學(xué)習(xí)，是不可能的，能否只標(biāo)一部分，并且

21、還能利用未標(biāo)的部分？,40,多示例機(jī)器學(xué)習(xí),傳統(tǒng)的機(jī)器學(xué)習(xí)中，一個(gè)對(duì)象有一個(gè)描述，而在一些實(shí)際問題中，一個(gè)對(duì)象可能同時(shí)有多個(gè)描述，到底哪個(gè)描述是決定對(duì)象性質(zhì)(例如類別)的，卻并不知道。解決這種“對(duì)象：描述：類別”之間1:N:1關(guān)系的學(xué)習(xí)就是多示例學(xué)習(xí),41,Ranking機(jī)器學(xué)習(xí),其原始說(shuō)法是learning for ranking問題主要來(lái)自信息檢索，假設(shè)用戶的需求不能簡(jiǎn)單地表示為“喜歡”或“不喜歡”，而需要將“喜歡”表示為一個(gè)順序

22、，問題是如何通過(guò)學(xué)習(xí)，獲得關(guān)于這個(gè)“喜歡”順序的模型。,42,數(shù)據(jù)流機(jī)器學(xué)習(xí),在網(wǎng)絡(luò)數(shù)據(jù)分析與處理中，有一類問題，從一個(gè)用戶節(jié)點(diǎn)上流過(guò)的數(shù)據(jù)，大多數(shù)是無(wú)意義的，由于數(shù)據(jù)量極大，不能全部存儲(chǔ)，因此，只能簡(jiǎn)單判斷流過(guò)的文件是否有用，而無(wú)法細(xì)致分析如何學(xué)習(xí)一個(gè)模型可以完成這個(gè)任務(wù)，同時(shí)可以增量學(xué)習(xí)，以保證可以從數(shù)據(jù)流中不斷改善(或適應(yīng))用戶需求的模型,43,研究現(xiàn)狀,上述的五類機(jī)器學(xué)習(xí)范式還處于實(shí)驗(yàn)觀察階段，沒有堅(jiān)實(shí)的理論基礎(chǔ)！這些范式主