On the Decomposition of Polychotomies into Dichotomies

Abstract

Many important classification problems are polychotomies, i.e. the data are organized into K classes with K ? 2. Given an unknown function F :\\Omega ! f1; : : : ; Kg representing a polychotomy, an algorithm aimed at "learning" this polychotomy will produce an approximation of F , based on the knowledge of a set of pairs f(x p ; F (x p ))g P p=1 . Although in the wide variety of learning tools there exist some learning algorithms capable of handling polychotomies, many of the interesting tools were designed by nature for dichotomies (K = 2). Therefore, many researchers are compelled to use techniques to decompose a polychotomy into a series of dichotomies in order to apply their favorite algorithms to the resolution of a general problem. A decomposition method based on error-correcting codes has been lately proposed and shown to be very efficient. However, this decomposition is designed only on the basis of K without taking the data into account. In this paper, we explore alter...