International audience

We propose a novel discriminative model for sequence labeling called Bregman conditional random fields (BCRF).Contrary to standard linear-chain conditional random fields, BCRF allows fast parallelizable inference algorithms based on iterative Bregman projections.We show how such models can be learned using Fenchel-Young losses, including extension for learning from partial labels.Experimentally, our approach delivers comparable results to CRF while being faster, and achieves better results in highly constrained settings compared to mean field, another parallelizable alternative.

Named-entity recognition (NER) is a task that typically requires large annotated datasets, which limits its applicability across domains with varying entity definitions. This paper addresses few-shot NER, aiming to transfer knowledge to new domains with minimal supervision. Unlike previous approaches that rely solely on limited annotated data, we propose a weakly-supervised algorithm that combines small labeled datasets with large amounts of unlabeled data. Our method extends the k-means algorithm with label supervision, cluster size constraints, and domain-specific discriminative subspace selection. This unified framework achieves state-of-the-art results in few-shot NER, demonstrating its effectiveness in leveraging unlabeled data and adapting to domain-specific challenges.

Descriptive grammars are highly valuable, but writing them is time-consuming and difficult. Furthermore, while linguists typically use corpora to create them, grammar descriptions often lack quantitative data. As for formal grammars, they can be challenging to interpret. In this paper, we propose a new method to extract and explore significant fine-grained grammar patterns and potential syntactic grammar rules from treebanks, in order to create an easy-to-understand corpus-based grammar. More specifically, we extract descriptions and rules across different languages for two linguistic phenomena, agreement and word order, using a large search space and paying special attention to the ranking order of the extracted rules. For that, we use a linear classifier to extract the most salient features that predict the linguistic phenomena under study. We associate statistical information to each rule, and we compare the ranking of the model’s results to those of other quantitative and statistical measures. Our method captures both well-known and less well-known significant grammar rules in Spanish, French, and Wolof.

We introduce a novel tagging scheme for discontinuous named entity recognition based on an explicit description of the inner structure of discontinuous mentions.We rely on a weighted finite state automaton for both marginal and maximum a posteriori inference.As such, our method is sound in the sense that (1) wellformedness of predicted tag sequences is ensured via the automaton structure and ( 2) there is an unambiguous mapping between wellformed sequences of tags and (discontinuous) mentions.We evaluate our approach on three English datasets in the biomedical domain, and report comparable results to state-of-the-art while having a way simpler and faster model.

Span-based nested named-entity recognition (NER) has a cubic-time complexity using a variant of the CYK algorithm.We show that by adding a supplementary structural constraint on the search space, nested NER has a quadratictime complexity, that is the same asymptotic complexity than the non-nested case.The proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.

In this paper, we prove that separable negative log-likelihood losses for structured prediction are not necessarily Bayes consistent, or, in other words, minimizing these losses may not result in a model that predicts the most probable structure in the data distribution for a given input.This fact opens the question of whether these losses are well-adapted for structured prediction and, if so, why.

In many Natural Language Processing applications, neural networks have been found to fail to generalize on out-of-distribution examples.In particular, several recent semantic parsing datasets have put forward important limitations of neural networks in cases where compositional generalization is required.In this work, we extend a neural graph-based semantic parsing framework in several ways to alleviate this issue.Notably, we propose: (1) the introduction of a supertagging step with valency constraints, expressed as an integer linear program;(2) a reduction of the graph prediction problem to the maximum matching problem; (3) the design of an incremental early-stopping training strategy to prevent overfitting.Experimentally, our approach significantly improves results on examples that require structural generalization in the COGS dataset, a known challenging benchmark for compositional generalization.Overall, our results confirm that structural constraints are important for generalization in semantic parsing.

Abstract We propose a novel graph-based approach for semantic parsing that resolves two problems observed in the literature: (1) seq2seq models fail on compositional generalization tasks; (2) previous work using phrase structure parsers cannot cover all the semantic parses observed in treebanks. We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems. We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems. Experimentally, our approach delivers state-of-the-art results on GeoQuery, Scan, and Clevr, both for i.i.d. splits and for splits that test for compositional generalization.

We propose to express the forward-backward algorithm in terms of operations between sparse matrices in a specific semiring. This new perspective naturally leads to a GPU-friendly algorithm which is easy to implement in Julia or any programming languages with native support of semiring algebra. We use this new implementation to train a TDNN with the LF-MMI objective function and we compare the training time of our system with PyChain—a recently introduced C++/CUDA implementation of the LF-MMI loss. Our implementation is about two times faster while not having to use any approximation such as the "leaky-HMM".

We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures.In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n 6 ) down to O(n 3 ).The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers.We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting.We also experiment with pre-trained word embeddings and Bertbased neural networks.⇤ Work partially done while the author was a postdoc at University of Amsterdam with Ivan Titov. 1 The set of words that a node dominates is the set of leaf nodes in the subtree for which this node is the root.

We treat projective dependency trees as latent variables in our probabilistic model and induce them in such a way as to be beneficial for a downstream task, without relying on any direct tree supervision.Our approach relies on Gumbel perturbations and differentiable dynamic programming.Unlike previous approaches to latent tree learning, we stochastically sample global structures and our parser is fully differentiable.We illustrate its effectiveness on sentiment analysis and natural language inference tasks.We also study its properties on a synthetic structure induction task.Ablation studies emphasize the importance of both stochasticity and constraining latent structures to be projective trees.

We present a new method for the joint task of tagging and non-projective dependency parsing.We demonstrate its usefulness with an application to discontinuous phrase-structure parsing where decoding lexicalized spines and syntactic derivations is performed jointly.The main contributions of this paper are (1) a reduction from joint tagging and non-projective dependency parsing to the Generalized Maximum Spanning Arborescence problem, and (2) a novel decoding algorithm for this problem through Lagrangian relaxation.We evaluate this model and obtain state-of-the-art results despite strong independence assumptions.

Caio Corro, Joseph Le Roux, Mathieu Lacroix, Antoine Rozenknop, Roberto Wolfler Calvo. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2016.