《機器學習》習題解答（第一章：緒論）

習題

1.1 表1.1中若只包含編號為1和4的兩個樣例，試給出相應的版本空間。

1.2 與使用單個合取式來進行假設表示相比，使用「析合範式」將使得假設空間具有更強的表示能力。例如 ， 會把 「 」

以及 「 」

都分類為「好瓜」。若使用最多包涵k個合取式的析合範式來表達表1.1西瓜分類問題的假設空間，試估算共有多少種可能的假設。

1.3 若數據包含雜訊，則假設空間中有可能不存在與所有訓練樣本都一致的假設。在此情形下，試設計一種歸納偏好用於假設選擇。

1.4 本章1.4節在論述「沒有免費的午餐」定理時，默認使用了「分類錯誤率」作為性能度量來對分類器進行評估。若換用其他性能度量$l$，則式(1.1)將改為

，

試證明「沒有免費的午餐定理」仍成立。

1.5 試述機器學習能在互聯網搜索的哪些環節起什麼作用。

解答

1.1

樣例1和樣例4：

編號 | 色澤 | 根蒂 | 敲聲 | 好瓜

取值一共7種，合取式為：

1.2

首先參考所有樣例：

編號 | 色澤 | 根蒂 | 敲聲 | 好瓜

1 | 青綠 | 蜷縮 | 濁響 | 是

根據色澤，根蒂，敲聲的屬性數量，假設空間的規模為： ，即k的最大值為48。注意，由於樣例中已經有正例，所以不需要考慮空集的情況。

首先不考慮冗餘的情況，那麼只需要枚舉出所有可能的組合即可，所有可能的假設可表示為：

但是實際情況中是有冗餘的，書中給出的冗餘示例就是包含關係，即 和 為冗餘關係，暫不考慮其他冗餘情況。

筆者數學水平一般，沒法用數學方法求解，所以使用Python寫了一段腳本，用於計算所有k值對應的可能假設數量：

from enum import Enum, uniqueColor = Enum(色澤, (青綠, 烏黑, *))Root = Enum(根蒂, (蜷縮, 硬挺, 稍蜷, *))Sound = Enum(敲聲, (清脆, 濁響, 沉悶,*))def searchConjunction(): 枚舉出所有的合取式，按照三屬性泛化，二屬性泛化，一屬性泛化，無泛化的順序排序 templist = [[],[],[],[]] for name, color in Color.__members__.items(): for name, root in Root.__members__.items(): for name, sound in Sound.__members__.items(): i = [color, root, sound] count = 0 for e in i: if e.name == "*": count +=1 templist[count].append(i) ConjunctionList = templist[3] + templist[2] + templist[1] + templist[0] return ConjunctionListdef redundancy(conjunction1, conjunction2): 檢查兩個合取式之間是否有冗餘關係 flag = 0 for i in range(len(conjunction1)): if conjunction1[i] != conjunction2[i]: if conjunction1[i].name == *: if flag == 2: return False else: flag = 1 elif conjunction2[i].name == *: if flag == 1: return False else: flag = 2 else: return False return Truedef isRedundancy(disjunction, conjunction): 檢查析合範式是否有榮冗餘 for d in disjunction: if redundancy(d, conjunction): return True return Falsedef searchDisjunction(DisjunctionList, ConjunctionList, t): 使用遞歸枚舉出所有的析合範式，不考慮冗餘，t為每個析合範式所包含的合取式個數 if t==0: return [i[1:] for i in DisjunctionList] templist = [] for l in DisjunctionList: for i, element in enumerate(ConjunctionList): if l == []: templist.append([i, element]) elif i > l[0]: if not isRedundancy(l[1:], element): templist.append([i] + l[1:] + [element]) return searchDisjunction(templist, ConjunctionList, t-1)ConjunctionList = searchConjunction()k = 18summ = 0for i in range(1,k+1): DisjunctionList = searchDisjunction([ [] ],ConjunctionList,i) count = len(DisjunctionList) summ += count print("k = " +str(i)+ ", sum = " + str(summ))

枚舉所有的組合，再過濾掉所有的冗餘假設， 這就是代碼的思路。

由於這種方法的時間複雜度非常高，所以k值較大時，運算速度非常慢，這裡給出幾個已算出的k值作為參考：

k = 1, sum = 48k = 2, sum = 979k = 3, sum = 11320k = 4, sum = 83967k = 5, sum = 430679k = 6, sum = 1612267

1.3

通常認為兩個數據的屬性越相近，則更傾向於將他們分為同一類。若相同屬性出現了兩種不同的分類，則認為它屬於與他最臨近幾個數據的屬性。也可以考慮同時去掉所有具有相同屬性而不同分類的數據，留下的數據就是沒誤差的數據，但是可能會丟失部分信息。

1.4

還是考慮二分類問題，NFL首先要保證真是目標函數f均勻分布，對於有X個樣本的二分類問題，顯然 共有 種情況。其中一半是與假設一致的，也就 。

此時， 應該是個常數，隱含的條件就該是(一個比較合理的充分條件) 。如果不滿足， NFL 應該就不成立了(或者不那麼容易證明)。

1.5

推薦系統（廣告，內容），搜索結果排名，以圖搜圖等。

推薦閱讀：