Accurate Maximum-Margin Training for Parsing with Context-Free Grammars

Alexander Bauer, Mikio Braun, Klaus Robert Muller

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


The task of natural language parsing can naturally be embedded in the maximum-margin framework for structured output prediction using an appropriate joint feature map and a suitable structured loss function. While there are efficient learning algorithms based on the cutting-plane method for optimizing the resulting quadratic objective with potentially exponential number of linear constraints, their efficiency crucially depends on the inference algorithms used to infer the most violated constraint in a current iteration. In this paper, we derive an extension of the well-known Cocke-Kasami-Younger (CKY) algorithm used for parsing with probabilistic context-free grammars for the case of loss-augmented inference enabling an effective training in the cutting-plane approach. The resulting algorithm is guaranteed to find an optimal solution in polynomial time exceeding the running time of the CKY algorithm by a term, which only depends on the number of possible loss values. In order to demonstrate the feasibility of the presented algorithm, we perform a set of experiments for parsing English sentences.

Original languageEnglish
Pages (from-to)44-56
Number of pages13
JournalIEEE Transactions on Neural Networks and Learning Systems
Issue number1
Publication statusPublished - 2017 Jan

Bibliographical note

Funding Information:
This work was supported by the Federal Ministry of Education and Research (BMBF) under the Berlin Big Data Center project (FKZ 01IS14013A) and by the Brain Korea 21 program through the National Research Foundation (NRF) of Korea within the Ministry of Education.

Publisher Copyright:
© 2012 IEEE.


  • Context-free grammar (CFG)
  • dynamic programming
  • inference
  • margin rescaling (MR)
  • natural language parsing
  • probabilistic context-free grammar (PCFG)
  • slack rescaling (SR)
  • structural support vector machines (SVMs)
  • structured output

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Accurate Maximum-Margin Training for Parsing with Context-Free Grammars'. Together they form a unique fingerprint.

Cite this