Timezone: »
A key feature of human intelligence is the ability to generalize beyond the training distribution, for instance, parsing longer sentences than seen in the past. Currently, deep neural networks struggle to generalize robustly to such shifts in the data distribution. We study robust generalization in the context of using recurrent neural networks (RNNs) to learn regular languages. We hypothesize that standard end-to-end modeling strategies cannot generalize well to systematic distribution shifts and propose a compositional strategy to address this. We compare an end-to-end strategy that maps strings to labels with a compositional strategy that predicts the structure of the deterministic finite state automaton (DFA) that accepts the regular language. We theoretically prove that the compositional strategy generalizes significantly better than the end-to-end strategy. In our experiments, we implement the compositional strategy via an auxiliary task where the goal is to predict the intermediate states visited by the DFA when parsing a string. Our empirical results support our hypothesis, showing that auxiliary tasks can enable robust generalization. Interestingly, the end-to-end RNN generalizes significantly better than the theoretical lower bound, suggesting that it is able to achieve atleast some degree of robust generalization.
Author Information
Soham Dan (University of Pennsylvania)
Osbert Bastani (University of Pennsylvania)
Dan Roth (University of Pennsylvania and AWS AI Labs)

Dan Roth is the Eduardo D. Glandt Distinguished Professor at the Department of Computer and Information Science, University of Pennsylvania, lead of NLP Science at AWS AI Labs., and a Fellow of the AAAS, the ACM, AAAI, and the ACL. In 2017 Roth was awarded the John McCarthy Award, the highest award the AI community gives to mid-career AI researchers. Roth was recognized “for major conceptual and theoretical advances in the modeling of natural language understanding, machine learning, and reasoning.” Roth has published broadly in machine learning, natural language processing, knowledge representation and reasoning, and learning theory, and has developed advanced machine learning based tools for natural language applications that are being used widely. Roth was the Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR) and a program chair of AAAI, ACL, and CoNLL. Roth has been involved in several startups; most recently he was a co-founder and chief scientist of NexLP, a startup that leverages the latest advances in Natural Language Processing (NLP), Cognitive Analytics, and Machine Learning in the legal and compliance domains. NexLP was acquired by Reveal in 2020. Prof. Roth received his B.A Summa cum laude in Mathematics from the Technion, Israel, and his Ph.D. in Computer Science from Harvard University in 1995.
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: Understanding Robust Generalization in Learning Regular Languages »
Wed. Jul 20th 06:20 -- 06:25 PM Room Room 310
More from the Same Authors
-
2021 : Robust Generalization of Quadratic Neural Networks via Function Identification »
Kan Xu · Hamsa Bastani · Osbert Bastani -
2021 : Mind the Gap: Safely Bridging Offline and Online Reinforcement Learning »
Wanqiao Xu · Kan Xu · Hamsa Bastani · Osbert Bastani -
2021 : Mind the Gap: Safely Bridging Offline and Online Reinforcement Learning »
Wanqiao Xu · Kan Xu · Hamsa Bastani · Osbert Bastani -
2021 : Improving Human Decision-Making with Machine Learning »
Hamsa Bastani · Osbert Bastani · Wichinpong Sinchaisri -
2021 : Improving Human Decision-Making with Machine Learning »
Hamsa Bastani · Osbert Bastani · Wichinpong Sinchaisri -
2023 : TRAC: Trustworthy Retrieval Augmented Chatbot »
Shuo Li · Sangdon Park · Insup Lee · Osbert Bastani -
2023 : TRAC: Trustworthy Retrieval Augmented Chatbot »
Shuo Li · Sangdon Park · Insup Lee · Osbert Bastani -
2023 Poster: On Regularization and Inference with Label Constraints »
Kaifu Wang · Hangfeng He · Tin Nguyen · Piyush Kumar · Dan Roth -
2023 Poster: PAC Prediction Sets for Large Language Models of Code »
Adam Khakhar · Stephen Mell · Osbert Bastani -
2023 Poster: LIV: Language-Image Representations and Rewards for Robotic Control »
Yecheng Jason Ma · Vikash Kumar · Amy Zhang · Osbert Bastani · Dinesh Jayaraman -
2023 Poster: Robust Subtask Learning for Compositional Generalization »
Kishor Jothimurugan · Steve Hsu · Osbert Bastani · Rajeev Alur -
2022 : Spotlight Presentations »
Adrian Weller · Osbert Bastani · Jake Snell · Tal Schuster · Stephen Bates · Zhendong Wang · Margaux Zaffran · Danielle Rasooly · Varun Babbar -
2022 Poster: Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval »
Uri Alon · Frank Xu · Junxian He · Sudipta Sengupta · Dan Roth · Graham Neubig -
2022 Poster: Versatile Offline Imitation from Observations and Examples via Regularized State-Occupancy Matching »
Yecheng Jason Ma · Andrew Shen · Dinesh Jayaraman · Osbert Bastani -
2022 Spotlight: Versatile Offline Imitation from Observations and Examples via Regularized State-Occupancy Matching »
Yecheng Jason Ma · Andrew Shen · Dinesh Jayaraman · Osbert Bastani -
2022 Spotlight: Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval »
Uri Alon · Frank Xu · Junxian He · Sudipta Sengupta · Dan Roth · Graham Neubig -
2022 Poster: ROCK: Causal Inference Principles for Reasoning about Commonsense Causality »
Jiayao Zhang · Hongming ZHANG · Weijie Su · Dan Roth -
2022 Poster: Sequential Covariate Shift Detection Using Classifier Two-Sample Tests »
Sooyong Jang · Sangdon Park · Insup Lee · Osbert Bastani -
2022 Spotlight: ROCK: Causal Inference Principles for Reasoning about Commonsense Causality »
Jiayao Zhang · Hongming ZHANG · Weijie Su · Dan Roth -
2022 Spotlight: Sequential Covariate Shift Detection Using Classifier Two-Sample Tests »
Sooyong Jang · Sangdon Park · Insup Lee · Osbert Bastani -
2021 Poster: Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddings »
Kan Xu · Xuanyi Zhao · Hamsa Bastani · Osbert Bastani -
2021 Spotlight: Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddings »
Kan Xu · Xuanyi Zhao · Hamsa Bastani · Osbert Bastani -
2020 Poster: Goodness-of-Fit Tests for Inhomogeneous Random Graphs »
Soham Dan · Bhaswar B. Bhattacharya -
2020 Poster: Robust and Stable Black Box Explanations »
Hima Lakkaraju · Nino Arsov · Osbert Bastani -
2020 Poster: Generating Programmatic Referring Expressions via Program Synthesis »
Jiani Huang · Calvin Smith · Osbert Bastani · Rishabh Singh · Aws Albarghouthi · Mayur Naik -
2019 Poster: Learning Neurosymbolic Generative Models via Program Synthesis »
Halley R Young · Osbert Bastani · Mayur Naik -
2019 Oral: Learning Neurosymbolic Generative Models via Program Synthesis »
Halley R Young · Osbert Bastani · Mayur Naik