The Unreasonable Syntactic Expressivity of RNNs

The Unreasonable Syntactic Expressivity of RNNs

When:

Thursday, November 12, 2020, 11:00am - 12:00pm PSTiCal

Where:

VTC Only
This event is open to the public.

Type:

NL Seminar

Speaker:

John Hewitt (Stanford Univ)

Video:

https://youtu.be/ZtuRyNKCu60

Description:

Abstract: In 2015, Andrej Karpathy posted a now famous blog post on The Unreasonable Effectiveness of Recurrent Neural Networks. To summarize this sense of wonder, Karpathy emphasized: 'We’ll train RNNs to generate text character by character and ponder the question “how is that even possible?”' RNNs empirically generate natural language with high syntactic fidelity, but their success is not well-understood theoretically. In this talk, I'll provide theoretical insight into this success, proving in a finite-precision setting that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. I'll introduce Dyck-(k,m), the language of well-nested brackets (of k types) and m-bounded nesting depth, reflecting the bounded memory needs and long-distance dependencies of natural language syntax. The best previously known results use O(k^(m/2)) memory (hidden units) to generate these languages. I'll prove that an RNN with O(m log k) hidden units suffices, an exponential reduction in memory, by an explicit construction. Finally, I'll show that no algorithm, even with unbounded computation, can suffice with o(m log k) hidden units.

Bio: John is a 3rd year PhD student in computer science at Stanford University, advised by Chris Manning and Percy Liang. He works on understanding and improving how unsupervised neural networks learn and process human languages. He is supported by a National Science Foundation Graduate Research Fellowship, and is the recipient of an EMNLP Runner Up Best Paper award. 

NOTE:

The speaker provided consent to be recorded, therefore, the playback link will be posted to USC/ISI's Youtube channel within 24-48 hours after the event concludes. 

 https://www.youtube.com/user/USCISI/