Kolmogorov's axioms of probability provided a suitable base for the theory of probability. In 1965 Kolmogorov proposed what was, in his opinion, a suitable base for the applications of probability: the algorithmic notion of randomness. Unfortunately, the latter is not computable.
The seminar will describe recent work done in the machine learning group at Royal Holloway to find practicable approximations to it (based on Support Vector machines and other kernel methods). Both the abstract notion of randomness and our specific approximations will be applied to three popular machine-learning and statistical problems: pattern recognition, regression and density estimation. For the first two problems we construct efficient algorithms producing prediction intervals (formally, expectation tolerance intervals) valid under the general iid assumption. For the third problem a negative result will be stated: confident density estimation is impossible under the general iid assumption.
The audience will need no prior knowledge of the algorithmic theory of randomness or Support Vector machines. Brief reviews of those subjects will be given in the seminar.