TY  - JOUR
ID  - jf:DAMI
T1  - Efficient prediction algorithms for binary decomposition techniques
A1  - Park, Sang-Hyeun
A1  - Fürnkranz, Johannes
JA  - Data Mining and Knowledge Discovery
Y1  - 2012
VL  - 24
IS  - 1
SP  - 40
EP  - 77
PB  - Springer Netherlands
SN  - 1384-5810
UR  - /publications/papers/dami12.pdf
M2  - doi: 10.1007/s10618-011-0219-9
KW  - aggregation
KW  - binary decomposition
KW  - efficient decoding
KW  - efficient voting
KW  - multiclass classification
KW  - pairwise classification
KW  - ternary ECOC
N2  - Binary decomposition methods transform multiclass learning problems into a series of two-class learning problems that can be solved with simpler learning algorithms. As the number of such binary learning problems often grows super-linearly with the number of classes, we need efficient methods for computing the predictions. In this article, we discuss an efficient algorithm that queries only a dynamically determined subset of the trained classifiers, but still predicts the same classes that would have been predicted if all classifiers had been queried. The algorithm is first derived for the simple case of pairwise classification, and then generalized to arbitrary pairwise decompositions of the learning problem in the form of ternary error-correcting output codes under a variety of different code designs and decoding strategies.
ER  -