A regularization method for non-trivial codes in polychotomous classification

Polychotomous classification is a widespread task in pattern recognition. A classifier relates an input pattern to a class C_k element of a fixed number K > 2 of classes C₁, C₂, . . . , C_K. Neural networks for classification are generally based on the trivial 1-out-of-K coding. The advantage of non-trivial codes for discrimination of multiple classes lies in the increased Hamming distance between reference vectors, which makes error detection and even error correction feasible. Dichotomies from non-trivial codes are not as well arranged as from 1-out-of-K coding and may even have worse classification results after training. The code becomes superior to the trivial alternative only if its growing Hamming distance compensates for the increased tendency of single output errors. In this paper, the design of non-trivial error-correcting codes is based on the maximization of a cost function Φ, where the cost function is given by a trade-off between the empirical risk on training samples and a regularization term in the decision space. The introduced algorithm is based on a semi-implicit optimization of the given cost function. The results are related to the coding of multiple classes from a real classification task in handwritten character recognition. The complete system consists of parallel neural networks, each consisting of hidden neurons in the first layer and a Boolean function in the second layer. A comparison between optimized non-trivial codes and the trivial 1-out-of-K code is presented. It is shown that the generally applied 1-out-of-K code is not optimal. The optimum is reached by non-trivial coding without increasing the size of the classification system.