Joint learning of constraint weights and gradient inputs in Gradient Symbolic Computation with constrained optimization

Max NelsonACL 2020

TL;DR

This paper introduces a novel method for simultaneously learning the weights of linguistic constraints and the "activations" of input symbols within Gradient Symbolic Computation (GSC). By reformulating this problem as a constrained optimization task, they enable the use of powerful optimization techniques like Sequential Quadratic Programming, offering a more robust approach to learning these complex grammars.

What Problem Does This Paper Address?

Traditional linguistic models, particularly those in Optimality Theory (OT), often rely on discrete representations of language. However, phenomena like "opacity" and "exceptionality" are difficult to capture with purely discrete systems. Gradient Symbolic Computation (GSC) offers a solution by allowing for "gradient" or "blended" representations, where linguistic units (like phonemes) can have varying degrees of activation. This introduces a significant learning challenge: not only do we need to learn the weights of linguistic constraints (as in standard OT learning), but we also need to learn the activation levels of input symbols. Previous work has tackled parts of this problem, but a unified approach to learning both constraint weights and input activations simultaneously, especially within the GSC framework, remained an open challenge. This paper aims to bridge that gap by proposing a method that tackles this joint learning problem.

Methods

The core of this paper's contribution lies in its novel approach to learning GSC grammars. The authors first establish a theoretical link: the set of grammars representable by GSC is a subset of those representable by "lexically-scaled faithfulness" (LSF) grammars. This crucial insight allows them to reframe the GSC learning problem. Instead of directly optimizing for GSC, they cast it as a constrained version of the LSF grammar learning problem.

Specifically, they formulate the problem as minimizing a loss function (derived from a Maximum Entropy probability distribution over candidate outputs) subject to a hard constraint. This constraint ensures that the learned LSF grammar is indeed a valid GSC grammar. This "quadratically-constrained optimization problem" is then solved using Sequential Quadratic Programming (SQP), an iterative method well-suited for such problems. This approach leverages existing, well-understood optimization techniques, making the learning process more tractable and robust than previous methods like simulated annealing or gradient descent, which struggled with the non-convexity introduced by gradient inputs.

Datasets

Not discussed in the paper. The paper uses a minimal example of French liaison for illustration, but does not refer to any formal datasets for training or evaluation.

Key Insights and Ideas

  • GSC as a Subset of LSF: The theoretical breakthrough is demonstrating that GSC grammars are a special case of lexically-scaled faithfulness (LSF) grammars. This equivalence is key to reformulating the learning problem.
  • Constrained Optimization for GSC Learning: By framing the GSC learning problem as a constrained LSF learning problem, the authors unlock the power of established optimization techniques like Sequential Quadratic Programming.
  • Non-Convexity of GSC Learning: The paper highlights that the joint learning of constraint weights and gradient inputs in GSC leads to a non-convex optimization problem, making standard gradient descent and related methods unreliable.
  • French Liaison as a Test Case: The application to French liaison demonstrates that the proposed method can learn interpretable grammars that align with existing GSC analyses, showcasing its practical potential.

Key Results

The paper presents a proof-of-concept using the French liaison phenomenon. The proposed learning algorithm, when applied to this example, successfully converges on a solution that resembles existing GSC analyses. Specifically, the model learns:

  • Interpretable Constraint Weights and Activations: The learned parameters reflect the linguistic analysis, with partially activated liaison consonants in words like "petit" and "ami," and near-zero activation in "héros," explaining why liaison occurs in the former but not the latter.
  • Robustness to Non-Convexity: The use of SQP allows the algorithm to navigate the non-convex optimization landscape and find meaningful solutions, as demonstrated by the French liaison example.

Limitations and Future Work

  • Theoretical Expressivity: While the paper establishes a subset-superset relationship between GSC and LSF grammars, it acknowledges that this doesn't fully clarify the linguistic expressivity of each theory. There might be phenomena capturable by GSC that are not easily represented by LSF grammars with a limited constraint set.
  • Computational Complexity: The paper notes that the optimization problem for GSC is inherently more complex than for LSF grammars due to the quadratic nature of the Harmony function.
  • Future Work: The authors suggest exploring the implications of the subset-superset relationship for linguistic theory and comparing the expressivity of GSC and LSF grammars. They also propose further research into finding GSC analyses for linguistic phenomena and evaluating the learnability of GSC grammars. Extending the approach to cover gradiently evaluated markedness constraints is also mentioned.

Summary updated

BibTeX
@inproceedings{nelson2020joint,
  author = {Max Nelson},
  title = {{Joint learning of constraint weights and gradient inputs in Gradient Symbolic Computation with constrained optimization}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
}

Loading related content...

Figure