Learning Theory

05-08

本章我們介紹Learning Theory中的部分內容，來自於Andrew Ng的CS229課程內容。

????????

1. Bias/variance tradeoff

在討論linear regression問題時，我們討論了簡單模型例如 $y= heta_{0}+ heta_{1}x$ 和複雜模型例如 $y= heta_{0}+ heta_{1}x+...+ heta_{5}x^{5}$ ，可以看到類似如下的例子：

如右圖所示，五階多項式來擬合數據並不能產生一個好的模型，儘管對於訓練集中的數據 $x$ (房屋面積)能夠很好的預測 $y$ (房屋價格)，但是模型並不能很好的預測不在模型中的數據。也就是訓練集中學習到的模型不能generalize well to other houses. 假設的Generalization error(後面會正式定義)是所有樣例的期望error，不一定是訓練集中的樣例。

上面的兩個模型都有很大的generalization error，但是兩個模型的問題是不同的。

如果 $y,x$ 之間的關係是非線性的額，那麼即便採用線性模型來擬合大量的訓練數據，線性模型依然無法精確獲取數據的結構，不正式地說，我們定義模型bias為期望generalization error即便我們用模型擬合一個非常大的訓練集。因此對於上面的問題，線性模型large bias，會underfit數據。
generalization error除了bias外還有一個重要部分是variance，當採用五階多項式來擬合餓數據，很有可能我們所擬合的是恰好這個小的、有限的數據集中的數據展現出的模式，並不反映 $y,x$ 之間的普遍關係。這可能例如我們數據集中恰好得到一個比正常貴的房子或者比正常便宜的房子，這種情況下我們可能獲得一個generalization error很大的模型，我們稱模型large variance

通常在bias和variance之間有tradeoff存在：

如果模型太簡單，參數太少，那麼就有可能擁有較大bias較小variance；
如果模型太複雜，參數太多，那麼就有可能擁有較小bias較大variance

在上述的例子中，採用quadratic function就會比first or fifth order polynomial擬合效果更好。

以下內容來自於知乎機器學習中的Bias(偏差)，Error(誤差)，和Variance(方差)有什麼區別和聯繫

bias描述的是根據樣本擬合出的模型的輸出預測結果的期望與樣本真實結果的差距，簡單講，就是在樣本上擬合的好不好，是不是准
variance描述的是根據樣本擬合出的模型在測試集上的表現，如果想要在variance上表現好，即得到low variance，就要簡化模型，減少模型參數，但這樣容易underfitting，欠擬合對應上圖的就是high bias，點偏離中心，low variance對應的點都很集中，但不一定在巴新附近，手很穩但是喵的不準

????????

2. Preliminaries

在接下來，我們將進行learning theory的學習，這個討論也將幫助我們磨練我們的直覺，並得出關於如何在不同環境中最好地應用學習演算法的經驗法則。我們將回答一系列問題：

我們能夠將上述討論的bias/variance形式化？這將導出model selection methods，例如如何自動的選擇採用幾階多項式來擬合數據
在機器學習中，我們所關心的事generalization error，但是絕大部分的機器學習演算法都採用模型擬合訓練數據，訓練數據上的誤差能告訴我們哪些關係generalization error的內容呢？
在什麼條件下我們能夠證明學習演算法非常好用？

我們首先證明兩個有用的引理(lemma).

The Union Bound: 假設 $A_{1},A_{2},...,A_{k}$ 是 $k$ 個different events(未必相互獨立)，那麼： $P(A_{1}cup A_{2}...cup A_{k})leq P(A_{1})+...+P(A_{k})$

Hoeffding inequality: 假設 $Z_{1},Z_{2},...,Z_{k}$ 是m個獨立同分布的變數，由 $Bernoulli(phi)$ 分布生成，例如 $P(Z_{i}=1)=phi,P(Z_{i}=0)=1-phi$ ，令 $hatphi=(1/m)sum_{i=1}^{m}{Z_{i}}$ 作為任意變數的平均值，對於任意的 $gamma>0$ ，那麼：

$P(|phi-hatphi|>gamma)leq 2exp(-2gamma^{2}m).$

Hoeffding不等式說明，如果我們將 $hatphi$ 作為 $phi$ 的估計，那麼如果 $m$ 足夠大， $hatphi$ 遠離 $phi$ 的概率就足夠小。比如想估計一個不均勻的硬幣頭朝上的概率 $phi$ ，那麼如果你投擲的足夠多，肯定可以得到一個不錯的概率估計 $hatphi$

採用上面的兩個引理，我們可以證明learning theory中最核心最重要的一些內容。為了簡化我們關注二分類問題 $yinleft{ 0,1 ight}$ ，而我們討論的內容能夠generalize到其他部分，包括回歸問題、多分類問題等。

2.1 訓練誤差VS一般誤差

假設給定訓練集 $S=left{ (x^{(i)},y^{(i)});i=1,...,m ight}$ ，其中訓練樣本 $(x^{(i)},y^{(i)})$ 來自於同一個概率分布 $D$ ，對於一個特定的hypothesis $h$ ，我們定義訓練誤差 training error(也稱為empirical risk或者empirical error)為：

$hatvarepsilon(h)=frac{1}{m}1left{ h(x^{(i)} e y^{(i)}) ight}$

當我們明確是在訓練集 $S$ 上的訓練誤差，則寫為： $hatvarepsilon_{S}(h)$

我們定義generalization error為： $varepsilon(h)=P_{(x,y)sim D}(h(x) e y).$ 表示如果從分布 $D$ 生成一個新的樣本 $(x,y)$ ，hypothesis $h$ 會misclassify的概率。

2.2 經驗風險最小化

考慮線性分類， $h_{ heta}(x)=1left{ heta^{T}xgeq0 ight}.$ 應該怎麼去fit參數 $heta$ 呢？一個好的方法是最小化訓練誤差，並且選擇 $hat heta=argmin_{ heta}hatvarepsilon(h_{ heta}).$

這稱為empirical risk minimization(ERM)，經驗風險最小化，產生的hypothesis是 $hat h=h_{hat heta}$ 。我們將ERM看作最基本的學習演算法，例如邏輯回歸也可以看做風險最小化的近似。

在learning theory的學習中，需要將模型的特定的參數等進行抽象，我們定義一個學習演算法使用的hypothesis class $H$ 為它所可以考慮的所有分類器的集合。對於線性分類來說， $H=left{ h_{ heta(x)}:h_{ heta(x)}=1left{ heta^{T}xgeq0 ight}, heta in R^{n+1} ight}.$ 是所有decision boundary是線形的分類器的集合。更廣泛的講，如果我們研究例如神經網路，我們可以讓 $H$ 做為某些神經網路結構所代表的分類器的集合。

經驗風險最小化可以看作在 $H$ 上的最小化，學習演算法會選擇的假設為：

$hat h=argmin_{h in H}hatvarepsilon(h).$