Liang Huang

Research Assistant Professor, Department of Computer Science
Computer Scientist, Natural Language Group, Information Sciences Institute (ISI)
Affiliated Faculty, Language Processing Lab, Department of Linguistics

University of Southern California (USC), Viterbi School of Engineering

4676 Admiralty Way, Suite 1001 [directions to my office]
Marina del Rey, CA 90292
(310) 448-9184 (phone)
(310) 822-0751 (fax)

Ph.D., University of Pennsylvania, 2008. (old homepage)
[thesis] [slides] (Advisors: A. Joshi and K. Knight. Committee: M. Johnson (external), M. Marcus, F. Pereira, and B. Taskar.)
B.S., Shanghai Jiao Tong University, 2003.

Research Scientist, Google Inc. (Mountain View), 2009.
Summer Intern, USC/ISI, 2005 and 2006.

[informal bio] [CV]

“Computer Science is no more about computers than astronomy is about telescopes.”

--- E. W. Dijkstra (1930-2002)

“When we study human language, we are approaching what some might call the 'human essence,' the distinctive qualities of mind that are, so far as we know, unique to man.”

--- Noam Chomsky (b. 1928)

Teaching

Current Teaching at USC:

Spring 2012: CS 570, Analysis of Algorithms.
Spring 2012: CS 561, Artificial Intelligence (in Prolog), with Kenji Sagae.
Fall 2011: CS 562, Statistical Natural Language Processing, with David Chiang.
Spring 2011: CS 599, Machine Translation (new course), with David Chiang and Kevin Knight.
Fall 2010: CS 562, Statistical Natural Language Processing, with Kevin Knight.
Spring 2010: CS 544, Natural Language Processing (with Hovy, Hobbs , and Kozareva).
Fall 2009: CS 562, Statistical Natural Language Processing, with David Chiang.

Past Teaching at Penn:

CSE 399: Python Programming (new course, Spring 2006)
Recitation Instructor, CSE 320, Algorithms (Spring 2005, Prof. Sanjeev Khannna)
Recitation Instructor, CSE 262, Automata and Formal Language Theory (Fall 2004, Prof. Jean Gallier).
Awarded University Graduate Teaching Prize, 2005.

Research

My research interests are mainly in the algorithmic and formal aspects of computational linguistics (esp. parsing and machine translation) and artificial intelligence in general. The key questions that motivate my research are: Why are computers so bad at understanding and processing natural language? Can we teach computers to process human language the way we humans do, that is, both fast (linear-time) and accurate? Or, can computers process human language the way they process programming languages, that is, fast and linear-time inspite of the inherent ambiguity of the former? So recently I have been focusing on linear-time algorithms for parsing and translation inspired by both human processing (psycholinguistics) and compiler theory.

On the other hand I also work on theoretical and practical problems in structured learning with inexact search that rises from NLP but also applies to other structured domains such as computational biology. I had also worked on structural biology (esp. protein folding) using dynamic programming inspired by computational linguistics (see below).

Lastly, I remain interested in theory and algorithms and some of my NLP papers draw unexpected connections from theoretical computer science, e.g., the linear-time synchronous binarization algorithm was inspired by Graham Scan for Convex Hull, and the k-best parsing algorithms are often used in the exams when I teach Algorithms.

Listing of my papers on Google Scholar and a subset in ACL Anthology Network.

Recent Talks:

Dynamic Programming for Incremental Parsing (2010-2011). Talk given at UCSD, Google, JHU, MIT, IBM, etc.
slides and video from the talk at JHU CLSP Seminar (Sep 2010).
Tree-based and Forest-based Translation (2009-2010). Talk given at BBN, CUHK, Berkeley, Pomona, etc.
slides from talk at Berkeley (Feb 2009).

Earlier Talks:

Forest-based Algorithms in NLP (thesis work, 2008). Talk given at MIT, Google, Stanford, CMU, etc.
- version 1 (includes cube pruning, but no forest-based translation):
  video from the CLSP seminar talk at JHU (on vimeo) (April 2008).
  video from the Google techtalk (on youtube) (March 2008). slides.
- version 2 (includes forest-based translation but no cube pruning; ≈thesis defense):
  slides from the LTI seminar talk at CMU (May 2009).
Tutorial: Advanced Dynamic Programming in Semiring and Hypergraph Frameworks.
NAACL 2009 and COLING 2008. [slides] [paper]
(based on my candidacy exam and Chapter 2 of my thesis)
Fast Decoding with Synchronous Grammars and n-gram Models ("forest rescoring" paper).
video and slides from the Microsoft Research talk (Dec 2006).

In Press:

Liang Huang, Suphan Fayong, and Yang Guo (2012). Structured Perceptron with Inexact Search.
To Appear in the Proceedings of NAACL 2012.
Ashish Vaswani, Liang Huang and David Chiang (2012). Smaller Alignment Models for Better Translations: Unsupervised Word Alignment with the L0-norm.
To Appear in the Proceedings of ACL 2012.

Recent and Representative Publications:

Liang Huang and Kenji Sagae (2010). Dynamic Programming for Linear-time Incremental Parsing.
In Proceedings of ACL 2010. Nominated for the Best Paper Award. [slides] [software] [bib]
- Liang Huang and Haitao Mi (2010). Efficient Incremental Decoding for Tree-to-String Translation.
  In Proceedings of EMNLP 2010. [slides] [bib]
  - Ashish Vaswani, Haitao Mi, Liang Huang and David Chiang (2011). Rule Markov Models for Fast Tree-to-String Translation.
    In Proceedings of ACL 2011. [slides by ashish] [bib]
Liang Huang and David Chiang (2005). Better k-best Parsing.
In Proceedings of IWPT 2005.
- Liang Huang and David Chiang (2007). Forest Rescoring: Faster Decoding with Integrated Language Models.
  In Proceedings of ACL 2007. Nominated for the Best Paper Award.
  - Liang Huang (2008). Forest Reranking: Discriminative Parsing with Non-Local Features.
    In Proceedings of ACL 2008. Best Paper Award.
Liang Huang, Kevin Knight, and Aravind Joshi (2006). Statistical Syntax-Directed Translation with Extended Domain of Locality.
In Proceedings of AMTA 2006.
- Haitao Mi, Liang Huang, and Qun Liu (2008). Forest-based Translation.
  In Proceedings of ACL 2008. [slides]
  - Haitao Mi and Liang Huang (2008). Forest-based Translation Rule Extraction.
    In Proceedings of EMNLP 2008. Nominated for the Best Paper Award. [slides]
Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight (2009). Binarization of Synchronous Context-Free Grammars.
Computational Linguistics, 35 (4). Conference version appeared at NAACL 2006.
(The core linear-time synchronous binarization algorithm was inspired by Graham Scan for Convex Hull as I used to work on Computational Geometry as an undergrad. It was a rather unexpected connection though.)
Adam Lucas, Liang Huang, Aravind Joshi, and Ken Dill (2007). Statistical Mechanics of Helix Bundles using a Dynamic Programming Approach. J. Am. Chem. Soc. (JACS), 129 (14), pp. 4272-4281. [PDF]
- Ken Dill, Adam Lucas, Julia Hockenmaier, Liang Huang, David Chiang, and Aravind Joshi (2007). Computational Linguistics: a new tool for exploring biopolymer structures and statistical mechanics. Polymer, 48 (15), pp. 4289-4300.

Full list of publications.

Students and Visitors

I have been extremely fortunate to work with...

PhD students: Ashish Vaswani (co-advised by David Chiang).
Visiting Scientists: Dr. Haitao Mi (2010-2011, from CAS/ICT).
Master's Students: William Chang (2009), Yang Guo (2010-2011), Jun Ma (2011), Yixuan Wu (2011), Suphan Fayong (2011-2012), Phani Vempaty (2011-2012), Theerawat Songyot (2012).
Undergraduate Students: Elizabeth Deng (2011).
Summer Interns: Alexander "Sasha" Rush (2010, from MIT), Yoav Goldberg (2010, from Ben Gurion, joint with Knight/Chiang), Licheng Fang (2011, from Rochester).

Misc

I am from Shanghai, China, and thus speak Wu natively. Mandarin is my second, but also native, language.
I am color-blind.
I love Baroque Music, esp. JS Bach. Outside of Baroque I love Tchaikovsky most.
I code in Python mainly (see my quick and easy two-hour tutorial), and try to avoid C/C++. I also like OCaml and Prolog, but hate Perl.
I enjoy hiking, ping-pong and badminton. I hate the traffic in LA, and try to bike to work.
I am interested in History of Science, esp. History of Mathematics.
I am involved with two Olympiads:
- I help organize the Linguistics Olympiad (NACLO) for high school students in Southern California. Take a look at previous years' problem sets -- they are real fun (well, assume you love languages)!
- I myself was a veteran of a different Olympiad -- the Informatics Olympiad (on algorithmic programming), and the ACM/ICPC programming contests. I subsequently co-authored a popular book on those programming contests for Chinese students. Currently I am co-coaching USC programming contests.
I enjoy helping students on writing and presentation. Here are my slides for ``how to write a good paper'' based on Simon-Peyton Jones's slides.

For more info please visit my homepage at Penn.

“It is not worth an intelligent man's time to be in the majority. By definition, there are already enough people to do that.”

--- G. H. Hardy (1877-1947)