Spectral Unsupervised Parsing with Additive Tree Metrics

We propose a spectral approach for un-supervised constituent parsing that comes with theoretical guarantees on latent struc-ture recovery. Our approach is grammar-less – we directly learn the bracketing structure of a given sentence without us-ing a grammar model. The main algorithm is based on lifting the concept of additive tree metrics for structure learning of la-tent trees in the phylogenetic and machine learning communities to the case where the tree structure varies across examples. Although finding the “minimal ” latent tree is NP-hard in general, for the case of pro-jective trees we find that it can be found using bilexical parsing algorithms. Empir-ically, our algorithm performs favorably compared to the constituent context model of Klein and Manning (2002) without the need for careful initialization.