A Coding Theory Framework for Reliable Classification and Clustering

The aim of this project is to characterize and improve the reliability of machine learning algorithms by extending concepts from modern coding theory to classification and clustering.

Error correcting codes are used in communication systems to protect messages from disturbances that occur during transmission by adding redundancy.

In machine learning, on the other hand, error correcting output codes (ECOCs) have been proposed to improve the performance of classifiers with multiple classes.

In our research, we lift the potentials of the  ECOC framework to yet another level by introducing the concept of blockwise classification. This allows us to scale up ECOCs to large lengths independently of the original number of classes.

Efficient graph-based coding schemes from modern coding theory can then be designed to improve the performance of ECOCs beyond existing works.

This will improve their capability to estimate the uncertainty of their output and their robustness against adversarial attacks, which is one of the weaknesses of the current machine learning models, such as deep neural networks (DNNs), that suffer from overconfidence.Blockwise classification opens also the way for an asymptotic analysis.

Analogously to the Shannon limit and the decoding thresholds of capacity-achieving code ensembles, we will work on deriving fundamental performance limits for multiclass problems. We will also extend blockwise processing to clustering problems and establish connections to ECOCs.