{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T15:01:14Z","timestamp":1761490874230},"reference-count":73,"publisher":"MIT Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>The best solution of structured prediction models in NLP is often inaccurate because of limited expressive power of the model or to non-exact parameter estimation. One way to mitigate this problem is sampling candidate solutions from the model\u2019s solution space, reasoning that effective exploration of this space should yield high-quality solutions. Unfortunately, sampling is often computationally hard and many works hence back-off to sub-optimal strategies, such as extraction of the best scoring solutions of the model, which are not as diverse as sampled solutions. In this paper we propose a perturbation-based approach where sampling from a probabilistic model is computationally efficient. We present a learning algorithm for the variance of the perturbations, and empirically demonstrate its importance. Moreover, while finding the argmax in our model is intractable, we propose an efficient and effective approximation. We apply our framework to cross-lingual dependency parsing across 72 corpora from 42 languages and to lightly supervised dependency parsing across 13 corpora from 12 languages, and demonstrate strong results in terms of both the quality of the entire solution list and of the final solution.<jats:sup>1<\/jats:sup><\/jats:p>","DOI":"10.1162\/tacl_a_00291","type":"journal-article","created":{"date-parts":[[2019,9,30]],"date-time":"2019-09-30T19:43:11Z","timestamp":1569872591000},"page":"643-659","source":"Crossref","is-referenced-by-count":3,"title":["Perturbation Based Learning for Structured NLP Tasks with Application to Dependency Parsing"],"prefix":"10.1162","volume":"7","author":[{"given":"Amichay","family":"Doitch","sequence":"first","affiliation":[{"name":"Faculty of Industrial Engineering and Management, Technion, IIT."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram","family":"Yazdi","sequence":"additional","affiliation":[{"name":"Faculty of Industrial Engineering and Management, Technion, IIT."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamir","family":"Hazan","sequence":"additional","affiliation":[{"name":"Faculty of Industrial Engineering and Management, Technion, IIT."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roi","family":"Reichart","sequence":"additional","affiliation":[{"name":"Faculty of Industrial Engineering and Management, Technion, IIT."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00100"},{"key":"bib2","first-page":"1","volume-title":"Proceedings of COLING","author":"Bawden Rachel","year":"2016"},{"key":"bib3","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00051"},{"issue":"2","key":"bib4","first-page":"123","volume":"24","author":"Breiman Leo","year":"1996","journal-title":"Machine Learning"},{"issue":"2","key":"bib5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/net.3230100202","volume":"10","author":"Camerini Paolo M.","year":"1980","journal-title":"Networks"},{"key":"bib6","first-page":"173","volume-title":"Proceedings of ACL","author":"Charniak Eugene","year":"2005"},{"key":"bib7","first-page":"489","volume-title":"Proceedings of ACL","author":"Collins Michael","year":"2002"},{"key":"bib8","doi-asserted-by":"publisher","DOI":"10.1162\/0891201053630273"},{"key":"bib9","volume-title":"Proceedings of ICLR","author":"Dozat Timothy","year":"2017"},{"key":"bib10","first-page":"334","volume-title":"Proceedings of ACL","author":"Dyer Chris","year":"2015"},{"key":"bib11","volume-title":"Real analysis: Modern techniques and their applications","author":"Folland Gerald","year":"1999"},{"key":"bib12","first-page":"369","volume-title":"Proceedings of ACL-AFNLP","author":"Ganchev Kuzman","year":"2009"},{"key":"bib13","first-page":"1100","volume-title":"Proceedings of EMNLP","author":"Gimpel Kevin","year":"2013"},{"issue":"1","key":"bib14","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1017\/S096354830600767X","volume":"16","author":"Goldberg Leslie Ann","year":"2007","journal-title":"Combinatorics Probability and Computing"},{"key":"bib15","unstructured":"Daniil Golod. 2009. The k-best paths in Hidden Markov Models. Algorithms and applications to transmembrane protein topology recognition. Master\u2019s thesis, University of Waterloo."},{"key":"bib16","volume-title":"Proceedings of LREC","author":"Grave Edouard","year":"2018"},{"key":"bib17","first-page":"392","volume-title":"Proceedings of ACL","author":"Hall Keith","year":"2007"},{"key":"bib18","first-page":"1667","volume-title":"Proceedings of ICML","author":"Hazan Tamir","year":"2012"},{"key":"bib19","first-page":"1887","volume-title":"Proceedings of NIPS","author":"Hazan Tamir","year":"2013"},{"key":"bib20","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/10761.001.0001","volume-title":"Perturbations, Optimization, and Statistics","author":"Hazan Tamir","year":"2016"},{"key":"bib21","first-page":"1077","volume-title":"Proceedings of ACL","author":"Huang Liang","year":"2010"},{"issue":"3","key":"bib22","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1017\/S1351324905003840","volume":"11","author":"Hwa Rebecca","year":"2005","journal-title":"Natural language engineering"},{"key":"bib23","first-page":"1700","volume-title":"Proceedings of EMNLP","author":"Kalchbrenner Nal","year":"2013"},{"key":"bib24","first-page":"2224","volume-title":"Proceedings of ICASSP","author":"Keshet Joseph","year":"2011"},{"key":"bib25","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00101"},{"key":"bib26","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller Daphne","year":"2009"},{"key":"bib27","first-page":"1","volume-title":"Proceedings of ACL","author":"Koo Terry","year":"2010"},{"key":"bib28","first-page":"1744","volume-title":"Proceedings of EMNLP","author":"Kuncoro Adhiguna","year":"2016"},{"key":"bib29","first-page":"1058","volume-title":"Proceedings of HLT-NAACL","author":"Lacroix Oph\u00e9lie","year":"2016"},{"key":"bib30","first-page":"282","volume-title":"Proceedings of ICML","author":"Lafferty John","year":"2001"},{"key":"bib31","author":"Li Jiwei","year":"2016","journal-title":"arXiv preprint arXiv:1601.00372v2"},{"key":"bib32","first-page":"1253","volume-title":"Proceedings of ACL","author":"Ma Chunpeng","year":"2018"},{"key":"bib33","first-page":"1337","volume-title":"Proceedings of ACL","author":"Ma Xuezhe","year":"2014"},{"key":"bib34","doi-asserted-by":"crossref","first-page":"725","DOI":"10.3115\/1613715.1613807","volume-title":"Proceedings of EMNLP","author":"Macherey Wolfgang","year":"2008"},{"key":"bib35","first-page":"2085","volume-title":"Proceedings of NIPS","author":"Maddison Chris","year":"2014"},{"key":"bib36","first-page":"617","volume-title":"Proceedings of ACL","author":"Martins Andre","year":"2013"},{"key":"bib37","first-page":"92","volume-title":"Proceedings of ACL","author":"McDonald Ryan","year":"2013"},{"key":"bib38","first-page":"523","volume-title":"Proceedings of EMNLP","author":"McDonald Ryan","year":"2005"},{"key":"bib39","first-page":"62","volume-title":"Proceedings of EMNLP","author":"McDonald Ryan","year":"2011"},{"key":"bib40","first-page":"629","volume-title":"Proceedings of ACL","author":"Naseem Tahira","year":"2012"},{"issue":"2","key":"bib41","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1561\/1500000015","volume":"5","author":"Nenkova Ani","year":"2011","journal-title":"Foundations and Trends in Information Retrieval"},{"key":"bib42","first-page":"1659","volume-title":"Proceedings of LREC","author":"Nivre Joakim","year":"2016"},{"key":"bib43","first-page":"193","volume-title":"Proceedings of ICCV","author":"Papandreou George","year":"2011"},{"key":"bib44","first-page":"1531","volume-title":"Proceedings of ACL","author":"Ponti Edoardo Maria","year":"2018"},{"issue":"2","key":"bib45","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/5.18626","volume":"77","author":"Rabiner Lawrence R.","year":"1989","journal-title":"Proceedings of the IEEE"},{"key":"bib46","first-page":"328","volume-title":"Proceedings of EMNLP","author":"Rasooli Mohammad Sadegh","year":"2015"},{"key":"bib47","first-page":"616","volume-title":"Proceedings of ACL","author":"Reichart Roi","year":"2007"},{"key":"bib48","first-page":"243","volume-title":"Proceedings of ACL-IJCNLP","author":"Rosa Rudolf","year":"2015"},{"key":"bib49","first-page":"1434","volume-title":"Proceedings of EMNLP","author":"Rush Alexander M.","year":"2012"},{"key":"bib50","first-page":"220","volume-title":"Proceedings of EACL","author":"Schlichtkrull Michael","year":"2017"},{"key":"bib51","first-page":"3919","volume-title":"Proceedings of HLT-NAACL","author":"Scholivet Manon","year":"2019"},{"key":"bib52","series-title":"Synthesis Lectures on Human Language Technologies","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02143-5","volume-title":"Linguistic Structure Prediction","author":"Smith Noah A.","year":"2011"},{"key":"bib53","volume-title":"Proceedings of ICLR","author":"Smith Samuel L.","year":"2017"},{"key":"bib54","first-page":"220","volume-title":"Proceedings of EACL","author":"S\u00f8gaard Anders","year":"2017"},{"key":"bib55","first-page":"39","volume-title":"Proceedings of HLT-NAACL","author":"Le Hai Son","year":"2012"},{"key":"bib56","first-page":"503","volume-title":"Proceedings of UAI","author":"Sontag David","year":"2008"},{"key":"bib57","doi-asserted-by":"crossref","first-page":"331","DOI":"10.3115\/1067807.1067851","volume-title":"Proceedings of EACL","author":"Steedman Mark","year":"2003"},{"key":"bib58","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00229"},{"key":"bib59","first-page":"649","volume-title":"Proceedings of HLT-NAACL","author":"Surdeanu Mihai","year":"2010"},{"key":"bib60","first-page":"1061","volume-title":"Proceedings of HLT-NAACL","author":"T\u00e4ckstr\u00f6m Oscar","year":"2013"},{"key":"bib61","first-page":"1221","volume-title":"Proceedings of AISTATS","author":"Tarlow Daniel","year":"2012"},{"key":"bib62","first-page":"711","volume-title":"Proceedings of EMNLP","author":"Tchernowitz Ilan","year":"2016"},{"key":"bib63","first-page":"1854","volume-title":"Proceedings of COLING","author":"Tiedemann J\u00f6rg","year":"2014"},{"key":"bib64","first-page":"69","volume-title":"Natural Language Processing and Chinese Computing","author":"Zhaopeng Tu","year":"2012"},{"key":"bib65","first-page":"1092","volume-title":"Proceedings of COLING","author":"Zhaopeng Tu","year":"2010"},{"key":"bib66","first-page":"425","volume-title":"Proceedings of ACL","author":"Vilares David","year":"2016"},{"issue":"1","key":"bib67","first-page":"1","volume":"1","author":"Wainwright Martin J.","year":"2008","journal-title":"Foundations and Trends in Machine Learning"},{"key":"bib68","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00113"},{"key":"bib69","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00248"},{"key":"bib70","first-page":"1325","volume-title":"Proceedings of EMNLP","author":"Wang Dingquan","year":"2018"},{"key":"bib71","first-page":"296","volume-title":"Proceedings of STOC","author":"Wilson David Bruce","year":"1996"},{"key":"bib72","first-page":"1857","volume-title":"Proceedings of EMNLP","author":"Zhang Yuan","year":"2015"},{"key":"bib73","first-page":"197","volume-title":"Proceedings of ACL","author":"Zhang Yuan","year":"2014"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T13:09:21Z","timestamp":1664543361000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/43522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":73,"alternative-id":["10.1162\/tacl_a_00291"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00291","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}