A Column Generation Bound Minimization Approach with PAC-Bayesian Generalization Guarantees

Jean-Francis Roy, Mario Marchand, François Laviolette
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1241-1249, 2016.

Abstract

The C-bound, introduced in Lacasse et al (2006), gives a tight upper bound on the risk of the majority vote classifier. Laviolette et al. (2011) designed a learning algorithm named MinCq that outputs a dense distribution on a finite set of base classifiers by minimizing the C-bound, together with a PAC-Bayesian generalization guarantee. In this work, we design a column generation algorithm that we call CqBoost, that optimizes the C-bound and outputs a sparse distribution on a possibly infinite set of voters. We also propose a PAC-Bayesian bound for CqBoost that holds for finite and two cases of continuous sets of base classifiers. Finally, compare the accuracy and the sparsity of CqBoost with MinCq and other state-of-the-art boosting algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-roy16, title = {A Column Generation Bound Minimization Approach with PAC-Bayesian Generalization Guarantees}, author = {Roy, Jean-Francis and Marchand, Mario and Laviolette, François}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {1241--1249}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/roy16.pdf}, url = {https://proceedings.mlr.press/v51/roy16.html}, abstract = {The C-bound, introduced in Lacasse et al (2006), gives a tight upper bound on the risk of the majority vote classifier. Laviolette et al. (2011) designed a learning algorithm named MinCq that outputs a dense distribution on a finite set of base classifiers by minimizing the C-bound, together with a PAC-Bayesian generalization guarantee. In this work, we design a column generation algorithm that we call CqBoost, that optimizes the C-bound and outputs a sparse distribution on a possibly infinite set of voters. We also propose a PAC-Bayesian bound for CqBoost that holds for finite and two cases of continuous sets of base classifiers. Finally, compare the accuracy and the sparsity of CqBoost with MinCq and other state-of-the-art boosting algorithms.} }
Endnote
%0 Conference Paper %T A Column Generation Bound Minimization Approach with PAC-Bayesian Generalization Guarantees %A Jean-Francis Roy %A Mario Marchand %A François Laviolette %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-roy16 %I PMLR %P 1241--1249 %U https://proceedings.mlr.press/v51/roy16.html %V 51 %X The C-bound, introduced in Lacasse et al (2006), gives a tight upper bound on the risk of the majority vote classifier. Laviolette et al. (2011) designed a learning algorithm named MinCq that outputs a dense distribution on a finite set of base classifiers by minimizing the C-bound, together with a PAC-Bayesian generalization guarantee. In this work, we design a column generation algorithm that we call CqBoost, that optimizes the C-bound and outputs a sparse distribution on a possibly infinite set of voters. We also propose a PAC-Bayesian bound for CqBoost that holds for finite and two cases of continuous sets of base classifiers. Finally, compare the accuracy and the sparsity of CqBoost with MinCq and other state-of-the-art boosting algorithms.
RIS
TY - CPAPER TI - A Column Generation Bound Minimization Approach with PAC-Bayesian Generalization Guarantees AU - Jean-Francis Roy AU - Mario Marchand AU - François Laviolette BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-roy16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 1241 EP - 1249 L1 - http://proceedings.mlr.press/v51/roy16.pdf UR - https://proceedings.mlr.press/v51/roy16.html AB - The C-bound, introduced in Lacasse et al (2006), gives a tight upper bound on the risk of the majority vote classifier. Laviolette et al. (2011) designed a learning algorithm named MinCq that outputs a dense distribution on a finite set of base classifiers by minimizing the C-bound, together with a PAC-Bayesian generalization guarantee. In this work, we design a column generation algorithm that we call CqBoost, that optimizes the C-bound and outputs a sparse distribution on a possibly infinite set of voters. We also propose a PAC-Bayesian bound for CqBoost that holds for finite and two cases of continuous sets of base classifiers. Finally, compare the accuracy and the sparsity of CqBoost with MinCq and other state-of-the-art boosting algorithms. ER -
APA
Roy, J., Marchand, M. & Laviolette, F.. (2016). A Column Generation Bound Minimization Approach with PAC-Bayesian Generalization Guarantees. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:1241-1249 Available from https://proceedings.mlr.press/v51/roy16.html.

Related Material