第2章_概念學習

1、Date:4/27/2022File:ML1.1Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering 概念學習概念學習 給定某一類別的若干正例和反例，從中獲得該類別的一給定某一類別的若干正例和反例，從中獲得該類別的一般定義。般定義。 搜索的觀點搜索的觀點 在預定義的假設(shè)空間中搜索假設(shè)，使其與訓練樣例有最在預定義的假設(shè)空間中搜索假設(shè)，使其與訓練樣例有最佳的擬合。佳的擬合。 利用假設(shè)空間的利用假設(shè)空間的 算法收斂到正確假設(shè)的條件算法收斂到正確假設(shè)的條件? 歸納

2、學習的本質(zhì)，從訓練數(shù)據(jù)中歸納學習的本質(zhì)，從訓練數(shù)據(jù)中的理由的理由?第第2章章 概念學習和一般到特殊序概念學習和一般到特殊序Date:4/27/2022File:ML1.2Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering簡介簡介 許多機器學習涉及到從特殊訓練樣例中得到一般概念。許多機器學習涉及到從特殊訓練樣例中得到一般概念。，可被看作一個對象或事件集合，它是從更大的，可被看作一個對象或事件集合，它是從更大的集合中選取的子集，或在這個較大集合中定義的布爾集

3、合中選取的子集，或在這個較大集合中定義的布爾函數(shù)。函數(shù)。的定義的定義 給定一個樣例集合以及每個樣例是否屬于某個概念的標注，給定一個樣例集合以及每個樣例是否屬于某個概念的標注，怎樣推斷出該怎樣推斷出該。又稱從樣例中逼近布爾函。又稱從樣例中逼近布爾函數(shù)。數(shù)。 概念學習是指從有關(guān)某個布爾函數(shù)的輸入輸出訓練樣例中概念學習是指從有關(guān)某個布爾函數(shù)的輸入輸出訓練樣例中推斷出該布爾函數(shù)。推斷出該布爾函數(shù)。Date:4/27/2022File:ML1.3Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Con

4、trol Engineering概念學習任務概念學習任務 一個例子一個例子 目標概念目標概念 Aldo進行水上運動的日子，表示為布爾函數(shù)進行水上運動的日子，表示為布爾函數(shù)EnjoySport 任務目的任務目的 基于某天的各屬性，預測基于某天的各屬性，預測EnjoySport的值的值 給定一個樣例集給定一個樣例集D 每個樣例表示為每個樣例表示為6個屬性的集合個屬性的集合Date:4/27/2022File:ML1.4Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engine

5、ering概念學習任務（概念學習任務（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表表2-1 目標概念目標概念EnjoySport的訓練樣例的訓練樣例Date:4/27/2022File:ML1.5Machine LearningPeng Kaixiang 2015. All

6、rights reserved.Machine Learning for Control Engineering概念學習任務（概念學習任務（3） 表示表示的形式（目標函數(shù)的表示）的形式（目標函數(shù)的表示） 一個簡單的形式，一個簡單的形式，的各屬性約束的的各屬性約束的 令每個假設(shè)為令每個假設(shè)為6個約束（或變量）的向量，每個約束對個約束（或變量）的向量，每個約束對應一個屬性可取值范圍，為應一個屬性可取值范圍，為 ？任意本屬性可接受的值？任意本屬性可接受的值 明確指定的屬性值明確指定的屬性值 不接受任何值不接受任何值 假設(shè)的例子假設(shè)的例子 / 所有的樣例都是正例所有的樣例都是正例 / 所有的樣例都是反

7、例所有的樣例都是反例Date:4/27/2022File:ML1.6Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering概念學習任務（概念學習任務（4）已知已知 實例集實例集X 每個實例每個實例x由由6個屬性描述，每個屬性的取值范圍已確定個屬性描述，每個屬性的取值范圍已確定 假設(shè)集假設(shè)集H 每個假設(shè)每個假設(shè)h描述為描述為6個屬性的取值約束的合取個屬性的取值約束的合取 目標概念目標概念c 一個布爾函數(shù)，變量為實例一個布爾函數(shù)，變量為實例 訓練樣例集訓練樣例集

8、D 目標函數(shù)（或目標概念）的正例和反例目標函數(shù)（或目標概念）的正例和反例求解求解 H中的一假設(shè)中的一假設(shè)h，使對于，使對于X中任意中任意x，h(x)=c(x)Date:4/27/2022File:ML1.7Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering術(shù)語定義術(shù)語定義 實例實例x 實例集實例集X 概念概念 目標概念目標概念c 訓練樣例訓練樣例x 訓練樣例集訓練樣例集D 正例，目標概念成員正例，目標概念成員 反例，非目標概念成員反例，非目標概念成員 假

9、設(shè)假設(shè)h 假設(shè)集假設(shè)集H就是尋找一個假設(shè)就是尋找一個假設(shè)h，使得對所有的，使得對所有的h，都有，都有h(x)=c(x)Date:4/27/2022File:ML1.8Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering學習假設(shè)學習假設(shè) 什么是歸納學習？什么是歸納學習？ 從特殊的樣例得到普遍的規(guī)律（從特殊的樣例得到普遍的規(guī)律（） 歸納歸納 只能保證輸出的假設(shè)能與訓練樣例相擬合只能保證輸出的假設(shè)能與訓練樣例相擬合 歸納假設(shè)的一個基本假定歸納假設(shè)的一個基本假定

10、對于未見實例最好的假設(shè)就是對于未見實例最好的假設(shè)就是 歸納學習假設(shè)歸納學習假設(shè) 任一假設(shè)如果在足夠大的訓練樣例集中很好地逼近目標任一假設(shè)如果在足夠大的訓練樣例集中很好地逼近目標函數(shù)，它也能在未見實例中很好地逼近目標函數(shù)。函數(shù)，它也能在未見實例中很好地逼近目標函數(shù)。Date:4/27/2022File:ML1.9Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering作為作為的概念學習的概念學習 概念學習可以看作一個概念學習可以看作一個 搜索范圍：假設(shè)的表示所隱

11、含定義的整個空間搜索范圍：假設(shè)的表示所隱含定義的整個空間 搜索目標：能夠最好地擬合訓練樣例的假設(shè)搜索目標：能夠最好地擬合訓練樣例的假設(shè) 當假設(shè)的表示形式選定后，那么就隱含地為學習算當假設(shè)的表示形式選定后，那么就隱含地為學習算法確定了所有假設(shè)的空間法確定了所有假設(shè)的空間 例子EnjoySport的假設(shè)空間，如果屬性Sky有3種可能的值，而AirTemp、Humidity、Wind、Water和 Forecast都只有兩種可能值。 實例空間X：包含322222=96種不同的實例 假設(shè)空間H 包含544444=5120種語法不同語法不同的假設(shè) 由于：包含有符號的假設(shè)將每個實例都分類為反例。因此，語義

12、語義不同不同的假設(shè)只有1+433333=973個。 Date:4/27/2022File:ML1.10Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering假設(shè)的一般到特殊序假設(shè)的一般到特殊序 假設(shè)的一般到特殊序關(guān)系假設(shè)的一般到特殊序關(guān)系 考慮下面兩個假設(shè)考慮下面兩個假設(shè) h1= h2= 任何被任何被h1劃分為正例的實例都會被劃分為正例的實例都會被h2劃分為正例，劃分為正例，因此因此h2比比h1更一般。更一般。 利用這個關(guān)系，無需列舉所有假設(shè)，就能在利用這個

13、關(guān)系，無需列舉所有假設(shè)，就能在無限的假設(shè)空間中進行徹底的搜索無限的假設(shè)空間中進行徹底的搜索Date:4/27/2022File:ML1.11Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering假設(shè)的一般到特殊序（假設(shè)的一般到特殊序（2） 關(guān)系關(guān)系“更一般更一般”的精確定義的精確定義 任給實例任給實例x和假設(shè)和假設(shè)h，說，說x滿足滿足h，當且僅當，當且僅當h(x)=1 令令hj和和hk是在是在X上定義的布爾函數(shù)，稱上定義的布爾函數(shù)，稱hj比比hk更更一般，當

14、且僅當一般，當且僅當( x X)(hk(x)=1)(hj(x)=1) 記為記為hj more_general_than_or_equal_to hk，或，或hj g hkDate:4/27/2022File:ML1.12Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering假設(shè)的一般到特殊序（假設(shè)的一般到特殊序（3） “更一般更一般”的嚴格情形的嚴格情形 hj g hk，當且僅當，當且僅當，(hj g hk) (hk g hj) “更特殊更特殊”關(guān)系的定義關(guān)

15、系的定義 hj g hk，當且僅當，當且僅當，hk g hj 以以EnjoySport為例說明上面的定義為例說明上面的定義 偏序的特點（區(qū)別于全序），全序上的搜索可以是偏序的特點（區(qū)別于全序），全序上的搜索可以是二分法，偏序的搜索比無序簡單，比全序復雜。二分法，偏序的搜索比無序簡單，比全序復雜。 這個偏序關(guān)系的定義與目標概念無關(guān)這個偏序關(guān)系的定義與目標概念無關(guān)Date:4/27/2022File:ML1.13Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineeri

16、ngh1=h2 =h3 =x1=x2 =Date:4/27/2022File:ML1.14Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control EngineeringFind-S：尋找極大特殊假設(shè)：尋找極大特殊假設(shè)使用使用more_general_than偏序的搜索算法偏序的搜索算法從從H中最特殊假設(shè)開始，然后在假設(shè)覆蓋正例中最特殊假設(shè)開始，然后在假設(shè)覆蓋正例失敗時將其一般化失敗時將其一般化1.將將h初始化為初始化為H中最特殊假設(shè)中最特殊假設(shè)2.對每個正例對每個正例x對對h的每個

17、屬性約束的每個屬性約束ai如果如果x滿足滿足ai那么不做任何處理那么不做任何處理否則將否則將h中中ai替換為替換為x滿足的另一個更一般約束滿足的另一個更一般約束3.輸出假設(shè)輸出假設(shè)hDate:4/27/2022File:ML1.15Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control EngineeringFind-S：尋找極大特殊假設(shè)（：尋找極大特殊假設(shè)（2） Find-S算法在例子算法在例子EnjoySport上的應用上的應用 h h h 遇到反例，遇到反例，h不變（因為不變

18、（因為h已經(jīng)能夠正確地識別已經(jīng)能夠正確地識別反例）反例） hDate:4/27/2022File:ML1.16Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control EngineeringDate:4/27/2022File:ML1.17Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control EngineeringFind-S：尋找極大特殊假設(shè)（：尋找極大特殊假設(shè)（3）

19、 Find-S算法演示了一種利用算法演示了一種利用more_general_than偏序來搜索偏序來搜索假設(shè)空間的方法，沿著偏序鏈，從較特殊的假設(shè)逐漸轉(zhuǎn)移假設(shè)空間的方法，沿著偏序鏈，從較特殊的假設(shè)逐漸轉(zhuǎn)移到較一般的假設(shè)。因此，每一步得到的假設(shè)都是在那一點到較一般的假設(shè)。因此，每一步得到的假設(shè)都是在那一點上與訓練樣例一致的最特殊的假設(shè)。上與訓練樣例一致的最特殊的假設(shè)。 Find-S的重要特點：對以屬性約束的合取式描述的假設(shè)空的重要特點：對以屬性約束的合取式描述的假設(shè)空間間H，保證輸出為，保證輸出為H中與正例一致的最特殊的假設(shè)。中與正例一致的最特殊的假設(shè)。 存在的問題存在的問題 是否收斂到了正確的

20、目標概念？是否收斂到了正確的目標概念？ 為什么要用最特殊的假設(shè)？為什么要用最特殊的假設(shè)？ 訓練樣例是否相互一致？訓練樣例是否相互一致？ 如果有多個極大特殊假設(shè)怎么辦？如果有多個極大特殊假設(shè)怎么辦？Date:4/27/2022File:ML1.18Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering 候選消除算法概說候選消除算法概說 概念學習的另一種方法，概念學習的另一種方法，（candidate-elimination） Find-S算法的不足，輸出的假設(shè)

21、只是算法的不足，輸出的假設(shè)只是H中能夠擬合訓練樣例的多個假中能夠擬合訓練樣例的多個假設(shè)中的設(shè)中的 候選消除算法輸出與訓練樣例一致的候選消除算法輸出與訓練樣例一致的 候選消除算法在描述這一集合時不需要明確列舉所有成員候選消除算法在描述這一集合時不需要明確列舉所有成員 利用利用more_general_than偏序結(jié)構(gòu)，可以維護一個一致假設(shè)集合的簡偏序結(jié)構(gòu)，可以維護一個一致假設(shè)集合的簡潔表示潔表示 候選消除算法的應用：候選消除算法的應用：、 候選消除算法的缺點：容錯性能差候選消除算法的缺點：容錯性能差Date:4/27/2022File:ML1.19Machine LearningPeng Kai

22、xiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除算法（變型空間和候選消除算法（2） “一致一致”的定義的定義 一個假設(shè)一個假設(shè)h與訓練樣例集合與訓練樣例集合D一致，當且僅當對一致，當且僅當對D中每一中每一個樣例個樣例都有都有h(x)=c(x)，即，即Consistent(h,D)( D)h(x)=c(x) “一致一致”與與“滿足滿足”的關(guān)系的關(guān)系 變型空間（變型空間（Version Space） 與訓練樣例與訓練樣例的所有假設(shè)組成的集合的所有假設(shè)組成的集合 表示了目標概念的所有合理

23、的變型表示了目標概念的所有合理的變型 關(guān)于關(guān)于H和和D的變型空間，記為的變型空間，記為VSH,D，是，是H中與訓練樣例中與訓練樣例D一一致的所有假設(shè)構(gòu)成的子集致的所有假設(shè)構(gòu)成的子集VSH,D=h H|Consistent(h,D)Date:4/27/2022File:ML1.20Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除算法（變型空間和候選消除算法（3） 列表后消除算法列表后消除算法表示變型空間的一種方法是列出其所有成員表示變型

24、空間的一種方法是列出其所有成員 變型空間變型空間包含包含H中所有假設(shè)的列表中所有假設(shè)的列表 對每個訓練樣例對每個訓練樣例，從變型空間中移除所有，從變型空間中移除所有h(x) c(x)的假設(shè)的假設(shè) 輸出輸出Version Space中的假設(shè)列表中的假設(shè)列表 優(yōu)點優(yōu)點 保證得到所有與訓練數(shù)據(jù)一致的假設(shè)保證得到所有與訓練數(shù)據(jù)一致的假設(shè) 缺點缺點 非常繁瑣地列出非常繁瑣地列出H中的所有假設(shè)，大多數(shù)實際的假設(shè)空間無法做到中的所有假設(shè)，大多數(shù)實際的假設(shè)空間無法做到Date:4/27/2022File:ML1.21Machine LearningPeng Kaixiang 2015. All rights

25、reserved.Machine Learning for Control Engineering變型空間和候選消除算法（變型空間和候選消除算法（4）的更簡潔表示的更簡潔表示 變型空間被表示為它的極大一般和極大特殊的變型空間被表示為它的極大一般和極大特殊的成員成員 這些成員形成了一般和特殊邊界的集合，這些這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結(jié)構(gòu)中劃分出變型空間邊界在整個偏序結(jié)構(gòu)中劃分出變型空間 以以EnjoySport為例為例Date:4/27/2022File:ML1.22Machine LearningPeng Kaixiang 2015. All rights rese

26、rved.Machine Learning for Control EngineeringDate:4/27/2022File:ML1.23Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除算法（變型空間和候選消除算法（5） 形式化定義形式化定義 極大一般極大一般 極大特殊極大特殊 關(guān)于假設(shè)空間關(guān)于假設(shè)空間H和訓練數(shù)據(jù)和訓練數(shù)據(jù)D的的一般邊界一般邊界G，是在，是在H中與中與D相一致的極大一般成員的集合相一致的極大一般成員的集合 關(guān)于假設(shè)

27、空間關(guān)于假設(shè)空間H和訓練數(shù)據(jù)和訓練數(shù)據(jù)D的的特殊邊界特殊邊界S，是在，是在H中與中與D相一致的極大特殊成員的集合相一致的極大特殊成員的集合Date:4/27/2022File:ML1.24Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除算法（變型空間和候選消除算法（6）: 令令X為一任意的實例集合，為一任意的實例集合，H為為X上定義的上定義的布爾假設(shè)的集合。令布爾假設(shè)的集合。令c: X0,1為為X上定義的任一目標概念，上定義的任一目標

28、概念，并令并令D為任一訓練樣例集合為任一訓練樣例集合。對所有的。對所有的X, H, c, D以以及良好定義的及良好定義的S和和G：VSH,D=h H|( s S)( g G)(g gh gs)證明：只需證明：證明：只需證明：1）每一個滿足上式右邊的）每一個滿足上式右邊的h都在都在VSH,D中，中，2）VSH,D的每個成員都滿足都滿足等式右邊。的每個成員都滿足都滿足等式右邊。Date:4/27/2022File:ML1.25Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control En

29、gineering變型空間和候選消除算法（變型空間和候選消除算法（7） 候選消除算法候選消除算法 初始化初始化G和和S 如果如果d是一個正例是一個正例 從從G中移去所有與中移去所有與d不一致的假設(shè)不一致的假設(shè) 對對S中每個與中每個與d不一致的假設(shè)不一致的假設(shè)s 從從S中移去中移去s 把把s的所有的極小泛化式的所有的極小泛化式h加入到加入到S中，其中中，其中h滿足滿足h與與 d一致，而且一致，而且G的某個成員比的某個成員比h更一般更一般 從從S中移去所有這樣的假設(shè)：它比中移去所有這樣的假設(shè)：它比S中另一個假設(shè)更一般中另一個假設(shè)更一般 如果如果d是一個反例是一個反例 從從S中移去所有與中移去所有與

30、d不一致的假設(shè)不一致的假設(shè) 對對G中每個與中每個與d不一致的假設(shè)不一致的假設(shè)g 從從G中移去中移去g 把把g的所有的極小特殊化式的所有的極小特殊化式h加入到加入到G中，其中中，其中h滿足滿足h與與d一致，而且一致，而且S的某個成員比的某個成員比h更特殊更特殊 從從G中移去所有這樣的假設(shè)：它比中移去所有這樣的假設(shè)：它比G中另一個假設(shè)更特殊中另一個假設(shè)更特殊Date:4/27/2022File:ML1.26Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變

31、型空間和候選消除算法（變型空間和候選消除算法（8） 算法舉例算法舉例S1:S2: G3:S2 S3 :S4: G4:G0 G1:G0 G1 G2 :Date:4/27/2022File:ML1.27Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering圖圖2-7 最終變型空間最終變型空間Date:4/27/2022File:ML1.28Machine LearningPeng Kaixiang 2015. All rights reserved.Machin

32、e Learning for Control Engineering變型空間和候選消除的說明變型空間和候選消除的說明 候選消除算法收斂到正確的假設(shè)候選消除算法收斂到正確的假設(shè) 訓練樣例中沒有錯誤訓練樣例中沒有錯誤 H中確實包含描述目標概念的正確假設(shè)中確實包含描述目標概念的正確假設(shè) 如果樣例中存在錯誤如果樣例中存在錯誤 如果給定足夠的訓練數(shù)據(jù)，我們會發(fā)現(xiàn)如果給定足夠的訓練數(shù)據(jù)，我們會發(fā)現(xiàn)S和和G邊界收斂得邊界收斂得到一個空的變型空間到一個空的變型空間 如果目標概念不能由假設(shè)表示方式所描述如果目標概念不能由假設(shè)表示方式所描述 比如是約束的析取比如是約束的析取 Date:4/27/2022File:

33、ML1.29Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除（變型空間和候選消除（2） 下一步需要什么樣的訓練樣例下一步需要什么樣的訓練樣例 一般來說，概念學習的一般來說，概念學習的，是產(chǎn)生，是產(chǎn)生實例以滿足當前變型空間中大約半數(shù)的假設(shè)。實例以滿足當前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個新樣例這樣，變型空間的大小可以在遇到每個新樣例時減半，正確的目標概念就可在只用時減半，正確的目標概念就可在只用log2|VS|

34、次次實驗后得到。實驗后得到。Date:4/27/2022File:ML1.30Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering變型空間和候選消除（變型空間和候選消除（3） 怎樣使用不完全學習概念怎樣使用不完全學習概念 雖然圖雖然圖2-7的變型空間中仍包含多個假設(shè)，即目的變型空間中仍包含多個假設(shè)，即目標概念還未學習到，但是仍然有可能對新樣例標概念還未學習到，但是仍然有可能對新樣例進行一定可信度的分類。進行一定可信度的分類。 待分類的新實例待分類的新實例D

35、ate:4/27/2022File:ML1.31Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering概念的應用概念的應用Date:4/27/2022File:ML1.32Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering概念的應用概念的應用 判斷是否是正例判斷是否是正例 判斷是否滿足判斷是否滿足S中的每個假設(shè)中的每個

36、假設(shè) 判斷是否是反例判斷是否是反例 判斷是否不滿足判斷是否不滿足G中的每個假設(shè)中的每個假設(shè)Date:4/27/2022File:ML1.33Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置歸納偏置 有關(guān)候選消除算法的幾個問題有關(guān)候選消除算法的幾個問題 如果目標概念不在假設(shè)空間中怎么辦？如果目標概念不在假設(shè)空間中怎么辦？ 是否可設(shè)計一個包含所有假設(shè)的空間來解決這是否可設(shè)計一個包含所有假設(shè)的空間來解決這一困難？一困難？ 假設(shè)空間的大小對于算法推廣到

37、未見實例的能假設(shè)空間的大小對于算法推廣到未見實例的能力有什么影響？力有什么影響？ 假設(shè)空間的大小對所需訓練樣例的數(shù)量有什么假設(shè)空間的大小對所需訓練樣例的數(shù)量有什么影響？影響？Date:4/27/2022File:ML1.34Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（2） 一個有偏的假設(shè)空間一個有偏的假設(shè)空間 在在EnjoySport這個例子中，假設(shè)空間限制為只包這個例子中，假設(shè)空間限制為只包含屬性值的合取。（有偏）含屬性值的合

38、取。（有偏） 這一限制，導致假設(shè)空間不能夠表示最簡單的這一限制，導致假設(shè)空間不能夠表示最簡單的析取形式的目標概念。析取形式的目標概念。Date:4/27/2022File:ML1.35Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（3） 無偏的學習器無偏的學習器 為了保證目標概念在假設(shè)空間中，需要提供一為了保證目標概念在假設(shè)空間中，需要提供一個假設(shè)空間，它能表達所有的可教授概念。換個假設(shè)空間，它能表達所有的可教授概念。換言之，它能表

39、達實例集言之，它能表達實例集X的所有子集。的所有子集。 問題：為什么問題：為什么2.3節(jié)中合取假設(shè)空間只能表示節(jié)中合取假設(shè)空間只能表示973個假設(shè)？個假設(shè)？Date:4/27/2022File:ML1.36Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（4） EnjoySport的無偏形式的無偏形式 帶來的問題：概念學習算法無法從訓練樣例中帶來的問題：概念學習算法無法從訓練樣例中泛化。泛化。 要想獲得單個目標概念，就必須提供要想獲得

40、單個目標概念，就必須提供X中所有實中所有實例作為訓練樣例例作為訓練樣例 使用使用2.6.3節(jié)討論的部分學習的無效節(jié)討論的部分學習的無效Date:4/27/2022File:ML1.37Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（5） 無偏學習的無用性無偏學習的無用性 歸納學習的一個基本屬性：學習器如果不對目歸納學習的一個基本屬性：學習器如果不對目標概念的形式做預先的假定，它從根本上無法標概念的形式做預先的假定，它從根本上無法對未

41、見實例進行分類對未見實例進行分類 歸納學習需要的預先假定，稱為歸納偏置歸納學習需要的預先假定，稱為歸納偏置Date:4/27/2022File:ML1.38Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（6） 歸納偏置的精確定義歸納偏置的精確定義 (Dc xi) L(xi,Dc) 需要在需要在Dc xi上附加怎樣的前提，以使上附加怎樣的前提，以使L(xi,Dc) 能夠演繹派生。能夠演繹派生。 L的歸納偏置定義為前提集合的歸納偏置定義

42、為前提集合B，使所有的新實例滿足：，使所有的新實例滿足：(B Dc xi) L(xi,Dc) 考慮對于實例集合考慮對于實例集合X的概念學習算法的概念學習算法L。令。令c為為X上定義的任上定義的任一概念，并令一概念，并令Dc為為c的任意訓練樣例集合，的任意訓練樣例集合，L(xi,Dc) 表示經(jīng)過表示經(jīng)過Dc訓練后訓練后L賦予實例賦予實例xi的分類。的分類。L的歸納偏置是最小斷言集合的歸納偏置是最小斷言集合B，它使任意目標概念，它使任意目標概念c和相應的訓練樣例和相應的訓練樣例Dc滿足：滿足： xi X(B Dc xi)L(xi,Dc)Date:4/27/2022File:ML1.39Machin

43、e LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering歸納偏置（歸納偏置（6） 候選消除算法的歸納偏置候選消除算法的歸納偏置 c HInductive Systems and Equivalent Deductive Systems(歸納與演繹)Date:4/27/2022File:ML1.40Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engi

44、neering歸納偏置（歸納偏置（7） 3個有偏程度不同的歸納學習算法個有偏程度不同的歸納學習算法 機械式機械式 候選消除算法候選消除算法 Find-S 一種算法的有偏性越強，它的歸納能力越強，一種算法的有偏性越強，它的歸納能力越強，可以分類更多的未見實例?？梢苑诸惛嗟奈匆妼嵗?某些歸納偏置隱含在學習器中，有些表示為某些歸納偏置隱含在學習器中，有些表示為斷言集合，可由學習器操作。斷言集合，可由學習器操作。Date:4/27/2022File:ML1.41Machine LearningPeng Kaixiang 2015. All rights reserved.Machine Learning for Control Engineering小結(jié)小結(jié) 概念學習可看作概念學習可看作的過程的過程; 假設(shè)的一般到特殊假設(shè)的一般到特殊可以定義在任何概念學習問題中，可以