人工智能課件 －07機(jī)器學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

12、的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。與示例空間有關(guān)的主要問題是示例的質(zhì)量。“搜索”作用是從示例空間中查找所需的示例；“解釋”是從搜索到的示例中抽象出所需的有關(guān)信息供形成知識使用?！靶纬芍R”通過綜合、歸納等形式形成一般的知識。“驗(yàn)證”檢驗(yàn)所形成的知識的正確性。第四節(jié) 歸納學(xué)習(xí)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é) 歸納學(xué)習(xí)(2)舍棄條件 是把示例中的某些無關(guān)條件的子條件舍去。例如：花色(c1,C)點(diǎn)數(shù)(c1,2)花色(c2,C)點(diǎn)數(shù)(c2,4)花色(c3,C)點(diǎn)數(shù)(c3,6)花色(c4,C)點(diǎn)數(shù)(c4,2)同花(c1,c2,c3,c4)由于點(diǎn)數(shù)對形成“同花”概念無直接影響，則可把示例中的“點(diǎn)數(shù)”舍去。第四節(jié) 歸納學(xué)習(xí)(3)增加操作 有時需要通過增加操作來形成知識，常用的方法有前件析取法和內(nèi)部析取法。前件析取法：前件析取法：前件析取法：

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

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

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

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

18、似的論域：源域S和目標(biāo)域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é) 類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)主要包括四個過程(1)輸入一組已知條件(已解決的問題)和一組未完全確定的條件(新問題)；(2)對輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對應(yīng)關(guān)系；(3)根據(jù)相似變換的方法，將已解決的問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題的新知識；(4)對類比推理中得到的新知識進(jìn)行驗(yàn)證。第五

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

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

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

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

23、全領(lǐng)域知識是把一個物體放置在另一個物體上面的安全性準(zhǔn)則：性準(zhǔn)則：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é) 解釋學(xué)習(xí)證明過程：證明過程：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é) 解釋學(xué)習(xí)2 2、獲取一般性知識、獲取一般性知識、獲取一般性知識、獲取一般性知識 任務(wù)：任務(wù)：任務(wù)：任務(wù)：對解釋結(jié)構(gòu)進(jìn)行一般化處理，從而得到關(guān)于目標(biāo)概念的一般性知識。處理的方法處理的方法處理的方法處理的方法：通常是把常量代換為變量，并把某些不重要的信息去掉，只保留對以后求解問題所必須的關(guān)鍵信息。對上面的解釋結(jié)構(gòu)進(jìn)行一般化處理可以得到一般的解釋結(jié)構(gòu)。第六節(jié) 解釋學(xué)習(xí)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é) 解釋學(xué)習(xí)得到的一般知識：Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)Isa(O2,table-book)Smaller(w1,15)Safe-To-Stack(O1,O2)第六節(jié) 解釋學(xué)習(xí)三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性三、領(lǐng)域知識的完善性 由于領(lǐng)域知識可能不完善，因此會出現(xiàn)兩種極端情況：1、構(gòu)造不出解釋 2、構(gòu)造出多種解釋 解決

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

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

28、es的知識。如何歸納？如何歸納？如何歸納？如何歸納？屬性空間的描述(假設(shè)空間 H,用向量形式描述)一些約定的符號：由“?”表示本屬性可取任意值；由“”表示本屬性不接受任何值；由“c”表示待學(xué)習(xí)的目標(biāo)概念。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 如果某些示例x滿足假設(shè)h的所有約束，那么h將x分為類為正例(h(x)=1)，或反例(h(x)=0)。因此，假設(shè)可為下面形式的表達(dá)式 最一般的假設(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é) 概念學(xué)習(xí)和一般到特殊序q歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣例集合中很好地逼近目標(biāo)函數(shù)，那么，它也能在未見的實(shí)例中很好地逼近目標(biāo)函數(shù)。第七節(jié) 概念學(xué)習(xí)和一般到特殊序二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí) 概念學(xué)習(xí)可以看成是一個搜索過程，范圍是假設(shè)的表示所隱含定義

30、的整個空間。搜索的目標(biāo)是尋找能很好地?cái)M合訓(xùn)練樣例的假設(shè)。1 1、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序 例子，兩個假設(shè) h1=h2=h2比h1的約束要少，因此，任何被h1劃分為正例的樣例，也將被h2劃分為正例。即h2比h1更一般。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 定義：設(shè)hj和hk是兩個布爾函數(shù)，如果 (xX)hk(x)=1)(hj(x)=1)則稱hj比hk更一般(記為 hjghk)。這種序稱為偏序。第七節(jié) 概念學(xué)習(xí)和一般到特殊序2 2、Find-S:Find-S:搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè) 使用偏序關(guān)系搜索與訓(xù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é) 概念學(xué)習(xí)和一般到特殊序例，用Find-S，學(xué)習(xí)EnjoySport。設(shè)(最特殊的假設(shè))，h=由示例1(正例)，修改h為：h=由示例2(正例)，修改h為：h=示例3(反例)，不修改h由示例4(正例)，修改h為：h=最后的輸出是：第七節(jié) 概念學(xué)習(xí)和一般到特殊序三、變型空間和侯選消除算法三、

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

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

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

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

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

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

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

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

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

41、義為：Gain(S,A)=Entropy(S)-Entropy(Sv)|Sv|S|vValue(A)其中，Value(A)是屬性A所有可能值的集合，Sv是S種屬性A為v的子集。第八節(jié) 決策樹學(xué)習(xí)例如、設(shè)S是一組有關(guān)天氣的訓(xù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é) 決策樹學(xué)習(xí)2、ID3算法 設(shè)，T_Attrs是該樹要測試的目標(biāo)屬性，Attrs是除目標(biāo)屬性外供學(xué)習(xí)到的決策樹測試的屬性列表。創(chuàng)建樹的Root節(jié)點(diǎn) 如果樣例都為正，則返回label=+的單節(jié)點(diǎn)樹Root 如果樣例都為反，則返回label=-的單節(jié)點(diǎn)樹Root 如果Attrs為空，則返回單節(jié)點(diǎn)樹，label=樣例中最普通的T_Attrs值 否則開始 AAttrs中分類樣例能力最好的屬性 Root的決策屬性A第八節(jié) 決策樹學(xué)習(xí) 對A的每個可能值vi 在Root下加一個新的分支對應(yīng)測試A=vi 令Examsvi為樣例中滿足屬

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

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

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