Papers by Ran Zmigrod
On Finding the K-best Non-projective Dependency Trees (2021.acl-long)
Copied to clipboard
| Challenge: | Existing work on finding the one-best dependency tree has not extended this to finding the K-best tree. |
| Approach: | They propose to simplify the K-best spanning tree algorithm by decoding the K best dependency trees with a root constraint. |
| Outcome: | The proposed algorithm can be used to find the K-best dependency trees without root constraint. |
“What is the value of templates?” Rethinking Document Information Extraction Datasets for LLMs (2024.findings-emnlp)
Copied to clipboard
Ran Zmigrod, Pranav Shetty, Mathieu Sibue, Zhiqiang Ma, Armineh Nourbakhsh, Xiaomo Liu, Manuela Veloso
| Challenge: | Existing work on prompt-response datasets for visually rich document understanding (VRDU) is labor-intensive. |
| Approach: | They propose a set of questions that are transformed from a key information extraction template to a prompt-response format using a plethora of bespoke templates. |
| Outcome: | The proposed datasets are compared with baseline models on K2Q with zero-shot prompting. |
Please Mind the Root: Decoding Arborescences for Dependency Parsing (2020.emnlp-main)
Copied to clipboard
| Challenge: | a dependency tree has a root constraint, but only one edge may emanate from the root node. |
| Approach: | They propose an algorithm which enforces a root constraint without compromising the original runtime. |
| Outcome: | The proposed algorithm satisfies the constraint without compromising the original runtime. |
Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology (P19-1)
Copied to clipboard
| Challenge: | Gender stereotypes are manifest in most of the world's languages and are consequently propagated or amplified by NLP systems. |
| Approach: | They propose a method for converting between masculine-inflected and feminine-infflectes sentences in morphologically rich languages to reduce gender stereotyping by a factor of 2.5 without any sacrifice to grammaticality. |
| Outcome: | The proposed approach reduces gender stereotyping by 2.5 without any sacrifice to grammaticality. |
Fine-Tuning Language Models with Differential Privacy through Adaptive Noise Allocation (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Language models can memorize detailed information and patterns, but raise privacy concerns . ANADP reduces the performance gap between regular and DP fine-tuning while maintaining the privacy constraints. |
| Approach: | They propose an algorithm that allocates additive noise based on the importance of model parameters to reduce the performance gap between regular fine-tuning and traditional DP fine- tuning. |
| Outcome: | The proposed algorithm narrows the performance gap between regular fine-tuning and traditional DP fine- tuning while maintaining privacy constraints. |
Exact Paired-Permutation Testing for Structured Test Statistics (2022.naacl-main)
Copied to clipboard
| Challenge: | Existing methods to evaluate test statistic are Monte Carlo approximations which use a summation over all 2 N possible swaps. |
| Approach: | They propose an exact algorithm for the paired-permutation test for a family of structured test statistics. |
| Outcome: | The proposed algorithm is 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset. |
Efficient Sampling of Dependency Structure (2021.emnlp-main)
Copied to clipboard
| Challenge: | Spanning trees are a fundamental model of dependency structure in natural language processing, syntactic dependency trees. |
| Approach: | They propose to use a spanning tree sampling algorithm to faithfully sample dependency trees from a graph subject to a root constraint. |
| Outcome: | The proposed sampling algorithm can sample K trees without replacement in O(K N3 + K2 N) time. |
Efficient Computation of Expectations under Spanning Tree Distributions (2021.tacl-1)
Copied to clipboard
| Challenge: | a general framework for inference in spanning tree models is presented . a spanning-tree model is a combinatorial structure that is important for natural language processing . |
| Approach: | They propose a general framework for inference in spanning tree models . they exploit a connection between expectations and gradients, which allows efficient algorithms . |
| Outcome: | The proposed framework is up to 15 times faster than existing algorithms and reduces runtime complexity by a factor of the sentence length. |
Information-Theoretic Probing for Linguistic Structure (2020.acl-main)
Copied to clipboard
| Challenge: | Neural networks are the backbone of modern stateof-the-art natural language processing systems. |
| Approach: | They propose an information-theoretic operationalization of probing as estimating mutual information that contradicts received wisdom . they evaluate on a set of ten typologically diverse languages often underrepresented in NLP research—plus English—totalling eleven languages. |
| Outcome: | The proposed model outperforms existing models on ten typologically diverse languages and English on 11 languages. |
UniMorph 4.0: Universal Morphology (2022.lrec-1)
Copied to clipboard
Khuyagbaatar Batsuren, Omer Goldman, Salam Khalifa, Nizar Habash, Witold Kieraś, Gábor Bella, Brian Leonard, Garrett Nicolai, Kyle Gorman, Yustinus Ghanggo Ate, Maria Ryskina, Sabrina Mielke, Elena Budianskaya, Charbel El-Khaissi, Tiago Pimentel, Michael Gasser, William Abbott Lane, Mohit Raj, Matt Coler, Jaime Rafael Montoya Samame, Delio Siticonatzi Camaiteri, Esaú Zumaeta Rojas, Didier López Francis, Arturo Oncevay, Juan López Bautista, Gema Celeste Silva Villegas, Lucas Torroba Hennigen, Adam Ek, David Guriel, Peter Dirix, Jean-Philippe Bernardy, Andrey Scherbakov, Aziyana Bayyr-ool, Antonios Anastasopoulos, Roberto Zariquiey, Karina Sheifer, Sofya Ganieva, Hilaria Cruz, Ritván Karahóǧa, Stella Markantonatou, George Pavlidis, Matvey Plugaryov, Elena Klyachko, Ali Salehi, Candy Angulo, Jatayu Baxi, Andrew Krizhanovsky, Natalia Krizhanovskaya, Elizabeth Salesky, Clara Vania, Sardana Ivanova, Jennifer White, Rowan Hall Maudslay, Josef Valvoda, Ran Zmigrod, Paula Czarnowska, Irene Nikkarinen, Aelita Salchak, Brijesh Bhatt, Christopher Straughn, Zoey Liu, Jonathan North Washington, Yuval Pinter, Duygu Ataman, Marcin Wolinski, Totok Suhardijanto, Anna Yablonskaya, Niklas Stoehr, Hossep Dolatian, Zahroh Nuriah, Shyam Ratan, Francis M. Tyers, Edoardo M. Ponti, Grant Aiton, Aryaman Arora, Richard J. Hatcher, Ritesh Kumar, Jeremiah Young, Daria Rodionova, Anastasia Yemelina, Taras Andrushko, Igor Marchenko, Polina Mashkovtseva, Alexandra Serova, Emily Prud’hommeaux, Maria Nepomniashchaya, Fausto Giunchiglia, Eleanor Chodroff, Mans Hulden, Miikka Silfverberg, Arya D. McCarthy, David Yarowsky, Ryan Cotterell, Reut Tsarfaty, Ekaterina Vylomova
| Challenge: | The Universal Morphology project provides broad-coverage instantiated morphological inflection tables for hundreds of diverse languages. |
| Approach: | They propose a language-independent feature schema for rich morphological annotation and a type-level resource of annotated data in diverse languages realizing that schema. |
| Outcome: | The proposed schema has added 66 new languages, including 24 endangered languages. |
Higher-order Derivatives of Weighted Finite-state Machines (2021.acl-short)
Copied to clipboard
| Challenge: | Weighted finite-state machines (WFSMs) have a storied role in NLP . e.g., conditional random fields for part-of-speech tagging are considered special cases of WFSM. |
| Approach: | They propose an algorithm for evaluating derivatives of all orders that is faster than prior algorithms . they also find that it is faster for computing second-order expectations . |
| Outcome: | The proposed algorithm is faster than prior algorithms and can compute second-order expectations. |
Efficient Semiring-Weighted Earley Parsing (2023.acl-long)
Copied to clipboard
| Challenge: | Using Earley's context-free parsing algorithm, we show that the speed-ups are effective in practice. |
| Approach: | They propose a context-free parsing algorithm with various known and new speed-ups that improve Earley's (1970) O(N3|G||R|) They also propose 'a binarized version' that achieves runtime of O(M| |G| when the grammar is represented compactly as a single finite-state automaton M. |
| Outcome: | The proposed algorithm can be used to reduce the complexity of CKY on a binarized version of the grammar G. |