第二十一学习之中的知识.ppt

第二十一章 學習之中的知識,21.1 學習之中的知識21.2 以解說為基礎的學習21.3 使用關連資訊21.4 歸納邏輯程式化,21.1 學習之中的知識,邏輯特徵會有幫助的理由是對於欲學習之函數的部分資訊能提供很自然的定義方式。這就好像解題（problem-solving，對於狀態和目的採用“黑箱”的功能性觀點）和規劃（planning，打開黑箱並對狀態和行為採取邏輯描述）之間的分別。,這個對於歸納式學習的簡單描述持續到1980年代早期。現代的方法是設計已經具有某些知識、並試圖學得更多的代理人。這似乎並不是很了不起的真知卓見，但是對於寫程式的方法卻造成很大的不同。這也可能與科學本身如何運作的理論有關聯。大致的想法用圖解的方式呈現於圖21.1。,一些簡單的範例,想像一些用背景知識學習的常識作為範例。很多看似合理的推論行為案例，在實際觀察的時候顯然並未單純遵循純粹推論原則。有時候只經過一個觀察就突然產生一般結論。Gary Larson有一次畫了一部卡通，其中一個戴眼鏡的石器時代穴居人Zog在一根尖樹枝尾端烤他的蜥蜴。或是想像一個到巴西的旅行者遇到第一個巴西人。聽到巴西人說葡萄牙語時，旅行者立刻得到巴西人說葡萄牙語的結論，然而發現巴西人的名字是費南多，旅行者卻不會做出所有巴西人都叫做費南多的結論。,最後，想像一個對藥物學一無所知，卻對診斷很熟練的醫科學生觀察一位患者和專業內科醫師之間診療諮詢的例子。在一連串問題和回答之後，醫師告訴患者要採取連續的某種抗生素療程。,一些普遍的方法,在上述的每一項範例中，我們可訴諸先驗知識以嘗試評斷所選擇的歸納結果。現在要看作用在這些例子上的是那一種連帶限制。而那些限制除了會引用到“背景”知識，還會用到“假說”和可見的“描述”和“分類”。,21.2 以解說為基礎的學習,以解說為基礎的學習法是一種經由歸納觀察結果而獲得一般法則的方法。舉個例子，請想像微分與簡化的問題（習題10.4）。若微分一個與X相關的表示式，例如X2，則會得到2X。（請注意，大寫的字母表示數學式的未知數，用來與邏輯變數x作區別。）在邏輯推論系統中，目標可能表示成ASK(Derivative(X2,X)=d,KB)，答案為d=2X。,從範例中萃取一般化法則,EBL背後的基本觀念是先用先驗知識建構一個對於觀察所得的解釋，接著建立該類別範例的定義，使得能夠使用同樣的解釋結構。這個定義提供所涵蓋的類別中所有範例之法則的基礎。”解說”可能是一個邏輯證明，但更一般化的是它可以是任何明定義確之步驟的推論或解題程序。可依課本例子得知。,增進效率,檢視圖21.2的一般化證明樹，可看到從證明樹中能獲得不只一項一般化法則。例如，若當抵達Primitive步驟時，就終止或刪除右側分枝的成長，得到下列法則Primitive(z)Simplify(1(0+z),z)這項法則有相同效力，但比使用ArithmeticUnknown的法則更一般化，因為包含若z為數值的情況。,選擇要產生哪個法則的問題演變為效率的問題。要分析由EBL所得到的效率須涉及三項因素：1.增加大量法則到知識庫中可能使推論程序變慢，因為推論的機制仍必須檢查法則，即使那些法則並不能產生答案。換言之，這會增加搜尋空間的分支係數。2.為了彌補這項缺點，衍生法則對所涵蓋之範例必須有足夠的速率提昇。發生的原因主要是因為衍生法則免除可能走入死路的狀況，也因為縮短了證明。3.衍生法則必須儘可能一般化，以便能套用於最大的可能範例集合。,21.3 使用關連資訊,巴西的旅行者似乎能夠對其他巴西人所說的語言作出充滿自信的一般化概論。這項推論是由旅行者的背景知識所認定，亦即相同國家的人通常使用相同語言。我們可以用一階邏輯表達這項概念：x,y,n,l 國籍(x,n)國籍(y,n)語言(x,l)語言(y,l)(21.4)如同（21.4）這類的敘述句表現出關連性的精確形式：給定國籍，則可完全決定語言。換一種說法：語言是國籍的一個函數。這些敘述句稱為功能性依存（functional dependencies）或裁決（determinations），經常出現在很多種應用當中（例如，定義資料庫設計），使用特別的語法描寫。,決定假說空間,雖然裁決會認可關於所有巴西人的一般化結論，或是在給定溫度之下的所有銅片，但它們不能從單一範例就產生對所有國籍、或是所有溫度和材料的一般化預測理論。它們的主要影響可視為限制學習代理人所需考慮的假說空間。,學習並使用相關資訊,先驗知識在學習當中很有用，但也同樣需要學習。要對關連基礎學習提出完整的觀念，必須要為裁決提出一項學習演算法。現在所提出的學習演算法是以直接找出與觀察結果一致的最簡單裁決為基礎。一項裁決P Q表示若任一個範例符合P，則該範例也必然符合Q。由課本中的範例，基本演算法列於圖21.3。,圖21.4是兩個演算法對於一項函數隨機產生的資料之學習效能，而該函數只取決於16個屬性中的5個屬性。顯然，若是所有可得的參數皆互相關連，則RBDTL不會有任何改善。,21.4 歸納邏輯程式化,歸納邏輯程式（ILP）是AI中最新領域之一。結合了歸納方法和一階邏輯表示法的能力，特別集中在將理論以邏輯程式的方式表現出來。過去五年來，它已成為機器學習研究議程的主要部份。造成這種情況有原因有兩個。第一，它對於引言中提到的一般KBIL問題提供一項嚴謹的方法。第二，它提供一個完整的歸納一般化演算法，例如範例的一階理論，因此可在參數基礎演算法完全無效的領域中成功地學習。,一個範例,從等式（21.3）回想一般知識基礎歸納的問題，即是在給定”背景”知識和以”描述”及”分類”所敘述的範例時，解決未知“假說”的連帶限制 背景 假說 描述分類 為了說明，我們使用從範例中學習家人關係的問題。觀察結果會包含一個展開的家庭關係樹，用Mother、Father、和Married關係，以及Male和Female屬性做描述。(如課本P12-18)採用習題7.6的家庭關係樹，同時也以圖21.5表示。,反解（inverse resolution）,反解是基於觀察到若範例分類是由背景假說描述所推論之結果，則必然可從解答證明這項事實（因為解答完整）。若可以將證明的步驟倒轉，就能夠找出讓證明得以進行的假說。關鍵是找出反解程序的方法，使得證明可以倒轉進行。,產生反證,反證程序由個別的反向步驟所組成。一個普通的解答步驟採用兩個子句C1和C2，並藉由解答這兩個子句而產生解決方法（resolvent）C。一個反解步驟使用一個解決方法C並產生兩個子句C1和C2，因此C是解C1和C2的結果；或是用到C和C1並產生一個適合的C2。,反解程序的初期步驟表示於圖21.6，我們專注於正範例”Grandparent（George,Anne）”。程序在證明的結尾開始進行，亦即，用反證的方式倒推回去。,發現新述詞和新知識,一項反轉完整解答策略的反解程序大體上是一個學習一階理論的完整演算法。也就是說，若有一些未知的假說產生一個範例集合，則反解程序可由那些範例中產生假說。這項觀察隱含一個有趣的可能性。例如，假設可得到的範例中包含各種落體的軌道。,圖21.7表示在學習Ancestor的定義時產生新述詞P的範例。一旦P被產生，就可用於之後的反解步驟。例如，後來的步驟能假設Mother(x,y)P(x,y)。因此，新述詞P的意義受限於引用它的假設之產生。另一項範例會造成Father(x,y)P(x,y)的限制。,由上而下的學習方法,基本上第二個傾向LP發展的方法是一階狀況下的決策樹學習技術一般化。不再從觀察和反向處理開始，而從一個非常普遍的法則開始，並逐漸將其特殊化，使其能與資料一致。基本上這是決策樹學習所作的事，其中決策樹會逐漸成長直到與觀察結果一致。在一階的狀況下，使用一階的描述取代屬性，而且假說是以一個子句的集合取代決策樹。,假設嘗試學習一個Grandfather(x,y)述詞的定義，並使用與之前相同的一組資料。就像用決策樹學習，可將範例分解為正範例和負範例。正範例為,而負範例為,上述範例是FOIL如何運作的簡單描述。圖21.8是概略的完整演算法。本質上，該演算法重複地建構一個子句，文字接著文字，直到與正範例的一些子集合一致，並不與任何負範例一致。則該子句涵蓋的正範例可由訓練集合中刪除，這個程序持續直到沒有任何正範例留下。,