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
A Primer on PAC-Bayesian Learning
Generalised Bayesian learning algorithms are increasingly popular in machine learning, due to their PAC generalisation properties and flexibility. The present paper aims at providing a...
https://arxiv.org/abs/1901.05353
A Primer on PAC-Bayesian Learning
PAC-Bayesian inequalities were introduced by McAllester (1998, 1999), following earlier remarks by Shawe-Taylor and Williamson (1997). The goal was to produce PAC-type risk bounds for Bayesian-flavored estimators. The acronym PAC stands for Probably Approximately Correct and may be traced back to Valiant (1984). This framework allows to consider not only classical Bayesian estimators, but rather any randomized procedure from a data-dependent distribution.
https://bguedj.github.io/icml2019/
Valiant 1984
people.mpi-inf.mpg.de
https://people.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/ValiantLearnable.pdf