? ? ? ? ? ? 向杜少致敬!?

Lecture 4: Feasibility of Learning

?

4.1. Learning is Impossible?

　?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖 4-1

?Q1：在訓練集 （in-sample） 能找到一個 g ≈ f, 但是你不能保證在應用數據 （out-sample）還有 g ≈ f 。

?Q2：就算在某種約束下，你能保證在應用數據 （out-sample） g ≈ f。 如果我有多個 g ≈ f， 即 g_1?≈ f、g_2?≈ f、g₃≈?f、… g_n?≈ f。 如何找到在 out-sample 上性能最好的 g_opt?呢？

?

4.2. Probalility to the Rescue

? ? learning 是做不到的！但是我們可以想一下，有沒有學習用少量的已知的事實去推測整個樣本的情況？ 現在給你一個罐子，你能給出黃綠彈珠所占的比例是多少？?假設黃綠彈珠的分布較均勻，可以通過抽樣的方法獲取黃綠彈珠的比例。

? ? ? ? ? ? ? ? ? ? ? ? ?圖 4-2

? ? ? ?假設在抽出的樣本中 orange marble 的比例是 v， green marble 的比例是 1 -v。 罐子中的 orange marble 的比例是 μ， green marble 的比例是 1-μ。

v 和 μ 基本不相同，那要在什么樣的條件下？ v 和 μ 才能足夠的接近？在數學中有個?Hoeffding's Inequality 能刻畫出 v 和 μ 的接近程度。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $$ \mathbb{P} [|\nu -\mu |] \leqslant 2 exp(-2\epsilon^2N)? $$

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?公式 4-1

? ? ? Hoeffding 不等式的良好性質：

　　? ?? 1. 只和 N、ε有關，和 μ、ν 無關

? ? ? ? ? ? 2. N 越大或 ε 越大， v 和 μ?大概近似正確（probably approximately correct PAC）

?

Q3：HOeffding 不等式和切比雪夫不等式的關系？

Q4：回憶一下以前學過的中心極限定理、大數定理

?

4.3. Connection to Learning

? ? ? ?上一節，我們一直在玩彈珠游戲。這個和機器學習有什么關系呢？

假設我們有一罐白色彈珠，? 這些彈珠有某些性質。我們準備用機器學習去預測這些彈珠的性質。 假設我們有個 g， 如果 g(x) = f(x) 則將彈珠染綠并放到罐子 B 中， 如果 g(x) != f(x) 則將彈珠染黃并放到 B 中。最終我們會得到罐子 B 會如下圖所示。

? ? ? ? ? ? 圖 4-3

? ? ? ?現在有一罐裝滿黃綠彈珠的罐子， orange marble 代表我們預測這個 marble 時出錯了， green marble 代表我們成功地預測這個 marble。 這樣就回到上一節。

現在，我們可以保證在 in-sample 上 g 和 f 的 pac 近似。 但是我們不能保證 g 和 f 的差別不大。 如果說 orange marble 的出現概率在 in-sample 和 out-sample 是 pac 近似正確，但是 orange marble 的比例很大。這也不是我們想要的， orange 出現比例越大說明 g 越不準確。而且我們是用一個固定的 g ，沒有學習的過程。不能算是學習，當然也不會是機器學習

?

4.4. Connection to Real Learning

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖 4-4

? ? ? 4.3 節時，我們不能保證選取那一個 h 和 f 足夠的接近，我們將所有的 h 拿出來給白色罐子染色。假設我們對某個罐子 sample 出來的 marble 全是 green。是不是就可以說這個罐子對應的 h 就是我們想要的？

因為有 Hoeffding 不等式，從直覺上來說這應該是對的。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖 4-5

? ? ?假設有150個人同時丟五次硬幣，統計其中有一個人丟出五次全部正面向上的概率是多少，不難得出一個人丟出五次正面向上的概率為 1/32。在 150 人有一個人投出全是正面的概率為 1 - (31/32)¹⁵⁰ > 99%。

這說明在圖 4-5 中，某個罐子中 sample 出來的 marble 全是 green。也不能說明這個罐子對應的 h 是好的。我們將這種 E_in? 和 E_OUT? 差別很大的 sample 起個新名字 —— BAD SAMPLE。現在我們引入一個新的 concept BAD DATA， 以及簡單地看下它的性質（也就是看圖不說話）

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖 4-6

? ? ? 將每次抽樣的數據集稱做 DATA， 如果在這個 DATA 上E_in? 和 E_OUT??far away， 我們稱之為 BAD DATA。 根據 Hoeffding 不等式，BAD DATA 出現概率非常的小。

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖 4-7

? ? ? ? ? 如果某個 DATA 在某個 h 表現不好， 就將 DATA 標記為 BAD。現在我們想知道在整個 hypothesis??空間上，踩到雷的概率上限是多少？

在 hypothesis 有 M 個h，那么可以得出踩雷的上限如公式 4-2 所示

?

? ? ? ? ? $$ \mathbb{P_\mathcal{D}} [BAD? \mathcal{D}]?\leqslant 2 exp(-2\epsilon^2N) + 2 exp(-2\epsilon^2N) + ... +?2 exp(-2\epsilon^2N) = 2M exp(-2\epsilon^2N)?$$? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?公式 4-2

? ? ? ?如果 M 是有限的，??E_in? = E_OUT?是 PAC， 和具體的 hypothesis 無關。在這種情況下，學習策略是選擇 E_in 最小的 g。對于有無限 hypothesis 的討論在未來的課程。

_?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

題外話：

? ? ? 本文中提到了 PAC， 可以參考一下《西瓜書》上面的討論。里面有恰 PAC 可學習、PAC 不可學習等幾個概念和證明（具體忘了）。后續筆記還有 pac 理論的升級版 ---- VC 維

? ? ? 4.3 節 Connection to Learning 是按照自己寫的，沒有嚴格跟著 ppt 走。

? ? ? Q1 ： 本文部分地回答了 Q1 問題，即有限假設空間下我們能 PAC 保證 g ≈ f

? ? ? Q2： Q2 問題算是機器學習中終極問題，涉及到的概念有 bias、variance、欠擬合、過擬合等。不容易回答

? ? ? Q3： 從圖 4-8 可以看出，切比雪夫不等式刻畫的是 期望、ε 間的關系??

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? 圖 4-8

? ? ? ?Q4： 我所接觸過的大數定律有三個，分別是切比雪夫大數定律、伯努力大數定律（見圖 4-9）、辛欽大數定理 （見圖 4-10）。

? ? ? ? ? ? ? ? ? ? ? 圖 4-9

? ? ? ? ? ? ? ?圖 4-10

? ? ? 中心極限定理的啥，后續補上吧

?

轉載于:https://www.cnblogs.com/tmortred/p/8046440.html

總結

以上是生活随笔為你收集整理的机器学习基石4-在何时才能使用机器学习（4）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。