華南理工大學(xué)《高級人工智能》復(fù)習(xí)資料

#/13華南理工大學(xué)《高級人工智能》復(fù)習(xí)資料1、計算 決策樹 （去年考的題型）設(shè)樣本集合如下所示，其中A、決策樹。B、C設(shè)樣本集合如下所示，其中A、決策樹。B、C是F的屬性，試根據(jù)信息增益標(biāo)準(zhǔn)（ID3算法）求解F的A0000111B0011001C0101010F0101110(已知log2(2/3)=-0.5842,log2(13)=-1.5850,log2(34)=-0.41504,)=4H7 A=0=4H7 A=0+3H7 A=11I. 2 2 2 1I—-71210g24+210g24+210g23+110g23卜0.96523+3H7 B=0 7 B=11I3 1 17I310g24+110g24+110g23+210g23卜0.857=4=4H+3H7 C=0 7C=11I1- 3一3一71110g24+310g24+310g23+010g2310.464所以第一次分類選屬性C，對C=0的四個例子再進(jìn)行第二次分類。22=所以第一次分類選屬性C，對C=0的四個例子再進(jìn)行第二次分類。22=-H+-H4 A=0 4A=141110g2+110g21=0.522H+H4 B=0 4 B=111110g14I22+110g2所以，可任選屬性A可任選屬性A或B作為第二次分類的標(biāo)準(zhǔn)，如選屬性A，則A=1的兩個例子再按屬性B分類，得到類，得到=1H+1H2 B=0 2B=1最后，最后，2、邏輯推理(去年考的題型)把謂詞公式變換成子句形式?(Vx)0y)P(a,x,y)-0x)(?(Vy)Q(y,b)-R(x))解：第一步，消去一號，得：?(?(Vx)0y)P(a,x,y))V0x)(??(Vy)Q(y,b)VR(x))第二步，?深入到量詞內(nèi)部，得：(Vx)(3y)P(a,x,y)V(3x)((Vy)Q(y,b)VR(x))第三步，變元易名，得(Vx)(3y)P(a,x,y)V(3u)(Vv)(Q(v,b)VR(u))第四步，存在量詞左移，直至所有的量詞移到前面，(Vx)(3y)(3u)(Vv)(P(a,x,y)V(Q(v,b)VR(u))由此得到前述范式第五步，消去“m(存在量詞)，略去V全稱量詞消去(R),因為它左邊只有(Vx),所以使用x的函數(shù)f(x)代替之，這樣得到:(Vx)(mu)(Vv)(P(a,x,f(x))VQ(v,b)VR(u))消去0u),同理使用g(x)代替之，這樣得到：(Vx)(Vv)(P(a,x,f(x))VQ(v,b)VR(g(x)))貝U，略去全稱變量，原式的Skolem標(biāo)準(zhǔn)形為：P(a,x,f(x))VQ(v,b)VR(g(x))3、謂詞公式表示知識與歸結(jié)法證明定理過程(去年考的題型)例設(shè)已知：(1)能閱讀者是識字的；(2)海豚不識字；(3)有些海豚是很聰明的。試證明：有些聰明者并不能閱讀。證首先,定義如下謂詞：R(x)：x能閱讀。L(x)：x識字。I(x)：x是聰明的。D(x)：x是海豚。然后把上述各語句翻譯為謂詞公式：(1)Vx(R(x)-L(x))⑵ Vx(D(x)-「L(x)) 已知條件⑶ 3x(D(x)Al(x))⑷ 3x(I(x)A-R(x)) 需證結(jié)論求題設(shè)與結(jié)論否定的子句集,得(1)「R(x)VL(x)⑵1D(y)V「L(y)(3)D(a)⑷I(a)⑸[I(z)VR(z)將子句集進(jìn)行歸結(jié)(6)R(a)⑷(5)歸結(jié)⑺L(a) (1)⑹歸結(jié)(8)「D(a)(2)(7)歸結(jié)(9)NIL⑶⑻歸結(jié)4、貝葉斯網(wǎng)絡(luò)推理(去年考的題型)根據(jù)圖所給出的貝葉斯網(wǎng)絡(luò)，其中：P(A)=0.5,P(B|A)=1,P(B|~A)=0.5,P(C|A)=1,P(C|~A)=0.5,P(D|BC)=1,P(D|B,~C)=0.5,P(D|~B,C)=0.5,P(D|~B,~C)=0。計算下列概率P(A|D)A/\BC\/DP(A|D)=aBCP(A,B,C,D)=abCP(A)P(B|A)P(C|A)P(D|B,C)BC=aP(A)BP(B|A)CP(C|A)P(D|B,C)BP(B|A)CP(C|A)P(D|B,C)=P(B|A)CP(C|A)P(D|B,C)+P(~B|A)CP(C|A)P(D|~B,C)=P(B|A)[P(C|A)P(D|B,C)+P(~C|A)P(D|B,~C)]+P(~B|A)[P(C|A)P(D|~B,C)+P(~C|A)P(D|~B,~C)]=1*[1*1+0]+0=1P(A|D)=aP(A)*1=0.5a同理P(~A|D)=ab,P(~A,B,C,D)BC=aBCP(~A)P(B|~A)P(C|~A)P(D|B,C)=aP(~A)BP(B|~A)CP(C|~A)P(D|B,C)BP(B|~A)CP(C|~A)P(D|B,C)=P(B|~A)CP(C|~A)P(D|B,C)+P(~B|~A)CP(C|~A)P(D|~B,C)=P(B|~A)[P(C|~A)P(D|B,C)+P(~C|~A)P(D|B,~C)]+P(~B|~A)[P(C|~A)P(D|~B,C)+P(~C|~A)P(D|~B,~C)]=0.5*[0.5*1+0.5*0.5]+0.5[0.5*0.5+0.5*0]=0.5P(~A|D)=aP(~A)*0.5=0.25a歸一化得P(A|D)=0.675、【謂詞歸結(jié)：說謊者與老實人】消解反演求解證明誰是說謊者 (去年考的題型)一個島上有兩種人，老實人總是說真話，說謊者總是說假話。問島上A、B、C三人：誰說謊？A答：B和C都說謊B答：A和C都說謊C答：A和B至少有一人說謊問題：請問誰是說謊者？解法一：令H(x)表示X說真話,W(x,y)表示x，y中至少一人說謊，V(x,y)表示x,y中至少一人說真話如果A為老實人，得子句如下：H(A)，一＞H(B),「H(C)(A,B)H(A),H(B)通過消解反演得到空子樹，故該假設(shè)不成立如果B為老實人，得子句如下：(B,C)H(B),「H(A),「H(C)H(A),H(B)通過消解反演得到空子樹，故該假設(shè)不成立如果C為老實人，分如下情況：A說謊，B說真話H(B),「H(A),「H(C)H(C)通過消解反演得到空子樹，故該假設(shè)不成立B說謊，A說真話H(A),「H(B),「H(C)H(C)通過消解反演得到空子樹，故該假設(shè)不成立A,B都說謊「H(A),V(B,C)「H(B),V(A,C)H(C)通過消解反演沒有空子樹，故該假設(shè)成立總結(jié)：A,B為說謊者解法二：設(shè)T(x):x是說真話的人A說真話：T(A)--T(B)八-T(C)A說假話：-T(A)-T(B)vT(C)B說真話：T(B)f-T(A)八-T(C)B說假話：-T(B)-T(A)vT(C)C說真話：T(C)f-T(A)v-T(B)C說假話：-T(C)-T(A)△T(B)?化為字句集-T(A)v-T(B)-T(A)v-T(C)T(A)vT(B)vT(C)-T(B)v-T(C)T(C)v-T(A)v-T(B)T(A)vT(C)7、T(C)vT(B)?求解問題的否定式和answer的析取8.-T(x)vanswer(x)9.T(C)vT(B)1.和6.歸結(jié)10.T(C)7.和9.歸結(jié)11.Answer(C)8.和10.歸結(jié)所以C是老實人。8.T(x)vanswer(x)9.T(C)vT(B)1.和6.歸結(jié)10.T(B)4.和9.歸結(jié)11.Answer(B)8.和10.歸結(jié)所以B不是老實人。8.T(x)vanswer(x)9.T(C)vT(A)1.和7.歸結(jié)10.T(A)2.和9.歸結(jié)11.Answer(A)8.和10.歸結(jié)所以A不是老實人。6、樸素貝葉斯學(xué)習(xí)法 （去年考的題型）樣例：某種天氣是否適合室外打網(wǎng)球訓(xùn)練數(shù)據(jù)—給定14個樣例（下頁表）輸入新實例<Outlook=sunny,Temperature=cool,Humidity=high,Wind=strong>求目標(biāo)概念的值PlayTennis=Yes/NoDayOutlookTemperatureHumidityWindPlayTennis1sunnyhothighweakno2sunnyhothighstrongno3overcasthothighweakyes4rainmildhighweakyes5raincoolnormalweakyes6raincoolnormalstrongno7overcastcoolnormalstrongyes8sunnymildhighweakno9sunnycoolnormalweakyes10rainmildnormalweakyes11sunnymildnormalstrongyes12overcastmildhighstrongyes13overcasthotnormalweakyes14rainmildhighstrongno解：將實例代入到樸素貝葉斯分類器輸出公式得如下式子v=argmaxP(v)口P(aIv)NB jiijv.e{yes,no}二argmaxP(v)P(sunnyIv)P(coolIv)P(highIv)P(strongIv).v.e{yes,no}計算vNB,可以從訓(xùn)練數(shù)據(jù)中獲得P(PlayTennis=Yes)=9/14=0.64P(PlayTennis=No)=5/14=0.36

各條件概率為：P(strong|Y)=3/9=0.33各條件概率為：P(strong|Y)=3/9=0.33P(high|Y)=3/9=0.33P(cool|Y)=3/9=0.33P(sunny|Y)=2/9=0.22P(strong|N)=3/5=0.60P(high|N)=4/5=0.80P(cool|N)=1/5=0.20P(sunny|N)=3/5=0.60由此得P(yes)P(strong|Y)P(high|Y)P(cool|Y)P(sunny|Y)=0.64*0.33*0.33*0.33*0.22=0.0051P(no)P(strong|N)P(high|N)P(cool|N)P(sunny|N)=0.36*0.60*0.80*0.20*0.6=0.0207由此知樸素貝葉斯分類器的輸出結(jié)果是PlayTennis=No概率歸一化，則得0.0207/(0.0051+0.0207)=0.8027、語義網(wǎng)絡(luò)屬性關(guān)系：AKO,AMO,ISA包含關(guān)系Part_of屬性關(guān)系Have,Can時間關(guān)系Before,After位置關(guān)系：Locted-on，Located-at，Located-under，Located-inside，Located-outside相近關(guān)系：Simliar-to，Near-to因果關(guān)系：If-then 組成關(guān)系：Composed-of用語義網(wǎng)絡(luò)表示下列命題（1）豬和羊都是動物；（2）豬和羊都是哺乳動物；（3）野豬是豬，但生長在森林中；（4）山羊是羊，頭上長著角；（5）綿羊是一種羊，它能生產(chǎn)羊毛。分析：對象有豬、羊都、動物、哺乳動物、野豬、山羊、綿羊、森林、羊毛、角等。語義關(guān)系，“動物”和“哺乳動物”、“哺乳動物”和“豬”、“哺乳動物”和“羊”、“羊”和“山羊”及“綿羊”、“野豬”和“豬”之間的關(guān)系是“是一種”的關(guān)系，可用來表示?！吧窖颉焙汀邦^上有角”之間是一種屬性關(guān)系，可用 來描述；“綿羊”和“羊毛”之間是一種屬性關(guān)系，可用 來描述；“野豬”和“森林”之間是位置關(guān)系，可用 來表示。語義網(wǎng)絡(luò)：8、框架表示法試實現(xiàn)一個“大學(xué)教師”的框架，大學(xué)教師類屬于教師，包括以下屬性：學(xué)歷（學(xué)士、碩士、博士）、專業(yè)（計算機(jī)、電子、自動化、 ）、職稱（助教、講師、副教授、教授）一般結(jié)構(gòu)：〈框架名〉〈槽名1＞〈側(cè)面11〉〈值111＞〈值11k1＞〈側(cè)面1n1＞〈值1n11＞〈值1n1kn1＞〈槽名2〉〈側(cè)面12〉〈值121＞〈值1211＞〈側(cè)面1n2＞〈值1n21＞〈值1n21n2＞…解：框架名：＜大學(xué)教師＞類屬：＜教師＞學(xué)歷：（學(xué)士，碩士，博士）專業(yè)：（計算機(jī)，電子，自動化）職稱：（助教，講師，副教授，教授）9、與或型正向演繹推理已知事實：Fido要么會犬叫和咬人，要么Fido就不是狗。已知規(guī)則：所有Terrier都是狗；②所有會犬叫的東西都是咬人的。求證：存在某個東西，它要么不是Terrier,要么會咬人。證明：將事實用謂詞邏輯表示F1：(CRY(X)八()V~DOG(X)F2：Vx(Terrier(x)-DOG(x))F3：Vx(CRY(x)-BITE(x))目標(biāo)表達(dá)式子：3x(~Terrier(x)VBITE(x))(CRY(X)八()V~DOG(X)((T)A()V~DOG(X)BIT(EX))V~DOG(X)由F2得F4：~DOG(x)一~Terrier(x)故BI(TEX))V~Terrier(x)即~Terrier(x)VBITE(x)結(jié)論成立。10、與或型逆向演繹推理已知事實：F1:DOG(FIDO)；狗的名字叫FidoF2:?BARKS(FIDO)；Fido是不叫的F3:WAGS-TAIL(FIDO)；Fido搖尾巴F4:MEOWS(MYRTLE)；貓咪的名字叫Myrtle已知規(guī)則：R1:[WAGS-TAIL(x1)ADOG(x1)]fFRIENDLY(x1)；搖尾巴的狗是溫順的狗R2:[FRIENDLY(x2)A?BARKS(x2)]f?AFRAID(y2,x2)；溫順而又不叫的東西是不值得害怕的R3:DOG(x3)fANIMAL(x3)；狗為動物R4:CAT(x4) fANIMAL(x4)；貓為動物R5:MEOWS(x5)fCAT(x5)；貓咪是貓求證：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?用目標(biāo)表達(dá)式表示此問題為:3(x)3(y)[CAT(x)ADOG(y)A?AFRAID(x,y)]CAT(x)ADOG(y) ?AFRAID(x,y)D0G(y){FIDO/y}?AFRAID/y)-BAEKS(y)~AFRAID9@2,x2){FIDO/y}D0G(y){FIDO/y}?AFRAID/y)-BAEKS(y)~AFRAID9@2,x2){FIDO/y}?BAEKS(FIDO)FRIENDLY(xl)WAGS-TAIL(y) DOG(y)({FIDO/y} j|{FIDO/y}終止在事實節(jié)點前的置換為{MYRTLE/x}和{FI悔夠把它應(yīng)用贏標(biāo)表達(dá)式=我們就得到該問題的回答語句如下： 1 1 」[CAT(MYRTLE)八DOG(FIDO)八?AFRAID(MYRTLE,FIDO)]9、產(chǎn)生式表示方式以及推理過程設(shè)有如下問題：(1)有五個相互可直達(dá)且距離已知的城市A、B、C、D、E,如圖所示;(2)某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;(3)找一條最短的旅行路線請用產(chǎn)生式規(guī)則表示旅行過程。解：①綜合數(shù)據(jù)庫(x)GOTO(A)GOTO(A)GOTO(B)GOTO(C)GOTO(D)GOTO(E)GOTO(x)為走向城市x(x)中x可以是一個字母，也可以是一個字符串。②初始狀態(tài)(A)③目標(biāo)狀態(tài)(Ax1x2x3x4A)④規(guī)則集：r1:IF L(S)=5 THENr2:IF L(S)<5 THENr3:IF L(S)<5 THENr4:IF L(S)<5 THENr5:IF L(S)<5 THEN其中L(S)為走過的城市數(shù)，⑤路線如下圖所示:最短旅行路線為：A->C->D->E->B->A總距離為5+6+8+10+7=3610、10、Kmeans數(shù)據(jù)對象集合S見表I,作為一個聚類分析的二維粹束，要反的簇的藪要k=2°⑴選擇。蛇),處(。。為初始的簇中心，I即 必=q=(⑼'aa=o2=(d,oi⑵對剩余的每個