Dynamische Programmierung im Rangraum: Skalierung strukturierter Inferenz mit low-rank HMMs und PCFGs

Versteckte Markov-Modelle (HMMs) und probabilistische kontextfreie Grammatiken (PCFGs) sind weit verbreitete strukturierte Modelle, die beide als Faktorgraphgrammatiken (FGGs) dargestellt werden können, eine mächtige Formulierung, die ein breites Spektrum von Modellen beschreiben kann. Neuere Forschungen haben gezeigt, dass es vorteilhaft ist, große Zustandsräume für HMMs und PCFGs zu verwenden. Allerdings ist die Inferenz mit großen Zustandsräumen rechnerisch anspruchsvoll, insbesondere bei PCFGs. Um dieser Herausforderung zu begegnen, nutzen wir die Tensor-Rangzerlegung (auch bekannt als CPD), um die rechnerischen Komplexitäten der Inferenz für einen Teilmenge von FGGs abzusenken, die HMMs und PCFGs umfasst. Wir wenden CPD auf die Faktoren einer FGG an und konstruieren dann eine neue FGG im Rangraum. Die Inferenz mit der neuen FGG liefert das gleiche Ergebnis, hat aber eine geringere Zeitkomplexität, wenn der Rangraum kleiner als der Zustandsraum ist. Wir führen Experimente zur Sprachmodellierung mit HMMs und zum unüberwachten Parsing mit PCFGs durch und zeigen bessere Leistungen als frühere Arbeiten. Unser Code ist öffentlich verfügbar unter \url{https://github.com/VPeterV/RankSpace-Models}.