Julien Ah-Pine

On aggregation functions based on linguistically quantified propositions and finitely additive set functions

Keywords:

We study aggregation functions defined as convex combinations of the linguistically quantified propositions "at least k criteria are satisfied". Our approach is similar to the TOWA function in spirit but instead of using a maxitive measure we propose to rely on a real-valued finitely additive set function. This assumption leads to a new framework. However, it is combinatorial by nature and, in general, it produces functions with high computational costs. Therefore, we analyze some particular settings and introduce new aggregation functions which can alleviate the combinatorial burden thanks to several combinatorial identities. These methods have interesting features and in particular, some of them make it possible to set different types of relationships between criteria by allowing the use of different t-norms. The interest of our proposals is illustrated on a famous example which cannot be modeled by classical aggregation functions such as the Choquet integral.

Introduction

Aggregation operators are mathematical functions that combine several input values into a unique representative one. These operators have been studied from different theoretical viewpoints and they have also been applied

Email address: julien.ah-pine@univ-lyon2.fr (Julien Ah-Pine) in many application fields such as multicriteria decision making, statistics, information fusion or pattern recognition among others [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications)[END_REF]. From a general standpoint, aggregation operators play an important role in problems where one needs to fuse information coming from different criteria (or attributes or sources). We assume that these pieces of information are numerical measures that all belong to the closed interval [0, 1]. Then an aggregation operator aims at synthesizing the latter numerical ratings into a unique global score in [0, 1]. More formally, an aggregation operator is defined as follows.

Definition 1. An aggregation operator is a function1 F : [0, 1] N → [0, 1] which fulfills the following requirements:

• F (0, . . . , 0) = 0,

• F (1, . . . , 1) = 1,

• F is non-decreasing in each variable.

Note that when N = 1, we have, ∀a ∈ [0, 1] : F (a) = a.

In this paper, we define new aggregation operators that can be formulated in the context of multicriteria decision making. Accordingly, the basic definitions and notations we use, are from this field. In that case, aggregation functions are used to help a decision maker when several alternatives are evaluated in regard to many criteria. The overall scores they produce allow the decision maker to better compare the alternatives and select the most performing ones. However, this implies that the aggregation function is able to reflect the decision maker's preference model.

In [START_REF] Bellman | Decision-Making in a Fuzzy Environment[END_REF][START_REF] Yager | Quantifiers in the formulation of multiple objective decision functions[END_REF][START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF], it was shown that multicriteria decision problems can be formulated by means of quantified linguistically propositions. Some basic examples of such statements are "all criteria are satisfied", "most of criteria are satisfied" and so on. Then using tools from fuzzy set theory, one can evaluate the membership values of these propositions for all alternatives, and use the latter measures to make decisions.

In our case, we focus on propositions of the type "at least k criteria are satisfied" where k is a non-negative integer. These events are studied and encountered in the so-called TOWA2 function [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF]. The latter aggregation op-erator is a convex combination of the membership functions of fuzzy subsets "at least k criteria are satisfied" with k varying from 1 to N .

The general formulation of the aggregation functions we propose share common roots with the TOWA method. Yet, our framework assumes a completely different type of measure for representing uncertainty. In [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF] a maxitive measure is employed whereas we suggest an additive set function.

However, using such a set function generally leads to combinatorial formulas with high computational complexities. But, as we will see, this combinatorial burden can be dramatically alleviated in several particular cases.

Furthermore, the aggregation functions we introduce, present interesting features in comparison to the TOWA operator and the Choquet integral as well. These properties make our proposals interesting both from a theoretical and a practical standpoints as we shall argue in the sequel.

To introduce our method we proceed as follows. In Section 2, we review the approach developed in [START_REF] Yager | Quantifiers in the formulation of multiple objective decision functions[END_REF][START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF] which leads to the formulation of the TOWA function in [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF]. Then in Section 3, we present our framework and we subsequently introduce several aggregation functions with their respective features. Next, in Section 4, we illustrate the interest of our different proposals using a well-motivated problem. We finally synthesize the findings of the paper and discuss some future works in Section 5.

Formulating multicriteria decisions and the TOWA operator

In this section, we discuss the previous works that have paved the way for our approach. In Paragraph 2.1, we recall the seminal framework developed by Bellman and Zadeh to cast multicriteria decision functions in terms of fuzzy sets. In the following parts, we detail some extensions proposed by Yager in a series of papers and we subsequently present the TOWA operator in Paragraph 2.2, the attitudinal character index in Paragraph 2.3 and the related OWA function in Paragraph 2.4. Then in Paragraph 2.5, we underline some possible extensions of these works in order to position our contribution.

Modeling multicriteria decisions by means of fuzzy subsets

Let X and A be two non-empty and finite sets of alternatives and criteria respectively. We denote by x an alternative in X, and we assume A contains N criteria which are denoted by A i with i = 1, . . . , N . Then let S designate a class of N fuzzy subsets of X where, for all i = 1, . . . , N , S i is the subset of alternatives such that "criterion A i is satisfied". For any fuzzy subset S i , we denote by µ S i its membership function. Given an alternative x, µ S i (x) is a real number in [0, 1] which can be interpreted as a degree of satisfaction: the closer to 1 the value µ S i (x) is, the more alternative x satisfies the criterion A i .

In [START_REF] Bellman | Decision-Making in a Fuzzy Environment[END_REF], Bellman and Zadeh propose a framework to define a decision function as a fuzzy subset of X. They particularly suggest to frame a decision function as the intersection of fuzzy subsets representing the different goals and the different constraints the alternatives should satisfy. They call this method the "confluence of goals and constraints". Such a general conjunction can be linguistically stated as "all goals and all constraints are satisfied". The best alternatives are the ones which have the greatest membership values in this fuzzy subset.

The TOWA operator

In [START_REF] Yager | Quantifiers in the formulation of multiple objective decision functions[END_REF][START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF], Yager proposes some extensions of Bellman and Zadeh's approach. He defines a decision function as a quantified linguistically proposition. One particular formulation is the following one: "Q objectives are satisfied" where Q is a linguistic quantifier. Yager makes the distinction between absolute and relative linguistic quantifiers. "At least one", "at least k" or "all", are instances of absolute quantifiers while examples of relative quantifiers could be "most", "few" or "many". The former type can be understood as fuzzy subsets of non-negative numbers whereas relative quantifiers are fuzzy subsets of the unit interval.

We are interested in absolute quantifiers and we focus on fuzzy subsets of X which correspond to the events "at least k criteria are satisfied" where k = 1, . . . , N . We denote these fuzzy subsets by E N k and they can be formally defined as follows:

E N k = 1≤i 1 <...<i k ≤N (S i 1 ∩ . . . ∩ S i k ) . (1)
There are many ways to determine µ E N k . The approach proposed in [START_REF] Yager | Quantifiers in the formulation of multiple objective decision functions[END_REF][START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF][START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF] amounts to assuming a possibility measure. In this case, µ is maxitive and given two subsets S, S , their fuzzy union is obtained through the following membership function: µ S∪S = max(µ S , µ S ). Therefore, the membership function of E N k can be written as follows:

µ E N k = max 1≤i 1 <...<i k ≤N µ S i 1 ∩...∩S i k . (2)
Then in order to define the membership functions of the fuzzy intersections involved in [START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications)[END_REF], one can use any triangular norm (t-norm) [START_REF] Menger | Statistical metrics[END_REF][START_REF] Schweizer | Probabilistic metric spaces[END_REF][START_REF] Klement | Triangular norms[END_REF]. Tnorms represent extensions of the intersection operation in the case of fuzzy subsets and they are functions

T : [0, 1] 2 → [0, 1] such that, ∀a, b, c ∈ [0, 1]: • T is commutative: T (a, b) = T (b, a). • T is associative: T (T (a, b), c) = T (a, T (b, c)). • T is non-decreasing: T (a, b) ≤ T (a, c) whenever b ≤ c. • 1 is a neutral element: T (a, 1) = a.
There are four fundamental t-norms which are the following ones:

• The minimum 3 t-norm: ∀a, b ∈ [0, 1] : T M (a, b) = min(a, b). • The product t-norm: ∀a, b ∈ [0, 1] : T P (a, b) = ab. • The Lukasiewicz t-norm: ∀a, b ∈ [0, 1] : T L (a, b) = max(a + b -1, 0). • The drastic t-norm: ∀a, b ∈ [0, 1] : T D (a, b) = min(a, b) if max(a, b) = 1,
and

T D (a, b) = 0 otherwise. It is interesting to mention that ∀a, b ∈ [0, 1] : T M (a, b) ≥ T P (a, b) ≥ T L (a, b) ≥ T D (a, b
). Thereby, one can use different t-norms to make the fuzzy intersections more or less strong and hence, assume different sorts of relationships between the arguments.

Using t-norms in the decision function described previously, we obtain the following formula:

µ E N k = max 1≤i 1 <...<i k ≤N T (µ S i 1 , . . . , µ S i k ). (3)
Next, let us assume that for an alternative x, τ is a permutation of {1, . . . , N } such that µ S τ (1) (x) ≥ µ S τ (2) (x) ≥ . . . ≥ µ S τ (N ) (x). Since any T is non-decreasing, thus we have the following property:

max 1≤i 1 <...<i k ≤N T (µ S i 1 (x), . . . , µ S i k (x)) = T (µ S τ (1) (x), . . . , µ S τ (k) (x)). (4)
In [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF], Yager considers all events E N k with k varying from 1 to N and mix their respective membership functions using a convex combination. This approach is named TOWA4 and is defined by the following equation:

TOWA w,T (x) = 1≤k≤N w k T µ S τ (1) (x), . . . , µ S τ (k) (x) . (5)
where w = (w 1 , . . . , w N ) is a weight vector such that 0 ≤ w k ≤ 1 for all k = 1, . . . , N and 1≤k≤N w k = 1.

Different behaviors and the attitudinal character index

In TOWA, the membership function "at least k criteria are satisfied" is weighted with respect to a non-negative value that reflects the importance of the linguistic quantifier "at least k". In such a case, different weighting schemes convey different semantics to the TOWA operator. Particular and completely opposite cases are the following ones:

• If w 1 = 1 and w k = 0 otherwise, then the TOWA function reduces to the membership function of the event "at least one criterion is satisfied". • If w N = 1 and w k = 0 otherwise, then it boils down to the membership function of "all criteria are satisfied" and this specific approach pertains to the initial method from Bellman and Zadeh [START_REF] Bellman | Decision-Making in a Fuzzy Environment[END_REF].

The former weight vector leads to a complete disjunction over all S k resulting in a tolerant behavior. In that case, it is sufficient that only one criterion is well satisfied for the overall membership value to be high. In contrast, the latter setting is a complete conjunction which corresponds to a severe aggregation function. In this context, the degree of satisfaction of all criteria should be high so as to obtain a high global membership grade.

In between these two cases, one can design more compensatory aggregation functions by suitably changing the weight vector w. In order to judge whether a weighting scheme w provides a TOWA closer to a disjunctive or a conjunctive behavior, Yager adopted in [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF] the attitudinal character or orness measure which was introduced in [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decision making[END_REF]. This index denoted AC takes as an argument a weight vector w and it gives as an output a real value in [0, 1]. It is defined as follows:

AC(w) = 1≤k≤N w k N -k N -1 . (6)
The closer to 1 AC(w) is, the more TOWA T,w tends to a disjunctive behavior. Besides, it is noteworthy that a uniform weighting scheme w = (1/N, . . . , 1/N ) has an orness value of 1/2. Accordingly, one can also position the behavior of an aggregation operator with respect to this uniformly balanced case which is equivalent to the arithmetic mean.

2.4. The OWA function as a particular case of TOWA TOWA is a generalization of a well-known aggregation function also defined by Yager in [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and OWA operators[END_REF] which is called OWA 5 . It corresponds to the situation where the t-norm T in ( 5) is set to T M , the minimum operator. In that case

T M µ S τ (1) (x), . . . , µ S τ (k) (x) = min µ S τ (1) (x), . . . , µ S τ (k) (x) = µ S τ (k) (x)
and thus we have:

OWA w (x) = TOWA w,T M (x) = 1≤k≤N w k µ S τ (k) (x). (7)

Towards an extension of the TOWA operator

In the previous paragraphs, we have reviewed the TOWA operator and some of its basic properties. We end this section by underlying two remarks that allow us to motivate the approach that we present in the sequel.

On the one hand, as already mentioned, TOWA relies on a maxitive measure. Indeed, max is the standard union operator for fuzzy subsets and, as pointed out in [START_REF] Fodor | Fuzzy Set-Theoretic Operators and Quantifiers[END_REF], simplicity and idempotency are two main reasons that can explain the particular role played by this operation. Nonetheless, this is not the sole possibility. For example, one could use any triangular conorm (t-conorm) for fuzzy unions [START_REF] Menger | Statistical metrics[END_REF][START_REF] Schweizer | Probabilistic metric spaces[END_REF][START_REF] Klement | Triangular norms[END_REF]. In fact, our proposal suggests another way to deal with fuzzy subsets namely, by means of an additive set function.

On the other hand, the TOWA function given in (5) assumes only one sort of t-norm T for all fuzzy intersections. But, one could use distinct tnorms for different subsets of S and thus assume several kinds of interaction between criteria. This would extend the TOWA operator in an interesting way. However, this ideal flexibility would not be without a cost. Indeed, in order to define (5) for all x ∈ X, one should specify, in a rigorous way, a set of fuzzy intersections for all possible subsets of S. In general terms, this would require setting 2 N t-norms. In contrast, our approach enables us to define aggregation functions that allow setting different fuzzy intersections between criteria but without such a heavy computational cost.

Aggregation functions based on finitely additive set functions

Similarly to the TOWA function, our approach consists of a convex combination of membership functions of the propositions E N k = "at least k criteria are satisfied" given in [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF]. Therefore, in general terms, it is defined as follows:

A w,T = 1≤k≤N w k µ E N k , ( 8
)
where w is a weight vector and T is a t-norm (whose role shall be explained more in details in the sequel). Nevertheless, despite starting from the same general definition given in (8), our method is distinct from TOWA.

Indeed, as underlined by Dubois and Prade (see for example [START_REF] Dubois | Fuzzy sets and probability: misunderstandings, bridges and gaps[END_REF]), fuzzy sets can be approached from different viewing angles. In fact, we interpret the membership function of S i as a likelihood function. From this viewpoint, the value µ S i (x) is a measure of the conditional uncertainty of the following event: "criterion A i is satisfied for a given x". Subsequently, this uncertainty can be modeled either by a possibility measure which is maxitive or a probability measure which is additive [START_REF] Dubois | Fuzzy sets and probability: misunderstandings, bridges and gaps[END_REF].

In the light of this latter consideration, the underlying framework of the TOWA approach could be understood as choosing a maxitive measure for dealing with the uncertainty conveyed by the fuzzy subsets in S (see also [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty, Approach to Computerized Processing of Uncertainty[END_REF]Section 1.4]). In our perspective, we rather assume that the uncertainty is modeled by a set function that is close to a probability measure. Indeed, we suppose a set function that is additive. However, as we shall see later on, this set function does not necessarily lie in the closed unit interval.

By assuming an additive set function instead of a maxitive one, we design a general scheme which leads to the definition of new kinds of aggregation operators.

The rest of this section is organized as follows. In Paragraph 3.1, we give more details about our framework. Then in Paragraph 3.2, we study the membership functions µ E N k and we show how they can be determined by using combinatorial tools. Afterwards, we examine (8) in our setting and we propose special cases that have interesting properties in Paragraphs 3.3, 3.4 and 3.5. In Paragraph 3.6, we enunciate some other properties that our proposals also satisfy.

Finitely additive set functions and some of their properties

Let S be the algebra of subsets generated by the finite class of fuzzy subsets S. Henceforth, we assume that µ is a real-valued set function, µ : S → R. We also suppose that µ is finitely additive and thus:

∀S, S ∈ S, S ∩ S = ∅ : µ S∪S = µ S + µ S . (9)
Let us denote S, the complement of S which is defined by X -S. In what follows, we recall well-known properties related to additive set functions.

Firstly, for all S, S in S, we have S ∪ S = X and S ∩ S = ∅. If we assume µ X (x) = 1 for all alternatives x ∈ X, then from ( 9) we can deduce the following relation:

∀S, S ∈ S : µ S = 1 -µ S . (10)
Secondly, for all S, S in S, it is clear that S = S ∩ (S ∪ S ) = (S ∩ S ) ∪ (S ∩ S ) which are disjoint from each other. As a consequence, it holds:

∀S, S ∈ S : µ S∩S = µ S -µ S∩S . (11)
Thirdly, one can observe that, for all S, S in S, S ∪ S can be expressed as (S ∩ S ) ∪ (S ∩ S) ∪ (S ∩ S ) with the latter three subsets being mutually disjoint. Therefore, by applying the previous relationships, we obtain the general formulation of the additivity property:

∀S, S ∈ S : µ S∪S = µ S + µ S -µ S∩S . (12)
It is worth underlying that ( 10) and ( 11) allow us to express the membership function of a fuzzy subset containing a complement, as a linear combination of membership functions of fuzzy subsets without any complement. Furthermore, [START_REF] Dubois | Fuzzy sets and probability: misunderstandings, bridges and gaps[END_REF] makes it also possible to formulate the membership function of an union as a linear combination of membership functions of subsets containing no complement. This property, which represents the core of our framework, can be generalized to all S in S as we shall explain in the sequel.

Let us use S to indicate either S or S in a generic manner. We define the set of fundamental intersections as the set of all possible intersections of size N contained in S that are particular cases of the following generic formula: S1 ∩ S1 ∩ . . . ∩ SN . There are 2 N fundamental intersections and they are all mutually disjoint. We also introduce the set of positive intersections which

A = S 1 ∩ S 2 ∩ S 3 , B = S 1 ∩ S 2 ∩ S 3 , . . . , G = S 1 ∩ S 2 ∩ S 3 and H = S 1 ∩ S 2 ∩ S 3 . Examples of positive intersections are A = S 1 ∩ S 2 ∩ S 3 , A ∪ B = S 1 ∩ S 2 and A ∪ B ∪ C ∪ F = S 2 .
are the elements of S that form fuzzy intersections which do not contain any complement and which can thus be expressed through the following formulation:

S i 1 ∩ . . . ∩ S i k with 1 ≤ i 1 < . . . < i k ≤ N and k = 1, . . . , N .
We illustrate these definitions in Figure 1 which is a Venn diagram corresponding to the case S = {S 1 , S 2 , S 3 }.

It is easy to see that all S in S can be formulated as a finite union of fundamental intersections. Then as a consequence of relationships [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decision making[END_REF] and [START_REF] Fodor | Fuzzy Set-Theoretic Operators and Quantifiers[END_REF], any fundamental product S1 ∩ S1 ∩ . . . ∩ SN can be equivalently formulated as a linear combination of membership functions of positive fuzzy intersections. Since all fundamental products are mutually disjoint, then all S in S can also be expressed as a linear combination of membership functions of positive intersections.

Therefore, in our setting, the finitely additive set function µ is completely determined by only defining the membership functions of positive intersections of S which consist of the following elements:

• all fuzzy subsets, {S i } 1≤i≤N , • all pairwise fuzzy intersections, {S i ∩ S j } 1≤i<j≤N , • all triple-wise fuzzy intersections, {S i ∩ S j ∩ S k } 1≤i<j<k≤N , • . . . • the fuzzy intersection made of the N elementary subsets, {S 1 ∩. . .∩S N }.
From a general perspective, in order to determine the membership function of any S in S, one can apply the following procedure:

• Express S as a finite union of fundamental products.

• Replace all S j by X -S j .

• Develop the resulting expression for each fundamental product.

• Replace the terms made of intersections of S j by their respective membership functions and replace the ∪ symbol by the regular sum.

Example 1. For illustration, let us determine the membership function of S 1 ∪ S 2 following the example depicted in Figure 1:

• S 1 ∪ S 2 = G ∪ H = (S 1 ∩ S 2 ∩ S 3 ) ∪ (S 1 ∩ S 2 ∩ S 3 ). • S 1 ∪ S 2 = ((X -S 1 ) ∩ (X -S 2 ) ∩ S 3 ) ∪ ((X -S 1 ) ∩ (X -S 2 ) ∩ (X -S 3 )). • S 1 ∪ S 2 = (S 3 -S 1 ∩ S 3 -S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 3 ) ∪ (X -S 1 -S 2 -S 3 + S 1 ∩ S 2 + S 1 ∩ S 3 + S 2 ∩ S 3 -S 1 ∩ S 2 ∩ S 3 ). • µ S 1 ∪S 2 = (µ S 3 -µ S 1 ∩S 3 -µ S 2 ∩S 3 + µ S 1 ∩S 2 ∩S 3 ) + (µ X -µ S 1 -µ S 2 -µ S 3 + µ S 1 ∩S 2 + µ S 1 ∩S 3 + µ S 2 ∩S 3 -µ S 1 ∩S 2 ∩S 3 ) = 1 -µ S 1 -µ S 2 + µ S 1 ∩S 2 .
Then in order to compute the membership functions of the positive fuzzy intersections, we propose to use t-norms. Accordingly, for all k-tuple (i 1 , . . . , i k ) such that 1 ≤ i 1 < . . . < i k ≤ N , we have:

µ S i 1 ∩...∩S i k = T (µ S i 1 , . . . , µ S i k ). ( 13
)
However, it is important to mention that even though µ S i (x) ∈ [0, 1] for all i = 1, . . . , N and for all x ∈ X, any t-norm does not necessarily allow the values of µ to lie in the closed unit interval. This is the reason why we assume µ to be a real-valued set function and not a measure. Such a topic was studied by Perovic et al in [START_REF] Perovic | Finitely additive probability measures on classical propositional formulas definable by Gödel's t-norm and product t-norm[END_REF]. These authors show that if T is a convex combination of T M and T P then µ is a probability measure [14, Theorem 2.2]. Otherwise, it is not guaranteed that all membership values lie in [0, 1].

Example 2. To illustrate this matter let us reproduce a counter example given in [START_REF] Perovic | Finitely additive probability measures on classical propositional formulas definable by Gödel's t-norm and product t-norm[END_REF]. This case amounts to evaluating the membership function of the event E 3 1 = "all criteria are not satisfied". This membership function can be firstly expressed as 1 -µ E 3 1 and it can be further expanded as follows

1 -( 1≤i≤N µ S i -1≤i<j≤N µ S i ∩S j + 1≤i<j<k≤N µ S i ∩S j ∩S k ). Now, suppose that an alternative x is such that µ S 1 (x) = µ S 2 (x) = µ S 3 (x) = 1/2, and we use T = T L (a, b) = max(a + b -1, 0), the Lukasiewicz t-norm. Then µ E 3 1 (x) = 3/2 -0 + 0 which is greater than 1, and thus µ E 3 1 (x) = -1/2 which is negative 6 .
As a result, we need to carefully choose the parameter setting in the general definition (8) so as to satisfy the definition of an aggregation function.

After having introduced the properties of the set function µ we use in our work, we focus in the next paragraph on the determination of the membership functions of the fuzzy proposition E N k = "at least k criteria are satisfied".

3.2.

Determining µ E N k using the Jordan formula First of all, let us notice that when assuming a probability measure, it is well-known that µ E N k can be determined by using the Jordan formula introduced in [START_REF] Jordan | Sur la probabilité des épreuves répétées, le théorème de Bernoulli et son inversion[END_REF][START_REF] Jordan | Problèmes de la probabilité des épreuves répétées dans le cas général[END_REF]. This identity generalizes the Poincaré formula which corresponds to the case k = 1 and which is also known as the inclusionexclusion principle or the sieve formula.

The Jordan formula was generalized to real-valued additive set functions by Takács in [START_REF] Takács | On the Method of Inclusion and Exclusion[END_REF]. Consequently, we can apply it in our framework. In order to recall the Jordan formula, let us firstly introduce the following so-called symmetric sums 7 , ∀k = 1, . . . , N :

Σ N k = 1≤i 1 <...<i k ≤N µ S i 1 ∩...∩S i k = 1≤i 1 <...<i k ≤N T (µ S i 1 , . . . , µ S i k ). ( 14
)
The Jordan formula enables us to determine the membership function of E N k as a linear combination of the symmetric sums Σ N k where the coefficients are binomial. We have, ∀k = 1, . . . , N :

µ E N k = k≤l≤N (-1) l-k l -1 k -1 Σ N l . ( 15
)
6 In contrast, if we choose T M (a, b) = min(a, b) as a t-norm, we will obtain µ E 3 1 (x) = 3/2 -3/2 + 1/2 = 1/2 and thus µ E 3 1 (x) = 1/2 as well which are all in [0, 1]. 7 Note that these functions should not be mistaken with the aggregation operators bearing the same name (see for example [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications)[END_REF]).

Example 3. In order to illustrate this identity, let us take again the example S = {S 1 , S 2 , S 3 } as described in Figure 1 and let us determine µ E 3 2 . From Figure 1, we can see that µ

E 3 2 = A + B + C + D. Using (15), we have µ E 3 2 = 1 1 Σ 3 2 -2 1 Σ 3 3 = Σ 3 2 -2Σ 3 3 . Next, Σ 3 2 = µ S 1 ∩S 2 + µ S 1 ∩S 3 + µ S 2 ∩S 3 and from the Venn diagram this is exactly (A + B) + (A + D) + (A + C) = 3A + B + C + D. Besides, Σ 3 3 = µ S 1 ∩S 2 ∩S 3 which is A. Thus, in this example, ( 15
) gives 3A + B + C + D -2A which is the correct solution.
Other particular cases of the Jordan formula are the Poincaré formula which determines the value of the event "at least one criterion is satisfied", and the measure of unanimity which is the value of the proposition "all criteria are satisfied". In the former case, µ E N 1 is given by the alternating sum Σ

N 1 -Σ N 2 + . . . + (-1) N +1 Σ N N .
In the latter case which corresponds to µ E N N , (15) simply reduces to Σ N N . Another kind of subsets that is related to the E N k is the family of propositions "exactly k criteria are satisfied" for all k = 1, . . . , N and which are denoted H N k . The latter events were studied by Jordan as well and their membership functions can be determined with an expression similar to µ E N k [START_REF] Jordan | Sur la probabilité des épreuves répétées, le théorème de Bernoulli et son inversion[END_REF][START_REF] Jordan | Problèmes de la probabilité des épreuves répétées dans le cas général[END_REF]. We have, ∀k = 1, . . . , N :

µ H N k = k≤l≤N (-1) l-k l k Σ N l . (16)
Interestingly, the setting we propose allows us to satisfy the following relationship.

Proposition 1. For all k = 1, . . . , N -1:

µ E N k = µ H N k + µ E N k+1 . (17)
Proof. By using the fact that l k = l-1 k-1 + l-1 k , we have:

µ E N k = k≤l≤N (-1) l-k l -1 k -1 Σ N l = k≤l≤N (-1) l-k l k - l -1 k Σ N l = µ H N k - k≤l≤N (-1) l-k l -1 k Σ N l .
Let us put k = k + 1 then it comes:

µ E N k = µ H N k + k ≤l≤N (-1) l-k l -1 k -1 Σ N l = µ H N k + µ E N k .
The Jordan formulas are in accordance with the framework we have discussed in the previous paragraph. Indeed, these expressions are only based upon the membership functions of positive intersections of fuzzy subsets in S. By combining ( 8) and ( 15), our method can thus be formulated as follows:

A w,T = 1≤k≤N w k k≤l≤N (-1) l-k l -1 k -1 Σ N l . (18)
However, determining the membership functions of the E N k generally leads to heavy computations because of the combinatorial nature of additive set functions. In the worst case, µ E N 1 , we need to determine the membership functions of 2 N fuzzy subsets. Furthermore, as we have underlined at the end of Paragraph 3.1, we also have to pay attention to the way we set the parameters of (18) in order to define valid aggregation functions.

In the subsequent paragraphs, we examine some particular cases of (18) that lead to the definition of valid and interesting aggregation operators.

Using T M for fuzzy intersections

One first remarkable case is when we apply the minimum t-norm for the determination of all positive fuzzy intersections in [START_REF] Gould | The Girard-Waring Power Sum Formulas for Symmetric Functions, and Fibonacci Sequences[END_REF].

Firstly, let us state the following relation related to the symmetric sums.

Lemma 1. Let x be an alternative and τ a permutation of {1, . . . , N } such that

µ S τ (1) (x) ≥ µ S τ (2) (x) ≥ . . . ≥ µ S τ (N ) (x).
Let T = T M for the determination of the membership functions of all positive intersections in S. Then for all k = 1, . . . , N :

Σ N k = 1≤l≤N -k+1 N -l k -1 µ S τ (N -l+1) . (19)
Proof. [START_REF] Perovic | Finitely additive probability measures on classical propositional formulas definable by Gödel's t-norm and product t-norm[END_REF] is the sum of all fuzzy intersections made of all possible combinations of size k of elements in S. By using T M , one can observe that in [START_REF] Perovic | Finitely additive probability measures on classical propositional formulas definable by Gödel's t-norm and product t-norm[END_REF], the smallest value

µ S τ (N ) (x) is added N -1 k-1 times (all combinations of size k involving µ S τ (N ) ), the second smallest value µ S τ (N -1) (x) is added N -2 k-1
times (all combinations of size k involving µ S τ (N -1) (x) but not µ S τ (N ) (x)) and so on. This enumeration is the combinatorial identity known as the hockey stick which leads to [START_REF] Ah-Pine | Data Fusion in Information Retrieval Using Consensus Aggregation Operators[END_REF].

Secondly, if we apply [START_REF] Ah-Pine | Data Fusion in Information Retrieval Using Consensus Aggregation Operators[END_REF] to determine the membership functions µ E N k , we obtain the following result.

Proposition 2. Under the same conditions stated in Lemma 1, it holds that, for all k = 1, . . . , N :

µ E N k (x) = µ S τ (k) (x). ( 20
)
Before establishing the proof of Proposition 2, let us first state the following combinatorial identity.

Lemma 2. For all k ≤ N : k≤l≤N (-1) l-k N l l k = 1 k=N , (21)
where 1 A equals 1 if the given proposition A is true and it equals 0 otherwise.

Proof. Let us recall that ∀k ≤ l ≤ N :

N l l k = N k N -k l-k .
By applying this combinatorial identity, we obtain:

k≤l≤N (-1) l-k N l l k = (-1) -k k≤l≤N (-1) l N k N -k l -k = (-1) -k N k k≤l≤N (-1) l N -k l -k .
Let us take l = l -k and N = N -k. Moreover, let us recall the binomial formula:

(a + b) N = 0≤l≤N N l a N -l b l . If a = 1 and b = -1 it holds: 0 N = 0≤l≤N (-1) l N l .
By making the variables changes and by applying the latter relation we have:

k≤l≤N (-1) l-k N l l k = (-1) -k N k 0≤l ≤N (-1) l +k N l = (-1) -k N k (-1) k 0 N = (-1) 0 N k 0 N -k .
From the equation above, one can see that k = N is the only case where we obtain a non-null value and it equals 1.

We can now establish the proof of Proposition 2.

Proof. From ( 15) and ( 19), we have:

µ E N k (x) = k≤l≤N (-1) l-k l -1 k -1 1≤m≤N -l+1 N -m l -1 µ S τ (N -m+1) = k≤l≤N (-1) l-k l -1 k -1 1≤m≤N N -m l -1 µ S τ (N -m+1) 1 m≤N -l+1 = 1≤m≤N µ S τ (N -m+1) k≤l≤N (-1) l-k l -1 k -1 N -m l -1 1 l≤N -m+1 = 1≤m≤N µ S τ (N -m+1) k≤l≤N -m+1 (-1) l-k l -1 k -1 N -m l -1 .
Let us denote l = l -1 and k = k -1. Then by using Lemma 2, it comes:

µ E N k (x) = 1≤m≤N µ S τ (N -m+1) k ≤l ≤N -m (-1) l -k l k N -m l = 1≤m≤N µ S τ (N -m+1) 1 k =N -m .
Finally, we have k = N -m iff k = N -m+1 which completes the proof.

Owing to the previous developments, we can enunciate the following theorem.

Theorem 1. Let T = T M for the determination of the membership functions of all positive intersections in S, then A w,T M = TOWA w,T M = OWA w . Proof. By using relation [START_REF] Grabisch | Bi-capacities for decision making on bipolar scales[END_REF] of Proposition 2 in the general definition [START_REF] Schweizer | Probabilistic metric spaces[END_REF], we obtain A w,T M = 1≤k≤N w k µ S τ (k) (x). Then according to [START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF], this latter expression is TOWA w,T M which is also OWA w as stated in [START_REF] Menger | Statistical metrics[END_REF].

Corollary 2. Let T = T M for the determination of the membership functions of all positive intersections in S, then for all weight vectors w, A w,T M is an aggregation function.

Therefore, our approach encompasses the OWA function as a special case. Moreover, using T M allows us to address the combinatorial issue since the OWA function has a O(N log N ) computational cost. Besides, it is interesting to point out that the OWA function already generalizes other well-known aggregation operators such as the arithmetic mean and order statistics (see for example [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications)[END_REF]).

Even though the case T = T M is interesting from a theoretical standpoint, it does not illustrate the innovative aspect of our proposal. In the sequel, we examine other particular cases which are more appealing in that respect.

Using T P for fuzzy intersections

In this paragraph, we demonstrate that using another fundamental tnorm, T P , we obtain other interesting properties. In that case, other combinatorial tools allow us to dramatically reduce the computational complexity of the symmetric sums. Indeed, in this context, we can apply the Newton-Girard formula (see for example [START_REF] Gould | The Girard-Waring Power Sum Formulas for Symmetric Functions, and Fibonacci Sequences[END_REF]) in order to calculate all Σ N k effectively. To this end, let us introduce the following power sums, ∀k = 1, . . . , N :

P N k = 1≤i≤N µ k S i . (22)
The Newton-Girard formula makes it possible to compute the symmetric sums in a recursive way by using the power sums. This is stated in the following proposition. Proposition 3. Let T = T P for the determination of the membership functions of all positive intersections in S. Then for all k = 1, . . . , N :

kΣ N k = 1≤l≤k (-1) l-1 Σ N k-l P N l , (23)
with the convention that Σ N 0 = 1. Owing to this result, we can calculate the symmetric sums with a O(N 2 ) computational cost instead of an exponential one. This implies that the computational complexity of A w,T P can be reduced from 2 N to O(N 2 ) as well. It remains to prove that using T P leads to a function satisfying the requirements given in Definition 1. This is stated in the following result. Theorem 3. Let T = T P for the determination of the membership functions of all positive intersections in S, then for all possible weight vectors w, A w,T P is an aggregation function.

Proof. It is evident that A w,T P (0, . . . , 0) = 0. Next, in order to prove that A w,T P (1, . . . , 1) = 1, we show by induction that µ E N k (1, . . . , 1) = 1 for all k = 1, . . . , N . It is clear that µ E N N (1, . . . , 1) = 1. Then assume that µ E N k (1, . . . , 1) = 1 and let us prove that, µ E N k-1 (1, . . . , 1) = 1 for all k = N, . . . , 2. To this end, we stated in Proposition 1 that µ

E N k-1 = µ H N k-1 + µ E N k .
Accordingly, it is sufficient to show that µ H N k (1, . . . , 1) = 0 for all k = 1, . . . , N -1. To achieve this result, one can observe that if

µ S 1 (x) = . . . = µ S N (x) = 1 then Σ N k = N k
and in that case:

µ H N k = k≤l≤N (-1) l-k l k N l = 1 k=N .
Indeed, this is exactly the relationship given in Lemma 2 and it enables us to claim that A w,T P (1, . . . , 1) = 1. Finally, because of [14, Theorem 2.2], we know that using T P for all positive intersections of S allows µ to be a probability measure. This implies that all µ E N k are non-decreasing in each argument. Therefore, A w,T P is also non-decreasing in each argument for it is a convex combination of the µ E N k . So far, we have studied our general approach (8) by varying the type of t-norm one could use to define the membership functions of positive fuzzy intersections and by letting the weight vector w free of restrictions. In this latter paragraph, we have studied the product operator T P and this t-norm not only allows us to reduce the complexity of our method, but it also provides a new kind of aggregation function. In the following paragraph, we pursue our work by restraining this time the weight vector w. As we shall see, unlike the methods we have examined so far, this approach enables us to employ different t-norms for different positive intersections in an effective manner.

Using two particular weight vectors

We investigate some particular settings of the weight vector w in (8). Our goal is twofold. On the one hand, we seek to design aggregation functions that can reproduce different types of behaviors between severe and tolerant.

On the other hand, we aim to reduce the computational cost due to the combinatorial nature of our framework.

We show that by defining two special weighting schemes, we can address both aforementioned matters in the same time. The weight vectors that we restrict our study to, are the following ones:

w ↑ = 2 N (N + 1) (1, 2, . . . , N ), ( 24
)
w ↓ = 2 N (N + 1) (N, N -1, . . . , 1). ( 25
)
The meaning of w ↑ can be explained as follows: the importance of the linguistic quantifier "at least k" linearly increases with respect to k. It is easy to show that this weighting scheme has an orness value of 1/3 whatever N . Therefore, the resulting function has a behavior closer to a conjunction than the uniform weighting scheme. In this case, an alternative needs to have a great membership value in all fuzzy subsets S i , in order to get a high overall score.

As far as w ↓ is concerned, it can be seen as the dual case. The orness of w ↓ is 2/3 which corresponds to a behavior that is more disjunctive than the arithmetic mean. Unlike w ↑ , it is more important that "at least one criterion is satisfied" in that case, since the highest weight is put on the membership value of the fuzzy event E N 1 . Then the importance of the linguistic quantifier "at least k" linearly decreases as k grows.

The former weight leads to a quite severe behavior while the latter one is rather indulgent. These cases correspond to two behaviors that are opposite to each other and hence, they address the first point we have raised previously.

In order to address the second point we are concerned with, let us start by reviewing two combinatorial properties.

Lemma 3. 0≤k≤N (-1) k N k = 1 N =0 , ( 26
) 0≤k≤N (-1) k k N k = -1 N =1 . ( 27
)
Proof. From the binomial formula, (a + b) N = 0≤k≤N N k a N -k b k , if we take a = 1 and b = -1 then we have: 0 N = 0≤k≤N (-1) k N k . In that case, if N = 0 then 0 0 = 1 whereas if N > 0 we obtain 0 N = 0 which proves (26).

Next from the binomial formula again, we can derived the following relation:

(a -1) N = 0≤k≤N N k a N -k (-1) k .
Then if we take the derivative with respect to a we obtain:

N (a -1) N -1 = 0≤k≤N (-1) k (N -k) N k a N -k-1
. Now, if we set a = 1, it comes the following identity:

N 0 N -1 = 0≤k≤N (-1) k (N -k) N k = N 0≤k≤N (-1) k N k - 0≤k≤N (-1) k k N k .
In this latter equation, the only case where the left hand side is non-null is when N = 1. In that context, the left hand side equals 1 and the right hand side can be simplified since 0≤k≤N (-1) k N k = 0 thanks to (26). The resulting relation is (27).

By using w ↑ and w ↓ in (8), we can in fact reduce the computational cost of our approach dramatically. This is claimed in the following statement. Proposition 4. Let w ↑ and w ↓ be two weighting schemes as defined in (24)8 and ( 25) respectively. Then it holds:

A w ↑ ,T = 2 N (N + 1) 1≤i≤N µ S i + 1≤i<j≤N µ S i ∩S j = 2 N (N + 1) 1≤i≤N µ S i + 1≤i<j≤N T (µ S i , µ S j ) , (28)
A w ↓ ,T = 2 N (N + 1) N 1≤i≤N µ S i - 1≤i<j≤N µ S i ∩S j = 2 N (N + 1) N 1≤i≤N µ S i - 1≤i<j≤N T (µ S i , µ S j ) . ( 29
) Proof. Let us recall that w ↑ = 2 N (N +1) (1, 2, . . . , N ) and if µ is finitely additive, then µ E N k = k≤l≤N (-1) l-k l-1 k-1 Σ N l .
Then we have:

A w ↑ ,T = 1≤k≤N w ↑ k µ E N k = 2 N (N + 1) 1≤k≤N k k≤l≤N (-1) l-k l -1 k -1 Σ N l = 2 N (N + 1) 1≤k≤N k 1≤l≤N (-1) l-k l -1 k -1 Σ N l 1 l≥k = 2 N (N + 1) 1≤l≤N 1≤k≤N k(-1) l-k l -1 k -1 Σ N l 1 k≤l = 2 N (N + 1) 1≤l≤N 1≤k≤l k(-1) l-k l -1 k -1 Σ N l .
Now, let us define k = k -1, l = l -1 and N = N -1. Then the equation above can be equivalently formulated as follows:

A w ↑ ,T = 2 N (N + 1) 0≤l ≤N 0≤k ≤l (k + 1)(-1) l -k l k Σ N +1 l +1 = 2 N (N + 1) 0≤l ≤N Σ N +1 l +1 0≤k ≤l (k + 1)(-1) l -k l k = 2 N (N + 1) 0≤l ≤N Σ N +1 l +1 0≤k ≤l k (-1) l -k l k + (-1) l -k l k = 2 N (N + 1) 0≤l ≤N Σ N +1 l +1 0≤k ≤l k (-1) l -k l k + 0≤k ≤l (-1) l -k l k .
Owing to Lemma 3, we can see that the term in brackets in the right hand side equals (0 + 1) when l = 0, then it reduces to (1 + 0) when l = 1, and it is (0 + 0) when l > 1. Accordingly, we have shown that:

A w ↑ ,T = 2 N (N + 1) (Σ N +1 1 + Σ N +1 2
).

The proof of (29) is similar. One can develop A w ↓ and obtain:

A w ↓ ,T = 2 N (N + 1) 0≤l ≤N Σ N +1 l +1 (N + 1) 0≤k ≤l (-1) l -k l k - 0≤k ≤l k (-1) l -k l k .
By using Lemma 3 as well, we can prove that:

A w ↓ ,T = 2 N (N + 1) ((N + 1)Σ N +1 1 -Σ N +1 2
).

From Proposition 4, it is clear that the computational complexities of A w ↑ ,T and A w ↓ ,T can be reduced from 2 N to O(N 2 ). It is important to underline that (28) and ( 29) only require the membership functions of the fuzzy subsets {S i } 1≤i≤N and {S i ∩ S j } 1≤i<j≤N .

In addition, this result invites us to consider different t-norms for different pairwise fuzzy intersections. Indeed, we propose to extend the result highlighted in Proposition 4 by setting not one t-norm for all positive intersections, but one t-norm per pairwise intersection {S i ∩ S j } 1≤i<j≤N . Let us denote by T * λ a parametric family of t-norms depending on a real parameter λ. We also introduce Λ = {λ ij } 1≤i<j≤N , a set of N (N -1)/2 values all belonging to the parameter's domain of the chosen family. In that case, λ ij is the parameter value that determines the membership function of the fuzzy subsets S i ∩ S j such that, ∀i, j = 1, . . . , N, i < j:

µ S i ∩S j = T * λ ij (µ S i , µ S j ). (30)
Following the results we have detailed previously, we can define the following functions:

A w ↑ ,T * λ ,Λ = 2 N (N + 1) 1≤i≤N µ S i + 1≤i<j≤N T * λ ij (µ S i , µ S j ) , (31)
A w ↓ ,T * λ ,Λ = 2 N (N + 1) N 1≤i≤N µ S i - 1≤i<j≤N T * λ ij (µ S i , µ S j ) . (32)
The next result states that (31) is an aggregation operator.

Theorem 4. Let w ↑ be the weighting scheme as defined in (24). Let T * λ be a parametric family of t-norms and Λ = {λ ij } 1≤i<j≤N a set of N (N -1)/2 real values all belonging to the domain of the chosen family. Then A w ↑ ,T * λ ,Λ defined in (31) is an aggregation function.

Proof. It is evident that A w ↑ ,T * λ ,Λ (0, . . . , 0) = 0. Next, it is easy to show that A w ↑ ,T * λ ,Λ (1, . . . , 1) = 1 since when µ S 1 (x) = . . . = µ S N (x) = 1 then T * λ ij (µ S i , µ S j ) = 1 and 1≤i<j≤N T * λ ij (µ S i , µ S j ) boils down to N (N -1)/2. Finally, A w ↑ ,T * ,Λ is non-decreasing since it is a convex combination of non- decreasing functions.
As far as A w ↓ ,T * λ ,Λ is concerned, not any t-norm leads to a valid aggregation function. A simple counter example is the following one.

Example 4. Suppose N = 2 and T * λ 12 = T D , the drastic t-norm. Let us take a first alternative

x such that µ S 1 (x) = µ S 2 (x) = 1 -with ≥ 0. We obtain A w ↓ ,T * λ ,Λ (x) = (2(2 -2 ) -0)/3 = (4 -4 )/3. One can observe that if < 1/4 then A w ↓ ,T * λ ,Λ (x)
> 1 which is not in line with Definition 1. Moreover, Let us assume a second alternative y with the following membership values µ S 1 (y) = 1 and µ S 2 (y) = 1 -. In this case, we obtain

A w ↓ ,T * λ ,Λ (y) = (2(2 -) -(1 -))/3 = (3 -)/3
which is a value lower than the former one. Consequently, in this example employing the drastic t-norm does not make A w ↓ ,T * λ ,Λ non-decreasing. Nonetheless, we provide below a sufficient condition for A w ↓ ,T * λ ,Λ to be an aggregation operator.

Theorem 5. Let w ↓ be the weighting scheme as defined in (25). Let T * λ be a parametric family of t-norms which satisfies the Lipschitz condition:

T * λ (b, c) -T * λ (a, c) ≤ b -a whenever a ≤ b. Let Λ = {λ ij } 1≤i<j≤N be a set of N (N -1)/2 real
values all belonging to the domain of the chosen family. Then A w ↓ ,T * λ ,Λ defined in (32) is an aggregation function. Proof. It is evident that A w ↓ ,T * λ ,Λ (0, . . . , 0) = 0 and it is also easy to prove that, A w ↓ ,T * λ ,Λ (1, . . . , 1) = 1. We show that if T * λ fulfills the Lipschitz condition then A w ↓ ,T * λ ,Λ is non-decreasing. Let us formulate A w ↓ ,T * λ ,Λ as follows:

A w ↓ ,T * λ ,Λ = 2 N (N + 1) N 1≤i≤N µ S i - 1≤i<j≤N T * λ ij (µ S i , µ S j ) = 2 N (N + 1) 1≤i≤N N µ S i - i<j≤N T * λ ij (µ S i , µ S j ) . Let g i (µ S 1 , . . . , µ s N ) = N µ S i -i<j≤N T * λ ij (µ S i , µ S j ).
Then to prove that A w ↓ ,T * λ ,Λ is non-decreasing, it is sufficient to prove that, g i (µ S 1 , . . . , µ s N ) is non-decreasing for all i = 1, . . . , N . To this end let us consider µ S i + with ≥ 0 and let us prove that, ∀i = 1, . . . , N : g i (µ S 1 , . . . , µ S i + , . . . , µ s N )g i (µ S 1 , . . . , µ S i , . . . , µ s N ) ≥ 0. Firstly, we have the following relationship:

g i (µ S 1 , . . . , µ S i + , . . . , µ s N ) -g i (µ S 1 , . . . , µ S i , . . . , µ s N ) = N -i<j≤N T * λ ij (µ S i + , µ S j ) -T * λ ij (µ S i , µ S j ) .
Secondly, since we assume that T * λ satisfies the Lipschitz condition for all λ, it comes the following inequalities, for all 1 ≤ i < j ≤ N :

T * λ ij (µ S i + , µ S j ) -T * λ ij (µ S i , µ S j ) ≤ .
Consequently, we obtain:

g i (µ S 1 , . . . , µ S i + , . . . , µ s N ) -g i (µ S 1 , . . . , µ S i , . . . , µ s N ) ≥ N - i<j≤N ≥ N -(N -1) ≥ 0.

Other properties of the introduced aggregation functions

We end this section by giving other properties related to aggregation operators (see for example [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications)[END_REF]). We review below the ones that we are interested in. An aggregation function F is:

• symmetric if ∀τ ∈ P N : F (x 1 , . . . , x N ) = F (x τ (1) , . . . , x τ (N ) )
, where P N denotes the set of all possible permutations of {1, . . . , N },

• strictly increasing if x ≺ y ⇒ F (x) < F (y), where x ≺ y ⇔ (∀i = 1, . . . , N : µ S i (x) ≤ µ S i (y)) ∧ ∃j ∈ {1, . . . , N } : µ S j (x) < µ S j (y), • idempotent if ∀a ∈ [0, 1] : F (a, . . . , a) = a.
It is not difficult to see that the following statements hold:

• A w,T M is symmetric, strictly increasing and idempotent for all weight vectors w.

• A w,T P is symmetric and strictly increasing for all weight vectors w.

• A w ↑ ,T * λ ,Λ is strictly increasing for all parametric families T * λ and all set of valid parameter values Λ.

• A w ↓ ,T * λ ,Λ is strictly increasing for all parametric families T * λ and all set of valid parameter values Λ such that T * λ satisfies the Lipschitz property. • For all sets of parameters Λ 1 and Λ 2 such that, for all i, j = 1, . . . , N , i < j: T *

λ 1 ij ≤ T * λ 2 ij , then: -A w ↑ ,T * λ 1 ,Λ 1 ≤ A w ↑ ,T * λ 2 ,Λ 2 , -A w ↓ ,T * λ 1 ,Λ 1 ≥ A w ↓ ,T * λ 2 ,Λ 2 .
From the latter property, it is noteworthy that these order relations allow one to design more or less strict aggregation functions from A w ↑ ,T * λ ,Λ and A w ↓ ,T * λ ,Λ , by suitably setting the set of fuzzy intersections Λ.

A numerical example

In order to illustrate the interest of our proposals, we use a well-known problem given by Grabisch and Labreuche in [START_REF] Grabisch | Bi-capacities for decision making on bipolar scales[END_REF]. In this example, we are provided with the satisfaction degrees of several individuals with respect to some criteria. The goal is to reproduce a given preference relation over the set of individuals by means of an aggregation function.

We recall the dean problem in Paragraph 4.1. We particularly review the fact that this problem cannot be solved by using a Choquet integral. Then in Paragraph 4.2, we address the dean problem with the aggregation operators we have introduced previously. To this end, we introduce elicitation procedures based on mathematical programming, in order to determine the parameters of the functions. Interestingly, we show that the newly introduced methods can solve the dean problem.

The dean's problem

Four students x 1 , x 2 , x 3 , x 4 are assessed with respect to three different courses: mathematics, physics and literature. These criteria are respectively denoted A 1 , A 2 , A 3 . The dean wants to decide about the ranking of the students according to the two following rules:

• For a student good at mathematics, literature is more important than physics. • For a student bad at mathematics, physics is more important than literature.

The performance table on the continuous scale [0, 1] is given below. In this example, we interpret the students' grades as their membership values in fuzzy subsets S i which are literally defined as "criterion A i is satisfied". Following the two aforementioned rules, it is easy to see that the dean's preference relation over the students is x 2 x 1 x 3 x 4 where x y means "x is strictly preferred to y". Grabisch and Labreuche showed in [START_REF] Grabisch | Bi-capacities for decision making on bipolar scales[END_REF] that it is not possible to achieve this latter linear order by a (unipolar) Choquet integral 9 for there is no capacity that can satisfy the two previous rules given the values provided in the performance table above.

Stud. µ S

Indeed, let us denote by ν a capacity over the set of criteria {A 1 , A 2 , A 3 }. In order to satisfy the expected preference relation, we should have x 2 x 1 and x 3

x 4 which translates as follows using a Choquet integral C ν : C ν (x 2 ) > C ν (x 1 ) and C ν (x 3 ) > C ν (x 4 ). By developing these two constraints we respectively obtain:

C ν (x 2 ) > C ν (x 1 ) ⇔ 1 -ν({A 1 , A 2 }) > ν({A 2 }), ( 33
) C ν (x 3 ) > C ν (x 4 ) ⇔ 1 -ν({A 1 , A 2 }) < ν({A 2 }). ( 34
)
Since the two equations on the right hand sides are incompatible with each other thus, it is not possible to represent the dean's preference relation by a Choquet integral. Besides, as the weighted mean and the OWA aggregation operators are particular cases of the Choquet integral, these classical aggregation functions cannot solve the problem neither.

Nevertheless, for illustration purpose, let us compute the aggregated values given by the arithmetic mean and a weighted mean. In this latter case, let us take the weight vector (0.5, 0.3, 0.2) which somehow reflects the impor-tance of the different courses. We obtain the following aggregated values: As expected, the overall scores we obtain do not satisfy the dean's ranking. Unlike these classical aggregation operators, we show that the aggregation operators we have introduced can represent the dean's preference model.

Stud. 1 3 µ S 1 + 1 3 µ S 2 + 1 3 µ S 3 5

4.2.

Eliciting the dean's preference model using the proposed aggregation operators We use the dean example for two purposes. As mentioned previously, it is our aim to demonstrate the interest of the introduced techniques by showing that they can solve the dean problem. In addition, we seek to illustrate the computation and some properties of our proposals. To this end, we apply an elicitation technique similar to the approach proposed by Marichal and Roubens in [START_REF] Marichal | Determination of weights of interacting criteria from a reference set[END_REF] which relies on a linear program. This method aims at maximizing the difference between the aggregated values of pairs of individuals that satisfy a strict preference relation.

Application of A w,T M

To begin with, let us take A w,T M defined in (8) as the aggregation function. This implies that we set T = T M for all positive fuzzy intersections in S, assuming the same strong t-norm between elements in S. The values of the different symmetric sums are the following ones:

Stud. Σ 3 1 Σ 3 2 Σ 3 3 x 1 1.
       ∀x : F w (x) = A w,T M (as given in (8)), N j=1 w j = 1, ∀x y : F w (x) -F w (y) > δ, δ > 0. (35)
As expected, we find that the problem is unfeasible. Indeed, as highlighted in Theorem 1, A w,T M reduces to the OWA function, a sub-case of the Choquet integral which was shown to be ineffective for the dean problem. In other words, there cannot be a weight vector w and a strictly positive δ such that, A w,T M (x 2 ) -A w,T M (x 1 ) > δ and A w,T M (x 3 ) -A w,T M (x 4 ) > δ.

Application of A w,T P

We take A w,T P as the aggregation operator. By setting T = T P we assume the same type of conjunction for the fuzzy subsets in S but this fuzzy intersection is weaker10 than T M .

In the case of T P , we can use the Newton-Girard formula to calculate all Σ N k recursively. To this end, we start by computing the power sums P 3 k given in (22) for k = 1, 2, 3: Unlike the previous case, A w,T P is not a sub-case of the Choquet integral. In addition, it is noteworthy that using T P for fuzzy intersections allows the problem to be solved. Indeed, we find the following optimal solution: δ * = 0.01066 with w * = (0.536842, 0, 0.463158 In this paragraph, we use A w ↑ ,T * λ ,Λ as the aggregation method. The weight vector w ↑ encodes a linear increase from the linguistic quantifier "at least k" to "at least k + 1". This corresponds to an orness value of 1/3 which means that it is a rather severe aggregation operator. However, one remarkable property of this approach is the possibility to set different t-norms for different pairwise intersections {S i ∩ S j } 1≤i<j≤N .

Stud. P
Accordingly, in this case, the unknown variable is no longer the weight vector but the set of t-norms that determine the membership values of all pairwise intersections {S i ∩ S j } 1≤i<j≤N . In that perspective, we propose to use the Frank t-norms to model the latter fuzzy intersections but other parametric families could be used.

Frank t-norms depend on a parameter λ which ranges in [0, ∞] and its definition is, ∀a, b ∈ [0, 1]:

T F λ (a, b) =          T M (a, b) if λ = 0, T P (a, b) if λ = 1, T L (a, b) if λ = ∞, log λ 1 + (λ a -1)(λ b -1) λ-1 otherwise. (36)
In this context, the elicitation procedure amounts to determining a set of N (N -1)/2 values Λ = {λ ij } 1≤i<j≤N such that, µ S i ∩S j = T F λ ij (µ S i , µ S j ). To this end, we propose the following optimization problem:

max δ subject to        ∀x : F Λ (x) = A w ↑ ,T F λ ,Λ (x) (as given in (31)), ∀i < j : λ ij ≥ 0, ∀x y : F Λ (x) -F Λ (y) > δ, δ > 0.
(37) Note that, even though (37) is similar in spirit to the previously introduced optimization problem (35), it is not a linear program since the constraints are no longer linear. fined in [START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF] with T = T P . In that case, the linear program (35) is feasible as well and we obtained: δ * = 0.00956, w * = (0.203187, 0, 0.796813) and the aggregated values 0.344223, 0.353785, 0.14761, 0.138048 for x 1 , x 2 , x 3 , x 4 respectively.

It appears that the application of (37) to the dean problem also leads to an optimal solution. Indeed, we obtain δ * = 0.00314, λ * 12 = 0.0480939, λ * 13 = 2756.24, λ * 23 = 25686.7 and the aggregated values below:

Stud. A w ↑ ,T F λ ,Λ
x 1 0.494398 x 2 0.497537 x 3 0.218556 x 4 0.215417

Similarly to A w,T P , the proposed aggregation function can model the dean's preference relation. It is worth noticing that despite the fact that we set the weight vector to w ↑ , we can solve the dean problem by suitably setting the t-norms of each pair of criteria and thus by assuming different sorts of interactions between the fuzzy subsets S 1 , S 2 and S 3 . The optimal solution we report, indicates that the t-norm for (S 1 , S 2 ) should be close to T P while the type of t-norm for (S 1 , S 3 ) and (S 2 , S 3 ) should be much weaker.

Application of A w

↓ ,T * λ ,Λ
In the case of A w ↓ ,T * λ ,Λ , the weight vector w ↓ corresponds to a linear decrease from w ↓ k to w ↓ k+1 . Unlike the previous method, the attitudinal character is 2/3 and hence, we have a rather indulgent function.

We use Frank t-norms again since this family satisfies the Lipschitz property as emphasized in Theorem 5. In order to address the example understudy, we apply the same optimization problem described in (37) but using A w ↓ ,T F λ ,Λ given in (32) for F Λ . In this case as well, we are able to represent the dean's preference model and this outcome demonstrates again the practical interest of our methods. The optimal solution is δ * = 0.00256, λ * 12 = 4531. This overall scores distribution is indeed in agreement with the expected linear order. Note moreover, that the aggregated values are greater than for the previous method which illustrate the fact that this aggregation operator is more tolerant than the former one.

Conclusion

Based on previous works, we have studied decision functions that rely on the linguistically quantified propositions "at least k criteria are satisfied". Similarly to the TOWA function, our general approach is based on a convex combination of the membership functions of the aforementioned fuzzy subsets. But, unlike the TOWA technique which relies on a maxitive measure, we assume a finitely additive set function. In this context, to determine the membership functions of all fuzzy subsets in S, we only need the membership functions of positive intersections {S i ∩ S j } 1≤i<j≤N , {S i ∩ S j ∩ S k } 1≤i<j<k≤N , . . . , which serve as a basis in our framework. Assuming that the membership functions {µ S i } 1≤i≤N are given, we propose to use t-norms to compute the membership functions of fuzzy intersections such as follows: {T (µ S i , µ S j )} 1≤i<j≤N , {T (µ S i , µ S j , µ S k )} 1≤i<j<k≤N , . . . Afterwards, by applying the Jordan formula, we have pointed out a formulation of our general approach that relies on a linear combination of symmetric sums. The latter expression, in its basic form, leads to heavy computations because of the combinatorial nature of the suggested framework. Nonetheless, we have examined particular cases that do not suffer from the computational cost burden. Then we have presented four particular settings of this general approach that all yield to valid aggregation functions and with a complexity that reduces from 2 N to O(N log N ) or O(N 2 ). The first technique which uses T M for fuzzy intersections reduces to the well-known OWA operator. However, the three remaining methods which respectively use T P , w ↑ and w ↓ as particular parameters values lead to new types of aggregation functions. In particular, our techniques make it possible to set different t-norms for different fuzzy intersections which is a new and particularly interesting feature.

Eventually, we have studied the application of these four proposals on a well-motivated problem that is impossible to address using classical aggregation operators such as the Choquet integral. We have illustrated the fact that all newly introduced aggregation functions can represent the decision model suggested by this problem and this outcome demonstrates the interest of our proposals from a practical standpoint.

Despite this positive empirical result, our proposals do not satisfy the idempotency property in general while this condition is usually required in multicriteria decision making. This drawback could limit the use of these techniques in the latter domain.

Consequently, as for the future, we intend to investigate the application of our aggregation functions in other fields such as information fusion where idempotency is not mandatory. From a more theoretical perspective, we also plan to examine other particular settings of our general framework.

Figure 1 :

 1 Figure 1: Venn diagram with S = {S 1 , S 2 , S 3 } respectively represented as solid red, dashed black and dotted blue circles. The 8 disjoint subsets A, B, C, D, E, F, G, H are the fundamental intersections of S:A = S 1 ∩ S 2 ∩ S 3 , B = S 1 ∩ S 2 ∩ S 3 , . . . , G = S 1 ∩ S 2 ∩ S 3 and H = S 1 ∩ S 2 ∩ S 3 . Examples of positive intersections are A = S 1 ∩ S 2 ∩ S 3 , A ∪ B = S 1 ∩ S 2 and A ∪ B ∪ C ∪ F = S 2 .

  1 µ S 2 µ S 3

	x 1	0.75 0.9 0.3
	x 2	0.75 0.8 0.4
	x 3	0.3 0.65 0.1
	x 4	0.3 0.55 0.2

  This result allows us to illustrate Proposition 2 since we clearly see that the obtained values correspond to the non-increasing order of each student's values distribution.Next, following[START_REF] Marichal | Determination of weights of interacting criteria from a reference set[END_REF], we apply the linear program below in order to determine if there is any aggregation function A w,T M that can reproduce the dean's ranking using the membership values given above.

	students in the fuzzy subsets E N k for k = 1, 2, 3 and we get:
	Stud. µ E 3 1	µ E 3 2	µ E 3 3
	x 1	0.9 0.75 0.3
	x 2	0.8 0.75 0.4
	x 3	0.65 0.3 0.1
	x 4	0.55 0.3 0.2
		max δ
	subject to
		95 1.35 0.3
	x 2	1.95 1.55 0.4
	x 3	1.05 0.5 0.1
	x 4	1.05 0.7 0.2
	Then by applying (15), we can compute the membership values of the

  19, λ * 13 = 0.226158, λ * 23 = 4842.72, and the aggregated values are: Stud. A w ↓ ,T F

		λ ,Λ
	x 1	0.789405
	x 2	0.79197
	x 3	0.507146
	x 4	0.504581

Note that to explicitly mention the number of arguments N , the notation F (N ) is often used in the literature. However, in order to lighten the notations, we choose to remove the superscript. We assume that we always have N input values but this is without loss of generality.

Triangular norms Ordered Weighted Average.

Also known as the Gödel or the Zadeh product.

Functions that mix T -norm with Ordered W eighted Averaging operators.

Ordered W eighted Averaging operators.

The aggregation operator A w ↑ ,T was initially introduce in[START_REF] Ah-Pine | Data Fusion in Information Retrieval Using Consensus Aggregation Operators[END_REF] in the context of metasearch tasks.

However, this goal can be reached by using a bipolar Choquet integral which is based on a bicapacity introduced by the same authors in[START_REF] Grabisch | Bi-capacities for decision making on bipolar scales[END_REF].

We remind that T 1 is weaker thanT 2 if for all a, b ∈ [0, 1] : T 1 (a, b) ≤ T 2 (a, b).

Note that, we also experimented with the aggregation function TOWA w,T P as de-

Acknowledgement

The author would like to thank the anonymous reviewers for their valuable comments.


Julien Ah-Pine
email: julien.ah-pine@univ-lyon2.fr

Edmundo Pavel

Soriano Morales
email: edmundo.soriano-morales@univ-lyon2.fr

A Study of Synthetic Oversampling for Twitter Imbalanced Sentiment Analysis

Keywords: Synthetic sampling, Sentiment analysis, Social media

The majority of Twitter sentiment analysis systems implicitly assume that the class distribution is balanced while in practice it is usually skewed. We argue that Twitter opinion mining using learning methods should be addressed in the framework of imbalanced learning. In this work, we present a study of synthetic oversampling techniques for tweet-polarity classification. The experiments we conducted on three publicly available datasets show that these methods can improve the recognition of the minority class as well as the geometric mean criterion.

Introduction

Micro-blogging services are communication tools that are massively used by people to instantaneously share their opinions about any kinds of topics. These opinions are of interest for companies or individuals, like politicians, as they allow them to monitor their online reputation. Twitter has been the most popular micro-blogging service with more than 500 million tweets per day in 2013 1 . Thus, sentiment analysis of tweets2 has received a lot of attention both from academia and industry during the last years.

In this paper, we focus on tweets polarity classification using supervised learning methods. This task is challenging in several respects. Firstly, tweets are limited to 140 characters and they contain irregular lexical units and syntactic patterns. Hence, these data are noisy, sparse and high-dimensional which makes the learning process difficult. Moreover, tweets expressing an opinion about a given topic usually present a skewed polarity distribution. In this case, any classifier would be biased towards the majority class.

In order to cope with these challenges, we propose to use synthetic oversampling techniques. These procedures are designed to deal with the class imbalance issue. We show that not only they enable reducing the bias towards the majority class, but they also alleviate the data sparsity burden commonly encountered in text mining.

The rest of the paper is organized as follows. In section 2, we discuss some related works in order to position and motivate our proposal. In section 3, we present our approach based on three synthetic oversampling methods and two supervised learning methods. Then, in section 4, we detail the experiments we conducted on three datasets including two different languages and we discuss the obtained results as well. We conclude the paper in section 5.

Related Works

Twitter Sentiment Analysis

Twitter sentiment analysis has received a growing interest starting from 2009 [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF][START_REF] Pak | Twitter as a corpus for sentiment analysis and opinion mining[END_REF]. In this work, we focus on polarity detection which aims at predicting the opinion of a tweet as positive or negative. Supervised learning techniques are the mainstream approaches in this case. Due to the characteristics of Twitter data, systems usually used for sentiment analysis (see [START_REF] Liu | A survey of opinion mining and sentiment analysis[END_REF] for a survey of this field) do not perform well. In order to improve classifiers' performance for tweets opinion mining, most of research works have proposed to extract features/lexicons which are specific to this type of data and/or leverage external resources [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF][START_REF] Pak | Twitter as a corpus for sentiment analysis and opinion mining[END_REF][START_REF] Kouloumpis | Twitter sentiment analysis: The good the bad and the omg![END_REF][START_REF] Sidorov | Empirical study of machine learning based approach for opinion mining in tweets[END_REF][START_REF] Kiritchenko | Sentiment analysis of short informal texts[END_REF][START_REF] Saif | Semantic patterns for sentiment analysis of twitter[END_REF][START_REF] Martínez-Cámara | Sentiment analysis in twitter[END_REF]. In contrast, we apply a corpus-based approach with no particular feature engineering.

Imbalanced Sentiment Analysis

The class imbalance problem in binary classification occurs when the sizes of the classes differ greatly. In this case, any classifier is biased toward the majority class (see [START_REF] He | Imbalanced Learning: Foundations, Algorithms, and Applications[END_REF] for a survey of the domain). For example, in the datasets we examined, near 70% of the tweets of the datasets we experimented with are negative. If a naïve classifier always assigns the negative polarity to any tweet, it will give an overall accuracy of 70% but without recovering any positive tweet, which is not satisfying.

Imbalanced learning for sentiment analysis has been studied by several researchers in different learning settings [START_REF] Li | Semi-supervised learning for imbalanced sentiment classification[END_REF][START_REF] Li | Imbalanced sentiment classification[END_REF][START_REF] Mountassir | An empirical study to address the problem of unbalanced data sets in sentiment classification[END_REF][START_REF] Xu | Word embedding composition for data imbalances in sentiment and emotion classification[END_REF]. However, we found very few papers that directly address imbalanced sentiment analysis for Twitter data [START_REF] Miura | Teamx: A sentiment analyzer with enhanced lexicon mapping and weighting scheme for unbalanced data[END_REF][START_REF] Hamdan | Lsislif: Feature extraction and label weighting for sentiment analysis in twitter[END_REF]. The methods that are proposed in the two latter works are similar to cost-sensitive approaches. In our case, we rather use sampling techniques.

3 The Proposed Approach

Vector Space Representation and Neighborhood

Tweets contain slang words and irregular expressions. Thus, linguistic analyses by conventional NLP tools often give poor performances on such texts. To circumvent these difficulties, and also to deal with different languages, we rely on a vectorial representation of tweets based on a bag-of-words approach. We denote by F the resulting feature space, x ∈ F is a vector representing a tweet and its coordinates are its words' frequency. In what follows, we use P and N to designate the subsets of tweets with the minority and the majority class labels respectively (|P| < |N|).

In order to compare tweets, we use the cosine similarity function. Note that all pairwise proximity measures lie between 0 and 1 since the coordinates of vectors are non-negative. Let x be any tweet in P then its neighborhood is denoted NN(x) and it consists of the k nearest neighbors.

Synthetic Oversampling

To face the skewed class distribution problem, one straightforward approach is to balance the training set so that |P| = |N|. Undersampling the majority class or oversampling the minority class are two possible strategies. Since the data are very sparse, undersampling the majority class is sub-optimal as we may lose meaningful examples in the learning process. Therefore, oversampling the minority class seems a better solution. In this case, synthetic oversampling creates new examples in P by taking convex combinations of existing points.

We recall three popular synthetic oversampling methods: SMOTE [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF], Borderline-SMOTE [START_REF] Han | Borderline-smote: A new over-sampling method in imbalanced data sets learning[END_REF] and ADASYN [START_REF] He | Adasyn: Adaptive synthetic sampling approach for imbalanced learning[END_REF]. Their general procedure can be cast as follows:

1. Select an original tweet x according to a probability distribution over P.

Determine NN(x).

3. Select a neighbor x according to a probability distribution over NN(x). 4. Create a synthetic example y as follows:

y = x + α(x -x) (1)
where α is a random value in [0, 1]. 5. Repeat 1-4 until the desired number of new examples is reached. 6. Append the set of synthetic points to P.

Note that y lies in the line segment joining x and x . It is important to notice that y belongs to the subspace spanned by the union of the underlying subspaces of x and x . Therefore, synthetic examples are less sparse than original ones.

The main differences between the three oversampling methods concern the random selection of x ∈ P in step 1. SMOTE assumes a uniform distribution over P whereas Borderline-SMOTE assumes a uniform distribution over B, a subset of P. B consists of tweets in P whose neighborhoods contain a majority of points in N. These items lie in subspaces where the decision boundary is prone to errors. Thereby, it is expected that oversampling in these parts of the space improves the classifier performances. Regarding ADASYN, it assumes a non uniform distribution over P. It can be seen as a smoothed version of Borderline-SMOTE: the noisier the neighborhood of x, the more synthetic points around x. In other words, the probability to select x in step 1 is proportional to the number of points of N contained in NN(x).

Datasets and Data Representation

We assess the approach introduced previously on three publicly available Twitter datasets. The first two are OMD "Obama-McCain Debate" [START_REF] Shamma | Tweet the debates: Understanding community annotation of uncollected sources[END_REF] and HCR "Health Care Reform" [START_REF] Speriosu | Twitter polarity classification with label propagation over lexical links and the follower graph[END_REF]. The third one is IW "Imagiweb" and concerns tweets in French, posted during the 2012 french presidential election [START_REF] Velcin | Investigating the image of entities in social media: Dataset design and first results[END_REF]. We chose political tweets because they present a particularly skewed class label distribution.

Concerning the vectorial representation of tweets, we used unigrams of words and we only removed the hapax.

We give the descriptive statistics3 of these datasets below:

-OMD: 1906 tweets (710 positive, 1196 negative) and 1569 features; -HCR: 1922 tweets (541 positive, 1381 negative) and 2066 features; -IW: 4519 tweets (1092 positive, 3427 negative) and 3918 features.

Supervised Learning Methods

We experimented with two different learning models: decision trees and the l1 penalized logistic regression. Decision trees are well-known symbolic learning techniques and offer the advantages of coping with high-dimensional data as well as providing humanreadable outputs. In this work, we used CART [START_REF] Breiman | Classification and regression trees[END_REF], which builds a binary classification tree based on the Gini index splitting criterion. The R package rpart was used and the default parameters values specified in rpart.control were applied.

The l1 penalized logistic regression [START_REF] Ng | Feature selection, l1 vs. l2 regularization, and rotational invariance[END_REF] is also an appropriate supervised learning for high-dimensional data since it implicitly performs feature selection. Moreover, this method has proven to provide competitive results in text classification [START_REF] Genkin | Large-scale bayesian logistic regression for text categorization[END_REF]. We used the glmnet R package [START_REF] Friedman | Regularization paths for generalized linear models via coordinate descent[END_REF] and in particular the function cv.glmnet which allows us to select the mixing parameter λ based on the error observed during training phase.

Assessment Measures

We use several performance criteria: overall accuracy (OA), F1-measures of the positive and negative classes (F-P and F-N respectively). OA evaluates the overall performance of a classifier but it does not properly account for the performances on P as compared to N because of the skewed distribution of class labels. Hence, we also use a popular criterion for imbalanced learning: the geometric mean (GM) of both class accuracy rates. Unlike OA, GM is independent of the class distribution (see [START_REF] He | Imbalanced Learning: Foundations, Algorithms, and Applications[END_REF]Chapter 8] for an overview of this topic). Thus we argue that GM should also be a default evaluation criterion in Twitter sentiment analysis tasks.

Experiments Setting and Results

It is important to note that we are not interested in comparing the results of decision trees against l1 penalized logistic regression. Our purpose is rather to illustrate that synthetic oversampling can improve the performances of learning methods on Twitter imbalanced-polarity detection tasks.

We tested the two learning models on the three collections with different relatively balanced training sets. In what follows, τ is a variable taking its values in {0, 1/4, 1/2, 3/4, 1} which measures how much the training set is balanced with respect to the initial distribution. In fact, τ = 0 is when no oversampling was carried out and we used the initial imbalanced training set (this is our baseline); τ = 1/4 means we generated (|N|-|P|)/4 positive synthetic examples; . . . ; and τ = 1 means we exactly sampled |N| -|P| new positive items in order to have a perfectly balanced training set. The neighborhood was set to k = 20 nearest neighbors 4 . The results we obtained using a 5 fold cross-validation are plotted in Figure 1 for decision trees and in Figure 2 for l1 penalized logistic regression. Fig. 1: Results for decision trees (CART). Solid line with circles refers to SMOTE, dashed line with triangles refers to Borderline-SMOTE and dotted line with plus signs refers to ADASYN. From left to right: plots of OA, F-P, F-N and GM measures. From top to bottom: plots for OMD, HCR and IW benchmarks. The x-axis refers to τ going from initial imbalanced (τ = 0) to fully balanced (τ = 1) training sets.

Our main findings are the following:

-For both decision tree and l1 penalized logistic regression, we note quite the same trends: oversampling generally improves the results. Indeed, All Fig. 2: Results for l1 penalized logistic regression. Same legend as in Figure 1.

three sampling globally improve the GM measure 5 . Thereby, our approach allows alleviating the class imbalance problem effectively. For OMD, when τ = 1, the most important gains for GM measures are given by ADASYN (1st row, 4th column in the figures). Regarding HCR and IW, Borderline-SMOTE performs the best but SMOTE often provides comparable results (2nd and 3rd rows respectively and 4th column in the figures). -All three oversampling strategies generally boosts F-P values 6 . The minority class is thus better recognized. However, this is at the expense of a reduction of F-N values. Nonetheless, since the increasing rate of F-P is generally much larger than the decreasing rate of F-N, we note the overall increase of GM values as highlighted previously. -For all three sampling techniques, the OA measure tends to diminish as the training set is more and more balanced. In fact, since the class distribution in the test set is skewed towards N, the errors on true negative tweets have more impact on OA than the correct detection of true positive tweets. This illustrates again the fact that OA is not a criterion that properly accounts for imbalanced data. -We cannot conclude on which of the three oversampling strategies is the best. However, we can make the following remarks:

• SMOTE and Borderline-SMOTE have quite the same behaviours for the HCR and IW collections. F-P measures are greater than ADASYN whereas F-N values are lower. Both methods allows a much better recognition of the minority class but in doing so they make more mistakes when detecting the majority class. • In contrast, ADASYN presents peculiar properties. The increase of GM values are lower than for the two other methods but this oversampling technique shows more stable OA values and even better ones in some cases. For the OMD dataset specifically, this approach not only provides among the best performances for the GM criterion but it also allows improving the OA measures unlike the other methods.

Conclusion

Twitter sentiment analysis is confronted with the class imbalance problem and it is important to take this aspect into account when designing opinion mining systems based on machine learning.

A way to address this challenge is to use synthetic oversampling which aims at balancing the training set in a meaningful way. Three state-of-the-art methods have been examined in that regard. We conducted experiments on politicaltweets polarity classification using three datasets and in two different languages. The obtained results show that our proposal makes it possible to deal with the skewed class distribution issue by providing better recognition of the minority class as well as obtaining large increases of the overall geometric mean criterion.

In future work, we intend to extend our study to multiclass sentiment analysis and also to examine the use of synthetic oversampling methods in other NLP tasks as a general approach to cope with the sparsity problem.

http://www.internetlivestats.com/twitter-statistics/

Short informal messages in a more general perspective.

We removed tweets that were labeled as neutral since we are only concerned with polarity detection.

We also tested with k = 10, 30 but the trends were similar and the results comparable.

The only exception is observed for OMD when using a fully balanced training sets (τ = 1) generated by Borderline-SMOTE with CART as shown in Figure1.

Except the same particular case mentioned previously.

Acknowledgment This work was partly supported by the french national projects Imagiweb ANR-2012-CORD-002-01 and Request PIA/FSN.