[Colloquium] TTIC Colloquium: David Chiang, University of Notre Dame

[Dawn Ellis]

When:     Monday, Sept. 29th at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       David Chiang, University of Notre Dame

Title:       Graph Grammars and Automata for NLP

Abstract:

All natural language processing systems implicitly or explicitly depend on
some representation of linguistic objects and some framework for defining
(probabilistic) transformations of those representations. Two such
representations that have been extraordinarily successful are sequences
(and finite-state machines over sequences) and trees (and finite-state
machines over trees). For representing linguistic meaning, however, there
is currently much interest in going beyond sequences or trees to graphs
(for example, abstract meaning representations), and in this talk I will
present some recent and current work on graphs, graph automata, and graph
grammars.

Hyperedge replacement grammar (HRG) is a formalism for generating graphs
whose kinship with context-free grammars immediately leads to some
important results: a probabilistic version, a synchronous version, and
efficient algorithms for searching or summing packed "forests." However,
until recently there was no practical algorithm for finding, given an input
graph, an HRG derivation of the graph. An algorithm due to Lautemann was
known to be polynomial-time for graphs that are connected and of bounded
degree. I will describe an optimization of this algorithm and some
important implementation details, resulting in an algorithm that is
practical for natural-language applications. This is joint work with Kevin
Knight and the ISI summer interns of 2013.

DAG acceptors are another formalism, much simpler than HRG, which were
recently extended by Quernheim and Knight, but still lacked efficient
algorithms for searching or summing over the derivations of an input graph,
and lacked a well-defined probability model. I will present solutions to
both of these problems, and discuss the problems that still remain. This is
joint work with Dan Gildea, Adam Lopez, Giorgio Satta, and other
participants in the JHU summer workshop in 2014.

David Chiang (PhD, University of Pennsylvania, 2004) is an associate
professor in the Department of Computer Science and Engineering at the
University of Notre Dame. His research is on computational models for
learning human languages, particularly how to translate from one language
to another. His work on applying formal grammars and machine learning to
translation has been recognized with two best paper awards (at ACL 2005 and
NAACL HLT 2009) and has transformed the field of machine translation. He
has received research grants from DARPA, NSF, and Google, has served on the
executive board of NAACL and the editorial board of Computational
Linguistics and JAIR, and is currently on the editorial board of
Transactions of the ACL.


Host:  Kevin Gimpel, kgimpel at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140922/42555606/attachment.htm