Week04. Feasibility of Learning

Course_Lin_MLF 2017.11

1. Learning is impossible?

• A learning Puzzle
  controversial answers
  争议的答案　 $\leftarrow$ 不同的判断规则
  adversarial

• A 'Simple' Binary Classification Problem

• No Free Lunch

2. Probability to the Rescue

• Inferring Something Unkown
  抓弹珠问题
  statistic 101: inferring orange probability
  sample 采样估计

• Possible versus Probable

• Hoeffding's Inequality
  $u$=orange probability in bin 真实值
  $v$= orange fraction in sample
  in big sample(N large), $v$ is probably close to $\mu$(within $\varepsilon$)
  

  $$\begin{align*} \mathbb{P} [ \mid v-\mu \mid > \varepsilon] \le 2 \exp( -2 \varepsilon^2N) \end{align*}$$
  called Hoeffding's Inequality, for marbles,coin,polling
  the statement $'v=\mu'$ is probably approximately correct(PAC)

3. Connection to Learning

• The Formal Guarantee
  in-sample error $E_{in}(h)$ is probably close to
  out-of-sample error $E_{out}(h)$ (within $\varepsilon$)
  

  $$\begin{align*} \mathbb{P}[ \mid E_{in}(h) - E_{out}(h) \mid > \varepsilon ] \le 2\exp(-2\varepsilon^2N) \end{align*}$$
  由霍夫丁不等式得出
  样本数据越大，预测结果与真实结果就越接近。

• Verification of One $h$
  The 'Verifiction' Flow
  vice versus

4. Connection to Real Learning

• Multiple h

• BAD Sample and BAD Data
  坏的样本数据，真实的分布与实际分布差别很大，会导致预测值与真实值差的很大，
  假设有很多的随机的资料，根据霍夫丁不等式，坏的样本数据站的比例是比较小的。

• Bad Data for Many $h$

• Bound of BAD Data
  只要对某个hypothesis是BAD的，就认为其是一个BAD的样本数据集
  

  $$\begin{align*} \mathbb{P}[ BAD \ \mathcal{D} ] &= \\ &= \mathbb{P}[ BAD \ \mathcal{D} for \ h_1 \ or \ BAD \ \mathcal{D} for \ h_2 \ or \ \dots \ or \ BAD \ \mathcal{D} for \ h_M ] \\ &\le \mathbb{P}[ BAD \ \mathcal{D} for \ h_1 ] + \mathbb{P}[ BAD \ \mathcal{D} for \ h_2 ] + \dots + \mathbb{P}[BAD \ \mathcal{D} for \ h_M ] \ (union \ bound) \\ &\le 2\exp( -2\varepsilon^2N ) + 2\exp(-2\varepsilon^2N) + \dots +2\exp(-2\varepsilon^2N) \\ &= 2M\exp(-2\varepsilon^2N) \end{align*}$$
  finite-bin version of Hoeffding,valid for all $M,N \ and \ \varepsilon$