Lunch at 12:30pm, talk at 1pm, in 148 Fitzpatrick

Title: Semirings and How to Solve Equations in Them

Abstract: Many algorithms from (slightly old-fashioned) natural language processing can be unified by defining them in terms of generic semirings (which have addition and multiplication but not subtraction or division). A case that commonly arises — but is commonly avoided because of the hassle — is finding the total weight of all paths of a finite automaton that has a cycle, or all trees of a context-free grammar that has a cycle, because this requires solving a system of linear or quadratic equations. I will present some algorithms by Lehmann (1977) and Esparza et al (2007) that solve these problems, and briefly show that (1) not only does this make the algorithms more generic, but it conveniently makes them handle infinities correctly; (2) how to adapt these algorithms to the setting of factor graph grammars, which have a block-sparse structure; and (3) close with an open problem of dealing with infinite gradients.

Bio: Dr. Chiang’s research is in natural language processing, the subfield of computer science that aims to enable computers to understand and produce human language. He focuses mainly on language translation, and am interested in syntactic parsing and other areas as well.