機(jī)器學(xué)習(xí)作業(yè)三

1、1.1 機(jī)器學(xué)習(xí)：人臉識(shí)別、手寫(xiě)識(shí)別、信用卡審批。 不是機(jī)器學(xué)習(xí)：計(jì)算工資，執(zhí)行查詢(xún)的數(shù)據(jù)庫(kù)，使用WORD。2.1 Since all occurrence of “” for an attribute of the hypothesis results in a hypothesis which does not accept any instance, all these hypotheses are equal to that one where attribute is “”. So the number of hypothesis is 4*3*3*3*3*3 +1 = 973.Wi

2、th the addition attribute Watercurrent, the number of instances = 3*2*2*2*2*2*3 = 288, the number of hypothesis = 4*3*3*3*3*3*4 +1 = 3889.Generally, the number of hypothesis = 4*3*3*3*3*3*(k+1)+1.2.3 Ans.S0= (,) v (,)G0 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: <Sunny, Warm, Normal, Str

3、ong, Warm, Same, Yes>S1=(Sunny, Warm, Normal, Strong, Warm, Same) v (,)G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 2: <Sunny, Warm, High, Strong, Warm, Same, Yes>S2= (Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, ？, Strong, Warm, Sa

4、me) v (,)G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: <Rainy, Cold, High, Strong, Warm, Change, No>S3=(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, ？, Strong, Warm, Same) v (,)G3 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?),(Sun

5、ny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same),(?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)Example 4: <Sunny, Warm, High, Strong, Cool, Change, Yes>S4= (Sunny, Warm, ?, Strong, ?, ?) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong,

6、?, ?)，(Sunny, Warm, ？, Strong, ？, ？) v (,)，(Sunny, Warm, ？, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Cool, Change)G4 =(Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same),(?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.4 Ans. (a) S= (4,6,3,5) (b) G=(3

7、,8,2,7) (c) e.g., (7,6), (5,4) (d) 4 points: (3,2,+), (5,9,+),(2,1,-),(6,10,-)2.6 Proof: Every member of VSH,D satisfies the right-hand side of expression.Let h be an arbitrary member of VSH,D, then h is consistent with all training examples in D.Assuming h does not satisfy the right-hand side of th

8、e expression, it means ¬(sS)(gG)(g h s) = ¬(sS)(gG) (g h) (h s). Hence, there does not exist g from G so that g is more general or equal to h or there does not exist s from S so that h is more general or equal to s. If the former holds, it leads to an inconsistence according to the definit

9、ion of G. If the later holds, itleads to an inconsistence according to the definition of S. Therefore, h satisfies the right-hand side ofthe expression. 􀀀 (Notes: since we assume the expression is not fulfilled, this can be only be if Sor G is empty, which can only be in the case of any inc

10、onsistent training examples, such as noiseor the concept target is not member of H.)貝葉斯：6.1 由題意可得，兩次對(duì)病人做化驗(yàn)測(cè)試都為正時(shí)，cancer和Øcancer的后驗(yàn)概率分別可表示為：P(canner|+，+)，P(Øcancer|+，+)。最后一個(gè)等號(hào)是因?yàn)榧俣▋蓚€(gè)測(cè)試是相互獨(dú)立的，即：P(+,+|cancer)=P(+|cancer)P(+|cancer)同理可得：P(+|cancer) P(+|cancer) P(cancer)=0.98*0.98*0.008=0.00768

11、32P(+|Øcancer) P(+|Øcancer) P(Øcancer)=0.03*0.03*0.992=0.0008928P(+,+) = P(+,+|cancer) P(cancer) + P(+,+|Øcancer)P(Øcancer)=0.0076832+0.0008928=0.008576所以：P(canner|+，+)0.0076832/0.008576=0.895896P(Øcancer|+，+)=0.1041046.2 由貝葉斯公式可知：因?yàn)槭录ancer與Øcancer互斥，且P(cancer)+P(

12、Øcancer)=1,有全概率公式可得： P(+) = P(+|cancer) P(cancer) + P(+|Øcancer)P(Øcancer)故所以中的歸一化方法正確。6.3 (a) P(h): 如果假設(shè)h1比h2更一般時(shí)，賦予P（h1）>=P(h2) (b) P(h): 如果假設(shè)h1比h2更一般時(shí)，賦予P（h1）<=P(h2) P(D|h)的分布同上(c) P(h) : 對(duì)任意假設(shè)hi和hj，P(hi)=P(hj)= P(D|h)的分布同上6.4 當(dāng)h()=時(shí)=1, 否則 =0 故 P(D) (a)用k表示合取式中布爾屬性的個(gè)數(shù)，用l 表示樣例

13、中與假設(shè)不一致 的樣例個(gè)數(shù)，則要被最小化的量的表達(dá)式為： + (b) 訓(xùn)練樣例集D有8個(gè)屬性A1,A1,A8,共8個(gè)屬性，需要3位來(lái)表示，目標(biāo)值為d,共有4個(gè)訓(xùn)練樣例，需要2位來(lái)表示。A1A2A3A4A5A6A7A8dX1011100000X2101100000X3110100000X4111100001在這組訓(xùn)練數(shù)據(jù)中，最短的一個(gè)一致假設(shè)為A1A2A3，則由上式可得，他的描述長(zhǎng)度為9位；存在一個(gè)不一致假設(shè)A1，需3位表示，只有一個(gè)屬性，有2個(gè)不一致，需4位，則此時(shí)的描述長(zhǎng)度為7位，小于一致假設(shè)是的9位，此時(shí)MDL選擇一個(gè)不一致的假設(shè)。 (c) P(h): 如果假設(shè)hi中的布爾屬性合取式中的屬

14、性個(gè)數(shù)小于hj的個(gè)數(shù)，則P(hi)>P(hj) P(D|h)= 6.5 在樸素貝葉斯分類(lèi)中，在給定目標(biāo)值V時(shí)，屬性之間相互獨(dú)立，其貝葉斯網(wǎng)如下所示,箭頭方向?yàn)閺纳系较隆Ｒ驗(yàn)閷傩詗ind與其它屬性獨(dú)立，沒(méi)有與其相關(guān)聯(lián)的屬性。機(jī)器學(xué)習(xí)1在測(cè)試一假設(shè)h時(shí)，發(fā)現(xiàn)在一包含n=1000個(gè)隨機(jī)抽取樣例的樣本s上，它出現(xiàn)r=300個(gè)錯(cuò)誤。Errors(h)的標(biāo)準(zhǔn)差是什么？將此結(jié)果與第節(jié)末尾的例子中標(biāo)準(zhǔn)差相比會(huì)得出什么結(jié)論？ 由題意知errors(h)=r/n=300/1000=0.3,由于r是二項(xiàng)分布，它的方差為np(1-p),然而p未知，用r/p代替p得出r的估計(jì)方差為1000*0.3*（1-0.3）

15、=210，相應(yīng)的標(biāo)準(zhǔn)差為sqrt(210)=14.5,這表示errors(h)=r/n中的標(biāo)準(zhǔn)差為14.5/1000=0.0145，由此得出以下結(jié)論：一般來(lái)說(shuō)，若在n個(gè)隨機(jī)選取的樣本中有r個(gè)錯(cuò)誤，errors(h)的標(biāo)準(zhǔn)差為sqrt(p(1-p)/n),它約等于用r/n= errors(h)來(lái)代替p. 2、如果沒(méi)有更多的信息對(duì)真實(shí)錯(cuò)誤率的評(píng)估也就是樣本錯(cuò)誤率， 則真實(shí)錯(cuò)誤率的標(biāo)準(zhǔn)差為：17/100=0.17 由95%的置信區(qū)間公式： 帶入數(shù)字得95%的置信區(qū)間為：0.17 +（1.96 X 0.04）.3.如果假設(shè)h在n=65的獨(dú)立抽取樣本上出現(xiàn)r=10個(gè)錯(cuò)誤，真實(shí)的錯(cuò)誤率的90%的置信區(qū)間（

16、雙側(cè)的）是多少？95%單側(cè)置信區(qū)間（即一個(gè)上界U，使得有95%置信區(qū)間errorD(h)U）是多少？90%單側(cè)區(qū)間是多少？解：樣本數(shù)為：n = 65，假設(shè)h在n個(gè)樣本上所犯的錯(cuò)誤為r = 10，所以樣本錯(cuò)誤率為errorS(h) = = = 。于是：errorD(h)的N%的置信區(qū)間為： 當(dāng)N = 90時(shí)，查表5-1得：zN = 1.64，可得真實(shí)錯(cuò)誤率的90%的置信區(qū)間為： = 0.16±0.07395%的單側(cè)置信區(qū)間為errorD(h)U，其中90%的單側(cè)置信區(qū)間為：errorD(h) U，其中（zN為置信度為80%的置信度時(shí)的值1.28）。4.要測(cè)試一假設(shè)h，其errorD(h)已知在0.2到0.6的范圍內(nèi)，要保證95%雙側(cè)置信區(qū)間的寬度小于0.1，最小應(yīng)搜集的樣例數(shù)是多少？解：若使95%雙側(cè)置信區(qū)間的寬度小于0.1，則： （其中zN = 1.96），上式中因此最少應(yīng)搜集的樣例數(shù)為3015.5 對(duì)隨即變量 ,為待估參數(shù),服從N(0,1) 分布,均值為d,方差為其中:erorD(h1)-errorD(h2)單側(cè)置信區(qū)間下限:d-zNs,+)同理可求單側(cè)置信區(qū)間上限:(-,d+ zN