nips nips2012 nips2012-80 nips2012-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Liva Ralaivola
Abstract: This paper provides the first —to the best of our knowledge— analysis of online learning algorithms for multiclass problems when the confusion matrix is taken as a performance measure. The work builds upon recent and elegant results on noncommutative concentration inequalities, i.e. concentration inequalities that apply to matrices, and, more precisely, to matrix martingales. We do establish generalization bounds for online learning algorithms and show how the theoretical study motivates the proposition of a new confusion-friendly learning procedure. This learning algorithm, called COPA (for COnfusion Passive-Aggressive) is a passive-aggressive learning algorithm; it is shown that the update equations for COPA can be computed analytically and, henceforth, there is no need to recourse to any optimization package to implement it. 1
[1] N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of online learning algorithms. IEEE Transactions on Information Theory, 50(9):2050–2057, 2004.
[2] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585, 2006.
[3] Y. Lee. Multicategory support vector machines, theory, and application to the classification of microarray data and satellite radiance data. Technical report, University of Wisconsin, 2002.
[4] Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines. Journal of the American Statistical Association, 99:67–81, march 2004.
[5] P. Machart and L. Ralaivola. Confusion matrix stability bounds for multiclass classification. Technical report, Aix-Marseille University, 2012.
[6] S. Matsushima, N. Shimizu, K. Yoshida, T. Ninomiya, and H. Nakagawa. Exact passiveaggressive algorithm for multiclass classification using support class. In SDM 10, pages 303– 314, 2010.
[7] E. Morvant, S. Koco, and L. Ralaivola. PAC-Bayesian Generalization Bound on Confusion ¸ Matrix for Multi-Class Classification. In John Langford and Joelle Pineau, editors, International Conference on Machine Learning, pages 815–822, Edinburgh, United Kingdom, 2012.
[8] J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, pages 1–46, 2011. 9