---
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 可能是辦不到的
- 因為我們不知道 true function $f$ 在資料以外長什麼樣子，所以不論我們以何種方式推斷，結果都有可能和 true function 不同，也就是我們其實沒有「learn」到東西

### No Free Lunch
- 我們已經看過 $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
- $\nu$ : sample 裡面的 positive item 機率 (已知)
- in-sample
- $\mu$ : 實際上的 positive item 機率 (未知)
- out-of-sample

### Possible v.s. Probable
- 「大致上」來說，$\nu$ 會和 $\mu$ 很接近

### Hoeffding's Inequality
<!--  -->

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

- 若 $N$ 越大，或者我們放寬能接受的誤差 $\epsilon$，則 $\mathbb P[|\nu-\mu|>\epsilon]$ 就越小，也就是 $\mathbb P[\nu\approx\mu]$ 會越大

- $\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)


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

### 剛剛講這麼多，跟 learning 的關係是什麼?
- 左右可一一對應
- 一顆彈珠 = 一筆資料
- 橘色彈珠 = 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
- 這裡多了兩個東西，$E_{in}$ 和 $E_{out}$
- $E_{in}$ 相當於剛剛的 $\nu$
- 也就是從罐子 sample 出來，橘球的比例
- $E_{out}$ 相當於剛剛的 $\mu$ (unknown)
- 也就是整個罐子中實際上橘球的比例

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

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

- ***不是很確定這裡說的東西跟前面的差別***


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

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

### Coin Game
- 銅板就是彈珠就是我們手上的資料

### BAD Sample and BAD Data
- 不好的資料表示 $E_{in}$ 跟 $E_{out}$ 差很多
- 再強調一次，Hoeffding 保證的是，在上表的一個 row 當中，BAD 佔的格數沒有很多格

### BAD Data for Many $h$
<!--  -->
- 不好的資料：
- 演算法選了一個 $E_{in}$ 最小的 $h$，結果選到雷 ($E_{in}$ 和 $E_{out}$ 差很多)，那就是不好的資料
- 也就是說，只要$D_n$ 這個資料集 使得Hypothesis set中的其中一個 $h_m$ 的 $E_{in}$ 跟 $E_{out}$ 差很多, 我們就說這個資料集$D_n$ 是不好的資料集
- **而我們想要知道，不好的資料發生的機率到底是多少？**

<!--  -->
- 假設 Hypothesis set 有M個**不同的** hypothesis, 則資料集是bad的機率 upper bound 為 $2M \exp(-2\epsilon^2N)$
- 也就是說在 Hypothesis set 有限, 且資料集的資料量大的時候, 資料是壞的機率仍然是小的

### Statistical Learning Flow

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

### 總結

## [作業一](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 ˊˋ