Sparse probabilistic classifiers

ABSTRACT

The scores returned by support vector machines are often used as a confidence measures in the classification of new examples. However, there is no theoretical argument sustaining this practice. Thus, when classification uncertainty has to be assessed, it is safer to resort to classifiers estimating conditional probabilities of class labels. Here, we focus on the ambiguity in the vicinity of the boundary decision. We propose an adaptation of maximum likelihood estimation, instantiated on logistic regression. The model outputs proper conditional probabilities into a user-defined interval and is less precise elsewhere. The model is also sparse, in the sense that few examples contribute to the solution. The computational efficiency is thus improved compared to logistic regression. Furthermore, preliminary experiments show improvements over standard logistic regression and performances similar to support vector machines.

REFERENCES

• 1: Bartlett, P. L., & Tewari, A. (2004). Sparseness vs estimating conditional probabilities: Some asymptotic results. Proceedings of the 17th Annual Conference On Learning Theory (pp. 564--578). Springer.
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Shantanu Chakrabartty , Gert Cauwenberghs, Gini Support Vector Machine: Quadratic Entropy Based Robust Multi-Class Probability Regression, The Journal of Machine Learning Research, 8, p.813-839, 5/1/2007
• 4: Olivier Chapelle, Training a Support Vector Machine in the Primal, Neural Computation, v.19 n.5, p.1155-1178, May 2007 [doi>10.1162/neco.2007.19.5.1155]
• 5: Chawla, N. V., Hall, L. O., Bowyer, K. W., & Kegelmeyer, W. P. (2002). Smote: Synthetic minority oversampling technique. Journal Of Artificial Intelligence Research, 16, 321--357.
• 6: Ronan Collobert , Fabian Sinz , Jason Weston , Léon Bottou, Trading convexity for scalability, Proceedings of the 23rd international conference on Machine learning, p.201-208, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143870]
• 7: Trevor F. Cox , Kim F. Pearce, A robust logistic discrimination model, Statistics and Computing, v.7 n.3, p.155-161, 1997 [doi>10.1023/A:1018530001135 ]
• 8: Grandvalet, Y., Mariéthoz, J., & Bengio, S. (2006). A probabilistic interpretation of SVMs with an application to unbalanced classification. Advances in Neural Information Processing Systems 18 (pp. 467--474). MIT Press.
• 9: S. S. Keerthi , K. B. Duan , S. K. Shevade , A. N. Poo, A Fast Dual Algorithm for Kernel Logistic Regression, Machine Learning, v.61 n.1-3, p.151-165, November 2005 [doi>10.1007/s10994-005-0768-5]
• 10: Gaëlle Loosli , Stéphane Canu, Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets", The Journal of Machine Learning Research, 8, p.291-301, 5/1/2007
• 11: Edgar Osuna , Robert Freund , Federico Girosi, Support Vector Machines: Training and Applications, Massachusetts Institute of Technology, Cambridge, MA, 1997
• 12: Platt, J. C. (2000). Probabilities for SV machines. Advances in Large Margin Classifiers (pp. 61--74). MIT Press.
• 13: Volker Roth, Probabilistic Discriminative Kernel Classifiers for Multi-class Problems, Proceedings of the 23rd DAGM-Symposium on Pattern Recognition, p.246-253, September 12-14, 2001
• 14: Roth, V. (2004). The generalized LASSO. IEEE Transactions on Neural Networks, 15, 16--28.
• 15: Kai Ming Ting, A Comparative Study of Cost-Sensitive Boosting Algorithms, Proceedings of the Seventeenth International Conference on Machine Learning, p.983-990, June 29-July 02, 2000
• 16: Vishwanathan, S. V. N., Smola, A. J., & Murty, M. N. (2003). SimpleSVM. Proceedings of the Twentieth International Conference on Machine Learning (pp. 760--767)
• 17: Mingrui Wu , Bernhard Schölkopf , Gökhan Bakır, A Direct Method for Building Sparse Kernel Learning Algorithms, The Journal of Machine Learning Research, 7, p.603-624, 12/1/2006
• 18: Zhu, J., & Hastie, T. (2001). Kernel logistic regression and the import vector machine. Advances in Neural Information Processing Systems 13.