Jean-François Bercher
email: jf.bercher@esiee.fr

Some possible rationales for Rényi-Tsallis entropy maximization

Keywords: Rényi entropy, Tsallis entropy, Displaced equilibriums, Generalized Pareto Distributions

Distributions derived from the maximization of Rényi-Tsallis entropy are often called Tsallis' distributions. We first indicate that these distributions can arise as mixtures, and can be interpreted as the solution of a standard maximum entropy problem with fluctuating constraints. Considering that Tsallis' distributions appear for systems with displaced or fluctuating equilibriums, we show that they can be derived in a standard maximum entropy setting, taking into account a constraint that displace the standard equilibrium and introduce a balance between several distributions. In this setting, the Rényi entropy arises as the underlying entropy.

Another interest of Tsallis distributions, in many physical systems, is that they can exhibit heavy-tails and model power-law phenomena. We note that Tsallis' distributions are similar to Generalized Pareto distributions, which are widely used for modeling the tail of distributions, and appear as the limit distribution of excesses over a threshold. This suggests that they can arise in many contexts if the system at hand or the measurement device introduces some threshold. We draw a possible asymptotic connection with the solution of maximum entropy. This view gives a possible interpretation for the ubiquity of Tsallis' (GPD) distributions in applications and an argument in support to the use of Rényi-Tsallis entropies.

Introduction

The [START_REF] Tsallis | Possible generalization of Boltzmann-Gibbs statistics[END_REF] entropy was introduced in statistical physics, originally for the description of multifractals systems. It is defined by

S α (f X ) = 1 1 -α f X (x) α dx -1 (1)
where α is a real parameter and f X an univariate distribution. Tsallis entropy is simply related to the [START_REF] Rényi | On measures of entropy and information[END_REF] entropy introduced on firm axiomatics grounds. In the two cases, the Shannon entropy S 1 (f X ) = -f X (x)log f X (x)dx is obtained in the limit case α = 1.

It is also convenient here to introduce the Kullback-Leibler and Rényi divergences from a density p to q: I(p||q) = p(x) log p(x) q(x) dx and I α (p||q) = 1 α -1 p(x) α q(x) 1-α dx.

(2)

The definition of I(p||q) requires that p is absolutely continuous with respect to q. It is understood, as usual, that 0 log 0 = 0 log 0/0 = 0 and that a log(a/0) = +∞ if a > 0.

Since the introduction of Tsallis entropy in statistical physics, a considerable amount of work has been devoted to the study of these alternative entropies and to the associated thermostatistics, called nonextensive thermostatistics. Indeed, it is known that for some complex systems, the celebrated Gibbs-Boltzmann formalism seems insufficient for a good description. Applications include fully developed turbulence, Levy anomalous diffusion, statistics of cosmic rays, econometry, and many others.

For this kind of problems, the formalism of nonextensive statistical mechanics (which recovers the classical one as a special limit case) leads to Tsallis' distributions. In a wide variety of fields, experiments, numerical results and analytical derivations fairly agree with the formalism and the description by a Tsallis distribution; see for instance [START_REF] Tsallis | Entropic nonextensivity: a possible measure of complexity[END_REF] and references therein.

These distributions are of very high interest in many physical systems, since they can exhibit heavy-tails, and model power-law phenomena (i.e. with density f X (x) ∝ x -a , a > 0). Indeed, power-laws are especially interesting since they appear widely in physics, biology, economy, and many other fields, see the review in [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF].

In physical systems, the equilibrium Boltzmann-Gibbs distribution can be derived, à la [START_REF] Jaynes | Information theory and statistical mechanics[END_REF], as a maximum entropy distribution, or as a minimum Kullback-Leibler divergence distribution, for a system submitted to a mean constraint (the value of the internal energy for instance). This derives from Sanov theorem whose essence is that, for a parent distribution q, then in the set of empirical probability distributions compatible with a given constraint, the one that becomes overwhelmingly preponderant, i.e. that has the greatest probability, is the nearest to q in the Kullback-Leibler sense.

Therefore, distributions derived using a maximum Tsallis entropy will not coincide with those derived for the classical maximum entropy approach and the maximum Tsallis entropy distribution, in the words of [START_REF] Grendar | Maximum entropy method with non-linear moment constraints: challenges[END_REF], will be asymptotically improbable. In view of the success of nonextensive statistics and of the successful identification of Tsallis' distributions in physical problems, there should exist some probabilistic setting that provides a justification for the maximization of Tsallis entropy. Some such possible rationales are described in this communication.

The Tsallis' distributions are obtained as the result of the maximization of Tsallis entropy (1) subject to a mean constraint and normalization. Two kind of constraints have been considered: the standard mean E[X] = m, and a generalized α-expectation E α [X] = m, which is taken with respect to the 'zooming distribution' p(x) α / p(x) α dx. These two constraints lead to a solution with the general form

f X (x) = 1 σ 1 + γ σ x -1 γ -1 for x F > x ≥ 0, (3)
where σ and γ are respectively the scale and shape parameters; for γ < 0, the density has a finite support, with x F = -σ/γ if γ < 0 and an infinite support otherwise. In the first case, the exponent is 1/(α -1) and σ = 1/β, and in the second case, the exponent is 1/(1 -α) and σ = 1/β(2 -α). For γ = 0 (α = 1), the solution reduces to f X (x) = 1/σ exp(-x/σ) for γ = 0.

2 Tsallis distributions as a mixture

Tsallis' distributions, have been found physically relevant for partially equilibrated systems, characterized by fluctuations of an intensive parameter, namely temperature fluctuations. They are obtained if the inverse of temperature, proportional to the parameter β of a Boltzmann distribution β exp(-βx), fluctuates according to a gamma distribution. This technique was later generalized as 'Superstatistics' by Beck and Cohen (2003) for more general distributions f β (β). In fact, this approach is the well-known technique of mixing, which is a standard technique for the derivation of distributions.

It is also possible (see [START_REF] Bercher | Maximum entropy with fluctuating constraints -The example of K-distributions[END_REF]), to relate this result to a (standard) maximum entropy approach, but with fluctuating constraints. Indeed, the canonical distribution maximizes the Shannon-Boltzmann entropy S = -f E (x) log f E (x)dΓ subject to normalization and to the observation constraint Ē = xf E (x)dΓ . The solution is f E (x| Ē) = e -βx-log Z(β) , where Z(β) = e -βE dΓ is the partition function. The entropy S( Ē) and the potential Φ(β) = log Z(β) are conjugated functionals while Ē and β are conjugated variables. This gives the standard relation Ē = -d log Z(β) dβ . Hence, it appears that variations of the thermodynamic β implies variations of its dual variable Ē and reciprocally. Thus, if the mean energy varies according to a distribution f Ē ( Ē), then this also gives a distribution f β (β) for β, and the global distribution becomes

P (E) = +∞ 0 f E (E| Ē)f Ē ( Ē)d Ē = P (E) = +∞ 0 f E (E|β)f β (β)dβ. (4)
This is similar to the 'Superstatistics', but with the recognition of the link between the intensive parameter β and the observable Ē, so that a model of fluctuations can be naturally introduced for Ē. For instance an inverse-gamma model for Ē leads to Tsallis distributions 1 . Then, this distribution, which arises as the solution of a standard maximum entropy with (inverse-gamma) fluctuating constraints, can in turn be viewed as the maximum Rényi-Tsallis entropy solution.

Amended MaxEnt

A key for the apparition of Levy distributions and a probabilistic justification might be that it seems to appear in the case of modified, perturbated, or displaced classical Boltzmann-Gibbs equilibrium. This means that the original MaxEnt formulation "find the closest distribution to a reference under a mean constraint" may be amended by introducing a new constraint that displaces the equilibrium, as discussed in [START_REF] Bercher | An amended maxent formulation for deriving Tsallis factors, and associated issues[END_REF]. The partial or displaced equilibrium may be imagined as an equilibrium characterized by two references, say r and q. Instead of selecting the nearest distribution to a reference under a mean constraint, we may look for a distribution p * simultaneously close to two distinct references: such a distribution will be localized somewhere 'between' the two references r and q. For instance, we may consider a global system composed of two subsystems characterized by two prior reference distributions. The global equilibrium is attained for some intermediate distribution, and the observable may be, depending on the viewpoint or on the experiment, either the mean under the distribution of the global system or under the distribution of one subsystem. This can model a fragmentation process: a system Σ(A, B) fragments into A, with distribution r, and B with distribution q, and the whole system is viewed with distribution p * that is some intermediate between r and q. This can also model a phase transition: a system leaves a state q toward r and presents an intermediate distribution p * . This intermediate distribution shall minimize its divergence to its "parent" distribution q(x), but also be 'not too far' from its attractor r(x). This can be stated as I(p||q)-I(p||r) ≤ θ, or equivalently as I(p||r) ≤ θ ′ . Remark that the first constraint can be interpreted as a constraint on the mean log-likelihood. The problem can be written as follows:

   min p I(p||q) s.t. I(p||q) -I(p||r) ≤ θ or I(p||r) ≤ θ ′ (5)
The optimum distribution solution of these two equivalent problems is

p * (x) = r(x) α q(x) 1-α r(x) α q(x) 1-α dx , (6)
The solution of the minimization problem satisfies a Pythagorean equality: I(p||q) = I(p||p * ) + I(p * ||q) for any distribution p such that θ = I(p||q) -I(p||r). It is interesting to note that the solution ( 6) is nothing but the escort or zooming distribution of nonextensive thermostatistics. With the expression of the solution p * (x), we obtain that

I(p * ||q) = αθ -log( R(x) α q(x) 1-α dx) = αθ -(α -1)I α (r||q), (7)
where we have recognized the Rényi divergence. Suppose now that the original problem is completed by an additional constraint. For instance, one classically has to account for an observable. The observable values are as usual the statistical mean under some distributions. Depending on the viewpoint, the observable may be a mean under distribution r, the distribution of an isolated subsystem, or under p * , the equilibrium distribution between r and q. Hence, the problem will be completed by an additional constraint, and we need to adjust the distribution r by further minimizing the Kullback-Leibler information divergence I(p * ||q), but with respect to r and subject to the mean constraint. This finally amounts to the minimization of the Rényi divergence in (7), I α (r||q) subject to the chosen mean constraint. Of course, the problem is similar to the maximization of Rényi-Tsallis entropy and leads to the Tsallis distribution (3), but with respect to the measure q(x).

Tsallis distribution as the distribution of excesses

A remarkable feature of the maximum Tsallis entropy construction is its ability to exhibit heavy tailed distributions. Tsallis distributions have the form (3) of a Generalized Pareto Distribution (GPD). The interesting point is that the GPD is employed outside the statistical physics field for modeling heavy tailed distributions. Examples of applications are numerous, ranging from reliability theory, traffic in networks, hydrology, climatology, geophysics, materials science, radar imaging or actuarial sciences.

These uses are related to the POT (Peaks over Threshold) method; see [START_REF] Leadbetter | On a basis for 'Peaks over Threshold' modeling[END_REF]. The underlying rationale is the Balkema-de Haan-Pickands theorem (see [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF]), which asserts that the distribution of excesses over a (high) threshold often follows approximately a GPD.

Indeed, there are many situations in which the system at hand, the measurement process or device only give access to values of a variate X greater than a parameter u. Hence, the recorded values are the excesses of X over the threshold u, that is values of the conditional random variable X u X u = (X -u)1 X>u .

The Pickands' theorem indicates, roughly speaking, that if F is in the domain of attraction of an extreme distribution, for instance the Fréchet distribution or Gumbel distribution, the distribution function of excesses F Xu converges (in the infinite norm sense) to a limit distribution which is nothing else but a GPD.

To the accumulation of random variables in the classical Central Limit Theorem corresponds here an increase in the threshold u. Furthermore, the GPD verifies a remarkable stability property with respect to thresholding, in the sense that the distribution of excesses of a GPD remains a GPD, with the same shape (exponent) parameter γ but a different scale parameter.

It is possible to draw another connection between the distribution of excesses and the maximum of Tsallis entropy. In [START_REF] Bercher | An entropic view of Pickands' theorem[END_REF], we indicate that the 1-norm, first moment and Rényi-Tsallis entropy of a suitably normalized version of the excess variable (in the Fréchet and Gumbel domain) converge asymptotically to constant values. Then, with an appropriate choice of α, this shows that the distribution of excesses is necessarily, asymptotically, the GPD solution of Tsallis' α-entropy maximization).

We have presented here several possible rationales for the apparition of Tsallis distributions and of the underlying Rényi-Tsallis entropy. A common feature is that the distribution or entropy appears in what sounds as exceptional situations: modified, perturbated or fluctuating equilibriums, or excess over a threshold. However, we believe that there is not probably a single reason that explains the success of Rényi-Tsallis entropy and distribution, and that the multiplicity of possible rationales is itself an explanation of this success.

A gamma model leads to the so-called K-distributions that also have interest in physical applications.


Vedran Vukotic
email: vedran.vukotic@irisa.fr

Vincent Claveau
email: vincent.claveau@irisa.fr

Christian Raymond
email: christian.raymond@irisa.fr

IRISA at DeFT 2015: Supervised and Unsupervised Methods in Sentiment Analysis

Keywords: Fouille d'opinion, apprentissage artificiel, boosting, apprentissage bayésien, plongement de mots Opinion mining, machine learning, boosting, Bayesian learning, word embedding

Cet article décrit la participation de l'équipe LinkMedia de l'IRISA à DeFT 2015. Notre équipe particpé à deux tâches : la classification en valence des tweets (tâche 1) et la classification à grain fin, elle même, décomposée en deux sous-tâches, à savoir la détection des classes génériques de l'information exprimée dans un tweet (tâche 2.1) et la classification des classes spécifiques (tâches 2.2) de l'émotion/sentiment/opinion exprimée. Pour ces trois tâches, nous adoptons une démarche d'apprentissage artificiel. Plus précisément, nous explorons l'intér de trois méthodes : i) le boosting d'arbres de décision, ii) l'apprentissage bayésien utilisant une technique issue de la recherche d'information, et iii) les réseaux neuronnaux convolutionnels. Nos approches n'exploitent aucune ressource externe (lexiques, corpus) et sont uniquement fondées sur le contenu textuel des tweets. Cela nous permet d'évaluer l'intérêt de chacune de ces méthodes, mais aussi des représentations qu'elles exploitent, à savoir les sacs-de-mots pour les deux premières et le plongement de mots (word embedding) pour les réseaux neuronaux.

Introduction

All the three classification problems analyzed in this paper are sentiment analysis problems. They consist of the same data samples, French tweets, whose target labels vary according to the task. After describing these classification tasks and their corresponding datasets in Section 1, we present and analyze the classifiers used in this work. In section 2, decision trees with boosting are applied directly to symbolic words. Section 3 describes a system consisting of Bayesian learning relying on information retrieval techniques. Section 4 deals with Convolutional Neural Networks (CNNs) combined with various word embedding methods. Finally, in section 5, all the three systems are compared for the three classifications tasks and a conclusion is given in section 6.

Task 1: valence classification

The provided training set consists of 7929 tweets, 102 of which were not found at the time of retrieval. Each sample belongs to one of the following three classes: positive (+), negative (-) and neutral/mixed (=). The distribution of the classes in the training set is sufficiently uniform: 31% (+), 24% (-) and 45% (=).

1.2 Task 2.1: detection of the generic class of the information

The provided training set for this task consists of 6754 tweets, 81 of which were not found at the time of retrieval. Each sample in this task belongs to one of the following four classes: information, opinion, sentiment and emotion. The classes are not very well distributed within this task, thus possibly introducing biases in the classifiers: 53% (INFORMATION), 34% (OPINION), 1% (SENTIMENT) and 12% (EMOTION).

1.3 Task 2.2: detection of the specific class of the opinion/sentiment/emotion For this task, 3183 tweets were provided, 40 of which were not found during retrieval. There are 18 classes in this task: negative surprise / negative astonishment (SURPRISE_NEGATIVE), agreement / understanding / approbation (AC-CORD), sadness / sorrow / suffering / despair / resignation (TRISTESSE), valorization / interest / appreciation (VAL-ORISATION), dissatisfaction / unhappiness (INSATISFACTION), fear / terror / worry / anxiety (PEUR), appeasement / relief / gratefulness / forgiving / serenity (APAISEMENT), anger / rage / irritation / exasperation / nervousness / impatience (COLERE), satisfaction / contentment / pride (SATISFACTION), disagreement / disapprobation (DESACCORD), displeasure / deception (DEPLAISIR), disturbance / embarrassment (DERANGEMENT), love / sweetness / affection / devotion / passion / envy / desire (AMOUR), contempt / disdain / disgust / hate (MEPRIS), pleasure / entertainment / joy / euphoria / happiness / ecstasy (PLAISIR), positive surprise / positive astonishment (SURPRISE_POSITIVE), boredom (ENNUI), devalorization / disinterest / depreciation (DEVALORISATION).

In this task, the classes are also not well balanced and could thus introduce a bias into the classifiers: 4.8% (AC-CORD), 0.3% (AMOUR), 0.3% (APAISEMENT), 6.6% (COLERE), 1.5% (DEPLAISIR), 0.4% (DERANGEMENT), 6.8% (DESACCORD), 12.6% (DEVALORISATION), 0.1% (ENNUI), 0.3% (INSATISFACTION), 5.5% (MEPRIS), 8.6% (PEUR), 1.1% (PLAISIR), 2.3% (SATISFACTION), 0.3% (SURPRISE_NEGATIVE), 0.1% (SURPRISE_POSITIVE), 1.1% (TRISTESSE), 47.3% (VALORISATION). Also, it is worth noticing that this task has the least samples and the most classes, which together with their nonuniform distribution is negatively effecting the learning of meaningful decision boundaries.

Test set

The test set of the DeFT 2015 challenge consists of 3383 tweets (2 of which were not found at the time of retrieval for some participants and were removed by the DeFT commission). The correct target labels were unknown at the time of developing the methods described in this articles, so all the experiments performed and described are done on splits of the provided training data into train, validation and test sets, as described in each of the following sections. The performance of our methods on the official test set is given at the end of this article.

Boosting decision trees

In order to tackle the three tasks presented in the introduction, we first adopt a standard Machine learning approach based: boosting decision Trees. This approach, using a very usual text representation of the tweets, is intended to be a baseline. In this section, we first describe the principles of this machine learning technique and then the performance obtained with the training dataset. In our case, in order to achieve better performance, several Decision Trees are inferred and from the training data and combined following the popular boosting algorithm AdaBoost.MH [START_REF] Schapire R | Boostexter: A boosting-based system for text categorization[END_REF]. This meta-learning framework is an iterative process, in which errors (tweets receiving the wrong class label) obtained with the tree inferred at the previous step are given more weight so that the next decision tree will focus more on this problematic examples.

The implementation that we used in our experiments is BONZAIBOOST1 .

Practical details and performance

The tweet are represented as sets of words (unigrams) in order to be manipulated by the decision trees. The test used in the nodes of the trees is thus just to check if a tweet contains a word or not.

Boosting was first proposed to improve the classification performance of weak learners, that is, classifiers with a low precision (though it has also be shown to improve results of strong classifiers). Thus, in the case of Decision Trees, boosting is often used with low depth trees (Antoine [START_REF] Laurent | Boosting bonsai trees for efficient features combination : application to speaker role identification[END_REF], such as decision stumps (depth=1).

During the training phase, we experimented with several number of iterations (n) for boosting and several depth of trees (d). These two parameters (n and d) were chosen through cross-validation in order to maximize the macro-precision, as it is the main score proposed by the organizers. The best performance is found for d = and n =; they are summarized in Table 1. Yet, it is noteworthy that several other settings (n and d) gave very close results. This is due to the fact that macro-precision is a very unstable score, since a simple tweet, if it is correctly or incorrectly classified in a class with very few tweets, can drastically change the final score.

One interesting thing with decision trees is that they can be interpreted, to some extents. It is even easier with decision stumps since one can directly see the (only) test, that is, in our case, the presence or absence of a word in a tweet, with the label of the class and a weight. Moreover, when using boosting over decision stumps, we get a high number of decision stumps, and thus a high number of these word/label/weight associations. They may be gathered to form a lexicon suited to the set of class used in the tasks. For instance, here is a small excerpt of such a lexicon concerning the word menace for Task 2.2 in which one can see that menace is strongly associated with PEUR, and to the contrary, strongly opposed to VALORISATION.

Bayesian learning

In this section we present the second machine learning approach tested by IRISA for Tasks 1, 2.1 and 2.2. As for the previous one, it relies on a simple representations of text, that is bags-of-words. It is a somewhat classical framework based on Bayesian learning whose only originality is to use Information Retrieval techniques in order to estimate certain probabilities needed to predict class labels of the tweets.

Principles

Let us note ω i the label of one the class and d j is the description of one of the tweets. Under a probabilistic framework, the goal of the task can be expressed as finding the class that maximizes this probability P (ω i |d j ), i.e.

ω * = arg max i P (ω i |d j )
By using the well-known Bayesian rule, this probability can be decomposed into:

P (ω i |d j ) = P (d j |ω i ) * P (ω i ) P (d j )
Moreover, since P (d j ) is constant for a given tweet, we have:

ω * = arg max i P (d j |ω i ) * P (ω i )
Finally the two probabilities to estimate on the training data are the a priori probability of a class P (ω i ) and the likelihood P (d j |ω i ).

In this work, the a priori probability is simply estimated by counting the number of tweets of each class, and by smoothing (Laplace smoothing) not to put a disadvantage on less populated classes:

P (ω i ) = nb tweets of class omega i + 1 nb tweets + nb classes
The main originality of our approach is to use an information retrieval technique in order to estimate the likelihood of a tweet given a class. For a given tweet, we use a k-nearest-neighbors approach: the k closest training tweets are retrieved by using an information retrieval system. More precisely, we use a system based on Okapi-BM25 [START_REF] Robertson | Okapi at TREC-7: Automatic Ad Hoc, Filtering, VLC and Interactive[END_REF] Task Macro-precision Micro-precision Task 1 0.679672521722188 0.615226864906434 Task 2.1 0.792678272906324 0.641901037750038 Task 2.2 0.449395650820018 0.590676883780332 Table 2:

score BM 25 (d) = ti qT F (t i , q) * T F BM 25 (t i , d) * IDF BM 25 (t i ) = ti (k 3 + 1) * tf (t i , q) k 3 + tf (t i , q) * tf (t i , d) * (k 1 + 1) tf (t i , d) + k 1 * (1 -b + b * dl(d)/dl avg ) * log N -df (t i ) + 0.5 df (t i ) + 0.5 (1)
From the k tweets with highest scores, we estimate the likelihood of the tweet for a given class as the proportion of tweets from this class in these k neighboring tweets.

Practical details and performance

For our experiments, the value for k was tuned on the training set through leave-one-out in order to maximize the macroprecision. The values found are k = 10 for task 1, k = 10 for task 2.1 and k = 3 for task 2.2.

The performance of our Bayesian learning approach is shown in table 2. It is computed with a 10-fold cross-validation over the training dataset.

In order to illustrate the influence of the number of neighbors considered when computing the likelihood, Figure 1 presents the macro and micro-precisions for each task, according to different values of k. One can notice that this value has only a limited influence on micro-precision (about 0.05 between maximum and minimum micro-precision values. Concerning macro-precisions, the situation is contrasted: for Task 1, k has a small influence. It is easily explained by the fact that there many tweets for each class, and thus it does not influe on the kNN process. Conversely, for Task 2.1 and 2.2, macro-precisions varies a lot. This is due to the fact that for some classes with very few training data, if k gets higher than the population of the class, the kNN will necessarily includes tweets from other classes. This fact is made worse by the instability of the macro-precision score (see Section 5.3), since tweets from these less populated classes will tend to be misclassified, even if the number of misclassified tweets do not vary so much globally.

Convolutional Neural Networks

Deep learning methods have been shown to produce state-of-the-art results in various tasks and different modalities (vision, speech, etc.). Convolutional Neural Networks [START_REF] Lecun | Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks[END_REF] represent one of the most used deep learning method in visual recognition. Recent works have shown that CNNs are also well suited for sentence classification problems and can produce state-of-the-art results [START_REF]Convolutional neural networks for sentence classification[END_REF][START_REF] Zhang | Effective use of word order for text categorization with convolutional neural networks[END_REF]. These studies have analyzed the performance of CNNs in datasets like movie reviews, the Stanford sentiment treebank, customer reviews and similar datasets that usually consists of positive/negative labels (either binary or with fine-grained intensities). In this section, we explore the feasibility and measure the performance of similar CNN models in multi-class emotion classification of short sentences (tweets).

CNNs consist of a series of interchanged convolutional and pooling layers, followed by a simple classifier (usually a MLP or an RBF). CNNs have two interesting properties that make them valuable and robust classifiers in computer vision: i) autonomous learning of meaningful features and ii) robustness to spatial variations (translational invariance).

Convolutional layers scan the inputs of the previous layer with learned kernels. The kernels are learned by backpropagation and become filters that respond to features relevant for the classification task. By applying multiply convolutional layers, the network learns meaningful features at different levels.

Pooling layers reduce the dimensionalites of their respective previous layers either by different downsampling methods or by more complex pooling methods that use different metrics. The most common pooling method in CNNs i s max-pooling. Max-pooling have been shown to provide good results while also being very computationally inexpensive [START_REF] Boureau | A theoretical analysis of feature pooling in vision algorithms[END_REF].

A typical approach in machine learning for improving generalization consists of combining different architectures. However, that can be computationally expensive. The dropout method suggest randomly disabling some hidden units during the training part, thus generating a big set of combined of virtual classifiers without the computational overhead [START_REF] Hinton | Improving neural networks by preventing co-adaptation of feature detectors[END_REF]. For a simple multilayer perceptron with N neurons in one hidden layer, an equivalent of 2 N virtual architectures would be generated by applying dropout. Dropout has been shown to significantly improve generalization of CNNs.

CNNs have recently been shown to be useful and perform well in NLP classification problems [START_REF]Convolutional neural networks for sentence classification[END_REF]. The difference between CNNs applied to computer vision and their equivalent in NLP lies in the input dimensionality and format. In computer vision, inputs are usually single-channel (eg. grayscale) or multi-channel (eg. BGR) matrices (2D), usually of constant dimensions. In sentence classification, each input consist of a sequence of words of non-constant length. Each word w is represented with a numerical vector (embedding) e w of a constant size. Word embeddings can be learned jointly, with the classifier, in a supervised manner or separately, usually in a unsupervised manner (eg. word2vec [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF]). All the word representations are then concatenated (in their respective order) and padded with zero-vectors to a fixed length (maximum possible length of the sentence). Eg. the phrase "Que la force soit avec toi #4mai" would be represented to the CNN input as x = e que ⊕ e la ⊕ e f orce ⊕ e soit ⊕ e avec ⊕ e toi ⊕ e T AG ⊕ e U N KN OW N ⊕ 0 ⊕ . . . 0 with | x i | = const., ∀i, where the ⊕ operator represents concatenation. Although this representation may look counter-intuitive from a more classical NLP viewpoint, it is a perfectly good representation for a CNN, due to their translational invariance property that enables them to be robust to changes in position within sentences, while still being able to grasp relevant features from the words and their context.

Model description

The model used in this work shares the same architecture as the simple model in (Kim, 2014): a single convolutional layer, followed by a max-over-time [START_REF] Collobert R | Natural language processing (almost) from scratch[END_REF] pooling layer and a standard soft-max fully connected layer at the end. A standard dropout of 0.5 (50% of the neurons are disabled in each iteration) is used.

The cross-validation of this method was done with 5-folds. Figure 2 shows the errors of the validation sets for different variations that will be described in the following subsections.

Prior to converting words to their numerical representation (word embedding), all the sentences were preprocessed in the following manner: all the words were converted to their lowercase equivalent; punctuation marks were isolated into separate elements; URLs and references were converted to respective tags ("<url>" and "<ref>"); finally, hashtags were converted to two separate elements: a tag and the original hashtag string (eg. "#nowplaying" → "<tag> nowplaying").

Randomly initialized word embeddings

In these experiments, word embeddings were initialized randomly from a uniform distribution U(-0.25, 0.25). Afterwards, the embeddings were trained in a supervised manner together with the CNN. This works by simply by extending backpropagation to the layer before the first convolutional layer (the lookup table). As seen is in figure 2, this method takes a significant number of epochs more to converge to a stable precision, but does perform quite well. It can be noticed that in Task 2.2 (figure 2 c.), due to the biggest number of classes and the least number of examples, it converged slower and with less good precision on the validation sets.

Word embeddings learned on a big corpus

These six experiments used external big corpuses to train embeddings for the French language in an unsupervised manner. It is important to note that obviously these embeddings had no special knowledge (an appropriate representation) of Twitter specifics (hashtags, references, URLs, etc.). Embeddings of unknown words are initialized randomly and are later either fine-tuned in a supervised manner or not. For each task, two variations were analyzed: one in which the embeddings learned in an unsupervised manner were kept static and one in which they were updated (fine-tuned) while learning the CNNs. The latter has been shown to perform slightly better but with no significant differences.

Compared to random embeddings, these embeddings trained on large corpora have a slight initial advantage but do not perform as well after more training epochs. Our explanation for this phenomena is that in such tasks, having a notion of the twitter specifics within the embeddings is advantageous and the method lacks that advantage.

Word embeddings learned on DeFT tweets

Here, we describe six experiments with embeddings learned directly from the tweets (the training set of the current fold) in an unsupervised manner, with word2vec [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF]

Performance comparison and discussion

Official results

The DeFT 2015 accepted three submissions (runs) per team. We opted to submit one run from Bayesian learning, one with Bonzaiboost and a last one from the CNN method with embeddings learned on tweets and fine tuned. It is important to notice that cross-validations differ in the experiments described in this paper prior to the final official evaluation (eg. CNNs use a 5-fold cross-validation while Naive Bayes was evaluated with a 10-fold cross-validation). The most indicative performance evaluation is thus given on the official DeFT 2015 test set and is shown in table 4.

Bayesian learning performed best in tasks 1 and 2.1. CNNs performed best in Task 2.2. This improvement of CNNs performances in multiclass data with less samples is due to gain brought by the directly learned embeddings. It is important to note that there should be room for improvement in CNNs to close the gap in simpler datasets (task 1 and 2.1) and probably improve upon the other results. We think that it would be valuable to research applying the same embeddings to a deeper CNN (more than one convolutional and one pooling layer) thus enabling the network to grasp concepts at greater distances within a sentence.

The difference observed between these values and the one estimated on the training set (10 points in macro-precision), especially for task 2.2, is left unexplained. A technical problem or the choice of wrong parameters may explain that, as well as a difference when building the training and the test sets. But we also give additional thoughts on the fact that the macro-precision was not a reliable choice in order to chose the best parameters (see below).

Data inconsistencies and its consequences

The training data contains many tweets whose provided label, whatever the tagset (ie. task 1, 2.1 or 2.2), is hard to explain. For instance, consider the following tweets:

AMOUR

. @RoyalSegolene "Les Français souhaitent à 90%

Discussion about the stability of macro-precision

The choice of macro-precision as the main evaluation score raise several issues. As it was explained before (cf. Sec. 3.2), this choice, combined with the fact that classes are strongly unbalanced (especially for task 2.2), is not well taken into The other problem we want to stress here is the instability of this score. As said earlier the correct or incorrect classification of a single tweet, in a less-populated class, may have a strong impact on the final result. It means that the difference between two systems' macro-precisions, is not necessarily statistically significant, even if the difference itself may appear as important. In order to illustrate that point, we consider two systems S1 and S2 based on on our boosting approach with sligthly different settings. S1 and S2 uses n = 100 iterations, but S1 builds decision stumps (d = 1) while the maximal depths for S2 is d = 10. These two systems are trained and evaluated on the training dataset (through 10-fold cross-validation) on task 2.2. The micro and macro-precisions for the whole dataset (concatenation of the 10 test folds) are given in Table 5. It is worth noting S2 performs better than S1; the difference between the two systems' macro-precision is high, and also important in a smaller extent in terms of micro-precisions. In order to study the stability of these scores, we also divide the dataset into 30 equal parts and compute for each of them and for each system the two scores. Thus, we have 30 macro-precisions and 30 micro-precisions for S1 and the same for S2. We indicate the average precisions over these 30 subsets in the Table 5. It appears that the average macro-precision for S2 is in fact much lower than when considering the dataset as a whole. In order confirm that, we compute a paired Student t-test between these two systems with the 30 pairs of scores. The p-value for the macro-precision is p = 0.2582, and the micro-precision's one is p = 0.00045. It means that the difference of macro-precision between S1 and S2 is not statistically significant, while the micro-precision difference can be considered as statistically significant.

This tends to demonstrate that macro-precision computed over a whole dataset of tweets is not a reliable score to evaluate the systems, especially when some classes only contains a few tweets, as it is the case for several classes of Task 2.2. Another side-effect is that using macro-precision to chose the final parameters of our machine learning techniques has certainly led us to pick up sub-optimal solutions.

Conclusion

For this participation of IRISA to Tasks 1, 2.1 and 2.2 of DeFT2015, we focused on Machine learning approaches exploiting only the texts of the tweets, with no external knowledge sources or metadata. Our goal was mainly to examine the interest of embeddings over traditional bag-of-words approach. We showed that traditional methods outperform simple deep methods (CNNs) in tasks with less classes and a sufficient number data samples for each class. Yet, for more complex tasks, deep learning has been shown to be a competitive approach, especially when combined with embeddings previously learned in an unsupervised manner and fine tuned during classification. Yet, the added-value is not proven and simple bags-of-words still appear as competitive.

The question of whether a deeper CNN architecture would be able match standard methods or even outperform them on all datasets is open for further future experimentation. Another point to investigate is the difference of results between train set (with cross-validation) and the test-set.

From the point of view of the tasks itself, we have pointed some inconsistencies in the ground-truth and explained how they challenged our machine learning techniques. More importantly, we have shown that the macro-precision is a too unstable score to evaluate the systems directly, at least for Task 2.2 in which some classes contains only a few tweets. As a result, the rankings of the participants based on this sole score, is unfortunately not reliable. On the contrary, micro-precision appears much more stable score and is more naturally optimized by usual machine learning frameworks.

  Figure 1: Macro and micro-precisions for Tasks 1, 2.1, 2.2 according to k

  For each epoch of the CNN the training set (the current IRISA AT DEFT 2015: SUPERVISED AND UNSUPERVISED REPRESENTATIONS METHODS IN SENTIMENT ANALYSIS training set of a 5-folds validation) is first randomly split into a smaller training set (90%) and a validation set (10%).

Figure 2 :

 2 Figure 2: Performance comparison of various text embedding methods with CNNs

Table 1 :

 1 Performance of Bonzaiboost in a 10-fold cross-validation2.1 PrinciplesDecision Trees are well-known classifiers based on a succession of test on the features of an example in order to determine its class. They can be easily inferred from training examples, they can deal with numeric or symbolic features, and they are able to handle any number of classes.

	Task	Parameters	Macro-precision Micro-precision
	Task 1	n = 2000d = 4	0.702	0.684
	Task 2.1 n = 100d = 3	0.712	0.717
	Task 2.2 n = 100d = 10	0.427	0.625

Table 4 :

 4 : three with static embeddings and three with furtherly Performance of the three proposed methods on the official DeFT 2015 test set

	Method

  Of course, such inconsistencies question the validity of the evaluation since the test set certainly contains identical flaws. They are also harmful for any machine learning technique during the training step. Unfortunately, this is more specifically the case for our Bayesian learning, to some extent, and for boosting. Concerning The former, one can easily understand that the kNN used to compute the likelihood will make its decision based on very close or similar examples. A similar example with a wrong label will chiefly biase the decision, especially when k is small. Thus, these inconsistencies are more particularly harmful for task 2.2, where the small number of examples for certain class requires us to set k to such small values. The boosting is also known to sensible to low quality training data. Since more weight is given to misclassified examples at each iteration, the inconsistent examples presented above will receive more and more weight and thus biased the final combination of weak learners[START_REF] Long R | Random classification noise defeats all convex potential boosters[END_REF]

		le développement des énergies renouvelables"
		http://t.co/TYyr2jFR81
	AMOUR	j'ai envie d'autres paysages que le vide et les cinq
		pauvres éoliennes de l'aube
	AMOUR	Les sénateurs écologistes fans de @RoyalSegolene »
		http://t.co/kSP3l2cv5s
	Most striking, very similar tweets may receive different annotations (here, labels for tasks 1 and 2.1):
	+/NONE	@fanph94 3/4: Lorsque la combustion est optimum, les
		particules fines émises sont composées de sels alcalins
		peu nocifs
	=/INFORMATION	@fanph94 4/4: Combustion de qualité + combustible
		sec et propre = quantités de particules fines émises
		réduites et moins nocives
	This inconsistencies are even more obvious with quasi-identical tweets:
	=/INFORMATION	#TribunedeGenève . L'Etat s'est trouvé face à un
		Diogène industriel: Trois cents tonnes de déchets
		toxiques à ... http://t.co/b4lJ9UsBrS
	+/NONE	L'Etat s'est trouvé face à un Diogène industriel: Trois
		cents tonnes de déchets toxiques à assainir. ...
		http://t.co/m8MeDGAvRg #Genève
	=/INFORMATION	Développement durable : 20 ans après le Caire, l'ONU
		réaffirme le rôle central des gens: A l'ouver...
		http://t.co/q9gD1sMXOQ RT @Mediaterre
	+/OPINION	Développement durable : 20 ans après le Caire,
		l'ONU réaffirme le rôle central des gens
		http://t.co/XCaVGb16F6
	+/OPINION	Développement durable : 20 ans après le Caire,
		l'ONU réaffirme le rôle central des gens
		http://t.co/LUelHU4flR #ecologie Mediaterre

Table 5 :

 5 Macro and Micro-precisions computed over the dataset as a whole or divided into 30 subsets account by our simple machine learning frameworks.

	IRISA AT DEFT 2015: SUPERVISED AND UNSUPERVISED REPRESENTATIONS METHODS IN SENTIMENT
		ANALYSIS
	System	macro-precision micro-precision
	S1 (whole dataset)	0.3696	0.5885
	S2 (whole dataset)	0.4485	0.6265
	S1 (average)	0.3563	0.5885
	S2 (average)	0.3744	0.6265

http://bonzaiboost.gforge.inria.fr/

Acknowledgement

This work was partly funded via the CominLabs excellence laboratory financed by the National Research Agency under reference ANR-10-LABX-07-01.

Emb. initialization

Fine These methods seem to perform the best. The unsupervised representation learning brought initial advantage (faster convergence). Fine-tuning the embeddings contributed to a very small advantage, except for task 2.2 where the supervised fine-tuning brought a significant advantage.

Combining embeddings learned in an unsupervised manner directly on the tweets (thus enabling them to have notions of Tweeter specifics) and fine tuning them in a supervised manner while training the CNNs is the best choice for this kind of tasks, especially if there is a significantly small number of training samples and a bigger number of classes, like in task 2.2.

Performance

Table 3 shows the results of the various methods with CNNs described in this section. Macro and micro precisions are computed with the official DeFT 2015 evaluation tool. Only macro-precision is evaluated during for the challenge, but here, we report also micro-precision as it might provide a better performance measure for this type of multiclass classification problems.

All the methods were evaluated with a 5-folds cross-validation (80% training and 20% test for each fold). It is clear that the best methods consists of training word embeddings in an unsupervised manner directly on tweets. Additionally supervised fine-tuning improves the performance, but just slightly.

Training embeddings in generic big corpus for specific classification tasks (like short tweets) does not seem to be a feasible method.

Random initialization of embeddings and supervised learning seems to also be feasible. One could think that this method is faster than training unsupervised embeddings first, but unsupervised word representation methods like word2vec [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] are very fast (especially in small datasets like this one) and significantly improves the speed of convergence and precision.

INFORMATION @ONPCofficiel Sortir du nucléaire oui, à condition d'avoir des nouvelles énergies plus écologiques, Cécile Duflot! POSITIVE_SURPRISE @LoireBretagne On s'étonne qu'elle soit ouverte, cette pêche à l'anguille. Sauf si pêcher une espèce menacée est une forme de protection... This even more problematic with less-populated classes; here are three of the eight tweets labeled as AMOUR (task 2.2) in the training data.


Mathieu Des Noes
email: mathieu.desnoes@cea.fr

Valentin Savin
email: valentin.savin@cea.fr

Jean Marc Brossier
email: jean-marc.brossier@gipsa-lab.grenoble-inp.fr

Laurent Ros
email: laurent.ros@gipsa-lab.grenoble-inp.fr

Iterative decoding of Gold sequences

Gold sequences are widely used in communications and positioning systems for synchronization purposes or spread spectrum transmissions. This paper addresses the decoding of the initial state of a Gold sequence. This can be used to detect a harmful interferer closed to a 3G femtocell base station and implement interference mitigation techniques. The decoder implements an iterative message-passing algorithm which is built upon a parity check matrix. Thus, it depends on the coding properties of Gold codes. In this paper, we synthesize the coding properties of Gold codes and use them to compute the number of parity check equations of weight t = 3, 4 or 5. Eventually, the impact of the parity check equations used for decoding is highlighted.

INTRODUCTION

Gold sequences form a family of binary sequences with excellent correlation properties [START_REF] Mceliece | Finite fields for computer scientists and engineers[END_REF]. Hence, they are widely used for synchronization purpose in wireless communications and positioning systems, and also for scrambling in multi-user asynchronous CDMA systems [START_REF]3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Spreading and modulation (FDD)[END_REF] [START_REF] Kaplan | Understanding GPS: principles and applications[END_REF]. A Gold sequence z is generated with a preferred pair of m-sequences x and y [START_REF] Mceliece | Finite fields for computer scientists and engineers[END_REF].

The conventional method to synchronize with a Gold sequence is to correlate the received signal with a replica of the searched sequence [START_REF] Polydoros | A unified approach to serial search spreadspectrum code acquisition-part I: general theory[END_REF] [START_REF] Akopian | Fast FFT based GPS satellite acquisition methods[END_REF]. If a correlation peak is observed and is above a given threshold, the synchronization is declared. An alternative method consists in performing detection through a decoding of the received sequence. In fact, a m-sequence generator can be regarded as a linear code generator. It is thus possible to detect a transmitted sequence with a suitable decoder. This solution was originally proposed in cryptography for fast correlation attacks on stream ciphers [6][7]. This has been applied more recently in wireless communications and localization [START_REF] Chugg | A new approach to rapid PN code acquisition using iterative message passing techniques[END_REF] [START_REF] Kerr | Iterative signal processing for blind code phase acquisition of CDMA 1x signals for radio spectrum monitoring[END_REF][10] [START_REF] Noes | Blind identification of the uplink scrambling code index of a WCDMA transmission and application to femtocell networks[END_REF]. Exploiting the unique properties of theses sequences, an iterative message-passing algorithm can be implemented to decode the received signal [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF]. All these papers focus on the decoding of m-sequences [START_REF] Mceliece | Finite fields for computer scientists and engineers[END_REF]. A notable exception is [START_REF] Principe | Performance evaluation of message-passing-based algorithms for fast acquisition of spreading codes with application to satellite positioning[END_REF] which proposes a decoding procedure for Gold sequences. The approach consists in searching parity check equations which are multiple of g z (x), the generator polynomial of sequence z. The authors did not detailed the coding properties of Gold sequences. One objective of this paper is to clarify this point.

The decoding procedure is known to be sensitive to the weight of the parity check equations [START_REF] Santhi | On the effect of parity-check weights in iterative decoding[END_REF]. It is given by the number of non zero coefficients of the equation. It is thus fundamental to study these parity check equations for Gold sequences. In this paper, we first provide a synthesis of Gold sequence properties from the viewpoint of coding theory. A Gold sequence is a codeword of a cyclic linear code characterized by the generator polynomials of m-sequences x and y. For the decoding procedure, we are interested in the properties of the dual code, since it defines the parity check equations used for decoding. This work will be helpful for evaluating the number of parity check equations of weight t = 3, 4 or 5. This tells us, if these equations at least even exist and if yes, how many can be used for decoding. The goal is to use parity check equations having the smallest weight t for decoding.

The number of parity check equations of weight t = 3 and 4 has already been computed by Kasami in [START_REF] Kasami | Some results on cyclic codes which are invariant under the affine group and their applications[END_REF]. In this paper we provide an analytical expression for the number of parity check equations of weight t = 5 when the degree of the generator polynomial r is odd. To the best of our knowledge, this has not been given in the literature yet. Knowing this number is important because there is no parity check equation of weight t < 5 when r is odd. Then, we have measured the probability of missed detection as a function of t and the number of equations used for decoding. This highlights the decisive impact of selecting an even or an odd degree r.

The paper is organized as follows. Section I details the generation of Gold sequences and the selection of the "preferred pair" of m-sequences used for generating a Gold sequence. Section II recalls some properties of linear cyclic codes and apply them to Gold codes. The number of parity check equations of weight t = 3, 4 or 5, when r is even or odd, is also given. Section III details the message-passing algorithm used for decoding. Section IV presents the decoding performance as a function of the degree r, the weight t and the length of the message at the input of the decoder. Eventually, Section V concludes this paper.

Notations: a sequence will be written with upper case with the bipolar representation (Z(k) ∈ {-1, +1}) and with lower case with the binary representation (z(k) ∈ {0, 1}). x mod n is the value of x modulo n. The index of a sequence is computed modulo the sequence's length N : s(k) = s(k mod N ). The modulo 2 binary addition is noted with symbol ⊕.

I. GENERATION OF GOLD SEQUENCES

A Gold sequence z is obtained by the binary addition of a "preferred pair" of m-sequences x and y [START_REF] Gold | Optimal binary sequences for spread spectrum multiplexing[END_REF] :

z(k) = x(k) ⊕ y(k) (1)
We will first review the main properties of m-sequences and then explain the meaning of "preferred pair".

A m-sequence is generated with a Linear Feedback Shift Register (LFSR) sequence generator. The feedback taps are given by the generator polynomial g(x) = r k=0 g k x k . It is primitive for a m-sequence, so that the sequence has the largest period among all the sequences that can be generated with a LFSR having the same number of registers. This is why they are named maximal length sequences, and in short msequences. If the primitive polynomial g(x) has degree r, the period is n = 2 r -1. There exist two structures for generating these sequences: Galois and Fibonacci generators [START_REF] Peterson | Introduction to spreadspectrum communications[END_REF]. They are depicted in Fig. 1 and Fig. 2. These two generators give sequences which are simply shifted with respect to each other. For instance, if the shift registers of the two generators are loaded with the same values, the Fibonacci architecture will generate sequence x(0), . . . , x(n -1), while the Galois one will generate sequence x(i), . . . , x(n -1), x(0), . . . , x(i -1) for some i > 0.

There exists a decimation factor d between any two msequences x and y having the same length [START_REF] Mceliece | Finite fields for computer scientists and engineers[END_REF] : y(k) = x(dk).

A "preferred pair" of m-sequences is such that d = 2 e + 1 and e satisfies [START_REF] Gold | Optimal binary sequences for spread spectrum multiplexing[END_REF] : gcd(2 e + 1, 2 r -1) = 1. This condition is met if:

r = 0 mod(4) ⇔ r is odd or r = 2 mod(4) (2)
and gcd(e,r) = 1 if r is odd

2 if r = 2 mod(4) (3)
Let SR x (i) be the content of the i th shift-register of sequence x. The state of sequence x is the vector

A x = (SR x (0) • • • SR x (r -1)
). With the Fibonacci generator, the initial state of a sequence x is given by its first r chips :

x(0) = SR x (0), • • • , x(r -1) = SR x (r -1
). This property is not valid for the Galois generator.

D D D D D + + + + x(k) x(k+r) x(k+r-1) x(k+r-2) x(k+2) x(k+1) g 0 =1 g r =1 g r-1 g r-2 g 2 g 1

II. DECODING OF GOLD SEQUENCES

A. Cyclic code properties

We will first recall some useful definitions concerning cyclic codes. They can be found in chapters 1 and 7 of [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]. A linear code [n, k] transforms an input vector u

= (u 0 , • • • , u k-1 ) containing the information message into a codeword c = (c 0 , • • • , c n-1 )
. It is specified either by its generating or parity check matrices G and E :

c = u G Ec T = 0 (4)
In this article, we will often use the polynomial representation of a codeword. This will be very useful to handle parity check equations. It is defined as follows : each code-

word c = (c 0 , • • • , c n-1 ) is associated with the polynomial c(x) = c 0 + c 1 x + • • • + c n-1 x n-1 .
In the sequel, we use the conventional and polynomial representations indistinctly. Assume that f (x) is the generator polynomial of code C, then every codeword c(x) is a multiple of f (x) modulo x n -1.

A cyclic code C fulfills the following property : if

(c 0 , • • • , c n-1 ) ∈ C then (c n-1 , c 0 , • • • , c n-2 ) ∈ C.
As a consequence, shifting one bit of the codeword c is represented by the polynomial xc(x). Hamming, BCH, simplex and Gold codes belongs to this family of linear cyclic codes.

Let C be a linear code [n, k], its dual C ⊥ is the set of vectors orthogonal to every codeword of C :

C ⊥ = {u | u.v = 0 for all v ∈ C} (5)
u.v is the conventional scalar product between vectors u and v.

When c ∈ C ⊥ , c(x) is referred as a parity check polynomial of C. The weight of a codewords is defined by the number of non-zero elements (Hamming weight). By extension, this is also used for parity check polynomials. The dual code of a cyclic code is also cyclic. Assume that f (x) is the generator polynomial of code C, the check polynomial of C is defined by: h(x) = (x n -1)/f (x). The generator polynomial of C ⊥ is the reciprocal of the check polynomial : f ⊥ (x) = x r h(x -1 ).

B. Gold sequence coding properties

In the domain of error correcting codes, a m-sequence is a codeword of a simplex code [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]. A simplex code S x is a cyclic linear code [n = 2 r -1, k = r] which check polynomial is g x (x). A Gold code is also a cyclic linear code [n = 2 r -1, k = 2r]. The information bits are loaded at initialization in the r shift registers of the 2 m-sequences x and y. The codeword is the generated sequence of length n = 2 r -1 bits. The dual of a Gold code is the intersection of the dual codes of the two simplex codes S x and S y used to generate the sequences x and y:

S ⊥ z = S ⊥ x ∩ S ⊥ y .
It is known from the literature that the dual code of simplex code S x is the Hamming code [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]. Let α denote the primitive root of polynomial g x (x). If c(x) ∈ S ⊥

H x = [n = 2 r -1, k = 2 r -r -1] generated by g(x)
x , it must verify c(α) = 0 [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]. Now, let's consider the case of c(x) ∈ S ⊥ z . Due to the decimation property between sequences x and y, the primitive root of g y (x) is β = α d . Thus, we shall have c(α) = c(α d ) = 0. α and β being primitive roots of g x (x) and g y (x), c(x) must be a multiple of g x (x)g y (x). As a conclusion, S ⊥ z is the set of codewords which polynomial is a multiple of g z (x) = g x (x)g y (x).

C. Number of parity check equations

Let define N * t the total number of parity check equations of weight t. Since S ⊥ z is a cyclic code, it is sufficient to enumerate only the parity check equations having a constant term equal to 1. The others are obtained by a simple cyclic shift. We note N t the number of equations having a constant term. It is related to N * t by the following equation [START_REF] Maitra | Results on multiples of primitive polynomials and their products over GF(2)[END_REF] :

N t = t 2 r -1 N * t (6)
Let A j denote the number of Gold sequences of weight j. The Pless equality links A j and N * j by the following equation [START_REF] Pless | Power moment identities on weight distributions in error correcting codes[END_REF]:

N j=0 (N -j) t A j = t j=0 γ j N * j (7)
where

γ j = t k=0 k!S(t, k)2 2r-k N -j N -k (8)
S(t, k) is a Stirling number of the second kind:

S(t, k) = 1 k! k i=1 (-1) k-i k i i t (9)
If the A j 's are known, N * t are computed by solving iteratively the set of t equations:

γ t N * t = N j=0 (N -j) t A j - t-1 j=0 γ j N * j ( 10
)
Since the all '0' codeword belongs to S z , we have A 0 = N * 0 = 1. Moreover N * 1 = 0 otherwise the Gold sequence would be equal to the all '0' vector whatever the initial state. Similarly, N * 2 = 0 otherwise, due to the "add and shift" property of msequences, their should exist a τ such that x(k)⊕y(k +τ ) = 0 for all k. This is not possible because sequences x and y are generated by distinct primitive polynomials.

Coefficients A j have been evaluated by Kasami when he studied the cross-correlation properties of m-sequences. If δ = gcd(r, e) = gcd(r, 2e), then [START_REF] Kasami | Some results on cyclic codes which are invariant under the affine group and their applications[END_REF]:

A 0 = 1 A 2 r-1 -2 (r+δ)/2-1 = (2 r-δ-1 + 2 (r-δ)/2-1 )N A 2 r-1 +2 (r+δ)/2-1 = (2 r-δ-1 -2 (r-δ)/2-1 )N A 2 r-1 = (2 r -2 r-δ + 1)N A j = 0 elsewhere (11)
It is remarkable that these numbers do not depend on the choice of the preferred pair of m-sequences. It is sufficient to satisfy the decimation property defined for selecting a preferred pair (see Section I).

Practically, δ is defined as follows:

• if r = 2 mod (4): δ = 2 • if r is odd : δ = 1
Inserting ( 11) in [START_REF] Noes | Blind identification of the scrambling code of a reverse link CDMA 2000 transmission[END_REF], we have the following results:

• if r is odd : N 3 = N 4 = 0
• If r is even and r = 2 mod (4):

N 3 = 1 and N 4 = (2 r -4)/3 (12)
These results have been already obtained by Kasami using a different approach [START_REF] Kasami | Some results on cyclic codes which are invariant under the affine group and their applications[END_REF].

When r is odd, there is no parity check equation of weight t < 5. This has an impact on the decoding performance which are better for smaller t [START_REF] Santhi | On the effect of parity-check weights in iterative decoding[END_REF].

We will now derive a theoretical formula of N 5 when r is odd.

To do so, we need to solve [START_REF] Noes | Blind identification of the scrambling code of a reverse link CDMA 2000 transmission[END_REF] with t = 5. Considering that N * 0 = 1 and N * 1 = N * 2 = N * 3 = N * 4 = 0, this reduces to:

N * 5 = 1 γ 5   N j=0 (N -j) 5 A j -γ 0   (13)
It is thus required to compute the 3 terms : γ 5 , γ 0 and N j=0 (N -j) 5 A j . Applying directly (8), we get:

γ 5 = 5!2 2r-5 γ 0 = 2 2r-5 (N 5 + 10N 4 + 15N 3 -10N 2 ) (14)
The third term is equal to:

N j=0 (N -j) 5 A j = a 5 (2 2r -1) + 5a 4 (2 2r-1 -2 r-1 ) +10a 3 (2 r-2 -2 2r-2 ) +10a 2 (2 3r+δ-3 -2 2r+δ-3 ) +5a(2 4r+δ-4 -2 3r+δ-4 ) +N 5 + 2 4r+2δ-5 -2 3r+2δ-5 (15) where a = 2 r-1 -1
The powers of a and N need to be expanded to compute N * 5 . We eventually obtain:

N * 5 = 2 5r-5 -11 2 4r-5 + 26 2 3r-5 -16 2 2r-5 5!2 2r-5 (16)
Finally, N 5 is given by:

N 5 = (2 r-1 -1)(2 r-1 -4) 6 (17)
Table I summarizes the values of N 3 , N 4 and N 5 according to the primitive polynomial degree r.

N3 N4 N5 r = 2 mod 4 1 (2 r -4)/3 - r is odd 0 0 (2 r-1 -1)(2 r-1 -4) 6
In addition, the only parity check polynomial existing for t = 3 and r even is known :

h 3 (x) = x 2(2 r -1)/3 + x (2 r -1)/3 + 1 (18)
Indeed, if r is even, h 3 (x) is divisible by every primitive polynomial of length r [START_REF] Huber | Some comments on zech's logarithms[END_REF]. This means that h 3 (α) = h 3 (α d ) = 0 and, invoking the minimal property of g x (x) and g y (x), h 3 (x) is a multiple of g x (x)g y (x). It is thus the polynomial representation of the only parity check equation of weight t = 3. This confirms the parity check polynomial found in [START_REF] Principe | Performance evaluation of message-passing-based algorithms for fast acquisition of spreading codes with application to satellite positioning[END_REF] for the Gold sequence used in the GPS.

Table II shows the number of parity check equations of weight t = 4 or t = 5, depending on r. For r even, only N 4 has been computed since there are obviously enough parity check equations of weight t = 4. Using an exhaustive search strategy, these theoretical values have been validated for r 11. One observes that there are plenty of parity check equations available. This will not be a limiting factor.

III. ITERATIVE MESSAGE-PASSING DECODING

A. Iterative message-passing algorithm

The principle for the decoding of a Gold sequence is to build a sparse parity check matrix E and then apply an iterative message passing algorithm on the induced Tanner graph [13][12][22]. This provides an approximation of the MAP decoding of the sequence.

The received sequence is noted z and R(i) = (-1) z(i) + w(i) is the observation of variable z(i) at the decoder input. w(i) is an additive white gaussian noise of variance σ 2 0 . It is assumed the receiver observes M elements of the sequence: R(0), • • • , R(M -1). For practical reasons, the decoder implements a Min-Sum (MS) algorithm [START_REF] Wiberg | Codes and decoding on general graphs[END_REF] since it is known to be insensitive to a uniform scaling of input variables R(i)'s.

B. Parity check matrix

Let consider a sparse parity check polynomial of degree m: c(x) = m k=0 c k x k . Since the dual code is cyclic, all the codewords x i c(x) belong to S ⊥ z and are parity check equations of S z . It is thus easy to build a parity check matrix based on c(x).

Assuming the entire sequence is observed, the parity check matrix is circulant and square (M = n) :

E =               c 0 • • • • • • c m 0 • • • • • • 0 0 c 0 • • • • • • c m 0 • • • 0 . . . .
0 0 • • • • • • 0 c 0 • • • • • • c m c m • • • • • • • • • 0 c 0 • • • c m-1 . . . . . . • • • • • • 0 . . . . . . . . . c 1 • • • c m 0 • • • • • • 0 c 0               (19)
In order to improve decoding performance, an usual design strategy is to increase the column weight of the parity check matrix, while keeping the row weight constant. Having a large degree improves the probability to correct an error on that variable because it receives more information from its neighboring nodes. This is achieved by concatenating parity check matrices such as [START_REF] Maitra | Results on multiples of primitive polynomials and their products over GF(2)[END_REF], generated by different parity check polynomials. The overall parity check matrix becomes:

E eq =     E 0 E 1 . . . E Neq-1     (20)
where N eq is the number of different parity check polynomials used for decoding.

C. Initial state estimation

The overall decoding operation is modeled as a function dec(.) that produces a status indicator I c and the estimated initial state of sequence z ( Âz ) :

{I c , Âz } = dec(R(0), R(1), • • • , R(M -1)) (21)
I c is the indication function of the decoder. It outputs a 1 if the decoder finds a valid codeword :

I c = 1, if all parity check equations are satisfied 0, otherwise (22)
If the decoding is successful (I c = 1), the soft decision output of the decoder is converted into a binary value (0 or 1) with a hard decision rule. Then, according to the Fibonacci representation of Fig. 1, the first 2r bits of the codeword represent the state of the shift registers of sequence z at initialization.

There exists a transposition matrix T Gold between the state of sequences z and x and y. It is defined by (27) in the Appendix. However, it is valid only with the Galois representation.

It is thus required to first defined the transposition matrix T F G between a Fibonacci and a Galois representation. It is defined by [START_REF] Penzhorn | Computation of low-weight parity checks for correlation attacks on stream ciphers[END_REF] in the Appendix. Eventually, the initial state of sequences x and y with the Fibonacci representation are obtained as follows :

Âx = T -1 F G,x [I r 0 r ]T -1 Gold T F G,z Âz Ây = T -1 F G,y [0 r I r ]T -1 Gold T F G,z Âz (23)

IV. SIMULATION RESULTS

The performance of the algorithm is measured by the probability of missed detection P m , defined as follows : The decoder stops when either all the parity check equations are satisfied or the maximum number of iteration N iter = 60 is reached. The Gold sequence used for the evaluation are noted with the octal representation of the generator polynomials of sequence x and y (e.g. : 2157-3515). The parity check equations used for decoding are listed in tables III and IV. We have used the following notation: c l (x) = x m +x i +x j +x k +1 for t = 5 and c l (x) = x m + x i + x j + 1 for t = 4. For r = 10, the parity check equation of weight t = 3 is given by (18) : c(x) = x 682 + x 341 + 1.

Fig. 3 shows the probability of missed detection as a function of the number of parity check polynomials used for decoding for r = 10. One observed a large improvement from N eq = 2 to 4, then the gain decreases. The overall gain from N eq = 2 to 10 is about 4.5 dB at P m = 0.01. For N eq > 8 the complexity of the decoder increases with the number of parity checks and there will be a trade-off between complexity and performance. We also plot the probability of missed detection measured for the Gold sequence (2011 -3515) with N eq = 10. One can observe that performances are identical. It means that from the decoding perspective, all Gold sequences of the same degree r can be decoded with the same probability of detection. Fig. 4 shows the probability of missed detection measured with the Gold sequence (4005,4445) of degree r = 11. We also observe a gain when N eq increases. Compared to Fig. 3, one can observe a loss of more than 2 dB for N eq = 10. This is due to the weight of the parity check polynomials t = 5, which degrades the performance. In this paper we have investigated the iterative decoding of Gold sequences. This allows to perform a blind estimation of the initial state of the sequence if the generator polynomials are known. We detailed the coding properties of Gold codes and gave the number of parity check equations of weight t = 3, 4 or 5. This could be used for estimating the least degree of parity check equations of weight t [START_REF] Maitra | Results on multiples of primitive polynomials and their products over GF(2)[END_REF]. This is a very valuable information for the search of parity check equations [START_REF] Penzhorn | Computation of low-weight parity checks for correlation attacks on stream ciphers[END_REF] [START_REF] Chose | Fast correlation attacks: An algorithmic point of view[END_REF]. Simulation results show that increasing the number of parity check polynomials improves noticeably the probability of detection. The selection of the degree r of the generator polynomial has a significant impact on the decoding performance. When r is odd, there are only parity check polynomials of weight t ≥ 5. This degrades the decoding performance compared to configurations with t = 3 and 4 obtained when r is even.

APPENDIX

A. Conversion between Galois and Fibonacci generator initial states

Let a Gal (k) and a F ib (k) be the state of the k th register with the Galois and Fibonacci's representations. They are linked as follows [17, page 106] :

a Gal (k) = k i=0 a F ib (i)g(k -i) k = 0, . . . , r -1
This can also be written with a matrix-vector notation. Let A Gal and A F ib be the vectors containing the state of the shift registers according to the Galois and Fibonacci representations. They are related by a transposition matrix T F G : A Gal = T F G A F ib . The elements of matrix T F G are defined by :

T F G (i, j) = g(i -j) if j ≤ i 0 if j > i (24)
On the other hand, the transposition from the Galois to the Fibonacci representation is obtained by the inversion of matrix T F G :

T GF = T -1 F G

B. Initial state of a Gold sequence

In this section, the relation existing between the initial state of a Gold sequence z and its preferred pair of m-sequences x and y is established. This relies on the property of LFSR sequence with the Galois representation. This is why sequences are designated with a subscript 'Gal' in the remaining part of this section.

Let SR z Gal (k) be the state of the k th shift-register of sequence z Gal with the Galois representation and K z Gal (x) = 2r-1 k=0 SR z Gal (k)x k be its polynomial representation. Likewise K x Gal (x) = r-1 k=0 SR x Gal (k)x k and K y Gal (x) = r-1 k=0 SR y Gal (k)x k are the equivalent representations for sequence x Gal and y Gal .

Let also define x Gal (x) = x Gal (0)+x(1) Gal x+• • •+x Gal (N -1)x N -1 as the polynomial representation of sequence x Gal . Likewise, y Gal (x) is the polynomial representation of sequence y Gal . With the Galois representation, the sequence polynomial is the result of the following division [START_REF] Peterson | Introduction to spreadspectrum communications[END_REF] :

x Gal (x) = K x Gal (x) g x (x)
Since z Gal (k) = x Gal (k) ⊕ y Gal (k), we have:

z Gal (x) = K x Gal (x) g x (x) + K y Gal (x) g y (x) = g x (x)K y Gal (x) + g y (x)K x Gal (x) g x (X)g y (x)
This means that sequence z Gal can be generated with polynomial g z (x) = g x (x)g y (x), and the initial state is related to the ones of sequences x Gal and y Gal by :

K z Gal (x) = g x (x)K y Gal (x) + g y (x)K x Gal (x) (25)
Let define A z Gal = (SR z Gal (0) • • • , SR z Gal (2r -1)) T , A x Gal = (SR x Gal (0) • • • , SR x Gal (r -1)) T and A y Gal = (SR y Gal (0) • • • , SR y Gal (r-1)) T , the initial state of sequences z Gal , x Gal and y Gal .

Rewritting [START_REF] Chose | Fast correlation attacks: An algorithmic point of view[END_REF], A z Gal , A x Gal and A y Gal are linked by :

A z Gal = T Gold (A T x Gal A T y Gal ) T ( 26
)
T Gold is the state transposition matrix defined by :

T Gold = [T y T x ] (27)
with T x (resp. T y ) being defined as follows:

T x =           g x (0) 0 • • • 0 . . .
0 0 • • • g x (r)           (28)

Fig. 1 .Fig. 2 .

 12 Fig. 1. Fibonacci feedback generator

P

  d = P (Ic = 1 and Âx = A x and Ây = A y ) P m = 1 -P d

Fig. 3 .

 3 Fig. 3. Probability of missed detection -r = 10

Fig. 4 .

 4 Fig. 4. Probability of missed detection -r = 11

TABLE I .

 I

NUMBER OF PARITY CHECK EQUATIONS OF WEIGHT t.

TABLE II .

 II NUMBER OF PARITY CHECK EQUATIONS OF WEIGHT t = 4AND 5.

	r	6	7	9	10	11	18
	N4	20	0	0	10710	0	173910
	N5	-	630	10710	-	173910	-

TABLE III

 III

	.	PARITY CHECK EQUATIONS FOR SEQUENCE (2157,3515).
			sequence (2157,3515)	sequence (2011,3515)
			m	i	j	m	i	j
	c1		171	106	54	111	106	65
	c2		185	166	4	131	32	31
	c3		205	168	28	151	102	73
	c4		222	77	22	194	179	166
	c5		230	98	31	222	212	130
	c6		258	180	133	244	163	6
	c7		271	255	189	256	248	25
	c8		293	101	15	262	64	62
	c9		307	42	7	288	173	87
	c10	314	229	219	298	159	84

TABLE IV .

 IV PARITY CHECK EQUATIONS FOR SEQUENCE (4005,4445).

				m	i	j	k
			c1	114	78	49	37
			c2	116	55	23	21
			c3	127	58	33	5
			c4	130	127	80	11
			c5	141	109	59	36
			c6	141	121	101	17
			c7	150	101	75	25
			c8	155	79	51	39
			c9	178	164	159	5
			c10	183	161	149	2
	-13 10	-12	-11	-10	-9	-8	-7	-6	-5	-4