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.