Alban Petit
email: alban.petit@lisn.upsaclay.frcaio.corro

Caio Corro

François Yvon
email: francois.yvon@isir.upmc.fr

Structural generalization in COGS: Supertagging is (almost) all you need

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.

Introduction

Semantic parsing aims to transform a natural language utterance into a structured representation. However, models based on neural networks have been shown to struggle on out-of-distribution utterances where compositional generalization is required, i.e., on sentences with novel combinations of elements observed separately during training [START_REF] Lake | Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks[END_REF][START_REF] Finegan-Dollak | Improving textto-SQL evaluation methodology[END_REF][START_REF] Keysers | Measuring compositional generalization: A comprehensive method on realistic data[END_REF]. [START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF] showed that neural graph-based semantic parsers are more robust to compositional generalization than sequence-to-sequence (seq2seq) models. Moreover, [START_REF] Herzig | Spanbased semantic parsing for compositional generalization[END_REF], [START_REF] Weißenhorn | Compositional generalization with a broadcoverage semantic parser[END_REF] and [START_REF] Petit | On graph-based reentrancy-free semantic parsing[END_REF] have shown that introducing valency and type constraints in a structured decoder improves compositional generalization capabilities.

In this work, we explore a different method for compositional generalization, based on supertagging. We demonstrate that local predictions (with global consistency constraints) are sufficient for compositional generalization. Contrary to [START_REF] Herzig | Spanbased semantic parsing for compositional generalization[END_REF] and [START_REF] Petit | On graph-based reentrancy-free semantic parsing[END_REF], our approach can predict any semantic graph (including ones with reentrancies), and contrary to [START_REF] Weißenhorn | Compositional generalization with a broadcoverage semantic parser[END_REF] it does not require any intermediate representation of the semantic structure.

Moreover, our experiments highlight two fundamental features that are important to tackle compositional generalization in this setting. First, as is well known in the syntactic parsing literature, introducing a supertagging step in a parser may lead to infeasible solutions. We therefore propose an integer linear programming formulation of supertagging that ensures the existence of at least one feasible parse in the search space, via the so-called companionship principle [START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF][START_REF] Bonfante | Supertagging with Constraints[END_REF]. Second, as the development dataset used to control training is in-distribution (i.e., it does not test for compositional generalization), there is a strong risk of overfitting. To this end, we propose an incremental early-stopping strategy that freezes part of the neural network during training.

Our contributions can be summarized as follows:

• we propose to introduce a supertagging step in a graph-based semantic parser;

• we show that, in this setting, argument identification can be reduced to a matching problem;

• we propose a novel approach based on inference in a factor graph to compute the weaklysupervised loss (i.e., without gold alignment);

• we propose an incremental early-stopping strategy to prevent overfitting;

• we evaluate our approach on COGS and observe that it outperforms comparable baselines on compositional generalization tasks. Notations. A set is written as {•} and a multiset as • . We denote by [n] the set of integers {1, ..., n}. We denote the sum of entries of the Hadamard product as ⟨•, •⟩ (i.e., the standard scalar product if arguments are vectors). We assume the input sentence contains n words. We use the term "concept" to refer to both predicates and entities.

Semantic parsing

COGS

The principle of compositionality states that "The meaning of an expression is a function of the meanings of its parts and of the way they are syntactically combined." [START_REF] Partee | Compositionality. Varieties of formal semantics[END_REF] Linguistic competence requires compositional generalization, that is the ability to understand new utterances made of known parts, e.g., understanding the meaning of "Marie sees Pierre" should entail the understanding of "Pierre sees Marie".

The Compositional Generalization Challenge based on Semantic Interpretation (COGS, [START_REF] Kim | COGS: A compositional generalization challenge based on semantic interpretation[END_REF] dataset is designed to evaluate two types of compositional generalizations. First, lexical generalization tests a model on known grammatical structures where words are used in unseen roles. For example, during training the word hedgehog is only used as a subject; the model needs to generalize to cases where it appears as an object. Second, structural generalization tests a model on syntactic structures that were not observed during training. Illustrations are in Table 1.

The error analysis presented by [START_REF] Weißenhorn | Compositional generalization with a broadcoverage semantic parser[END_REF] emphasizes that neural semantic parsers achieve good accuracy for lexical generalization but fail for structural generalization.

Semantic graph construction. A semantic structure in the COGS dataset is represented as a logical form. We transform this representation into a graph as follows:

1. For each concept instance, we add a labeled vertex.

2. For each argument p of a concept instance p ′ , we create a labeled arc from the vertex representing p ′ to the vertex representing p.

3. COGS explicitly identifies definiteness of nouns. Therefore, for each definite noun that triggers a concept, we create a vertex p with label definite and we create an arc with label det from p to the vertex representing the noun's concept.1 Indefiniteness is marked by the absence of such structure.

This transformation is illustrated in Figure 1.

Graph-based decoding

The standard approach [START_REF] Flanigan | A discriminative graph-based parser for the Abstract Meaning Representation[END_REF][START_REF] Dozat | Simpler but more accurate semantic dependency parsing[END_REF][START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF] to graph-based semantic parsing is a two-step pipeline:

1. concept tagging;

2. argument identification. The second step is a sub-graph prediction problem.

Concept tagging. We assume that each word can trigger at most one concept. Let T be the set of concepts, including a special tag ∅ ∈ T that will be used to identify semantically empty words (i.e., words that do not trigger any concept). Let λ ∈ R n×T be tag weights computed by the neural network. Without loss of generality, we assume that λ i,∅ = 0, ∀i ∈ [n]. We denote a sequence of tags as a boolean vector x ∈ {0, 1} n×T where x i,t = 1, t ̸ = ∅, indicates that word i triggers concept t. This means that ∀i ∈ [n], t∈T x i,t = 1. Given weights λ, computing the sequence of tags of maximum linear weight is a simple problem.

Argument identification. We denote L the set of argument labels, e.g., agent ∈ L. The second step assigns arguments to concepts instances. For this, we create a labeled graph G = (V, A) where:

• V = {i ∈ [n]|x i,∅ ̸ = 0}
is the set of vertices representing concept instances;

• A ⊆ V × V × L is the set of labeled arcs, where (i, j, l) ∈ A denotes an arc from vertex i to vertex j labeled l.

In practice, we construct a complete graph, including parallel arcs with different labels, but excluding self-loops. Given arc weights µ ∈ R A , argument identification reduces to the selection of the subset of arcs of maximum weight such at most one arc with a given direction between any two vertices is selected. Again, this problem is simple. We denote a set of arcs as a boolean vector z ∈ {0, 1} A where z i,j,l = 1 indicates that there is an arc from vertex i to vertex j labeled l in the prediction.

Multiple concepts per words. More realistic semantic parsing scenarios require to trigger more than one concept per word. This only impacts the concept tagging step: one must change the model to allow the prediction of several concepts per word, for example via multi-label prediction or using several tagging layers [START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF]. The argument identification step is left unchanged, i.e., we create one vertex per predicted concept in the graph.

Supertagging for graph-based semantic parsing

In the syntactic parsing literature, supertagging refers to assigning complex descriptions of the syntactic structure directly at the lexical level (Bangalore and Joshi, 1999). For example, while an occurrence of the verb 'to walk' can be described in a coarse manner via its part-of-speech tag, a supertag additionally indicates that this verb appears in a clause with a subject on the left and a verbal phrase on the right, the latter also potentially requiring an object on its right, see Figure 2 for an illustration in the formalism of lexicalized Tree-Adjoining Grammars (LTAGs, Joshi et al., 1975).

We propose to introduce an intermediary semantic supertagging step in a graph-based semantic parser. The pipeline of Section 2. (left) A standard LTAG parsing pipeline. We start with an input sentence, then predict one part-of-speech tag per word. This part-of-speech can be used as feature or to filter the set of possible supertags in the next step. The supertagging step chooses one supertag per word. Finally, in the last step we merge all supertags together. This operation can be synthesised as a derivation tree where arc labels indicate Gorn adresses of substitution and adjunction operations. We refer readers unfamiliar with LTAG parsing to [START_REF] Kallmeyer | Parsing Beyond Context-Free Grammars[END_REF]. (right) Our semantic parsing pipeline. We start with an input sentence, then predict at most one concept per word, where ∅ indicates no concept.

The supertagging step assigns one supertag per concept instance (i.e., excluding words tagged with ∅). Finally, the argument identification step identifies arguments of predicates using the valency constraints from the supertags.

argument identification.

This new pipeline is illustrated on Figure 3. Note that the introduction of the novel step does not impact the concept tagging step. As such, our approach is also applicable to datasets that would require multiple concepts prediction per word (see Section 2.2).

Semantic supertagging

In our setting, a supertag indicates the expected arguments of a concept instance (potentially none for an entity) and also how the concept is used. Contrary to syntactic grammars, our supertags do not impose a direction. In the following, we refer to an expected argument as a substitution site and to an expected usage as a root.

Formally, we define a (semantic) supertag as a multiset of tuples (l, d) ∈ L × {-, +} where l is a label and d indicates either substitution site or root, e.g., (agent, -) is a substitution site and (agent, +) is a root. For example, in Figure 1, the supertag associated with 'like' is (agent, -), (ccomp, -) and the one associated with 'prefer' is (agent, -), (xcomp, -), (ccomp, +) . The set of all supertags is denoted S.

The Companionship principle (CP).2 Let us first consider the following simple example: assuming we would like to parse the sentence "Marie ate", yet associate the transitive supertag (agent, -), (theme, -) to the verb. In this case, the argument identification step will fail: the verb has no object in this sentence. The CP states that each substitution site must have a potential root in the supertag sequence. That is, in the supertagging step, we must make sure that the number of substitution sites with a given label exactly matches the number of roots with the same label, to ensure that there will exist at least one feasible solution for the next step of the pipeline. As such, supertagging here is assigning tags in context.

Theorem 1. Given a set of supertags, a sequence of concept instances and associated supertag weights, the following problem is NP-complete: is there a sequence of supertag assignments with linear weight ≥ m that satisfies the CP?

Proof. First, note that given a sequence of supertags, it is trivial to check in linear time that its linear weight is ≥ m and that it satisfies the CP, therefore the problem is in NP. We now prove NPcompleteness by reducing 3-dimensional matching to supertagging with the CP. 3-dim. matching is defined as follows:

Let A = {a(i)} n i=1 , B = {b(i)} n i=1 and C = {c(i)} n i=1 be 3 sets of n elements and D ⊆ A × B × C. A subset D ′ ⊆ D is a 3-dim. matching if and only if, for any two distinct triples (a, b, c) ∈ D ′ and (a ′ , b ′ , c ′ ) ∈ D ′ , the following three conditions hold: a ̸ = a ′ , b ̸ = b ′ and c ̸ = c ′ .
The following decision problem is known to be NP-complete [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]: given A, B, C and D, is there a 3-dim. matching

D ′ ⊆ D with |D ′ | ≥ n?
We reduce this problem to supertagging with the CP as follows.

We construct an instance of the problem with 3n concept instances a(1), ..., a(n), b(1), ..., b(n), c(1), ..., c(n). The supertag set S is defined as follows, where their associated weight is 0 except if stated otherwise:

• For each triple (a, b, c) ∈ D, we add a supertag (b, -), (c, -) with weight 1 if and only if it is predicted for concept a;

• For each b ∈ B, we add a supertag (b, +) with weight 1 if and only if it is predicted for concept b;

• For each c ∈ C, we add a supertag (c, +) with weight 1 if and only if it is predicted for concept c.

If there exists a sequence of supertag assignment satisfying the CP that has a weight ≥ m = 3n, then there exists a solution for the 3-dim. matching problem, given by the supertags associated with concept instances a(1), ..., a(n).

Note that an algorithm for the supertagging decision problem could rely on the maximisation variant as a subroutine. This result motivates the use of a heuristic algorithm. We rely on the continuous relaxation of an integer linear program that we embed in a branch-and-bound procedure.We first explain how we construct the set of supertags as it impacts the whole program.

Supertag extraction. To improve generalization capabilities, we define the set of supertags as containing (1) the set of all observed supertags in the training set, augmented with (2) the crossproduct of all root combinations and substitution site combinations. For example, if the training data contains supertags (ccomp, +), (agent, -) and

(agent, -), (theme, -) , we also include (ccomp, +), (agent, -), (theme, -) and (agent, -) in the set of supertags.

Formally, let S + (resp. S -) be the set of root combinations (resp. substitution site combinations) observed in the data. The set of supertags is:

S = s + ∪ s -s + ∈ S + ∧ s -∈ S - ∧ s + ∪ s -̸ = .
Note that the empty multiset can not be a supertag. Supertag prediction. Let y -∈ {0, 1} n×S - and y + ∈ {0, 1} n×S + be indicator variables of the substitution sites and roots, respectively, associated with each word, e.g. y - i,s = 1 indicates that concept instance at position i ∈ [n] has substitution sites s ∈ S -. We now describe the constraints that y -and y + must satisfy. First, each position in the sentence should have exactly one set of substitution sites and one set of roots if and only if they have an associated concept:

s∈S - y - i,s = 1 -x i,∅ ∀i ∈ [n] (1) s∈S + y + i,s = 1 -x i,∅ ∀i ∈ [n] (2)
Next, we forbid the empty supertag:

y - i, + y + i, ≤ 1 ∀i ∈ [n] (3)
Finally, we need to enforce the companionship principle. We count in v - s,l the number of substitution sites with label l ∈ L in s ∈ S -, and similarly in v + s,l for roots. We can then enforce the number of roots with a given label to be equal to the number of substitution sites with the same label as follows:

i∈[n], s∈S - y - i,s v - s,l = i∈[n], s∈S + y + i,j v + s,l ∀l ∈ L . (4)
All in all, supertagging with the companionship principle reduces to the following integer linear program:

max y -,y + ⟨y -, ϕ -⟩ + ⟨y + , ϕ + ⟩, s.t. (1-4), y -∈ {0, 1} n×S -, y + ∈ {0, 1} n×S + .
In practice, we use the CPLEX solver.3 Timing. We initially implemented this ILP using the CPLEX Python API. The resulting implementation could predict supertags for only ≈ 10 sentences per second. We reimplemented the ILP using the CPLEX C++ API (via Cython) with a few extra optimizations, leading to an implementation that could solve ≈ 1000 instances per second.

Argument identification

The last step of the pipeline is argument identification. Note that in many cases, there is no ambiguity, see the example in Figure 3: as there is at most one root and substitution site per label, we can infer that the theme of concept instance eat is cake, etc. However, in the general case, there may be several roots and substitution sites with the same label. In the example of Figure 1, we would have 3 agent roots after the supertagging step.

For ambiguous labels after the supertagging step, we can rely on a bipartite matching (or assignment) algorithm. Let l ∈ L be an ambiguous label. We construct a bipartite undirected graph as follows:

• The first node set C contains one node per substitution site with label l;

• The second node set C ′ contains one node per root with label l;

• we add an edge for each pair (c, c ′ ) ∈ C × C ′ with weight µ i,j,l , where i ∈ [n] and j ∈ [n] are sentence positions of the substitution site represented by c and the root represented by c ′ , respectively.

We then use the Jonker-Volgenant algorithm [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF][START_REF] David F Crouse | On implementing 2d rectangular assignment algorithms[END_REF] to compute the matching of maximum linear weight with complexity cubic w.r.t. the number of nodes. Note that thanks to the companionship principle, there is always at least one feasible solution to this problem, i.e., our approach will never lead to a "dead-end" and will always predict a (potentially wrong) semantic parse for any given input.

Training objective

Supervised loss. Let ( x, y -, y + , z) be a gold annotation from the training dataset. We use separable negative log-likelihood losses (NLL) for each step as they are fast to compute and work well in practice [START_REF] Zhang | Dependency parsing as head selection[END_REF][START_REF] Corro | On the inconsistency of separable losses for structured prediction[END_REF]. The concept loss is a sum of one NLL loss per word:

ℓ concept (λ; x) = -⟨λ, x⟩ + i∈[n] log t∈T exp λ i,t .
For supertagging, we use the following losses:

ℓ sub. (ϕ -; y -) = -⟨ϕ -, y -⟩ + i∈[n] log s∈S - exp ϕ - i,s , ℓ root (ϕ + ; y + ) = -⟨ϕ + , y + ⟩ + i∈[n] log s∈S + exp ϕ + i,s .
Finally, for argument identification we have one loss per couple of positions in the sentence:

ℓ arg. (µ; z) = -⟨µ, z⟩ + (i,j)∈[n]×[n] log l∈L exp µ i,j,l .
Note that for the concept loss, we have a special empty tag with null score for the case where there is no concept associated with a word in the gold output (and similarly for argument identification).

Weakly-supervised loss. In practice, it is often the case that we do not observe the alignment between concept instances and words in the training dataset, which must therefore be learned jointly with the parameters. To this end, we follow an "hard" EM-like procedure [START_REF] Radford | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF]:

• E step: compute the best possible alignment between concept instances and words;

• M step: apply one gradient descent step using the "gold" tuple ( x, y -, y + , z) induced by the alignment from the E step.

Note that the alignment procedure in the E step is NP-hard [START_REF] Petit | On graph-based reentrancy-free semantic parsing[END_REF], Theorem 2), as the scoring function is not linear. For example, assume two concept instances p and p ′ such that p ′ is an argument of p. If p and p ′ are aligned with i and j, respectively, the alignment score includes the token tagging weights induced by this alignment plus the weight of the labeled dependency from i to j.

We propose to reduce the E step to maximum a posteriori (MAP) inference in a factor graph, see Figure 4. We define one random variable (RV) taking values in [n] per concept instance. The assignment of these RVs indicate the alignment between

A1 A2 A3 A4 u1 CAT u2 EAT u3 THE u4 CAKE b12 AGENT b24 THEME b34 DET ATMOSTONE Ai ui 1 λ1,t 2 λ2,t 3 λ3,t 4 λ4,t 5 λ5,t Ai \ Aj 1 2 3 4 5 1 -∞ µ 1,2,l µ 1,3,l µ 1,4,l µ 1,5,l 2 µ 2,1,l -∞ µ 2,3,l µ 2,4,l µ 2,5,l 3 µ 3,1,l µ 3,2,l -∞ µ 3,4,l µ 3,5,l 4 µ 4,1,l µ 4,2,l µ 4,3,l -∞ µ 4,5,l 5 µ 5,1,l µ 5,2,l µ 5,3,l µ ,,l -∞ Figure 4: (left)
The factor graph used to compute the best alignment of the semantic graph in E steps for the sentence 'A cat ate the cake'. Each variable corresponds to a concept instance in the semantic graph and has an associated unary factor. For each argument of a concept instance, we add a binary factor between between the concept instance and its argument's instance. (center) Weights of an unary factor given the value of its corresponding variable. We denote t the concept corresponding to that factor (displayed above unary factors). (right) Weights of a binary factor b ij , where the concept instance represented by A j is an argument of the concept instance represented by A i in the semantic graph. We denote l the label of the argument (displayed above binary factors).

concept instances and words. Unary factors correspond to tagging weights, e.g. aligning a concept t ∈ T with word i ∈ [n] induces weight λ i,t . Binary factors correspond to argument identification: for each arc the semantic graph, we add a binary factor between the two concept instances RVs that will induce the dependency weight given the RVs assignment. Finally, there is a global factor acting as an indicator function, that forbids RVs assignments where different concept instances are aligned with the same word. We use AD3 [START_REF] André | An augmented lagrangian approach to constrained map inference[END_REF] for MAP inference in this factor graph.

Related work

Compositional generalization. Compositional generalization has been a recent topic of interest in semantic parsing. This is because failure to generalize is an important source of error, especially in seq2seq models [START_REF] Lake | Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks[END_REF][START_REF] Finegan-Dollak | Improving textto-SQL evaluation methodology[END_REF][START_REF] Herzig | Spanbased semantic parsing for compositional generalization[END_REF][START_REF] Keysers | Measuring compositional generalization: A comprehensive method on realistic data[END_REF]. Several directions have been explored in response. Zheng and Lapata (2021) rely on latent concept tagging in the encoder of a seq2seq model, while [START_REF] Lindemann | Compositional generalisation with structured reordering and fertility layers[END_REF] introduce latent fertility and re-ordering layers in their model. Another research direction uses data augmentation methods to improve generalization [START_REF] Jia | Data recombination for neural semantic parsing[END_REF][START_REF] Andreas | Good-enough compositional data augmentation[END_REF][START_REF] Akyürek | Learning to recombine and resample data for compositional generalization[END_REF][START_REF] Qiu | Improving compositional generalization with latent structure and data augmentation[END_REF][START_REF] Yang | SUBS: Subtree substitution for compositional semantic parsing[END_REF].

Span-based methods have also been shown to improve compositional generalization [START_REF] Pasupat | Span-based hierarchical semantic parsing for task-oriented dialog[END_REF][START_REF] Herzig | Spanbased semantic parsing for compositional generalization[END_REF][START_REF] Liu | Learning algebraic recombination for compositional generalization[END_REF]. Particularly, [START_REF] Liu | Learning algebraic recombination for compositional generalization[END_REF] explicitly represent input sentences as trees and use a Tree-LSTM [START_REF] Sheng | Improved semantic representations from tree-structured long short-term memory networks[END_REF] in their encoder. While this parser exhibits strong performance, this approach requires work from domain experts to define the set of operations needed to construct trees for each dataset. Other line of work that seek to tackle compositional generalization issues include using pretrained models (Herzig et al., 2021;[START_REF] Furrer | Compositional generalization in semantic parsing: Pre-training vs. specialized architectures[END_REF], specialized architectures [START_REF] Korrel | Transcoding compositionally: Using attention to find more generalizable solutions[END_REF][START_REF] Russin | Compositional generalization by factorizing alignment and translation[END_REF][START_REF] Gordon | Permutation equivariant models for compositional generalization in language[END_REF][START_REF] Csordás | The devil is in the detail: Simple tricks improve systematic generalization of transformers[END_REF] and regularization [START_REF] Yin | Consistency regularization training for compositional generalization[END_REF].

Graph-based semantic parsing. Graph-based methods have been popularized by syntactic dependency parsing [START_REF] Mcdonald | Non-projective dependency parsing using spanning tree algorithms[END_REF]. To reduce computational complexity, [START_REF] Dozat | Simpler but more accurate semantic dependency parsing[END_REF] proposed a neural graph-based parser that handles each dependency as an independent classification problem. Similar approaches were applied in semantic parsing, first for AMR parsing [START_REF] Lyu | AMR parsing as graph prediction with latent alignment[END_REF][START_REF] Groschwitz | AMR dependency parsing with a typed semantic algebra[END_REF]. Graph-based approaches have only recently been evaluated for compositional generalization. The approach proposed by [START_REF] Petit | On graph-based reentrancy-free semantic parsing[END_REF] showed significant improvements compared to existing work on compositional splits of the GeoQuery dataset. However, their parser can only generate trees. [START_REF] Weißenhorn | Compositional generalization with a broadcoverage semantic parser[END_REF] and [START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF] introduced approaches that can handle arbitrary graphs, a requirement to successfully parse COGS.

Experiments

We use a neural network based on a BiLSTM [START_REF] Hochreiter | Long short-term memory[END_REF] and a biaffine layer for arc weights [START_REF] Dozat | Deep biaffine attention for neural dependency parsing[END_REF] Table 2: Exact match accuray on COGS. We report results for each subset of the test set (structural generalization and lexical generalization) and the overall accuracy. For our results, we report the mean over 3 runs. Entries marked with † use a subset of 1k sentences from the generalization set as their development set.

evaluate our approach in a fully supervised setting, i.e., we do not use a pre-trained neural network like BERT [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF]. Code to reproduce the experiments is available online.4

6.1 Early stopping COGS only possesses an in-distribution development set and the accuracy of most parsers on this set usually reaches 100%. Previous work by [START_REF] Conklin | Meta-learning to compositionally generalize[END_REF] emphasized that the lack of a development set representative of the generalization set makes model selection difficult and hard to reproduce. They proposed to sample a small subset of the generalization set that is used for development. Both their work and LaGR [START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF] use this approach and sample a subset of 1000 sentences from the generalization set to use as their development set. However, we argue that this development set leaks compositional generalization information during training.

We propose a variant of early stopping to prevent overfitting on the in-distribution data without requiring a compositional generalization development set. We incrementally freeze layers in the neural network as follows: each subtask (predic-tion of tags, supertags, dependencies) is monitored independently on the in-distribution development set. As soon as one of these tasks achieves 100% accuracy, we freeze the shared part of the neural architecture (word embeddings and the BiLSTM). We also freeze the layers that produce the scores of the perfectly predicted task. For each subsequent task that achieves perfect accuracy, the corresponding layers are also frozen. This early stopping approach prevents overfitting.

We also experimented using the hinge loss instead of the NLL loss as it shares similar properties to our early stopping strategy: once a prediction is correct (including a margin between the gold output and other outputs), the gradient of the loss becomes null. We however found that this loss yields very low experimental results (null exact match score on the test set).

Results

All results are exact match accuracy, i.e., the ratio of semantic structures that are correctly predicted. We report the overall accuracy,5 the accuracy over all lexical generalization cases as well as the individual accuracy for each structural generalization case. We report mean accuracy over 3 runs. External baselines. We compare our method to several baselines: (1) the seq2seq models of [START_REF] Kim | COGS: A compositional generalization challenge based on semantic interpretation[END_REF], [START_REF] Akyürek | Learning to recombine and resample data for compositional generalization[END_REF] and [START_REF] Zheng | Compositional generalization via semantic tagging[END_REF]; (2) two graph-based models, LAGR [START_REF] Jambor | LAGr: Label aligned graphs for better systematic generalization in semantic parsing[END_REF] and the AM parser of [START_REF] Weißenhorn | Compositional generalization with a broadcoverage semantic parser[END_REF]; (3) LeAR [START_REF] Liu | Learning algebraic recombination for compositional generalization[END_REF], a semantic parser that relies on a more complex Tree-LSTM encoder [START_REF] Sheng | Improved semantic representations from tree-structured long short-term memory networks[END_REF]. We also report the performance of LeAR when a BiLSTM is used in the encoder instead of the Tree-LSTM.

Our baselines. We also report results for our model using the standard graph-based semantic parsing pipeline (Section 2.2), that is without the intermediary supertagging step. Note that, in this case, the supertagging loss becomes an auxiliary loss, as proposed by [START_REF] Candito | Auxiliary tasks to boost biaffine semantic dependency parsing[END_REF].

Result comparison. We observe that our approach outperforms every baseline except LEAR. Importantly, our method achieves high exact match accuracy on the structural generalization examples, although the Obj to subj PP generalization remains difficult (our approach only reaches an accuracy of 75.0% for this case).

We now consider the effect of our novel inference procedure compared to our standard graphbased pipeline. It predicts PP recursion and CP recursion generalizations perfectly, where the baseline accuracy for these cases is 0. For Obj to subj PP generalization, our best configuration reaches an accuracy of 75.0%, 5 times more than the baselines. All in all, the proposed inference strategy improves results in the three structural generalizations subsets, and brings lexical generalization cases closer to 100% accuracy.

Impact of training procedure. The early stopping approach introduced above has a clear impact A mistake occurs for 'donkey' as the theme root is predicted, instead of agent. This is probably due to the introduction of a PP before the verb, which confuses the network: PP only occur with objects during training. Using ILP fixes this mistake.

for Obj to subj PP, resulting in a 23.9 points increase (from 51.1 to 75.0). Such improvements are not observed for the baselines. From this, we conclude that our neural architecture tends to overfit the COGS training set and that some measures must be taken to mitigate this behaviour. Suppertagging accuracy. We report in Table 3 the supertagging accuracy with and without enforcing the companionship principle. We observe a sharp drop in accuracy for the Obj to Subj PP generalization when the companionship principle is not enforced. This highlights the importance of structural constraints to improve compositional generalization. We observe that the many error are due to the presence of the prepositional phrase just after the subject: this configuration causes the supertagger to wrongly assign a theme root to the subject, instead of agent. When the companionship principle is enforced, this mistake is corrected. An illustration is in Figure 5.

Conclusion

We proposed to introduce a supertagging step in a graph-based semantic parser. We analysed complexities and proposed algorithms for each step of our novel pipeline. Experimentally, our method significantly improves results for cases where compositional generalization is needed.

Limitations

One limitation of our method is that we cannot predict supertags unseen during training (e.g., combinaison of roots unseen at training time). Note however that this problem is well-known in the syntactic parsing literature, and meta-grammars could be used to overcome this limitation. Another downside of our parser is the use of an ILP solver. Although it is fast when using the COGS dataset, this may be an issue in a more realistic setting. Finally, note that our method uses a pipeline, local predictions in the first steps cannot benefit from argument identification scores to fix potential errors.

Figure 1 :

 1 Figure 1: (left) Semantic analysis of the sentence "The cat liked that Emma preferred to walk" in the COGS formalism. A * denotes definiteness of the following predicate. (right) Graph-based representation of the semantic structure. Note that we mark definiteness using an extra vertex anchored on the determiner.

Figure 2 :

 2 Figure 2: Two supertag examples from an LTAG. (left) Supertag associated with an intransitive verb. The substitution site NP↓ indicates the position of the subject. (right) Supertag associated with a transitive verb. The supplementary substitution site on the right indicates the position of the object of the verbal phrase.

Figure 3 :

 3 Figure3: Comparaison of a LTAG parsing pipeline and the proposed semantic parsing pipeline. (left) A standard LTAG parsing pipeline. We start with an input sentence, then predict one part-of-speech tag per word. This part-of-speech can be used as feature or to filter the set of possible supertags in the next step. The supertagging step chooses one supertag per word. Finally, in the last step we merge all supertags together. This operation can be synthesised as a derivation tree where arc labels indicate Gorn adresses of substitution and adjunction operations. We refer readers unfamiliar with LTAG parsing to[START_REF] Kallmeyer | Parsing Beyond Context-Free Grammars[END_REF]. (right) Our semantic parsing pipeline. We start with an input sentence, then predict at most one concept per word, where ∅ indicates no concept. The supertagging step assigns one supertag per concept instance (i.e., excluding words tagged with ∅). Finally, the argument identification step identifies arguments of predicates using the valency constraints from the supertags.

Figure 5 :

 5 Figure 5: (top) Gold semantic graph. (bottom) Supertags predicted without enforcing the companionship principle.A mistake occurs for 'donkey' as the theme root is predicted, instead of agent. This is probably due to the introduction of a PP before the verb, which confuses the network: PP only occur with objects during training. Using ILP fixes this mistake.

Table 1 :

 1 William A muffin was blessed PP dative to double dative Jane shipped the cake to John Jane shipped John the cake Agent NP to unaccusative The cobra helped a dogThe cobra frozeStructural generalizationsObj to subj PP Noah ate the cake on the plate The cake on the table burned PP recursion Ava saw the ball in the bottle Ava saw the ball in the bottle on the table on the floor CP recursion Emma said that the cat danced Emma said that Noah knew that Lucas saw that the cat danced Examples of lexical generalization and structural generalization from COGS, adapted from (Kim and Linzen, 2020, Table1). For PP and CP recursions, the number of recursions observed at test time is greater than the number of recursions observed during training.

		Training example	Generalization example
	Lexical generalizations
	Subj to obj (common) Prim to subj (proper) Active to passive	A hedgehog ate the cake Paula The crocodile blessed	The baby liked the hedgehog Paula sketched William

  . More detail are given in Appendix A. As usual in the compositional generalization literature, we

			Structural gen.		Lexical gen. Overall
	Obj to Subj PP PP recursion CP recursion
	Seq2seq models
	Kim and Linzen (2020) Conklin et al. (2021) † Akyürek et al. (2021) Zheng and Lapata (2021)	0 -0 0	0 -1 39	0 -0 12	42 -96 99	35 67 83 89
	Structured models
	LEAR (Liu et al., 2021) w/o Tree-LSTM reproduction by Weißenhorn et al. (2022) Jambor and Bahdanau (2022) † Weißenhorn et al. (2022)	--93 -59	--99 -36	--100 -100	--99 -82	97.7 80.7 99 82.3 79.6
	Our baselines: Standard graph-based parser
	Full model w/o early stopping w/o early stopping & w/o supertagging loss	11.6 12.7 9.8	0 0 0	0 0 0	97.4 97.3 97.5	84.1 84.1 84.1
	Proposed method: graph-based parser with supertagging
	Full model w/o early stopping	75.0 51.1	100 100	100 100	99.1 98.9	98.1 96.7

  Obj to Subj PP PP rec. CP rec.

	Word level accuracy
	ILP No ILP	90.2 71.6	100 99.9	100 100
	Sentence level accuracy
	ILP No ILP	75.0 9.0	100 99.6	100 100
	Table 3: Supertagging accuracy using our integer linear program (ILP) and without (i.e. simply predicting the best supertag for each word, without enforcing the com-panionship principle).

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 1089-1101 December 6-10, 2023 ©2023 Association for Computational Linguistics

Using the determiner as the head of a relation may be surprising for readers familiar with syntactic dependency parsing datasets, but there is no consensus among linguists about the appropriate dependency direction, see e.g., Müller (2016, Section 1.5) for a discussion.

We borrow the name from[START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF][START_REF] Bonfante | Supertagging with Constraints[END_REF], although our usage is slightly different.

https://www.ibm.com/products/ ilog-cplex-optimization-studio

https://github.com/alban-petit/ semantic-supertag-parser

As COGS contains 1,000 sentences for each generalization, case, this number mostly reflects the accuracy for lexical generalization, which account for 85.7% of the test set.

Acknowledgments

We thank the anonymous reviewers and metareviewer for their comments and suggestions. This work was funded by the UDOPIA doctoral program in Artifial Intelligence from Université Paris-Saclay (ANR-20-THIA-0013) and benefited from computations done on the Saclay-IA platform.

A Neural architecture

The neural architecture used in our experiments to produce the weights λ, ϕ + , ϕ -and µ is composed of:

• An embedding layer of dimension 200 followed by a bi-LSTM [START_REF] Hochreiter | Long short-term memory[END_REF] with a hidden size of 400.

• A linear projection of dimension 300 followed by a RELU activation and another linear projection of dimension |T | to produce λ.

• A linear projection of dimension 200 followed by a RELU activation and another linear projection of dimension |S + | to produce ϕ + .

• A linear projection of dimension 200 followed by a RELU activation and another linear projection of dimension |S -| to produce ϕ -.

• A linear projection of dimension 200 followed by a RELU activation and a bi-affine layer to produce µ.

We apply dropout with a probability of 0.3 over the outputs of each layer except the final layer for each weight matrix. The learning rate is 5 × 10 -4 and there are 30 sentences per mini-batch.