人工智能課件 －07機器學習

《人工智能課件 －07機器學習》由會員分享，可在線閱讀，更多相關(guān)《人工智能課件 －07機器學習（81頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第7章 機器學習第一節(jié) 基本概念一、什么是機器學習一、什么是機器學習一、什么是機器學習一、什么是機器學習1、學習對“學習”概念研究有較大影響的幾種觀點：(1)學習是系統(tǒng)改進其性能的過程-西蒙的觀點(2)學習是獲取知識的過程-ES專家的觀點(3)學習是技能的獲取-心理學家的觀點(4)學習是事物規(guī)律的發(fā)現(xiàn)過程-AI專家的觀點綜合觀點：綜合觀點：綜合觀點：綜合觀點：學習是一個有特定目的的知識獲取過程，其內(nèi)在的行為是獲取知識、積累經(jīng)驗、發(fā)現(xiàn)規(guī)律；外部表現(xiàn)為改進性能、適應(yīng)環(huán)境、實現(xiàn)系統(tǒng)的自我完善。第一節(jié) 基本概念2、機器學習 所謂機器學習就是使計算機能模擬人的學習行為，自動地通過學習獲取知識和技能，不斷

2、改善其性能，實現(xiàn)自我完善。q機器學習研究工作的主要方面機器學習研究工作的主要方面機器學習研究工作的主要方面機器學習研究工作的主要方面(1)學習機理的研究；(2)學習方法的研究；(3)面向任務(wù)的學習。第一節(jié) 基本概念二、機器學習的發(fā)展歷史二、機器學習的發(fā)展歷史二、機器學習的發(fā)展歷史二、機器學習的發(fā)展歷史大致分為四個階段。(1)第一階段，20世紀50年代中期到60年代中期，稱為熱烈時期。研究的內(nèi)容主要是“沒有知識”的學習，其對象是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)，主要方法是不斷修改系統(tǒng)的控制參數(shù)以改進系統(tǒng)的性能，不涉及與具體任務(wù)有關(guān)的知識。(2)第二階段，20世紀60年代中期到70年代中期，稱為冷靜時期

3、。研究目標是模擬人類的概念學習過程，并采用邏輯結(jié)構(gòu)和圖結(jié)構(gòu)作為機器內(nèi)部的描述。第一節(jié) 基本概念(3)第三階段，20世紀70年代中期到80年代中期，稱為復興時期。單概念學習擴展到多概念學習，探索不同的學習策略和學習方法。機器的學習過程一般建立在大規(guī)模的知識庫上，實現(xiàn)知識強化學習。示例歸約學習成為研究的主流。(4)第四階段，20世紀80年代中期以后，符號學習由“無知”學習轉(zhuǎn)向到有專門領(lǐng)域知識的增長型學習，因而出現(xiàn)了有一定知識背景的分析學習。第二節(jié) 主要策略與基本結(jié)構(gòu)一、主要策略一、主要策略一、主要策略一、主要策略 機械學習策略 指導式學習策略 類比學習策略 示例學習策略二、機器學習的分類二、機器學

4、習的分類二、機器學習的分類二、機器學習的分類q1、按系統(tǒng)的學習能力分 有監(jiān)督學習 無監(jiān)督學習q2、按學習方法分 機械式學習 指導式學習 類比學習 示例學習 解釋學習q3、按推理方式分 演繹學習 歸納學習q4、按綜合屬性分 歸納學習 分析學習 連接學習 遺傳算法 分類器系統(tǒng)第二節(jié) 主要策略與基本結(jié)構(gòu)第二節(jié) 主要策略與基本結(jié)構(gòu)三、機器學習系統(tǒng)的基本結(jié)構(gòu)三、機器學習系統(tǒng)的基本結(jié)構(gòu)三、機器學習系統(tǒng)的基本結(jié)構(gòu)三、機器學習系統(tǒng)的基本結(jié)構(gòu)環(huán)境學習知識庫執(zhí)行學習系統(tǒng)的基本結(jié)構(gòu)學習系統(tǒng)的基本結(jié)構(gòu) 一個學習系統(tǒng)應(yīng)具有環(huán)境、學習、知識庫、執(zhí)行四個要素。1973年莎利斯關(guān)于機器學習系統(tǒng)的定義：如果一個系統(tǒng)能夠從某個過

5、程或環(huán)境的未知特征中學到有關(guān)信息，并且能把學到的信息用于未來的估計、分類、決策或控制，以便改進系統(tǒng)的性能，那么它就是學習系統(tǒng)，因此，一個學習系統(tǒng)應(yīng)具有環(huán)境、具有一定的學習能力、能應(yīng)用知識求解問題、能提高系統(tǒng)的性能。環(huán)境向系統(tǒng)的學習部分提供某些信息，學習部分利用這些信息修改知識庫，以增進系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識庫完成任務(wù)，同時把獲得的信息反饋給學習部分。第二節(jié) 主要策略與基本結(jié)構(gòu)q影響學習系統(tǒng)設(shè)計的重要因素影響學習系統(tǒng)設(shè)計的重要因素影響學習系統(tǒng)設(shè)計的重要因素影響學習系統(tǒng)設(shè)計的重要因素(1)環(huán)境向系統(tǒng)提供的信息質(zhì)量(2)知識的表示形式q選擇表示方式時，應(yīng)注意的問題選擇表示方式時

6、，應(yīng)注意的問題選擇表示方式時，應(yīng)注意的問題選擇表示方式時，應(yīng)注意的問題 表達能力 易于推理 容易修改知識庫 知識表示易于擴展第三節(jié) 機械學習 機械學習又稱為死記硬背式學習，是一種最簡單、最原始的學習方法。q基本思想：基本思想：基本思想：基本思想：把新的知識存儲起來，供需要時檢索調(diào)用，而無需推理和計算。在機械學習中只記憶計算的輸入輸出，忽略計算過程，因此就把計算問題化簡成存儲問題。即：(X1,X2,Xn)(Y1,Y2,Ym)f(X1,X2,Xn)(Y1,Y2,Ym)第三節(jié) 機械學習q機械學習的主要問題機械學習的主要問題機械學習的主要問題機械學習的主要問題(1)存儲信息的組織；(2)環(huán)境的穩(wěn)定性與

7、存儲的信息的通用性；(3)存儲與計算之間的權(quán)衡。第四節(jié) 歸納學習 歸納學習是應(yīng)用歸納推理進行學習的一類方法，分為示例學習(有教師)、觀察與發(fā)現(xiàn)學習(無教師)兩種。一、歸納推理一、歸納推理一、歸納推理一、歸納推理從具體到一般的推理方法。q歸納推理的重要特性歸納推理的重要特性歸納推理的重要特性歸納推理的重要特性(1).歸納出的結(jié)論只能以某種程度相信它為真；(2).歸納推理是非單調(diào)的。第四節(jié) 歸納學習q常用的歸納推理方法常用的歸納推理方法常用的歸納推理方法常用的歸納推理方法1、枚舉歸納2、聯(lián)想歸納3、類比歸納4、逆推理歸納5、消除歸納1、枚舉歸納 設(shè)a1,a2,an是某類事物A中的具體事物，若已知a

8、1,a2,an都有屬性P，并且沒有發(fā)現(xiàn)反例，當n足夠大時，就可得出結(jié)論：“A中所有事物都具有屬性P”。例如、張三是足球運動員，他的體格健壯。李四是足球運動員，他的體格健壯。劉六是足球運動員，他的體格健壯。當事實足夠多時，可歸納出：“凡是足球運動員，他的體格一定健壯”的一般性結(jié)論。第四節(jié) 歸納學習第四節(jié) 歸納學習如果，每個實例都帶有一定得可信度因子，例如、張三是足球運動員，他的體格健壯(0.95)。李四是足球運動員，他的體格健壯(0.90)。劉六是足球運動員，他的體格健壯(1.0)。則可用各個實例可信度的平均值作為一般知識的可信度。例如、得出的結(jié)論：“凡是足球運動員，他的體格一定健壯”(0.95

9、)第四節(jié) 歸納學習2、聯(lián)想歸納 若已知兩個事物a與b有n個屬性相似或相同，即 a具有屬性P1，b具有屬性P1 a具有屬性P2，b具有屬性P2 a具有屬性Pn，b具有屬性Pn發(fā)現(xiàn)a具有屬性Pn+1，則當n足夠大時，可歸納出：b也具有屬性Pn+1 的結(jié)論。第四節(jié) 歸納學習3、類比歸納設(shè)A、B分別是兩類事物的集合：A=a1,a2,B=b1,b2,并ai和bi總是成對出現(xiàn)，且當ai有屬性P時，bi就有屬性Q與之對應(yīng)，即 P(ai)Q(bi)則當A與B有一對新元素出現(xiàn)時，設(shè)為a和b，若已知a有屬性P，就可得出b有屬性Q，即 P(a)Q(b)第四節(jié) 歸納學習4、逆推理歸納 是一種由結(jié)論成立而推出前提以某種

10、可信度成立的歸納方法。一般模式是：(1)若H為真時，則HE必為真或以可信度cf1成立；(2)觀察到E成立或以可信度cf2成立；(3)則H以某種可信度cf成立。表示為：H E cf1 E cf2 H cfcf的計算方法可根據(jù)問題的實際情況而定。例如，可把P(E|H)當成HE的可信度cf1，則EH的可信度cf1可按Bayes公式計算。由cf1和cf2就可計算出H的可信度 cf=cf1cf2第四節(jié) 歸納學習5、消除歸納 當我們對某個事物發(fā)生的原因不清楚時，通常會作一些假設(shè)，這些假設(shè)之間是析取關(guān)系。以后，隨著對事物認識的不斷深化，原先作出的某些假設(shè)有可能被否定，經(jīng)過若干次否定后，剩下的就可作為事物發(fā)生

11、的原因。這樣的思維過程稱為消除歸納。已知：A1 V A2 V V An A1 Ai 結(jié)論：Aj第四節(jié) 歸納學習二、示例學習二、示例學習二、示例學習二、示例學習 示例學習是通過從環(huán)境中獲得若干與某個概念相關(guān)的示例，經(jīng)歸納得出一般性概念的學習方法。1 1、示例學習的學習模型、示例學習的學習模型、示例學習的學習模型、示例學習的學習模型示例空間搜索解釋形成知識知識庫驗證第四節(jié) 歸納學習示例學習的學習過程：示例學習的學習過程：示例學習的學習過程：示例學習的學習過程：首先從示例空間中選擇合適的訓練示例，然后經(jīng)解釋歸納出一般性知識，最后再從示例空間中選擇更多的示例對它進行驗證。與示例空間有關(guān)的主要問題是示例

12、的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。“搜索”作用是從示例空間中查找所需的示例；“解釋”是從搜索到的示例中抽象出所需的有關(guān)信息供形成知識使用?！靶纬芍R”通過綜合、歸納等形式形成一般的知識。“驗證”檢驗所形成的知識的正確性。第四節(jié) 歸納學習2、形成知識的方法(1)變量代換常量 是枚舉歸納的常用方法。例如，“同花”概念的形成示例1：花色(c1,C)花色(c2,C)花色(c3,C)花色(c4,C)同花(c1,c2,c3,c4)示例2：花色(c1,H)花色(c2,H)花色(c3,H)花色(c4,H)同花(c1,c2,

13、c3,c4)將這兩個示例中的常量C和H用變量x代換即可形成一般性知識：花色(c1,x)花色(c2,x)花色(c3,x)花色(c4,x)同花(c1,c2,c3,c4)第四節(jié) 歸納學習(2)舍棄條件 是把示例中的某些無關(guān)條件的子條件舍去。例如：花色(c1,C)點數(shù)(c1,2)花色(c2,C)點數(shù)(c2,4)花色(c3,C)點數(shù)(c3,6)花色(c4,C)點數(shù)(c4,2)同花(c1,c2,c3,c4)由于點數(shù)對形成“同花”概念無直接影響，則可把示例中的“點數(shù)”舍去。第四節(jié) 歸納學習(3)增加操作 有時需要通過增加操作來形成知識，常用的方法有前件析取法和內(nèi)部析取法。前件析取法：前件析取法：前件析取法：

14、前件析取法：通過對示例的前件進行析取形成知識。例如，“臉牌”示例1:點數(shù)(c1,J)臉(c1)示例2:點數(shù)(c1,Q)臉(c1)示例3:點數(shù)(c1,K)臉(c1)若將各示例的前件進行析取，則可得到一般知識：規(guī)則：點數(shù)(c1,J)V 點數(shù)(c1,Q)V 點數(shù)(c1,K)臉(c1)第四節(jié) 歸納學習 內(nèi)部析取法內(nèi)部析取法內(nèi)部析取法內(nèi)部析取法：在示例的表示中使用集合與集合間的成員關(guān)系來形成知識。例如，“臉牌”示例1:點數(shù)(c1)J臉(c1)示例2:點數(shù)(c1)Q臉(c1)示例3:點數(shù)(c1)K臉(c1)用內(nèi)部析取法可得到一般知識：規(guī)則：點數(shù)(c1)J,Q,K臉(c1)第四節(jié) 歸納學習(4)合取變析取

15、是通過把示例中條件的合取關(guān)系變?yōu)槲鋈￡P(guān)系來形成一般性知識的。例如，由“男同學和女同學可以組成一個班”，可以歸納出“男同學或女同學可以組成一個班”(5)歸結(jié)歸納 利用歸結(jié)原理，可得到如下形成知識的方法。PE1H PE2H可得到：E1E2H第四節(jié) 歸納學習三、觀察與發(fā)現(xiàn)學習三、觀察與發(fā)現(xiàn)學習三、觀察與發(fā)現(xiàn)學習三、觀察與發(fā)現(xiàn)學習 觀察學習(主要用于概念聚類)觀察與發(fā)現(xiàn)學習 機器發(fā)現(xiàn)(發(fā)現(xiàn)規(guī)律、或規(guī)則)1、概念聚類 基本思想：基本思想：基本思想：基本思想：把示例按一定的方式和準則進行分組，如劃分為不同的類、不同的層次等，使不同的組代表不同的概念，并且對每一組進行特征概括，得到一個概念的語義描述。2、機

16、器發(fā)現(xiàn) 困難的。第五節(jié) 類比學習 類比學習是通過對相似事物進行比較所進行的一種學習方法，基礎(chǔ)是類比推理。例如、盧瑟福將原子結(jié)構(gòu)和太陽系進行類比，發(fā)現(xiàn)了原子結(jié)構(gòu)；水管中的水壓計算公式與電路中的電壓計算公式相似。第五節(jié) 類比學習一、類比推理一、類比推理一、類比推理一、類比推理 類比推理是指，由新情況與記憶中的已知情況在某些方面相似，從而推出它們在其他相關(guān)方面也相似。類比推理是在兩個相似域之間進行的：一個是已認識的域，稱為源域，記為 S；另一個是當前尚未完全認識的域，稱為目標域，記為T。類比推理的目的就是從S中選出與當前問題最近似的問題及其求解方法來求解當前的問題，或者建立起目標域中已有命題間的聯(lián)系

17、，形成新知識。設(shè)S1、T1分別表示 S 與 T 中的某一情況，且S1與T1相似，再假設(shè)S2與S1相關(guān)，則由類比推理可推出T中的T2,且T2與S2相似。第五節(jié) 類比學習q推理過程推理過程推理過程推理過程(1)回憶與聯(lián)想 通過回憶與聯(lián)想在S中找出與當前問題相似的問題。(2)選擇 從S的相似的問題選出最相似的問題。(3)建立對應(yīng)關(guān)系 在S與T相似的問題之間建立相似元素的對應(yīng)關(guān)系，并建立相應(yīng)的映射。(4)轉(zhuǎn)換 把S中的有關(guān)知識引入到T中，從而建立起求解當前問題的方法或者學習到關(guān)于T的新知識。第五節(jié) 類比學習q類比推理形式的說明類比推理形式的說明類比推理形式的說明類比推理形式的說明 設(shè)有兩個具有相同或相

18、似的論域：源域S和目標域T，且已知S中的元素a和T中的元素b具有相似的屬性P，即P(a)P(b)，a還具有屬性Q，即Q(a)。根據(jù)類比推理，b也具有屬性Q。即 P(a)Q(a),P(a)P(b)|-Q(b)Q(a)第五節(jié) 類比學習二、類比學習二、類比學習二、類比學習二、類比學習主要包括四個過程(1)輸入一組已知條件(已解決的問題)和一組未完全確定的條件(新問題)；(2)對輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對應(yīng)關(guān)系；(3)根據(jù)相似變換的方法，將已解決的問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題的新知識；(4)對類比推理中得到的新知識進行驗證。第五

19、節(jié) 類比學習q類比學習的研究分為兩類類比學習的研究分為兩類類比學習的研究分為兩類類比學習的研究分為兩類(1)問題求解型的類比學習 基本思想：基本思想：基本思想：基本思想：是當求解一個新問題時，總是首先回憶以 前是否求解過類似的問題，若是，則可以 此為根據(jù)，通過對先前的求解過程加以適 當修改，使之滿足新問題的解。(2)預測推定型的類比學習 又分為傳統(tǒng)的類比法和因果關(guān)系型的類比兩種類型。第五節(jié) 類比學習 傳統(tǒng)類比法 傳統(tǒng)類比法可用來推斷一個不完全確定的事物可能還具有的其他屬性。因果關(guān)系型類比 因果關(guān)系型類比的基本問題是：已知因果關(guān)系S1:AB，給定事物 A與A相似，則可能有與B相似的事物B滿足因果

20、關(guān)系 S2:AB。進行類比的關(guān)鍵是匹配，實現(xiàn)匹配的常用方法：進行類比的關(guān)鍵是匹配，實現(xiàn)匹配的常用方法：進行類比的關(guān)鍵是匹配，實現(xiàn)匹配的常用方法：進行類比的關(guān)鍵是匹配，實現(xiàn)匹配的常用方法：等價匹配：兩個對象之間具有完全相同的特性數(shù)據(jù)。選擇匹配：選擇中特性進行匹配。規(guī)則匹配：規(guī)則的前提和結(jié)論都匹配，則規(guī)則匹配。啟發(fā)式匹配：通過抽象，在更高層次上進行匹配。第六節(jié) 解釋學習 一種分析學習方法?；舅枷耄夯舅枷耄夯舅枷耄夯舅枷耄和ㄟ^運用相關(guān)的領(lǐng)域知識，對當前提供的實例進行分析，從而構(gòu)造解釋并產(chǎn)生相應(yīng)的知識。已建立的系統(tǒng)，米切爾的LEX、LEAP；明頓的PRODIGY等。第六節(jié) 解釋學習一、基于解釋

21、學習的概念一、基于解釋學習的概念一、基于解釋學習的概念一、基于解釋學習的概念 通過運用相關(guān)的領(lǐng)域知識及一個訓練實例來對某個目標概念進行學習，并最終形成對這個概念的一般性描述。q米切爾關(guān)于解釋學習的一般框架米切爾關(guān)于解釋學習的一般框架米切爾關(guān)于解釋學習的一般框架米切爾關(guān)于解釋學習的一般框架給定：領(lǐng)域知識DT,目標概念TC,訓練實例TE,操作性準則OC。找出：滿足OC的關(guān)于TC的充分條件。第六節(jié) 解釋學習二、基于解釋學習的學習過程二、基于解釋學習的學習過程二、基于解釋學習的學習過程二、基于解釋學習的學習過程 1、構(gòu)造解釋 學習過程 2、獲取一般性知識1、構(gòu)造解釋 任務(wù)：任務(wù)：任務(wù)：任務(wù)：證明提供給

22、系統(tǒng)的訓練實例為什么是滿足目標概念的一個實例。證明過程通過運用領(lǐng)域知識進行演繹實現(xiàn)，證明的結(jié)果是得到一個解釋結(jié)構(gòu)。例如、設(shè)要學習的目標概念是“一個物體(Obj1)可以安全地放置在另一個物體(Obj2)上”，即 Safe-To-Stack(Obj1,Obj2)第六節(jié) 解釋學習第六節(jié) 解釋學習訓練實例為描述物體訓練實例為描述物體Obj1Obj1與與Obj2Obj2的事實的事實：On(Obj1,Obj2)Isa(Obj1,book-AI)Isa(Obj2,table-book)Volume(Obj1,1)Density(Obj1,0.1)第六節(jié) 解釋學習 領(lǐng)域知識是把一個物體放置在另一個物體上面的安

23、全領(lǐng)域知識是把一個物體放置在另一個物體上面的安全性準則：性準則：Fragile(y)Safe-To-Stack(x,y)Lighter(x,y)Safe-To-Stack(x,y)Volume(p,v)Density(p,d)*(v,d,w)Weight(p,w)Isa(p,table-book)Weight(p,15)Weight(p1,w1)Weight(p2,w2)smaller(w1,w2)Lighter(p1,p2)第六節(jié) 解釋學習證明過程：證明過程：Safe-To-Stack(Obj1,Obj2)Lighter(Obj1,Obj2)Weight(Obj1,0.1)Weight(Ob

24、j2,15)Smaller(0.1,15)Isa(Obj2,table-book)Volume(Obj1,1)Density(Obj1,0.1)*(1,0.1,0.1)第六節(jié) 解釋學習2 2、獲取一般性知識、獲取一般性知識、獲取一般性知識、獲取一般性知識 任務(wù)：任務(wù)：任務(wù)：任務(wù)：對解釋結(jié)構(gòu)進行一般化處理，從而得到關(guān)于目標概念的一般性知識。處理的方法處理的方法處理的方法處理的方法：通常是把常量代換為變量，并把某些不重要的信息去掉，只保留對以后求解問題所必須的關(guān)鍵信息。對上面的解釋結(jié)構(gòu)進行一般化處理可以得到一般的解釋結(jié)構(gòu)。第六節(jié) 解釋學習Safe-To-Stack(O1,O2)Lighter(O1

25、,O2)Weight(O1,w1)Weight(O2,15)Smaller(w1,15)Isa(O2,table-book)Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)第六節(jié) 解釋學習得到的一般知識：Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)Isa(O2,table-book)Smaller(w1,15)Safe-To-Stack(O1,O2)第六節(jié) 解釋學習三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性 由于領(lǐng)域知識可能不完善，因此會出現(xiàn)兩種極端情況：1、構(gòu)造不出解釋 2、構(gòu)造出多種解釋 解決

26、的根本方法：解決的根本方法：解決的根本方法：解決的根本方法：提供完善的領(lǐng)域知識。同時具有測試和修正不完善知識的能力。第七節(jié) 概念學習和一般到特殊序一、簡介一、簡介一、簡介一、簡介 問題：問題：問題：問題：給定一樣例集合以及每個樣例是否屬于某一概念的標注，怎樣自動推斷出該概念的一般定義。該問題被稱為概念學習，或稱為從樣例中逼近布爾函數(shù)。有怎樣的函數(shù)形式？輸入xi輸出yi=f(xi)概念學習：概念學習：概念學習：概念學習：概念學習是指從有關(guān)某個布爾函數(shù)的輸入輸出訓練樣例中推斷出該布爾函數(shù)。第七節(jié) 概念學習和一般到特殊序例子、例子、例子、例子、ExampleSkyAirTempHumidityWin

27、dWaterForestEnjoySport1234sunnysunnyRainysunnyWarmWarmColdWarmNormalHighHighHighStrongStrongStrongStrongWarmWarmWarmCoolSameSameSameChangeYesYesNoYes目標概念目標概念EnjoySport的正例和反例的正例和反例 學習的任務(wù)：學習的任務(wù)：學習的任務(wù)：學習的任務(wù)：基于某天的各屬性，以預測出該天EnjoySport的值。第七節(jié) 概念學習和一般到特殊序 設(shè)，實例各屬性的約束關(guān)系是合取關(guān)系，因此，希望歸納出形如 Sky=?Wind=?EnjoySport=Y

28、es的知識。如何歸納？如何歸納？如何歸納？如何歸納？屬性空間的描述(假設(shè)空間 H,用向量形式描述)一些約定的符號：由“?”表示本屬性可取任意值；由“”表示本屬性不接受任何值；由“c”表示待學習的目標概念。第七節(jié) 概念學習和一般到特殊序 如果某些示例x滿足假設(shè)h的所有約束，那么h將x分為類為正例(h(x)=1)，或反例(h(x)=0)。因此，假設(shè)可為下面形式的表達式 最一般的假設(shè)是G=，將所有的示例分類為正例。最特殊的假設(shè)是S=，將所有的示例分類為反例。因此，歸納的任務(wù)轉(zhuǎn)換為對假設(shè)空間的搜索問題，即，因此，歸納的任務(wù)轉(zhuǎn)換為對假設(shè)空間的搜索問題，即，因此，歸納的任務(wù)轉(zhuǎn)換為對假設(shè)空間的搜索問題，即，

29、因此，歸納的任務(wù)轉(zhuǎn)換為對假設(shè)空間的搜索問題，即，搜索能正確分類示例的一個假設(shè)或假設(shè)的集合搜索能正確分類示例的一個假設(shè)或假設(shè)的集合搜索能正確分類示例的一個假設(shè)或假設(shè)的集合搜索能正確分類示例的一個假設(shè)或假設(shè)的集合。第七節(jié) 概念學習和一般到特殊序q歸納學習的假設(shè)條件歸納學習的假設(shè)條件歸納學習的假設(shè)條件歸納學習的假設(shè)條件 任一假設(shè)如果能夠在足夠大的訓練樣例集合中很好地逼近目標函數(shù)，那么，它也能在未見的實例中很好地逼近目標函數(shù)。第七節(jié) 概念學習和一般到特殊序二、作為搜索的概念學習二、作為搜索的概念學習二、作為搜索的概念學習二、作為搜索的概念學習 概念學習可以看成是一個搜索過程，范圍是假設(shè)的表示所隱含定義

30、的整個空間。搜索的目標是尋找能很好地擬合訓練樣例的假設(shè)。1 1、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序 例子，兩個假設(shè) h1=h2=h2比h1的約束要少，因此，任何被h1劃分為正例的樣例，也將被h2劃分為正例。即h2比h1更一般。第七節(jié) 概念學習和一般到特殊序 定義：設(shè)hj和hk是兩個布爾函數(shù)，如果 (xX)hk(x)=1)(hj(x)=1)則稱hj比hk更一般(記為 hjghk)。這種序稱為偏序。第七節(jié) 概念學習和一般到特殊序2 2、Find-S:Find-S:搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè) 使用偏序關(guān)系搜索與訓練樣例

31、相一致的假設(shè)的一種方法是從假設(shè)空間H中最特殊的假設(shè)開始，然后在該假設(shè)覆蓋正例失敗時將其一般化。Find-SFind-S算法算法算法算法(1)將h初始化為H中最特殊的假設(shè)(2)對每個正例x 對h的每個屬性約束ai 如果x滿足ai，那么不做任何事 否則,將h中ai替換為x滿足的另一個更一般約束(3)輸出假設(shè)h第七節(jié) 概念學習和一般到特殊序例，用Find-S，學習EnjoySport。設(shè)(最特殊的假設(shè))，h=由示例1(正例)，修改h為：h=由示例2(正例)，修改h為：h=示例3(反例)，不修改h由示例4(正例)，修改h為：h=最后的輸出是：第七節(jié) 概念學習和一般到特殊序三、變型空間和侯選消除算法三、

32、變型空間和侯選消除算法三、變型空間和侯選消除算法三、變型空間和侯選消除算法 在Find-S算法中，找到的只是H中能夠滿足訓練樣例集合的多個假設(shè)中的一個。而在侯選消除算法中，輸出的是與訓練樣例一致的所有假設(shè)的集合。定義：一個假設(shè)h與訓練樣例集合D一致,當且僅當對D中的每一個樣例都有h(x)=c(x)。Consistent(h,D)=(D)h(x)=c(x)即，當一個假設(shè)能正確分類一組樣例時，稱為這個假設(shè)與這些樣例是一致的。第七節(jié) 概念學習和一般到特殊序 侯選消除算法能夠表示與訓練樣例一致的所有假設(shè)。在假設(shè)空間中的這一子集稱為關(guān)于假設(shè)空間H和訓練樣例D的變型空間。定義：關(guān)于假設(shè)空間H和訓練樣例D的

33、變型空間，標記為VSH,D，是H中與訓練樣例D一致的所有假設(shè)構(gòu)成的子集。VSH,D=hH|Consistent(h,D)第七節(jié) 概念學習和一般到特殊序1 1、列表后消除算法、列表后消除算法、列表后消除算法、列表后消除算法 表示變型空間的一種直觀方法是列出其所有的成員，通過檢測所有成員就可得到H和D的變型空間。列表后消除算法列表后消除算法列表后消除算法列表后消除算法(1)VersionSpace 包含H中所有假設(shè)的列表(2)對每個訓練樣例 從變型空間中移去所有h(x)c(x)的假設(shè)(3)輸出VersionSpace中的假設(shè)列表 原則上，只要假設(shè)空間是有限的，都可以使用該算法。原則上，只要假設(shè)空間

34、是有限的，都可以使用該算法。原則上，只要假設(shè)空間是有限的，都可以使用該算法。原則上，只要假設(shè)空間是有限的，都可以使用該算法。第七節(jié) 概念學習和一般到特殊序2 2、侯選消除算法、侯選消除算法、侯選消除算法、侯選消除算法變型空間的偏序表示：變型空間的偏序表示：變型空間的偏序表示：變型空間的偏序表示：只要能給出假設(shè)空間的極大一般成員G和極大特殊成員S，就可列出變型空間中的所有成員，其方法是使用偏序結(jié)構(gòu)來生成S和G集合之間的所有假設(shè)。第七節(jié) 概念學習和一般到特殊序侯選消除算法侯選消除算法侯選消除算法侯選消除算法 基本思想：基本思想：基本思想：基本思想：首先將G邊界集合初始化為H中的最一般假設(shè)：G0=，

35、將S邊界集合初始化為H中的最特殊假設(shè)：S0=；對每個訓練樣例進行處理時，S和G邊界被分別泛化和特殊化，從變型空間中逐步消除與樣例不一致的假設(shè)。在所有的樣例被處理完后，得到的變型空間就包含了所有與樣例一致的假設(shè)。第七節(jié) 概念學習和一般到特殊序侯選消除算法：侯選消除算法：侯選消除算法：侯選消除算法：將G集合初始化為H中極大一般假設(shè)將S集合初始化為H中極大特殊假設(shè)對每個訓練樣例d,進行下列操作：如果d是一個正例 從G中移去所有與d不一致的假設(shè) 對S中每個與d不一致的假設(shè)s 從S中移去s 把s的所有極小泛化式h加入到S中，其中h滿足 h與d一致，而且G的某個成員比h更一般 從S中移去這樣的假設(shè)：它比S

36、中另一假設(shè)更一般第七節(jié) 概念學習和一般到特殊序 如果d是一個反例 從S中移去所有與d不一致的假設(shè) 對G中每個與d不一致的假設(shè)g 從G中移去g 把g的所有極小特殊化式h加入到G中,其中h滿足 h與d一致，而且S的某個成員比h更特殊 從G中移去這樣的假設(shè)：它比G中另一假設(shè)更特殊第七節(jié) 概念學習和一般到特殊序例、學習“EnjoySport”S0:S1:S2:訓練樣例：1.,EnjoySport=Yes2.,EnjoySport=YesG0,G1,G2:第七節(jié) 概念學習和一般到特殊序S2,S3G2:,G3:訓練樣例：3.,EnjoySport=No 反例使G的邊界特殊化。在示例3中，由6個屬性可以使G

37、2特殊化，在此只有3個，因為其他3個不滿足示例1和示例2。第七節(jié) 概念學習和一般到特殊序S3S4,G3:,G4:訓練樣例：4.,EnjoySport=Yes第七節(jié) 概念學習和一般到特殊序最終的變型空間最終的變型空間最終的變型空間最終的變型空間S4,G4:,第七節(jié) 概念學習和一般到特殊序關(guān)于變型空間和侯選消除算法的說明：關(guān)于變型空間和侯選消除算法的說明：關(guān)于變型空間和侯選消除算法的說明：關(guān)于變型空間和侯選消除算法的說明：(1)由侯選消除算法得到變型空間能夠收斂到目標概念的假設(shè)條件是在訓練樣例中沒有錯誤；H中確實包含描述目標概念的正確假設(shè)。(2)侯選消除算法提取的是合取關(guān)系，如果是析取關(guān)系，則前面

38、的假設(shè)空間無法包含，因此，必須擴大假設(shè)空間，使每個可能的假設(shè)都包含在內(nèi)。(3)為了使侯選消除算法可以處理更大的假設(shè)空間，應(yīng)使用歸納偏置。歸納偏置就是在歸納時預先進行的某種假設(shè)。例如，侯選消除的歸納偏置是“目標概念包含在給定的H種”。第八節(jié) 決策樹學習 決策樹是一種逼近離散值函數(shù)的方法，對噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習析取表達式。決策樹的歸納偏置是優(yōu)先選擇較小的樹。第八節(jié) 決策樹學習一、決策樹表示法一、決策樹表示法一、決策樹表示法一、決策樹表示法OutlookSunnyOvercastRainHumidityHighNormalNoYesYesWindStrongWeakNoYes概念 Pla

39、y Tennis 的決策樹第八節(jié) 決策樹學習 通常決策樹代表實例屬性值約束的合取。從樹根到葉節(jié)點的每一條路徑對應(yīng)一組屬性測試的合取，樹本身代表這些合取的析取。例如，前面的決策樹代表 (Outlook=Sunny Humidity=Normal)(Outlook=overcast)(Outlook=RainWind=Weak)第八節(jié) 決策樹學習q決策樹學習的使用范圍決策樹學習的使用范圍決策樹學習的使用范圍決策樹學習的使用范圍(1)實例是由“屬性-值”對表示的(2)目標函數(shù)具有離散的輸出值(3)可能需要析取的描述(4)訓練數(shù)據(jù)中可能包含錯誤(5)訓練數(shù)據(jù)可以包含缺少屬性值的實例第八節(jié) 決策樹學習二

40、、基本的決策樹學習算法二、基本的決策樹學習算法二、基本的決策樹學習算法二、基本的決策樹學習算法 大多數(shù)決策樹學習算法是一種核心算法(ID3)的變形，該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。1、節(jié)點的選擇依據(jù) ID3算法的核心問題是選取在樹的每個節(jié)點要測試的屬性。ID3是選擇最有助于分類實例的屬性。定義定義定義定義(熵熵熵熵)：設(shè)S是包含某個目標概念的樣例集合，如果目標概念具有c個不同的屬性，那么S相對于c個狀態(tài)的分類的熵定義為：Entropy(S)=-pilog2pii=1c第八節(jié) 決策樹學習 定義定義定義定義(信息增益信息增益信息增益信息增益)：一個屬性A相對樣例集合S的信息增益定

41、義為：Gain(S,A)=Entropy(S)-Entropy(Sv)|Sv|S|vValue(A)其中，Value(A)是屬性A所有可能值的集合，Sv是S種屬性A為v的子集。第八節(jié) 決策樹學習例如、設(shè)S是一組有關(guān)天氣的訓練樣例，它的Wind屬性具有Weak和Strong兩個值。S包含14個樣例9+,5-。在正例中的6個和反例中的2個有 Wind=Weak，其他的是Wind=Stron。則 Values(Wind)=Weak,Strong S=9+,5-Sweak6+,2-Sstrong 3+,3-Gain(S,Wind)=E(S)-(8/14)E(Sweak)-(6/14)E(Sstrong

42、)=0.94 (8/14)0.811-(6/14)1.0 =0.048第八節(jié) 決策樹學習2、ID3算法 設(shè)，T_Attrs是該樹要測試的目標屬性，Attrs是除目標屬性外供學習到的決策樹測試的屬性列表。創(chuàng)建樹的Root節(jié)點 如果樣例都為正，則返回label=+的單節(jié)點樹Root 如果樣例都為反，則返回label=-的單節(jié)點樹Root 如果Attrs為空，則返回單節(jié)點樹，label=樣例中最普通的T_Attrs值 否則開始 AAttrs中分類樣例能力最好的屬性 Root的決策屬性A第八節(jié) 決策樹學習 對A的每個可能值vi 在Root下加一個新的分支對應(yīng)測試A=vi 令Examsvi為樣例中滿足屬

43、性A的值為vi的子集 如果為Examsvi空 在這個新分支下加一個葉節(jié)點,節(jié)點label=樣例 中最普遍的T_Attrs值 否則在這個新分支下加一個子樹ID3 (Examsvi，T_Attrs，Attrs A)結(jié)束 返回Root第八節(jié) 決策樹學習例子、PlayTennis訓練數(shù)據(jù)的ID3算法Day Outlook Temperature Humidity Wind PlayTennisD1D2D3D4D5D6D7D8D9D10D11D12D13D14SunnySunnyOvercastRainRainRainOvercastSunnySunnyRainSunnyOvercastOvercast

44、RainHotHotHotMildCoolCoolCoolMildCoolMildMildMildHotMildWeakStrongWeakWeakWeakStrongStrongWeakWeakWeakStrongStrongWeakStrongHighHighHighHighNormalNormalNormalHighNormalNormalNormalHighNormalHighNoNoYesYesYesNoYesNoYesYesYesYesYesNo第八節(jié) 決策樹學習確定根節(jié)點：確定根節(jié)點：確定根節(jié)點：確定根節(jié)點：有四個侯選屬性(Outlook,Temperature,Humidity

45、,Wind),計算每個侯選屬性信息增益：Gain(S,Outlook)=0.246 Gain(S,Terminature)=0.029 Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048因此，選擇OutLook為根節(jié)點。第八節(jié) 決策樹學習OutlookD1,D2,D149+,5-?SunnyD1,D2,D8,D9,D112+,3-OvercastD3,D7,D12,D134+,0-YesRainD4,D5,D6,D10,D143+,2-第八節(jié) 決策樹學習對“Sunny”分支：Ssunny=D1,D2,D8,D9,D11 Gain(Ssunny,Humidity)=0.97 Gain(Ssunny,Temperature)=0.57 Gain(Ssunny,Wind)=0.19所以，節(jié)點測試屬性為“Humidity”第八節(jié) 決策樹學習SunnyHumidityD1,D2,D8,D9,D11HighWeakStrongD1,D20+,2-NoD8,D91+,1-?D111+,0-Yes第八節(jié) 決策樹學習對“Weak”分支繼續(xù)D8,D91+,1-TemperatureMildCoolD80+,1-NoD91+,0-Yes