Programmation dynamique dans l’espace des rangs : mise à l’échelle de l’inférence structurée avec des HMMs et PCFGs de faible rang

Les modèles de Markov cachés (HMMs) et les grammaires contextuelles probabilistes (PCFGs) sont des modèles structurés largement utilisés, tous deux pouvant être représentés sous forme de grammaires de graphes factorisés (FGGs), un formalisme puissant capable de décrire une gamme étendue de modèles. Des recherches récentes ont montré qu'il était avantageux d'utiliser des espaces d'états importants pour les HMMs et les PCFGs. Cependant, l'inférence dans ces grands espaces d'états est exigeante sur le plan computationnel, particulièrement pour les PCFGs. Pour relever ce défi, nous utilisons la décomposition du rang tensoriel (aussi connue sous le nom de CPD) afin de réduire la complexité computationnelle de l'inférence pour un sous-ensemble des FGGs englobant les HMMs et les PCFGs. Nous appliquons la CPD aux facteurs d'un FGG, puis construisons un nouveau FGG défini dans l'espace de rang. L'inférence avec ce nouveau FGG produit le même résultat mais présente une complexité temporelle inférieure lorsque la taille du rang est plus petite que celle de l'espace d'états. Nous menons des expériences en modélisation linguistique par HMM et en analyse syntaxique non supervisée par PCFG, montrant des performances supérieures à celles des travaux précédents. Notre code est disponible au public sur \url{https://github.com/VPeterV/RankSpace-Models}.