西瓜書划水筆記

12-13

第一章緒論

1.1 求版本空間

根據 P.5 的說明，我們只需要不斷刪除和正例不一致的假設和與反例一致的假設，即可得到樣本空間。因此我們可以很容易得出只包含編號為 1 以及 4 的兩個樣例的版本空間。

色澤根蒂敲聲青綠***蜷縮***濁響*蜷縮濁響青綠*濁響青綠蜷縮*青綠蜷縮濁響

1.2 估算全部假設

樣本空間：3*4*4+1 = 49

k 最大取 2*3*3=18

1.3 歸納偏好

去除假設一樣而標記不一樣的樣本即可

1.4 推廣證明 NFL 定理

$Lemma 1: l(h(x) = f(x)) + l(h(x) e f(x))= C$

$Proof:$

$l(0,0) = l(1,1), l(0,1) = l(1,0)$

$l(0,0) + l(0,1) = l(1,1) + l(1,0) = C$

$l(h(x) = f(x)) + l(h(x) e f(x))= C$

$sum_{f}sum_{h}sum_{x in chi -X}P(x)l(h(x),f(x))P(h|X,L_a)$

$= sum_{x in chi -X}P(x)sum_{f}l(h(x),f(x))sum_{h}P(h|X,L_a)$

$= 2^{|chi - 1} C sum_{x in chi -X} P(x)$

$Q.E.D$

1.5 機器學習的互聯網應用

眾所周知