L'application des algorithmes minimisant le regret cumulé dans des problèmes de bandits manchots a récemment donné naissance à une intelligence artificielle de Go de niveau mondial. Cependant il s'avère que pour cette application la recherche du meilleur bras n'est contrainte que par le temps dont on dispose et pas par une contrainte du type "exploration/exploitation". Dans ce cadre on définit de manière naturelle le regret simple et on construit de nouveaux algorithmes minimisant ce dernier plutôt que le regret cumulé. De façon étonnante peut être, il s'avère qu'il existe des liens très fort entre le regret cumulé et le regret simple d'un algorithme de bandits manchots. Le but de cet exposé sera de présenter ces liens de manière formelle et d'en déduire les conséquences pratiques.

Attention : exposé exceptionnellement à 16h !

Je rappellerai les principes generaux de ce que l'on appelle un cadre a la Le Cam, et reprouverai l'inegalite d'information dans ce cadre. On verra ensuite l'inegalite de van Trees comme une inégalité d'information pour une certaine famille bayesienne. Les hypotheses dont on aura besoin pour l'établir ainsi seront ensuite relachees par une etude directe. La presentation sera interactive, et les avis, idees, ou ameliorations de l'auditoire seront regulierement demandes !

[d'après un article d'András Antos et Ioannis Kontoyiannis paru dans Random Structures and Algorithms (2001)].
Suppose P is an arbitrary discrete distribution on acountable alphabet. Given an i.i.d. sample (X1,...,Xn) drawn from P, we consider the problem of estimating the entropy H(P) or some other functional F=F(P) of the unknown distribution P. We show that, for additive functionals satisfying mild conditions (including the cases of the mean, the entropy, and mutual information), the plug-in estimates of F are universally consistent. We also prove that, without further assumptions, no rate-of-convergence results can be obtained for any sequence of estimators. In the case of entropy estimation, under a variety of different assumptions, we get rate-of-convergence results for the plug-in estimate and for a nonparametric estimator based on match-lengths. The behavior of the variance and the expected error of the plug-in estimate is shown to be in sharp contrast to the finite-alphabet case. A number of other important examples of functionals are also treated in some detail.

Etant donnée une suite de variables i.i.d., et un paramètre de dimension k à estimer, si l'on munit l'espace du paramètre d'une loi a priori dont la densité est strictement positive en la "vraie" valeur du paramètre, le Théorème de Bernstein von Mises dit que, si le modèle paramétrique est "régulier", la loi a posteriori du paramètre est proche, en variation totale, de la loi gaussienne centrée en l'estimateur du maximum de vraisemblance et de variance l'inverse de l'information de Fisher divisée par la racine carrée du nombre d'observations. Je présenterai la preuve du théorème classique paramétrique. Suivant cette preuve, je montrerai quels sont les points délicats si l'on est dans le cadre paramétrique suivant: les variables sont à valeur dans l'ensemble des entiers, et l'on veut estimer les k premières probabilités, k tendant vers l'infini. Ou encore: on veut estimer une fonction de la loi, en utilisant une estimation calculée sur l'estimation de la loi tronquée en ses k premières valeurs.

Exposé en deux parties d'une heure chacune séparée par une pause.
Cet exposé est une introduction aux méthodes d'estimation Bayésienne non-paramétrique. Nous prouverons le théorème de vitesse de convergence de la mesure a posteriori énoncé dans "Convergence rates of posterior distributions" de Ghosal, Ghosh, van der Vaart (2000) et discuterons brièvement ses possibles extensions à des cadres non i.i.d. Ensuite nous étudierons son application dans le cadre de lois a priori construites à partir de processus Gaussiens.

Bibliographie:

• Ghosal, Ghosh, van der Vaart (2000) "Convergence rates of posterior distributions" Ann. Statis. 28(2)
• Ghosal, van der Vaart (2007) "Convergence rates of posterior distributions for noniid observations" Ann. Statis. 35(1)
• van der Vaart and van Zanten "Rates of contraction of posterior distributions based on Gaussian process priors" Ann. Statis. (to appear)

Coder efficacement toutes les sources stationnaires ergodiques sur un alphabet infini n'est pas possible : il faut se restreintre à des classes de processus plus restreintes. Après avoir exposé des résultats généraux pour ces classes, permettant de décider lesquelles sont traitables, je me concentrerai sur les classes dites "enveloppes" (dont les queues de probabilité sont contrôlées), pour lesquelles nous avons obtenu des résultats précis et un algorithme efficace.

Nous étudierons l'article "Mutual Information, Metric Entropy and Cumulative Relative Entropy Risk" de Haussler et Opper (1997). Un statisticien observe un n-échantillon d'une loi P_theta appartenant à une famille {P_theta : theta dans Theta} connue. La redondance, ou entropie relative, mesure la perte de l'estimateur P_n^chapeau. Le risque bayésien sera encadré par des transformées de Laplace de la distance de Hellinger, tandis que le risque minimax sera relié à l'entropie métrique de la famille {P_theta : theta dans Theta} pour cette même distance.
Slides de l'exposé