Spectral Unsupervised Parsing with Additive Tree Metrics

We propose a spectral approach for unsupervised constituent parsing that comes with theoretical guarantees on latent structure recovery. Our approach is grammarless ‐ we directly learn the bracketing structure of a given sentence without using a grammar model. The main algorithm is based on lifting the concept of additive tree metrics for structure learning of latent 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 projective trees we find that it can be found using bilexical parsing algorithms. Empirically, our algorithm performs favorably compared to the constituent context model of Klein and Manning (2002) without the need for careful initialization.

• Publication year

  2014

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2014-06-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/v1/P14-1100
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Nonconvex Global Optimization for Latent-Variable Models

  2013cited by this paper
• Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction

  2013cited by this paper
• Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion

  2013cited by this paper
• Identifiability and Unmixing of Latent Parse Trees

  2012cited by this paper
• Spectral Learning of Latent-Variable PCFGs

  2012cited by this paper
• Two Step CCA: A new spectral method for estimating vector models of words

  2012cited by this paper
• Concavity and Initialization for Unsupervised Dependency Parsing

  2012cited by this paper
• Unfolding Latent Tree Structures using 4th Order Tensors

  2012cited by this paper
• Empirical Risk Minimization for Probabilistic Grammars: Sample Complexity and Hardness of Learning

  2012cited by this paper
• A Feature-Rich Constituent Context Model for Grammar Induction

  2012cited by this paper
• Greedy Learning of Binary Latent Trees

  2011cited by this paper
• A Universal Part-of-Speech Tagset

  2011cited by this paper
• Spectral Methods for Learning Multivariate Latent Tree Structure

  2011influential reference
• A Spectral Algorithm for Latent Tree Graphical Models

  2011cited by this paper
• Kernel Embeddings of Latent Tree Graphical Models

  2011cited by this paper
• On Sparse Nonparametric Conditional Covariance Selection

  2010influential reference
• Word Representations: A Simple and General Method for Semi-Supervised Learning

  2010cited by this paper
• From Baby Steps to Leapfrog: How “Less is More” in Unsupervised Dependency Parsing

  2010cited by this paper
• Learning Latent Tree Graphical Models

  2010influential reference
• Viterbi Training Improves Unsupervised Dependency Parsing

  2010cited by this paper
• Sparsity in Dependency Grammar Induction

  2010cited by this paper
• Grammatical inference as a principal component analysis problem

  2009cited by this paper
• Improving Unsupervised Dependency Parsing with Richer Contexts and Smoothing

  2009cited by this paper
• Shared Logistic Normal Distributions for Soft Parameter Tying in Unsupervised Grammar Induction

  2009cited by this paper
• A spectral algorithm for learning Hidden Markov Models

  2008cited by this paper
• Estimating time-varying networks

  2008influential reference
• Time varying undirected graphs

  2008influential reference
• The minimum evolution distance-based approach of phylogenetic inference

  2007influential reference
• Fast Unsupervised Incremental Parsing

  2007cited by this paper
• Contrastive Estimation: Training Log-Linear Models on Unlabeled Data

  2005cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2004cited by this paper
• A Generative Constituent-Context Model for Improved Grammar Induction

  2002cited by this paper
• Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

  1999cited by this paper
• A few logs suffice to build (almost) all trees (l): part I

  1997cited by this paper
• Building a Large Annotated Corpus of English: The Penn Treebank

  1993influential reference
• Theoretical foundation of the minimum-evolution method of phylogenetic inference.

  1993cited by this paper
• Class-Based n-gram Models of Natural Language

  1992cited by this paper
• Basic Methods of Probabilistic Context Free Grammars

  1992cited by this paper
• The neighbor-joining method: a new method for reconstructing phylogenetic trees.

  1987cited by this paper
• A Note on the Metric Properties of Trees

  1974cited by this paper
• The Recovery of Trees from Measures of Dissimilarity

  1971cited by this paper
• Approximating discrete probability distributions with dependence trees

  1968cited by this paper

• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees

  2022cites this paper
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees

  2021cites this paper
• Co-training an Unsupervised Constituency Parser with Weak Supervision

  2021cites this paper
• Thesis Proposal

  2020cites this paper
• Unsupervised Recurrent Neural Network Grammars

  2019cites this paper
• Compound Probabilistic Context-Free Grammars for Grammar Induction

  2019cites this paper
• Aspect based sentiment analysis by a linguistically regularized CNN with gated mechanism

  2019cites this paper
• Deep Latent Variable Models of Natural Language

  2018cites this paper
• Kernel and Moment Based Prediction and Planning : Applications to Robotics and Natural Language Processing

  2018influential citation
• Relation Classification via BiLSTM-CNN

  2018cites this paper
• 3 Canonical Correlation Analysis for Deriving Word Embeddings

  2017cites this paper
• Distant supervised relation extraction via long short term memory networks with sentence embedding

  2017cites this paper
• Explorer Encoding Prior Knowledge with Eigenword Embeddings

  2017cites this paper
• ExploringWeakly Labeled Data Across the Noise-Bias Spectrum

  2016cites this paper
• Joint Learning of Constituency and Dependency Grammars by Decomposed Cross-Lingual Induction

  2015cites this paper
• Spectral Probablistic Modeling and Applications to Natural Language Processing

  2015cites this paper
• Spectral Semi-Supervised Discourse Relation Classification

  2015cites this paper
• A convex and feature-rich discriminative approach to dependency grammar induction

  2015cites this paper
• Distant Supervision for Relation Extraction via Piecewise Convolutional Neural Networks

  2015cites this paper
• Encoding Prior Knowledge with Eigenword Embeddings

  2015cites this paper
• Eigenwords: spectral word embeddings

  2015cites this paper
• Advances in spectral learning with applications to text analysis and brain imaging

  2014cites this paper
• Proposal Context Awareness and Personalization in Dialogue Planning

  2014cites this paper
• Spectral Learning Techniques for Weighted Automata, Transducers, and Grammars

  2014cites this paper
• Spectral Probabilistic Modeling and Applications to Natural Language Processing

  2013cites this paper
• Research Statement 1 Overview

  year unknowncites this paper