1、第三章 學(xué)習(xí)的計(jì)算理論 示例學(xué)習(xí)的優(yōu)化問題 最優(yōu)覆蓋問題(MCV)生成具有最少數(shù)目公式的覆蓋； 最簡(jiǎn)公式問題(MCOMP)生成具有最少數(shù)目選擇子及屬性值的公式，或極大復(fù)合； 最優(yōu)示例學(xué)習(xí)問題(OPL)生成只由最簡(jiǎn)公式組成的最優(yōu)覆蓋。 二. 最優(yōu)覆蓋問題是NP難題 定理3.1：已知兩個(gè)問題P1和P2,如果P1是NP難題。并且P1可在多項(xiàng)式時(shí)間內(nèi)歸納到P2,則P2也是NP難題，并稱P1可（多項(xiàng)式）歸納到P2,如果P2反過來(lái)也能歸納到P1,則稱P1和P2是等價(jià)的。 定理3.2：最優(yōu)集合覆蓋問題(SETCV)是從一個(gè)有窮集合的有窮覆蓋中，找到一個(gè)具有最小基數(shù)的子覆蓋。即設(shè)T是一個(gè)m個(gè)點(diǎn)的集合，F(xiàn)是T的

2、子集族。 F=S1, ,Sp, 其中Si T。SETCV是找到F的具有最少數(shù)目的子族F,使得F是T的一個(gè)覆蓋：F F, 并且 |F|=最?。黄渲蟹?hào)| |表示基數(shù)。 定理3.3 最優(yōu)覆蓋問題(MCV)是NP難題。 設(shè) T=1, ,7 , F=S1, ,S6 S1=1,4,5,7, S2=3,4, S3=2,5,7,S4=1,2,6, S5=1,3,7, S6=3,5,6,定理3.4 最簡(jiǎn)公式問題是NP難題。 定理3.5 最優(yōu)示例學(xué)習(xí)問題是NP難題。 SETCV MCV, Li,歸納,P0,Li MCOMP P0+ 三. 最小屬性子集問題 定理3.6 最小屬性子集問題(MAS)是NP難題。,歸納

3、到,Pi,算法GMAS A ,i1; 建立正例集 PE在反例集NE背景下的聯(lián)合擴(kuò)張矩陣EM(PE|NE); 這里聯(lián)合擴(kuò)張矩陣是將所有正例的擴(kuò)張矩陣羅在一起。,(3) 在EM(PE|NE)找到一列，記為第j列，它含有最少數(shù)目的死元素“*”,AA xj. (4) 如果EM(PE|NE) 刪去所有在第j列含有非死元素的行； (5) 如果EM(PE|NE)= ,則終止，并返回A;否則iI+1.并轉(zhuǎn)向(3); 參考文獻(xiàn)： 歸納學(xué)習(xí)算法，理論，應(yīng)用。 洪加榮著 P.46-52, P.57-58.,1. 將h初始化為H中最特殊假設(shè) 2. 對(duì)每個(gè)正例x 對(duì)h的每個(gè)屬性約束a 如果x滿足a 那么不做任何處理 否

4、則將h中a替換為x滿足的另一個(gè)更一般約束 3. 輸出假設(shè)h h h h h,表 FIND-S算法,候選消除算法： 將G集合初始化為H中極大一般假設(shè) 將S集合初始化為H中極大特殊假設(shè) 對(duì)每個(gè)訓(xùn)練例d,進(jìn)行以下操作： 如果是一正例 從G中移去所有與d不一致的假設(shè) 對(duì)S中每個(gè)與d不一致的假設(shè)s 從s中移去s 把s的所有的極小泛化式h加入到S中，其中h滿足 h與d一致，而且G的某個(gè)成員比h更一般 從S中移去所有這樣的假設(shè)：它比S中另一假設(shè)更一般 如果是一個(gè)反例 從S中移去所有與d不一致的假設(shè) 對(duì)G中每個(gè)與d不一致的假設(shè)g 從G中移去g 把g的所有的極小特殊化式h加入到G中，其中h滿足 h與d一致，而且

5、S的某個(gè)成員比h更特殊 從G中移去所有這樣的假設(shè)：它比G中另一假設(shè)更特殊, ,S0:,S1:,S2:,G0,G1,G2:, ,S2,S3:,G3:,G2:, , ,S3:,S4:,G4:,G3:,表 目標(biāo)概念EnjoySport的正例和反例,第三章 概念學(xué)習(xí)和一般到特殊序 2.1 簡(jiǎn)介 定義：概念學(xué)習(xí)是指從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。 2.2 概念學(xué)習(xí)任務(wù),概念學(xué)習(xí)任務(wù)能被描述為：實(shí)例的集合、實(shí)例集合上的目標(biāo)函數(shù)、候選假設(shè)的集合以及訓(xùn)練例的集合。 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。 2.3 作為搜

6、索的概念學(xué)習(xí) EnjoySport的實(shí)例空間： 322 2 2 2=96 假設(shè)空間：5 4 4444=5120 1+4 33 3 3 3=973 假設(shè)的一般到特殊序 定義：令hj和hk為在X上定義的布爾函數(shù)。稱hj more_general_than_or_equal_to hk（記作 hjg hk），當(dāng)且僅當(dāng),已知： 實(shí)例集X:可能的日子由下面的屬性描述： Sky（可能取值為Sunny,Cloudy和Rain) AirTemp(可取值為Warm和Cold) Humidity(可取值為Normal和High) Wind(可取值為Strong和Weak) Water(可取值為Warm和Cool) Forecast(可取值為Same和Change) 假設(shè)集H: 每個(gè)假設(shè)描述為6個(gè)屬性Sky,AirTemp,Humidity,Wind,Water和Forecast的值約束的合取。約束可以為“？”（表示接受任意值），“ ” （表示拒絕所有值），或一特定值,目標(biāo)概念c: EnjoySport: X0,1 訓(xùn)練樣例集D:目標(biāo)函數(shù)的正例和反例（見表2-1) 求解： H中的一假設(shè)h,使對(duì)于X中任意x, h(x)=c(x),實(shí)例集 X,假設(shè)集 H,h1,h2,h3,特殊,一般,列表后消