Séance du 20 janvier 2020

Séance organisée par Stéphane Gaïffas et Marc Hoffmann

Lieu : IHP, amphi Hermite

14.00 : Robin Ryder (Université Paris-Dauphine)

Titre : A Bayesian non-parametric methodology for inferring grammar complexity

Résumé : Based on a set of strings from a language, we wish to infer the complexity of the underlying grammar. To this end, we develop a methodology to choose between two classes of formal grammars in the Chomsky hierarchy: simple regular grammars and more complex context-free grammars. To do so, we introduce a probabilistic context-free grammar model in the form of a Hierarchical Dirichlet Process over rules expressed in Greibach Normal Form. In comparison to other representations, this has the advantage of nesting the regular class within the context-free class. We consider model comparison both by exploiting this nesting, and with Bayes’ factors. The model is fit using a Sequential Monte Carlo method, implemented in the Birch probabilistic programming language. We apply this methodology to data collected from primates, for which the complexity of the grammar is a key question.

Co-authors: Lawrence Murray, Judith Rousseau and Achille Thin

15.00 : Othmane Mounjid (Ecole Polytechnique)

Titre : Improving reinforcement learning algorithms: towards optimal learning rate policies.

Résumé : This paper investigates to what extent one can improve reinforcement learning algorithms. Our study is split in three parts. First, our analysis shows that the classical asymptotic convergence rate $O(1/\sqrt{N})$ is pessimistic and can be replaced by $O((\log(N)/N)^{\beta})$ with $\frac{1}{2}\leq \beta \leq 1$ and $N$ the number of iterations. Second, we propose a dynamic optimal policy for the choice of the learning rate $(\gamma_k)_{k\geq 0}$ used in stochastic algorithms. We decompose our policy into two interacting levels: the inner and the outer level. In the inner level, we present the PASS algorithm (for ``PAst Sign Search'') which, based on a predefined sequence $(\gamma^o_k)_{k\geq 0}$, constructs a new sequence $(\gamma^i_k)_{k\geq 0}$ whose error decreases faster. In the outer level, we propose an optimal methodology for the selection of the predefined sequence $(\gamma^o_k)_{k\geq 0}$. Third, we show empirically that our selection methodology of the learning rate outperforms significantly standard algorithms used in reinforcement learning (RL) in the three following applications: the estimation of a drift, the optimal placement of limit orders and the optimal execution of large number of shares.

16.00 : Jaouad Mourtada (Università di Genova)

Titre : Estimation de densité mal spécifiée, régression logistique et régression aux moindres carrés

Résumé : Nous étudions le problème de l'apprentissage statistique supervisé avec perte logarithmique, c'est-à-dire de l'estimation de densité conditionnelle avec risque de Kullback-Leibler. Il s'agit alors, à partir d'un jeu de données étiquetées supposées i.i.d., de produire un estimateur de la densité conditionnelle de la réponse sachant la variable prédictive. Étant donnée une classe de référence de densités conditionnelles (c'est-à-dire un modèle statistique), l'objectif est de contrôler l'excès de risque par rapport au modèle, c'est-à-dire la différence entre l'erreur de l'estimateur et celle du meilleur élément du modèle. Dans cette approche, nous ne supposons pas que le modèle contienne la vraie loi des observations.

Nous introduisons une nouvelle procédure pour ce problème, le SMP (Sample Minmax Predictor), qui minimise une borne générale d'excès de risque. Nous appliquons en particulier cette procédure au modèle linéaire Gaussien ainsi qu'au problème de la régression logistique. Dans les deux cas, le SMP est une procédure "impropre", c'est-à-dire en dehors du modèle, qui admet une forme explicite. De plus, cet estimateur admet des bornes d'excès de risque en d/n (où d est la dimension du modèle et n le nombre d'observations) qui ne se dégradent pas dans le cas "mal spécifié" où la loi des observations n'appartient pas au modèle. De telles garanties sont inaccessibles à tout estimateur propre (appartenant au modèle) tel que l'estimateur du maximum de vraisemblance (éventuellement pénalisé), et améliorent également les garanties obtenues par réduction à une variante séquentielle du problème.

Nous revisitons au passage le problème de la régression linéaire (du point de vue prédictif), où nous étudions l'influence de la loi des variables prédictives sur la difficulté du problème au sens minimax. Notre analyse repose sur un contrôle des moments négatifs de matrices de covariances empiriques, sous une hypothèse minimale de régularité.