Vincent Claveau
email: vincent.claveau@irisa.fr

Ewa Kijak
email: ewa.kijak@irisa.fr

Olivier Ferret
email: olivier.ferret@cea.fr

Improving distributional thesauri by exploring the graph of neighbors

In this paper, we address the issue of building and improving a distributional thesaurus. We first show that existing tools from the information retrieval domain can be directly used in order to build a thesaurus with state-of-the-art performance. Secondly, we focus more specifically on improving the obtained thesaurus, seen as a graph of k-nearest neighbors. By exploiting information about the neighborhood contained in this graph, we propose several contributions. 1) We show how the lists of neighbors can be globally improved by examining the reciprocity of the neighboring relation, that is, the fact that a word can be close of another and vice-versa. 2) We also propose a method to associate a confidence score to any lists of nearest neighbors (i.e. any entry of the thesaurus). 3) Last, we demonstrate how these confidence scores can be used to reorder the closest neighbors of a word. These different contributions are validated through experiments and offer significant improvement over the state-of-the-art.

Introduction

Distributional thesauri are useful for many NLP tasks and their construction is an issue widely discussed for several years [START_REF] Grefenstette | Explorations in automatic thesaurus discovery[END_REF]. However this is still a very active research field, maintained by the increasingly large number of available corpus and by many applications. These thesauri associate each of their entry with a list of words that are desired semantically close to the entry. This notion of proximity varies (synonymy, other paradigmatic relations, syntagmatic relations [START_REF] Budanitsky | Evaluating WordNet-based measures of lexical semantic relatedness[END_REF][START_REF] Adam | Évaluer et améliorer une ressource distributionnelle : protocole d'annotation de liens sémantiques en contexte[END_REF], for a discussion)), but the methods used for the automatic construction of thesauri are often shared. For the most part, these methods rely on the distributional hypothesis of [START_REF] Firth | Studies in Linguistic Analysis, chapter A synopsis of linguistic theory 1930-1955[END_REF]: each word is characterized by the set of contexts in which it appears, and the semantic proximity of two words can be inferred from the proximity of their contexts. This hypothesis has been implemented in different ways, and several propositions to improve the results have been explored (see next section for a state of the art).

The work presented in this article are part of this framework. We propose several contributions on the creation of these distributional thesauri and their improvement. We first show that models from information retrieval (IR) can provide information on semantic relationships, and are thus adapted to the task of creating these thesauri. In addition, they offer very competitive results compared to the state of the art, while enjoying existing tools (Section 3).

The most important part of our work then focuses on the exploitation of such semantic neighborhood relations. The IR models indeed provide lists ordering all words by decreasing similarity, that form a graph of nearest neighbors. We propose to take advantage of some of the neighborhood information contained in this graph and we derive three contributions. 1) We globally improve neighbor lists by taking into account the reciprocity of the neighborhood relationship, that is to say the fact that a word is a close neighbor of another and vice versa (Section 4).

2) We also propose a method that associates each neighbor list (i.e. each entry of the thesaurus built) with a confidence score (Section 5). This method uses the nearest neighbor graph to estimate the probabilities that a given word is the i-th neighbor of another word.

3) Finally, on the basis of this work, we show how to use this confidence score and these probabilities to reorder the list of nearest neighbors (Section 6). To achieve this goal, we model the reranking as an optimization problem of assignments, solved by the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF].

Related work

The notion of distributional thesaurus, as it was initially defined by [START_REF] Grefenstette | Explorations in automatic thesaurus discovery[END_REF], followed by Lin (1998a) and [START_REF] Curran | Improvements in automatic thesaurus extraction[END_REF], is not often considered specifically, probably because of its strong link with the notion of semantic similarity. As a consequence, the improvement of distributional thesauri has been first a side effect of the improvement of the distributional similarity measures used for their building and more precisely, of the distributional data they rely on. Both the nature of the constituents of distributional contexts and their weighting have been considered in this regard. Concerning their weighting, [START_REF] Broda | Rank-Based Transformation in Measuring Semantic Relatedness[END_REF] proposed to turn the weights of context constituents into ranks to make them less dependent on a specific weighting function while [START_REF] Zhitomirsky | Bootstrapping Distributional Feature Vector Quality[END_REF], extended by Yamamoto and Asakura (2010), defined a bootstrapping method for modifying the weights of constituents in the distributional context of a word according to the similarity with its semantic neighbors.

The nature of distributional contexts has been first considered through the distinction between windowbased and syntactic co-occurrents [START_REF] Grefenstette | Explorations in automatic thesaurus discovery[END_REF][START_REF] Curran | Improvements in automatic thesaurus extraction[END_REF]. However, most of the work related to this issue has focused on the fact that the "traditional" representation of distributional contexts is very sparse and redundant, as illustrated by [START_REF] Hagiwara | Selection of effective contextual information for automatic synonym acquisition[END_REF]. Hence, several methods for dimension reduction were tested in this context: from Latent Semantic Analysis [START_REF] Landauer | A solution to Plato's problem: the latent semantic analysis theory of acquisition, induction, and representation of knowledge[END_REF], extended for syntactic co-occurrents [START_REF] Padó | Dependency-based construction of semantic space models[END_REF], to Random Indexing [START_REF] Sahlgren | Vector-based semantic analysis: Representing word meanings based on random labels[END_REF], Non-negative Matrix Factorization (Van de Cruys, 2010) and more recently, lexical representations learnt by neural networks [START_REF] Huang | Improving word representations via global context and multiple word prototypes[END_REF][START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF].

The work we present in this article follows a different perspective as our objective is to improve an existing distributional thesaurus by relying on its structure through a reranking of its neighbors. Such approach was adopted to some extent by [START_REF] Zhitomirsky | Bootstrapping Distributional Feature Vector Quality[END_REF] as it exploited the neighbors of an entry in an initial thesaurus for reweighting its distributional representation and finally, reranking its neighbors. [START_REF] Ferret | Identifying bad semantic neighbors for improving distributional thesauri[END_REF] proposed a more indirect method in which the reranking is based on the downgrading of the neighbors that are detected as not similar to their entry through a pseudo word sense disambiguation task: such detection occurs if a certain proportion of the occurrences of a neighbor are not tagged as the entry. Finally, the closest work to ours is [START_REF] Ferret | Combining bootstrapping and feature selection for improving a distributional thesaurus[END_REF], which selects in an unsupervised way a set of examples of semantically similar words from an initial thesaurus for training a classifier whose decision function is used for reranking the neighbors of each entry. Its unsupervised selection of examples is more precisely based on the symmetry of semantic similarity relations.

As [START_REF] Ferret | Combining bootstrapping and feature selection for improving a distributional thesaurus[END_REF], our work exploits a certain kind of symmetry in the relation of distributional neighborhood between words but extends it to a larger scale by considering the initial thesaurus as a k-nearest neighbor graph and using the relations in this graph for reranking the neighbors of each entry, similarly to [START_REF] Carlos | Unsupervised manifold learning using reciprocal knn graphs in image re-ranking and rank aggregation tasks[END_REF] in the context of image retrieval.

IR models for building distributional thesauri

Principles

As mentioned in the state of the art, distributional approaches aim to calculate similarities between textual representations of word contexts. Methods to calculate similarities from IR seem then relevant for this problem. For a given word, the set of contexts of all its occurrences is considered as a document. The proximity between two words is then measured on their contexts by a similarity function from IR. This idea has many links with the work from the state of the art, but seems relatively unexplored, with the exeption of [START_REF] Vechtomova | A domain-independent approach to finding related entities[END_REF] in the specific context of similar named entities. It offers the advantage of being easily implementable because of the numerous IR tools available. Some adaptations are of course required. In contrast to IR, the stop words are kept as well as their positions relative to the considered occurrence. Lemmatization instead of stemming is performed. For example, in the excerpt: "... all forms of restrictions on freedom of expression, threats ...", the indexing terms restriction-2, on-1, of+1, expression+2 are added to the context of freedom noted C(freedom). The whole set of collected contexts for a word is used as a query in order to find its distributional neighbors. According to an IR similarity measure, the nearest words of this query (those whose contexts are closest) are returned.

We tested some of the most classical similarity measures used in IR: Hellinger [START_REF] Escoffier | Analyse factorielle et distances répondant au principe d'équivalence distributionnelle[END_REF][START_REF] Domengès | Analyse factorielle sphérique : une exploration[END_REF], TF-IDF/cosinus, and Okapi-BM-25 [START_REF] Robertson | Okapi at TREC-7: Automatic Ad Hoc, Filtering, VLC and Interactive[END_REF]. The last model can be seen as a variation of TF-IDF that better takes into account the difference between document sizes. This point is of importance since in our case the documents (namely the set of contexts of a word) are actually of very variable sizes, due to the very variable number of occurrences of each word. The Okapi-BM25 similarity between a word w i (C(w i ) being the query), and w j (C(w j ) being a document), is given in Eqn 1.

similarity(wi, wj) = t∈C(w i ) (k3 + 1) * qtf k3 + qtf * tf * (k1 + 1) tf + k1 * (1 -b + b * dl(C(w j )) dlavg ) * log n -df (t) + 0.5 df (t) + 0.5 (1)
qtf is the number of occurrences of the word t in the query (C(w i )), dl is the size of C(w j )), dl avg the average size of all contexts, n is the number of documents (that means in our case the number of considered words/thesaurus entries). df (t) is the number of contexts (C(•)) containing t. Finally, k 1 , k 3 and b are some constants, with default values k 1 = 2, k 3 = 1000 and b = 0.75. Details of these classical IR models are not given here but can be found in [START_REF] Christopher | Introduction to Information Retrieval[END_REF].

In the following experiments, the context of an occurrence is defined by the two words before and after the occurrence, and we also use an adjusted version of Okapi-BM25 similarity that enhances the influence of the document size and gives more importance to the most discriminating context words by setting b = 1 and putting the IDF squared to give more importance to the most discriminating context words.

Experimental setup

For the sake of comparison, we use in our experiments the data and baselines provided by [START_REF] Ferret | Identifying bad semantic neighbors for improving distributional thesauri[END_REF]. The corpus used to build the distributional thesaurus is AQUAINT-2. It is a collection of articles from press containing about 380 million words. The thesaurus entries are all the nouns in the corpus with a frequency > 10. That represents 25,000 entries (i.e. unique nouns), denoted by n in the remaining. The corpus is labeled in parts of speech by TreeTagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF]. In this way, we can identify the names that form the thesaurus entries and thus compare to existing work. However this information is not used to build the thesaurus, ensuring the portability of the method to other languages, similarly to [START_REF] Freitag | New experiments in distributional representations of synonymy[END_REF].

To evaluate the built thesauri, WordNet 3.0 synonyms [START_REF] Miller | WordNet: An On-Line Lexical Database[END_REF] and Moby [START_REF] Ward | Moby thesaurus[END_REF] are used as references, either separately, or jointly. These two resources exhibit quite different and complementary characteristics: on the one hand, WordNet indicates strong paradigmatic links between words (synonyms or quasi-synonyms). On the other hand, Moby groups words sharing more extended syntagmatic and paradigmatic relations, including synonymy, hyper/hypo-nymy, meronymy, but also many more complex types such as the composition of co-hyponymy and hyponymy (abolitionannulment, cataclysmdebacle) or hypernymy and co-hyponymy (abyssrift, algorithmroutine). As a result, WordNet provides lists of 3 neighbors on average for the 10,473 names of the corpus it covers, while Moby provides lists of 50 neighbors on average for 9,216 names. When combined, the two resources provide a reference of 38 neighbors on average for 12,243 names. It is this combination of WordNet and Moby that will be used as the main reference in all evaluations of this article. Some results restricted to WordNet or Moby only as reference are also given in some cases to illustrate the impact of our methods on semantic simlarity versus semantic relatedness relations.

Through this intrinsic evaluation framework, the semantic neighbors of about half of the entries of our thesauri are evaluated, which can be considered as a very large evaluation set compared to classical benchmarks such as WordSim 353 for instance [START_REF] Gabrilovich | Computing semantic relatedness using wikipedia-based explicit semantic analysis[END_REF]. This kind of intrinsic evaluation is of course limited by the relations that are present in the resources used as gold standards, often restricted to "classical" relation types such as synonymy or hypernymy. In our case, this limitation Reference Method MAP R-Prec P@1 P@5 P@10 P@50 P@100 WordNet + Moby holds true for WordNet's synonyms but can be considered as far less restrictive for the related words of Moby, due to the diversity of their underlying relation types.

Results

For a given name, our approach by IR models returns a list of names ordered by decreasing similarity. This list is compared to the reference one by computing several classical measures (expressed in % in the following): the precision after k first names, denoted P@k, the Mean Average Precision (MAP) which is the mean of the average precision scores for each query after a reference synonym is found, and the R-precision (precision at R-th position in the ranking of results, where R is the number of relevant names for the query). Table 1 indicates the performance of different models of IR similarities. For purposes of comparison, we show the results obtained under the same conditions by [START_REF] Ferret | Identifying bad semantic neighbors for improving distributional thesauri[END_REF], with both a state of the art approach based on using cosine similarity over pointwise mutual information between contexts (referred as base in the table), and an improved version by learning as described in section 2 (referred as best rerank). We also give the results on the same corpus on an approach based on syntactic co-occurrents (Ferret, 2014 in press), extracted with the Minipar syntactic parser as in (Lin, 1998b).

In these early results, it is worth noting that some IR similarities are quite inefficient, including the TF alone or Hellinger similarity. This is hardly surprising since these similarities use very basic weights that do not enhance the discriminative contexts of words. The similarities that include a notion of IDF get better results in this. Okapi BM25-based similarities offer good results. The standard Okapi version yields performance similar to the state of the art, and the adjusted version even widely outperforms the two systems from [START_REF] Ferret | Identifying bad semantic neighbors for improving distributional thesauri[END_REF], in particular in terms of overall quality (measured by the MAP). Moreover, the results of this adjusted version are comparable to those obtained with syntactic co-occurrents while it only exploits window-based co-occurents, known to give usually worst results than syntactic co-occurrents, without even lemmatization. This latest version of the system serves as reference for the rest of this article.

Reciprocity in the graph of k-NN

Computing all the similarities between all pairs of words produces a weighted graph of neighbors: Each word is connected with certain strength to the n other words. The results above do not reflect this structure. The following sections aim to examine how take advantage of the neighborhood relations embedded in this graph. It must be first noted that some of the IR similarity measures we used are not symmetric, including Okapi-BM25. The similarity between a word w i , used as query, and another word w j does not give the same value as the similarity between the query w j and w i . Apart from that, even if the similarity measure it-self is symmetric, nearest neighbor relationships are not.

It seems then reasonable to assume that the reciprocity between two adjacent words (each belonging to the k nearest neighbors of the other) is a sign of confidence on the proximity between these words. Using this information to improve the previous results is discussed in this section. In the following, τ w i (w j ) denotes the rank of the word w j in the list of neighbors of w i . τ w i (w j ) thus varies from 1 to n.

Distributional neighborhood graph

Reciprocal relationship in distributional neighborhood has already been discussed and used in some work [START_REF] Ferret | Identifying bad semantic neighbors for improving distributional thesauri[END_REF] on distributional semantic, or more generally, on nearest neighbors graphs [START_REF] Carlos | Unsupervised manifold learning using reciprocal knn graphs in image re-ranking and rank aggregation tasks[END_REF]. In these papers, the reciprocity was considered for giving a new similarity score in a simple way. For a word w i and its neighbor w j , the maximal or the minimal rank between τ w i (w j ) and τ w j (w i ) is taken as the new rank. These two operators have too severe effects as only one rank is taken into consideration to decide the final score. This leads to highly degraded performance as shown later. Many other aggregation operators have however been proposed in other contexts with a behavior may be more appropriate to the task, including fuzzy logic [START_REF] Detyniecki | Mathematical aggregation operators and their application to video querying[END_REF]. These operators carry some semantic that allow to comprehend their behavior, such as T-norms (fuzzy logic AND) and S-norms (or T-conorms, fuzzy OR).

In this section, we test some of these operators without claiming to be exhaustive. These are defined on [0, 1] 2 , 1 being the certainty. They are used to generate a new similarity score according to:

score w i (w j ) = Aggreg(1 -τ w i (w j )/n, 1 -τ w j (w i )/n) (2)
where Aggreg is an aggregation operator. The new scores are then used to produce a new list of nearest neighbors of w i (the higher the score, the greater proximity is proven). We thus perceive the semantic associated with these operators. For example, if the aggregation function is max, we get the expected behavior of the fuzzy OR associated with this S-norm: w j will be ranked very close to w i in the new list if w j was close to w i or if w i was close to w j . For the T-norm min, this happens if w j is close to w i and w i is close to w j .

Results

Besides the min and max aggregation operators, Figure 1 reports the results obtained with the following T-norms (or T-norm families dependent on a parameter γ) used as aggregation function Aggreg:

T Prob (x, y) = x * y T Lukasiewicz (x, y) = max(x + y -1, 0) T Hamacher (x, y) = x * y γ+(1-γ) * (x+y-x * y) ; γ ≥ 0 T Yager (x, y) = max(0, 1 -γ (1 -x) γ + (1 -y) γ ) ; γ > 0
We also tested the standard related S-norms, obtained by generalization of the De Morgan's law: S(x, y) = 1 -T (1 -x, 1 -y). For the T-norm families dependent on a parameter, we varied this parameter value in a systematic way. The results reported correspond to the parameter values that maximize the MAP.

All these operators get very different results. Some operators, such as min, max, Lukasiewicz, and others for some γ, induce a threshold effect which degrades the performance: they return a default value generating too much ex aequo among the neighbors, for some values of τ w i (w j ) and τ w j (w i ). T-norms, focusing on pairs of words symmetrically close to each other, are too restrictive. This is consistent with the conclusions of the work cited: if the reciprocity condition is applied too strictly, it does not improve the nearest neighbor lists over all the words. In contrast, S-norms seem better able to take advantage of the ranking. The improvements are modest in terms of overall quality (MAP), but important at some ranks (e.g. P@10).

Finally, it is important to note that these results depend heavily on the resource used as reference. We tested the aggregation rank with S Hamacher , γ = 0.95, on Moby and WordNet references separately. Results are given in Table 2. Because Wordnet is based on a synonymy relationship strong enough (and therefore reciprocal), the performance gains on WordNet are much higher than on Moby. 5 Confidence estimation for a distributional neighborhood list

In the previous section, the rank of w i in the list of neighbors of w j is used to improve the ranking of w j in the list of neighbors of w i . We can also be interested in a more general way to the relative positions of w i and w j in all neighbor lists of all the words. Thereby, we expect to derive a more complete information. As a first step, we define a confidence criterion associated with each list of nearest neighbors, only based on the neighborhood graph.

Principle

We make the following assumption: the nearest neighbor list of a word w is probably of good quality if the distance (in terms of rank) between w and each of its neighbors w i , denoted δ(w, w i ), is consistent with the distance observed between these same words (w, w i ) in other lists. The intuition here is that words supposed to be close should also be found close to the same other words. If k nearest neighbors of w have this property, then we attribute a high confidence to the neighbor list of w. Formally, we define the confidence of the k-nearest neighbor list of w by:

Q(w) = {w i |τw(w i )≤k} p(δ(w, w i ) = τ w (w i )) (3)
where p(δ(w, w i ) = τ w (w i )) is the probability that w i is the τ w (w i )-th neighbor of w. The problem is then to estimate the probability distribution p(δ(w, w i )) for each pair of words (w, w i ). To achieve this goal, we use the Parzen windows which is a method for nonparametric density estimation. We describe below how this classic method [START_REF] Parzen | On estimation of a probability density function and mode[END_REF][START_REF] Wasserman | All of Statistics: A Concise Course in Statistical Inference[END_REF] is applied in our context.

Parzen-window density estimation

Let x ab = δ(w a , w b ) be the distance (in terms of ranks) between two words w a and w b in a list of neighbors of any given word. Considering the n words of the thesaurus, we have a sample of n realizations assumed iid: (x 1 ab , x 2 ab , ... , x n ab ), which are the observed distances between w a et w b in each (complete) neighbor list of each word. These counts can be represented by an histogram as illustrated in Figure 2 (a). Using the Parzen window technique, we can then estimate the probability density of x ab with a kernel density estimator with Eqn 4 where h is a smoothing parameter called the bandwidth, and K( ) is a kernel that we choose Gaussian. The resulting density is illustrated in Figure 2 (b).

p h (x ab ) = 1 n h n i=1 K x ab -x i ab h with K(u) = 1 √ 2π e -u 2 2 (4)
Thus, the resulting probability is a mixture of Gaussians centered on each x i ab . These methods are known to be sensitive to the bandwidth h, which controls the regularity of the estimation. The problem of choosing h is crucial in density estimation and was widely discussed in the literature. We use Silverman's rule of thumb (Silverman, 1986, page 48, eqn (3.31)) to set its value. Under the assumption of normality of the underlying distribution, this rule provides a simple way to calculate the optimal parameter h when Gaussian functions are used to approximate univariate data (Eqn 5 where σ is the standard deviation of the samples, and q 3 -q 1 is the interquartile range). ĥ = 0.9 min(σ,

q 3 -q 1 1.34 ) n -1 5 (5)
Once these probabilities have been estimated on each of the k-nearest neighbors of w, we can calculate the confidence score Q(w). The complexity of this estimation for all neighbor lists is O(k * n 2 ).

Using the confidence score

The expected benefit of using the confidence score is to have an a priori indication on the quality of a neighbor list for a given word. Such a score may thus be useful for many applications using thesauri produced by our approach (e.g. for expanding queries in information retrieval tasks). An evaluation of the confidence score through such applications would certainly be the most suitable, but beyond the scope of this article. We use default direct assessment towards the MAP: we measure the correlation between MAP and the confidence score, the idea being that an entry with a neighbor list of low quality matches an entry with low MAP. We use Spearman's correlation ρ and the Kendall's rank correlation coefficient τ , which do not make any assumption about linearity and compare only the order of words classified according to their MAP with the order according to their confidence score. The results of these coefficients are given in Table 3, along with p-value of the associated test of significance. A coefficient Correlation coefficient value statistical significance Kendall τ 0.37 p < 10 -64 Spearman ρ 0.51 p < 10 -64

Table 3: Correlation coefficient values between the MAP and the confidence score, and their statistical significance (p-value).

Figure 3: Average MAP computed on words with a confidence score lower than a threshold q (x-axis, log-scale), and cumulative proportion of concerned words.

value of 1 indicates a perfect correlation, 0 no correlation and -1 an inverse correlation. A low p-value, for example < 0.05, indicates a statistically significant result. The confidence scores are obtained with k = 20. Other experiments, not reported here, show that this parameter k has little influence on the correlation, for values between 5 and 100. These measures attest to some statistically significant correlation between our confidence score and the MAP, however this correlation is imperfect and non-linear. We compute the average MAP on neighbor lists with a confidence score lower than a threshold q. Figure 3 represents the average MAP (y-axis) in function of the threshold q (x-axis). It shows that the confidence score is still a good indicator of quality, as the MAP decreases with the confidence score.

The confidence score can be used to improve the performance of aggregation techniques presented in Section 4 by integrating it in the final score:

score w i (w j ) = Q(w j ) * Aggreg(1 -τ w i (w j )/n, 1 -τ w j (w i )/n) (6)
As shown in Table 4, using this information allows even greater gains than those reported in the previous section (a Wilcoxon test (p < 0.05) [START_REF] Hull | Using Statistical Testing in the Evaluation of Retrieval Experiments[END_REF] is performed to ensure that the differences are statistically significant; non-significant ones are shown in italics). In the next section, we propose another use of the confidence scores to improve results more specifically on the head of the lists, that is to say on the neighbors judged closest.

Method MAP R-Prec P@1 P@5 P@10 P@50 P@100 S Hamacher γ = 0.95 9.61 (+7.20) 11.59 (+5.85) 30.86 (-0.53) 19.52 (+5.83)

Local reranking

The previous method gives an overall score to the list, but one can also make use of the individual ranking probabilities p(δ(w i , w j )), estimated according to the method of Parzen windows. For a given word w, we have for each of its neighbors w j the probability of his current rank: p(δ(w, w j )) = τ w (w j ). For a given neighbor w j , we can also calculate the probability of any other rank τ : p(δ(w, w j )) = τ with τ = 1, 2, ... In this section, we propose to rely on these more local information to improve the performance by reranking the k-nearest neighbors.

Reranking by the Hungarian algorithm

A simple approach would be to reorder the list based on this criterion, from the most probable neighbors to the least ones. But ranking probability estimation for each word is imperfect, and such a reranking strongly degrades the results. We therefore propose instead a method to rerank the k-nearest neighbors on a more local and controlled manner: a word that was not originally in the k-nearest neighbors can not become a k-nearest neighbor, and a word can not be reranked too far from its original rank.

Our problem is expressed by the following matrix M profit . The rows correspond to words in their original ranks (denoted w 1 to w k ), the columns to new ranks τ at which these words can be assigned, and matrix values are the probabilities of each word w j to appear at rank τ . Given these probabilities, the goal is to find the most likely permutation of the k-nearest neighbors.

Mprofit

=    p(δ(w, w1) = 1) • • • p(δ(w, w1) = k) . . . . . . . . . p(δ(w, w k ) = 1) • • • p(δ(w, w k ) = k)   
As pointed out, we want to avoid that an initially very close neighbor was moved far away and vice versa. This constraint is added by multiplying the matrix M profit by a penalty matrix M penalty (see below) with the Hadamard product (element by element matrix product, denoted •).

Mpenalty =      1 k-1 k • • • 0 k-1 k 1 • • • 1 k . . . . . . . . . 0 1 k • • • 1     
We then face a combinatorial optimization problem which can be solved in polynomial time by the Hungarian method [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF], for a description of the algorithm) on the matrix of assignment costs M profit • M penalty . This algorithm was originally proposed to optimize the assignment of workers (in our case, the neighbors) on tasks (in our case, ranks), according to the profit generated by each worker for each task (in our case, the probability that a neighbor stands at a given rank). The result of this algorithm therefore indicates a new rank for each word. The algorithm converges to an optimal solution with a complexity O(k 3 ) (for reranking the k-nearest neighbors).

Results

Table 5 presents the performance achieved by our local reranking method compared to the adjusted Okapi-BM25 reference using the same experimental conditions as above. As before, the considered neighborhood is set to k = 20. Precisions beyond this threshold are unchanged and thus not reported. We test the effectiveness of the local reranking on all neighbor lists and on a third of lists with the lowest quality scores.

It appears that the reranking on the whole lists does not provide a real gain. However, the gain is substantial on the lists with low confidence score. Moreover, unlike the experiments of section 4, these gains apply by construction to the heads of lists, which are most likely to be used in practice. This difference between results on the whole set of words and on those with the lowest confidence scores can be explained in two ways. First, the lists with the highest confidence scores correspond largely to the lists with the best MAP, as expected and illustrated in Figure 3. This therefore suggests a priori little room for improvement. Second, regardless of MAP, we can also assume that these lists already have an optimum arrangement of individual probabilities that explains the high confidence score. The reranking thus concerns only few neighbors.

Conclusion and future work

The different contributions proposed in this article do not place themselves all at the same level. The thesaurus construction using tools from the IR is not a major conceptual innovation, but this approach seems curiously unexplored although it provides very competitive results while requiring minimum implementations through existing tools from IR.

The various propositions exploiting the neighborhood graph to improve the thesaurus are part of a more original approach where the whole thesaurus is considered. We have specifically examined the aspects of reciprocity and distance, in terms of rank, between two words to offer several contributions. The improvements obtained by aggregation over all neighbors or by the local reranking from confidence scores validate our approach. It should be noted that the gains are small in absolute terms, but, compared to those observed in the field, correspond to significant improvements.

The various aspects of this work open up many prospects of research. For example, many other aggregate functions in addition to those tested in section 4 exist in the literature. Some may even offer the possibility of integrating the confidence score associated with each neighbor, as Choquet's or Sugeno's integrals [START_REF] Detyniecki | Mathematical aggregation operators and their application to video querying[END_REF]. More generally, it would be interesting to iteratively use improvements of neighbor lists to update the confidence scores, etc., in the spirit for example of what is proposed by [START_REF] Carlos | Unsupervised manifold learning using reciprocal knn graphs in image re-ranking and rank aggregation tasks[END_REF]. A detailled analysis of the impact of these techniques according to the type of semantic relation is still to be performed. Beyond the distributional thesauri construction, the proposed methods to compute confidence scores or reorder lists of neighbors can be applied to other problems where the k-nearest neighbor graphs of are built. Also note that we have only considered a small part of the information carried by the neighborhood graph. We focused on the aspects of reciprocity, but taking into account other aspects of the graph (in particular the transitivity, or more generally its topology), could lead to further improvements.

Figure 1 :

 1 Figure 1: Performance of reciprocal rank aggregation, on the reference WordNet+Moby

  Figure 2: (a) Example of two distributions of distances x ab and x ac between a word w a and two of its neighbors w b and w c , represented as histograms (blue and red) (b) Same distributions represented by densities estimated with the Parzen-windows method.

Table 1 :

 1 Performance of IR models for distributional thesaurus building with the references WordNet, Moby and WordNet+Moby

		Ferret 2013 base	5.6	7.7	22.5	14.1	10.8	5.3	3.8
		Ferret 2013 best rerank	6.1	8.4	24.8	15.4	11.7	5.7	3.8
		Hellinger	2.45	2.89	9.73	6.28	5.31	4.12	3.30
		TF-IDF	5.40	7.28	21.73 13.74 9.59	5.17	3.49
		Okapi-BM25	6.72	8.41	24.82 14.65 10.85	5.16	3.66
		Okapi-BM25 ajusted	8.97	10.94 31.05 18.44 13.76	6.46	4.54
		Ferret 2014 synt	7.9	10.7	29.4	18.9	14.6	7.3	5.2
		Ferret 2013 base	9.8	8.2	11.7	5.1	3.4	1.1	0.7
	WordNet	Ferret 2013 best rerank 10.7 Okapi-BM25 ajusted 14.17 12.22 16.97 7.10 9.1 12.8 5.6	3.7 4.47	1.2 1.41	0.7 0.84
		Ferret 2014 synt	13.3	11.5	15.6	6.9	4.5	1.5	0.9
		Ferret 2013 base	3.2	6.7	24.1	16.4	13.0	6.6	4.8
	Moby	Ferret 2013 best rerank Okapi-BM25 ajusted	3.5 5.69	7.2 9.14	26.5 32.18 21.37 16.42 17.9 14.0	6.9 8.02	4.8 5.69
		Ferret 2014 synt	4.8	9.4	30.6	21.7	17.3	8.9	6.5

Table 2 :

 2 Performance and gains (%) of reciprocal rank aggregation, relatively to adjusted Okapi-BM25, on the references WordNet and Moby taken separately, with aggregation operator S Hamacher , γ = 0.95

Table 4 :

 4 Performance gains (%) by reciprocal rank aggregation using the confidence score, on Word-Net+Moby reference.

	Target	MAP	R-Prec	P@1	P@5	P@10
	all words	9.16 (+2.17) 11.24 (+2.76) 30.73 (-1.02) 19.30 (+4.64)	14.37 (+4.44)
	the third of words with the lowest Q(w) 9.55 (+6.44) 11.81 (+7.99) 31.85 (+2.56) 20.43 (+10.81) 15.46 (+12.37)

Table 5 :

 5 Performance gains (%) of reranking with the Hungarian algorithm.

This work is licenced under a Creative Commons Attribution 4.0 International License. Page numbers and proceedings footer are added by the organizers. License details: http://creativecommons.org/licenses/by/4.0/


René Lozi
email: rlozi@unice.fr

MATHEMATICAL CHAOTIC CIRCUITS: AN EFFICIENT TOOL FOR SHAPING NUMEROUS ARCHITECTURES OF MIXED CHAOTIC/PSEUDO RANDOM NUMBER GENERATORS

Keywords: Mathematical circuits, chaos, pseudo-random numbers, attractors, mathematical engineering, Chua's circuit

During the last decades, it had been highlighted the duality between chaotic numbers and pseudo-random numbers. Emergence of pseudo-randomness from chaos via various under-sampling methods has been recently discovered. Instead of opposing both qualities (chaos and pseudo-randomness) of numbers, it should be more interesting to shape mixed Chaotic/Pseudo-random number generators, which can modulate the desired properties between chaos and pseudo-randomness. Because nowadays there exist increasing demands for new and more efficient number generators of this type it is important to develop new tools to shape more or less automatically various families of such generators. Mathematical chaotic circuits have been recently introduced for such a purpose among several others. There some analogy between them and electric circuits, but the components. Mathematical circuits use new ones we describe therein. The combination of such mathematical components leads to several news applications which improve the performance of well known chaotic attractors (Hénon, Chua, Lorenz, Rössler, ...). They can be also used in larger scale to shape numerous architectures of mixed Chaotic/Pseudo Random Number Generators.

Introduction

During the last decades, on one hand, it had been highlighted the duality between chaotic numbers and pseudo-random numbers (e.g. sometimes chaotic numbers used in particle swam optimisation are more efficient than pseudo-random numbers, sometimes high quality pseudo-random numbers are needed for cryptography).

On the other hand, emergence of pseudo-randomness from chaos via various under-sampling methods has been recently discovered. Instead of opposing both qualities (chaos and pseudo-randomness) of numbers, it should be more interesting to shape mixed Chaotic/Pseudo-random number generators, which can modulate the desired properties between chaos and pseudo-randomness.

Because nowadays there exist increasing demands for new and more efficient number generators of this type (these demands arise from different applications, such as multi-agents competition, global optimisation via evolutionary algorithms or secure information transmission, etc.), it is important to develop new tools to shape more or less automatically various families of such generators.

Mathematical chaotic circuits have been recently introduced for such a purpose among various others. By analogy of electronic circuitry: i.e. the design of electronic circuits which are composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires through which electric current can flow; mathematical chaotic circuits are composed of individual components (generators, couplers, samplers, mixers, reducers and, shapers, etc.) connected through streams of data. The combination of such mathematical components leads to several news applications such as improving the performance of well known chaotic attractors (Chua, Lorenz, Rössler, Hénon, Lozi, Logistic or Symmetric Tent map, etc.).

They can be also used in larger scale to shape numerous architectures of mixed Chaotic/Pseudo Random Number Generators.

In Sect. 2 we recall briefly those famous chaotic attractors. In Sect. 3 we introduce the chaotic mathematical circuits. In Sect. [START_REF] Tucker | The Lorenz attractor exists[END_REF] we show some applications of chaotic circuits.

Chaotic and random numbers

Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions. Small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes for chaotic systems, rendering long-term prediction impossible in general. This property is popularly referred to as the "butterfly effect". This happens even though these systems are deterministic (i. e. their future behavior is fully determined by their initial conditions), with no random elements involved. In other words, the deterministic nature of these systems does not make them predictable. We recall first the most studied examples of systems of differential equations (continuous dynamical systems) and mappings (discrete dynamical systems) which we will use in this article to explain the new paradigm of chaotic circuitry. We then introduce several types (chaotic, mixing and geometric) of undersampling in order to overcome the poor quality of chaotic generators. Those mechanisms allow the emergence of pseudo-randomness from chaos. A number of (chaos based) Chaotic Pseudo Random Number Generators (CPRNG) can be built using those undersampling methods.

Continuous dynamical systems: Lorenz, Rössler models and Chua's electronic circuit

The first example of such well known chaotic continuous system in the dissipative case was pointed out by the meteorologist E. Lorenz in1963 [START_REF] Lorenz | Deterministic nonperiodic flow[END_REF] who introduced the following non linear system of differential equations as a extremely simplified model of atmospheric dynamics. It is precisely these equations which led Lorenz to the discovery of the sensitive dependence of initial conditions -an essential factor of unpredictability in many systems. suggest that almost all points in phase space tend to a strange attractor the: Lorenz attractor (see Fig. 1).

x ( x y ), y x y xz , z xy z ,

σ ρ β ɺ ɺ ɺ  =- +  = --   = -  (
Figure 1: The Lorenz attractor Figure 2: The Rössler attractor

In 1976, O. E. Rössler followed a different direction of research to obtain a chaotic model. Considering that, due to extreme simplification used by Lorenz in order to obtain equation ( 1), there is no actual link between this equation and the Rayleigh-Benard problem from which it is originate; he followed a new way in the study of a chemical multivibrator. He started to design some three-variable oscillator based on a two-variable bistable system coupled to a slowly moving third-variable. The resulting three-dimensional system was only producing limit cycles at the time. At an international congress on rhythmic functions held on September 8-12, 1975 in Vienna, he met A. Winfree, a theoretical biologist who challenged him to find a biochemical reaction reproducing the Lorenz attractor. Rössler failed to find a chemical or biochemical reaction producing the Lorenz attractor but, he instead found a simpler type of chaos in a paper he wrote during the 1975 Christmas holidays [START_REF] Rössler | Chaotic behavior in simple reaction system[END_REF]:

x y z , y x ay, z b z( x c ), ɺ ɺ ɺ  =--  = +   = + -  (3)
The obtained chaotic attractor for the parameter value

(see Fig. 2), does not have the rotation symmetry of the Lorenz attractor defined by ( 5), but it is characterized by a map equivalent to the Lorenz map.

S( x, y, z ) ( x, y, z )

= ---

The Chemical reaction scheme leading to (3) is meticulously analyzed by Ch. Letellier and V. Messager [START_REF] Letellier | Influences on Otto Rössler's earliest paper on chaos[END_REF]. The structure of the Rössler attractor is simpler than the Lorenz's one. However even if hundreds of papers has been written on it, the rigorous proof of its existence is not yet established as done for Lorenz equations [START_REF] Tucker | The Lorenz attractor exists[END_REF].

Few years later, in October 1983, visiting T. Matsumoto at Waseda University, L. O. Chua found an electronic circuit [START_REF] Chua | The Double Scroll Family[END_REF] mimicking directly on an oscilloscope screen a chaotic signal (Fig 3). This circuit (Fig. 4) contains three linear energy-storage elements (an inductor and two capacitors), a linear resistor, and a single nonlinear resistor, namely Chua's diode (Fig. 5) with three segment linear characteristics defined by

R p R p R 0 R 1 0 1 f ( v ) m v ( m m ) v B v B 2   = + - + --   (6)
where the slopes in the inner and the outer regions are 0 m and 1 m , respectively, and p B ± denote the breakpoints. The dynamics of Chua's circuit is governed by [START_REF] Hénon | A Two-dimensional mapping with a strange attractor[END_REF] where C , and the intensity of the electrical current through the inductor L : Equation ( 7) can be transformed into the system of three first-order autonomous differential equations whose dimension-less form is

1 2 1 1 2 1 2 2 C 1 C C C C 2 C C L C dv C G( v -v )-f ( v ), dt dv C G( v -v ) i , dt di L L v . dt  =     = +   =-   (7)
x ( y x f ( x )), y x y z , z y, 1 f ( x ) bx ( a b ) x 1 x 1 , 2 α β ɺ ɺ ɺ  = --  = -+   =-    = + - + --   (8)
for which the set of parameter values

is very often used in order to generate chaotic signals. All those models are studied very thoroughly since their discovery 30 years ago. However, even if their equations are very simple, their dynamics is not easily understandable, hundreds of articles have published in this aim. The technique often used to simplify those models is the use of the Poincaré map [START_REF] Lozi | Can we trust in numerical computations of chaotic solutions of dynamical systems?[END_REF].

2-Dimensional discrete dynamical systems: Hénon and Lozi mapping.

In order to study numerically the properties of the Lorenz attractor, M. Hénon an astronomer of the observatory of Nice, France, introduced in 1976 a simplified model of the Poincaré map of this attractor [START_REF] Hénon | A Two-dimensional mapping with a strange attractor[END_REF]. The Lorenz attractor being imbedded in dimension 3, the corresponding Poincaré map is a mapping from the plane

2 ℝ into 2 ℝ .
Therefore the Hénon mapping is also defined in dimension 2 as

H a,b 2 x y 1 ax : y bx     + -   =         (10)
It is associated to the dynamical system Hénon pointed out numerically that there exists an attractor with fractal structure. This was the first example of strange attractor (previously introduced by D. Ruelle and F. Takens [START_REF] Ruelle | On the nature of turbulence[END_REF]), for a mapping defined by an analytic formula. The like-Cantor set structure in one direction orthogonal to the invariant manifold in this simple mapping was a dramatic surprise in the community of physicists and mathematicians. In order to go further in the way of simplifying such a model, few years later, using one of the first desktop electronic calculator HP-9820, we found out, that the linearized version of the Hénon mapping (known as Lozi mapping)

2 x y 1 ax n 1 n n y n 1 bx n   = + - +  + =   (11)
a ,b x y 1 a x L : y bx     + - =         (12)
displayed numerically (for a = 1.7 and b = 0.5) the same structure of strange attractor, but the curves were replaced by straight lines (Fig. 7).

1-Dimensional discrete dynamical systems: Logistic and Tent Map

In mathematics, computations done on one dimensional objects are more tractable than those done on two-dimensional features. Hence it is interesting to consider one-dimensional discrete dynamical systems. The most studied examples are the logistic and the tent (symmetric or skew) map of the interval. In 1838 the belgium mathematician Pierre François Verhulst [START_REF] Verhulst | Notice sur la loi que la population poursuit dans son accroissement[END_REF] introduced a differential equation modelling the grow of population in a simple demographic model, as an improvement of the Malthusian growth model, in which some resistence to the natural increase of population is added. He later, in 1845 [START_REF] Verhulst | Recherches mathématiques sur la loi d'accroissement de la population[END_REF], called logistic function the solution of this equation. In 1973, the biologist Sir R. M. May introduced the nonlinear, discrete time dynamical system

n 1 x rx ( 1 x ) n n + = - ( 13
)
as a model for the fluctuations in the population of fruit flies in a closed container with constant food [START_REF] May | Stability and Complexity of Models Ecosystems[END_REF]. Due to the similarity of both equations although one is a continuous dynamical system, and the other a discrete one, he called Eq. ( 13) logistic equation. The logistic map (Fig. 7)

[ ] [ ] f : 0,1 0,1 r → f ( x ) rx( 1 x ) r = - (14)
associated to ( 13) and generally considered for

[ ] r 0,4 ∈
is often cited as an archetypal example of how complex, chaotic behavior can arise from very simple non-linear dynamical equations. Similarly to the linearization of the Hénon map into Lozi map, one can consider the linearized version of the logistic map which is called, due to its shape (see Fig. 8), the Tent map

f ( x ) 1 2 x = - (15)
associated to the dynamical system

n 1 x 1 2 x n + = - (16)
When the summit of this tent is not exactly in the middle of the interval of definition, the corresponding map is also called the skew tent map.

Chaotic dynamical systems in low dimension are often used since their discovery in the 70' in order to generate chaotic numbers, because they are very easy to implement in numerical algorithms [START_REF] Sprott | Chaos and Time-Series Analysis[END_REF]. However, as we point out in [START_REF] Lozi | Can we trust in numerical computations of chaotic solutions of dynamical systems?[END_REF], the computation of numerical approximation of their periodic orbits leads to very different results from the theoretical ones. The collapsing of iterates of dynamical systems or at least the existence of very short periodic orbits, their non constant invariant measure, and the easily recognized shape of the function in the phase space avoid the use of one-dimensional map (logistic, baker, or tent, …) as a Pseudo Random Number Generator (PRNG). However, the very simple implementation in computer program of chaotic dynamical systems led some authors to use it as a base of cryptosystem [START_REF] Baptista | Cryptography with chaos[END_REF][START_REF] Ariffin | Modified Baptista type chaotic cryptosystem via matrix secret key[END_REF]. In addition it seems that for some applications, chaotic numbers are more efficient than random numbers. That is the case for evolutionary algorithms [START_REF] Pluhacek | Extended Initial Study on the Performance of Enhanced PSO Algorithm with Lozi Chaotic Map[END_REF][START_REF] Tang | Parrondo's games with chaotic switching[END_REF] or chaotic optimization [START_REF] Araujo | Particle swarm approaches using Lozi map chaotic sequences to fuzzy modelling of an experimental thermal-vacuum system[END_REF].

The route from chaos to pseudo-randomness via chaotic or mixing undersampling

In this subsection we show how to overcome the poor quality of chaotic generators using two types (chaotic, mixing) of undersampling. Before presenting both undersampling mechanisms, we have to show how to stabilize the chaotic properties of chaotic number when realized on a computer. In order to simplify the presentation below, we use as an example a system of 2-coupled symmetric tent map [START_REF] Pluhacek | Extended Initial Study on the Performance of Enhanced PSO Algorithm with Lozi Chaotic Map[END_REF], even though other chaotic maps of the interval (as the logistic map, the baker transform, etc.) can be used for the same purpose (as a matter of course, the invariant measure of the chaotic map considered is preserved).

The system is simply described by

1 1 1 1 2 2 1 1 n n n n n n x ( ε ) f ( x ) ε f ( y ) y ε f ( x ) ( ε ) f (y ) + + = - +   = + -  (17)
We use generally )

1 n n n X F X A f (X ) + = = ⋅ (18) where 1 ( ) ( ) ( )
n n p n f x f X f x       =         ⋮ ⋮ , 1 n n p n x X x       =         ⋮ ⋮ , (19) and 1
=1-ε ε ε ε ε =1- ε ε ε A ε ε =1- ε ε ε ε ⋯ ⋯ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋯ ⋯ = = = = ≠ = - =             =               ∑ ∑ ∑ (20)
with

j p i ,i i , j j 1, j i = 1- ε ε = = ≠
∑ on the diagonal (the matrix A is always a stochastic matrix iff the coupling constants verify 0 i , j ε > for every i and j).

It is noteworthy that these families of very weakly coupled maps are more powerful than the usual formulas used to generate pseudo-random sequences, mainly because only additions and multiplications are used in the computation process, no division being required. Moreover the computations are done using floating point or double precision numbers, allowing the use of the powerful Floating Point Unit (FPU) of the modern microprocessors. In addition, a large part of the computations can be parallelized taking advantage of the multicore microprocessors which are used nowadays. Moreover, a determining property of such coupled map is the high number of parameters used ( ( 1) p p ×for p coupled equations) which allows to choose them as cipher-keys, when used in chaos based cryptographic algorithms, due to the high sensitivity to the parameters values [START_REF] Lozi | Emergence of randomness from chaos[END_REF]. However Chaotic numbers are not pseudo-random numbers because the plot of the couples of any component ( )

1 , j j n n x x + of iterated points ( ) 1 ,
n n X X + in the corresponding phase plane reveals the map f used as one-dimensional dynamical systems to generate them via [START_REF] Lozi | Giga-Periodic Orbits for Weakly Coupled Tent and Logistic Discretized Maps, Modern Mathematical Models, Methods and Algorithms for Real World Systems[END_REF]. Nevertheless, we have recently introduced a family of enhanced Chaotic Pseudo Random Number Generators (CPRNG) in order to compute faster long series of pseudorandom numbers with desktop computer [START_REF] Lozi | Complexity leads to randomness in chaotic systems[END_REF]. This family is based on the previous ultra weak coupling which is improved in order to conceal the chaotic genuine function.

The first process of undersampling, the chaotic one is used in order to hide f of [START_REF] Lozi | Giga-Periodic Orbits for Weakly Coupled Tent and Logistic Discretized Maps, Modern Mathematical Models, Methods and Algorithms for Real World Systems[END_REF], in the phase space j j n n 1

( x , x )

+ for any j, the sequence of the real line. The pseudo-code, for computing such chaotically sub-sampled iterates is:

1 2 p 1 p 0 0 0 0 0 X ( x , x , x , x ) seed … - = = n 0; q 0; = = do { while n N < do{ while m n x T < compute 1 2 p 1 p n n n n ( x , x , , x , x ); n … - + + } compute 1 2 p 1 p n n n n ( x , x , , x , x ) … - ; then 1 ; q n( q ) n( q ) n; x x n ; q ) = = + + + + }
This chaotic under-sampling is possible due to the independence of each component of the iterated points n X vs. the others [START_REF] Lozi | New Enhanced Chaotic Number Generators[END_REF].

A second mechanism can improve the unpredictability of the pseudo-random sequence generated as above, using synergistically all the components of the vector n X instead of two.

Given p 1

thresholds

1 2 p 1 0 T T T 1 ⋯ - < < < < forming a partition 1 2 1 , , , p J J J - … of the interval [ ] 1,1 -
, the pseudo-code, for computing such chaotically sub-sampled iterates is

1 2 p 1 p 0 0 0 0 0 X ( x , x , x , x ) seed … - = = n 0; q 0; = = do { while n N < do{ while m n 0 x J ∈ compute 1 2 p 1 p n n n n ( x , x , , x , x ); n … - + + } compute 1 2 p 1 p n n n n ( x , x , x , x ) … - ; let k be such that p n k x J ∈ ; then k ; q n( q ) n( q ) n; x x n ; q ) = = + + + + }.
This second mechanism is called the mixing undersampling.

Geometric undersampling

Geometric undersampling is based on the coupling in another way of p tent maps on the p-dimensional torus [ ]

p p p J 1,1 ℝ = - ⊂
, which can directly generate random numbers, without sampling or mixing, provided p is large enough, although it is possible to combine those processes with it. After presenting this ring coupling in high dimension, we introduce the geometric undersampling fitted to obtain randomness with small values of p (e.g. p = 2).

We first define the mapping

p p M : J J p → 1 2 1 1 1 1 2 3 2 2 2 1 1 1 1 2 1 2 1 2 n n n n n n n n p p p p n n n p n x k x x x x k x x x M x x x k x + + +   - + ×             - + ×           = =                         - + ×   ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ (21)
with the parameters k 1 i = ± . In order to confine every variable

j x n on [ ] p p p J 1,1 ℝ = - ⊂
we do, for every iteration, the transform

1 1 1 2 1 2 j n j n if ( x ) add if ( x ) substract + +  < -  > -  (22)
The particularity of this coupling is that each variable j x n is coupled only with itself and To evaluate the random properties of these generators, the set of NIST tests have been used (Fig. 10). The random properties validations of both a 4-dimensional system and a 10-dimensional one have been carried out [START_REF] Taralova | Dynamical and statistical analysis of a new Lozi function for random numbers generation[END_REF]. 21) is a good PRNG when p 4 ≥ , in lower dimension 2 and 3, the chaotic numbers are not equidistributed on the torus (see Fig. 11). In order to improve the ring coupling mechanism in low dimension, a geometric undersampling based on geometric nature of the invariant measure is used. We present briefly this new mechanism which allows the emergence of randomness from chaos, in the simplest case, the 2-dimensional ring mapping M 2 on the torus 2 J (i.e. a square) into itself, with k k 1 1 2 = = . For this mapping

1 1 2 1 2 2 1 1 1 2 1 2 n n n n n n x x x x x x + +  = - +   = - +   (23) with 1 1 1 2 1 2 j n j n if ( x ) add if ( x ) substract + +  < -  > -  (24)
it is possible to define several critical lines which split the square in a partition of 32 sub-regions, in which the density is uniform [START_REF] Taralova | Dynamical and statistical analysis of a new Lozi function for random numbers generation[END_REF]. Each density can be computed explicitly using a cell-to-cell analysis by the means of a Markov process.

The geometric undersampling process consists in magnifying a square G included in one region We have also used NIST test to confirm the random property of the geometrical undersampling process. They are all successful (Fig. 13).

Figure 13: Geometrical undersampling: each sequence of components satisfies the NIST test for randomness In the case of 2 coupled maps the geometric undersampling allows the building of a PRNG which passes all NIST Test. It is very effective for generating 2 parallel streams of pseudo-random numbers, as shown in [START_REF] Lozi | From chaos to randomness via geometric undersampling[END_REF], in which sequences up to 10 12 consecutives iterates of ( 23) have been computed, providing more than 3.5×10 10 random numbers in a very short time.

Mathematical chaotic circuits

In this Section we introduce the new paradigm of mathematical (chaotic) circuits, which should constitute a new branch of mathematical engineering, in the sense of building models using equations like electronics engineering do using transistors, diodes, etc.

An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires through which electric current can flow. The combination of components and wires allows various simple and complex operations to be performed: signals can be amplified, computations can be accomplished, and data can be moved from one place to another. Very complex systems can be analyzed using various sophisticated methods [START_REF] Vaidyanathan | Anti-synchronization of four-wing chaotic systems via sliding mode control[END_REF]. We introduce in the same way mathematical circuits which are composed of individual components (generators, couplers, samplers, mixers, reducers, cascaders and shapers, etc.) connected through streams of data. The combination of such mathematical components leads to several new applications such as improving the performance of well known chaotic attractors (Chua, Lorenz, Rössler, Hénon, logistic) presented in Sect. 2 for application purposes.

Analog electric circuits are very commonly represented by schematic diagrams, in which wires are shown as lines, and each component has a unique symbol (See Fig. 14). We present in this Section some symbols we design in order to draw mathematical schematic diagrams. First, we describe generator symbols, which are, from a mathematical point of view, equivalent to a battery or a variable current generator in an electric circuit. In the paradigm of mathematical circuitry they generate a digital signal (in one or several dimensions) rather than an electrical current characterized by its voltage and intensity variations (nonetheless, a voltage or an intensity variation can be considered as a physical signal which can be discretized). This signal can be either continuous as in Chua's circuit, Lorenz or Rössler attractors or discrete as in the Hénon, Lozi, Logistic or the symmetric Tent mapping. We consider first the continuous ones.

Continuous generators: Chua's circuit, Rössler and Lorenz attractors

From a mathematical point of view, at least in order to implement applications of chaotic behaviors, all the chaotic attractors (1), ( 3), ( 8) have the same structure: given initial values and a set of parameters, they provide three streams of data symbolized by three arrows. On the contrary, the electric realization of their equation leads to very different electric circuits. For example, concerning the Chua's circuit, even if the scheme of Fig. 4 is easily understandable by electric engineers, it is of no help to build a device using mathematical properties of chaos (like a secure communication system based on it [START_REF] Lozi | Secure communications via chaotic synchronization II: noise reduction by cascading two identical receivers[END_REF]). This is why it is more useful to represent Chua's circuit as a chaos generator by the diagram of Fig. 15(a). On this detailed flowchart of continuous generator, the solid line arrows coming out from the generator represent the three components of the signal x( t ) ( x( t ), y( t ), z(t)) = , the dashed line arrow which points at λ stands for the parameter value, and the dot line arrow which points at 0 x x( 0 ) = , the given initial value of the signal. If there is no ambiguity on the nature of the generator used, the symbol can be simplified as in Fig. 15(b).

Apart from chaotic circuits running wit

There is a need to design such generator can be considered: the Lozi map ( 12) is name inside the symbol is changed). In and the logistic map [START_REF] Ariffin | Modified Baptista type chaotic cryptosystem via matrix secret key[END_REF].

Elementary circuit elements: cou

We present in this section some other than to give a tedious list of elementary them each time they are first used for a are connected through streams of data re There are two types of couplers: rin symbolized by the following circuit ( ) , and dashed line arrow for schematic diagrams. Rather circuit design, we introduce ler, mixer and reducer. They s given by Eq. ( 18) can be and side and one full coupler

Other circuit elements

As done for the schematization of electr purpose: cascader (see Fig. 22) for sec (see Fig. 23) [START_REF] Lozi | Secure communications via chaotic synchronization II: noise reduction by cascading two identical receivers[END_REF]; geometric sampler ( in order to modify the invariant measure (left): Circuit of chaotic undersampling using a sampler (right): Circuit of mixing undersampling using a mixer ctric circuits, several other mathematical circuit element secure communication using two or four synchronized C (Fig. 24), in order to represent the geometric undersam ure of a chaotic generator (Fig. 25), etc. In the limited extend of this paper; it consider the circuit of Cms-PRNG rece recently introduced in order to resist to channel [START_REF] Cherrier | Noise-resisting ciphering based on a chaotic multi-stream pseudo-random number generator[END_REF]. The main idea is to estab alphabet constituting the plain text and the noise boundedness allows restricting effects of the noise. Another combinati seems more interesting to shape mixed properties between chaos and pseudo-ran . Some ting the bounds of the aforementioned intervals in orde ation of logistic and symmetric Tent map is also cons ed Chaotic/Pseudo-random number generators, which randomness for optimization using evolutionary algorith ndom number generators (Cms-PRNG) ations in order to design chaotic multistream pseudo r related sequences of pseudo-random numbers, possessin ly obtained by adding a full coupler as a keyer as show duction process of Eq. ( 24)) when p = 3. Finally we con re 26: Circuit of Cms-PRNG with only 3 streams thematical circuits. We first or a novel ciphering method mission of the signal in any correspondence between the e realistic assumption about rder to precisely resist to the nsidered [START_REF] Garasym | Design of Gigaperiodic Robust Chaotic Pseudo Random Number Generator and applicable to cryptography[END_REF]. Nowadays, it ch can modulate the desired rithms [START_REF] Hamaizia | Fast chaotic optimization algorithm based on locally averaged strategy and multifold chaotic attractor[END_REF][START_REF] Hamaizia | An improved chaotic optimization algorithm using a new global locally averaged strategy[END_REF]. random number generators sing a large number of keys own in the circuit of Fig. 26, onsider

⋮ ⋮ + = = + + = ≠ + = ≠ + - - - - + - - - + = =     = - + - +   ∑ ∑               = - + - +   ∑ ∑             = - + -∑ ∑     

Conclusion

We have introduced the paradigm of chaotic mathematical circuitry which shows some similarity to the paradigm of electric circuitry -the design of electronic circuits. This new paradigm allows, as an example, the building of new chaotic and random number generators. Mathematical circuitry should constitute a new branch of mathematical engineering, in the sense of building models using equations like electronics engineering do using transistors, diodes, etc. Alongside to electronic circuits, the new theory of mathematical circuits allows many new applications in chaotic cryptography, genetic algorithms in optimization and in control [START_REF] Pluhacek | Designing PID controller for DC motor system by means of enhanced PSO algorithm with discrete chaotic Lozi map[END_REF], etc. Due to the versatility of the new components we introduce, the combined operation of these chaotic mathematical circuits remains largely unexplored.

Emergence of pseudo-randomness from chaos via various under-sampling methods has been recently discovered. Instead of opposing both qualities (chaos and pseudo-randomness) of numbers, it should be more interesting to shape mixed Chaotic/Pseudo-random number generators, which can modulate the desired properties between chaos and pseudo-randomness. Chaotic circuitry is the perfect mathematical frame in which such improvement can be easily designed.

1 )

 1 Numerical simulations for an open neighbourhood of the classical parameter values10

Figure 3 :

 3 Figure 3: The Chua attractor

Figure 4 (

 4 Figure 4 (left): Realization of Chua's circuit the Lorenz attractor Figure 5 (right): Three-segment piecewise-linear v-i characteristic of nonlinear voltage controlled resistor (Chua's diode)

Figure 6 (

 6 Figure 6 (left): Hénon strange attractor, 10000 successive points obtained by iteration of the mapping Figure 7 (right): Lozi strange attractorFor the parameter value a = 1.4 and b = 0.3 (see Fig.6) M. Hénon pointed out numerically that there exists an attractor with fractal structure. This was the first example of strange attractor (previously introduced by D. Ruelle and F. Takens[START_REF] Ruelle | On the nature of turbulence[END_REF]), for a mapping defined by an analytic formula. The like-Cantor set structure in one direction orthogonal to the invariant manifold in this simple mapping was a dramatic surprise in the community of physicists and mathematicians. In order to go further in the way of simplifying such a model, few years later, using one of the first desktop electronic calculator HP-9820, we found out, that the linearized version of the Hénon mapping (known as Lozi mapping)

Figure 7 :Figure 8 :

 78 Figure 7: Cobweb of the logistic map for r = 4 Figure 8: Graph of the symmetric tent map

  done with double precision numbers. With these numerical values, the collapsing effect disappears and the invariant measure of any component is the Lebesgue measure[START_REF] Lozi | Giga-Periodic Orbits for Weakly Coupled Tent and Logistic Discretized Maps, Modern Mathematical Models, Methods and Algorithms for Real World Systems[END_REF]. When computations are done with double precision number it is not possible to find any periodic orbit, up to 11 5 10 n = × iterations. More generally, the coupling of p maps takes the form ( ) (

  Fig. 9.

Figure 9 :

 9 Figure 9: Ring coupling between the variables j x n

Figure 10 :

 10 Figure 10: Example of NIST Test for i 1 k ( 1 ) i + = -, i = 1,4 , each sequence of components satisfies the NIST test for randomness Although system (21) is a good PRNG when p 4 ≥ , in lower dimension 2 and 3, the chaotic numbers are not

Figure 11 : 2 J

 112 Figure 11: Invariant densities of iterates in 32 sub-regions bounded by critical lines of M 2 on the torus 2 J [22]

  (as for example the square G = [0.36,0.64] × [0.36,0.64]) included in region m on Fig. 12, up to the size of the square 2 J .

Figure 12 :

 12 Figure 12: The square G = [0.36,0.64]´[0.36,0.64] in which the iterates of (23) are geometrically undersampled

Figure 14 :

 14 Figure 14: Electrical symbols (left-hand side column) and electronic circuit symbols (right-hand side column) used for drawing schematic diagram

Figure 15 :

 15 Figure 15: (b) S The diagram defined above is suitabl attractor, for generating streams of data, case, more arrows can be added (see Fig In fact, mathematical circuits capture 3.2 Discrete generators: Hénon, Lozi

Figure 16

 16 Figure 16 (left (b) Simpl Figure 17 (right) On Remark: In the rest of this article, discrete signal n x .

  Fig on the right hand side. : (a) Electrical Chua's circuit: continuous generator ) Simplified symbol of a continuous generator able, even if we use others types of equations like the Lo ta, provided the number of streams is the same as in Ch ig. 18)). re the essential of dynamics of chaotic attractors. ozi, Logistic and Tent map ith continuous signal, there are chaotic circuits functio tors. For this purpose the classical chaotic mappings pre ) is represented by the symbols of Fig. 16, the Hénon m In dimension 1 the symbol of Fig. 17 stands for both the eft): (a) Discrete generator (Lozi map, expanded symbol plified symbol of 2-dimensional discrete generator One-dimensional discrete generator (e.g. symmetric tent e, we use solid line arrow for continuous signal x( t ) , oupler, mixer, sampler and reducer r symbols we design in order to draw mathematical sc ary mathematical components used for mathematical ci a practical purpose. That list includes: coupler, sampler represented by continuous or dashed line and arrows. ring coupler or full coupler. The coupling of p maps Fig. 18) in which there are p generators on the left hand Lorenz (1) or the Rössler (3) Chua's circuit (if it is not the ctioning with discrete signal. resented in Sect. 2.2 and 2.3 map (10) also (provided the the symmetric tent map (15) ol) ent map)

Figure 18 (

 18 Figure 18 (left): Circuit of co Figure 19 (right): R The circuit of Fig. 19 displays a ring mapping p p M : J J p → (21), meanw

Figure 23 (

 23 Figure 23 (right): Two ca

Figure 22 (Fi 4

 224 Figure 22 (left): Cascader symbol cascading receiver based on several Chua's circuits com

4. 1 FigureFigure 24 (

 124 Figure

  

				p n 1 x +	p n 1 2 x k	p	1	p 1 j 2 -=	ε	1 p , j n x	p 1 j 2 -=	ε	j p , j n x
											(27)
	⋮			⋮		⋮
		+	 	 	+	   	+	 

Another combination recently studied [START_REF] Garasym | Design of Gigaperiodic Robust Chaotic Pseudo Random Number Generator and applicable to cryptography[END_REF] is obtained using in the same time both logistic [START_REF] Ariffin | Modified Baptista type chaotic cryptosystem via matrix secret key[END_REF] and symmetric Tent map [START_REF] Pluhacek | Extended Initial Study on the Performance of Enhanced PSO Algorithm with Lozi Chaotic Map[END_REF] with the reduction process (24):

The corresponding circuit is displayed on Fig. 27, each horizontal generator being, for example, the logistic map, and the vertical generator, the Tent map.

Mixed Chaotic/Pseudo-random number generators

Taking advantage of properties as ergodicity and stochasticity of chaos, some new algorithms called chaos optimization algorithms (COA) are developed [START_REF] Hamaizia | Fast chaotic optimization algorithm based on locally averaged strategy and multifold chaotic attractor[END_REF][START_REF] Hamaizia | An improved chaotic optimization algorithm using a new global locally averaged strategy[END_REF]. Those algorithms depend strongly on the shape of the invariant measure of the chaotic mapping they use (see Fig. 28 for the shape of the numerical computed invariant measure of the Lozi map [START_REF] Sprott | Chaos and Time-Series Analysis[END_REF] and Fig. 29 for the invariant measure of the logistic map). In fact there is a need of to choose the good shape of invariant measure for each specific optimization problem. Hence, instead of looking for family of chaotic generators having the requested shape, it is more simple to use a standard CMS-PRNG which provides pseudo-random numbers with Lebesgue invariant measure, and to transform this equal repartition on the interval adding a new transform to these iterated points. As an exemple of such method, one can consider the transform S defined by Eq. ( 27) applied after Eq. ( 26). Such "shaper" transform can be symbolized by adding a shaper circuit element after any circuit of CPRNG (Fig. 28).