-
Structural generalization in COGS: Supertagging is (almost) all you need
Authors:
Alban Petit,
Caio Corro,
François Yvon
Abstract:
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 a…
▽ More
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.
△ Less
Submitted 21 October, 2023;
originally announced October 2023.
-
Overcoming the compression limit of the individualsequence (zero order empirical entropy) using the Set Shaping Theory
Authors:
Aida Koch,
Alix Petit,
Christian Schmidt,
Adrain Vdberg,
Logan Lewis
Abstract:
Given the importance of the claim, we want to start by exposing the following consideration: this claim comes out more than a year after the article "Practical applications of Set Shaping Theory in Huffman coding" which reports the program that carried out an experiment of data compression in which the coding limit NH0(S) of a single sequence was questioned. We waited so long because, before makin…
▽ More
Given the importance of the claim, we want to start by exposing the following consideration: this claim comes out more than a year after the article "Practical applications of Set Shaping Theory in Huffman coding" which reports the program that carried out an experiment of data compression in which the coding limit NH0(S) of a single sequence was questioned. We waited so long because, before making a claim of this type, we wanted to be sure of the consistency of the result. All this time the program has always been public; anyone could download it, modify it and independently obtain the reported results. In this period there have been many information theory experts who have tested the program and agreed to help us, we thank these people for the time dedicated to us and their precious advice. Given a sequence S of random variables i.i.d. with symbols belonging to an alphabet A; the parameter NH0(S) (the zero-order empirical entropy multiplied by the length of the sequence) is considered the average coding limit of the symbols of the sequence S through a uniquely decipherable and instantaneous code. Our experiment that calls into question this limit is the following: a sequence S is generated in a random and uniform way, the value NH0(S) is calculated, the sequence S is transformed into a new sequence f(S), longer but with the symbols belonging to the same alphabet, finally we code f(S) using Huffman coding. By generating a statistically significant number of sequences we obtain that the average value of the length of the encoded sequence f(S) is less than the average value of NH0(S). In this way, a result is obtained which is incompatible with the meaning given to NH0(S).
△ Less
Submitted 1 January, 2024; v1 submitted 19 October, 2023;
originally announced October 2023.
-
Reviewed of the compression limit of an individual sequence using the Set Shaping Theory
Authors:
Aida Koch,
Alix Petit
Abstract:
Abstract: In this article, we will analyze in detail the coding limit of an individual sequence by introducing the latest developments brought by the Set Shaping Theory. This new theory made us realize that there is a huge difference between source entropy and zero order empirical entropy. Understanding the differences between these two variables allows us to take an important step forward in the…
▽ More
Abstract: In this article, we will analyze in detail the coding limit of an individual sequence by introducing the latest developments brought by the Set Shaping Theory. This new theory made us realize that there is a huge difference between source entropy and zero order empirical entropy. Understanding the differences between these two variables allows us to take an important step forward in the study of the compression limit of an individual sequence, which we know is not calculable.
△ Less
Submitted 8 May, 2023;
originally announced May 2023.
-
On graph-based reentrancy-free semantic parsing
Authors:
Alban Petit,
Caio Corro
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…
▽ More
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.
△ Less
Submitted 15 February, 2023;
originally announced February 2023.
-
Practical applications of Set Shaping Theory in Huffman coding
Authors:
Christian Schmidt,
Adrian Vdberg,
Alix Petit
Abstract:
One of the biggest criticisms of the Set Shaping Theory is the lack of a practical application. This is due to the difficulty of its application. In fact, to apply this technique from an experimental point of view we must use a table that defines the correspondences between two sets. However, this approach is not usable in practice, because the table has A^N elements, with A number of symbols and…
▽ More
One of the biggest criticisms of the Set Shaping Theory is the lack of a practical application. This is due to the difficulty of its application. In fact, to apply this technique from an experimental point of view we must use a table that defines the correspondences between two sets. However, this approach is not usable in practice, because the table has A^N elements, with A number of symbols and N length of the message to be encoded. Consequently, these tables can be implemented in a program only when A and N have a low value. Unfortunately, in these cases, there are no compression algorithms with such efficiency as to detect the improvement introduced by this method. In this article, we use a function capable of performing the transform without using the correspondence table; this allows us to apply this theory to a wide range of values of A and N. The results obtained confirm the theoretical predictions.
△ Less
Submitted 27 August, 2022;
originally announced August 2022.
-
Preventing posterior collapse in variational autoencoders for text generation via decoder regularization
Authors:
Alban Petit,
Caio Corro
Abstract:
Variational autoencoders trained to minimize the reconstruction error are sensitive to the posterior collapse problem, that is the proposal posterior distribution is always equal to the prior. We propose a novel regularization method based on fraternal dropout to prevent posterior collapse. We evaluate our approach using several metrics and observe improvements in all the tested configurations.
Variational autoencoders trained to minimize the reconstruction error are sensitive to the posterior collapse problem, that is the proposal posterior distribution is always equal to the prior. We propose a novel regularization method based on fraternal dropout to prevent posterior collapse. We evaluate our approach using several metrics and observe improvements in all the tested configurations.
△ Less
Submitted 28 October, 2021;
originally announced October 2021.
-
Patch-based field-of-view matching in multi-modal images for electroporation-based ablations
Authors:
Luc Lafitte,
Rémi Giraud,
Cornel Zachiu,
Mario Ries,
Olivier Sutter,
Antoine Petit,
Olivier Seror,
Clair Poignard,
Baudouin Denis de Senneville
Abstract:
Various multi-modal imaging sensors are currently involved at different steps of an interventional therapeutic work-flow. Cone beam computed tomography (CBCT), computed tomography (CT) or Magnetic Resonance (MR) images thereby provides complementary functional and/or structural information of the targeted region and organs at risk. Merging this information relies on a correct spatial alignment of…
▽ More
Various multi-modal imaging sensors are currently involved at different steps of an interventional therapeutic work-flow. Cone beam computed tomography (CBCT), computed tomography (CT) or Magnetic Resonance (MR) images thereby provides complementary functional and/or structural information of the targeted region and organs at risk. Merging this information relies on a correct spatial alignment of the observed anatomy between the acquired images. This can be achieved by the means of multi-modal deformable image registration (DIR), demonstrated to be capable of estimating dense and elastic deformations between images acquired by multiple imaging devices. However, due to the typically different field-of-view (FOV) sampled across the various imaging modalities, such algorithms may severely fail in finding a satisfactory solution.
In the current study we propose a new fast method to align the FOV in multi-modal 3D medical images. To this end, a patch-based approach is introduced and combined with a state-of-the-art multi-modal image similarity metric in order to cope with multi-modal medical images. The occurrence of estimated patch shifts is computed for each spatial direction and the shift value with maximum occurrence is selected and used to adjust the image field-of-view.
We show that a regional registration approach using voxel patches provides a good structural compromise between the voxel-wise and "global shifts" approaches. The method was thereby beneficial for CT to CBCT and MRI to CBCT registration tasks, especially when highly different image FOVs are involved. Besides, the benefit of the method for CT to CBCT and MRI to CBCT image registration is analyzed, including the impact of artifacts generated by percutaneous needle insertions. Additionally, the computational needs are demonstrated to be compatible with clinical constraints in the practical case of on-line procedures.
△ Less
Submitted 9 November, 2020;
originally announced November 2020.
