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.

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

Cousins

Hadamard code — Hadamard codes and subcodes can be used as ECOCs [1,15,16].
Binary BCH code — BCH codes can be used as ECOCs [1].
One-hot code — One-hot codes are the primary codes used in multiclass classification [13,17–19].
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].

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 et al., “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]: V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
[16]: A. Zhang et al., “On Hadamard-Type Output Coding in Multiclass Learning”, Intelligent Data Engineering and Automated Learning 397 (2003) DOI
[17]: G. Anthony, H. Gregg, and M. Tshilidzi, “Image Classification Using SVMs: One-against-One Vs One-against-All”, (2007) arXiv:0711.2914
[18]: 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
[19]: W. Utschick and W. Weichselberger, “Stochastic Organization of Output Codes in Multiclass Learning Problems”, Neural Computation 13, 1065 (2001) 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.