Data driven approach to designing minimum hamming distance polychotomizer

ABSTRACT

A polychotomous classifier assigns an observation to one of the K categories with K > = 3. Multiple binary classifiers (K = 2) such as the popular Support Vector Machines can be combined to achieve multi-class classification. Commonly used approaches include the one-vs-others scheme and the one-vs-one (pairwise coupling) scheme. While literature reported better performance from pairwise coupling than one-vs-others, the number of base learners required by pairwise coupling is quadratic in K. Alternatively, error correcting output codes (ECOC) provides a more general framework for designing polychotomizers. It associates each class with a codeword, which provides the capability to unify the traditional schemes. However, the design of an effective "coding matrix" remains an open problem. We study one kind of ECOC polychotomizer that decodes using minimum hamming distance. We propose a novel data-driven way to design the codewords based on inter-cluster distance. It provides a systematic way to extend the traditional schemes and construct effective polychotomizers. Experiments are conducted on synthetic data and real world applications including UCI repository problems and CENPARMI handwritten numerals. Experiments show that the proposed scheme can achieve competitive accuracy compared with both traditional schemes, and the number of base learners is typically much less than the requirement of the pairwise scheme.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
• 2: Koby Crammer , Yoram Singer, On the Learnability and Design of Output Codes for Multiclass Problems, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.35-46, June 28-July 01, 2000
• 3: T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263--286, 1995.
• 4: Robert P. W. Duin , Fabio Roli , Dick de Ridder, A note on core research issues for statistical pattern recognition, Pattern Recognition Letters, v.23 n.4, p.493-499, February 2002 [doi>10.1016/S0167-8655(01)00181-7]
• 5: J. Friedman. Another approach to polychotomous classification. Technical Report, Statistics Department, Stanford University, 1996.
• 6: C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13:415--425, 2002.
• 7: J. C. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin dags for multiclass classification. In Advances in Neural Information Processing Systems, volume 12, pages 547--553. MIT Press, 2000.
• 8: D. T. Ross, U. Sherf, and et al. A cdna microarray gene expression database for the molecular pharmacology of cancer. Nature Genetics, 24(3):236--244, 2000.
• 9: T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classification by pairwise coupling. In Proc. NIPS, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation

Keywords:
coding matrix, minimum hamming distance, polychotomizer