Low-Rank Approximation of Weighted Tree Automata

Guillaume Rabusseau, Borja Balle, Shay Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We describe a technique to minimize weighted tree automata (WTA), a powerful formalisms that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our method relies on a singular value decomposition of the underlying Hankel matrix defined by the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an infinite Hankel matrix implicitly represented as a WTA. We provide an analysis of the approximation error induced by the minimization, and we evaluate our method on real-world data originating in newswire treebank. We show that the model achieves lower perplexity than previous methods for PCFG minimization, and also is much more stable due to the absence of local optima.
Original languageEnglish
Title of host publicationProceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) 2016
Pages839-847
Number of pages23
Volume38
Publication statusPublished - 2016
Event19th International Conference on Artificial Intelligence and Statistics - Cadiz, Spain
Duration: 9 May 201611 May 2016
https://www.aistats.org/aistats2016/

Conference

Conference19th International Conference on Artificial Intelligence and Statistics
Abbreviated titleAI and Statistics 2016
Country/TerritorySpain
CityCadiz
Period9/05/1611/05/16
Internet address

Fingerprint

Dive into the research topics of 'Low-Rank Approximation of Weighted Tree Automata'. Together they form a unique fingerprint.

Cite this