Extending Local Learners with Error-Correcting Output Codes

Error-correcting output codes (ECOCs) represent classes with a set of output bits, where each bit encodes a binary classification task corresponding to a unique partition of the classes. Algorithms that use ECOCs learn the function corresponding to each bit, and combine them to generate class predictions. ECOCs can reduce both variance and bias errors for multiclass classification tasks when the errors made at the output bits are not correlated. They work well with global (e.g., C4.5) but not with local (e.g., nearest neighbor) classifiers because the latter use the same information to predict each bit's value, which yields correlated errors. This is distressing because local learners are excellent classifiers for some types of applications. We show that the output bit errors of local learners can be decorrelated by selecting different features for each bit. This yields bit-specific distance functions, which causes different information to be used for each bit's prediction. We present promising empirical reslts for this combination of ECOC, nearest neighbor, and feature selection. We also describe modifications to racing algorithms for featre selection that improve their performance in tis context