1.1 表1.1中若只包含編號(hào)為1和4的兩個(gè)樣例蹦漠，試給出相應(yīng)的版本空間
樣本空間各屬性的取值：
色澤：青綠、烏黑车海、*
根蒂：蜷縮笛园、稍蜷、*
敲聲：濁響、沉悶研铆、*
版本空間定義：學(xué)習(xí)過(guò)程是基于有限的訓(xùn)練集進(jìn)行闸度，可能有多個(gè)假設(shè)與訓(xùn)練集一致，即存在著一個(gè)與訓(xùn)練集一致的“假設(shè)集合”蚜印，稱(chēng)為“版本空間”。
所以對(duì)于編號(hào)1和4的版本空間為：
1.色澤=青綠留量；根蒂=蜷縮窄赋；敲聲=濁響
2.色澤=青綠；根蒂=蜷縮楼熄；敲聲=*
3.色澤=青綠；根蒂=*可岂；敲聲=濁響
4.色澤=青綠；根蒂=*缕粹；敲聲=*
5.色澤=*稚茅；根蒂=蜷縮平斩；敲聲=濁響
6.色澤=*亚享；根蒂=蜷縮；敲聲=*
7.色澤=*绘面；根蒂=*欺税；敲聲=濁響
2.2與使用單個(gè)合取式來(lái)進(jìn)行假設(shè)表示相比，使用“析合范式”將使得假設(shè)空間具有更強(qiáng)的表示能力晚凿。例如
好瓜←→（(色澤=)∧(根蒂=蜷縮)∧(敲聲=)）∨（(色澤=烏黑)∧(根蒂=*)∧(敲聲=沉悶)）會(huì)把“（(色澤=青綠)∧(根蒂=蜷縮)∧(敲聲=清脆)）”以及“（(色澤=烏黑)∧(根蒂=硬挺)∧(敲聲=沉悶)）”都分類(lèi)為“好瓜”。
若使用最多包含k個(gè)合取式的析合范式來(lái)表達(dá)表1.1西瓜分類(lèi)問(wèn)題的假設(shè)空間歼秽，試估算共有多少種可能的假設(shè)。
表1.1西瓜數(shù)據(jù)集中情组，色澤共有2個(gè)屬性值哲银，根蒂共有3個(gè)屬性值，敲聲共有3個(gè)屬性值呻惕。為計(jì)算方便荆责，下面的計(jì)算不考慮空集的情況（若考慮空集，則直接在每種假設(shè)的情況下再加上一種含空集的假設(shè)計(jì)算即可）
計(jì)算假設(shè)還需考慮每個(gè)屬性的通配符（泛化）的情況亚脆，則用單個(gè)合取式來(lái)表示假設(shè)共有3×4×4=48種不同假設(shè)，分別為：
①不含泛化屬性的假設(shè)：2×3×3=18種
②含一個(gè)屬性泛化的假設(shè)：2×3+2×3+3×3=21種
③含兩個(gè)屬性泛化的假設(shè)：2+3+3=8種
④含三個(gè)屬性泛化的假設(shè)：1種
用“析合范式”表示假設(shè)
（1）不考慮冗余情況：易知k的取值范圍是[1，48]寺滚，則假設(shè)總數(shù)就是從48個(gè)合取式中取出k個(gè)進(jìn)行組合的加總，共有 種假設(shè)
（2）考慮冗余情況：試想當(dāng)取k=18的時(shí)候恰好有一種組合方式是由18種不含泛化屬性的假設(shè)組合成的村视，此時(shí)若取k=19，則必然引入至少1個(gè)含一個(gè)屬性泛化的假設(shè)進(jìn)行組合蚁孔，就必然會(huì)產(chǎn)生冗余的情況。所以可知k的取值范圍是[1杠氢，18]，且k=18時(shí)組合產(chǎn)生的假設(shè)只有1種另伍。
求最多包含k個(gè)合取式的析合范式的假設(shè)數(shù)量最容易想到的辦法就是作差計(jì)算
計(jì)算思路：
①求出k在每種取值下的所有組合數(shù)
②求出k在每種取值下出現(xiàn)冗余的組合數(shù)
③將上面兩數(shù)相減即可得出析合范式的假設(shè)數(shù)量
計(jì)算流程
結(jié)果：
k=1，48
k=2摆尝，931
k=3，10341
k=4堕汞，72647
k=5，346712
k=6臼朗，1181588
……
在利用python求解的過(guò)程中遇到比較大的問(wèn)題就是隨著k的增大，組合數(shù)量呈指數(shù)級(jí)增長(zhǎng)视哑，對(duì)計(jì)算機(jī)的運(yùn)算能力和內(nèi)存的要求都非常高。此種方法運(yùn)算到k=5時(shí)用時(shí)33s挡毅，k=6時(shí)用時(shí)6min，k=8時(shí)出現(xiàn)內(nèi)存溢出跪呈。
針對(duì)此現(xiàn)象，曾嘗試加入相關(guān)的能提高運(yùn)算速度和減少內(nèi)存消耗的方法改進(jìn)代碼耗绿，但是由于技術(shù)有限，處理后的效果并不顯著误阻。
1.3若數(shù)據(jù)包含噪聲晴埂，則假設(shè)空間中可能不存在與所有訓(xùn)練樣本都一致的假設(shè)寻定。在此情形下儒洛，試設(shè)計(jì)一種歸納偏好用于假設(shè)選擇
歸納偏好通俗的理解就是在面對(duì)有不同分類(lèi)結(jié)果的西瓜時(shí)狼速，你更傾向于根據(jù)哪種“標(biāo)準(zhǔn)”來(lái)分類(lèi)琅锻。在西瓜問(wèn)題上向胡，假設(shè)空間中可能不存在與所有訓(xùn)練樣本都一致的假設(shè)，此時(shí)我更傾向于選擇與訓(xùn)練集好瓜屬性盡可能一致的標(biāo)準(zhǔn)捷枯，即精度越高越好的歸納偏好专执。
1.4本章1.4節(jié)在論述“沒(méi)有免費(fèi)的午餐”定理時(shí)淮捆，默認(rèn)使用了“分類(lèi)錯(cuò)誤率”作為性能度量來(lái)對(duì)分類(lèi)器進(jìn)行評(píng)估本股。若換用其他性能度量l,則將（1.1）式改寫(xiě)成下面形式，試證明沒(méi)有免費(fèi)的午餐”定理仍成立
以下分析均基于二分類(lèi)任務(wù)
式1.2中拄显，l ( h (x), f (x) )表示分類(lèi)器對(duì)一個(gè)樣例分類(lèi)正確或者錯(cuò)誤的“分?jǐn)?shù)”，并且分類(lèi)正確與錯(cuò)誤的分?jǐn)?shù)是固定的常數(shù)躬审，即 l (0,0) = l (1,1) = a , l (0,1) = l (1,0) = b
可推出 l (0,0) + l (0,1) = l (1,1) + l (1, 0）= A ，A亦為固定常數(shù)
因此 l ( h (x) = f (x) ) + l ( h (x) ≠ f (x) )=A
基于以上推導(dǎo)承边，可求出某種分類(lèi)器的總“得分”，過(guò)程如下
可以看到博助，采用任一性能度量，算法的種類(lèi)并不影響分類(lèi)的總“得分”富岳，即所有分類(lèi)器的期望性能都是相同的，也就是說(shuō)“沒(méi)有免費(fèi)的午餐”定理成立窖式。
思考：上面的分析參考了網(wǎng)上的文章得出。在剛開(kāi)始看見(jiàn)式(1.2)時(shí)萝喘，思維被固定在 l ( h (x)狼电，f (x) ) 的意義上了弦蹂，然后自己就嘗試拋掉式(1.2)列舉一個(gè)具體的性能指標(biāo)“查全率”來(lái)分析：
在二分類(lèi)任務(wù)中肩碟，查準(zhǔn)率
由上面公式可以看出凸椿，N是所有西瓜的總數(shù)（已知常數(shù)），TP+FN為真實(shí)情況中好瓜的數(shù)量（已知常數(shù)）脑漫，現(xiàn)在只需證明P(·)與算法無(wú)關(guān)就能證明查準(zhǔn)率R與采用何種算法無(wú)關(guān)。
對(duì)TP/N的理解：所有西瓜中有多少比例的好瓜被預(yù)測(cè)正確了
假設(shè)目標(biāo)函數(shù) f 服從均勻分布优幸，則 f 的期望值與采用哪種算法無(wú)關(guān)，而 f 的期望值可以理解為在所有西瓜中好瓜被預(yù)測(cè)正確的概率有多大网杆，也就是說(shuō) f 的期望就是TP/N或P(·)，所以查準(zhǔn)率R不受采用何種算法無(wú)關(guān)碳却，“沒(méi)有免費(fèi)的午餐”定理成立。
“沒(méi)有免費(fèi)的午餐”定理的成立昼浦，需要遵從很?chē)?yán)謹(jǐn)?shù)募僭O(shè)。而事實(shí)上我們的假設(shè)通常沒(méi)有辦法實(shí)現(xiàn)关噪，所以才造成了采用不同算法有不同的性能表現(xiàn)鸟蟹，這一點(diǎn)可以回看之前同學(xué)對(duì)各分類(lèi)器的總結(jié)章節(jié)
1.5 試述機(jī)器學(xué)習(xí)能在互聯(lián)網(wǎng)搜索的哪些環(huán)節(jié)起作用
①在網(wǎng)頁(yè)中推送用戶經(jīng)常瀏覽的內(nèi)容：客戶日常搜索的關(guān)鍵字會(huì)被輸入到系統(tǒng)中使兔，經(jīng)過(guò)神經(jīng)網(wǎng)絡(luò)等算法處理，在網(wǎng)頁(yè)上及時(shí)更新用戶感興趣的推送內(nèi)容
②智能語(yǔ)音搜素：如百度的語(yǔ)音搜索火诸、siri的語(yǔ)音搜索，涉及到自然語(yǔ)言處理等內(nèi)容
③互聯(lián)網(wǎng)金融中客戶的識(shí)別：如螞蟻金服中會(huì)通過(guò)記錄客戶的金融記錄和信用記錄置蜀，對(duì)客戶進(jìn)行分類(lèi)和給客戶提出風(fēng)險(xiǎn)提示，當(dāng)中涉及復(fù)雜的數(shù)據(jù)挖掘盯荤、神經(jīng)網(wǎng)絡(luò)等算法。
代碼：我的碼云
