Machine Learning Foundation

前一講提到了無論是 stochastic noise 或是 ground truth 過複雜而引進的 deterministic noise ，對本身就複雜 (VC dimension 高) 的 model 而言，overfitting 是很容易發生的，而解決之道其一就是這一講所要介紹的 Regularization。

上一講提到了利用 nonlinear transform 來處理 data 並不 linear separable 的情形，讓 ML model 具備了更強的 fitting 能力，但在這麼做的同時，也提高了 hypothesis set 的 VC dimension，使得 model 的 complexity 增加，變得不容易 generalizaion ，而這也是這一講要探討的 overfitting 。

在此之前，針對 linear separable 的 data ，我們利用找可以切分這些數據點的 hyper-plane 來做 classification (或 regression )。但這個強大的假設並不適用於每筆真實世界中的 data ，所以我們勢必得處理 non-linear 的問題。換句話說，我們希望 hypothesis set 中可以包含更多的候選人（可以 match nonlinear 特性的那些 function ），同時去驗證在這樣的情況下，學習依然是可行的。

總結目前學到的 3 個 linear model。

Linear Model 的核心在於 feature 分量的 weighted sum $\mathbf{w}^T \mathbf{x}$， 在 binary classification ，我們用 step function 將其二分 ($\mathcal{Y} = \lbrace , -1,1,\rbrace$)，而在 linear regression 中，我們將其直接作為輸出。而這一講要介紹的則是將 $\mathbf{w}^T \mathbf{x}$ 通過一個 nonlinear function mapping 到[$0,1$]，賦予他機率的意義 ($\Pr[y = +1 | \mathbf{x}]$)。

在前幾講的討論中，我們討論了 binary classification 的問題，及這個問題在機器學習上的可行性。但很多時候，我們不希望機器只會說是或不是，亦即不希望它的 output space $\mathcal{Y}$ 只是單純的 {$1, -1$}。舉例來說，給定一些資料，請你預測明天的股價，除了想預測會漲或會跌之外，到底漲多少或跌多少也是我們有興趣知道的事情，而這也是接下來兩講想解決的事情 - Regression。

前面幾講的討論中，我們都假設有一個 ground truth function $f$ 去 generate data，且我們所拿到的 $\mathcal{D}$ 是乾淨的，然而在真實世界中，無可避免地會遇到 noise 加在 data 上，如此情況下 learning 是否還是可行？ (VC bound 是否還是 work ?) 另外，前方討論時，我們都以 0/1-error 作為衡量 model 好壞的 metric，如果換成不同的 metric 呢？

於前一講中，我們證明了 growth function 為 POLY(N) iff break point 存在，而這件事可以說明在 training data 上的表現不會和 testing data 差的太多 $E_i(h) \approx E_o(h)$ (if 數據點夠多 $N$ )。而這一講中，我們由 break point 引進 VC Dimension $d \scriptscriptstyle VC$ ，來當作衡量 $\mathcal{H}$ 複雜度的一個指標。

前一講中講述了 break point 的存在，壓制了 growth function $m_H(N)$ 的成長速度，於這一講中，我們想嚴格地說明只要存在 break point ，$m_H(N)$ 便會是 POLY(N) 。

上一講提到了在 hypothesis set $\mathcal{H}$ 為有限，且sample size $|\mathcal{D}|$ 足夠大的情況下，是 PAC-learnable 的。但當 $|\mathcal{H}| , \rightarrow , \infty$的時候呢？ (e.g 2D linear perceptron)

這一講要討論的是機器學習真的是可行的嗎？能推廣到所有 scenerio 嗎？或是只有部份？是否需要某些假設才能證明可行呢？

這講建構了一個大略的 ML 世界觀。

於前一講講述了 ML 的 framework ，於這一講中，我們會利用一個簡單的 learning model ， 去解決 binary classification 的問題。

其實是大一升大二的暑假，閒來無事找的開放式課程，那時也做了一些筆記，沒想到兩三年過後，自己做專題也走向了這個領域XD，於是順手把它整理上來囉！