Liang Huang Huang Liang

I received Ph.D. in 2008, and I am currently Assistant Professor at the City University of New York (CUNY). Please visit my new homepage instead.

Contents below are no longer updated.

Email: liang.huang.sh at gmail dot com

Places that I regularly visit during my PhD: USC/ISI, Rochester, CAS/ICT, and HKUST.

My advisor is Prof. Aravind Joshi.
My external co-advisor is Prof. Kevin Knight at USC/ISI.

Research Area: Computational Linguistics (and Theoretical Computer Science).
Also Interested in: AI Search, Psycholinguistics, and Historical Linguistics.

[CV].

“God has a Book where he maintains the best proofs of all mathematical theorems, proofs that are elegant and perfect... You don't have to believe in God, but you should believe in the Book.”

-- Paul Erdös (1913-1996)

What's New...

[June 2009] I just taught a tutorial at NAACL 2009 on Advanced Dynamic Programming, which is a revised version of my COLING 2008 tutorial (see below). Final slides will be posted here (in about a week). This survey paper contains the references.
[Jan 2009] I started my first job as a Research Scientist at Google. I continue to work with my students at CAS/ICT.
[Nov-Dec 2008] I am visiting Dekai Wu at HKUST.
[Sep 2008] I have just defended! My thesis is on Forest-based Algorithms in Natural Language Processing (slides here).
[Aug 2008] I just taught a tutorial on Advanced Dynamic Programming at COLING 2008, held in Manchester, UK. Here is the survey paper to accompany the tutorial. Final slides with animations are here (5M), and the 2ups version without animations are here (3M).
[June 2008] My paper on forest reranking won one of the two Outstanding Full Paper Awards at ACL 2008.

About Me...

I am from Shanghai China, speaking Wu as my native language. During high school years, I got fascinated in programming so I went to college with a major in computer science at Shanghai Jiao Tong University, focusing on algorithms and theory. Throughout the years I competed in various algorithmic programming contests, including the National Olympiads in Informatics (NOI) and the ACM International Collegiate Programming Contests (ACM/ICPC). Then I came to the US in Fall 2003 to pursue a PhD in computer science on the beautiful campus of the University of Pennsylvania (Penn). In addition, I spent two summers (2005 and 2006) at the Information Sciences Institute, University of Southern California (USC/ISI), under Kevin Knight and Daniel Marcu. I also work on applying computational linguistics to computational biology, in collaboration with Ken Dill's group at UCSF. My other long-term collaborators include David Chiang (ISI), Hao Zhang and Dan Gildea (Rochester). In 2007 I haphazardly spent three months visiting Prof. Qun Liu's lab at the Institute of Computing Technology, Chinese Academy of Sciences. It turned out to be very productive and I have been collaborating with them ever since; I thank the US Government for making it possible by delaying my visa for 6 months.

Teaching

Teaching is great fun for me!

Instructor and Course-Developer:

CSE 399-005, Python Programming, Spring 2006

Teaching Assistant:

CSE 262 Automata, Complexity and Computability, Fall 2004 (TA for Prof. Jean Gallier),
CSE 320 Algorithms, Spring 2005 (TA for Prof. Sanjeev Khanna)

Awarded 2005 Penn Prize for Excellence in Teaching by Graduate Students (University award for top 12 TAs).
My basic idea of teaching is intuition visualisation. Click here for my teaching statement.

I have also (co-)taught at the Chinese Academy of Sciences and the Hong Kong University of Science and Technology.

Research Interests

Computational Linguistics
- Efficient Parsing Algorithms and Applications
- Syntax-based Machine Translation
- Synchoronous Grammars and Tree Transducers
Theoretical Computer Science
- Generic Dynamic Programming, Hypergraph and Semiring Frameworks
- Algorithms for k-best Problems

If we knew what we were doing, it wouldn't be called research, would it?
-- Albert Einstein

Publications

An approximation of my NLP papers on Google Scholar.

PhD Dissertation Related
- Qualification Exam Report (WPE II): Dynamic Programming in Semiring and Hypergraph Frameworks.
  Committee: Sudipto Guha, Aravind Joshi, and Fernando Pereira (chair).
  Defended on Tuesday November 28th, 2006. More info.
- Dissertation Proposal
  Defended on Monday February 25th, 2008.
- Dissertation: Forest-based Algorithms in Natural Language Processing.
  [pdf] [slides] [bib]
  Defended on Thursday September 18th, 2008.
  Advisors: Aravind Joshi and Kevin Knight (external, USC/ISI).
  Committeee: Mark Johnson (external, Brown), Mitch Marcus, Fernando Pereira, and Ben Taskar (chair).
Computational Linguistics
- Liang Huang and Kenji Sagae (2010). Dynamic Programming for Linear-time Incremental Parsing.
  To appear in Proceedings of ACL 2010. Nominated for the Best Paper Award.
  [pdf]
- Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight (2009). Binarization of Synchronous Context-Free Grammars.
  Computational Linguistics, 35(4).
  [pdf]
  Journal version of the NAACL 2006 conference paper below, with many new results, especially the first real-data examples of non-binarizable syntactic reorderings between English/Chinese, English/French, and English/German, and a new section on efficient handling of those non-binarizable rules.
- Liang Huang, Wenbin Jiang, and Qun Liu (2009).
  Bilingually-Constrained (Monolingual) Shift-Reduce Parsing.
  In Proceedings of EMNLP 2009.
  [pdf] [slides] [bib]
- Wenbin Jiang, Liang Huang, and Qun Liu (2009).
  Automatic Adaptation of Annotation Standards: Chinese Word Segmentation and POS Tagging -- A Case Study.
  In Proceedings of ACL-IJCNLP 2009.
  [pdf] [slides] [bib]
- Haitao Mi and Liang Huang (2008). Forest-based Translation Rule Extraction.
  In Proceedings of EMNLP 2008, Honolulu, Hawaii. Nominated for the Best Paper Award.
  [pdf] [slides] [bib]
- Liang Huang (2008). Forest Reranking: Discriminative Parsing with Non-Local Features.
  In Proceedings of ACL 2008, Columbus, OH. Best Paper Award.
  [pdf] [slides] [bib]
  Software: the modified Charniak parser that outputs packed forests (to be released).
- Haitao Mi, Liang Huang, and Qun Liu (2008). Forest-based Translation.
  In Proceedings of ACL 2008, Columbus, OH.
  [pdf] [slides] [bib]
- Wenbin Jiang, Liang Huang and Qun Liu and Yajuan Lü (2008). A Cascaded Linear Model for Joint Chinese Word Segmentation and Part-of-Speech Tagging.
  In Proceedings of ACL 2008, Columbus, OH.
  [pdf] [slides] [bib]
- Liang Huang and David Chiang (2007). Forest Rescoring: Faster Decoding with Integrated Language Models.
  In Proceedings of ACL 2007, Prague, Czech Rep. Nominated for the Best Paper Award.
  [paper] [slides] [bib]
  Software: Cubit
- Liang Huang (2007). Binarization, Synchronous Binarization, and Target-side Binarization.
  In Proceedings of the HLT-NAACL Workshop on Syntax and Structure in Statistical Translation (SSST), Rochester, NY.
  [paper] [slides] [bib]
- Liang Huang, Kevin Knight, and Aravind Joshi (2006). Statistical Syntax-Directed Translation with Extended Domain of Locality.
  In Proceedings of the 7th Biennial Conference of the Association for Machine Translation in the Americas (AMTA), Boston, MA.
  [paper] [slides] [bib]
  Preliminary version appeared in the Proceedings of HLT-NAACL 2006 Workshop on Computationally Hard Problems.
- Hao Zhang, Liang Huang, Daniel Gildea, and Kevin Knight (2006). Synchronous Binarization for Machine Translation.
  In Proceedings of the HLT-NAACL 2006, Brooklyn, NY.
  [paper] [slides] [bib]
- Liang Huang and David Chiang (2005). Better k-best Parsing.
  In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT 2005), Vancouver, BC.
  [paper (corrected)] [slides] [bib]. cited >50 times in Google Scholar.
  Note: This version corrects the behavior of the published version in some boundary conditions regarding Algorithm 3. Thanks to David A. Smith and Jonathan May for pointing it out. The actual implementations, however, use an earlier version which has the correct behavior (but less efficient). The published version is archived here.
- Liang Huang, Hao Zhang and Dan Gildea (2005). Machine Translation as Lexicalized Parsing with Hooks.
  In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT 2005), Vancouver, BC.
  [paper] [slides] [bib]
Computational Biology
- Adam Lucas, Liang Huang, Aravind Joshi, and Ken Dill (2007). Statistical Mechanics of Helix Bundles using a Dynamic Programming Approach.
  In J. Am. Chem. Soc., 129 (14), pp. 4272-4281. JACS online version.
- 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.
  In Polymer 48 (15), pp. 4289-4300, Elsevier.
Programming Languages
- Stephanie Weirich and Liang Huang (2004). A Design for Type-Directed Programming in Java.
  In Proceedings of the Workshop on Object-Oriented Developments, ENTCS.
  [ps] [pdf]
  The extended version is University of Pennsylvania Computer & Information Science Technical Report MS-CIS-04-11. [ps] [pdf].
Algorithms
- Rujia Liu and Liang Huang. The Art of Algorithms and Programming Contests (Book in Chinese). Tsinghua University Press, 2003.
  Contents (in English) Errata (in Chinese)

Trivia

Some facts about me...

My favorite programming language is Python. I also love OCaml. Needless to say, I hate C/C++.
Like many other computer scientists, I am a Mac lover. For desktop OS, I use Debian and Ubuntu. I have been lucky enough not to have a Windows machine for the past 5 years.
I am a big fan of PhD Comics!
I am a fan of Zinedine Zidane for his unraveled elegance, and thus Real Madrid.
Playing Go often prevents me from doing research...
I am color-blind. Here are some resources I collected on color-blindness. I am very interested in the mathematical theory characterizing the color space of color-blind people. Recently some experiments convinced me (and my non-color-blind friends) that my color space is two-dimensional rather than 3D, basically collapsing the red-green plane into a diagonal line (which means the transformation is irrevertible). The projected colors are usually "brownish-yellow" in the eyes of non-color-blind people. My blue vision is not affected though, and that's why it is always my favorite color. However, I don't like what they call "bleu".
I proudly speak Wu Chinese as my mother tongue, though Mandarin is also native to me.
In terms of the number of speakers, Wu (Sino-Tibetan : Sinitic : Southern) is the second largest language in China and the 10th largest in the world. It is a soft and light language spoken mainly in the Jiang-Nan region, i.e., Shanghai, Zhejiang and southern part of Jiangsu. It is very different from Mandarin in many aspects (details here).
Here are some further resources on Chinese Linguistic Groups and the Sinitic Group. I will be involved in the Romanization of Wu and/or Shanghainese.
I deeply love Bach's music. I currently run a web radio "simply baroque" in honor of Ton Koopman and Yo-Yo Ma.
I am big fan of Classical Chinese Poetry. If you don't speak Chinese, check out this site or this site.