019 學習中的知識

Post date: 2013/4/9 下午 12:17:46

本章中我們研究當你已經知道某些東西時的學習問題

先驗知識(prior knowledge)

學習的邏輯形式

實例和假設

回憶一下第十八章中的餐館學習問題:學習用來決定是否等待座位的規則。實例用屬性(attributes)

描述,諸如 Alternate(改變),bar(酒吧),Fri/Sat(週五/週六)等等。在邏輯表示中,實例由邏輯語句所

描述;屬性則成為一元謂詞。

外延(extension)

不一致

錯誤反例

錯誤正例

當前最佳假設搜尋

當前最佳假設搜尋(current-best-hypothesis search)的想法是維護一個簡單的假設,並根據出現的

新實例對其進行調整,以維持一致性。

一般化

特殊化

丟棄條件(dropping conditions)

最少約定搜尋

當前最佳假設方法即使在資料不充分而對選擇沒有把握的時候,也必須選擇某個特定假設作為

最佳猜測,因而會產生回溯。替代地,我們可以只保存與目前已有的所有資料保持一致的全部假設。

每個新的實例若非不產生任何影響,則為去掉某些假設。

版本空間(version space,或變形空間),相對應的學習演算法(如圖19.3所示)被稱為版本空間學習演算法(也叫做替代消除演算法)。

邊界集

G-集

S-集

● 當前的版本空間是與到目前為止所有的實例都保持一致的假設的集合。他用 G-集和S-集表示,

每個邊界集都是一組假設集。

● S-集中的每個成員都與目前為止所有的觀察一致,並且不存在更特殊的一致假設。

● G-集中的每個成員都與目前為止所有的觀察一致,並且不存在更一般的一致假設。

更新S和G(函數VERSION-SPACE-UPDATE的工作)。根據定義,並輔以圖19.4,重新建構演算法。

考慮S-集和G-集中的成員Si和Gi。對於每個成員,新的實力可能是一個錯誤正例或者錯誤反例。

1. Si的錯誤正例:意味著Si 太一般化了,但是根據定義不存在 Si的一致的特殊化,所以我們把它從S-集中去掉。

2. Si的錯誤反例:意味著Si 太特殊化了,所以我們把它替換成所有對其進行的直接一般化,倘若他們比G中的某成員更特殊。

3. Gi的錯誤正例:意味著Gi太一般化了所以我們把它替換成所有對其進行的直接特殊化,倘若他們比S中的某成員更一般

4. Gi的錯誤反例:意味著Gi太特殊化了,但是根據定義不存在Gi的一致的一般化,所以我們把他從G-集中去掉。

我們持續對每個新的實例執行這些操作,直到下列3種情況之一發生:

1. 在版本空間中剛好剩下一個假設,這種情況下我們將他作為唯一假設返回;

2. 版本空間坍塌──S 或者 G 變為空集,顯示對訓練集合而言,沒有一致的假設。這與決策樹演

算法的簡單版本中的失敗情況相同。

3. 當我們用完全部實例後,在版本空間中還剩下多個假設。這意味著版本空間表示了假設的一個

析取式。對於任何新的實例,如果所有的析取子具意見都相同,則我們可以返回他們對該實例

的分類。如果不同,則一種可能方法是採用多數投票。

版本空間方法有幾個主要缺點:

● 如果領域中含有雜訊或對於精確分類有不充分的屬性,則版本空間(version space)恆將坍塌。

● 如果我們允許假設空間的無限析取式,那麼S-集將總是包含反例描述的析取式的負面表示。

● 對於某些假設空間來說,即使存在高效率的學習演算法,S-集和G-集中的元素個數仍然可能按

照屬性個數的指數級增長。

一般化層次結構

學習中的知識

前一節描述了歸納學習最簡單的背景。為了理解先驗知識的角色,我們需要談一談假設、實

例描述以及分類之間的邏輯關係。令 Descriptions(描述)表示所有訓練集中實例描述的聯集,

Classifications(分類)表示所有實例分類的聯集。那麼一個「解釋觀察事實」的Hypothesis(假設)就必

須滿足下面的屬性(回顧 |= 表示 「邏輯蘊涵」):

Hypothesis ^ Descriptions |= Classifications

蘊涵限制

一些簡單的例子

讓我們考慮一些根據背景知識進行學習的常識性例子。推理行為很多顯然合理情況在面對觀察

時很明顯不遵循純粹歸納的簡單原則。

● 有時人們只進行一次觀察之後就迅速地得到一個結論。Gary Larson 曾經畫過一個卡通片,其

中有一個帶著眼鏡的洞穴人 Zog 再用一根尖棍子的末端烤蜥蜴。一群與他同時代但沒他聰明的

人驚訝地觀察著他,他們一直自己徒手在火上烤食物。這種啟蒙式的經驗足以讓那些觀察者們

信服一條無痛亨飪的一般原則。

● 或者考慮一個去巴西的旅行者,他第一次遇到巴西人時的情況。聽到他在說葡萄牙語,他會立

即得出巴西人說葡萄雅語的結論;但是當知道他的名字是 Fernando 時,他卻不會得出所有巴西

人都叫 Fernando 的結論。

● 最後,考慮這樣的情況:一個不懂藥理但是精通診斷學的醫學院學生在觀察病人和內科專家之

間的諮詢過程。經過一系列的問答,專家告訴病人吃一個療程的某種特定的抗生素。這個醫學

院學生就會推論出一條一般規則:那種特定的抗生素對一種特定的感染有效。

這些都是「使用背景知識能夠使學習的速度遠快於用純歸納程式進行學習所期望達到的速度」的案例。

一般方案

在前面的每個例子中,人們可以求助於先驗知識來試著對選中的一般化結論進行判斷。我們現

在看看在每個例子中什麼類型的蘊涵限制可以起作用。在 Hypothesis(假設)和觀察到的

Descriptions(描述)與 Classifications(分類)之外,這些限制將會涉及到 Background(背景)知識。

在烤蜥蜴的例子中,洞穴人們透過解釋尖棍子的成功而進行一般化:他能夠在支撐蜥蜴的同時

保持手遠離火。透過這樣的解釋,他們能夠推斷出一般規則:任何長的、硬的、尖銳的物體可以被

用於烤小的、軟的食物。這種類型的一般化過程被稱為基於解釋的學習,或縮寫為EBL。注意一般

規則邏輯上遵循洞穴人們所擁有的背景知識。因此,被 EBL 滿足的蘊涵限制就是:

Hypothesis ^ Descriptions |= Classifications

Background |= Hypothesis

因為 EBL 使用公式 19.3 ,他最初被認為是一種從實例中進行學習的更好方法。

相關性

基於相關性的學習或縮寫為RBL

基於知識的歸納學習演算法或縮寫為KBIL

歸納邏輯程式設計或縮寫為ILP

在ILP系統中,先驗知識再降低學習複雜度上扮演了兩個重要角色:

1. 因為任何產生的假設必須同時與先驗知識和新的觀察都保持一致,所以有效假設空間的規模就

會減小,只包含那些與已知的知識一致的理論。

2. 對於任何給定觀察集合,建構對觀察的解釋所需要的假設規模可以減小很多,因為可以得到先

驗知識,幫助找出再對觀察的解釋過程中的新規則。假設越小,就越容易被找到。

基於解釋的學習

備忘法(memoization)

從實例中抽取一般規則

EBL背後的基本想法是首先使用先驗知識構造對觀察的一個解釋,然後建立一個針對能夠使用

相同的解釋結構的相同類型的定義。這個定義為涵蓋該類中所有情況的規則提供了基礎。「解釋」

可以是一個邏輯證明,但是更一般地,他是步驟定義明確的任何推理或問題求解過程。關鍵是能夠

明確把這些相同步驟應用於其他情況的必要條件。

重申一下,基本的 EBL 過程是如下進行的:

1. 給定一個實例,使用可用的背景知識,建構出一棵把目標謂詞應用於實例的證明。

2. 同時,使用與原始證明相同的推理步驟,為經過變形的目標構造一棵一般化證明樹。

3. 構造一條新的規則,其左側由證明樹的葉子節點組成,右側是經過變形的目標(在根據一般化證

明過程對變數進行必要的受限之後)。

4. 丟棄左側任何與目標中的變數取值完全無關的條件。

改進效率

圖19.7中的一般化證明樹實際上能夠產生不止一條一般規則。例如,如果當證明樹的右側分支

達到 Primitive 步驟的時候,我們就終止其生長,或稱剪枝(prune),那麼我們就得到規則:

Primitive(z) => Simplify(1 8 (0 + z), z)

這條規則與使用 ArithmeticUnknown 的規則一樣有效,但是更一般化,因為它可以涵蓋當 z 是一個數

字時的情況。我們可以在經過 Simplify(y + z,w)步驟之後透過剪枝抽取出一條甚至更一般的規則:

Simplify(y + z,w) => Simplify(1 * (y + z), w)

一般來說,從一般化證明樹的任何部分子樹上都可以抽取出一條規則來。現在我們面臨一個問題:

我們應該選擇其中哪條規則?

要選擇產生哪條規則其實取決於效率問題。從EBL得到的效率分析涉及 3 個因素:

1. 加入大量的規則會使推理過程減慢,因為推理機制即使在規則部會產生解的情況下仍然必須檢

查這些規則。換句話說,他增加了搜尋空間的分支因數。

2. 為了補償推理中的速度下降,那些產生的規則在處理他們能涵蓋的情況時必須顯著提高速度。

這些速度提高得以實作主要是因為產生的規則避免了其他情況下可能選取的死路,同時也因為

他們能夠縮短證明過程本身。

3. 產生的規則應該盡可能具有一般性,使得他們能夠用於各種情況的最大可能集合。

可操作性

使用相關資訊進行學習

我們的巴西旅行者看來能夠得到關於其他巴西人所使用語言的可靠的一般化。這個推理來自她

的背景知識,即一個給定國家中的人們(通常)說相同的語言。我們可以用一階邏輯把她表示如下:

Nationality(x,n)^Nationality(y,n) 交集 Language(x,l) => Language(y,l)

(字面翻譯:「如果x 和 y 有相同的國籍 n,而且 x 說的語言是l,那麼 y 說的語言也是 l 」)不難證明

,從語句和觀察

Nationality(Fernando,Brazil) 交集 Language(Fernando,Protuguese)

能夠蘊涵得到下面的結論:

Nationality(x,Brazil) => Language(x,Portuguese)

這些語句稱為函數依賴關係或稱決定關係

決定導電率和密度的相關屬性可以類似地表示為:

Material(x,m) 交集 Temperature(x,t) > Conductance(x,p);

Material(x,m) 交集 Temperature(x,t) > Density(x,d)

決定假設空間

儘管決定關係支援了關於所有巴西人或者給定溫度下所有銅塊的一般結論,但是他們當然無法

從單一實例中為所有國籍或所有溫度和材料產生一個一般性的預測理論。

學習和使用相關性資訊

我們在本章的介紹說過,先驗知識在學習中很有用,但是也必須經過學習。為了提供基於

相關性的學習的完整情況,我們同樣必須給出一個對於決定關係的學習演算法。

陳述性偏差

歸納邏輯程式設計

歸納邏輯程式設計(ILP)將歸納方法和一階表示的表達能力結合起來,特別集中於把假設表示為

邏輯程式。他之所以常用有 3 個原因。首先,ILP為一般基於知識的歸納學習問題提供了一種嚴格

的方法。其次,它提供了完備的演算法,從實例中歸納一般的一階理論,因此他可以在那些基於屬

性的演算法難於應用的場合中成功地完成學習。

一個例子

一般的基於知識的歸納問題就是「求解」如下蘊涵限制:

Background 交集 Hypothesis 交集 Descriptions |= Classifications

且求解是對未知的 Hypothesis(假設),並給定 Background(背景)知識及由 Descriptions(描述)與

Classifications(分類)所描述的實例。為了進一步說明,我們考察根據實例對家族關係進行學習的問題。

描述過程由一棵擴展的家族樹組成,按造Father(父)、Mother(母)與 Married(婚姻)關係以及

Male(男性)與Female(女性)屬性進行描述。

由上而下的歸納學習方法

ILP的第一種方法從一般的規則入手,逐步對其進行特殊化以使它能整合資料。這本質上就是

決策樹學習中發生的情況,其中決策樹是逐步成長的,直到與觀察結果相一致。要實作IPL,我們

選擇一階文字而不使用屬性特徵,並且用一組子句而不是決策樹表示假設。

使用逆向演繹的歸納學習

ILP中的第2種主要方法使用了普通演繹推理證明的逆過程。逆向歸結是基於這樣一個觀察事

實的:如果實例Classifications 是根據BackgroundHypothesisDescriptions得出的,那麼一定能夠透過

歸結解消證明這個事實(因為歸結是完備的)。如果我們可以「逆向執行證明過程」,就能找到證明過

程中的Hypothesis。那麼這裡的關鍵就在於找到逆轉歸結過程的途徑。

歸結式C

線性歸結

逆向蘊涵

透過歸納邏輯程式設計進行發現

逆向歸納過程將一個完整的歸納策略反其道而行,原理上,他是學習一階理論的一個完整演算法。

也就是說,如果某個未知的Hypothesis 產生了一組實例,那麼逆向歸納過程可以根據這些實例

產生 Hypothesis。這個現象提示了一個有趣的可能性:設想現成的實例中包含了落體的各種軌跡。

那麼逆向歸納程式是不是在理論上有能力推導出萬有引力定律呢?答案顯然是肯定的,因為在給定了

合適的數學背景知識之後,萬有引力定律可以用來解釋這些實例。類似地,可以想像電磁學、量子力學

和相對論都在ILP 程式的範疇內。當然,同樣也在猴子與印表機問題的範疇內。我們還需要更好的

啟發式演算法和新思維來構造搜尋空間。

總結

本章研究了各種使用先驗知識幫助代理人從新的經驗中進行學習的方法。因為很多先驗知識是

用關係模型而不是基於屬性的模型來表示的,所以我們也討論了一些允許對關係模型進行學習的系統。

要點為:

● 在學習中用先驗知識引導出累積學習的圖景,獲得更多知識時,學習代理人可改進其學習能力。

● 先驗知識透過去除其他一致假設以及「填充」實例的解釋來幫助學習,因此允許較短的假設。

這些貢獻的結果經常是能夠從更少的實例進行更快的學習。

● 對先驗知識扮演的不同邏輯角色加以理解,如同透過蘊涵限制表示的那樣,能夠幫助人們定義

各種學習技術。

基於解釋的學習(EBL)透過解釋實例並推廣其解釋,從單個實例中抽取一般規則。它提供了一種

演繹方法把第一原理知識轉變成有用的、高效率的、且專用的專門技術。

基於相關性的學習(RBL)以決定關係的形式使用先驗知識對相關屬性進行辨識,從而產生一個縮

減的假設空間並提高學習速度。RBL還允許從單個實例進行演繹的一般化。

基於知識的歸納學習(KBIL)在背景知識的幫助下尋找能解釋觀察集的歸納假設。

歸納邏輯程式設計(ILP)技術在用一階邏輯表達的知識的基礎上執行KBIL。ILP方法能夠學習在

基於屬性的系統中無法表達的關係知識。

● ILP 可透過改進一般規則由上而下的方法來完成,或透過逆向進行演繹過程的由下而上方法來完成。

● ILP 方法能夠自然地產生新的謂詞,用以表達簡潔的新理論,並表現出作為通用科學理論形式化系統的希望。