1、2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,1,機器學習,第12章 歸納和分析學習的結(jié)合,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,2,概述,純粹的歸納學習方法通過在訓練樣例中尋找經(jīng)驗化的規(guī)律來形成一般假設(shè) 純粹的分析方法使用先驗知識演繹推導一般假設(shè) 本章考慮將歸納和分析的機制結(jié)合起來的方法，并獲得兩者的優(yōu)點：有先驗知識時獲得更高的泛化精度和依賴訓練數(shù)據(jù)克服先驗知識的不足 所得到的結(jié)合的方法比純粹的歸納方法和分析方法的性能都要高,2003.12.18,機器學習-歸納

2、和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,3,動機,歸納學習尋找擬合訓練數(shù)據(jù)的一般假設(shè)，分析學習尋找擬合先驗知識的一般假設(shè)，同時使它覆蓋訓練數(shù)據(jù) 歸納方法和分析方法對假設(shè)的論證方法有根本區(qū)別，因此優(yōu)缺點互為補充，將它們結(jié)合起來有可能得到更強有力的學習方法 純粹的分析學習方法的優(yōu)缺點 優(yōu)點：可用先驗知識從較少的數(shù)據(jù)中更精確地泛化以引導學習 缺點：當先驗知識不足或不正確時，可能產(chǎn)生誤導 純粹的歸納學習方法的優(yōu)缺點 優(yōu)點：不需要顯示的先驗知識，主要基于訓練數(shù)據(jù)學習規(guī)律 缺點：訓練數(shù)據(jù)不足時，會失敗，會被其中隱式的歸納偏置所誤導,2003.12.18,機器學習-歸納和分析

3、學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,4,表12-1 純粹的分析學習和純粹的歸納學習的比較,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,5,動機（2）,圖12-1 概述了學習問題的分布范圍，它隨著可獲得的先驗知識和訓練數(shù)據(jù)不同而變化 在一個極端，有大量的訓練數(shù)據(jù)，但沒有先驗知識 在另一個極端，有很強的先驗知識，但訓練數(shù)據(jù)很少 多數(shù)實際學習問題位于這兩個極端之間，通?？梢詮慕频南闰炛R開始 本章考慮的問題是： 什么樣的算法，使用近似的先驗知識結(jié)合可用數(shù)據(jù)來形成一般的假設(shè),2003.12.18,機器學習-

4、歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,6,動機（3）,即使使用最純粹的歸納學習算法，仍有機會基于特定學習任務(wù)的先驗知識來選擇設(shè)計方案 通常設(shè)計者將領(lǐng)域特定的知識嵌入到學習算法中，但我們感興趣的是一個系統(tǒng)能將先驗知識和訓練數(shù)據(jù)作為顯示的輸入給學習器 概括而言，我們感興趣的是領(lǐng)域無關(guān)算法，這種算法使用顯示輸入的領(lǐng)域相關(guān)的知識，這種算法具備以下的屬性： 如果沒有領(lǐng)域理論，它至少能像純粹的歸納方法一樣有效學習 如果沒有完美的領(lǐng)域理論，它至少能像純粹的分析方法一樣有效學習 如果領(lǐng)域理論和訓練數(shù)據(jù)都不完美，它應(yīng)能結(jié)合兩者的長處，比單純的歸納或分析方法的性能要好 它應(yīng)能

5、處理訓練數(shù)據(jù)中未知程度的差錯 它應(yīng)能處理領(lǐng)域理論中未知程度的差錯 這里列出的期望目標很難達到，目前沒有算法能以一般化的方式滿足所有這些約束,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,7,學習的歸納-分析途徑,本章考慮的學習問題 已知 一個訓練樣例集合D，可能包含差錯 一個領(lǐng)域理論B，可能包含差錯 候選假設(shè)的空間H 求解 一個最好地擬合訓練樣例和領(lǐng)域理論的假設(shè) 最好地擬合訓練樣例和領(lǐng)域理論的確切定義,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,8,學習的歸納-分析途徑

6、（2）,確定先驗知識和數(shù)據(jù)權(quán)值的一種解決方法是使用貝葉斯觀點 貝葉斯定律描述了怎樣計算給定訓練數(shù)據(jù)D時假設(shè)h的后驗概率 貝葉斯定律基于觀察到的數(shù)據(jù)D以及先驗知識計算后驗概率，以P(h), P(D)和P(D|h)的形式表示 我們可以把P(h), P(D)和P(D|h)看作是某種形式的背景知識 貝葉斯理論可看作一種為領(lǐng)域理論加權(quán)的方法，它與觀察到的數(shù)據(jù)D一起，賦予h的后驗概率為P(h|D) 貝葉斯公式提供了為先驗知識和觀察到數(shù)據(jù)的貢獻加權(quán)的方法 但是，貝葉斯公式隱含假定了關(guān)于P(h), P(D), P(D|h)概率分布的完美知識 貝葉斯公式?jīng)]有提供將這些近似已知的概率分布與觀察數(shù)據(jù)結(jié)合起來的方法,

7、2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,9,假設(shè)空間搜索,大多數(shù)學習任務(wù)可以刻畫為假設(shè)空間上的搜索任務(wù),而決定這個搜索任務(wù)的4個參數(shù)是： 假設(shè)空間H 搜索的初始假設(shè)h0 定義單個搜索步的搜索算子集合O 指定搜索目標的判據(jù)G 本章探索了3種方法，它們用先驗知識來改變純歸納方法執(zhí)行的搜索 使用先驗知識推導出搜索起步的初始假設(shè)：Kbann 使用先驗知識來改變假設(shè)空間搜索的目標：Ebnn 使用先驗知識改變可用的搜索步：Focl,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,

8、10,使用先驗知識得到的初始假設(shè),KBANN技術(shù)：一種使用先驗知識的方法是將假設(shè)初始化為完美擬合領(lǐng)域理論，然后按照需要歸納地精化初始假設(shè)以擬合訓練數(shù)據(jù) 這種技術(shù)的動機是：如果領(lǐng)域理論是正確的，初始假設(shè)將正確分類所有訓練樣例，而無需再修正；如果初始假設(shè)不能完美地分類訓練樣例，那么它需要被歸納精華，以改進它在訓練樣例上的擬合度 在純粹歸納的反向傳播算法中，權(quán)值一般被初始化為小的隨機值，KBANN的含義是：即使領(lǐng)域理論是近似正確的，將網(wǎng)絡(luò)初始化為擬合領(lǐng)域理論，比初始化為隨機值有更好的近似開端,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,

9、11,KBANN算法,KBANN假定領(lǐng)域理論用一組命題形式的非遞歸的Horn子句來表示，輸入和輸出如下： 已知： 一組訓練樣例 由非遞歸命題型Horn子句組成的領(lǐng)域理論 求解： 一個擬合訓練樣例的被領(lǐng)域理論偏置的人工神經(jīng)網(wǎng)絡(luò) KBANN算法包含兩個階段 創(chuàng)建一個完美擬合領(lǐng)域理論的人工神經(jīng)網(wǎng)絡(luò) 使用反向傳播算法來精化初始網(wǎng)絡(luò)以擬合訓練樣例,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,12,表12-2 KBANN算法,KBANN(Domain_Theory, Training_Examples) Domain_Theory：非遞歸命題

10、型Horn子句集 Training_Examples：目標函數(shù)的對的集合 分析步：創(chuàng)建一個等價于領(lǐng)域理論的初始網(wǎng)絡(luò) 對每個實例屬性創(chuàng)建一個網(wǎng)絡(luò)輸入 對Domain_Theory的每個Horn子句，創(chuàng)建如下的網(wǎng)絡(luò)單元 連接此單元的輸入到此子句的先行詞測試的屬性 對子句的每個非負先行詞，賦予權(quán)值W給對應(yīng)的sigmoid單元輸入 對子句的每個負先行詞，賦予權(quán)值-W給對應(yīng)的sigmoid單元輸入 設(shè)置此單元的閾值w0為-(n-0.5)W，其中n為子句的非負先行詞的數(shù)目 在網(wǎng)絡(luò)單元之間增加附加的連接，連接深度為i的每個網(wǎng)絡(luò)單元到深度為i+1的所有網(wǎng)絡(luò)單元的輸入層上，賦予這些附加的連接為接近0的隨機權(quán)值

11、歸納步：精化此初始網(wǎng)絡(luò) 應(yīng)用反向傳播算法來調(diào)整初始網(wǎng)絡(luò)權(quán)值以擬合Training_Examples,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,13,舉例,表12-3 Cup學習任務(wù) 領(lǐng)域理論 訓練樣例 在KBANN算法的第一步，構(gòu)建一個與領(lǐng)域理論一致的初始網(wǎng)絡(luò)，見圖12-2 對領(lǐng)域理論中每個Horn子句建立一個sigmoid單元 對該Horn子句的每個先行詞，建立其對應(yīng)的Sigmoid單元作為輸入 對于每個對應(yīng)于非負先行詞的輸入，權(quán)值被設(shè)置為某正常量W，對每個對應(yīng)于負先行詞的輸入，權(quán)值為-W 單元的閾值權(quán)w0設(shè)為-(n-0.5)

12、W，其中n為非負先行詞的數(shù)目 附加許多輸入到每個閾值單元，它們的權(quán)值設(shè)置為近似0，從而允許網(wǎng)絡(luò)能夠?qū)W習到超出領(lǐng)域理論的依賴關(guān)系 在KBANN算法的第二步，使用訓練樣例和反向傳播算法來精化網(wǎng)絡(luò)權(quán)值 圖12-3在歸納步發(fā)現(xiàn)了全新的依賴關(guān)系,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,14,KBANN算法說明,KBANN的好處和局限 好處：在給定近似正確領(lǐng)域理論時，能夠比反向傳播有更高的泛化精度，特別是在訓練數(shù)據(jù)稀少時 局限：只能使用命題領(lǐng)域理論，如果給予很不精確的領(lǐng)域理論，KBANN也可能被誤導，從而其泛化精度變得低于反向傳播,200

13、3.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,15,使用先驗知識改變搜索目標,將先驗知識合并到梯度下降中需最小化的誤差判據(jù)，這樣網(wǎng)絡(luò)需要擬合的是訓練數(shù)據(jù)和領(lǐng)域理論的組合函數(shù) TangentProp算法 TangentProp算法接受的領(lǐng)域知識被表示為對應(yīng)于其輸入變換的目標函數(shù)的導數(shù) 例如，對每個實例xi描述為一個實數(shù)，那么每個訓練樣例的形式可能是 圖12-5，基于3個訓練樣例學習目標函數(shù)f，通過擬合訓練值f(xi)的同時擬合相應(yīng)的導數(shù)，學習器能夠?qū)崿F(xiàn)更好的泛化 概括而言，包含訓練導數(shù)的效果是為了克服反向傳播算法中的歸納偏置，將其替換為所希

14、望的導數(shù)的顯示輸入信息 ？P248-P249,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,16,TangentProp舉例,Simard et al.提供了TangentProp的泛化精度與純歸納反向傳播之間的比較結(jié)果 針對任務(wù)是為單個數(shù)字0到9的圖像做標注 給予TangentProp的先驗知識是：數(shù)字的分類不因圖像的水平和垂直平移而改變 表12-4，顯示TangentProp的泛化精度高于純反向傳播算法,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,17,Tangen

15、tProp的說明,TangentProp使用的先驗知識形式為目標函數(shù)對應(yīng)其輸入變換的所希望的導數(shù) TangentProp通過使一個指標函數(shù)最小化來結(jié)合先驗知識和觀察到的訓練數(shù)據(jù)，這個指標函數(shù)同時度量了網(wǎng)絡(luò)對應(yīng)訓練樣例值的誤差和網(wǎng)絡(luò)對應(yīng)于導數(shù)的誤差 值決定了網(wǎng)絡(luò)在中個誤差中擬合這兩部分的程度，它由設(shè)計者選擇 TangentProp的不足：對于先驗知識中的錯誤健壯性不強，而且不能預(yù)先知道訓練導數(shù)中的錯誤出現(xiàn)程度，因而不能很好地選擇常量以確定擬合訓練值和訓練導數(shù)的相對重要程度,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,18,Tange

16、ntProp的說明（2）,TangentProp和反向傳播的搜索方法比較 TangentProp通過改變梯度下降最小化的指標函數(shù)來影響假設(shè)搜索，相當于改變了搜索目標 如果訓練樣例和先驗知識都正確，并且目標函數(shù)可用ANN精確表示，那么滿足TangentProp指標的權(quán)向量集合將為滿足反向傳播指標的權(quán)向量集合的子集，一些不正確的假設(shè)會被TangentProp剔除掉 對目標函數(shù)的訓練導數(shù)擬合的另一種方法是，簡單地將觀察到的訓練樣例附近的附加訓練樣例綜合起來，使用已知的訓練導數(shù)來估計這些附近的實例的訓練值,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講

17、者：陶曉鵬,19,EBNN算法,EBNN是基于解釋的神經(jīng)網(wǎng)絡(luò)，它用兩種方式改進了TangentProp算法 它不依靠用戶提供訓練導數(shù)，而是對每個訓練樣例自行計算訓練導數(shù)，計算方法是通過用一套給定的領(lǐng)域理論來解釋每個訓練樣例 涉及了如何確定學習過程中歸納和分析部分相對重要程度的問題，的值是對每個訓練樣例獨立選擇的，它基于一個啟發(fā)式規(guī)則，考慮領(lǐng)域理論能否精確預(yù)測特定樣例的訓練值 因此，對于那些能由領(lǐng)域理論正確解釋的訓練樣例，學習的分析成分被強化，而對不能正確解釋的樣例，分析成分被弱化,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,20,

18、EBNN算法（2）,EBNN的輸入包括： 形式為的一組訓練樣例，不包含訓練導數(shù) 一組領(lǐng)域理論，表示為一組預(yù)先訓練過的神經(jīng)網(wǎng)絡(luò)，而不是KBANN采用的Horn子句 EBNN的輸出：一個能逼近目標函數(shù)f的新的神經(jīng)網(wǎng)絡(luò)，學習到的網(wǎng)絡(luò)能夠擬合訓練樣例以及從領(lǐng)域理論中抽取的f的訓練導數(shù) 圖12-7，圖的上面部分顯示的是目標函數(shù)Cup的領(lǐng)域理論，每一方塊表示領(lǐng)域理論中一個神經(jīng)網(wǎng)絡(luò)，圖的下面是要學習的新神經(jīng)網(wǎng)絡(luò)，稱為目標網(wǎng)絡(luò),2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,21,EBNN算法（3）,EBNN通過執(zhí)行TangentProp算法來學習目

19、標網(wǎng)絡(luò) EBNN把接收到的輸入訓練值和從領(lǐng)域理論中計算出的導數(shù)提供給TangentProp EBNN計算訓練導數(shù)的方法 ？,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,22,EBNN算法的說明,概括地說，EBNN算法使用的領(lǐng)域理論被表示為一組預(yù)先學習到的神經(jīng)網(wǎng)絡(luò)，然后領(lǐng)域理論與訓練樣例一起訓練其輸出假設(shè) 對每個訓練樣例，EBNN使用其領(lǐng)域理論來解釋它，然后從此解釋中抽取訓練導數(shù) 對實例的每個屬性計算出一個訓練導數(shù)，以描述按照領(lǐng)域理論，目標函數(shù)值是怎樣被屬性值的微小變化影響的 Prolog-EBG與EBNN的區(qū)別 EBNN能夠處理不

20、完美的領(lǐng)域知識，而Prolog-EBG不能 Prolog-EBG學習到逐漸增長的Horn子句集，而EBNN學習到固定大小的神經(jīng)網(wǎng)絡(luò),2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,23,使用先驗知識來擴展搜索算子,FOCL是純歸納算法FOIL的一個擴展，它們的區(qū)別在于：搜索單個Horn子句的一般到特殊過程中候選假設(shè)生成的方法 FOIL生成每個候選特化式是通過加入一個新文字到子句前件中得到的 FOCL使用同樣的方法產(chǎn)生候選特化式，但還基于領(lǐng)域理論生成了附加的特化式 操作型文字和非操作型文字 操作型文字：當一個文字可被用于描述一個輸出假設(shè)

21、 非操作型文字：只出現(xiàn)在領(lǐng)域理論中作為中間特征但不是實例的原子屬性的文字,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,24,FOCL算法,FOCL使用下面兩種算子擴展當前假設(shè)h 對不是h一部分的每個操作型文字，創(chuàng)建h的一個特化式，方法是加入文字到前件中 按照領(lǐng)域理論，創(chuàng)建一個操作型的且是目標概念的邏輯充分條件，將這組文字加入到h的當前前件中，最后修剪h的前件，移去對于訓練數(shù)據(jù)不需要的文字，具體過程如下： 首先選擇一條領(lǐng)域理論子句，它的頭部匹配目標概念，如果有多個這樣的子句，選擇其中子句體關(guān)于訓練樣例有最高信息增益的 所選子句的前件形成了目標概念的一個邏輯充分條件，在這些充分條件中，再次使用領(lǐng)域理論，每個非操作型文字被替換掉，將子句前件代入到子句后件中 這個展開的過程持續(xù)到充分條件被表述為操作型文字，如果有多個可選的展開，那么用貪婪法選擇有最大信息增益的一個 最后，修剪充分條件。對表達式中的每個文字，除非文字的移除會降低訓練樣例上的分類精度，否則它被移去 上面的討論很容易擴展到一階表示中，類似第10章,2003.12.18,機器學習-歸納和分析學習的結(jié)合 作者：Mitchel