Matroids Hitting Sets and Unsupervised Dependency Grammar Induction
This paper formulates a novel problem on graphs: find the minimal subset of edges in a fully connected graph, such that the resulting graph contains all spanning trees for a set of specifed sub-graphs. This formulation is motivated by an un-supervised grammar induction problem from computational linguistics. We present a reduction to some known problems and algorithms from graph theory, provide computational complexity results, and describe an approximation algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency Grammar InductionSimilar Papers 제목 키워드 기반
StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling
There are two major classes of natural language grammar -- the dependency grammar that models one-to-one correspondences between words and the constituency grammar that models the assembly of one or several corresponded …
Constituency ParsingDependency ParsingLanguage ModelingLanguage Modelling+2Unsupervised Induction of Tree Substitution Grammars for Dependency Parsing
Inducing a grammar directly from text is one of the oldest and most challenging tasks in Computational Linguistics. Significant progress has been made for inducing dependency grammars, however the models employed are ove…
Dependency Grammar InductionDependency ParsingUnsupervised Dependency ParsingDependency Induction Through the Lens of Visual Perception
Most previous work on grammar induction focuses on learning phrasal or dependency structure purely from text. However, because the signal provided by text alone is limited, recently introduced visually grounded syntax mo…
Constituency Grammar InductionConstituency ParsingDependency ParsingShared Logistic Normal Distributions for Soft Parameter Tying in Unsupervised Grammar Induction
We present a family of priors over probabilistic grammar weights, called the shared logistic normal distribution. This family extends the partitioned logistic normal distribution, enabling factored covariance between the…
Dependency Grammar InductionUnsupervised Dependency ParsingDependency Grammar Induction with a Neural Variational Transition-based Parser
Dependency grammar induction is the task of learning dependency syntax without annotated training data. Traditional graph-based models with global inference achieve state-of-the-art results on this task but they require …
Dependency Grammar InductionVariational Inference