Error-correcting output code (ECOC)

Error-correcting output code (ECOC)[1,2]

Description

A length-\(n\) binary or ternary (over \(\{\pm 1,0\}\)) block code used to convey information about classes to classifiers in multiclass machine learning. Rows of the code's generator matrix denote different classes, while columns correspond to classifiers. The \(\pm 1\) elements can be used to distinguish between a pair of chosen classes, while a zero entry correspond to a classifier ignoring that particular class.

A data-driven ECOC (DECOC) [3] is an ECOC whose design takes into account features of the data that is to be classified. Not always decoded using the Hamming metric.

Decoding

Standard Hamming-distance decoding [4].Inverse Hamming decoding [5].Euclidean-distance decoding or attenuated Euclidean decoding [6].Loss-based decoding [2].Probabilistic-based decoding [7].

Realizations

Multiclass problems in machine learning, relevant to facial recognition [8,9], text recognition [10], or digit classification [11].

Notes

See [12][13; Ch. 6] for overviews of ECOCs.See [14] for a library of ECOCs.

Parent

Block code

Children

One-hot code — One-hot codes are the primary codes used in multiclass classification [13,15–17].
One-versus-one (OVO) code — One-vs-one codes are often used in multiclass classification because they separate the muilticlass task into several two-class tasks [13].

Cousins

Hadamard code — Hadamard codes and subcodes can be used as ECOCs [1,18,19].
Binary BCH code — BCH codes can be used as ECOCs [1].

References

[1]: T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
[2]: Allwein, Erin L., Robert E. Schapire, and Yoram Singer. "Reducing multiclass to binary: A unifying approach for margin classifiers." Journal of machine learning research 1.Dec (2000): 113-141.
[3]: J. Zhou, H. Peng, and C. Y. Suen, “Data-driven decomposition for multi-class classification”, Pattern Recognition 41, 67 (2008) DOI
[4]: Nilsson, Nils J. "Learning machines." (1965).
[5]: T. Windeatt and R. Ghaderi, “Coding and decoding strategies for multi-class learning problems”, Information Fusion 4, 11 (2003) DOI
[6]: O. Pujol, S. Escalera, and P. Radeva, “An incremental node embedding technique for error correcting output codes”, Pattern Recognition 41, 713 (2008) DOI
[7]: A. Passerini, M. Pontil, and P. Frasconi, “New Results on Error Correcting Output Codes of Kernel Machines”, IEEE Transactions on Neural Networks 15, 45 (2004) DOI
[8]: T. Windeatt, “Boosted ECOC ensembles for face recognition”, International Conference on Visual Information Engineering (VIE 2003). Ideas, Applications, Experience (2003) DOI
[9]: J. Kittler, R. Ghaderi, T. Windeatt, and J. Matas, “Face verification using error correcting output codes”, Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 DOI
[10]: R. Ghani, “Combining labeled and unlabeled data for text classification with a large number of categories”, Proceedings 2001 IEEE International Conference on Data Mining DOI
[11]: J. Zhou and C. Y. Suen, “Unconstrained numeral pair recognition using enhanced error correcting output coding: a holistic approach”, Eighth International Conference on Document Analysis and Recognition (ICDAR’05) (2005) DOI
[12]: S. Escalera, O. Pujol, and P. Radeva, “On the Decoding Process in Ternary Error-Correcting Output Codes”, IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 120 (2010) DOI
[13]: L. Rokach, Pattern Classification Using Ensemble Methods (WORLD SCIENTIFIC, 2009) DOI
[14]: Escalera, Sergio, Oriol Pujol, and Petia Radeva. "Error-correcting ouput codes library." The Journal of Machine Learning Research 11 (2010): 661-664.
[15]: G. Anthony, H. Gregg, and M. Tshilidzi, “Image Classification Using SVMs: One-against-One Vs One-against-All”, (2007) arXiv:0711.2914
[16]: K. Potdar, T. S., and C. D., “A Comparative Study of Categorical Variable Encoding Techniques for Neural Network Classifiers”, International Journal of Computer Applications 175, 7 (2017) DOI
[17]: W. Utschick and W. Weichselberger, “Stochastic Organization of Output Codes in Multiclass Learning Problems”, Neural Computation 13, 1065 (2001) DOI
[18]: V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
[19]: A. Zhang, Z.-L. Wu, C.-H. Li, and K.-T. Fang, “On Hadamard-Type Output Coding in Multiclass Learning”, Intelligent Data Engineering and Automated Learning 397 (2003) DOI

Page edit log

Victor V. Albert (2024-01-02) — most recent

Cite as:

“Error-correcting output code (ECOC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/ecoc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/ecoc.yml.