Search
Current issue
Categories
- acquisition lab
- alums
- awards
- candy
- colloquia
- computation
- department news
- dissertation defenses
- events
- faculty news
- glsa
- grad-student news
- grants
- graphs
- issues
- 04:04 (2006-02-16)
- 04:05 (2006-02-23)
- 04:06 (2006-03-02)
- 04:07 (2006-03-09)
- 04:08 (2006-03-16)
- 04:09 (2006-03-30)
- 04:10 (2006-04-06)
- 04:11 (2006-04-13)
- 04:12 (2006-04-20)
- 04:13 (2006-04-27)
- 04:14 (2006-05-04)
- 04:15 (2006-05-11)
- 04:16 (2006-05-18)
- 04:17 (2006-06-29)
- 04:18 (2006-07-27)
- 04:19 (2006-08-31)
- 04:20 (2006-09-07)
- 04:21 (2006-09-14)
- 04:22 (2006-09-21)
- 04:23 (2006-09-28)
- 04:24 (2006-10-05)
- 04:25 (2006-10-12)
- 04:26 (2006-10-19)
- 04:27 (2006-10-26)
- 04:28 (2006-11-02)
- 04:29 (2006-11-09)
- 04:30 (2006-11-16)
- 04:31 (2006-11-23)
- 04:32 (2006-11-30)
- 04:33 (2006-12-07)
- 04:34 (2006-12-14)
- 04:35 (2006-12-21)
- 05:01 (2007-02-01)
- 05:02 (2007-02-08)
- 05:03 (2007-02-15)
- 05:04 (2007-02-22)
- 05:05 (2007-03-01)
- 05:06 (2007-03-08)
- 05:07 (2007-03-15)
- 05:08 (2007-03-29)
- 05:09 (2007-04-05)
- 05:10 (2007-04-12)
- 05:11 (2007-04-19)
- 05:12 (2007-04-26)
- 05:13 (2007-05-03)
- 05:14 (2007-05-10)
- 05:15 (2007-05-17)
- 05:16 (2007-05-24)
- 05:17 (2007-05-31)
- 05:18 (2007-06-28)
- 05:19 (2007-07-26)
- 05:20 (2007-08-30)
- 05:21 (2007-09-06)
- 05:22 (2007-09-13)
- 05:23 (2007-09-20)
- 05:24 (2007-09-27)
- 05:25 (2007-10-04)
- 05:26 (2007-10-11)
- 05:27 (2007-10-18)
- 05:28 (2007-10-25)
- 05:29 (2007-11-01)
- 05:30 (2007-11-08)
- 05:31 (2007-11-15)
- 05:32 (2007-11-22)
- 05:33 (2007-11-29)
- 05:34 (2007-12-06)
- 05:35 (2007-12-13)
- 06:01 (2008-01-24)
- 06:02 (2008-01-31)
- 06:03 (2008-02-07)
- 06:04 (2008-02-14)
- 06:05 (2008-02-21)
- 06:06 (2008-02-28)
- 06:07 (2008-03-06)
- 06:08 (2008-03-13)
- 06:09 (2008-03-20)
- 06:10 (2008-03-27)
- 06:11 (2008-04-03)
- 06:12 (2008-04-10)
- 06:13 (2008-04-17)
- 06:14 (2008-04-24)
- 06:15 (2008-05-01)
- 06:16 (2008-05-08)
- 06:17 (2008-05-15)
- 06:18 (2008-06-26)
- 06:19 (2008-07-31)
- 06:20 (2008-08-28)
- 06:21 (2008-09-04)
- 06:22 (2008-09-11)
- 06:23 (2008-09-18)
- 06:24 (2008-09-25)
- 06:25 (2008-10-02)
- 06:26 (2008-10-09)
- 06:27 (2008-10-16)
- 06:28 (2008-10-23)
- 06:29 (2008-10-30)
- 06:30 (2008-11-06)
- 06:31 (2008-11-13)
- 06:32 (2008-11-20)
- 06:33 (2008-12-04)
- 06:34 (2008-12-11)
- 06:35 (2008-12-18)
- 07:01 (2009-01-22)
- 07:02 (2009-01-29)
- 07:03 (2009-02-05)
- 07:04 (2009-02-12)
- 07:05 (2009-02-19)
- 07:06 (2009-02-26)
- 07:07 (2009-03-05)
- 07:08 (2009-03-12)
- 07:09 (2009-03-26)
- 07:10 (2009-04-02)
- 07:11 (2009-04-09)
- 07:12 (2009-04-16)
- 07:13 (2009-04-23)
- 07:14 (2009-04-30)
- 07:15 (2009-05-07)
- 07:16 (2009-05-14)
- 07:17 (2009-05-21)
- 07:18 (2009-09-09)
- 07:19 (2009-09-16)
- 07:20 (2009-09-23)
- 07:21 (2009-10-01)
- 07:22 (2009-10-07)
- 07:23 (2009-10-14)
- 07:24 (2009-10-22)
- 07:24 (2009-10-28)
- 07:25 (2009-10-29)
- 07:26 (2009-11-11)
- 07:27 (2009-11-18)
- jobs
- miscellany
- phonetics lab
- phonology group
- photo albums
- prosody group
- publications/presentations
- semantics reading group
- syntax reading group
- undergrad news
- visiting scholars
- whisc
Other Ling Newsletters
« Anna Verbuk to the University of Illinois at Urbana-Champaign | Main | WHISC Season Wraps Up Next Week»
David Smith Colloquium
David Smith
UMass Amherst Computer Science
Linguistic Inference by Loopy Belief Propagation
Friday, May 15, 3:30 pm, in South College 301
Abstract
Much recent work in natural language processing treats linguistic analysis as an inference problem over graphs. This development opens up useful connections between graph theory, machine learning, and linguistics. We formulate dependency parsing as a graphical model with the novel ingredient of global constraints. We show how to apply loopy belief propagation (BP), a simple and effective tool for approximate learning and inference, to the problem of syntactic analysis. As a parsing algorithm, BP is both asymptotically and empirically efficient. Even with second-order features or latent variables, which would make exact parsing considerably slower or NP-hard, BP needs only O(n^3) time with a small constant factor. Furthermore, such features significantly improve parse accuracy over exact first-order methods. Incorporating additional features increases the runtime additively rather than multiplicatively. Global constraints are propagated by combinatorial optimization algorithms, which greatly improve on collections of local constraints. Finally, I will discuss two extensions to the basic BP parser: a joint model of morphology, syntax, and simple semantic roles and a joint model of sentences and their translations.