Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm
Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm
复制标题
DOI：
10.5555/2789272.2831140
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
Pascal Germain;A. Lacasse;François Laviolette;M. Marchand;Jean-Francis Roy
中科院分区：
文献类型：
--
作者：
Pascal Germain;A. Lacasse;François Laviolette;M. Marchand;Jean-Francis Roy
我们提出了一个广泛的分析行为的多数票在二进制分类。特别是，我们引入了一个风险约束的多数票，称为C界，考虑到选民的平均质量和他们的平均分歧。我们还提出了一个广泛的PAC-Bayesian分析，展示了如何从训练数据中包含的各种观察来估计C界。该分析旨在是独立的，可以用作PAC-贝叶斯统计学习理论的介绍材料。它从一般的PAC-Bayesian角度开始，并以不常见的PAC-Bayesian边界结束。其中一些界限不包含Kullback-Leibler分歧，而其他界限则允许将内核函数用作投票者（通过样本压缩设置）。最后，在分析的基础上，我们提出了MinCq学习算法，该算法基本上最小化了C界。MinCq简化为一个简单的二次规划。除了理论上的基础，MinCq实现了最先进的性能，如我们与AdaBoost和支持向量机的广泛实证比较所示。
We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback-Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.