CS Colloquium on Wednesday, June 9, 2004 Title: Extracting Meaning with Kolmogorov and Shannon Speaker: Paul Vitanyi CWI and University of Amsterdam Time: 3:30pm Place: MCS 135, 111 Cummington Street (please see http://cs-www.bu.edu/colloquium for directions) Abstract: As perhaps the last mathematical innovation of an extraordinary scientific career, Kolmogorov in 1974 proposed to found statistical theory on finite combinatorial and computability principles independent of probabilistic assumptions, as the relation between the individual data and its explanation (model), expressed by Kolmogorov's structure function. It turns out that this proposal is formally a Shannon's rate distortion function for individual data and related to lossy compression. In classical probabilistic statistics the goodness of the selection process is measured in terms of expectations over probabilistic ensembles. For current applications, average relations are often irrelevant, since the part of the support of the probability density function that will ever be observed has about zero measure. This may be the case in, for example, complex video and sound analysis. There arises the problem that for individual cases the selection performance may be bad although the performance is good on average, or vice versa. There is also the problem of what probability means, whether it is subjective, objective, or exists at all. Kolmogorov's proposal outlined strives for the firmer and less contentious ground expressed in finite combinatorics and effective computation. Our main result, with the beauty of truth, justifies Kolmogorov's intuition. A practical consequence is: While the best fit (minimal randomness deficiency under complexity constraints on the model) cannot be computationally monotonically approximated, we can monotonically minimize the two-part code, or the one-part code, and thus monotonically approximate {\em implicitly} the best fitting model. But this should be sufficient: we want the best model rather than a number that measures its goodness. These results open the possibility of model selection and prediction that are best possible for {\em individual} data samples, and thus usher in a completely new era of statistical inference that is *always* best rather than *expected*. Based on joint work with Nikolai Vereshchagin presented partially at the 47th IEEE Symp on Foundat. Comput. Sci., 2002, Vancouver, Canada. See paper at: http://www.cwi.nl/~paulv/selection.html or http://arXiv.org/abs/cs.CC/0204037 and recent work with Peter Grunwald and Nikolai Vereshchagin. Host: Steve Homer (http://www.cs.bu.edu/~homer)