Johannes Jurgovsky
email: johannes.jurgovsky@uni-passau.de

Michael Granitzer
email: michael.granitzer@uni-passau.de

Christin Seifert
email: christin.seifert@uni-passau.de

Evaluating Memory Efficiency and Robustness of Word Embeddings

Keywords: natural language processing, word embedding, memory efficiency, robustness, evaluation

Skip-Gram word embeddings, estimated from large text corpora, have been shown to improve many NLP tasks through their highquality features. However, little is known about their robustness against parameter perturbations and about their efficiency in preserving word similarities under memory constraints. In this paper, we investigate three post-processing methods for word embeddings to study their robustness and memory efficiency. We employ a dimensionality-based, a parameterbased and a resolution-based method to obtain parameter-reduced embeddings and we provide a concept that connects the three approaches. We contrast these methods with the relative accuracy loss on six intrinsic evaluation tasks and compare them with regard to the memory efficiency of the reduced embeddings. The evaluation shows that low Bit-resolution embeddings offer great potential for memory savings by alleviating the risk of accuracy loss. The results indicate that post-processed word embeddings could also enhance applications on resource limited devices with valuable word features.

Introduction

Word embeddings, also referred to as "word vectors" [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF], capture syntactic and semantic properties of words solely from raw natural text corpora without human intervention or language dependent preprocessing. In natural language texts, the co-occurrence of words to appear together in the same context depends on the syntactic form and meaning of the individual words. In word embeddings the various nuances of word-to-word relations are distributed across several dimensions in vector space. These vector spaces are high-dimensional to provide enough degrees of freedom for hundreds of thousands of words to allow the relative arrangement of their embeddings reflect as many pairwise relations as possible out of the corpus statistics. However, embeddings carry a lot of information about words, which is hard to understand, interpret and quantify or may even be redundant and non-informative.

The NLP community has been successfully exploiting these embeddings over the last years, e.g. [START_REF] Collobert | Natural language processing (almost) from scratch[END_REF][START_REF] Baroni | Dont count, predict! a systematic comparison of context-counting vs. context-predicting semantic vectors[END_REF]. However, the gain in task-accuracy brings the downside that high-dimensional continuous valued word vectors require a large amount of memory. Moreover, embeddings are trained by a fixed-size network architecture that sweeps through a huge text corpus. Consequently, the total number of parameters in the embedding matrix is implicitly defined a-priori. Further, there is no natural transition to more memory efficient embeddings, by which one could trade accuracy for memory. This is particularly limiting for NLP-applications on resource limited devices where memory is still a scarce resource. An embedding matrix with 150,000 vocabulary words can easily require 60-180 Megabytes of memory, which is rather inconvenient to be transferred to and stored in a browser or mobile application. This restriction gives rise to contemplate different types of post-processing methods in order to derive robust and memory-efficient word vectors from a trained embedding matrix.

In this paper, we investigate three post-processing methods for word vectors trained with the Skip-Gram algorithm that is implemented in the Word2Vec software toolkit1 [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. The employed post-processing methods are (i) dimensionality reduction (PCA), (ii) parameter reduction (Pruning) and (iii) Bit-resolution reduction (Truncation). To isolate the effects on embeddings with different sizes, sparsity levels and resolutions, we employ intrinsic evaluation tasks based on word relatedness and abstain from extrinsic classification tasks. Our work makes the following contributions:

• We show through evaluation that Skip-Gram word embeddings are robust against linear dimensionality reduction, pruning and resolution-reduction on all tasks with only moderate loss of < 10% at a reduction of 40%. • Our experiments reveal that higher-dimensional embeddings capture a larger fraction of redundant information, which can be exploited in favor of memory savings. • We propose the resolution-based post-processing method as a means to gradually trade word vector quality for memory.

The remainder of this paper is structured as follows: First we present related work from the domain of language modeling and word representations. Next, we provide a conceptional overview of the post-processing methods used to reduce the amount of parameters in word embeddings. Then, we describe the experimental setup and the results in detail. A final discussion highlights the benefits of the different findings for practical applications.

Related Work

In computational linguistics, generating count-based language models has been an active research area since decades. The most common approach involves three parts: Collecting co-occurrence statistics of words from large text corpora, transforming (e.g. tf-idf, Point-wise Mutual Information (PMI)) the counts to derive word association scores and finally applying a dimensionality reduction method (e.g. PCA, SVD). Dimensionality reduction is used for both smoothing sparsity and reducing the overall amount of parameters in order to obtain a low-dimensional and dense embedding matrix [START_REF] Turney | From frequency to meaning: Vector space models of semantics[END_REF]. In this kind of approach, the quality of word vectors depends on the choice of methods used. In contrast, advances in recent years gave rise to new techniques [START_REF] Bengio | A neural probabilistic language model[END_REF][START_REF] Collobert | Natural language processing (almost) from scratch[END_REF][START_REF] Mnih | Three new graphical models for statistical language modelling[END_REF][START_REF] Huang | Improving word representations via global context and multiple word prototypes[END_REF], that implicitly model word co-occurrences by predicting context words from observed input words. Instead of first collecting co-occurrences of context words and then re-weighting these values with tf-idf or PMI, predictive models directly set the word vectors to optimally predict the contexts in which the corresponding words tend to appear. Since similar words appear in similar contexts, the classifier in a predictive model is trained to assign similar vectors to similar words. In an extensive evaluation, Baroni et al. [START_REF] Baroni | Dont count, predict! a systematic comparison of context-counting vs. context-predicting semantic vectors[END_REF] ascertain that embeddings of predictive models are superior to their count-based counterparts on word similarity tasks.

One particularly efficient representative of the family of predictive models is the Skip-Gram method, proposed by Mikolov et al. [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. It offers the convenient property that the output of the model is a linear function of an input word vector and a context word vector, which not only results in meaningful nearest neighbours but also in informative relative positions of pairs of word embeddings. The intriguing finding is that arithmetic operations on word vectors in embedding space accurately reflect semantic and syntactic operations on words. We chose to use these embeddings in our experiments, since they encode a variety of language related information in both local and global neighborhoods. A thorough explanation of the rationale behind this technique was given by Levy and Goldberg [START_REF] Levy | Neural word embedding as implicit matrix factorization[END_REF][START_REF] Goldberg | word2vec Explained: deriving Mikolov et al.'s negativesampling word-embedding method[END_REF].

Evaluations of word embeddings are published whenever new embedding methods are proposed. Besides manually inspecting 2D-projections of word vectors (e.g. t-SNE [START_REF] Van Der Maaten | Visualizing data using t-SNE[END_REF], PCA), it is difficult to associate meaning to individual dimensions. In language modeling, authors have traditionally employed perplexity to evaluate their models. In recent years, the common approach shifted towards testing the embeddings on various word similarity or word analogy test datasets [START_REF] Baroni | Dont count, predict! a systematic comparison of context-counting vs. context-predicting semantic vectors[END_REF][START_REF] Mikolov | Linguistic Regularities in Continuous Space Word Representations[END_REF]. In this domain, the work of Chen et al. [START_REF] Chen | The expressive power of word embeddings[END_REF] is the closest one to ours. Therein, they include a short section about information reduction capabilities of embeddings with limited experiments on other types of embeddings. We were particularly interested in preserving the linear structure in Word2Vecembeddings under limited memory conditions. So far, we are not aware of other experiments that explore ways to reduce word vectors in terms of memory.

Methodology

The word embeddings we use in our experiments, are obtained from Mikolov's Skip-Gram algorithm [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. As a recent study [START_REF] Levy | Neural word embedding as implicit matrix factorization[END_REF] revealed, the algorithm factorizes an implicit word-context matrix, whose entries are the Point-wise Mutual Information of word-context pairs shifted by a constant offset. This PMI-matrix M ∈ R |V |×|V | is factorized into a word embedding matrix W ∈ R |V |×d and a context matrix C ∈ R d×|V | , where |V | is the number of words in the vocabulary and d is the number of dimensions of each word vector. The context matrix is only required during training and usually discarded afterwards. The result of optimizing the Skip-Gram's objective is that word vectors (rows in W ) have high similarity with respect to their cosine-similarity in case the words are syntactically or semantically similar. Besides that, the word vectors are dense and have significantly fewer dimensions than there are context words -columns in M . With sufficiently large d, the PMI-matrix could be perfectly reconstructed from its factors W and C, and thus provide the most accurate information about word co-occurrences in a corpus [START_REF] Baroni | Dont count, predict! a systematic comparison of context-counting vs. context-predicting semantic vectors[END_REF]. However, increasing the dimensionality d of word vectors also increases the amount of memory required to store the embedding matrix W . When using word embeddings in an application, we do not aim for a perfect reconstruction of the PMI-matrix but for reasonably accurate word vectors that reflect word similarities and word relations of language. Therefore, a more memory-efficient, yet accurate version of W would be desirable.

Memory Reduction with Post-Processing

More formally, we want to have a mapping τ from the full embedding matrix W to Ŵ = τ (W ), where Ŵ can be stored more efficiently while at the same time its word vectors are similarly accurate as the original vectors in W . For the vectors in Ŵ to have an accuracy loss as low as possible, word vectors in W must be robust against the mapping function τ . We consider W robust against the transformation τ , if the loss of τ (W ) is small compared to W across very different evaluation tasks. A memory reduction through τ can be induced by reducing the number of dimensions, the amount of effective parameters or the parameters' Bit-resolution. Accordingly, we employed three orthogonal post-processing methods that can be categorized into dimensionality-based, parameter-based and resolution-based approaches:

• Dimensionality-based: Methods in this category can be described by the mapping τ dim : R |V |×d → R |V |× d, where d < d. Fewer dimensions directly relate to less required memory. The dimensionality-based approaches provide a transformation that projects embeddings onto a lower-dimensional subspace while preserving the dominant properties of words. Both linear (e.g. PCA) and non-linear dimensionality (e.g. multilayer Autoencoder) reduction methods are applicable, as long as the inverse τ -1 of the transformation is available. In both variants, the computational overhead for computing τ and the memory overhead for storing the inverse τ -1 have to be considered. For linear transformations there is no memory overhead since the transformation can once be applied to the embedding matrix and subsequent methods can use the transformed embeddings alike. If there is reason to assume that the word vectors lie on a nonlinear manifold, nonlinear dimensionality reduction techniques can find a mapping to the components of the potentially lowdimensional manifold. Both the computational overhead for estimating the nonlinear components and the memory overhead for storing the inverse of the mapping alongside with the transformed embeddings is high. In this work, we select one method of each category. In particular, we explore the robustness and memory efficiency of embeddings after applying PCAreduction, Pruning and Bit-Truncation. In the following section we describe the selected methods along with the rationale for the selection (see Figure 1).

Post-Processing Methods

We employ the following post-processing methods: Linear Transformation Dimensionality-based approaches assume that points are not uniformly scattered across the embedding space but exhibit certain directions of dominant variations. If there is some kind of structure in the data, it should be possible to exploit it by means of representing the same data with fewer dimensions. If the discarded dimensions only accounted for redundant information, we would obtain basis vectors that describe the word embeddings equally well but with fewer parameters. Since our evaluation tasks rely on vector arithmetic and cosine similarities, we do not use nonlinear dimensionality reduction methods as these operations would be meaningless on the transformed embeddings L produced by a nonlinear mapping. Therefore, we used the PCA-solution as a linear transformation to obtain lower dimensional embeddings.

Pruning With Pruning we refer to a parameter-based method that discards a subset of the values in the embedding matrix by setting them to zero. With λ ∈ [0, 1] we denote the Pruning level. Our naive pruning strategy is agnostic to word vectors since it determines a global threshold value p λ from the whole matrix in such a way that λ * 100% of the matrix's values are greater than the threshold. All values w ij below that threshold |w ij | < |p λ | are set to zero. As a result of the pruning operation, we obtain a sparser embedding matrix with a degree of sparsity equivalent to 1-λ. Sparse matrices can be compressed more easily and thus require less memory than dense matrices. The rationale for using Pruning as reduction strategy arose from the observation that on normalized word vectors, pruning gradually projects points onto their closest coordinate axis. As we increase the pruning level, more points have coordinates that are aligned with the coordinate axes. Due to the normalization, this alignment gradually affects some but not all dimensions of individual word vectors. We hypothesize that up to a certain pruning level, the inaccuracy induced by Pruning has no qualitative effect on word vector arithmetic and word similarity computations.

Bit-Truncation Besides a plain reduction of parameters by means of projection on fewer principle components, we explored a rather memory-focused approach that leaves the embedding dimensions untouched but migrates continuous word embeddings to discrete ones. The motivation is that in distributed embeddings the factors on all dimensions partially contribute to the meaning of a word. Thus, there should exist some degree of contribution which makes the meaning shift from one notion to another whereas for smaller contributions, the meaning is unaffected. We can exploit this relationship between the proximity of the embeddings' values and their similarities in meaning for purposes of memory efficiency by imposing resolution constraints on the value range along each coordinate. The Skip-Gram algorithm is defined on continuous valued word vectors which assumes each dimension to be real-valued. Figuratively, continuous embeddings allow for arbitrary positioning of a word's embedding in embedding space up to the precision of the datatype used. With Bit-Truncation we rasterize the embedding space uniformly by subdividing the range of values on each coordinate axis into distinct groups. Thus, all the factors of a distributed embedding still contribute to the meaning but only up to some pre-defined precision.

For the Bit-Truncation method, we adopt the approach described in [START_REF] Chen | The expressive power of word embeddings[END_REF] with slight adaptions. To reduce the resolution of the real numbers that make up the embedding matrix, first we shift the values to the positive range. Then we re-scale the values to the interval [0, 1] and multiply them by 2 B , where B is the number of Bits we want to retain. Finally we cast the values to a 32-Bit Integer datatype. After casting to Integer, each coordinate axis has a resolution of r = 2 B non-overlapping equally-spaced intervals. Consequently, the number of distinguishable regions in embedding space R = r d is exponential in the number of dimensions d.

Experimental Setup

In all experiments we used word vectors estimated with the Skip-Gram method of the word2vec-toolkit from a text corpus containing one billion words. The corpus was collected from the latest snapshot of English Wikipedia articles2 . After removing words that appeared less than 100 times, the vocabulary contained 148,958 words, both uppercase and lowercase. We used a symmetric window covering k = 9 context words and chose the negative-sampling approximation to estimate the error from neg = 20 noise words. With this setup, we computed word vectors of several sizes in the range d ∈ [50, 100, 150, 300, 500]. After training, all vectors are normalized to unit length. To evaluate the robustness and efficiency of word vectors after applying post-processing, we compare PCAreduction, Pruning and Bit-Truncation on three types of intrinsic evaluation tasks: word relatedness, word analogy and linguistic properties of words. In each of these tasks, we use two different datasets.

Word Relatedness: The WordSim353 (WS353) [START_REF] Finkelstein | Placing search in context: The concept revisited[END_REF] and MEN [START_REF] Bruni | Multimodal Distributional Semantics[END_REF] datasets are used to evaluate pairwise word relatedness. Both consist of pairs of English words, each of which has been assigned a relatedness score by human evaluators. The WordSim353 dataset contains 353 word pairs with scores averaged over judgments of at least 13 subjects. For the MEN dataset, a single annotator ranked each of the 3000 word-pairs relative to each of 50 randomly sampled word-pairs. The evaluation metric is the correlation (Spearman's ρ) between the human ratings and the cosine-similarities of word vectors.

Word Analogy: The word analogy task is more sensitive to changes of the global structure in embedding space. It is formulated as a list of questions of the form "a is to â as b is to b", where b is hidden and has to be guessed from the vocabulary. The dataset we use here was proposed by Mikolov et al. [START_REF] Mikolov | Linguistic Regularities in Continuous Space Word Representations[END_REF] and consists of 19544 questions of this kind. About half of them are morphosyntactical (wa-syn) (loud is to louder as tall is to taller ) and the other half semantic (wa-sem) questions (Cairo is to Egypt as Stockholm is to Sweden). It is assumed that the answer to a question can be retrieved by exploiting the relationship a → â and applying it to b. Since Word2Vec-embeddings exhibit a linear structure in embedding space, word relations are consistently reflected in sums and differences of their vectors. Thus, the answer to an analogy question is given by the target word w t whose embedding w t is closest to w q = âa + b with respect to the cosine-similarity. The evaluation metric is the percentage of questions that have been answered with the expected word.

Linguistic Properties: Schnabel et al. [START_REF] Schnabel | Evaluation methods for unsupervised word embeddings[END_REF] showed that results from intrinsic evaluations are not always consistent with results on extrinsic evaluations. Therefore, we include the recently proposed QVEC-evaluation 3 [START_REF] Ling | Evaluation of Word Vector Representations by Subspace Alignment[END_REF] as additional task. This evaluation uses two dictionaries of words, annotated with linguistic properties: a syntactic (QVEC-syn) dictionary (e.g., ptb.nns, ptb.dt) and a semantic (QVEC-sem) dictionary (e.g., verb.motion, noun.position). The proposed evaluation method assigns to each embedding dimension the linguistic property that has highest correlation across all mutual words. The authors showed that the sum over all correlation values can be used as an evaluation measure for word embeddings. Moreover, they showed that this score has high correlation with the accuracy the same embeddings achieve on real-world classification tasks.

Results

Since we evaluate the robustness of word embeddings against post-processing, we report the relative loss induced by applying a post-processing method. The loss is measured as the difference between the score of original embeddings and the score of post-processed embeddings. In case of the word relatedness task, the score is the Spearman correlation. On the word analogy task, the score is given as accuracy. And on the linguistic properties task, the score is the output of the QVEC evaluation method. We divide the loss by the score of the original embeddings to obtain a relative loss that is comparable across tasks.

Robustness of Word Vectors

In Figure 2 we report the mean relative loss, averaged over the five word vector sizes on all datasets. The percentage of reduction refers to the fraction of principle components with lowest eigenvalues that were discarded after applying PCA and to the fraction of parameters that were set to zero after pruning, respectively.

The word embeddings show a similar trend for all three post-processing methods. A small relative reduction results in a small loss, whereas a large reduction leads to a large loss. For all methods, the loss increases exponentially with the percentage of reduction. On the word analogy datasets, the loss is consistently higher than on the word relatedness and QVEC datasets. In particular, the relative loss on word relatedness datasets is predominantly unaffected (relative loss < 10%) by post-processing up to a reduction threshold of 40%. Compared to the naive Pruning approach, PCA-transformed embeddings suffer lower loss on all tasks. Actually, on WordSim353 and MEN, PCA-reduced embeddings exhibit slight negative loss (< 3%). Bit-Truncation produces no loss on any dataset until the Bit-resolution of the parameters is lower than 8-Bit. To summarize,

Memory Efficiency

The percentage of reduction achieved by PCA is directly proportional to memory savings induced by the smaller number of dimensions. There, the sweet spot is task-dependent and the relative reduction can be rather high before word vector quality suffers a loss. In contrast, the number of pruned values is not directly proportional to memory savings, since the coding of sparse matrices requires additional memory. For instance, the row compressed storage method [START_REF] Saad | Iterative methods for sparse linear systems[END_REF] has, without further assumptions about the shape of the matrix, a memory complexity of O(3k), where k is the number of non-zero elements in the sparse matrix. Thus, the pruning method would only start to pay off in terms of memory consumption above a pruning level of 2 3 , which would result in serious quality-loss. Finally, post-processing the embedding matrix with Bit-Truncation does not cause any loss on any of the evaluated datasets up to 75% reduction (24Bit). For resolutions below r = 2 8 , all evaluated datasets respond to the lowprecision embeddings with abruptly increasing loss. Figure 3 shows that higher-dimensional embeddings (d = 500) can be reduced more aggressively than lower-dimensional ones before reaching the same level of relative loss. Since a similar behavior holds on all tasks (not shown due to space constraints), the observation is two-fold: First, it suggests that, the higherdimensional the embedding space is, the more non-zero parameters there are and the higher their resolution is, the more redundant is the information that is captured in the embeddings. Secondly, the consistency across dimensionality-based and parameter-based methods indicates that neither the number of dimensions or parameters nor the continuous values alone but the number of distinguishable regions in embedding space is crucial for accurate word embeddings. With a sufficiently large Bit-resolution the accuracy of all embedding sizes approximates the same accuracy level as with continous values. Thus, we can confirm the finding in [START_REF] Chen | The expressive power of word embeddings[END_REF] also for Skip-Gram embeddings: The same accuracy can be achieved with discretized values at sufficiently large resolutions. Additionally, we state that this observation not only holds for cosine-similarity on word relatedness tasks but also for vector arithmetic on the word analogy task and for QVEC on the linguistic properties task. To summarize, Skip-Gram word embeddings can be stored more efficiently using a post-processing method that reduces the number of distinguishable regions R = (2 B ) d in embedding space. Pruning does so by producing increasingly large zero-valued regions around each coordinate axis (2 B -const.). PCA does so by mapping the word vectors into an embedding space with fewer dimensions d < d. And Bit-Truncation directly lowers the resolution of each coordinate by constraining the Bit-resolution B < B.

Discussion

Memory efficiency: If an application can take a loss in word vector accuracy in favor of memory or transmission times, Skip-Gram embeddings can be reduced with all three evaluated methods. Thereby, pruning is the least efficient method as the overhead introduced by sparse coding could only be compensated by pruning levels above 2 3 . Such an aggressive pruning strategy would result in an average accuracy loss of more than 30%. In contrast, the linear dimensionality reduction technique worked well on our tasks and it allows for a consistent transition from higher to lower dimensional embeddings. The accuracy of PCAreduced embeddings even improves over equivalently large original non-reduced embeddings on word relatedness and word analogy tasks (see evaluation data online4 ). Thus, in terms of memory, it can be more efficient to first train highdimensional embeddings and afterwards reduce them with PCA to the desired size. The resolution-based approach provides the greatest potential for memory savings. With only 8-Bit precision per value, there is no loss on any of the tasks. A straight-forward implementation can thus fit the whole embedding matrix in only 25% of memory. Resolution and Semantic Transition: Another observation is depicted in Table 1. On the word analogy dataset, the transition from lower to higher-precision values not only yields increasingly better average accuracy but also corresponds to a semantic transition from lower to higher relatedness. Even if the embeddings' values have only 3-Bit precision, the retrieved answer words are not totally wrong but still in some kind related to the expected answer word. It seems that some notions of meaning are encoded on a finer scale in embedding space and that these require more Bits to remain distinguishable. For coarse resolutions (3-Bit) the regions in embedding space are too large to allow an identification of a country's currency. Because there are many words within the same distance to the target location, the most frequent one is retrieved as answer to the question. As the resolution increases, regions get smaller and thus more nuanced distances between word embeddings emerge, which yields not only increasingly accurate but also progressively more related answers.

Conclusion

In this paper, we explored three methods to post-process Skip-Gram word embeddings in order to identify means to reduce the amount of memory required to store the embedding matrix. Therefore, we evaluated the robustness of embeddings against a dimensionality-based (PCA), parameter-based (Pruning) and a resolution-based (Bit-Truncation) approach. The results indicate, that embeddings are most robust against Bit-Truncation and PCA-reduction and that preserving the number of distinguishable regions in embedding space is key for obtaining memory efficient (75% reduction) and accurate word vectors. Especially resource limited devices can benefit from these compact high-quality word features to improve NLP-tasks under memory constraints.

Fig. 1 :

 1 Fig. 1: Three methods for post-processing a word embedding matrix: PCA-Reduction (top), Pruning across all Bit-planes (left) and Truncation of the least significant Bits (right).

3Fig. 2 :

 2 Fig. 2: Mean relative loss of embeddings after (a) PCA: percentage of removed dimensions, (b) Pruning: percentage of removed parameters and (c) Bit-Truncation: remaining Bits. Scores on the QVEC datasets are not shown for PCA since they are not comparable across different word vector sizes.

Fig. 3 :

 3 Fig. 3: Relative loss of embeddings on the syntactic word analogy dataset (wasyn) after PCA (a), Pruning (b) and Bit-Truncation (c).

•

  Parameter-based: Whereas dimensionality-based methods change the bases of the embedding space, parameter-based methods leave the structure untouched but directly modify individual parameter values in the embedding matrix: τ par : R |V |×d → R |V |×d , where τ par is supposed to map most values to zero and leave only few non-zero elements in the output matrix. For instance, a simple pruning strategy can be used. Then, the output of τ par is a sparse matrix that can be stored more efficiently. • Resolution-based: τ res : R |V |×d → {0, • • • , r -1} |V |×d , where r ∈ N + is the resolution of the coordinate axes. With discrete coordinates, values can be stored at lower Bit-precision. Resolution-based methods discretize the coordinate axes into distinct intervals and thus reduce the resolution of the word vectors. For instance, the Bit-Truncation method subdivides the embedding space into regions of equal size.

Table 1 :

 1 Answer words for several country-currency analogy questions from word embeddings at different resolutions. Finally, all answer words are currencies.

	Questions		Expected 3-Bit	4-Bit 5-Bit 6-Bit 7-Bit
	Europe euro : Japan	?	yen	Nagasaki Taiwan yen yen yen
	Europe euro : Korea	?	won	Kim	PRC PRC PRC dollar
	Europe euro : USA	?	dollar	Dusty proposal US euros dollar
	Europe euro : Brazil	?	real	Alegre proposal dollar euros euros
	Europe euro : Canada		? dollar	Calgary Calgary dollar dollar dollar

https://code.google.com/p/word2vec/

https://dumps.wikimedia.org/enwiki/20150112/

http://tinyurl.com/jj-ecir2016-eval

Acknowledgments. The presented work was developed within the EEXCESS project funded by the European Union Seventh Framework Programme FP7/2007-2013 under grant agreement number 600601.


K S Olsen

Franck Montmessin

A Fedorova

Alexander Trokhimovskiy

Oleg Korablev

Trace gas retrievals for the ExoMars Trace Gas Orbiter Atmospheric Chemistry Suite mid-infrared solar occultation spectrometer

Trace gas retrievals for the ExoMars Trace Gas Orbiter

Atmospheric Chemistry Suite mid-infrared solar occultation spectrometer

Mars Express Planetary Fourier Spectrometer (PFS), operates in both nadir and solar occultation mode, and will be able to measure the physical state of the atmosphere (vertical profiles of temperature, pressure and dust opacity). NOMAD is also a multi-channel spectrometer with complimentary objectives to ACS. It consists of a pair of combination echelle-AOTF spectrometers, much like SPICAM/V and ACS NIR, that operate in both nadir and solar occultation mode. In its original configuration, TGO carried a high-resolution Fourier transform spectrometer (FTS) covering a wide spectral range to detect trace gases [START_REF] Wennberg | MATMOS: the Mars atmospheric Trace Molecule Occultation Spectrometer[END_REF], supported by the nadir-viewing NOMAD instrument capable of carrying out trace gas mapping studies. The ACS MIR channel aims to reproduce the capabilities of the FTS using a novel concept for atmospheric studies: a cross-dispersion spectrometer combining an echelle grating with a wide blaze angle and secondary, steerable diffraction grating [START_REF] Korablev | The Atmospheric Chemistry Suite (ACS) of three spectrometers for the Ex-oMars 2016 Trace Gas Orbiter[END_REF]. It is capable of finer resolution than its echelle-AOTF counterparts, but is limited in its instantaneous spectral range compared to its FTS predecessor.

The ACS MIR block is thermally isolated from TIRVIM and coupled to NIR, but shares a common electronics block. It consists of an entry telescope and collimator, a large echelle grating (107×240 mm, 3.03 grooves per mm), a steerable pair of secondary grating mirrors, and a Sofradir MCT array detector The lowdensity echelle grating at a high blaze angle (63.43 • ) provides overlapping spectra at high orders. The secondary grating separates the orders and the resulting spectra are recorded by the detector with 640 pixels in the x direction corresponding to wavelength, and 512 pixels in the y direction corresponding to order. Several spectra are recorded for each order on sequential pixel rows. The secondary grating has two reflective gratings mounted side-by-side that can rotated. We will use ten secondary grating positions, each with an instantaneous spectral width of around 16 cm -1 between 2380 and 4350 cm -1 . The spectral orders and range covered by each position are given in Table .  During the acquisition of a set of solar occultation spectra, the grating position can be changed between each measurement, allowing for the retrieval of vertical profiles for several trace gases and major species at the same time. Raw spectral images will be processed by ESA at the European Space Operations Centre (ESOC), calibrated spectra will be produced by Roscosmos at the Space Research Institute (IKI), and there are two parallel trace gas retrieval operations: at IKI, based on SPICAV retrievals, and at LATMOS, presented here. All three channels of the ACS instrument, and the other TGO instruments have been switched on and checked out on several occasions between launch and orbit capture.

ACS MIR Retrievals

The LATMOS ACS MIR retrievals will be based on software prepared for the high-resolution solar occultation FTS from the original TGO configuration. We will use the GGG software suite maintained at NASA's Jet Propulsion Laboratory. GGG is derived from early versions of the Occultation Display Spectra (ODS) software developed or the ATMOS spectrometer flown on the space shuttles [START_REF] Norton | ATMOS data processing and science analysis methods[END_REF]. It is designed to be a multipurpose and robust spectral fitting suite and is currently used for the MkIV balloon FTS missions [START_REF] Toon | The JPL MkIV interferometer[END_REF] and the Total Carbon Column Observing Network (TCCON) of ground-based FTSs [START_REF] Wunch | The Total Carbon Column Observing Network[END_REF].

The main component of GGG is GFIT, which computes volume absorption coefficients for each gas in the fitting spectral range, computes a spectrum line-by-line, and fits the computed spectrum to the measured spectrum using a non-linear Levenberg-Marqhardt minimization. The state vector contains the continuum level and tilt, and volume mixing ratio (VMR) scaling factors (VSFs) for each target gas. GFIT is capable of fitting multiple gases at the same time. The VSF is a multiplicative scaling factor applied to the a priori VMR vertical profile. In principle, GFIT only modifies the magnitude, and not the shape of, the a priori VMR vertical profile. However, in solar occultation mode, the a priori can be scaled for each observed spectrum at each tangent altitude.

The computed spectrum is calculated using the HI-TRAN 2012 spectral line list [START_REF] Rothman | The HITRAN2012 molecular spectroscopic database[END_REF], with modifications provided by JPL for the TCCON collaboration. Line broadening coefficients for CO 2 need to be modified to reflect the lower pressure and colder temperatures of the Martian atmosphere, and collisional-induced broadening in 95% CO 2 atmosphere. We are implementing new broadening parameters from [START_REF] Brown | CO2-broadened water in the pure rotation and ν2 fundamental regions[END_REF] and [START_REF] Lavrentieva | Linelist of HD 16 O for study of atmosphere of terrestrial planets (Earth, Venus and Mars[END_REF]. In theory, the retrievals done with GGG are independent of the VMR a priori. For consistency, a single set of a priori VMR vertical profiles will be used. These will be refined as our knowledge of the Mars atmosphere increases. The VMRs of major interfering species, CO 2 and H 2 O, may be updated for each occultation.

Temperature and pressure are vital parameters for accurately computing absorption line depths. A first attempt at spectral fitting will be done using climatological models from the Mars Climate Database. New observations of temperature and pressure made by the Mars Reconaissance Orbiter's Mars Climate Sounder and the TIRVIM channel will be assimilated into the LMD General Circulation Model. When a more accurate assimilation is ready, the retreivals will be reprocessed using the updated a priori vertical profiles of temperature, pressure, CO 2 VMR, and H 2 O VMR.

Much work is being done to investigate the limits of the retrieval algorithm by generating synthetic spectra for different atmospheric conditions (temperature, pressure, dust loading, and trace gas abundances). To test our ability to resample the spectra, very high resolution spectra are computed first, then resampled to the realistic, non-uniform spacing of an MIR order. Noise is added to the spectra, they are resampled to a uni-form fitting grid, and spectral fitting is performed using generic a priori to see how well the trace gas VMR vertical profiles used to create the synthetic spectra are reproduced.

We will introduce the ExoMars TGO mission, the ACS instrument and summarize the results of prescience-operations instrument check-outs. The GGG software suite will be introduced, as will be the work done to adapt it for use at Mars with ACS MIR, such as modelling the ACS MIR instrument line shape. We will show our simulations of solar occultation transmission spectra, and present results of our effort to fit these spectra and retrieve vertical profiles of trace gas VMRs. To search for methane, the -8.7 • secondary grating position will be used. This spectrum represents a tangent altitude of 20 km and a peak methane abundance of 6 ppmv.

Figure 1 :

 1 Figure1: An excerpt from the ACS MIR spectral atlas showing the contribution from methane to the solar occultation transmission spectra. This spectrum shows all secondary grating positions, but the ACS MIR instrument can only record a spectrum for one position instantaneously. The dashed vertical lines show the range of each position. To search for methane, the -8.7 • secondary grating position will be used. This spectrum represents a tangent altitude of 20 km and a peak methane abundance of 6 ppmv.

Table 1 :

 1 Spectral ranges and orders of secondary grating positions.

	Grating Diffraction Minimum	Maximum
	angle	orders	wavelength wavelength
	7.5 •	205-213	2.790 µm	2.899 µm
	5.7 •	214-223	2.665 µm	2.790 µm
	3.9 •	224-235	2.529 µm	2.665 µm
	2.1 •	236-248	2.397 µm	2.529 µm
	0.3 •	249-258	2.304 µm	2.397 µm
	-3.3 •	142-149	3.984 µm	4.209 µm
	-5.1 •	150-161	3.688 µm	3.984 µm
	-6.9 •	162-174	3.414 µm	3.688 µm
	-8.7 •	175-190	3.127 µm	3.413 µm
	-10.5 •	191-208	2.857 µm	3.127 µm


Bruno Yun
email: yun@lirmm.fr

Madalina Croitoru
email: croitoru@lirmm.fr

Pierre Bisquert
email: pierre.bisquert@inra.fr

Are ranking semantics sensitive to the notion of core?

come

INTRODUCTION

Logical based argumentation instantiates abstract argumentation frameworks [START_REF] Dung | On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games[END_REF] by constructing arguments from inconsistent knowledge bases, computing attacks between them and using so-called argumentation semantics in order to select acceptable arguments and their conclusions. Several approaches for logic based argumentation exist in the literature: assumption-based argumentation frameworks (ABA) [START_REF] Bondarenko | An Assumption-Based Framework for Non-Monotonic Reasoning[END_REF], DeLP [START_REF] García | Defeasible Logic Programming: An Argumentative Approach[END_REF], deductive argumentation (where an argument is perceived as a tuple (H, C) of a set of premises H and a conclusion C) [START_REF] Besnard | Elements of Argumentation[END_REF] or ASPIC/ASPIC+ [START_REF] Modgil | The ASPIC+ framework for structured argumentation: a tutorial[END_REF]. In this paper we do not follow the argumentation semantics "a la Dung" introduced by [START_REF] Dung | On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games[END_REF] but study ranking semantics [START_REF] Besnard | A logic-based theory of deductive arguments[END_REF][START_REF] Matt | A Game-Theoretic Measure of Argument Strength for Abstract Argumentation[END_REF][START_REF] Leite | Social Abstract Argumentation[END_REF][START_REF] Cayrol | Graduality in Argumentation[END_REF][START_REF] Amgoud | Ranking-Based Semantics for Argumentation Frameworks[END_REF] that return a total order over the set of arguments in the logical argumentation framework. For instantiation, we focus on a particular subset of first order logic: existential rules. The choice of the language is motivated by the practical relevance demonstrated by many applications [START_REF] Thomazo | Mixing Materialization and Query Rewriting for Existential Rules[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF][START_REF] Zhang | Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering[END_REF] but also certain features that make it challenging for instantiating argumentation frameworks such as n-ary (as opposed to binary only) negative constraints or existential variables in the head of rules. We investigate two di↵erent notions of core in such a logically instantiated argumentation framework that will remove redundant arguments and attacks in a di↵erent manner. We then ask the following research question: "Will the manner of defining the core of a logically instantiated argumentation framework a↵ect the ⇤ Corresponding Author.

Appears in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AA-MAS 2017), S. Das, E. Durfee, K. Larson, M. Winiko↵ (eds.), May 8-12, 2017, São Paulo, Brazil. ranking output of ranking semantics? ". Our initial intuition was that the answer is "no" since the core of an argumentation framework is supposed to return an equivalent, but smaller, argumentation framework. Surprisingly, the answer is "yes". We give an example of such a change using one particular ranking semantics and show how such a behaviour is not unique. Our contribution is thus not only to uncover this unexpected behaviour but also to investigate some of its reasons. The salient points of the paper are :

• The first investigation of ranking semantics in the first order logic fragment of existential rules.

• The study of several notions of core in logical argumentation framework and the proof of their equivalences and properties.

• The first characterisation of core-induced ranking modifications of semantics satisfying postulates from [START_REF] Bonzon | A Comparative Study of Ranking-Based Semantics for Abstract Argumentation[END_REF]. The paper is organized as follows. Section 2 gives the relevant background regarding existential rules and presents the logical instantiation of an argumentation framework using this language (i.e. the structure of the arguments and the attacks). In Section 3, we recall the existing notions of core and focus on two types of core and their di↵erent properties. In Section 4, we explain the di↵erent changes that can occur to a ranking of arguments when considering the cores and conclude the paper in Section 5.

LOGIC BASED ARGUMENTATION

This section will put the basis for logical argumentation and its instantiation using existential rules. After describing the logical language used in this paper, existential rules, we give an instantiation of a logical argumentation framework (AF) that is using this language. We extend the state of the art by considering a definition of an argument that imposes minimality.

In this paper we are interested in argumentation frameworks instantiated using existential rules [START_REF] Croitoru | Introducing Preference-Based Argumentation to Inconsistent Ontological Knowledge Bases[END_REF][START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF][START_REF] Arioua | Formalizing and Studying Dialectical Explanations in Inconsistent Knowledge Bases[END_REF]. The existential rules language [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] extends plain Datalog with existential variables in the rule head and is composed of formulae built with the usual quantifiers [START_REF] Besnard | Elements of Argumentation[END_REF][START_REF] Besnard | A logic-based theory of deductive arguments[END_REF] and only two connectors: implication (!) and conjunction (^). A subset of this language, also known as Datalog ± , refers to identified decidable existential rule fragments [START_REF] Gottlob | Datalog+/-: Questions and Answers[END_REF][START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF]. The language has attracted much interest recently in the Semantic Web and Knowledge Representation community for its suitability for representing knowledge in a distributed context (such as Ontology Based Data Access applications) [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF][START_REF] Thomazo | Mixing Materialization and Query Rewriting for Existential Rules[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF][START_REF] Magka | Computing Stable Models for Nonmonotonic Existential Rules[END_REF][START_REF] Bourhis | The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules[END_REF][START_REF] Zhang | Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering[END_REF]. The language is composed of the following elements:

• A fact is an existentially closed atom (of the form p(t1, . . . , t k ) where p is a predicate of arity k and ti, i 2 [1, . . . , k] are terms, i.e. variables or constants).

• An existential rule is of the form 8 ! X , ! Y H[ ! X , ! Y ] ! 9 ! Z C[ ! Z , ! X ]
where H and C are facts or conjunctions of facts and ! X , ! Y , ! Z their respective sets of variables.

• A negative constraint is a particular kind of rule where H is a conjunction of atoms and C is ? (absurdum). It implements weak negation.

• A knowledge base K = (F , R, N ) is composed of a set of facts F , a set of rules R and a set of negative constraints N . We denote by C`⇤ R (F ) the closure of F by R (computed by all possible applications of the rules in R over F until a fixed point is reached). C`⇤ R (F ) is said to be R-consistent if no negative constraint hypothesis can be deduced from it. Otherwise C`⇤ R (F ) is R-inconsistent. When considering consistent facts, entailment implicitly considers rules application (i.e. F |= q is equivalent to C`⇤ R (F ) |= q). Let us define the notion of an argument in this logical language. For decidability reasons in the following we only consider the Datalog ± fragment. An argument is composed of a set of facts called hypothesis (or the support of the argument) and a conclusion entailed from the hypothesis. The following definition of an argument improves upon the state of the art [START_REF] Croitoru | Introducing Preference-Based Argumentation to Inconsistent Ontological Knowledge Bases[END_REF][START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] by considering hypothesis minimality and removing sequences of derivations. Definition 1. Let K = (F , R, N ) be a knowledge base. An argument a is a tuple (H, C) with H a R-consistent subset of F and C a conjunction of facts such that:

• H ✓ F and C`⇤ R (H) 6 |= ?.

• C`⇤ R (H) |= C. • @H 0 ⇢ H s.t. C`⇤ R (H 0 ) |= C.
The support H of an argument a is denoted by Supp(a) and the conclusion C by Conc(a). If X is a set of arguments, we denote by Base(X) = S a2X Supp(a).

Example 1. Let K = (F , R, N ) be a Datalog ± knowledge base with:

• F = {P ussycat(T om), Cat(T om), Mouse(Jerry), T urtle(John)}.

• R = {8x(Cat(x) ! P ussycat(x)), 8x(P ussycat(x) ! Cat(x)), 8x(Cat(x) ! Mammal(x)), 8x(Mouse(x) ! Mammal(x))}. • N = {8x, y, z(Cat(x) ^Mouse(y) ^T urtle(z) ! ?)}.
From Definition 1 we can obtain the set of all arguments A of K = (F , R, N ) (it contains 75 arguments). An example of an argument a1 2 A is a1 = ({P ussycat(T om)}, P ussycat(T om)). Another example is a18 = ({Cat(T om), Mouse(Jerry)}, Mammal(T om) ^Mammal(Jerry)).

Similar to [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] we consider here the undermine attack: an argument a attacks an argument b i↵ the conclusion of a and an element of the support of b are R-inconsistent. Please note that, due to the possibility of having more than two atoms in the hypothesis of negative constraints in the language, this attack is not symmetric [START_REF] Croitoru | Introducing Preference-Based Argumentation to Inconsistent Ontological Knowledge Bases[END_REF][START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF]. Definition 2. We say that an argument a attacks an argument b denoted by (a, b) 2 C i↵ 9 2 Supp(b) s.t. {Conc(a), } is R-inconsistent. We denote the set of attackers of an argument a by Att(a).

Example 1 (cont.). Let us consider a12 2 A such that a12 = ({T urtle(John), Mouse(Jerry)}, T urtle(John) Mouse(Jerry)). We have (a12, a1) 2 C but (a1, a12) / 2 C.

Following the proof of [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] we can easily see that the obtained argumentation framework ASK = (A, C) with A being the set of arguments and C the set of attacks defined above satisfies the rationality postulates of [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF][START_REF] Caminada | An Axiomatic Account of Formal Argumentation[END_REF]. However, its main drawback lies in the large number of the generated arguments (and corresponding attacks). As shown in Example 1, for a simple and basic knowledge base of four facts, four rules and a negative constraint we can generate 75 arguments (even when taking into account minimality). The large number of (potentially equivalent) arguments might impact on the structure of the ranking output of logical argumentation frameworks. This is why in the next section we investigate the notion of core. Our hypothesis is that considering the core will allow us to reduce the number of arguments and attacks while preserving the same logically equivalent output.

CORE EQUIVALENCES

The core is a notion introduced in [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] that enables to simplify logically instantiated argumentation frameworks without losing data. In this section we will use two notions of core initially defined in [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] and we will adapt them to the logical instantiation using existential rules of this paper. We give an example of how the two core notions yield argumentation frameworks with significantly less arguments for the same logical output and prove two new key results that extend the state of the art. First, we give the relation between the base of the two cores for existential rule instantiated argumentation frameworks. Second, we show how the two cores can be obtained from each other.

Equivalence & Core Definitions

The notion of core relies on the notion of equivalence of formulae, arguments and, subsequently, of induced argumentation frameworks. To define the notion of core we first need to define the notion of equivalence of formulae. Adapting [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] for existential rules, two facts are equivalent if the sets given by the closure 1 of each fact are equal. Similarly, we say that two sets of facts are equal if, for each fact in every set, we can find an equivalent fact in the other set. Definition 3. Let f1, f2 be two facts or conjunction of facts and F1, F2 be two sets of facts. We say that:

• f1 and f2 are equivalent (f1

⌘ f2) i↵ C`⇤ R (f1) = C`⇤ R (f2).
• F1 and F2 are equivalent

(F1 ⇠ = F2) i↵ 8f 2 F1, 9f 0 2 F2 s.t. f ⌘ f 0 and 8f 2 F2, 9f 0 2 F1 s.t. f ⌘ f 0 . F1 F2 otherwise.
Example 1 (cont.). We have that P ussycat(T om) ⌘ Cat(T om) since C`⇤ R (P ussycat(T om)) = C`⇤ R (Cat(T om)) = {Cat(T om), P ussycat(T om), Mammal(T om)}. 1 In the following we consider that the rule application is using the restricted chase that does not consider redundant new facts generated by each step of the rule application (see more details in [START_REF] Baget | Revisiting Chase Termination for Existential Rules and their Extension to Nonmonotonic Negation[END_REF]).

Using the equivalence of formulae in Definition 3 and following [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] we can now define the notion of equivalence between arguments. We will consider two equivalence relations. The first one (⇡1) considers two arguments as being equivalent if they have equal supports and equivalent conclusions. The second one (⇡2) considers two arguments as being equivalent if they have equivalent supports and equivalent conclusions. Note that if there are two arguments a and a 0 such that a ⇡1 a 0 then obviously a ⇡2 a 0 . Definition 4. [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] Let a and a 0 be two arguments. We have:

• a ⇡1 a 0 i↵ Supp(a) = Supp(a 0 ) and Conc(a) ⌘ Conc(a 0 ).

• a ⇡2 a 0 i↵ Supp(a) ⇠ = Supp(a 0 ) and Conc(a) ⌘ Conc(a 0 ).

Example 1 (cont.). Let us consider the argument a13 2

A such that a13 = ({Cat(T om)}, Cat(T om)). We have that a13 6 ⇡1 a1 but a13 ⇡2 a1.

The following result is trivially true:

Proposition 1. Let AS = (A, C) be an AF and a, a 0 2 A. If (a, a 0 ) 2 C then a 6 ⇡1 a 0 and a 6 ⇡2 a 0 .
Before we can define the notion of core, we first need to give the notions of equivalence relation, equivalence class and the set of all possible equivalence classes . Definition 5. If X is a set of elements, ⇠ an equivalence relation on X and x 2 X, then x⇠ = {x 0 2 X|x 0 ⇠ x} (we say that x⇠ is the equivalence class of an element x for equivalence relation ⇠). Finally, the set of all possible equivalence classes will be denoted by X/ ⇠ = {x⇠|x 2 X}. Note that for readability purposes, we will sometimes denote x⇠ by x whenever the equivalence relation is obvious.

We are now ready to define the notion of core of a logical argumentation framework. A core of an argumentation system AS = (A, C) is an argumentation system that can be seen as a particular subgraph AS 0 = (A 0 , C 0 ) of AS. There are three restrictions. First, A 0 must obviously be a subset of the set of arguments A. Second, for a given equivalence relation ⇡ on the arguments, there must be a unique argument in A 0 for each equivalence class. Last but not least, C 0 must be a restriction of C to the arguments of AS 0 . Definition 6. [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] Let AS = (A, C) and AS 0 = (A 0 , C 0 ) be two AFs and ⇡ an equivalence relation on arguments. AS 0 is a core of AS i↵:

• A 0 ✓ A • 8G 2 A/ ⇡, 9!a 2 A s.t. a 2 G \ A 0
for the given equivalence relation ⇡.

• C 0 = C |A 0 . We denote by Core⇡(AS) the set of all cores of an argumentation framework AS for equivalence relation ⇡.

Note that since we consider two equivalence relations for arguments we can naturally construct two sets of cores from an argumentation framework AS: Core⇡ 1 (AS) that follows the first equivalence relation and Core⇡ 2 (AS) that follows the second.

Example 1 (cont.). Let us consider the knowledge base introduced in Example 1. We are interested in what arguments are contained in two distinct notions of core using the previous definitions. Table 1 has five columns. The first three columns represents an example of 20 arguments (out of 75) that can be constructed over the knowledge base of Example 1 along with their respective supports and conclusions. The last two columns show whether the 20 arguments belong or not to two examples of cores c1 and c2. The two examples of cores have been constructed using respectively the first and the second equivalence relations: core c1 2 Core⇡ 1 (ASK) and core c2 2 Core⇡ 2 (ASK) (such that it is included in Core⇡ 2 (c1), as it can be verified in Table 1). Please note that for space reasons we did not include the full predicate names but only their abbreviations.

Name Support Conclusion c1 c2 a1 {P } P X X a2 {P } MT X X a3 {M } M X X a4 {M } MJ X X a5 {T } T X X a6 {P, M } P ^M X X a7 {P, M } MT ^M X X a8 {P, M } P ^MJ X X a9 {P, M } MT ^MJ X X a10 {P, T } P ^T X X a11 {P, T } MT ^T X X a12 {T, M} T ^M X X a13 {C} C X a14 {C} MT X a15 {C, M } C ^M X a16 {C, M } MT ^M X a17 {C, M } C ^MJ X a18 {C, M } MT ^MJ X a19 {C, T } C ^T X a20 {C, T } MT ^T X Acronym Meaning P P ussycat(T om) MT Mammal(T om) C Cat(T om) T T urtle(John) M Mouse(Jerry) MJ Mammal(Jerry)
Table 1: Some arguments constructed from the knowledge base of Example 1 and two particular cores obtained using respectively ⇡1 and ⇡2.

The next section is dedicated to properties on the two types of cores obtained from the equivalence relation ⇡1 and ⇡2.

Core equivalence properties

Let us first summarize the theoretical results of this section. In Proposition 2, we show that the attack relation of Definition 2 satisfies properties of [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] which implies equivalences between the argumentation framework and any of its cores. In Proposition 3, we show that it is not useful to employ a more restrictive equivalence relation (and therefore a more general AF) once a core has already been obtained using a less restrictive one (outputting a more constrained AF). In Proposition 4, we show that all cores constructed using ⇡2 can be constructed using specific cores of ⇡1 on which we compute a core using ⇡2. This basically means that we can bypass the core constructed with ⇡1 when we are interested by a less restrictive relation such as ⇡2. Proposition 3 and Proposition 4 combined provide an important result as it will allow us not to be concerned about the order of applying cores on the argumentation framework.

According to [START_REF] Amgoud | Equivalence in logic-based argumentation[END_REF] there are two properties that are satisfied by the attack relation. First, if two arguments have equivalent conclusions, then they attack the same arguments. Second, if two arguments have equivalent supports, then they are attacked by the same arguments. We show next that we respect both conditions in the following proposition.

Proposition 2. Given a logical AF ASK = (A, C) with A being the set of arguments defined by Definition 1 and C the set of attacks defined according to Definition 2, the set C enjoys the following properties:

1.

C1b : 8a, b, c 2 A, if Conc(a) ⌘ Conc(b) then ((a, c) 2 C , (b, c) 2 C). 2. C2b : 8a, b, c 2 A, if Supp(a) ⇠ = Supp(b) then ((c, a) 2 C , (c, b) 2 C).
Proof. Let K = (F , R, N ) a knowledge base expressed using existential rules and ASK = (A, C) the corresponding argumentation framework. Now, we consider a, b, c 2 A. A natural question one can ask at this point is whether the order of applying the cores matters. To answer this question, we provide two main results. The first proposition shows that using a more restrictive equivalence relation than the one used to compute a core does not change this core. We begin by defining the notion of less restrictive equivalence relation and follow with the proposition. Definition 7. Let ⇡ and ⇡ 0 be two equivalence relation on a set of elements X, we say that ⇡ is more restrictive than ⇡ 0 (and thus, ⇡ 0 is less restrictive than ⇡) i↵ 8x, x 0 2 X s.t.

x ⇡ x 0 ) x ⇡ 0 x 0 . Proposition 3. Let AS be an AF and ⇡, ⇡ 0 two equivalence relation such that ⇡ is more restrictive than ⇡ 0 . It holds that: 8c 0 2 Core ⇡ 0 (AS), Core⇡(c 0 ) = {c 0 }.

Proof. Suppose that we have 8a, a 0 2 A, a ⇡ a 0 ) a ⇡ 0 a 0 . Now, let us consider c 0 = (A 0 , C 0 ) 2 Core ⇡ 0 (AS) and c = (A, C) 2 Core⇡(c 0 ). We denote by X the set such that A 0 = X [ A and X \ A = ;. If X 6 = ;, it means that 9b 2 X and 9b 0 2 A s.t. b 6 ⇡ 0 b 0 and b ⇡ b 0 , contradiction. It follows that: X = ; and that c 0 is the only core of Core⇡(c 0 ). Now, we can prove the most important property of this section and namely that the set of cores of an argumentation framework AS using ⇡2 is equal to the set of cores using ⇡2 that are built on cores of AS using ⇡1.

Proposition 4. Let AS = (A, C) be an AF and ⇡1, ⇡2 be the equivalence relations defined in Definition 4. We have that:

Core⇡ 2 (AS) = S c 1 2Core⇡ 1 (AS) Core⇡ 2 (c1).
Proof. This proof will be split in two parts:

• (✓) We prove this inclusion by construction. Let c 0 = (A 0 , C 0 ) 2 Core⇡ 2 (AS), by definition, 8G 2 A/ ⇡1, we chose an unique x in G for c1. Here, if 9a 2 G \ A 0 then we choose x = a otherwise we choose a random element of G. Now that we have a specific core c1 of A for ⇡1, we repeat the process and construct c2 from c1. In the end, c2 = c 0 .

• (◆) Let c1 = (A1, C1) 2 Core⇡ 1 (AS) and c2 = (A2, C2) 2 Core⇡ 2 (c1).
We prove that c2 2 Core⇡ 2 (AS). We will proceed by proving each parts of Definition 6.

-Since c2 is a core of c1 for equivalence relation ⇡2, then A2 ✓ A1. Likewise, since c1 is a core of AS, we have A1 ✓ A. Finally, we have that A2 ✓ A.

-Let f : A1/ ⇡2! A/ ⇡2 a function that takes as input an element x of A1/ ⇡2 and returns an element x of A/ ⇡2 s.t. x \ x 6 = ;. We will show that this function is a bijection. Since c2 is a core of c1 for ⇡2, we have that 8x 2 A1/ ⇡2, 9!x 2 x \ A2. But now, since f is a bijection, we can easily conclude that 8

⇤ Injective: Suppose that 9x, ȳ 2 A1/ ⇡2 s.t. f (x) = f (ȳ) =
x 2 A/ ⇡2 , 9!x 2 x \ A2.
-The final point is obvious since it is only a restriction of attacks.

This ends the proof.

From Proposition 3 and Proposition 4, the following proposition holds: Proposition 5. Let AS = (A, C) be an AF and ⇡1, ⇡2 be the equivalence relations defined in Definition 4. We have that:

S c 2 2Core⇡ 2 (AS) Core⇡ 1 (c2) = S c 1 2Core⇡ 1 (AS) Core⇡ 2 (c1
). Proposition 5 is very important for the next section that characterises ranking changes induced by cores. This is because Proposition 5 tells us that in the case that we are only concerned by ⇡2-induced ranking changes, we can bypass the core obtained via ⇡1. (a) Representation of the core c1 of ASK using ⇡1 and displayed in Table 1. (b) Representation of the core c2 of ASK using ⇡2 and displayed in Table 1.

Figure 1: Representation of cores of ASK using di↵erent equivalence relations.

RANKINGS ON DIFFERENT CORES

Now that we have investigated the notions of core for an argumentation framework, we can study how ranking semantics behave on them. In [START_REF] Amgoud | Argumentation-based Ranking Logics[END_REF], the authors define the notion of a argumentation based ranking logic (ARL) that takes a knowledge base as input and, using ranking semantics on the instantiated argumentation graph, provides a ranking of the formulae of the knowledge base. In the following we adapt their results and provide the corresponding existential rule argumentation based ranking logic. The extension we have provided is two fold. First we consider the existential rules framework for instantiation. Second, we take into account the notion of core in the reasoning mechanism. The new process is composed of four steps:

1. First, an argumentation framework is instantiated from a knowledge base K = (F , R, N ). (See Example 1 for the knowledge base considered as example throughout the paper.)

2. Second, a core c constructed using an equivalence relation is considered. (See Table 1 for two examples of cores on the knowledge base from Example 1 considering the two equivalence relations defined in the previous section, and Figure 1 for the visual depiction of the cores as graphs.)

3. Third, the arguments of c are ranked using a ranking semantics S. (See Table 2 for the ranking of the arguments of the two cores from Figure 1 and Table 1 outputted by burden ranking semantics [START_REF] Amgoud | Ranking-Based Semantics for Argumentation Frameworks[END_REF].)

4. Finally, their conclusions are ranked following a simple principle: a formula is ranked higher than another formula if it is supported by an argument which is ranked higher than any argument supporting the second formula. (See Table 3.) Before commenting on the results of ranking on the knowl-edge base, let us first define the ARL for existential rules. The definition follows the definition of [START_REF] Amgoud | Argumentation-based Ranking Logics[END_REF] adapted for existential rules and the notion of core. Please note that the ranking on arguments resulting from a ranking semantics S on an argumentation framework AS will be denoted by S AS or simply by if there is no ambiguity. For two arguments a, b 2 A, the notation a b means that b is at least as acceptable as a. Definition 8. An existential rule ARL is a tuple L = (K, AS, c, S, K, C 0 ) with K = (F , R, N ) a knowledge base expressed using existential rules, AS the instantiated argumentation framework, c = (A 0 , C 0 ) a core of AS for a given equivalence relation, S a ranking semantics and K, C 0 defined as follows:

• 8X ✓ F, C 0 (X) = { |9a 2 A 0 \Arg(X) s.t. Conc(a) ⌘ }, i.e. C 0 (X)
is the set of equivalent facts that can be concluded by arguments of the core c constructed on subsets of X.

• 8X ✓ F, 8 , 2 C 0 (X), ( , ) 2 K(X) i↵ 9a 2 A 0 \ Arg(X) s.t. Conc(a) ⌘ and 9b 2 A 0 \ Arg(X) s.t. Conc(b) ⌘ , (a, b) 2 S((A 0 , C 0 )). K(X)
corresponds to a ranking on elements of C 0 (X) obtained via the ranking of arguments S((A 0 , C 0 )).

Let us now show by the means of an example that the ranking semantics considered (namely burden semantics) is sensitive to the notion of core and thus outputs di↵erent rankings for logically equivalent argumentation graphs.

Example 1 (cont.). Let c1 (resp. c2) be the core of ASK using equivalence relation ⇡1 (resp. ⇡2). The argumentation graph of c1 (resp. c2) is represented in Figure 1a (resp. Figure 1b). The ranking on arguments of c1 (resp. c2) computed with the burden-based semantics is given in a1, a2, a13, a14 a3, a4, a5 a6, a7, a8, a9, a10, a11, a15, a16, a17, a18, a19, a20 a12

x ? ? ? ? ? ? ? (a) Ranking on arguments of c1 using the burdenbased (and Discussion-based) semantics.

x ? ? ? a1, a2, a3, a4, a5 a6, a7, a8, a9, a10, a11, a12

x ? ? ? (b) Ranking on arguments of c2 using the burden-based (and Discussion-based) semantics. 2a (resp. Table 2b). Finally, the ranking of conclusions is computed and displayed in Table 3a (resp. Table 3b). Note that in this example, the discussion-based semantics [START_REF] Amgoud | Ranking-Based Semantics for Argumentation Frameworks[END_REF] gives the same ranking.

This example shows that, surprisingly, a core does not always have the same ranking as the original argumentation framework (since c1 and c2 have di↵erent rankings). For instance, a1 is ranked higher than a3 for c1 (Table 2a) but a1 is ranked equal to a3 for c2 (Table 2b). This change in the ranking of arguments is significant as it impacts the ranking of their conclusions. Hence, the atom Cat(T om) which was ranked higher than Mouse(Jerry) and T urtle(John) (Table 3a) is now ranked equal to them (Table 3b). This is caused by the existence of equivalences (Cat(T om) and P ussycat(T om)) in the knowledge base. In fact, these equivalences generate redundant attacks between arguments that decrease the ranking of other arguments. That is why, by deleting redundancy in cores, we can observe that the ranking of some arguments is modified.

Hence, the chosen equivalence relation also plays a role in the ranking (as we have di↵erent rankings for the two cores). The next subsection investigates the reasons for such a behaviour.

Characterising ranking changes

In the rest of this section, we consider an argumentation framework and one of its cores constructed either using ⇡1 or ⇡2. We give a necessary and su cient condition for obtaining a equal (w.r.t. the set of arguments) ⇡1 and ⇡2-induced core from its original argumentation framework. Then, for those argumentation framework where the induced core is di↵erent, we provide su cient conditions for characterising the di↵erence between the ranking of the core and the one of its original argumentation framework. More precisely, we show that:

1. We provide a su cient condition for arguments that have their rank increased in the induced core. The new ranking of these arguments is further characterised by a su cient condition on their respective positions. This is done via the CP postulate characterisation.

2. We provide a su cient condition for arguments that do not change their rank in the induced core. This is done via the NaE postulate characterisation.

3. Last, we provide a su cient condition for arguments that have their rank decreased. This is done via the CP and SCT postulates characterisation.

Identity of induced core. We begin by introducing the notation needed for the rest of this section.

Definition 9. Let us consider an AF AS = (A, C) and one of its core c 0 = (A 0 , C 0 ) for an equivalence relation, we will denote by X c 0 (or simply X if the core is obvious) the set of arguments that have been deleted, namely A = A 0 [ X, X \ A 0 = ; and C 0 = C |A 0 . If X 6 = ; then the core is said to be di↵erent than the argumentation framework, otherwise it is no di↵erent.

The next proposition gives a necessary and su cient condition for all core using ⇡1 of an AF AS to be no di↵erent than the AS. Proposition 6. Let K = (F , R, N ) be a knowledge base and ASK the corresponding AF. We have that Core⇡

1 (ASK) = {ASK} i↵ for all R-inconsistent subset Y of F , @y1, y2, C`⇤ R (Y ) |= y1, C`⇤ R (Y ) |= y2, y1 6 = y2 and y1 ⌘ y2.
Proof. We divide this proof in two parts: • ()) We show that contrapositive of this implication is true by reductio ad absurdum. Suppose that there

is a R-inconsistent subset Y of F , 9y1, y2, C`⇤ R (Y ) |= y1, C`⇤ R (Y ) |= y2, y1 6 = y2, y1 ⌘ y2 and Core⇡ 1 (ASK) = {ASK}. Let us consider Y 00 ✓ Y s.t. @Y 0 ⇢ Y 0 and C`⇤ R |= y1.
We have that a = (Y 00 , y1) and b = (Y 00 , y2) are two arguments of ASK. Furthermore, we have that a ⇡1 b meaning that ASK / 2 Core⇡ 1 (ASK), contradiction.

• (() We show that this implication is true by reductio ad absurdum. Suppose that Core⇡ 1 (ASK) 6 = {ASK}. It means that 9c1 = (A1, C1) 2 Core⇡ 1 (ASK) with X 6 = ;. Therefore, it exists an argument x 2 X s.t.

x 2 A and x / 2 A1. We deduce that 9x 0 2 A1 s.t. Conc(x) ⌘ Conc(x 0 ), Supp(x) = Supp(x 0 ). By definition of an argument, we have that C`⇤ R (Supp(x)) |= Conc(x) and C`⇤ R (Supp(x 0 )) |= Conc(x 0 ), contradiction.

This ends the proof.

Similarly, we show a necessary and su cient condition for all core using ⇡2 of an AF AS to be no di↵erent than the AS. Proposition 7. Let K = (F , R, N ) be a knowledge base and ASK the corresponding AF. We have Core⇡ 2 (ASK) = {ASK} i↵ @f1, f2 2 F s.t. f1 ⌘ f2, f1 6 = f2 and for all R-

consistent subset Y ✓ F, @y1, y2, C`⇤ R (Y ) |= y1, C`⇤ R (Y ) |= y2, y1 6 = y2 and y1 ⌘ y2.
Proof. We divide this proof in two parts: • ()) We show that contrapositive of this implication is true by reductio ad absurdum in the same fashion as the proof of Proposition ), Supp(x) ⇠ = Supp(x 0 ). We can consider two cases which both lead to contradictions:

-If Supp(x) 6 = Supp(x 0 ), there exists a 2 Supp(x) and a / 2 Supp(x 0 ) (resp. a / 2 Supp(x) and a 2 Supp(x 0 )). Since we have Supp(x) ⇠ = Supp(x 0 ), there exists a 0 2 Supp(x 0 ) (resp. a 0 2 Supp(x)) s.t. a ⌘ a 0 , contradiction.

-If Supp(x) = Supp(x 0 ), then since C`⇤ R (Supp(x)) |= Conc(x) and C`⇤ R (Supp(x 0 )) |= Conc(x 0 ), contradiction This ends the proof.

Rank increase. From now on, we consider an argumentation framework AS = (A, C) and c 0 = (A 0 , C 0 ) one of its core for equivalence relation ⇡1 or ⇡2. An interesting property is that for each attack that comes from a argument removed by the core and reaches an argument of the core, we can find an attack that comes from an argument of the core and reaches the same argument. 2 X} of attacks that come from an argument of X and attack an argument of A 0 . Then, the set E 0 = {W ✓ C and W maximal |8(wi, wj), (w k , w l ) 2 W, wi ⇡ w k , wj = w l , wi, w k 2 X and wj, w l / 2 X} is a partition of E. The function f : C 0 ! E 0 that associates to each attack (a 0 , b 0 ) 2 C 0 a set of attacks W 2 E 0 with 8(wi, wj) 2 W, wi ⇡ a 0 and wj = b 0 is surjective.

Proof. Let us consider W 2 E 0 and an element (wi, wj) 2 W . Then since c 0 is a core of AS for ⇡1 (resp. ⇡2), we have that 9!z 2 wi⇡ 2 \ A 0 (resp. wi⇡ 1 \ A 0 ). Furthermore, using Proposition 2, we get that (z, wj) 2 C 0 . This proposition means that the modification of the ranking is induced mainly by a quantitative loss. We now introduce the notion of graph isomorphism which will be used to clone our argumentation frameworks. Definition 10. Let G1, G2 be two oriented graphs such that V (G1) denotes the set of vertices of G1 and E(G1) the set of its arcs. We say that : V (G1) ! V (G2) is an isomorphism i↵ 8(x, y) 2 E(G1), ( (x), (y)) 2 E(G2). For simplicity purposes and with a slight abuse, we will also write G2 = (G1).

Using the previous Proposition 8, we can have a better understanding as to why some arguments have better ranking in a core than in AS with some ranking semantics. This is because arguments of c 0 that have equivalent arguments in X (for ⇡2 or ⇡1) have their attacks amplified by those arguments. Of course, depending of the ranking semantics, having more attackers does not always mean that the ranking of the argument is worst. This concept corresponds to the CP postulate defined in [START_REF] Bonzon | A Comparative Study of Ranking-Based Semantics for Abstract Argumentation[END_REF]. AS a and a 6 S AS b. Note that the burden-based semantics [START_REF] Amgoud | Ranking-Based Semantics for Argumentation Frameworks[END_REF] and the discussionbased semantics [START_REF] Amgoud | Ranking-Based Semantics for Argumentation Frameworks[END_REF] both satisfy the CP postulate.

We are now interested in the impact of arguments removed by a core on other arguments still inside this core. Definition 12. Let AS be an AF and c 0 one of its core. We denote by J c 0 (or J if the core is obvious) the set of arguments of the core that have at least one attacker that belongs to X. More precisely, J = {a 2 A 0 |9(e, a) 2 C 0 and f ((e, a)) 6 = ;}. The next proposition states that every argument of the core that is attacked by an argument of X is ranked better in the core. Proposition 9. Let AS be an AF, c 0 a core of AS for ⇡1 or ⇡2, an isomorphism s.t. AS 0 = AS [ (c 0 ), S a ranking that satisfies CP and S AS 0 the ranking obtained on AS 0 using S. We have that 8b 2 J, b S In Proposition 9, we showed that some arguments of the core may be ranked higher. We now proceed further in this direction by introducing a su cient condition for characterising the ranking of such arguments. Unchanged rank. We now give a su cient condition for an argument to keep the same rank. The basic notion behind this is that arguments that are not attacked by others do not undergo a change in their rank. This is true if the NaE postulate is satisfied, namely if all the non-attacked argument have the same rank. Proof. We know that the core c 0 has fewer arguments and attacks than AS. Thus, the argument a is not attacked either in c 0 or (c 0 ). Furthermore, since S satisfies NaE, (a) and a are equivalent.

Rank decrease. In the next proposition, we introduce a su cient condition for an argument of the core to have its rank decreased. This condition is true only if the semantics used for the ranking satisfies the CP and SCT postulates.

The SCT postulate basically says that if the attackers of an argument b are at least as numerous and acceptable as those of an argument a and either the attackers of b are strictly more numerous or acceptable than those of a, then a is strictly more acceptable than b.

Definition 14. [START_REF] Bonzon | A Comparative Study of Ranking-Based Semantics for Abstract Argumentation[END_REF] Let AS = (A, C) be an AF and S a ranking semantics. S is said to satisfy SCT i↵ 8a, b 2 A s.t. there is an injective mapping g from Att(a) to Att(b) with 8a 0 2 Att(a), a 0 S AS g(a 0 ) and (|Att(a)| < |Att(b)| or 9a 0 2 Att(a), a 0 S AS g(a 0 ), g(a 0 ) 6 S AS a 0 ) then b S AS a and a 6 S AS b.

Note that the burden-based semantics, discussion-based semantics, the Categoriser and the ranking-based semantics SAF satisfy the SCT postulate.

The idea behind the next proposition is that if an argument has all of its attackers increase in rank, then its rank is obviously reduced. AS 0 b (using Proposition 9). Finally, using the SCT postulate, we conclude that (a) S AS 0 a and a 6 S AS 0 (a).

DISCUSSION

Classically, logical argumentation allows for a more practical and application-oriented use of argumentation theory. However, one usual caveat of such a framework is the appearance of a large number of redundant arguments. In this paper, we used the notion of core to reduce the size of argumentation graphs, and study whether this simplification has an impact on the total order over the set of arguments outputted by a particular class of ranking semantics.

More precisely, we first gave two notions of core based on equivalence and/or equality of arguments' supports and conclusions in the context of the existential rules fragment. We provided theoretical results extending the state of the art regarding core equivalence in the context of logical argumentation framework. We then studied how ranking semantics behaved w.r.t. notions of core and we showed that, depending on the used notion of core, the obtained argument ranking can be di↵erent. Finally, in light of this result, we introduced the notion of core-induced modification and gave a characterisation for semantics satisfying several postulates.

Our contribution is the first approach that formally study the impact of the notion of core on ranking semantics. As such, several avenues are contemplated. In particular, while we showed that depending of the core, the obtained rankings can be di↵erent, we envision to study the e↵ect of ranking semantics on cores coming from new and existing equivalence relations in the literature. While our results concern ranking semantics satisfying the CP, N aE and SCT postulates, it would be interesting to see how other semantics such as the Categoriser [START_REF] Besnard | A logic-based theory of deductive arguments[END_REF] and the Social Abstract Argumentation [START_REF] Leite | Social Abstract Argumentation[END_REF] impact our work therefore widening its scope.

Finally, while we provided some clues as to why some arguments may have a better core-induced ranking, this issue needs to be detailed (w.r.t. necessary conditions as well) since our work focuses on a more graph-structural characterisation.

1 .

 1 Suppose that Conc(a) ⌘ Conc(b). If (a, c) 2 C, it means that 9 2 Supp(c) such that there is a negative constraint N 2 N with C`⇤ R ({Conc(a), }) |= HN , where HN denotes the existential closure of the hypothesis of N . However, since Conc(a) ⌘ Conc(b), we can infer that C`⇤ R (Conc(a)) = C`⇤ R (Conc(b)), thus C`⇤ R ({Conc(b), }) |= HN and (b, c) 2 C. Likewise, ((b, c) 2 C ) (a, c) 2 C) which ends the proof. 2. Suppose now that Supp(a) ⇠ = Supp(b). If (c, a) 2 C, it means that 9 2 Supp(a) such that there is a negative constraint N 2 N with C`⇤ R ({Conc(c), }) |= HN . However, since Supp(a) ⇠ = Supp(b), by definition, we have that 9 0 2 Supp(b) s.t. 0 ⌘ , i.e. C`⇤ R ( 0 ) = C`⇤ R ( ). Therefore, we can infer that C`⇤ R ({Conc(c), 0 }) |= HN and (c, b) 2 C. Likewise, ((c, b) 2 C ) (c, a) 2 C) which ends the proof.

Proposition 8 .

 8 Let us consider the set E = {(a, b) 2 C|a 2 X and b /

Figure 2 :

 2 Figure 2: Representation of an argumentation framework AS = (A, C) and one of its core c 0 = (A 0 , C 0 ).

Definition 11 .

 11 [START_REF] Bonzon | A Comparative Study of Ranking-Based Semantics for Abstract Argumentation[END_REF] Let AS = (A, C) be an AF, S a semantics and S AS the ranking obtained after applying S on AS. S is said to satisfy CP i↵ 8a, b 2 A, |Att(a)| < |Att(b)| ) b S

Example 2 .

 2 Let AS = (A, C) be an AF and c 0 = (A 0 , C 0 ) a core of AS for an equivalence relation. In this example depicted in Figure 2, we have A = {a, b, c, d, e, i, g, h} and C = {(i, a), (g, a), (c, b), (d, b), (e, b), (h, b)}. Suppose that ī = {i, g} and c = {c, d, e}. The core c 0 is such that A 0 = {a, i, c, b, h}. In this case, J = {a, b}.

  AS 0 (b) and (b) 6 S AS 0 b. Proof. Let (a, b) be an attack of c 0 such that f ((a, b)) 6 = ;. It means that there exists an argument a 0 2 X such that (a 0 , b) 2 C. We thus have |Att( (b))| < |Att(b)| and since S satisfies CP , b S AS 0 (b) and (b) 6 S AS 0 b.

Proposition 10 .

 10 Let a, b 2 J, if S satisfies CP and Att(a) P e2Att(a)\C 0 |f ((e, a))| < Att(b) P e2Att(b)\C 0 |f ((e, b))| then (b) S AS 0 (a) and (a) 6 S AS 0 (b). Proof. We have that for all arguments a in A 0 , Att(a) P e2Att(a)\C 0 |f ((e, a))| = |Att(a) \ A 0 |. Thus, we can say that if |Att(a) \ A 0 | < |Att(b) \ A 0 | then |Att( (a))| < |Att( (b))|. Since S is a semantics that satisfy CP , (b) S AS 0 (a) and (a) 6 S AS 0 (b). Example 2 (cont.). We have that f ((i, a)) = {(g, a)}, f ((c, b)) = {(d, b), (e, b)} and f ((h, b)) = ;. Thus, we can compute that Att(a) P e2Att(a)\C 0 |f ((e, a))| = 2 1 = 1 and Att(b) P e2Att(b)\C 0 |f ((e, b))| = 4 2 = 2. We conclude that under a semantics S satisfying CP , b S c 0 a and a S c 0 b.

Definition 13 .

 13 [START_REF] Bonzon | A Comparative Study of Ranking-Based Semantics for Abstract Argumentation[END_REF] Let AS = (A, C) be an argumentation framework and S a ranking semantics. S is said to satisfy the NaE postulate i↵ 8a, b 2 A s.t. Att(a) = Att(b) = ;, we have a S AS b and b S AS a. Note that the burden-based semantics, discussion-based semantics, the Categoriser [8], the ranking-based semantics SAF [21], the Tuples [15] and the Matt & Toni semantics [23] satisfy the NaE postulate. Proposition 11. Let AS = (A, C) be an AF, a be an argument of A s.t. Att(a) = ;, c 0 = (A 0 , C 0 ) a core of AS s.t. a 2 A 0 and an isomorphism s.t. AS 0 = AS [ (c 0 ). If S is a semantics that satisfies NaE then a S AS 0 (a) and (a) S AS 0 a.

Proposition 12 .

 12 Let AS = (A, C) be an AF, c 0 = (A 0 , C 0 ) a core of AS, a / 2 J an argument of A 0 and AS 0 = AS [ (c 0 ). If S is a semantics that satisfies CP and SCT and Att(a) ✓ J then (a) S AS 0 a and a 6 S AS 0 (a). Proof. Since a / 2 J, we have that Att( (a)) = { (a 0 )|a 0 2 Att(a)} and thus |Att(a)| = |Att( (a))|. Now, since Att(a) ✓ J, we have that 8b 2 Att(b), b S AS 0 (b) and (b) 6 S

Table x

 x

	?
	?
	?
	?
	?
	?
	?

Table 2 :

 2 Ranking on arguments induced by di↵erent cores of ASK.

	x ?	P, MT , C	x ?
	? ?	M, MJ , T	? ?	x ?	P, MT , M, MJ , T	x ?
	? ? ? ? ? ? (a) Ranking on conclusions using the ranking on arguments P ^M, MT ^M, P ^MJ , MT ^MJ , P ^T, MT ^T, C ^M, C ^MJ , C ^T T ? ? ? ? ? ? ^M	? ? ? ? (b) Ranking on conclusions using the ranking on ? ? P ^M, MT ^M, P ^MJ , MT ^MJ , P ^T, MT ^T, T ? ? ^M arguments of Table 2b.
	of Table 2a.

Table 3 :

 3 Ranking on conclusions induced by di↵erent cores of ASK.

  6. Indeed, following the same reasoning, we can deduce that there exists two arguments a, b 2 ASK s.t. a ⇡1 b and thus a ⇡2 b. It means that ASK / 2 Core⇡ 2 (ASK), contradiction. • (() We show that this implication is true by reductio ad absurdum. Suppose that Core⇡ 2 (ASK) 6 = {ASK}. It means that 9c2 = (A2, C2) 2 Core⇡ 2 (ASK) with X 6 = ;. Therefore, it exists an argument x 2 X s.t. x 2 A and x / 2 A2. It means that 9x 0 2 A2 s.t. Conc(x) ⌘ Conc(x 0