Many important classification problems are polychotomies i.e., the data are
organized into *K* classes with *K* > 2. The problem of finding an
approximation of an unknown function *F* representing a polychotomy is much
easier if it is first decomposed into a set of smaller subproblems called
dichotomies, i.e., classification problems of two classes. Given a training
set of an unknown *K*-partition of , an algorithm learning
this polychotomy by decomposition into *L* dichotomies produces an
approximation of the following form:

with , where
is a function selected in the set of
hypotheses of the method to solve subproblem *l*, and is a mapping associating to each set of *L* answers
of the classifiers, a set of *K* confidences of membership to each class.

Two different types of decomposition/reconstruction schemes can be
distinguished: *a* *priori* schemes are determined independently of the data,
while *a* *posteriori* schemes depend on the training data. This work consists
of a comparative study of different methods for a posteriori reconstruction.

The decomposition scheme can be specified by a *decomposition* *matrix* such that if class *k* is
associated with *z* by , if class *k* is ignored by
.

The reconstruction basically consists in the function arg max.
The determination *a* *posteriori* of the mapping *m* is based on a dataset
distinct
from the one used to select the and distinct from the one use to
test the system. In this framework, one can forget about the decomposition and
consider the classification problem given by
to be solved by a model of the form arg
max. In what follows, the task is represented by the
two matrices and , with ,
and , if and only if . Two different ways of doing this reconstruction
are studied: linear and non-linear methods.

Tue Mar 31 18:35:24 MET DST 1998