Three New Probabilistic Models for Dependency Parsing: An Exploration

What it is about

The paper gives an O(n^3) bottom-up dynamic-programming parser for projective dependency trees, which became the basis of most projective decoders. On top of it Eisner proposes three probabilistic models: a bigram lexical affinity model (A), a sense-tagging model (B) in which words are generated with their selectional preferences, and a generative model (C) in which each word fleshes out its own children, speaker-oriented. He trains them on dependency trees derived from the Wall Street Journal part of the Penn Treebank and tests on 400 held-out sentences. Model C performs best; the paper's full results give 93% correct tags and 87% correct parents for model C, while the pilot tables are the basis for the ranking. The main claim is that lexical word-pair statistics, not constituents, carry most of the parsing signal.

For Mova

I1. gparse/src/eisner.rs: use the Eisner chart as an exact decoder over the same scores as en's perceptron, and report the search error: the share of EWT test sentences where the greedy en tree scores below the projective optimum.
I2. en/src/parse.rs: check whether word-pair features (head word times child word) are present; if not, add them as in model A and measure cv LAS on the train folds.
I3. en/src/ud.rs backoff tables: test whether conditioning the UPOS and FEATS backoff on the head lexeme, as in model C, improves UFeats on EWT test (95.66 now), with a run of en ud-eval each.

The chapters that match are 22-phrases and 23-complementation, where selectional preferences of heads and complements are described. The code touched is gparse/src/eisner.rs (the exact projective decoder), en/src/parse.rs (lexical features) and en/src/ud.rs. Measure first: the search error of en against the Eisner optimum on EWT test (idea I1), since it says whether better search is worth more than better features.

Institutions

🎓University of PennsylvaniaPhiladelphia ·

United States143 works · 56,645 citations

Topics Dependency parsing

Cite

Cite as Jason M. Eisner. 1996. Three New Probabilistic Models for Dependency Parsing: An Exploration. COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics.

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/992628.992688

@inproceedings{eisner1996three,
  title = {{Three New Probabilistic Models for Dependency Parsing: An Exploration}},
  author = {Jason M. Eisner},
  booktitle = {COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics},
  year = {1996},
  doi = {10.3115/992628.992688},
  url = {https://doi.org/10.3115/992628.992688}
}

References

6 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

Ezra Bla.(:k, Fred ,lelinck, et a.1. 1992. Towards history-ba,sed gramnl~u:s: using richer mod(,.ls [br probabilistic i,~trsing. [u Fifth I)AI~,FA Worksh.op ou £'pecch and Natural Language, Arden (7onfcrcn(:c Ceutcr, llnrrim~m, New York, Febrl,u'y. find
['(enne.th W. (3mr(:h. 1988. A stochastic parts pro-gi:ntll a, nd noun l)hra,se parser for unrestri(:tcd text. In /'roe, of the 2rid (;onf. on Applied Natural Lang'uage lJroccssing, 136 148, Austin, TX. Asso(:i~Lti(,n for ('~omput~Ltimml l,inguistics, Morristowu, N.I. find
Mi(:ha.el ./. (',ollins. 1996. A new statistical parser based on bigr~un lexi(:~fl del)cndeucies, h, l~rocc.cd - iTtfJS of tit(; 24th A CL, S~l, nt~,, (~171'Z, (]A, July. find
Ja.sol! 1'3isner. 199(;. An empirical (:omp~H'ison of prob-~dfility nlodcls for dependeucy gl:a, lnnlaJ:. Teehnic;d ILeport IRCS 96 11, University of PennsylvaJtilt. I!'red .felinck. 1985. M~rkov sour(:e modeliug of text gener~Ltiou. In .I. Skwirzinski, editor, hnpact of IS"o-tossing 7~chniques ou (… find
Igor A, Mel'(:uk. 1988. l)cpcndcncy Syntax: 7?worg and l'racticc. St~te University of New York Press. find
IL Meria.hlo. 1990. Tagging text with ;L probabilistic model, lu l~rocccdinw of the IBM Natural Language. 17'L, Paris, Fra.nce, pp. 161-172. find

This page in Markdown → https://md.research.elamur.ai/free/en/papers/eisner-1996-three-new-probabilistic-models-dependency/

📄 Three New Probabilistic Models for Dependency Parsing: An Exploration