Error Correcting Output Code (ECOC)
An Error Correcting Output Code (ECOC) is an Error Correcting Code that is used by a machine learning system to solve a multi-classification problem.
- AKA: Error Correcting Output Coding (ECOC).
- Example(s):
- Counter-Example(s):
- See: Code Design System, Claude Shannon, Computing, Telecommunication, Information Theory, Coding Theory, Error Control, Communication Channel, Cirrus Logic, Bell System Technical Journal, AT&T, Redundancy (Information Theory), Richard Hamming.
References
2019a
- (Neill & Bollegala, 2019) ⇒ James O' Neill, and Danushka Bollegala. (2019). “Error-Correcting Neural Sequence Prediction".
- QUOTE: We propose a novel neural language modelling (NLM) method based on error-correcting output codes (ECOC), abbreviated as ECOC-NLM. This latent variable based approach provides a principled way to choose a varying amount of latent output codes and avoids exact softmax normalization. Instead of minimizing measures between the predicted probability distribution and true distribution, we use error-correcting codes to represent both predictions and outputs. Secondly, we propose multiple ways to improve accuracy and convergence rates by maximizing the separability between codes that correspond to classes proportional to word embedding similarities.
2019b
- (Pavlu, 2019) ⇒ Virgil Pavlu (2019). "Error-Correcting Output Codes". In: ML Lecture Notes.
- QUOTE: Error-Correcting Output Codes(ECOC)[1] is an ensemble method designed for multi-class classification problem. In multi-class classification problem, the task is to decide one label from $k > 2$ possible choices. For example, in digit recognition task, we need to map each hand written digit to one of $k = 10$ classes. Some algorithms, such as decision tree, naive bayes and neural network, can handle multi-class problem directly.
ECOC is a meta method which combines many binary classifiers in order to solve the multi-class problem.
- QUOTE: Error-Correcting Output Codes(ECOC)[1] is an ensemble method designed for multi-class classification problem. In multi-class classification problem, the task is to decide one label from $k > 2$ possible choices. For example, in digit recognition task, we need to map each hand written digit to one of $k = 10$ classes. Some algorithms, such as decision tree, naive bayes and neural network, can handle multi-class problem directly.
1995
- (Dietterich & Bakiri, 1995) ⇒ Thomas G. Dietterich, and Ghulum Bakiri (1995). "Solving Multiclass Learning Problems via Error-Correcting Output Codes". In: Journal of Artificial Intelligence Research (JAIR), Volume 2. DOI:10.1613/jair.105.
- QUOTE: Table 3 shows a 15-bit error-correcting code for the digit-recognition task. Each class is represented by a code word drawn from an error-correcting code.
- QUOTE: Table 3 shows a 15-bit error-correcting code for the digit-recognition task. Each class is represented by a code word drawn from an error-correcting code.
| Class | Code Word | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $f_0$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_{10}$ | $f_{11}$ | $f_{12}$ | $f_{13}$ | $f_{14}$ | |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 7 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 8 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 9 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
::This error-correcting code approach suggests that we view machine learning as a kind of communications problem in which the identity of the correct output class for a new example is being "transmitted" over a channel. The channel consists of the input features, the training examples, and the learning algorithm. Because of errors introduced by the nite training sample, poor choice of input features, and was in the learning process, the class information is corrupted. By encoding the class in an error-correcting code and "transmitting" each bit separately (i.e., via a separate run of the learning algorithm), the system may be able to recover from the errors.