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

Area of Science:

• Computational Linguistics
• Machine Learning
• Natural Language Processing

Background:

• Natural language parsing is often framed within structured output prediction using maximum-margin methods.
• Efficient training relies on cutting-plane algorithms, which depend on effective inference for constraint identification.

Purpose of the Study:

• To develop an efficient inference algorithm for training maximum-margin parsers.
• To extend the Cocke-Kasami-Younger (CKY) algorithm for loss-augmented inference.

Main Methods:

• The study extends the Cocke-Kasami-Younger (CKY) algorithm to incorporate loss-augmented inference.
• This extension is applied within the cutting-plane optimization framework for structured output prediction.

Main Results:

• The derived algorithm guarantees finding an optimal solution in polynomial time.
• The computational overhead is a term dependent on the number of possible loss values, exceeding standard CKY runtime.

Conclusions:

• The enhanced CKY algorithm provides an effective approach for training maximum-margin natural language parsers.
• Experimental results demonstrate the feasibility and efficiency of the proposed method for parsing English sentences.