SUPERVISED TRAINING ON SYNTHETIC LANGUAGES: A NOVEL FRAMEWORK FOR UNSUPERVISED PARSING by Dingquan Wang A dissertation submitted to The Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy Baltimore, Maryland October, 2019 © Dingquan Wang 2019 All rights reserved Abstract This thesis focuses on unsupervised dependency parsing—parsing sentences of a language into dependency trees without accessing the training data of that language. Different from most prior work that uses unsupervised learning to estimate the parsing parameters, we estimate the parameters by supervised training on synthetic lan- guages. Our parsing framework has three major components: Synthetic language generation gives a rich set of training languages by mix-and-match over the real languages; surface-form feature extraction maps an unparsed corpus of a language into a fixed-length vector as the syntactic signature of that language; and, finally, language-agnostic parsing incorporates the syntactic signature during parsing so that the decision on each word token is reliant upon the general syntax of the target language. The fundamental question we are trying to answer is whether some useful informa- tion about the syntax of a language could be inferred from its surface-form evidence (unparsed corpus).
This is the same question that has been implicitly asked by previ- ous papers on unsupervised parsing, which only assumes an unparsed corpus to be available for the target language. We show that, indeed, useful features of the target language can be extracted automatically from an unparsed corpus, which consists only of gold part-of-speech (POS) sequences. Providing these features to our neural parser ii enables it to parse sequences like those in the corpus. Strikingly, our system has no supervision in the target language.
Rather, it is a multilingual system that is trained end-to-end on a variety of other languages, so it learns a feature extractor that works well. This thesis contains several large-scale experiments requiring hundreds of thou- sands of CPU-hours. To our knowledge, this is the largest study of unsupervised parsing yet attempted. We show experimentally across multiple languages: (1) Fea- tures computed from the unparsed corpus improve parsing accuracy.
(2) Including thousands of synthetic languages in the training yields further improvement. (3) Despite being computed from unparsed corpora, our learned task-specific features beat previous works’ interpretable typological features that require parsed corpora or expert categorization of the language. iii Thesis Committee Primary Readers Jason Eisner (Primary Advisor) Professor Department of Computer Science Johns Hopkins University Tal Linzen Assistant Professor Department of Cognitive Science and Computer Science Johns Hopkins University Joakim Nivre Professor of Computational Linguistics Department of Linguistics and Philology Uppsala University Slav Petrov Principal Scientist / Research Director Google AI Matt Post Research Scientist Human Language Technology Center of Excellence Department of Computer Science Johns Hopkins University iv For Y. Acknowledgments Portions of this thesis include four peer-reviewed papers (Wang and Eisner, 2016; Wang and Eisner, 2017; Wang and Eisner, 2018a; Wang and Eisner, 2018b).
I would like to thank my adviser Jason Eisner, who contributed substantial edits on all of these papers as well as the rest chapters in this thesis (expecially Chapter 2). Jason is the most incredible advisor I have ever worked with. He is known for his long technical emails to collaborators. But when I first got one of his legendary emails, I was still blown away by its depth and vision.1 When I was writing a paper in 2018, I still went back to his emails from 2014 for reference.
Jason’s extraordinarily high standards on papers make him the worst enemy before submission deadlines, and the best ally after submission deadlines, when it is time to improve the written and talk presentations further. His attitude towards research goes beyond the research itself, rather, he views our research as a means to serve the community, and I would like to emulated him in the future. In addition to Jason, I’m grateful to the people who have served as committee members who went beyond the call of duty to support me on my journey toward this degree. Thanks to my Graduate Board Oral (GBO) exam committee, consisting of Kevin Duh, Sanjeev Khudanpur, Benjamin Van Durme, Gèraldine Legendre (alternate), 1 Also the length—I printed out my first one, which took 15 A4 pages.
vi Colin Wilson, and David Yarowsky (alternate), for their insightful comments on the proposal. Thanks to my dissertation committee, consisting of Tal Linzen, Joakim Nivre, Slav Petrov, and Matt Post, for their patience in reading through this document and suggesting improvements to hold this work to a higher standard. Most of this work is funded by the U. National Science Foundation under Grant No.
The state of Maryland provides indispensable computing resources via the Maryland Advanced Research Computing Center (MARCC), which makes the massive experiments possible. Early discussions and code prototypes of Wang and Eisner (2016) are provided by Raman Arora, Matt Gormley and Sharon Li. Lillian Lee, who serves as the co-editor-in-chief of the TACL, gave careful corrections on Wang and Eisner (2016), Wang and Eisner (2017), and Wang and Eisner (2018a). Denise Link-Farajali and Anne Colgan from the Center for Leadership Education gave thorough and detailed writing suggestions, where Denise helped on the abstract, Chapters 1 and 2; and Anne helped on the acknowledgments and Chapter 7.
Outside the JHU, this work benefited from productive discussions with Regina Barzilay, Emily Bender, Michael Collins, Adam Fisch, Jiang Guo, Mitch Marcus, Graham Neubig, Mohammad Sadegh Rasooli, Lyle Ungar, Wenpeng Yin, and Mo Yu. Of course, as an Argonaut,2 I’m fortunate to have worked closely with other Argonauts, including Nicholas Andrews, Jacob Buckman, Ryan Cotterell, Nathaniel (Wes) Filardo, Matthew Francis-Landau, Juneki Hong, Xiang (Lisa) Li, Xiaochen Li, Chu-Cheng Lin, Chenxi Liu, Becky Marvin, Hongyuan Mei, Sebastian Mielke, Guanghui Qin, Pushpendre Rastogi, Nanyun (Violet) Peng, Adi Renduchintala, Darcey Riley, Tim Vieira, Shijie Wu, Akshay Srivatsan, Adam Teichert, and Mozhi (Miles) 2 https://www.edu/~jason/Argo/ vii Zhang, who are incredibly smart problem solvers and generous helpers. I want to thank to them for brainstorming ideas, and giving feedback on paper drafts and practice talks. Beyond Argo, I’m a proud member of the CLSP and CS community at JHU and grateful to my colleagues there for fostering a relaxed, creative and collaborative atmosphere.
They are: Tongfei Chen, Shuoyang Ding, Seth Ebner, Dongji Gao, Lv Hang, Huda Khayrallah, Rebecca Knowles, Keith Levin, Ke Li, Chunxi Liu, Xutai Ma, Arya McCarthy, Poorya Mianjy, Adam Poliak, Pamela Shapiro, Suzanna Sia, Shuo Sun, Yiming Wang, Zachary Wood-Doughty, Winston Wu, Patrick Xia, Hainan Xu, Sheng Zhang, and Xiaohui Zhang. Thanks to Zachary Burwell, Ruth Scally, and Cathy Thornton for managing the administrative stuff so smoothly that it freed me from the distractions outside the research. I thank my mom and dad for their endless and unconditional support so that I could pursue the degree this far. I owe you so much especially for not being able to come back and spend Chinese New Years with you since 2013.
Finally, thanks to Yuehan, who is the motivator, the encourager, the morale booster, the problem solver, the complaint listeneer, the happiness sharer, the best friend, the love of my life, and the true author of this work. viii Table of Contents Abstract ii Thesis Committee iv Acknowledgments vi Table of Contents ix List of Tables xvi List of Figures xviii 1 Introduction 1 1.1 Parse Trees in the Era of Neural Networks .1 Making neural models linguistically informed .2 Understanding neural models .3 Guiding model transfer across domains .1 Reason for using dependency structure .3 Unsupervised Dependency Parsing .4 Our Approach: An Artificial Linguist .1 The importance of the synthetic training languages .1 Bayesian Estimation and Inference .1 Maximum a posteriori estimation .3 Posterior mean estimator .2 Amortized Bayes Estimator (our proposal) .3 An Analogy: Statistical Estimation as Function Inversion .4 From Grammar Induction to Other Tasks .1 Grammar induction as Bayesian estimation .2 Limitations of grammar induction .3 Unsupervised parsing as (amortized) Bayesian inference .4 Typology prediction as (amortized) Bayesian inference .5 Eliminating explicit grammars altogether. 35 3 Resolving the Challenge of Data Sparsity—the Galactic Dependencies 37 3.3 Synthetic Language Generation .4 Modeling Dependent Order .2 Training parameters on a real language .3 Setting parameters of a synthetic language .6 Exploratory Data Analysis .1 Single-source selection .4 Experiment with Noisy Tags .8 Conclusions and Future Work. 66 4 Fine-Grained Prediction of Syntactic Typology 70 4.4 Simple “Expected Count” Baseline .5 Proposed Model Architecture .1 Directionality predictions from scores .2 Design of the scoring function ψ( x) .3 Design of the featurization function π ( x) .2 Comparison of architectures .3 Contribution of different feature classes .4 Robustness to noisy input .6 Comparison with grammar induction .7 Fine-grained analysis .8 Binary classification accuracy .9 Final evaluation on test data .8 Conclusions and Future Work.
102 5 Unsupervised Dependency Parsing 104 5.1 Per-language learning .2 Multi-language learning .3 Exploiting parallel data .4 Situating our work .3 The Typology Component .1 Design of the surface features π (u) .4 The Parsing Architecture .5 Training the System .2 Comparison among architectures .3 Comparison to SST .4 Oracle typology vs.5 Selected hyperparameter settings .6 Performance on noisy tag sequences .7 Analysis by dependency relation type .8 Final evaluation on test data .7 Conclusion and Future Work. 129 6 Synthetic Data Made to Order 132 xiii 6.1 Chapter 3: Universal and reusable synthetic data .2 This chapter: Tailored synthetic data .2 Modeling Surface Realization .1 Realization is systematic .2 A parametric realization model .3 Generating training data .1 Estimation of bigram models .2 Divergence of bigram models .1 Efficiently computing expected counts .2 Efficient enumeration over permutations .1 Pruning high-degree trees .2 Minibatch estimation of c p .1 Data and setup .4 Sensitivity to initializer .5 Final evaluation on the test languages .7 Conclusion and Future Work. 160 7 Conclusion 163 References 166 Vita 196 xv List of Tables 2.1 A snippet of a PCFG for constituency structure.1 Features that fire in the two subtrees .2 Statistics on the treebanks of 10 real training languages.3 Split, langauge, and (sub-)family information of the 37 UD treebanks.4 Final comparison on all languages.5 Tagging accuracy on the 8 dev languages.1 Three typological properties in the World Atlas of Language Struc- tures (WALS).2 Data split of the 37 real treebanks.3 Comparison over different architectures on 16 training languages.4 Comparison over different subsets of hand-engineered features on 16 training languages.5 Comparison over grammar induction methods on 16 training languages.6 Accuracy on the simpler task of binary classification of relation direc- tionality brokedown by relation types.7 Accuracy on the simpler task of binary classification of relation direc- tionality brokedown by languages.8 Our final comparison on 51 training+testing languages.1 Average parsing results over 16 languages.2 The WALS features used in our experiment.3 Final evaluation table.1 Full results on single-source transfer using the synthetic languages. 157 xvii List of Figures 1.1 An English dependency tree in the UD version 1 scheme.2 An English constituency tree.3 A non-projective dependency tree.1 The setup of the traditional grammar induction approach.2 The setup of the proposed unsupervised parsing framework.1 The original UD tree for a short English sentence.2 Parsability of real versus synthetic languages.3 POS Perplexity of real versus synthetic languages.4 2-D visualization of the language space.5 Comprehensive results for single-source selection parsing using “kite graph”.6 Chance that selecting from synthetic languages achieves better UAS than selecting from real languages.7 UAS performance of different source parsers when applied to English development sentences.1 Basic predictive architecture.2 Extracting and pooling the neural features.3 Cross-validation loss broken down by relation.4 Comparison between our approach against the baseline model that ignores the input corpus.5 Scatterplots of predicted vs.1 A 2-layer typology component.2 The architecture of the delexicalized graph-based BIST parser.4 Effect of the size |u(ℓ) | of the unparsed corpus.5 Performance on noisy input over 16 training languages.6 Evaluation by dependency relation type, showing an equal-weighted average of the 16 development languages.7 The confusion matrix of our parser.1 The correlation between the divergence and transfer parsing accuracy.