---
# System prepended metadata

title: Ch4 Feasibility of Learning
tags: [機器學習基石上：數學篇]

---

---
tags: 機器學習基石上：數學篇
---

Ch4 Feasibility of Learning
===


## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)



## [Learning is Impossible?](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/ytNk2/learning-is-impossible)

### Learning 可能是辦不到的
![](https://i.imgur.com/mN05eY1.png)
- 因為我們不知道 true function $f$ 在資料以外長什麼樣子，所以不論我們以何種方式推斷，結果都有可能和 true function 不同，也就是我們其實沒有「learn」到東西

### No Free Lunch
![](https://i.imgur.com/fyiQxIu.png)
- 我們已經看過 $D$ 有 5 個 data point
- 就算我們從 hypothesis set 中找到一個 $g$，它在 $D$ 中的輸出都和 $f$ 相同，但根據不同的 $f$，$g$ 在 $D$ 以外的地方，很可能輸出和 $f$ 不同或者相同，平均而言就是 $g$ 沒有學到任何東西
- 若我們只是讓算法找到 $g$ 在 $D$ 上做得好，其實沒辦法說 $g$ 在 $D$ 以外到底做得好還是不好，若要有辦法說的話，就要加上一些假設
- 若只堅持 true function $f$ 是不知道的，那麼我們就沒辦法 learn 到東西。


## [Probability to the Rescue](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/2cbIS/probability-to-the-rescue)


### Statistics 101: Inferring Orange Probability
![](https://i.imgur.com/J5yzMmX.png)
- $\nu$ : sample 裡面的 positive item 機率 (已知)
    - in-sample
- $\mu$ : 實際上的 positive item 機率 (未知)
    - out-of-sample

### Possible v.s. Probable
![](https://i.imgur.com/sMsyChX.png)
- 「大致上」來說，$\nu$ 會和 $\mu$ 很接近

### Hoeffding's Inequality
<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/HoeffdingsInequality.jpg) -->
![](https://i.imgur.com/BaWelGB.png)

- $N$: sample數量
- $\epsilon$ : 自訂的 $v$ 與 $\mu$ 差距門檻
- **PAC：有很高的機率差不多是對的**
    - probably 有很高機率
        - 機率為 $1-2\exp(-2\epsilon^2N)$
    - approximately 差不多 
        - 誤差小於 $\epsilon$


![](https://i.imgur.com/E1dpxDG.png)
- 若 $N$ 越大，或者我們放寬能接受的誤差 $\epsilon$，則 $\mathbb P[|\nu-\mu|>\epsilon]$ 就越小，也就是 $\mathbb P[\nu\approx\mu]$ 會越大


![](https://i.imgur.com/e07RhiJ.png)
- $\mathbb P[|\nu-\mu|>0.3] = 0.33$
    - ***奇怪難道不用除以 2 嗎? $\nu\leq0.1$ 應該只佔了一半才對呀? 另一半是 $\nu\geq 0.7$ 不是ㄇ***
        - 可以參考論壇 [討論](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/discussions/weeks/4/threads/jzXAbrj6EemYkQrKkuKfCg) 

![](https://i.imgur.com/KtHu6sg.png)

## [Connection to Learning](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/XCaz0/connection-to-learning)

### 剛剛講這麼多，跟 learning 的關係是什麼?
![](https://i.imgur.com/TzgKYwt.png)
- 左右可一一對應
    - 一顆彈珠 = 一筆資料
    - 橘色彈珠 = h 判斷錯的一筆資料 ($h(x_i)\neq f(x_i)$)
    - 綠色彈珠 = h 判斷正確的一筆資料 ($h(x_i)=f(x_i)$)
    - 從罐子裡 sample 出一把彈珠並檢查橘色比例 = 從母體 sample 出一個 dataset $D$ 並檢查 $h$ 錯誤率
    - 我認為
        - 罐子裡的所有彈珠 = 資料的母體
        - 罐子本身(會替彈珠上顏色) = 某固定的 hypothesis
- 注意這裡的 $h$ 必須是固定的，不能一下用這個 $h_1$ 來看彈珠顏色，一下用那個 $h_2$ 來看彈珠顏色
    - 就像我們必須從同一個罐子裡抽彈珠出來一樣，不能一下從這個罐子抽，一下從那個罐子抽
- 不考慮 noise 的話，資料中的 $y_n$ 其實就是 $f(x_n)$
- i.i.d.: independently and identically distributed


### Added Components
![](https://i.imgur.com/cIW4Epq.png)
- 這裡多了兩個東西，$E_{in}$ 和 $E_{out}$
    - $E_{in}$ 相當於剛剛的 $\nu$
        - 也就是從罐子 sample 出來，橘球的比例
    - $E_{out}$ 相當於剛剛的 $\mu$ (unknown)
        - 也就是整個罐子中實際上橘球的比例

![](https://i.imgur.com/6Ryrm8G.png)
- 既然如此，我們就可以直接把 $\nu$ 代換成 $E_{in}$、把 $\mu$ 帶換成 $E_{out}$，得到公式 $\mathbb P[|E_{in}-E_{out}|>\epsilon]\leq 2\exp(-2\epsilon^2 N)$


### Verification of One $h$
![](https://i.imgur.com/lOWgD8W.png)
- 然而，我們剛剛所有一切的推導都是建立在「只有一個 hypothesis $h$」所算出來的機率
- 但實際上，我們需要從 hypothesis set 的 $\{h_1,...,h_M\}$ 裡面挑出一個最好的 $g$，那麼就不在剛剛的 PAC 的保證範圍
- *Q: 也許可以想成，一個 $h$ 有 0.9 的機率是對的，那從 10 個 $h_i$ 中挑出隨便一個，**都會是對的機率就只有 $0.9^{10}\approx 0.349$ ?***


![](https://i.imgur.com/2KtXbP5.png)
- ***不是很確定這裡說的東西跟前面的差別***


![](https://i.imgur.com/6MeCkqY.png)


## [Connection to Real Learning](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/qlkBl/connection-to-real-learning)

### Multiple $h$
![](https://i.imgur.com/TT5lAIS.png)
- 假設現在演算法從 hypothesis **set** 裡面挑出了 $E_{in}$ 最低的(圖右一)，那它就有很高機率 $E_{out}$ 最低嗎?
- 答案是不會的，因為就算你所有的 $h_i$ 都是隨便亂猜，當 $h$ 的選擇一多，就很有可能有幸運全都猜對的 $h$，結果我們卻選了它
- 下面以硬幣舉例

### Coin Game
![](https://i.imgur.com/SO0vJNt.png)
- 銅板就是彈珠就是我們手上的資料



### BAD Sample and BAD Data
![](https://i.imgur.com/8qg6Jha.png)
- 不好的資料表示 $E_{in}$ 跟 $E_{out}$ 差很多
- 再強調一次，Hoeffding 保證的是，在上表的一個 row 當中，BAD 佔的格數沒有很多格


### BAD Data for Many $h$
<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/badData01.jpg) -->
![](https://i.imgur.com/9bYHI4M.png)
- 不好的資料：
    - 演算法選了一個 $E_{in}$ 最小的 $h$，結果選到雷 ($E_{in}$ 和 $E_{out}$ 差很多)，那就是不好的資料
    - 也就是說，只要$D_n$ 這個資料集 使得Hypothesis set中的其中一個 $h_m$ 的 $E_{in}$ 跟 $E_{out}$ 差很多, 我們就說這個資料集$D_n$ 是不好的資料集
- **而我們想要知道，不好的資料發生的機率到底是多少？**


<!-- ![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/badData02.jpg) -->
![](https://i.imgur.com/8ZQ7Hsb.png)
- 假設 Hypothesis set 有M個**不同的** hypothesis, 則資料集是bad的機率 upper bound 為 $2M \exp(-2\epsilon^2N)$
- 也就是說在 Hypothesis set 有限, 且資料集的資料量大的時候, 資料是壞的機率仍然是小的


### Statistical Learning Flow
![](https://i.imgur.com/pWE3LWm.png)


### 這題稍難
![](https://i.imgur.com/O6z5bRN.png)
- 我們可以發現到，$h_1$ 和 $h_3$ 某種程度來說是重疊的；$h_2$ 和 $h_4$ 也是重疊的 (一體兩面)
- 因此我們在做 union bound 的時候，似乎可以只用 2 個 hypothesis 來計算


### 總結
![](https://johnnyasd12.gitbooks.io/machine-learning-ntu/content/assets/w4Summary.jpg)


## [作業一](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/exam/opdrz/zuo-ye)
i dunno if my answer is correct


678全錯

9.
$C_{5}^{10}\times\frac{1}{2}^{10}$

12.
$2exp(-2\times0.8\times0.8\times10)$

13.
$(1/6 * 1/2)^5$
錯

14.
ABCD四種骰子都有1/2的機率是orange
$(1/2)^5$
錯

15~20懶得寫code ˊˋ













