Elamur Research⌕
☰
home / papers / 2008 / Dependency Parsing by Belief Propagation

Dependency Parsing by Belief Propagation

Paper · 2008 · David Smith and Jason Eisner

Summary

Higher-order features in dependency parsing, such as interactions between grandparent, parent and child or between sibling links, tend to improve accuracy. The cost is that exact projective parsing becomes slower and exact non-projective parsing becomes NP-hard. Smith and Eisner recast parsing as a Markov random field. Boolean variables stand for candidate links, soft factors score single links or combinations of links, and a new kind of hard global factor (TREE or PTREE) forces the output to be a valid tree. They then run loopy belief propagation (BP) over this model for both training and decoding. The global tree factor sends its messages using an ordinary first-order parser as a subroutine. Higher-order factors repeatedly adjust the edge weights that this parser sees. Each iteration costs O(n³), and adding more features increases runtime additively rather than multiplicatively. In experiments on Danish, Dutch and English, BP-based models with higher-order factors beat first-order baselines. They were also faster and more accurate than the earlier hill-climbing approximation for non-projective parsing. The work shows that intractable structured models can be handled by message passing that wraps an efficient combinatorial algorithm.

Key points

  • Model components:
    • LINK factors borrow their feature set from McDonald et al. (2005).
    • Higher-order factors include GRAND, SIB, CHILDSEQ (a weighted split head-automaton parametrization) and NOCROSS.
    • Optional TAG, TAGLINK and TRIGRAM factors allow tags to be inferred jointly with the parse.
  • Non-projective experiments:
    • The languages were Danish and Dutch, which are highly non-projective, and English, which is only slightly so.
    • First-order parsers produced far too many crossing links, so NOCROSS, GRAND and CHILDSEQ factors were added.
    • Each of these significantly beat the first-order baseline, though the gains did not always add up.
  • Comparison with hill-climbing: BP outperformed the hill-climbing method of McDonald and Pereira (2006) in both speed and accuracy. It also yields approximate marginals rather than a single best parse.
  • Weaker constraints at decoding (Table 3, 5 BP iterations):
    • For a first-order model trained with TREE, decoding with weaker constraints is usually harmful.
    • NOT2 drops Danish from 85.5 to 81.8.
    • Using weak constraints during training as well hurts more; English falls to 66.4 under NOT2.
    • Decoding with PTREE slightly helps Danish (85.8) and English (88.8) but hurts Dutch (83.9).
  • Search error (Danish, higher-order projective model PTREE+LINK+GRAND): relative to the MBR parse, weakened decoding constraints gave 2.2% error for NOT2, 2.1% for EXACTLY1, 1.7% for EXACTLY1+NO2CYCLE, and 0.0% for PTREE.

Interesting ideas

  • I1. Use a fast exact solver as a message-passing component. Embed an efficient algorithm for the core structure (here a first-order parser) inside BP so it computes the messages of a global constraint factor. This keeps known combinatorial structure while still allowing rich, intractable interactions, which could carry over to alignment or other structured prediction tasks in Ukrainian NLP.
  • I2. Self-stacking with soft beliefs. The parser repeatedly refeeds its own probabilistic output, not a 1-best parse, to reweight edges until it converges. This is a principled alternative to multi-stage pipelines in which one model feeds features to another.
  • I3. Merge small constraints into larger factors. Replacing many pairwise constraints with one global constraint, such as NOT2 versus ATMOST1, leaves the distribution unchanged but makes BP more accurate. This design rule applies to any loopy graphical model.
  • I4. Train under the true constraints even if decoding is cheaper. Training with the full TREE constraint was essential. At test time, a weaker global constraint (EXACTLY1 plus MBR decoding to remove cycles) may suffice and runs in O(n²).
  • I5. Joint inference over shared input. Tags, link roles and parse links can all live in one factor graph and influence each other cheaply. This is attractive for joint POS tagging and parsing on UD treebanks for morphologically rich languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Johns Hopkins UniversityBaltimore · United States187 works · 92,194 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

🧭 Topics 1 Dependency parsing · 120 works

Cite

Cite as David Smith and Jason Eisner. 2008. Dependency Parsing by Belief Propagation. Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{smith2008dependency,
  title = {{Dependency Parsing by Belief Propagation}},
  author = {David Smith and Jason Eisner},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613737},
  url = {https://doi.org/10.3115/1613715.1613737}
}

References

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

  1. C. Bessière and J.-C. Régin. 1997. Arc consistency for general constraint networks: preliminary results. In IJCAI, pages 398–404. find
  2. L. Bottou. 2003. Stochastic learning. In Advanced Lectures in Machine Learning, pages 146–168. Springer. find
  3. A. Braunstein, M. Mezard, and R. Zecchina. 2005. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms, 27:201–226. find
  4. M. Buch-Kromann. 2006. Discontinuous Grammar. A Model of Human Parsing and Language Acquisition”. Dr.ling.merc. dissertation, Copenhagen Business School. find
  5. E. Charniak and M. Johnson. 2005. Coarse-to-fine nbest parsing and maxent discriminative reranking. In ACL, pages 173–180. find
  6. D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
  7. R. Dechter. 2003. Constraint Processing. Morgan Kaufmann. find
  8. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using combinatorial optimization within max-product belief propagation. In NIPS 2006, pages 369–376. find
  9. J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In ACL, pages 457–480.
  10. J. Eisner, E. Goldlust, and N. A. Smith. 2005. Compiling comp ling: Weighted dynamic programming and the dyna language. In HLT-EMNLP, pages 281–290. find
  11. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In COLING.
  12. G. Elidan, I. McGraw, and D. Koller. 2006. Residual belief propagation: Informed scheduling for asynchronous message passing. In UAI. find
  13. J. T. Goodman. 1996. Parsing algorithms and metrics. In ACL, pages 177–183. find
  14. J. Goodman. 1999. Semiring parsing. Computational Linguistics, 25(4):573–605. find
  15. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In ACL, pages 586–594. find
  16. T. Koo, A. Globerson, X. Carreras, and M. Collins. 2007. Structured prediction models via the Matrix-Tree Theorem. In EMNLP-CoNLL. find
  17. D. MacKay. 2003. Information Theory, Inference, and Learning Algorithms. Cambridge. find
  18. A. Mackworth. 1977. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118. find
  19. A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing. 2008. Stacking dependency parsers. In EMNLP. find
  20. T. Matsuzaki, Y. Miyao, and J. Tsujii. 2005. Probabilistic CFG with latent annotations. In ACL, pages 75–82.
  21. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL.
  22. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In ACL.
  23. J. Nivre and R. McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In ACL.
  24. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. find
  25. The CoNLL 2007 shared task on dependency parsing. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL.
  26. J.-C. Régin. 1994. A filtering algorithm for constraints of difference in csps. In AAAI, pages 362–367. find
  27. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In EMNLP, pages 129–137. find
  28. J. Sherman and W. J. Morrison. 1950. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Stat., 21:124–127. find
  29. D. Sleator and D. Temperley. 1993. Parsing English with a link grammar. In IWPT, pages 277–291, August.
  30. D. A. Smith and N. A. Smith. 2007. Probabilistic models of nonprojective dependency trees. In EMNLP-CoNLL. find
  31. C. Sutton and A. McCallum. 2004. Collective segmentation and labeling of distant entities in information extraction. In ICML Workshop on Statistical Relational Learning. find
  32. C. Sutton and A. McCallum. 2007. Improved dynamic schedules for belief propagation. In UAI. find
  33. C. Sutton, K. Rohanimanesh, and A. McCallum. 2004. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. In ICML. find
  34. R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7:25–35. find
  35. R. W. Tromble and J. Eisner. 2006. A fast finite-state relaxation method for enforcing global constraints on sequence decoding. In HLT-NAACL, pages 423–430. find
  36. Y. Weiss and W. T. Freedman. 2001. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 47. find
  37. D. Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. CL, 23(3):377–404.
  38. J. S. Yedidia, W. T. Freeman, and Y. Weiss. 2004. Constructing free-energy approximations and generalized belief approximation algorithms. MERL TR2004-040, Mitsubishi Electric Research Laboratories. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/smith-2008-dependency-parsing-belief-propagation/