APPRENABILITÉ DANS LES PROBLÈMES DE L'INFÉRENCE SÉQUENTIELLE
Daniil Ryabko · LillOA (Université de Lille (University Of Lille)) · 2011
Given a growing sequence of observations x_1,...,x_n,..., one is required, at each time step n, to make some inference about the stochastic mechanism generating the sequence. Several problems that have numerous applications in different branches of mathematics and computer science can be formulated in this way. For example, one may want to forecast probabilities of the next outcome x_{n+1} (sequence prediction); to make a decision on whether the mechanism generating the sequence belongs to a certain family $H_0$ versus it belongs to a different family $H_1$ (hypothesis testing); to take an action in order to maximize some utility function. In each of these problems, as well as in many others, in order to be able to make inference, one has to make some assumptions on the probabilistic mechanism generating the data. Typical assumptions are that x_i are independent and identically distributed, or that the distribution generating the sequence belongs to a certain parametric family. The central question addressed in this work is: under which assumptions is inference possible? This question is considered for several problems of inference, including sequence prediction, hypothesis testing, classification and reinforcement learning.