IV. Feasibility of Learning

1. Learning is Impossible?

Lin provides two examples to show learning seems to be impossible.

2. Probability to the Rescue

Hoeffding’s Inequality:

$\mu$μ is the actual frequency of event A and $\nu$ν is my hypothetical frequency of event A. Hoeffding’s Inequality shows that the probability of the exitance of a huge gap($\epsilon$ϵ) between $\mu$μ and $\nu$ν is tiny when I have a large N(big data)
the statement ‘$\mu = \nu$μ=ν’ is probably approximately correct(PAC)

3. Connection to Learning

The verification flow guarantee ‘historical records’(training set) are similar to the current conditon(test set).
Check ② of this quiz:

4. Connection to Real Learning

‘Bad Data’ could happens from time to time(let’s say if you filp a coin 5 times and get 5 heads). Accroding to Hoeffding’s inequality, the probability could be tiny when you have a large data.