機器學習課堂筆記4

1，機器什麼時候可以學習

2，為什麼機器可以學習

3，機器怎麼學習

4，機器怎麼樣才能學得更好

VC維：

課堂筆記3中提到“break point”的概念：在資料量達到一定數量k的時候，假設集合H無法再shatter這k個資料，則成長函數mH的break point就是k。VC dimision=k-1，即假設集合H可以shatter的最大的資料量，記為dvc

不同的假設集合H的VC維是不一樣的，對于課堂筆記1中提到的感覺器算法（PLA），其VC維=d+1,其中d是輸入變量X的次元。對于有些H，VC維是無限大（比如機器學習筆記3中提到的convex set，對任意數量的資料都可以shatter）

有了VC維的概念，當dvchi有限的時候，就可以用其保證Ein和Eout是接近的。這種接近是一般意義上的，即對任何機器學習算法，任何産生X的分布，任何可能的目标函數f，都能保證樣本内的錯誤Ein和樣本外錯誤Eout是PAC的，是以我們可以有以下的機器學習的架構：

一般來說，我們可以根據假設集合H的假設自由度（即假設中待确定的參數的數量）來近似估計VC維。例如有W=(w0,w1,...,wd)，dvc(H)近似等于d.可以把VC維看成對假設H有多強的度量，dvc越小，假設H越簡單，我們越可以保證Ein和Eout是很接近的，但是也越難以找到好的假設h讓Ein足夠小。反之，Ein可以很小，但是Eout可能和Ein相差很遠（也就是過拟合問題）。

可以用dvc表示模型複雜度。模型複雜度影響着Ein和Eout的差别。根據學習筆記3中的公式：

模型複雜度和Eout，Ein的關系圖如下：

可以看到Eout是随着dvc先減少後增加的。

dvc還可以指導我們需要多少資料量才能達到某種精度要求：

假設需要Ein和Eout相差超過0.1的機率不超過0.1，則我們學習需要的資料量是：

理論上來說，需要的資料量是dvc的一萬倍。但是dvc是非常寬松的上界，是以實際上：