research-article

Free access

Concise integer linear programming formulations for dependency parsing

Authors:

André F. T. Martins,

Eric P. XingAuthors Info & Claims

ACL '09: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 1

Pages 342 - 350

Published: 02 August 2009 Publication History

Abstract

We formulate the problem of non-projective dependency parsing as a polynomial-sized integer linear program. Our formulation is able to handle non-local output features in an efficient manner; not only is it compatible with prior knowledge encoded as hard constraints, it can also learn soft constraints from data. In particular, our model is able to learn correlations among neighboring arcs (siblings and grandparents), word valency, and tendencies toward nearly-projective parses. The model parameters are learned in a max-margin framework by employing a linear programming relaxation. We evaluate the performance of our parser on data in several natural languages, achieving improvements over existing state-of-the-art methods.

References

[1]

E. Boros and P. L. Hammer. 2002. Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1--3):155--225.

Digital Library

[2]

S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proc. of CoNLL.

Digital Library

[3]

X. Carreras, M. Collins, and T. Koo. 2008. TAG, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proc. of CoNLL.

Digital Library

[4]

X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. of CoNLL.

[5]

M. Chang, L. Ratinov, and D. Roth. 2008. Constraints as prior knowledge. In ICML Workshop on Prior Knowledge for Text and Language Processing.

[6]

Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396--1400.

[7]

J. Clarke and M. Lapata. 2008. Global inference for sentence compression an integer linear programming approach. JAIR, 31:399--429.

Digital Library

[8]

K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. JMLR, 7:551--585.

Digital Library

[9]

A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. of ACL.

Digital Library

[10]

P. Denis and J. Baldridge. 2007. Joint determination of anaphoricity and coreference resolution using integer programming. In Proc. of HLT-NAACL.

[11]

Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammar. In Proc. of ACL.

Digital Library

[12]

J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233--240.

[13]

J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proc. of ACL.

Digital Library

[14]

J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of COLING.

Digital Library

[15]

S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudo-projectivity: a polynomially parsable non-projective dependency grammar. In Proc. of COLING-ACL.

Digital Library

[16]

S. Lacoste-Julien, B. Taskar, D. Klein, and M. I. Jordan. 2006. Word alignment via quadratic assignment. In Proc. of HLT-NAACL.

Digital Library

[17]

T. L. Magnanti and L. A. Wolsey. 1994. Optimal Trees. Technical Report 290-94, Massachusetts Institute of Technology, Operations Research Center.

[18]

A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing. 2008. Stacking dependency parsers. In Proc. of EMNLP.

Digital Library

[19]

A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009. Polyhedral outer approximations with application to natural language parsing. In Proc. of ICML.

Digital Library

[20]

R. T. McDonald and F. C. N. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of EACL.

[21]

R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of IWPT.

Digital Library

[22]

R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP.

Digital Library

[23]

J. Nivre and R. McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proc. of ACL-HLT.

[24]

V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004. Semantic role labeling via integer linear programming inference. In Proc. of COLING.

Digital Library

[25]

M. Richardson and P. Domingos. 2006. Markov logic networks. Machine Learning, 62(1):107--136.

Digital Library

[26]

S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of EMNLP.

Digital Library

[27]

R. T. Rockafellar. 1970. Convex Analysis. Princeton University Press.

[28]

D. Roth and W. T. Yih. 2005. Integer linear programming inference for conditional random fields. In ICML.

Digital Library

[29]

A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer.

[30]

D. A. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of EMNLP.

Digital Library

[31]

M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, and J. Nivre. 2008. The conll-2008 shared task on joint parsing of syntactic and semantic dependencies. Proc. of CoNLL.

Digital Library

[32]

R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25--36.

[33]

M. Wang, N. A. Smith, and T. Mitamura. 2007. What is the Jeopardy model? A quasi-synchronous grammar for QA. In Proceedings of EMNLP-CoNLL.

[34]

Y. Zhang and S. Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search. In Proc. of EMNLP.

Digital Library

Cited By

Wang KHe HNguyen TKumar PRoth DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)On regularization and inference with label constraintsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619893(35740-35762)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619893
Li YSaeed DZhang XZiebart BGimpel KKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Moment distributionally robust tree structured predictionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601159(12237-12252)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601159
Meshi OLondon BWeller ASontag D(2019)Train and test tightness of LP relaxations in structured predictionThe Journal of Machine Learning Research10.5555/3322706.332271920:1(480-513)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3322706.3322719
Show More Cited By

Index Terms

Concise integer linear programming formulations for dependency parsing

Recommendations

Incremental integer linear programming for non-projective dependency parsing
EMNLP '06: Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing

Integer Linear Programming has recently been used for decoding in a number of probabilistic models in order to enforce global constraints. However, in certain applications, such as non-projective dependency parsing and machine translation, the complete ...
Integer Linear Programming Approach to Dependency Parsing for MALAYALAM
ITC '10: Proceedings of the 2010 International Conference on Recent Trends in Information, Telecommunication and Computing

This paper is an attempt to show that a dependency parser for Malayalam language can be produced using Integer Linear Programming Approach. We describe a process for developing a parser by incorporating the Paninian Grammar concepts in Malayalam.
Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '09: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 1

August 2009

572 pages

ISBN:9781932432459

General Chair:
Keh-Yih Su
Behavior Design Corp., Taiwan

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 02 August 2009

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
681
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)6

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang KHe HNguyen TKumar PRoth DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)On regularization and inference with label constraintsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619893(35740-35762)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619893
Li YSaeed DZhang XZiebart BGimpel KKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Moment distributionally robust tree structured predictionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601159(12237-12252)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601159
Meshi OLondon BWeller ASontag D(2019)Train and test tightness of LP relaxations in structured predictionThe Journal of Machine Learning Research10.5555/3322706.332271920:1(480-513)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3322706.3322719
Sun WChen YWan XLiu M(2019)Parsing chinese sentences with grammatical relationsComputational Linguistics10.1162/coli_a_0034345:1(95-136)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1162/coli_a_00343
Sachan MXing EGuo YFarooq F(2018)Parsing to ProgramsProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3219819.3219972(2140-2149)Online publication date: 19-Jul-2018
https://dl.acm.org/doi/10.1145/3219819.3219972
Das DChen DMartins ASchneider NSmith N(2014)Frame-semantic parsingComputational Linguistics10.1162/COLI_a_0016340:1(9-56)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1162/COLI_a_00163
Smith NMartins A(2013)Linguistic structure prediction with the sparseptronXRDS: Crossroads, The ACM Magazine for Students10.1145/2425676.242569019:3(44-48)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2425676.2425690
Bach NMinh NOanh TShimazu A(2013)A Two-Phase Framework for Learning Logical Structures of Paragraphs in Legal ArticlesACM Transactions on Asian Language Information Processing10.1145/2425327.242533012:1(1-32)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2425327.2425330
Bohnet BNivre JTsujii JHenderson JPasca M(2012)A transition-based system for joint part-of-speech tagging and labeled non-projective dependency parsingProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391114(1455-1465)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391114
Srikumar VKundu GRoth DTsujii JHenderson JPasca M(2012)On amortizing inference cost for structured predictionProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391073(1114-1124)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391073
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents