|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-99-051
Margin
error and generalization capabilities of multi-class discriminant
systems
André Elisseeff, Hélène Paugam-Moisy
ERIC,Université LumièreLyon2
Yann Guermeur
LORIA, Vandœuvre-lès-Nancy
Received:
03-DEC-1999
Abstract
Discriminant models
are usually initially conceived to deal with two-class problems, and
then extended simply to deal with multi-class applications. One way
to do so is to divide the problem at hand into several "one class
against the others" ones. In some particular cases such as support
vector machines, multi-class systems are built independently from
their bi-class implementation but they lose their theoretical foundations.
Starting from notions of margin in the context of bi-class discrimination
and related generalization error bounds, this report proposes a direct
approach to multi-class discriminant systems. It exposes an
extension of a lemma by Bartlett to the multi-class case. After a
discussion about the notion
of margin and its use for bi-class discriminant models, a margin for
the multi-class case is introduced. Generalization error bounds
for multiple output classifiers are then computed in terms of covering
numbers. This report shows how to bound these numbers for sets of
functions of interest and to give an example for linear discriminant
systems. This study aims at establishing theoretical foundations
for the analysis of multi-class systems and highlights
a way to derive multi-class support vector machines. Precisely, it
exhibits a notion of margin the maximization of which induces a low
generalization error.
Download Compressed Postscript
|