林軒田機器學習基石筆記 - 第五講、第六講

發表於 更新於 分類於 ， 閱讀次數： Disqus：

  • 本文為一系列課程之筆記，建議從" 機器學習基石筆記-1 "開始閱讀

  • 本文討論內容請參考: 機器學習基石第五講 : Training versus Testing 機器學習基石第六講 : Theory of Generalization

  • 本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義

回顧上一篇的結論，只要 Hypothesis set \(\mathbb{H}\) 是有限集 (#\(\mathbb{H}=M\) is finite)，且dataset \(\mathbb{D}\) 有夠多的資料(#\(\mathbb{D}=N\) is large enough)，我們就能確定 :

\(\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)\) 有一個很小的上界\(2Me^{-2\epsilon^2N}\)

\(\implies E_{out}\)與 \(E_{in}\) 夠接近 ( Learning Algorithm 從 \(\mathbb{H}\) 選出來的 \(g\) ，\(E_{out}(g)\)與 \(E_{in}(g)\) 夠接近 )

\(\implies E_{in}(g) \rightarrow 0\) 則 \(E_{out}(g) \rightarrow 0\)

那我們現在有兩個問題要解決 :

  1. \(2Me^{-2\epsilon^2N}\)這個上界夠好嗎?
  2. 如果 \(\mathbb{H}\) 是 \(infinite\ set\) ?

這兩個問題其實是一體兩面，解決了一個，另外一個也就能順利解決。 我們能不能找到一個足以代表 \(infinite\ \mathbb{H}\) 的一個 \(finite\ number\ -m_{\mathbb{H} }\) 替換掉 \(M\) ，形成一個更逼近的上界，也可以處理 \(infinite\ \mathbb{H}\)沒有上界的情況 ?

\(2Me^{-2\epsilon^2N}\)這個上界夠好嗎?

這是一個簡單的文式圖，如果我們今天要算 \(B_1\cup B_2\cup B_3\) 數量的上界，最簡單的莫過於直接把三者數量相加， \(B_1+B_2+B_3\) 絕對是 \(B_1\cup B_2\cup B_3\)的其中一個上界，但我們也很清楚的知道，當三者重疊部分越多，這樣的上界越不逼近。

但在上一篇的證明中，我們卻利用這樣的方法找出其上界

當 \(M\) 為 \(finite\) 時還行得通，反正我們只要確定有上界即可逼近，但當 \(M\) 為 \(infinite\) 時就會出現很大的問題。

### 如果 \(\mathbb{H}\) 是 \(infinite\ set\) ?

在處理這個問題以前，我們先定義一些概念: * dichotomy 以 \(\mathbb{R}^2\) 為例，在其中有\(N\)個資料點 \(\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N\)，則顯然的能將這 \(N\)個資料點進行二元分類的 \(\mathbb{H}\) 是一個 \(infinite\ set\) (任何一條在 \(\mathbb{R}^2\) 的直線都是一個 \(h\))。 從數學的角度來說， \(dichotomy\) 代表的是一個族 ( \(family\) )，就 hypothesis \(\mathbb{H}\) 來看，若把對 \(\mathbb{X}_1,\mathbb{X}_2,...,\)family\(\mathbb{X}_N\) 進行同一種分類的 \(h\) 視為同一族，那麼我們便可以將無限多的 \(h\) 變成有限個 \(dichotomies\)。

  • Growth Function \(m_\mathbb{H}(N)\) : \(\mathbb{H}\rightarrow\mathbb{R}^1\) \(m_\mathbb{H}(N)=\max\limits_{\forall x_i\in\chi}(\mathbb{H}(\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N ))\)，這函數白話一點來說，就是所有的 \(h\) 到底可以把資料點做出多少種不同的二元分類。在 Machine Learning 的討論中，\(N\) 都是有限正整數，那麼\(m_\mathbb{H}(N)\)出來的值也必然會是有限正整數 ( \(\leq2^N\) )1

  • shatter 我們說 \(\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N\) 可以被 \(shatter\) \(\implies m_\mathbb{H}(N)=2^N\) (所有的分類情況都會發生)。所以在 \(\mathbb{R}^2\) 情況下，\(\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N\) 可以被 \(shatter\) (當 \(N\leq3\))

    \(Mathematical\ \ \ Definition\ :\) \(C\ shatters\ A\ \ if\ \ \forall a\in A，\exists c\in C\ \ s.t\ \ a=c\cap A \\ i.e.\ \mathbb{P}(A)=\left\{ c\cap A \mid\ c\in C\right\}\)

  • Break Point 第一個不會被 \(shatter\) 的 \(N\)，在 \(\mathbb{R}^2\) 情況下，\(break\ point=4\) > Break Point是一項很重要的指標，代表著當 \(N>Break\ Point\) 時，整個成長會大幅趨緩 ( \(O(N)\ll 2^N,when\ N>Break\ Point\) )。

  • Big O ( Time complexity 、成長速度、無限大漸進概念)

    \(Mathematical\ \ \ Definition\ :\) \(Given f(x),g(x)\ \ \\\exists\ M,x_0\ \ \forall\ x\geq x_0\ \ s.t.\ \mid f(x)\mid\leq M\mid g(x)\mid \\\implies\ f(x)\in O(g(x)) \ or\ f(x)=O(g(x))\)

資料空間 &分類型態2 Break Point \(m_\mathbb{H}(N)\) O(N)
1-D Positive ray 2 N+1 \(O(N)\)
1-D Positive interval 3 \(\frac{1}{2}N^2+\frac{1}{2}N+1\) \(O(N^2)\)
Convex Set \(\infty\) \(2^N\) -
2-D Perceptron 4 \(<2^N\) (in some cases) \(O(N^3)\)

  • Bounding Function \(B(N,K)=\max\limits_{N>K}(m_{\mathbb{H} }),\ where\ K=Break\ Point\) 這樣看起來還是有點抽象，我引用林軒田與Yaser S . Abu-Mostafa所著的 " Learning From Data " 一書的說法比較清楚 : \[B (N, k)\ is\ the\ maximum\ number\ of\ dichotomies\\ on\ N\ points\ such\ that\ no\ subset\ of\ size\ k\ of\ the\ N\ points\ can\ be\ shattered\\ by\ these\ dichotomies.\] 在討論Bounding Function時，我們已經不管分類的型態是什麼，單純只看Break Point K為多少。(1-D perceptron 或是 1-D positive ray K值都是3)

    (這邊在課堂上都保守的以 \(\leq\) 表示，但實際上有更強的 \(=\) 關係)

    從上圖我們可以發現Bounding Function的幾個重要性質3 : \[B(N,K)=B(N-1,K)+B(N-1,K-1)\] \[m_\mathbb{H}(N)\leq B(N,K)\]

現在所有的工具都準備好了，我們該準備來面對上面的問題了~ 為了避免因為 \(infinite\ \mathbb{H}\) 而造成的上界快速擴張狀況，我們用\(m_\mathbb{H}(N)\)來取代原本的 \(M\) 最後可以得到一個比較逼近的上界4 : \[\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)\leq 4m_\mathbb{H}(N)e^{\frac{1}{8}\epsilon^2N}\] 我們稱之為 \(Vapnik-Chervonenkis Bound\ (VC\ Bound)\)

結論

\(\mathbb{P}(\mid E_{in}(g)-E_{out}(g)\mid>\epsilon)\) \(\leq 4m_\mathbb{H}(2N)\cdot e^{-\frac{1}{8}\epsilon^2N}\) \(\leq 4(2N)^{K-1}\cdot e^{-\frac{1}{8}\epsilon^2N}\ ,\ if\ N\ is\ large\ enough\ and\ K\ exists.\) (\(\because m_\mathbb{H}(N)\leq B(N,K)\leq N^{K-1}\))

\(\therefore\)存在 \(Break\ point\) 且 \(N\) 夠大的情況下，即使 \(infinite\ \mathbb{H}\)，演算法從\(E_{in}\)很小的條件下挑出一個 \(g\)，都一定會有一個有限上界可以確保\(E_{in}\)跟\(E_{out}\)夠接近。

註釋

\(\because B(N,K)=\sum\limits_{j=0}^{K-1}{ {N}\choose{j} }={ {N}\choose{0} }+{ {N}\choose{1} }+{ {N}\choose{2} }+...+{ {N}\choose{K-1} }\\ ={ {N}\choose{0} }+({ {N-1}\choose{1} }+{ {N-1}\choose{0} })+({ {N-1}\choose{2} }+{ {N-1}\choose{1} })+...+({ {N-1}\choose{k-1} }+{ {N-1}\choose{k-2} })\\ ={ {N-1}\choose{0} }+({ {N-1}\choose{1} }+{ {N-1}\choose{2} }+..+{ {N-1}\choose{k-1} })+({ {N-1}\choose{0} }+{ {N-1}\choose{1} }+..+{ {N-1}\choose{k-2} })\\ =\sum\limits_{j=0}^{K-2}{ {N}\choose{j} }+\sum\limits_{j=0}^{K-1}{ {N-1}\choose{j} }\)

PS: \(E_{in},E'_{in}\ and\ E_{out}\)，其實就是個別代表著實務上的 \(E_{train},E_{val}\ and\ E_{test}\)

Step2 : 當\(N\)足夠大時，\(E_{in}(E'_{in})\)的整體分布狀況會近似於以\(E_{out}\)為中心的常態分佈，\(E_{in}\)越往右跑，\(E'_{in}\)會越往左靠

\(\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\) \(\geq\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\ and\ \sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\) \(=\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\times\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\ \ \mid \ \sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\)

\(\therefore\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq(1-2e^{-2({\frac{\epsilon}{2} })^2N})\times\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\)

Step3 : W.L.O.G assum : \(e^{\frac{1}{2}\epsilon^2N}< \frac{1}{4}\) (if not ,VC BOund 顯然為真) \(\therefore\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq\frac{1}{2}\times\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\) \(\therefore 2\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\)

Step4 : 現在整個母體的機率已經被我們用\(D\ and\ D'\)限制住 \(\mathbb{P}(\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\) \(\leq2\mathbb{P}(\sup\limits_{h\in\mathbb{H} }\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\) \(\leq 2\sum\limits_{h\in\mathbb{H} }\mathbb{P}(\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\) \(=2m_\mathbb{H}(2N)\times\mathbb{P}(\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\mid)\) (\(\because\)把\(D,D'\)作為一個母體來看) \(=2m_\mathbb{H}(2N)\times\mathbb{P}(\mid E_{in}(h)-\frac{E_{in}(h)-E'_{in}(h)}{2}\mid>\frac{\epsilon}{2})>\frac{\epsilon}{4}\mid)\) (\(\because E_{in}(h)-E'_{in}(h)<\frac{\epsilon}{2}\implies\frac{E_{in}(h)-E'_{in}(h)}{2}<\frac{\epsilon}{4}\implies E_{in}(h)-\frac{E_{in}(h)}{2}-\frac{E'_{in}(h)}{2}<\frac{\epsilon}{4}\)) \(\leq 2m_\mathbb{H}(2N)\cdot 2\cdot e^{-2e^{-2({\frac{\epsilon}{2} })^2N} }\)(\(\because\)針對單一\(h\)，所以\(M=1\)) \(=4m_\mathbb{H}(2N)e^{-\frac{1}{8}\epsilon^2N}\)得證

  1. 為什麼 \(m_\mathbb{H}(N)\) 不一定會等於要取 \(\max\) ? 為什麼不等於\(2^N\)? 從排列組合的觀點來看，\(N\) 個點的二元分類應該要有 \(2^N\) 種，但我們這裡要的是 \("Linear\ separable"\) 所以會有所差異。 從上圖可以看出來，\(N=4\) 時，應該會有16種二分法，但是由於我們要求線性可分，因此一定「至少」有兩種 ( 圖中打 X 的狀況以及其對稱情況 )不符合我們的需求。 為什麼是「至少」? 如果這 \(N\) 筆資料有特別的排列情況(EX:共線)，當然有可能有更多種狀況會被排除，但，\(m_\mathbb{H}(N)\)函數要的是「max」，也就是說我現在要看的是被排除最少的情況，所以在 \(N=4\) 時，\(m_\mathbb{H}(4)=14\) ( 那兩種被排除的狀況，就是不管四筆資料怎麼分布，絕對都會被排除 ) 當然，\(m_\mathbb{H}(N)\)也會跟資料本身處的維度空間有關。↩︎

  2. 林軒田教授在課堂上講了四種的資料空間及分類型態 : 2-D Preceptron , 1-D Positive Ray , 1-D Positive interval and Convex Set↩︎

  3. 試證明 \(B(N,K)=B(N-1,K)+B(N-1,K-1)\) Claim:\(B(N,K)=\sum\limits_{j=0}^{K-1}{ {N}\choose{j} }\) Proof : \(B(N,K)\\=2^N-{ {N}\choose{K} }-{ {N}\choose{K+1} }-...-{ {N}\choose{N} }\\={ {N}\choose{0} }+{ {N}\choose{1} }+{ {N}\choose{2} }+...+{ {N}\choose{K-1} }\\=\sum\limits_{j=0}^{K-1}{ {N}\choose{j} }\) \(B(N,K)\)的最高次項為\(N^{K-1}\) 因為最後一項為\(\frac{N(N-1)(N-2)...(N-K+1)}{K!}\)↩︎

  4. 證明 \(\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)\leq 4m_\mathbb{H}(N)e^{\frac{1}{8}\epsilon^2N}\) Proof : Step1 : Assume \(D'\) iid with \(D\) is a data set with size N (ghost data) (若\(E_{in}\)與\(E_{out}\)離得很遠，則\(D\)裡面N筆資料大多沒選到error點，那母體種再取N個點(\(D'\))就會包含比較多的error，\(E'_{in}\)與\(E_{out}\)就會有較大機率會比較靠近)↩︎