2015/11/04 by Guillaume Rabusseau, Borja Balle, Rabusseau, Guillaume +3
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Natural Language Processing Techniques #cs.FL #cs.LG
paper · pdf · doi:10.48550/arxiv.1511.01442
To appear in AISTATS 2016
openalex publication_date 2015/11/04 · arxiv created 2015/12/24 · arxiv updated 2015/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.