第十八章经由观察而学习精品课件.ppt

第十八章第十八章經由觀察而學習經由觀察而學習18.1學習性代理人的通用模型18.2歸納學習法18.3決策樹的學習18.4使用資訊理論18.5學習通用的邏輯表述18.6為何學習可行：計算學習理論18.1學習性代理人的通用模型學習性代理人的通用模型一個具有學習特性的代理人，在概念上可分解為如圖18.1所示的四項元件。其中最重要的是區分負責改善內部效能的學習元素學習元素，和負責選擇外在行動的效能元素效能元素。之前被當成是完整代理人的部份即是一個效能元素；它能取得認知並決定行動。學習元素的設計受到四項主要關鍵問題的影響：效能元素的哪一個元件需要改善。效能元素的哪一個元件需要改善。這些元件使用什麼描述方法。這些元件使用什麼描述方法。能得到哪些回饋。能得到哪些回饋。能得到哪些先驗資訊。能得到哪些先驗資訊。元件的表示方法元件的表示方法 這些元件中的任何一種都可以用本書介紹的表示法表示。已有許多個例子：決定性敘述法，例如競局程式中效能函數的線性加權多項式，和邏輯代理人各元件的比例項（proportional）與一階邏輯敘述；以及機率描述，例如用於決策理論代理人推論元件的信念網路。有用的回饋（有用的回饋（availablefeedback）對一些例如預測行動結果的元件而言，有用的回饋通常能告知代理人何者是正確的結果。亦即，代理人預測特定行動（煞車）將有特定的結果（在10呎內停住），而環境立刻提供一個描述實際正確結果的認知（在15呎內停止）。任何可察覺元件輸出與輸入情況的環境就稱為監督式學習（supervisedlearning）。先驗知識先驗知識 大部分AI、計算機科學、以及心裡學中的學習研究，都曾研究過這樣的例子：代理人從不具有任何它想學習的知識開始，只具有由經驗獲得其所呈現之例子的方法。雖然這是重要的特例，對一般情況而言卻不一定如此。大部分的人類學習都發生在有充足背景知識的情況下。總結總結效能元素的七個元件，任一個都可以用數學方法描述成一個函數：例如，相關於環境進化方法的資訊可被描述為從一個環境狀態（目前狀態）到另一個環境狀態（下一個或多個狀態）的函數；一個目標可被描述為從一個狀態到一個布林值（0或1），表示該狀態是否滿足目標的函數。重點是，所有的學習都可被視為學習一個函數的表示法。18.2歸納學習法歸納學習法 在控制學習之中，學習元素被給定對應於特定輸入的函數正確（或幾近正確）值，並嘗試改變函數的表示法以符合回饋所提供的資訊。更正式的說法為，一個範例是一組（x,f(x)），其中x是輸入，而f(x)是套用x時該函數的輸出。在圖18.2(c)則有一個更複雜的h函數。兩個函數的範例點一致，但若給予其他x作為輸入，則兩者的y值不同。在(d)之中有一個函數故意忽略範例點中的一個，但用簡單函數就可以符合其他的點。因為不知道真正的f，因此對h有很多選擇，但也因為沒有進一步的知識，就沒有理由偏好(b)，(c)，或(d)。任何對於一項假說的偏好超越了與範例的一致性，就稱為一項偏見偏見（bias）。回到關於代理人的討論，假設有一個被教師教導的反射代理人。圖18.3的例子顯示出REFLEX-LEARNING-ELEMENT會更新擁有一序對（percept,action）的全域變數。該項認知可能是棋盤上的位置，而動作可能是由圍棋高手所決定的最佳棋步。本章討論兩種邏輯敘述句的學習方法：決策樹決策樹法（decisiontree）使用專為學習而明確設計的有限制邏輯敘述句表示法；版本空間版本空間法（version-space）較為普遍，但經常很缺乏效率。第19章將討論類神經網路類神經網路（neuralnetworks），是非線性數值函數的一般表示法。競局評估函數所使用的線性加權多項式是類神經網路的一項特例。18.3決策樹的學習決策樹的學習 決策樹歸納法是最簡單，也是最成功的學習演算法形式之一。不僅是進入歸納式學習法領域一項很好的介紹，同時也易於實行。本節首先談論效能元素，然後說明如何學習它。以決策樹作為效能元素以決策樹作為效能元素 一個決策樹的輸入是一個由屬性的集合所描述的物件或狀態，輸出則是一個”是”或”不是”的決策。因此決策樹是一個布林函數。雖然決策樹也可以描述輸出範圍較大的函數，但為了簡化，通常只注意布林的狀況。決策樹的表示法 若決策樹對應於關聯敘述句的集合，一個基本的問題是：決策樹能否表現任何集合。答案是否，因為決策樹隱然受到無法敘述單一物件的限制。也就是說，決策樹的語言基本上是命題式的，其中每個屬性的測試都是一個命題。我們無法使用決策樹表達用到兩個以上不同物件的測試，例如，r2Nearby(r2,r)Price(r,p)Price(r2,p2)Cheaper(p2,p)由範例歸納決策樹由範例歸納決策樹 範例範例（example）是由屬性的值和目的述詞所描述。目的述詞的值被稱為該範例的類別類別（classification）。若目的述詞對某些範例成立，則稱這是一個正範例正範例（positive）；否則稱為負負範例範例（negative）。一個餐廳領域的範例集合X1,X12展示於圖18.5。正範例是目的WillWait的值（X1,X3,）為真，而負範例則是（X2,X5,）為偽。完整的範例集合被稱為訓練集合訓練集合（trainingset）。找尋一個與訓練集合一致的決策樹似乎有點困難，實際上卻存在一個簡單解。可以單純地建立一棵決策樹，對於每個範例都有一條到達葉節點的路徑與之對應，該路徑依序測試每個屬性，並遵循該範例的值，而葉節點擁有該範例的類別。當再次被給予同樣的範例，決策樹將可給出正確的類別。圖18.6表示該演算法如何開始。已知12個訓練範例，被分類為正副兩個集合。接著決定使用哪個屬性作為決策樹的第一項測試。圖18.6(a)表現出Patrons是很重要的屬性，因為若Patrons的值為None或Some，則需要處理能被確定回答的範例集合（分別是No和Yes）。（若值為Full，就需要額外的測試。）繼續套用DECISION-TREE-LEARNING演算法（圖18.7），直到獲得圖18.8的樹。這棵樹與原來顯示於圖18.4的樹很明顯不同，儘管實際上那些資料確實都是由使用原來那棵樹的代理人所產生。評估學習演算法的效能評估學習演算法的效能 若一項學習演算法所產生的假說在預測不可見範例（unseenexample）的分類表現良好，則稱其為良好的演算法。第18.6節將可看到如何預估學習演算法做預測的品質。現在將檢視一項在事實發生後評估預測品質的方法。若使用所有可得的範例作訓練，則必須再取得更多的範例以作測試，因此通常採用下列方法會更方便：1.收集一個大量範例的集合。2.將該集合分割為沒有交集的兩個集合：訓訓練練集集合合和測試集合測試集合。3.使用學習演算法和訓練集合作為範例以產生一個假說。4.量測測試集合中能被正確分類的範例比例。5.對不同大小的訓練集合，以及隨機選擇的各種大小的訓練集合重複步驟到。決策樹學習法實務決策樹學習法實務 決策樹為成比例的知識提供一個簡單的表示法，可用於作決策，並將物件分類。雖然決策樹學習法因為其表述方式的限制而不能產生有趣的科學理論，卻已被廣泛地應用於各方面。鑽油平台設備之設計鑽油平台設備之設計 1986年，BP部署一個稱為GASOIL的專家系統，用於近海鑽油平台的油氣分離（將瓦斯與石油分離）系統之設計。油氣分離是在礦源用一個非常巨大、複雜、且昂貴的分離系統完成，需要根據多項屬性作設計，包括瓦斯、石油、和水的相對比例，流速，壓力，密度，黏度，溫度，以及對於月亮週期的敏感度。當時，GASOIL是世界上最大的商用專家系統，包含將近2500項規則。人工製作這樣一個系統大約需要花費10人年的時間。將決策樹學習法套用到既有的設計資料庫，用100人天（Michie,1986）就開發出這套系統。學習飛行學習飛行 為一個複雜的系統設計自動控制有兩種方法。一種是為系統的變動過程建立一個精確的模型，並使用多種正規（包括AI規劃法）方法之一設計一個有若干確定特性之控制器。或者，可以單純地學習從系統狀態到正確行動的正確對應。18.4使用資訊理論使用資訊理論 用於決策樹學習以選擇屬性的方針，被設計成讓最終產生的樹深度為最小。觀念是選擇到目前為止，看起來有可能成能為範例提供正確分類的屬性。一項完美的屬性將範例分成皆為正或皆為負的集合。雜訊與過當雜訊與過當 前面曾看到若有兩個或多個範例有相同的描述（用屬性描述），但卻有不同的分類，則DECISION-TREE-LEARNING演算法必然無法找到一個能與所有範例一致的決策樹。之前提到的解法是讓每個葉節點回報其範例集合的多數分類，或是回報每個分類的評估機率，並使用相對發生的次數做評估。前者適用於要求決策樹表現精確邏輯函數的代理人，後者則用於決策理論代理人。擴大決策樹的適用性擴大決策樹的適用性 為了將決策樹歸納法擴展到更廣泛而多樣的問題，必須提出一些考量。以下將對每一項作簡單的介紹，建議可經由作相關的習題以獲得完整的了解：失落的資料（Missingdata）多元值的屬性（Multivaluedattributes）有連續值的屬性（Continuous-valuedattributes）18.5學習通用的邏輯表述學習通用的邏輯表述 藉以學習更多普遍型態的邏輯描述。過程中，將會建立一個通用的框架以了解學習演算法，框架的建立是根據將歸納學習視為一個在大空間中尋找良好假說的中心觀念假說空間（hypothesisspace）-由該項工作所選定的表示語言所定義。假說假說 通常的狀況是：從目標預測開始，通稱為。（例如，在餐廳領域中，就是WillWait。）會是個一元（unary）預測，且我們試圖找出一個相等的邏輯表示法，可用來對範例作正確分類。每個假說提出一個這樣的表述，稱為目標預測的候選定義候選定義（candidatedefinition），例如，圖18.8的決策樹表示下列邏輯定義。範例範例 就邏輯而言，一個範例是一個能或不能套用目標概念的物件，並且有一些邏輯表述。通稱第i個範例為Xi。其表述是敘述句Di(Xi)，其中Di可以是任何有單一參數的邏輯表示式。若範例為正，則以敘述句Q(Xi)表示分類，並以Q(Xi)表示範例為負。例如，圖18.5的第一個範例。目前最佳假說搜尋目前最佳假說搜尋(Current-best-hypothesissearch)目前最佳假說搜尋根據的觀念是維護單一假說，並在新範例到達時調整假說，以維護一致性。基本演算法由JohnStuartMill（1843）所述，而且可能更早的時候就出現了。設有一些假說，例如Hr，使我們盲目地成長。只要每個新範例一致，就不需要什麼了。接著一個偽負範例X13發生，我們怎麼做？圖18.10(a)用圖表的方式將Hr表示為區域：矩形內的任何東西都是Hr延伸的一部分。實際上已看到的範例被表示為”+”或”-“，而且可以發現Hr將所有範例正確歸類成WillWait的正或負範例。現在可以定義CURRENT-BEST-LEARNING演算法，如圖18.11所示。請注意每次考慮要將假說一般化或特殊化，就必須檢查與其他範例的一致性，因為不保證一個延伸的任意加大或縮小能避免包含或排除任何其他負或正的範例。最少約束搜尋最少約束搜尋 需要回溯是因為目前最佳假說方法必須選擇一個特定的假說作為最佳猜測，即使還沒有足夠的資料能確定該項選擇。所能採取的替代做法是保持原狀，只除了目前為止與所有資料一致的那些假說。每個新的實例若非不造成任何影響，就是會刪除一些假說。剩餘假說的集合被稱為版本空間版本空間（versionspace），而學習演算法（在圖18.12）被稱為版本空間學習演算法（也稱為候選削去候選削去(candidateelimination)演算法）。圖18.13是版本空間範圍集合表示法的一般結構。為了指出表示法是充足的，需要下列兩項特性：1.每個一致的假說（除了在範圍集合中的假說）都比G集合的一些成員更明確，且比S集合的成員更一般化。2.每個假說若比G集合的成員更明確，且比S集合的成員更一般化，則為一個一致性的假說。圖18.14表示這樣的狀況：沒有任何已知範例存在於S之外，但卻又存在於G之內，因此任何間隔中的假說必然一致。討論討論 版本空間的方法有兩項根本的缺點：1.若領域中包含雜訊，或實際分類的屬性不充足，版本空間必然會崩塌。2.若允許假說空間無限制分離，則S集合一定會包含單一的最明確假說，亦即，截至目前正範例描述中可分解的部分。同樣地，G集合恰好包含負範例描述之分解的否定。18.6為何學習可行：計算學習理論為何學習可行：計算學習理論 學習代表表現得更好是經驗所造成的。之前已看到多種推論學習的演算法，並解釋過為何能適用於代理人。基本原則如下：任何嚴重錯誤的假說幾乎在少量的範例之後必會有很高的機率被發現，因為它會造成不正確的預測。因此，任何與相當大的訓練集合一致的假說似乎不可能會有嚴重錯誤也就是說，其必然十之八九逼近正確（ProbablyApproximatelyCorrect）。圖18.15指出所有假說的集合H，分割為環繞f和其餘函數的-球，稱為Hbad。決策串列的學習決策串列的學習 一個決策串列（decisionlist）是一種限制形態的邏輯表示法。決策串列由一系列測試所組成，其中每一項都是文字的聯結。圖18.16顯示一個表現假說H4的決策串列，由之前的CURRENT-BEST-LEARNING演算法所獲得：xWillWait(x)Patrons(x,Some)(Patrons(x,Full)Fri/Sat(x)我們將使用一個稱為DECISION-LIST-LEARNING的貪婪演算法，可重複地找出一項恰與訓練集合中某些子集合一致的測試。一旦找出這樣的一項測試，就將它加入建構中的決策串列，並移除相關的範例。接著用剩下的範例建構其餘的決策串列。這個程序一直重複，直到沒有範例剩下。演算法列於圖18.17。圖 18.18這 張 圖 表 示 DECISION-LIST-LEARNING演算法對餐廳資料的預測效能，是可 見 範 例 數 量 的 函 數。DECISION-LIST-LEARNING的曲線被列出作為比較。討論討論計算學習理論以產生一種檢視學習問題的新方法。在1960年代早期，學習理論專注於有限制的確認（identificationinthelimit）。確認演算法必須傳回一個確實符合真值函數的假說。標準方法是結合目前最佳假說和版本空間的方法：目前最佳假說是假說空間在某種固定的簡化順序下，第一個一致性假說。