## The Controversial of Learning

$g(\text{ hypothesis }) \approx f(\text{real function})$ 在 已知数据里面是可行的；但是对不可见的数据，想要实现 $g(\text hypothesis) \approx f(\text {real function} )$，其实是未知的。

## Hoeffding’s Inequality

• valid for all N and $\epsilon$
• does not depend on $\mu$, no need to know $\mu$
• larger sample size N or looser gap $\epsilon$ => higher probability for $\nu \approx \mu$

## Connection to Learning

• if large N, can probably infer unknow $| h(x) \neq f(x) |$ by know $| h(x_{n} \neq y_n)|$
• $E_{in}(h)$: 在已知的样本里，假设函数与实际函数不相等的概率。$E_{out}(h)$: 在所有样本里，上述二者不相等的概率。
• $E_{in}(h)$ small is a good choice, but $E_{in}(h)$ is not always small.

## multiple h

• 这就是一个bad sample，因为其使得$E_{in}(h)$ far away $E_{out}(h)$
• $E_{in}(h)$ = 0
• $E_{out}(h)$ = $1/2$
• 最优P为lowest $E_{in}(h_{m})$