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

1、1.1 機(jī)器學(xué)習(xí)：人臉識別、手寫識別、信用卡審批。 不是機(jī)器學(xué)習(xí)：計算工資，執(zhí)行查詢的數(shù)據(jù)庫，使用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 由題意可得，兩次對病人做化驗測試都為正時，cancer和Øcancer的后驗概率分別可表示為：P(canner|+，+)，P(Øcancer|+，+)。最后一個等號是因為假定兩個測試是相互獨立的，即：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 由貝葉斯公式可知：因為事件cancer與Øcancer互斥，且P(cancer)+P(

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

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

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

15、-0.3）=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é)論：一般來說，若在n個隨機(jī)選取的樣本中有r個錯誤，errors(h)的標(biāo)準(zhǔn)差為sqrt(p(1-p)/n),它約等于用r/n= errors(h)來代替p. 2、如果沒有更多的信息對真實錯誤率的評估也就是樣本錯誤率， 則真實錯誤率的標(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的獨立抽取樣本上出現(xiàn)r=10個錯誤，真實的錯誤率的90%的

16、置信區(qū)間（雙側(cè)的）是多少？95%單側(cè)置信區(qū)間（即一個上界U，使得有95%置信區(qū)間errorD(h)U）是多少？90%單側(cè)區(qū)間是多少？解：樣本數(shù)為：n = 65，假設(shè)h在n個樣本上所犯的錯誤為r = 10，所以樣本錯誤率為errorS(h) = = = 。于是：errorD(h)的N%的置信區(qū)間為： 當(dāng)N = 90時，查表5-1得：zN = 1.64，可得真實錯誤率的90%的置信區(qū)間為： = 0.16±0.07395%的單側(cè)置信區(qū)間為errorD(h)U，其中90%的單側(cè)置信區(qū)間為：errorD(h) U，其中（zN為置信度為80%的置信度時的值1.28）。4.要測試一假設(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 對隨即變量 ,為待估參數(shù),服從N(0,1) 分布,均值為d,方差為其中:erorD(h1)-errorD(h2)單側(cè)置信區(qū)間下限:d-zNs,+)同理可求單側(cè)置信區(qū)間上限:(-,d+ zN