# 2.3 Probably Approximately Correct Learning

如我我們用 tightest 的長方形當作我們的 hypothesis，我們想要知道我們需要多少的 examples。我們想要我們的 hypothesis 「大致上正確」，也就是說 ++error probability 要被某個值給 bound 住++。

在 <font color = "snake">Probably Approximately Correct (PAC) learning</font> 中，給定一個 class $C$、有未知但固定的 probability distribution 的 examples，我們希望能找到 ++examples 的個數 <font color = "green">$N$</font>++，使得：

:::success
對任意的 $\delta<{1\over2}$、$\epsilon>0$
機率至少是 $1-\delta$ 的情況下，hypothesis $h$ 的 error 最多只有 $\epsilon$
:::
> 超過一半以上的機率，錯誤不超過某個大於零的 $\epsilon$


舉例來說：


像前面說的，我們用所有可能的長方形中最 tight 的（$S$）當作我們的 hypothesis（$h$），所以 error region 就是介於 $C$ 和 $h=S$ 之間的上下左右四塊長方形的和。

我們希望去確認說發生 error，也就是有某個 positive example 落到這四塊長方形的機率不超過 $\epsilon$。所以如果我們可以保證說這四塊長方形每塊的 error 都被 bound 在 $\epsilon \over 4$，那也就代表整體的 error 不超過 $4 \times {\epsilon \over 4}=\epsilon$，並且因為我們四個角落都算了兩次，所以實際上的 error 就會比 $4 \times {\epsilon \over 4}$ 還要小。

如果我們 randomly 加入一個 example，它沒有落到圖中那個 shaded 的長方形的機率會是 $1-{\epsilon \over 4}$

$\rightarrow$ 如果我們隨便抽 $N$ 個 independent 的 example，沒有落到同樣這個長方形的機率就是 $(1-{\epsilon \over 4})^N$

$\Rightarrow$

:::danger
（p.29 待補）
:::