ECAI-2002 Conference Paper

[full paper]

From Margins to Probabilities in Multiclass Learning Problems

Andrea Passerini, Massimiliano Pontil, Paolo Frasconi

We study the problem of multiclass classification within the framework of error correcting output codes (ECOC) using margin-based binary classifiers. An important open problem in this context is how to measure the distance between class codewords and the outputs of the classifiers. In this paper we propose a new decoding function that combines the margins through an estimate of their class conditional probabilities. We report experiments using support vector machines as the base binary classifiers, showing the advantage of the proposed decoding function over other functions of the margin commonly used in practice. We also present new theoretical results bounding the leave-one-out error of ECOC of kernel machines, which can be used to tune kernel parameters. An empirical validation indicates that the bound leads to good estimates of kernel parameters and the corresponding classifiers attain high accuracy.

Keywords: Machine Learning, Error Correcting Output Codes, Support Vector Machines,, Statistical Learning Theory

Citation: Andrea Passerini, Massimiliano Pontil, Paolo Frasconi: From Margins to Probabilities in Multiclass Learning Problems. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.400-404.