Member-only story
Bayes Optimal Classifier
Machine Learning from First Principles: Blog Post 5
In the last blog we learnt what realizability and sample complexity are. Reiterating it, realizability assumption states that the optimal hypothesis lies in the finite hypothesis class. This is a strong assumption as the universe would not be kind enough to lend us the correct answer from the set we choose to find it from. This assumption is just for understanding and starting simple and would be relaxed today. Sample complexity is a function of epsilon and delta and it tells us the minimum number of samples we need which would make the hypothesis class PAC learnable.
The ηH(ε, 𝜹) above is the sample complexity. It is a function of ε, 𝜹 and H. The more complex the hypothesis class H, the more samples you need. The definition says, with a given accuracy (ε) and probably correctness (𝜹) the algorithm is guaranteed to return a hypothesis (h) whose error (Lpx(h)) is ≤ ε with probability ≥ 1 - 𝜹 (low error with high probability), provided you have iid samples which are at least as much as defined by the sample complexity. This is the definition of a PAC learnable problem.
