PAC-Bayesian learning of linear classifiers

ABSTRACT

We present a general PAC-Bayes theorem from which all known PAC-Bayes risk bounds are obtained as particular cases. We also propose different learning algorithms for finding linear classifiers that minimize these bounds. These learning algorithms are generally competitive with both AdaBoost and the SVM.

REFERENCES

• 1: Ambroladze, A., Parrado-Hernández, E., & Shawe-Taylor, J. (2006). Tighter PAC-Bayes bounds. Proceedings of the 2006 conference on Neural Information Processing Systems (NIPS-06) (pp. 9--16).
• 2: Arindam Banerjee, On Bayesian bounds, Proceedings of the 23rd international conference on Machine learning, p.81-88, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143855]
• 3: Catoni, O. (2007). PAC-Bayesian surpevised classification: the thermodynamics of statistical learning. Monograph series of the Institute of Mathematical Statistics, http://arxiv.org/abs/0712.0248.
• 4: John Langford, Tutorial on Practical Prediction Theory for Classification, The Journal of Machine Learning Research, 6, p.273-306, 12/1/2005
• 5: Langford, J., & Shawe-Taylor, J. (2003). PAC-Bayes & margins. In S. T. S. Becker and K. Obermayer (Eds.), Advances in neural information processing systems 15, 423--430. Cambridge, MA: MIT Press.
• 6: David A. McAllester, PAC-Bayesian Stochastic Model Selection, Machine Learning, v.51 n.1, p.5-21, April 2003 [doi>10.1023/A:1021840411064]
• 7: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26, 1651--1686.
• 8: Matthias Seeger, Pac-bayesian generalisation error bounds for gaussian process classification, The Journal of Machine Learning Research, 3, p.233-269, 3/1/2003 [doi>10.1162/153244303765208386]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory