An Overview of Algorithmic Randomness and its Application to Reliable Instance Classification

Machine-learning classiers are difficult to apply in application domains where incorrect predictions can have serious consequences. In these domains, classifiers can be applied only if they guarantee reliable predictions. The transductive confidence machines framework allows to extend classifiers such that they produce predictions that are complemented with a confidence value. The confidence value provides an upper bound on the error rate and can be defined prior to classification. Transductive confidence machines are based on difficult mathematical concepts such as algorithmic randomness and Martin-Löf randomness tests. In the report we explain these concepts in detail, integrate them to motivate transductive confidence machines, and review crucial theoretical and practical properties of transductive confidence machines