Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

• URL: http://arxiv.org/abs/2212.09140v2
• Date: Fri, 9 Jun 2023 15:42:50 GMT
• Title: Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars
• Authors: Songlin Yang, Roger P. Levy, Yoon Kim
• Abstract summary: We study grammar induction with mildly context-sensitive grammars for unsupervised discontinuous parsing. Our approach fixes the rule structure in advance and focuses on parameter learning with maximum likelihood. Experiments on German and Dutch show that our approach is able to induce linguistically meaningful trees with continuous and discontinuous structures.
• Score: 14.256041558454786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study grammar induction with mildly context-sensitive grammars for unsupervised discontinuous parsing. Using the probabilistic linear context-free rewriting system (LCFRS) formalism, our approach fixes the rule structure in advance and focuses on parameter learning with maximum likelihood. To reduce the computational complexity of both parsing and parameter estimation, we restrict the grammar formalism to LCFRS-2 (i.e., binary LCFRS with fan-out two) and further discard rules that require O(n^6) time to parse, reducing inference to O(n^5). We find that using a large number of nonterminals is beneficial and thus make use of tensor decomposition-based rank-space dynamic programming with an embedding-based parameterization of rule probabilities to scale up the number of nonterminals. Experiments on German and Dutch show that our approach is able to induce linguistically meaningful trees with continuous and discontinuous structures

Related papers

• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs) Ins, the unknown dependency of future observations and rewards from the past interactions can be captured experimentally. Many algorithms first reconstruct this unknown dependency using automata learning techniques.
  arXiv  Detail & Related papers  (2024-09-04T14:26:58Z)
• Scalable Learning of Latent Language Structure With Logical Offline Cycle Consistency [71.42261918225773]
  Conceptually, LOCCO can be viewed as a form of self-learning where the semantic being trained is used to generate annotations for unlabeled text. As an added bonus, the annotations produced by LOCCO can be trivially repurposed to train a neural text generation model.
  arXiv  Detail & Related papers  (2023-05-31T16:47:20Z)
• Learning of Structurally Unambiguous Probabilistic Grammars [7.347989843033034]
  We show that a CMTA can be converted into a probabilistic grammar. We show that the learned CMTA can be converted into a complete algorithm for learning a structurally unambiguous probabilistic context free grammar.
  arXiv  Detail & Related papers  (2022-03-17T17:01:51Z)
• Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks [0.0]
  Probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs) are widely used sequence models with complementary strengths and limitations. We present Recursive Bayesian Networks (RBNs), which generalise and unify PCFGs and DBNs, combining their strengths and containing both as special cases.
  arXiv  Detail & Related papers  (2021-11-02T19:21:15Z)
• Extracting Grammars from a Neural Network Parser for Anomaly Detection in Unknown Formats [79.6676793507792]
  Reinforcement learning has recently shown promise as a technique for training an artificial neural network to parse sentences in some unknown format. This paper presents procedures for extracting production rules from the neural network, and for using these rules to determine whether a given sentence is nominal or anomalous.
  arXiv  Detail & Related papers  (2021-07-30T23:10:24Z)
• PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols [22.728124473130876]
  We present a new parameterization form of PCFGs based on tensor decomposition. We use neural parameterization for the new form to improve unsupervised parsing performance. We evaluate our model across ten languages and empirically demonstrate the effectiveness of using more symbols.
  arXiv  Detail & Related papers  (2021-04-28T12:25:27Z)
• Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version) [6.3455238301221675]
  We present an algorithm for extracting the context free grammars (CFGs) from a trained recurrent neural network (RNN) We develop a new framework, pattern rule sets (PRSs), which describe sequences of deterministic finite automata (DFAs) that approximate a non-regular language. We show how the PRS may converted into a CFG, enabling a familiar and useful presentation of the learned language.
  arXiv  Detail & Related papers  (2021-01-20T16:22:25Z)
• Learning of Structurally Unambiguous Probabilistic Grammars [7.347989843033034]
  We restrict attention to structurally unambiguous weighted context-free grammars (SUWCFG) We show that SUWCFG can be represented using co-linear multiplicity tree automata (CMTA), and provide a learning algorithm that learns CMTAs. We demonstrate the usefulness of our algorithm in learning PCFGs over genomic data.
  arXiv  Detail & Related papers  (2020-11-15T08:07:04Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation [77.7420231319632]
  We adapt contextual generation of categorical sequences to a policy gradient estimator, which evaluates a set of correlated Monte Carlo (MC) rollouts for variance control. We also demonstrate the use of correlated MC rollouts for binary-tree softmax models, which reduce the high generation cost in large vocabulary scenarios.
  arXiv  Detail & Related papers  (2019-12-31T03:01:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.