Learning is Impossible?

Probability to the Rescue

• N: sample數量
• $v$ : sample 裡面的 positive item 機率
• $\mu$ : 實際上的 positive item 機率
• $\epsilon$ : 自訂的 $v$ 與 $\mu$ 差距門檻
• PAC: 有很高的機率差不多是對的

Connection to Learning

• i.i.d.: independently and identically distributed

最後的問題沒懂

Connection to Real Learning

不好的資料

• $E_{in}$ 跟 $E_{out}$ 差很多

假設

• 資料集有 $D_1$ 到 $D_{5678}$ 這麼多種
• Hypothesis set 有 $h_1$ 到 $h_M$ 這麼多種

那麼

• 只要 $D_n$ 這個資料集 使得Hypothesis set中的其中一個 $h_m$ 的 $E_{in}$ 跟 $E_{out}$ 差很多, 我們就說這個資料集$D_n$ 是不好的資料集

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

總結

作業一

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 ˊˋ