Week 4 : Feasibility of Learning

  • No Free Lunch :
    • 在驗證$g$的時候，如果是用原本的 $\mathcal{D}$，那很容易的說明${g} \approx \mathsf{f}$
    • 但是如果資料是用$\mathcal{D}$以外的資料來驗證，那我們無法明確說明${g} \approx \mathsf{f}$
      • 而我們真正希望的是 : $g$在 $\mathcal{D}$以外的資料也$\approx \mathsf{f}$
  • Hoeffding’s Inequality :
    • 假設母體機率為$\mu$，樣本機率為$\nu$
    • 結論 : 當樣本數$N$很大時，$\nu$ is probably close to $\mu$ (within $\epsilon$ : 可接受之誤差)
    • 公式 : $\Bbb{P}[|\nu - \mu| > \color{red}{\epsilon}] \le 2exp(-2 \color{red}{\epsilon}^2 \color{blue}{N})$
    • 當$\nu = \mu$時，可以稱為Probably Approximately Correct(PAC)
    • 所以計算時只需$\nu$與$\epsilon$即可，無須知道$\mu$
  • 應用於Learning中
    • 對於任一固定$h$，可以probably藉由已知$E_{int}(h)$，推論出未知$E_{out}(h)$
      • $E_{in}(h)=\frac{1}{N}\sum_{n=1}^{N} [h(x_n) \neq y_n]$
      • $E_{out}(h)=\epsilon_{x\sim P} [h(x) \neq f(x)]$
  • 結合 : $\Bbb{P}[|E_{in}(h) - E_{out}(h)| > \color{red}{\epsilon}] \le 2exp(-2 \color{red}{\epsilon}^2 \color{blue}{N})$
  • 當$E_{out}(h)=E_{in}(h)$時，即為PAC
  • 當$E_{out}(h) \approx E_{in}(h)$時 :
    1. 若$E_{in}(h)$很小(對於固定$h$)，且$\mathcal{A}$挑該$h$當$g$，則可說$g=f$ PAC
    2. 若$\mathcal{A}$強迫該$h$當$g$，$E_{in}(h)$通常不會太小，則可說$g \neq f$ PAC
  • 結論 :
    1. 若$\mathcal{H}$的數量$M$為有限個，且$N$足夠大，則不論$\mathcal{A}$挑了哪個$g$，皆是$E_{out}(g) \approx E_{in}(g)$
    2. 若$\mathcal{A}$挑了一個$g$，其$E_{in}(g) \approx 0$，則可以說PAC保證$E_{out}(g) \approx 0$ → Learning possible!