Seonglae ChoProbabilistic Approximately Correct framework
In statistical learning theory, what's important is not the "average error" but rather the guarantee that "the error is small with high confidence". Therefore, we approach this by calculating the probability tail where the error exceeds a certain value. We introduce a Confidence Parameter similar to the p-value in Significance Testing. This ensures that the probability of the learning result being sufficiently accurate (approximately correct) is guaranteed to be at least 1−δ
- Empirical risk where is the predicted output
- Theoretical risk
- Generalization gap
- Upper bounds , with high probability
With high probability, the generalization error of an hypothesis is at most something we can control and even compute. There is a probabilistic guarantee that the true error can be upper bounded by adding a margin to the training error.
The generalization error of an hypothesis is at most something we can control and even compute for any .
- Prior here means exploration mechanism of
- Posterior here means the twisted prior after confronting with data
Prototypical bound (McAllester, 1998, 1999)
Analysis of expected error over probability distribution Q instead of single hypothesis .
when think of as .
Probabilistic Approximately Correct Notion
PAC Bayes results
