AAI06歸納學(xué)習(xí)(2)高級人工智能史忠植

第六章歸納學(xué)習(xí)(2)史忠植中科院計(jì)算所2/6/20231史忠植高級人工智能決策樹發(fā)現(xiàn)概念描述空間一種特別有效的方法是形成決策樹。Hunt、Marin、和Stone于1966年研制了一個(gè)概念學(xué)習(xí)系統(tǒng)CLS,可以學(xué)習(xí)單個(gè)概念，并用此學(xué)到的概念分類新的實(shí)例。Quinlan于1983年研制了ID3(1983)。Schlimmer和Fisher于1986年構(gòu)造了ID4算法，允許遞增式地構(gòu)造決策樹。Utgoff于1988年提出ID5算法，它允許通過修改決策樹來增加新的訓(xùn)練實(shí)例，而無需重建決策樹2/6/20232史忠植高級人工智能決策樹2/6/20233史忠植高級人工智能決策樹2/6/20234史忠植高級人工智能決策樹2/6/20235史忠植高級人工智能決策樹2/6/20236史忠植高級人工智能決策樹2/6/20237史忠植高級人工智能決策樹2/6/20238史忠植高級人工智能決策樹2/6/20239史忠植高級人工智能決策樹2/6/202310史忠植高級人工智能決策樹2/6/202311史忠植高級人工智能決策樹2/6/202312史忠植高級人工智能CLS算法

(1)如果C中全部實(shí)例為正例，則建立一個(gè)YES結(jié)點(diǎn)，并且停止。如果C中全部實(shí)例為反例，則建立一個(gè)NO結(jié)點(diǎn)，并且停止。否則選擇一個(gè)屬性A,根據(jù)它的值v1,…,vn

建立決策樹。(2)根據(jù)值V，將訓(xùn)練實(shí)例$C$劃分為子集C1,…,Cn。(3)對每個(gè)集合Ci遞歸地應(yīng)用此算法。2/6/202313史忠植高級人工智能決策樹

CLS算法可以產(chǎn)生所有可能的決策樹，正確分類訓(xùn)練實(shí)例，并能選擇最簡單的決策樹。但是，它的學(xué)習(xí)問題不能太大。為了克服這種限止，ID3采用訓(xùn)練實(shí)例的子集，即可以選擇窗口來形成決策樹。這種樹可以正確分類窗口中的所有對象。然后，使用該樹可以分類訓(xùn)練集中的所有其它對象。如果該樹對所有對象給以正確的解答，那么，它對整個(gè)訓(xùn)練集是正確的，算法就結(jié)束。如果不是這樣，選擇一個(gè)例外加到窗口繼續(xù)處理，直到發(fā)現(xiàn)正確的決策樹為止。2/6/202314史忠植高級人工智能決策樹

ID3采用信息論方法，減小對象分類的測試期望值。屬性選擇是基于可能性假設(shè)，即決策樹的復(fù)雜性與消息傳遞的信息量有關(guān)。設(shè)C包括類P的對象p和類N的對象n,假設(shè)：(1)任何C的正確決策樹，以C中表示同樣的比例將對象分類。任何對象屬于類P的概率為p/(p+n)，

屬于類N的概率為n/(p+n)。2/6/202315史忠植高級人工智能決策樹

(2)當(dāng)用決策樹進(jìn)行分類時(shí)，返回一個(gè)類。作為消息源`P'或`N'有關(guān)的決策樹，產(chǎn)生這些消息所需的期望信息為：

I(p,n)=-p/p+nlog2(p/(p+n))-n/p+nlog2(n/(p+n))2/6/202316史忠植高級人工智能決策樹

決策樹根的屬性A具有A1,A2,…,Am，它將C劃分為C1,C2,…,Cm,其中Ci

包括C中屬性$A$的值為Ai的那些對象。設(shè)Ci包括類P的對象pi和類N的對象ni。子樹Ci所需的期望信息是I(pi,ni)。以屬性A作為樹根所要求的期望信息可以通過權(quán)值平均得到：E(A)={pi+ni}/{p+n}I(pi,ni)其中第i個(gè)分支的權(quán)值是與C中屬于Ci的對象成比例。所以按A分支的信息增益為：

gain(A)=I(p,n)-E(A)2/6/202317史忠植高級人工智能決策樹

ID3檢查所有的候選屬性，選擇增益最大的屬性A作為根結(jié)點(diǎn)，形成樹。然后，對子樹C1,C2,…,Cm以同樣處理，遞歸地形成決策樹。2/6/202318史忠植高級人工智能ID3算法

(1)選擇給定訓(xùn)練實(shí)例的隨機(jī)子集（稱為窗口）。

(2)重復(fù)(a)形成一條規(guī)則解釋當(dāng)前窗口。(b)從其余實(shí)例中尋找該規(guī)則的例外。(c)由當(dāng)前窗口和規(guī)則例外生成新的窗口。

直到該規(guī)則沒有例外為止。2/6/202319史忠植高級人工智能ID3算法

ID3專門用于處理大量對象。事實(shí)上，時(shí)間計(jì)算增加僅與下面乘積成線性關(guān)系：(1)訓(xùn)練對象數(shù),(2)

描述對象的屬性數(shù),(3)

決策樹的結(jié)點(diǎn)數(shù)，它反映所求概念的復(fù)雜性。2/6/202320史忠植高級人工智能決策樹

ID3DecisionTreeLearningAlgorithm

ID3(Examples,Target,Attributes)CreatearootnodeIfallExampleshavethesameTargetvalue,givetherootthislabelElseifAttributesisemptylabeltherootaccordingtothemostcommonvalueElsebeginCalculatetheinformationgainforeachattribute,accordingtotheaverageentropyformulaSelecttheattribute,A,withthelowestaverageentropy(highestinformationgain)andmakethistheattributetestedattherootend2/6/202321史忠植高級人工智能決策樹

Foreachpossiblevalue,v,ofthisattributeAddanewbranchbelowtheroot,correspondingtoA=vLetExamples(v)bethoseexampleswithA=vIfExamples(v)isempty,makethenewbranchaleafnodelabelledwiththemostcommonvalueamongExamplesElseletthenewbranchbethetreecreatedbyID3(Examples(v),Target,Attributes-{A})end2/6/202322史忠植高級人工智能決策樹ID4

1986,Schlimmer和Fisher設(shè)計(jì)了ID4學(xué)習(xí)算法,是一種遞增式學(xué)習(xí)算法。他們修改ID3算法，在每個(gè)可能的決策樹結(jié)點(diǎn)創(chuàng)建一系列表。每個(gè)表由全部未檢測屬性值和每個(gè)值的正例和反例數(shù)組成。當(dāng)處理一個(gè)新例時(shí)，每個(gè)屬性值的正例或反例遞增計(jì)量。2/6/202323史忠植高級人工智能決策樹ID4

輸入:決策樹，一個(gè)實(shí)例輸出:決策樹(1)若該實(shí)例是正例，正例數(shù)加1，否則，反例數(shù)加1。(2)如果實(shí)例全部為正例或反例，則返回決策樹。(3)否則(a)計(jì)算期望信息分?jǐn)?shù)。(b)實(shí)例中出現(xiàn)的每個(gè)屬性、每個(gè)值，使之遞增正例數(shù)或者反例數(shù)。(c)計(jì)算全部屬性的信息分?jǐn)?shù)。

2/6/202324史忠植高級人工智能決策樹ID4

(d)如果沒有根，或者最大屬性不在根結(jié)點(diǎn)，則創(chuàng)建新樹。

(i)如果最大屬性是x2

依賴關(guān)系，那么用它作為這棵樹的根結(jié)點(diǎn)。(ii)鏈接根到每個(gè)根屬性的值

(e)跳轉(zhuǎn)到步驟(1)，下面創(chuàng)建的子樹鏈到該實(shí)例的根屬性值。2/6/202325史忠植高級人工智能決策樹ID5

在ID4的基礎(chǔ)上Utgoff提出了ID5學(xué)習(xí)算法(Utgoff1988)。ID5與ID4的差別在于檢測屬性。ID5拋棄舊的檢測屬性下面的子樹，從下面選出檢測屬性形成樹。這種方法的優(yōu)點(diǎn)是在樹操縱時(shí)重新計(jì)算正例和反例的數(shù)，不要對實(shí)例重新處理。2/6/202326史忠植高級人工智能ID5算法

(1)對結(jié)點(diǎn)每個(gè)可能的檢測屬性，修改屬性的正例和反例數(shù)，以及修改該屬性值觀察值的正例數(shù)和反例數(shù)。(2)如果非檢測屬性的最低信息論測度低于當(dāng)前的檢測屬性，則將該檢測屬性提上來，重新構(gòu)造決策樹。(3)在給定結(jié)點(diǎn)僅觀察到正例或反例，那么保存其余訓(xùn)練實(shí)例。結(jié)束停止。(4)在實(shí)例描述中，對所希望檢測屬性值下面的決策樹進(jìn)行遞歸修改。2/6/202327史忠植高級人工智能ID5屬性提升算法

(1)遞歸地提升屬性到最近子樹的根結(jié)點(diǎn)。(2)對每個(gè)子樹的分支值，將舊的檢測屬性推到新屬性下，構(gòu)造新的決策樹。這樣，形成一組子樹，每個(gè)根結(jié)點(diǎn)都是所希望的檢測屬性。(3)合并子樹，形成決策樹，其根結(jié)點(diǎn)是所希望的檢測屬性。2/6/202328史忠植高級人工智能決策樹

Missingvalues

MultivaluedattributesContinuousvaluedattributes2/6/202329史忠植高級人工智能歸納學(xué)習(xí)的計(jì)算理論

學(xué)習(xí)的計(jì)算理論主要研究學(xué)習(xí)算法樣本復(fù)雜性計(jì)算復(fù)雜性。2/6/202330史忠植高級人工智能Gold學(xué)習(xí)理論

在形式語言學(xué)習(xí)的上下文中，Gold引入收斂的概念，有效地處理了從實(shí)例學(xué)習(xí)的問題。學(xué)習(xí)算法允許提出許多假設(shè)，無須知道什么時(shí)候它是正確的，只要確認(rèn)某點(diǎn)它的計(jì)算是正確的假設(shè)。由于Gold算法的復(fù)雜性很高，因此這種風(fēng)范并沒有在實(shí)際學(xué)習(xí)中得到應(yīng)用。2/6/202331史忠植高級人工智能Gold學(xué)習(xí)理論

基于Gold學(xué)習(xí)框架，Shapiro提出了模型推理算法研究形式語言與其解釋之間的關(guān)系，也就是形式語言的語法與語義之間的關(guān)系。模型論把形式語言中的公式、句子理論和它們的解釋─模型，當(dāng)作數(shù)學(xué)對象進(jìn)行研究。Shapiro模型推理算法只要輸入有限的事實(shí)就可以得到一種理論輸出(Shapiro1981)。2/6/202332史忠植高級人工智能Gold學(xué)習(xí)理論

Gold的語言學(xué)習(xí)理論研究引入兩個(gè)基本概念，即極限辨識枚舉辨識,這對早期的歸納推理的理論研究起了非常重要的作用(Gold1967)。2/6/202333史忠植高級人工智能Gold學(xué)習(xí)理論

極限辨識把歸納推理看作一種無限過程，歸納推理方法的最終或極限行為可以看作是它的成功標(biāo)準(zhǔn)。假設(shè)M是一種歸納推理方法，它企圖正確地描述未知規(guī)則R。假設(shè)M重復(fù)運(yùn)行，R的實(shí)例集合則愈耒愈大，形成M推測的無限序列g(shù)1,g2,…。如果存在某個(gè)數(shù)m，使得gm是R的正確描述， gm=gm＋1=gm＋2=…,

2/6/202334史忠植高級人工智能Gold學(xué)習(xí)理論

枚舉辨識是第一種方法推測多項(xiàng)式序列的抽象，即對可能的規(guī)則空間進(jìn)行系統(tǒng)搜索，直到發(fā)現(xiàn)與迄今為止的所有數(shù)據(jù)相一致的推測。假設(shè)規(guī)定了規(guī)則的具體領(lǐng)域，有一個(gè)描述枚舉，即d1，d2,d3,…,以致于領(lǐng)域中的每一條規(guī)則在枚舉中有一種或多種描述。給定一條規(guī)則的某個(gè)實(shí)例集合，枚舉辨識方法將通過這個(gè)表，找到第一個(gè)描述d1，即與給定的實(shí)例相容，那么推測為d1。這種方法不能確定是否會達(dá)到正確的極限辨識。如果實(shí)例表示和相容關(guān)系滿足下面兩個(gè)條件，那么枚舉方法保證極限辨識該領(lǐng)域中的全部規(guī)則：(1)一個(gè)正確假設(shè)總是與給定的實(shí)例相容。(2)任何不正確的假設(shè)與實(shí)例足夠大的集合或與全部集合不相容。為了枚舉方法是可計(jì)算的，枚舉d1,d2,d3,…必須是可計(jì)算的，它必須能夠計(jì)算給定的描述與給定的實(shí)例集合是相容的。2/6/202335史忠植高級人工智能枚舉辨識算法枚舉辨識算法。輸入：一組表達(dá)式的集合E=e1,e2,…。

諭示(oracle)TE提供足夠的目標(biāo)實(shí)例集。

排序信息的諭示LE。輸出：一系列假設(shè)斷言H1,H_2,…,每個(gè)假設(shè)Hi都在E中，并與第i個(gè)實(shí)例一致。2/6/202336史忠植高級人工智能枚舉辨識算法過程：1.初始化，i1;2.examples

emptyset;3.Loop:

3.1調(diào)用TE(),將example加到集合examples;3.2WhileLE(ei,+x)=no,對正例集+x,或者LE(ei,-x)=yes,對反例集-x,ii+1;

4.輸出ei2/6/202337史忠植高級人工智能模型推理系統(tǒng)模型推理問題是科學(xué)家所面臨的問題抽象，他們在具有固定概念框架的某種領(lǐng)域里工作，進(jìn)行試驗(yàn)，試圖找到一種理論可以解釋他們的結(jié)果。在這種抽象中研究的領(lǐng)域是對給定的一階語言L某種未知模型M的領(lǐng)域，實(shí)驗(yàn)是檢測M中L語句的真值，目標(biāo)是尋找一組正確假設(shè)，它們包含全部正確的可測試的句子。

L語句分成兩個(gè)子集：觀測語言Lo和假設(shè)語言Lh。假設(shè)

LoLh

L‘其中

是空語句。2/6/202338史忠植高級人工智能模型推理系統(tǒng)模型推理問題可以定義如下：假設(shè)給定一階語言$L和兩個(gè)子集：觀測語言Lo和假設(shè)語言Lh。另外對L的未知模型M給定一種處理機(jī)制oracle。模型推理問題是尋找M的一種有限的Lo─完備公理化。求解模型推理問題的算法稱為模型推理算法。模型M的枚舉是一個(gè)無限序列F1,F2,F3,…，其中Fi是關(guān)于M的事實(shí)，Lo的每個(gè)語句發(fā)生在事實(shí)Fi=<,V>,i>0。模型推理算法一次讀入給定觀測語言Lo的模型的一種枚舉，一個(gè)事實(shí)，產(chǎn)生假設(shè)語言Lh的語句的有限集稱為算法的推測。2/6/202339史忠植高級人工智能模型推理系統(tǒng)

h是整個(gè)遞歸函數(shù)。設(shè)Sfalse為

，Strue為{}，k為0。repeat

讀入下一個(gè)事實(shí)Fn=<,V>，

加到Sv,while

∈Sfalse以致于Tk

n或有一個(gè)i

∈

Strue以致于

Tk

niidok=k+1，輸出Tkforever2/6/202340史忠植高級人工智能Valiant學(xué)習(xí)理論

Valiant認(rèn)為一個(gè)學(xué)習(xí)機(jī)必須具備下列性質(zhì)：(1)機(jī)器能夠證明地學(xué)習(xí)所有類的概念。更進(jìn)一步，這些類可以特征化。(2)對于通用知識概念類是合適的和不平常的。(3)機(jī)器演繹所希望的程序的計(jì)算過程要求在可行的步數(shù)內(nèi)。2/6/202341史忠植高級人工智能Valiant學(xué)習(xí)理論

學(xué)習(xí)機(jī)由學(xué)習(xí)協(xié)議和演繹過程組成。學(xué)習(xí)協(xié)議規(guī)定從外部獲得信息的方法。演繹過程是一種機(jī)制，學(xué)習(xí)概念的正確識別算法是演繹的。從廣義來看，研究學(xué)習(xí)的方法是規(guī)定一種可能的學(xué)習(xí)協(xié)議，使用這種協(xié)議研究概念類，識別程序可以在多項(xiàng)式時(shí)間內(nèi)演繹。具體協(xié)議允許提供兩類信息。第一種是學(xué)習(xí)者對典型數(shù)據(jù)的訪問，這些典型數(shù)據(jù)是概念的正例。要確切地說，假設(shè)這些正例本質(zhì)上有一種任意確定的概率分布。調(diào)用子程序EXAMPLES產(chǎn)生一種這樣的正例。產(chǎn)生不同例子的相對概率是分布確定的。第二個(gè)可用的信息源是ORACLE。在最基本的版本中，當(dāng)提交數(shù)據(jù)時(shí)，它將告訴學(xué)習(xí)該數(shù)據(jù)是否是概念的正例示。2/6/202342史忠植高級人工智能Valiant學(xué)習(xí)理論

假設(shè)X是實(shí)例空間，一個(gè)概念是X的一個(gè)子集。如果實(shí)例在概念中則為正例，否則為反例。概念表示是一種概念的描述，概念類是一組概念表示。學(xué)習(xí)模型是概念類的有效的可學(xué)習(xí)性。Valiant學(xué)習(xí)理論僅要求對目標(biāo)概念的很好近似具有極高的概率。允許學(xué)習(xí)者產(chǎn)生的概念描述與目標(biāo)概念有一個(gè)小的偏差

，它是學(xué)習(xí)算法的一個(gè)輸入?yún)?shù)。并且，允許學(xué)習(xí)者失敗的概率為，這也是一個(gè)輸入?yún)?shù)。兩種概念之間的差別采用在實(shí)例空間X的分布概率D來評測：

diffD(c1,c2)=D(x)2/6/202343史忠植高級人工智能Valiant學(xué)習(xí)理論

根據(jù)協(xié)議，一個(gè)概念類C是可學(xué)習(xí)的當(dāng)且僅當(dāng)有一種算法A，使用協(xié)議，對所有的目標(biāo)概念表示c*C和全部分布D，(1)執(zhí)行時(shí)間是與1/、1/、c*數(shù)目和其它相關(guān)參數(shù)有關(guān)的多項(xiàng)式。(2)輸出C中的概念c具有概率1-，

diffD(c,c*)<2/6/202344史忠植高級人工智能SupportVectorMachine(SVM)2/6/202345史忠植高級人工智能SupportVectorMachine(SVM)2/