Canada

We present Earley&#39;s (1970) context-free parsing algorithm as a deduction system, incorporating various known and new speed-ups. In particular, our presentation supports a known worst-case runtime improvement from Earley&#39;s (1970) O(N^3|G||R|), which is unworkable for the large grammars that arise in natural language processing, to O(N^3|G|), which matches the complexity of CKY on a binarized version of the grammar G. Here N is the length of the sentence, |R| is the number of productions in G, and |G| is the total length of those productions. We also provide a version that achieves runtime of O(N^3|M|) with |M| |G| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate the possibility of deduction cycles, and further generalize Stolcke&#39;s method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars.

&lt;iframe src=&quot;https://app.sli.do/event/6qSnTPZvioRLfFJpZUjhCw/embed/polls/82823563-7a45-49a2-9883-af6aa9e5511f&quot; width=&quot;300&quot; height=&quot;400&quot;&gt;&lt;/iframe&gt;

ACL 2023

Efficient Semiring-Weighted Earley Parsing

prefix weight

deduction system

semiring parsing

context-free grammar

earley's algorithm

### Welcome to ACL 2023, the 61st Annual Meeting of the Association for Computational Linguistics! 
<br>The conference will be held in Toronto, Canada, July 9-14, 2023.<br><br>
Following the succession of the recent conferences in our field, ACL 2023 will adopt a hybrid format.
While the impact of Covid has considerably diminished in terms of traveling, obtaining visas to Canada
entails a very long process. Moreover, the global economic conditions pose challenges for many individuals to travel to conferences. Recognizing these circumstances, we know many participants may not be
able to attend the conference in person. Therefore, we are committed to providing a great virtual platform
so everyone has the opportunity to interact with other participants and enjoy the conference. Based on the
current registered participants, approxiately 30% have chosen to attend the conference virtually. Whether
you join us in person or virtually, we sincerely hope everyone has a remarkable conference experience.<br>
This General Chair’s message is where I express my gratitude to the many individuals who have made
enormous contributions to the conference over the past year.

Read [**ACL 2023 General Chair's message**](https://docs.google.com/document/d/1WobYM7norbG4dI48s75HfJoD89qgX5a_F-6U8AteLSA/edit?usp=sharing/) in full.

##### **[Conference Handbook](https://2023.aclweb.org/downloads/acl2023-handbook.pdf)**
<br><br><br><br>

The Association for Computational Linguistics (ACL) is the premier international scientific and professional society for people working on computational problems involving human language, a field often referred to as either computational linguistics or natural language processing.

We present Earley's (1970) context-free parsing algorithm as a deduction system, incorporating various known and new speed-ups. In particular, our presentation supports a known worst-case runtime improvement from Earley's (1970) O(N^3|G||R|), which is unworkable for the large grammars that arise in natural language processing, to O(N^3|G|), which matches the complexity of CKY on a binarized version of the grammar G. Here N is the length of the sentence, |R| is the number of productions in G, and |G| is the total length of those productions. We also provide a version that achieves runtime of O(N^3|M|) with |M| |G| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate the possibility of deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars.

<iframe src="https://app.sli.do/event/6qSnTPZvioRLfFJpZUjhCw/embed/polls/82823563-7a45-49a2-9883-af6aa9e5511f" width="300" height="400"></iframe>

poster

Analogical reasoning is a fundamental capacity of human cognition that allows us to reason abstractly about novel situations by relating them to past experiences. While it is thought to be essential for robust reasoning in AI systems, conventional approaches require significant training and/or hard-coding of domain knowledge to be applied to benchmark tasks. Inspired by cognitive science research that has found connections between human language and analogy-making, we explore the use of intuitive language-based abstractions to support analogy in AI systems. Specifically, we apply large pre-trained language models (PLMs) to visual Raven's Progressive Matrices (RPM), a common relational reasoning test. By simply encoding the perceptual features of the problem into language form, we find that PLMs exhibit a striking capacity for zero-shot relational reasoning, exceeding human performance and nearing supervised vision-based methods. We explore different encodings that vary the level of abstraction over task features, finding that higher-level abstractions further strengthen PLMs' analogical reasoning. Our detailed analysis reveals insights on the role of model complexity, in-context learning, and prior knowledge in solving RPM tasks.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/b9fe3543-ea0e-4d29-b674-6f7c526aad98" width="300" height="400"></iframe>

In-Context Analogical Reasoning with Pre-Trained Language Models

We consider the automated generation of sonnets, a poetic form constrained according to meter, rhyme scheme, and length. Sonnets generally also use rhetorical figures, expressive language, and a consistent theme or narrative. Our constrained decoding approach allows for the generation of sonnets within preset poetic constraints, while using a relatively modest neural backbone. Human evaluation confirms that our approach produces Shakespearean sonnets that resemble human-authored sonnets, and which adhere to the genre's defined constraints and contain lyrical language and literary devices.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/93fa7d03-5085-4724-9201-1d982a57159e" width="300" height="400"></iframe>

The Mechanical Bard: An Interpretable Machine Learning Approach to Shakespearean Sonnet Generation

As natural language processing (NLP) has recently seen an unprecedented level of excitement, and more people are eager to enter the field, it is unclear whether current research reproducibility efforts are sufficient for this group of beginners to apply the latest developments. To understand their needs, we conducted a study with 93 students in an introductory NLP course, where students reproduced the results of recent NLP papers. Surprisingly, we find that their programming skill and comprehension of research papers have a limited impact on their effort spent completing the exercise. Instead, we find accessibility efforts by research authors to be the key to success, including complete documentation, better coding practice, and easier access to data files. Going forward, we recommend that NLP researchers pay close attention to these simple aspects of open-sourcing their work, and use insights from beginners' feedback to provide actionable ideas on how to better support them.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/7c27dccd-1fe5-48c1-95d1-85d86b1e8555" width="300" height="400"></iframe>

NLP Reproducibility For All: Understanding Experiences of Beginners

Target-dependent sentiment classification~(TSC) enables a fine-grained automatic analysis of sentiments expressed in texts. Sentiment expression varies depending on the domain, and it is necessary to create domain-specific datasets.While socially important, TSC in the news domain remains relatively understudied.We introduce MAD-TSC, a new dataset which differs substantially from existing resources.First, it includes aligned examples in eight languages to facilitate a comparison of performance for individual languages, and a direct comparison of human and machine translation. Second, the dataset is sampled from a diversified parallel news corpus, and is diversified in terms of news sources and geographic spread of entities.Finally, MAD-TSC is more challenging than existing datasets because its examples are more complex.We exemplify the use of MAD-TSC with comprehensive monolingual and multilingual experiments.The latter show that machine translations can successfully replace manual ones, and that performance for all included languages can match that of English by automatically translating test examples.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/455a969e-c877-44bc-a401-4df529334144" width="300" height="400"></iframe>

MAD-TSC: A Multilingual Aligned News Dataset for Target-dependent Sentiment Classification

With the ubiquitous use of online meeting platforms and robust automatic speech recognition systems, meeting transcripts have emerged as a promising domain for natural language tasks. Most recent works on meeting transcripts primarily focus on summarization and extraction of action items. However, meeting discussions also have a useful question-answering (QA) component, crucial to understanding the discourse or meeting content, and can be used to build interactive interfaces on top of long transcripts. Hence, in this work, we leverage this inherent QA component of meeting discussions and introduce MeetingQA, an extractive QA dataset comprising of questions asked by meeting participants and corresponding responses. As a result, questions can be open-ended and actively seek discussions, while the answers can be multi-span and distributed across multiple speakers. Our comprehensive empirical study of several robust baselines including long-context language models and recent instruction-tuned models reveals that models perform poorly on this task (F1 = 57.3) and severely lag behind human performance (F1 = 84.6), thus presenting a challenging new task for the community to improve upon.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/df641a16-a853-4f2d-b8d1-d82560d84058" width="300" height="400"></iframe>

MeetingQA: Extractive Question-Answering on Meeting Transcripts

It is critical to measure and mitigate fairness-related harms caused by AI text generation systems, including stereotyping and demeaning harms. To that end, we introduce FairPrism, a dataset of 5,000 examples of AI-generated English text with detailed human annotations covering a diverse set of harms relating to gender and sexuality. FairPrism aims to address several limitations of existing datasets for measuring and mitigating fairness-related harms, including improved transparency, clearer specification of dataset coverage, and accounting for annotator disagreement and harms that are context-dependent. FairPrism's annotations include the extent of stereotyping and demeaning harms, the demographic groups targeted, and appropriateness for different applications. The annotations also include specific harms that occur in interactive contexts and harms that raise normative concerns when the "speaker" is an AI system. Due to its precision and granularity, FairPrism can be used to diagnose (1) the types of fairness-related harms that AI text generation systems cause, and (2) the potential limitations of mitigation methods, both of which we illustrate through case studies. Finally, the process we followed to develop FairPrism offers a recipe for building improved datasets for measuring and mitigating harms caused by AI systems.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/01fc3f35-0cd3-4463-b079-8cce8e1fa364" width="300" height="400"></iframe>

FairPrism: Evaluating Fairness-Related Harms in Text Generation

Evaluating multi-document summarization (MDS) quality is difficult. This is especially true in the case of MDS for biomedical literature reviews, where models must synthesize contradicting evidence reported across different documents. Prior work has shown that rather than performing the task, models may exploit shortcuts that are difficult to detect using standard n-gram similarity metrics such as ROUGE. Better automated evaluation metrics are needed, but few resources exist to assess metrics when they are proposed. Therefore, we introduce a dataset of human-assessed summary quality facets and pairwise preferences to encourage and support the development of better automated evaluation methods for literature review MDS. We take advantage of community submissions to the Multi-document Summarization for Literature Review (MSLR) shared task to compile a diverse and representative sample of generated summaries. We analyze how automated summarization evaluation metrics correlate with lexical features of generated summaries, to other automated metrics including several we propose in this work, and to aspects of human-assessed summary quality. We find that not only do automated metrics fail to capture aspects of quality as assessed by humans, in many cases the system rankings produced by these metrics are anti-correlated with rankings according to human annotators.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/0e9bc9ca-a913-465e-9281-1e3f472771d2" width="300" height="400"></iframe>

Automated Metrics for Medical Multi-Document Summarization Disagree with Human Evaluations

We present PaRTE, a collection of 1,126 pairs of Recognizing Textual Entailment (RTE) examples to evaluate whether models are robust to paraphrasing. We posit that if RTE models understand language, their predictions should be consistent across inputs that share the same meaning. We use the evaluation set to determine if RTE models' predictions change when examples are paraphrased. In our experiments, contemporary models change their predictions on 8-16% of paraphrased examples, indicating that there is still room for improvement.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/0fe64542-8a01-43d0-aa9f-84052bfb10b1" width="300" height="400"></iframe>

Evaluating Paraphrastic Robustness in Textual Entailment Models

Large language models (LLMs) have shown impressive performance in following natural language instructions to solve unseen tasks. However, it remains unclear whether models truly understand task definitions and whether the human-written definitions are optimal. In this paper, we systematically study the role of task definitions in instruction learning. We first conduct an ablation analysis informed by human annotations to understand which parts of a task definition are most important, and find that model performance only drops substantially when removing contents describing the task output, in particular label information. Next, we propose an automatic algorithm to compress task definitions to a minimal supporting set of tokens, and find that 60\% of tokens can be removed while maintaining or even improving model performance. Based on these results, we propose two strategies to help models better leverage task instructions: (1) providing only key information for tasks in a common structured format, and (2) adding a meta-tuning stage to help the model better understand the definitions. With these two strategies, we achieve a 4.2 Rouge-L improvement over 119 unseen test tasks.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/982af804-3b12-4f08-95bf-e2c17bf8d011" width="300" height="400"></iframe>

Did You Read the Instructions? Rethinking the Effectiveness of Task Definitions in Instruction Learning

When people think of everyday things like an egg, they typically have a mental image associated with it. This allows them to correctly judge, for example, that "the yolk surrounds the shell" is a false statement. Do language models similarly have a coherent picture of such everyday things? To investigate this, we propose a benchmark dataset consisting of 100 everyday things, their parts, and the relationships between these parts, expressed as 11,720 "X relation Y?" true/false questions. Using these questions as probes, we observe that state-of-the-art pre-trained language models (LMs) like GPT-3 and Macaw have fragments of knowledge about these everyday things, but do not have fully coherent "parts mental models" (54-59% accurate, 19-43% conditional constraint violation). We propose an extension where we add a constraint satisfaction layer on top of the LM's raw predictions to apply commonsense constraints. As well as removing inconsistencies, we find that this also significantly improves accuracy (by 16-20%), suggesting how the incoherence of the LM's pictures of everyday things can be significantly reduced.

<iframe src="https://app.sli.do/event/pk54NpNnxuhWHUa3vSMXH2/embed/polls/15f28102-47dc-4840-ad93-d72f3dff5de4" width="300" height="400"></iframe>

Downloads

Next from ACL 2023

In-Context Analogical Reasoning with Pre-Trained Language Models

Similar lecture

A Fast Algorithm for Computing Prefix Probabilities