Umberto Grandi
email: authoratumberto.grandi@ut-capitole.fr

Andrea Loreggia

Francesca Rossi

Vijay Saraswat

A Borda Count for Collective Sentiment Analysis

Sentiment analysis assigns a positive, negative or neutral polarity to an item or entity, extracting and aggregating individual opinions from their textual expressions by means of natural language processing tools. In this paper we observe that current sentiment analysis techniques are satisfactory in case there is a single entity under consideration, but can lead to inaccurate or wrong results when dealing with a set of multiple items. We argue in favor of importing techniques from voting theory and preference aggregation to provide a more accurate definition of the collective sentiment over a set of multiple items. We propose a notion of Borda count which combines individuals' sentiment with comparative preference information, we show that this class of rules satisfies a number of properties which have a natural interpretation in the sentiment analysis domain, and we evaluate its behavior when faced with highly incomplete domains.

Introduction

We live in a world where we communicate more and more on social media, writing text that reflects our opinions and feelings. Being able to formalize such opinions and reason with them can be very useful for a number of practical applications. First, service providers may personalize their offer based on customers opinions. Second, companies may test what products would be better received by potential consumers, and adjust their strategy accordingly. Third, community councils and candidates in political elections may evaluate the reception of their proposals, and focus their attention on the most preferred ones. It comes therefore as no surprise that the extraction of individual opinions from textual expressions, such as tweets, blog posts, or product reviews, has been the subject of a very active area of research in recent years.

Researchers in sentiment analysis and opinion mining (34; 40) developed a collection of tools in natural language processing (NLP) for the extraction of opinions, sentiments, or attitudes of individuals from their textual expressions. In order to summarize the opinion of all the individuals in a unique indicator, the opinions extracted are then used to define a notion of collective sentiment about the entities under consideration, be they commercial products, policies or candidates.

In this paper we observe that current sentiment analysis techniques are good enough when we are trying to understand the positive or negative opinion of a set of agents over a single item, but they fall short when we are considering several items. Our claim stems from the observation that, when several items are being compared, the approach taken by sentiment analysis of only focusing on positive or neutral polarities may differ from the approach that computes the most preferred item by making use of comparative preference information. Consider for instance the following situation, in which two candidates Ann and Bob are competing in an election.

Example 1. Assume there are a total of 35 people who are expressing their positive or negative attitude on social media about two candidates Ann and Bob: 20 persons are talking positively about Ann, 15 persons are talking negatively about Ann, 30 persons are talking positively about Bob, and 5 persons are talking negatively about Bob. However, what people write on social media is just a textual abstraction of the comparative preferences they have in mind, which in this particular case we assume to be a ranked list of the two candidates. Assume therefore that their preferences are as described in the following table, where candidates to the left are more preferred than candidates to the right, and the bar signals the threshold of positive vs. negative opinions: | Ann Bob

Sentiment analysis Bob Majority rule Ann

In the profile described above there are 30 voters that express a positive opinion about Bob, and 20 voters that express a similar opinion about Ann. Hence, sentiment analysis, as well as similar methods based solely on sentiment information, would conclude that Bob is the most popular candidate. However, if we assume that the election will be decided by majority voting (which is the only sensible rule to be used when deciding among two candidates), then Ann will be the winner of the election with 25 votes over 10 for Bob, unlike the outcome of sentiment analysis. Observe that the positive/negative opinions expressed by the individuals are consistent with the preferences that will then be revealed at the time of voting.

The situation above is a good example of the use of sentiment analysis and preference aggregation for the prediction of a real-world event. In this particular case, a prediction of an electoral result is being based on the number of positive opinions extracted from voters. Similar examples can also be devised to point out a problem in situations of decision-making: think of Ann and Bob as two products that a firm is considering to promote, and the sentiment and preferences expressed in the table be those extracted from conversations and reviews of its customers. When the firm needs to decide which of the two products to invest in, sentiment analysis and preference aggregation would give two different recommendations.

The first message of this paper is that all these considerations can be phrased in the framework of preference analysis (43; 28) and voting theory [START_REF]Handbook of Social Choice and Welfare[END_REF]. For instance, sentiment analysis as presented in the example above uses a preference aggregation method called approval voting [START_REF] Brams | Approval voting[END_REF], which is based only on positive or negative opinions expressed over candidates. Text-extracted opinions may present both polarities and preference orderings, and the main contribution of this paper is to propose a definition of collective sentiment that makes use of both kinds of information.

Building on the classical Borda count (see, e.g., [START_REF] Brams | Voting procedures[END_REF]) we define and study a class of voting rules that aggregate both polarities and preference orderings into a collective sentiment, taking into account the incompleteness inherent in text-extracted opinions, where each individual may refer only to some of the items under consideration. We study the behavior of this class of rules from a decision-theoretic perspective. First, we list a number of properties that are desirable in the context of sentiment analysis, and we show that our proposed rules satisfy all such conditions. Second, we perform experiments to quantify the discrepancy between classical sentiment analysis techniques and our proposed rule, and we investigate its behavior with respect to partial information. The results we obtain indicate that our proposed Borda count not only satisfies a list of desirable properties when its outcome is used as a basis for decision-making, but also it is computationally tractable and it behaves well in highly incomplete domains.

To the best of our knowledge this paper is the first attempt to apply techniques from preference aggregation and voting theory to sentiment analysis over multiple issues. Related work has focused on sketching a road map for developing sentiment analysis as an alternative to opinion polls for the prediction of electoral results [START_REF] Metaxas | How (not) to predict elections[END_REF], focusing however on the statistical significance of the population studied rather than on the aggregation method used. Preference aggregation techniques have been used with success in other areas of computer science such as human computation and collective annotation of textual corpora (21; 35), and on developing procedures for collective decision making that are able to handle incomplete preferences (42; 44). A line of work which is similar in spirit to the one proposed in this paper is the work of Brams and Sanver [START_REF] Brams | Voting systems that combine approval and preference[END_REF] in social choice theory, albeit for the specific setting of committee decisions and elections. We refer to Section 4.3 for a more detailed discussion of this approach. We also acknowledge the work of Garg et al. [START_REF] Garg | Generalized opinion pooling[END_REF] on opinion pooling, which is however focused on the aggregation of probabilistic opinions. The present work expands our previous position paper on the use of preferences and voting techniques in sentiment analysis [START_REF] Grandi | From sentiment analysis to preference aggregation[END_REF].

The paper is organized as follows. In Section 2 we present the basic concepts and definitions of the framework of sentiment analysis and that of voting theory. In Section 3 we provide a formal definition of preferential information extracted from text, we formalize the two classical approaches of sentiment analysis and voting theory, and we present our novel definition of preference structure that combines sentiment with comparative preference. In Section 4 we put forward our definition of a Borda count for collective sentiment analysis and we evaluate rules from this class from both an axiomatic and an algorithmic perspective. Section 5 presents an experimental analysis of the differences between classical sentiment analysis and our proposed Borda count, and evaluates it in conditions of data sparsity. Section 6 concludes the paper and points at a number of challenges for future work in applying techniques from preference aggregation and voting theory to the domain of sentiment analysis.

Background

In this section we present the basic definitions of sentiment analysis, voting theory and preference aggregation.

Sentiment Analysis

Sentiment analysis and opinion mining (40; 34) is a collection of techniques for the extraction of people's opinions, sentiments, and evaluations from textual expressions. A set of entities or alternatives X is defined as the sentiment targets, and individual opinions about entities in X are extracted from a given set of product reviews, blog posts or other sources of textual information.

Formally, two forms of opinions can be identified:

Definition 1. (33) A regular opinion is a tuple (g, s, h, t) where g is the sentiment target, s is the sentiment about the target, h is the opinion holder and t is the opinion time.

Definition 2. (30) A comparative opinion (e 1 , e 2 , pa, h, t) is a tuple where e 1 and e 2 are two entities that are being compared, pa is the preferred alternative among e 1 and e 2 , h is the opinion holder and t the time.

Sentiment targets are also called entities or items, and can be anything such as products, policies or persons. The sentiment s in a regular opinion is usually taken to be a positive, negative or neutral polarity, i.e., an element of {+, -, 0}, although recent developments are directed to a more general setting of graded polarity such as a "fivestars" scale or numerical score [START_REF] Esuli | Sentiment quantification[END_REF]. The opinion holder h is the individual who wrote a text expressing sentiment s, and the time t is the moment at which h wrote the text. In this paper we will not make use of the temporal information, but we refer the reader to Section 6 for further discussion on the important role that temporal information may play in the development of principled notions of collective sentiment.

The objective of sentiment analysis is to extract all possible opinion tuples as in Definitions 1 and 2. Popular approaches to perform this task use a bag of words extracted from a tagged corpus of positive sentences, and then count in a more or less complex way the presence of such positive words in untagged documents [START_REF] Pang | Thumbs up? sentiment classification using machine learning techniques[END_REF]. Machine learning techniques such as naive Bayes approaches and sentiment classificators built using semi-supervised learning are also widely used for these tasks (see, e.g., (41; 5) for regular opinions and (30; 25) for comparative opinions).

A notion of collective sentiment aggregates individuals' opinions into a collective view, and it is usually expressed as a polarity. The most common approaches define the collective sentiment as a positive sentiment if the number of positive opinions about the item outnumbers the number of negative opinions. When more than one item is considered, each textual expression is classified as positive, negative or neutral, and the items with the largest number of positive expressions are declared as the most preferred ones according to the collective opinion (see, e.g., (38; 6; 13)).

Voting Theory

There is a wide literature in the field of economic theory and, more recently, artificial intelligence, which studies the problem of aggregating the preferences of a set of agents into a common collective choice or preference [START_REF]Handbook of Social Choice and Welfare[END_REF]. Formally, the problem is defined by a set of individuals I expressing preferences over a number of alternatives X , and by a voting rule F which associates a set of winning candidates with such preferences. Preferences can be specified in many different ways, for instance rankings, approvals or a set of binary comparisons. In this paper we consider two such definitions. The first and more common approach represents preferences as linear orders, i.e., transitive, anti-symmetric and complete binary relations over X . A profile of preferences P = (< 1 , . . . , < n ) is defined by the choice of a preference relation < i for each of the n individuals. We write a < i b to denote that agent i prefers item b to item a in profile P . A (non-resolute) voting rule F associates with every profile P a non-empty subset of winning candidates F (P ) ∈ 2 X \ ∅. A large number of voting rules have been proposed in the literature (see, e.g., Brams and Fishburn, [START_REF] Brams | Voting procedures[END_REF]), and we now present the definition of a widely used procedure that we will later use to ground our definition of collective sentiment: Definition 3 (Borda rule). Given a linear order < i for each i ∈ I, the Borda rule assigns to each alternative c ∈ X one point for each alternative that is ranked lower than c in < i , and then takes the sum over all individuals. The alternatives with the highest overall score are elected as the winners.

The Borda rule is a widely studied voting procedure that can easily be adapted to different preference models, such as orders with ties [START_REF] Fagin | Comparing and aggregating rankings with ties[END_REF] and partial orders (24; 1; 16). An axiomatic characterization of this rule was first presented by Young [START_REF] Young | An axiomatization of Borda's rule[END_REF].

The second approach that we will consider represents individual preferences as a set of approved alternatives. In this case, the only information collected from individuals is whether they approve or not a given alternative, and the following procedure is used to decide the winning alternative: Definition 4 (Approval voting). Given a subset of approved alternatives A i ⊆ X for each i ∈ I, the winners of approval voting are the candidates that receive the highest number of approvals.

Despite its simple definition, approval voting has been the subject of an extensive literature since its first appearance (see, e.g., [START_REF]Handbook of Approval Voting[END_REF]).

Both approval voting and the Borda rule can be adapted to output a ranking of the candidates (from higher to lower score) transforming the two voting rules into social welfare functions [START_REF] Rossi | A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice[END_REF], i.e., functions which associate with every profile of preferences a ranking of the alternatives.

Research in voting theory and preference aggregation has focused on the evaluation of different definitions of collective preference, either by means of axiomatic properties that specify desirable characteristics of the outcome of aggregation, by running experiments on realistic preference distributions, or by analyzing their computational properties such as the complexity of determining the winner (4; 12). We refer to Section 4.1 and 4.4 for a more detailed discussion of these aspects.

How to model individuals' opinions

Sentiment analysis and preference aggregation take two different approaches in the representation of absolute and comparative preferential information that is extracted from individual data. The aim of this section is to formally define these two approaches, and to propose a novel structure for preference representation that combines sentiment polarity with comparative preferences.

Individual data

We assume to have collected a set of textual expressions T i for every individual i ∈ I, and that exploiting tools from NLP we are able to extract regular opinions expressed by individuals about the entities in a set X in the form of a score (see Definition 1), as well as comparative opinions in the form of binary comparisons (see Definition 2).

Definition 5. The individual data extracted from a set of individual expressions T i is a tuple (σ i , P i , N i ) where:

• σ i : D i → R is a function defined on a subset of entities D i ⊆ X representing all regular opinions, i.e., degrees of positive and negative opinions over entities;

• P i is a preorder with domain P i ⊆ X , representing the set of positive comparative opinions of individual i;

• N
i is a preorder with domain N i ⊆ X representing the set of negative comparative opinions of individual i.

We make the further assumption that the individual data is always coherent, i.e., the sets P i and N i are disjoint sets and when entities a and b are in P i (resp. N i ) then both σ i (a) and σ i (b) are positive numbers (resp. negative), and also that a

P i b (resp. a N i b) if σ i (b) < σ i (a).
Observe moreover that the sets D i , P i and N i may have non-empty intersection.

Example 2. A company wants to evaluate three products of different colors: red (R), green (G) and blue (B). A corpora of textual expressions by three individuals is collected and the individual data extracted is as follows. The first individual has a positive opinion about all three products R, G, B, but the degree of these opinions is slightly different: we extract a score of 5 for product R, a score of 4 for entities G and B, and no pairwise comparison among the products. The second individual has a positive score of 1 about product G while expressing a negative opinion about the other two colors. She also expresses a direct preference of R over B. Finally, the third individual has a neutral opinion about R and B, while she considers alternative G negatively with a score of -4. We can summarize the opinions extracted from the three individuals in the terminology of our Definition 5:

• Individual 1: σ 1 (R) = 5, σ 1 (G) = σ 1 (B) = 4 and P 1 = N 1 = ∅; • Individual 2: σ 2 (G) = 1, P 2 = ∅, and N 2 = {R, B} with B N 2 R; • Individual 3: σ 3 (R) = σ 3 (B) = 0, σ 3 (G) = -4, and P 3 = N 3 = ∅.

The sentiment analysis approach

Sentiment analysis (at least in its most common implementation) disregards the intensity of sentiment as well as the comparative opinions, focusing only on the extraction of a positive, negative or neutral polarity from individual expressions.

Definition 6. Given individual data (σ i , P i , N i ) extracted from individual expressions T i , the pure sentiment data associated with it is a function Sent i :

E i → {+, -, 0}, where E i = D i ∪ P i ∪ N i , defined as: Sent i (c) =          sgn(σ i (c)) if c ∈ D i 0 if σ i (c) = 0 + if c ∈ P i - if c ∈ N i
After the information about the individual sentiments have been extracted, the most common approach in the definition of the collective sentiment is to choose the entities with the largest amount of positive opinions, disregarding the number of negative opinions.

Example 3. The pure sentiment data associated with Example 2 is the following:

• Individual 1: Sent 1 (R) = Sent 1 (G) = Sent 1 (B) = + • Individual 2: Sent 2 (G) = + and Sent 2 (R) = Sent 2 (B) = - • Individual 3: Sent 3 (R) = Sent 3 (B) = 0 and Sent 3 (G) = -
Using approval voting as a definition of the collective sentiment we obtain G as the most preferred entity, with two positive opinions received. With the same method we can easily construct a collective ranking of the entities, obtaining R and B tied in the second position with just one positive opinion received.

The voting theory approach

While sentiment analysis focuses only on polarities, the other extreme of the spectrum is the approach of voting theory, that is restricted to comparative preference information only. For the purpose of this paper we represent individual preferences by using preorders, i.e., reflexive and transitive binary relations. This choice is motivated by two important characteristics of preferences extracted from textual expressions:

• Interpersonal incomparability: Since individuals have very different styles of writing or attitudes towards judging the entities under consideration, we believe that scores or any other form of graded polarity cannot be compared across individuals. Therefore we argue in favor of an ordinal representation of both regular and comparative opinions.

• Incompleteness: Since preferences and sentiments are observed from individual expressions we cannot assume this information to be complete.

Formally, we can define the voting theory approach as follows:

Definition 7. Given the individual data (σ i , P i , N i ) extracted from individual ex- pressions T i , the pure preference data associated with it is a preordered set (D i , D i ), where D i = D i ∪ P i ∪ N i , defined as: x D i y ⇔         
x P i y and x, y ∈ P i or x N i y and x, y ∈ N i or x ∈ N i and y ∈ P i or σ i (x) σ i (y) and x, y ∈ D i Pure preference data is thus the union of the comparative opinions extracted from the ordinal relation entailed by σ i , with the addition of all the binary comparisons between elements from P i and elements from N i .

Example 4. The pure preference data associated with Example 2 is the following:

• Individual 1: B ∼ 1 G < 1 R • Individual 2: B < 2 R < 2 G • Individual 3: G < 3 B ∼ R Where G < R stands for G R and R G, and G ∼ R stands for G R and R G.
Using a straightforward adaptation of the Borda rule to preorders, we obtain B < G < R as the collective ranking: R receives 4 points, one for each alternative that is strictly ranked below by one of the individuals, G receives 2 points, and B only 1 point.

Combining Sentiment with Preference

In this section we propose a novel structure that combines features from both the sentiment analysis approach and the voting theory approach presented in the previous two sections. On the one hand we take binary comparisons as central to our analysis, using preorders to represent comparative preferential information. On the other hand, we complement this representation with a classification of the alternatives into three disjoint sets representing the positive, negative and neutral polarity: Definition 8. An SP-structure (for Sentiment-Preference structure) over a set of candidates X is a tuple S = (P, N , Z), where P, N and Z are disjoint subsets of X , and both P and N are ordered respectively by preorders P and N .

An SP-structure indicates the subsets of positive (P), negative (N ) and neutral (Z) candidates among the set of entities X , and specifies a set of binary comparisons between positive or negative candidates. The remaining elements of X \ (P ∪ N ∪ Z) are those alternatives for which no information has been collected.

We obtain SP-structures from individual data as follows:

Definition 9. Let (σ i , P i , N i ) be the individual data extracted from individual expressions T i . The SP-structure associated with it is the tuple (P i , N i , Z i ):

• P i = P i ∪ D + i where D + i = {x ∈ D i | σ i (x) > 0} • N i = N i ∪ D - i where D - i = {x ∈ D i | σ i (x) < 0} • Z i = {x ∈ D i | σ i (x) = 0}
with preorder relations defined as follows:

x P i y ⇔

x P i y and x, y

∈ P i or σ i (x) σ i (y) and x, y ∈ D + i x N i y ⇔
x N i y and x, y ∈ N i or σ i (x) σ i (y) and x, y ∈ D - i Example 5. The SP-structures associated with Example 2 are the following:

• Individual 1: P 1 = {R, G, B} with G P 1 R and G ∼ P 1 B, N 1 = Z 1 = ∅ • Individual 2: P 2 = {G}, N 2 = {R, B} with B N 2 R, Z 2 = ∅ • Individual 3: P 3 = ∅, N 3 = {G} and Z 3 = {R, B}
SP-structures can be easily visualized, and in Figure 1 we draw the three structures described above. Alternatives that are in higher positions in the table are preferred to those that are in lower positions, and the three sets P, Z and N are separated by horizontal lines. In conclusion, an SP-structure compactly represents both sentiment information in the form of three polarity sets, as well as comparative opinions in the two preorders over the positive and negative sets. SP-structures are based on a purely ordinal view of preferences, hence assuming a very low degree of interpersonal comparability among individuals' preferences. This assumption could be relaxed by, for instance, normalizing the scores extracted from the individual data, or directly using them in the construction of the collective sentiment. While these approaches may fit some particular applications, they require additional important assumptions when merging comparative opinions, which are of an ordinal nature, with the possibly normalized scores used to represent regular opinions.

R P | G ∼ B G R, B Z R G N | B

Borda counts for aggregating SP-structures

In order to aggregate SP-structures, and therefore put forward our definition of collective sentiment, in this section we define a class of aggregation procedures based on the classical Borda count (see Definition 3). We begin by introducing a list of properties which are desirable in the context of sentiment analysis, and then put forward our definition of aggregation method. We show that this method satisfies all the desirable properties we introduced and that it generalizes both the existing definition used by sentiment analysis and the classical Borda rule in preference aggregation. We conclude the section with a study of the algorithmic aspects of our proposed Borda count.

Desired Axiomatic Properties

The axiomatic method consists in first specifying a number of desirable properties about the problem at hand, and then show a solution that satisfies them, or prove that there exists none. In this section we adapt classical axiomatic properties from the literature in social choice theory to the case of SP-structures, providing a suitable interpretation in the domain of sentiment analysis. We build on the axiomatization of the Borda rule proposed by Young [START_REF] Young | An axiomatization of Borda's rule[END_REF], which we complement with axioms specific to our domain of application.

We first need to introduce some useful notation. Let us call a collection of SPstructures (S 1 , . . . , S n ) a profile, which we denote by S. If S 1 and S 2 are profiles of SP-structures, let S 1 + S 2 be the profile obtained by putting together the two original profiles (renaming voters if necessary), i.e. if S 1 = (P 1 , . . . , P n ) and S 2 = (Q 1 , . . . , Q m ), then S 1 + S 2 = (P 1 , . . . , P n , Q 1 , . . . , Q m ). A profile is called symmetric if the set of individuals can be partitioned in pairs of individuals {i, i } with completely opposite SP-structures, i.e., if

P i = N i , N i = P i , P i = ← -- N i and N i = ← - P i , where P i = ← -- N
i means that the preorder over the set P for voter i is equal to the inverted preorder over the set N of voter i . A symmetric profile necessarly contains an even number of SP-structures. Finally, given a single SP-structure S = (P, N , Z), we say that a voter i ranks a above b in S if one of the following four conditions holds: b P i a and a P i b, or b N i a and a N i b, or a ∈ P and b ∈ Z ∪ N , or a ∈ Z and b ∈ N .

Let F be a rule which associates a set of most preferred alternatives with a profile of SP-structures. We now list a number of desirable properties for such an aggregation rule F .

The first set of properties is an adaptations of classical axioms from social choice theory, regarding the equality of treatment of alternatives and individuals:

• Neutrality: For any profile S and permutation of entities ρ : X → X , we have that F (S ρ ) = ρ(F (S)), where S ρ is profile S with alternatives in X renamed by ρ.

• Anonymity: For any profile S and permutation of individuals ρ : I → I, we have that F (S ρ(1) , . . . , S ρ(n) ) = F (S 1 , . . . , S n ).

Neutrality requires that if we rename the items in X , the result should be the renaming of the initial result. Anonymity instead formalizes the fact that the collective opinion should not depend on the name of the individuals. The following two properties provide requirements on how to treat consensus and total disagreement in the individual preferences:

• Weak-Pareto: If S is a profile in which all individuals rank a above b, then b ∈ F (S).

• Cancellation. If a profile S is symmetric then all entities are in the winning set, i.e., F (S) = X .

The weak-Pareto property is a fundamental property when aggregating individuals' preferences: agreement among all individuals should be reflected in the collective opinion. Cancellation requires instead that if the disagreement is so extreme, as in a symmetric profile where individuals come in pairs whose preferences cancel each other out, then all items should be declared as the most preferred ones in the collective opinion.

The following two properties formalize the requirement that more information collected over an individual's preferences should lead to a result that is more preferred by that individual:

• Voters participation: For all profiles S = (S 1 , . . . , S n ) and SP-structure S n+1 , any candidate in F (S + S n+1 ) \ F (S) is ranked in higher or same position than any candidate in F (S) in the preferences of voter n + 1.

• Rank participation: For all profiles S = (S 1 , . . . , S n ) and SP-structure S ⊂ S n , any candidate in F (S) \ F (S -n + S ) is ranked in higher or same position than any candidate in F (S -n + S ) in the preferences of voter n. 1In the classical voting theory context, participation means that voters have an incentive to participate [START_REF] Moulin | Condorcet's principle implies the no show paradox[END_REF]. In a sentiment analysis context individuals have already expressed their opinion, so we do not need to favor their participation. However, the first property tells us that considering one more individual in the computation of the collective sentiment should result in a candidate that is higher in her ranking. In a similar way, the second property requires that more information on an individual's opinion lead to results that the individual ranks higher. Finally, the following property formalizes the possibility of using techniques such as map-reduce (18) in particular profiles, for a more efficient computation of the set of most preferred alternatives:

• Consistency: For all profiles S 1 and S 2 , if

F (S 1 ) ∩ F (S 2 ) = ∅ then F (S 1 + S 2 ) = F (S 1 ) ∩ F (S 2 ).
Consistency can be an important property in an application domain where one needs to deal with big quantities of data, such as sentiment analysis. It tells us that if we manage to partition the (possibly very large set of) individual opinions into smaller sets which have some best candidate in common, perhaps by means of a proper heuristic, then we can work on the elements of the partition independently. Thus divide and conquer approaches are possible, which parallelize and possibly speed up the computation. All properties presented above are adapted from the literature on social choice theory [START_REF]Handbook of Social Choice and Welfare[END_REF]. Not all combinations of axiomatic properties are feasible: for instance, the well-known Arrow's Theorem showed that it is not possible to aggregate linear orders using a rule that satisfies three simple desirable properties (namely, a weaker version of anonymity, an additional property called independence of irrelevant alternatives, and weak-Pareto) (3). This is not the case for the list of axioms presented above, as we will show in the following sections.

The B * α Rule

In this section we propose a parameterized class of aggregation procedures for profiles of SP-structures that builds on the classical Borda count, taking into account the incompleteness of the ordering and the additional information given by the sentiment polarity expressed by the individuals.

Definition 10. Given an SP-structure S = (P, N , Z) over X , the s * α -score of an entity c ∈ X in S is defined as follows:

s * α (c, S) =      α 1 | down P (c)| + α 2 | inc P (c)| + α 3 |Z| + α 4 if c ∈ P -α 1 | up N (c)| -α 2 | inc N (c)| -α 3 |Z| -α 4 if c ∈ N 0 if c ∈ P ∪ N Where α = (α 1 , α 2 , α 3 , α 4 ) with α 1 , α 2 , α 3 , α 4 ∈ R + . If c in P, down P (c)
is the set of elements of N that are less preferred than c, up P (c) is the set of elements of P that are more preferred than c, and inc P (c) is defined as the the set of elements that are incomparable to c in P (in N , respectively, for down N , up N and inc N ). We will omit the reference to S when it is clear from the context.

The s * α -score is defined as a parametrized class of scoring functions over SPstructures. It combines the approach from sentiment analysis, giving α 4 points to each alternative in the positive set and -α 4 to all those in the negative set, with a generalization of the classical Borda rule, giving α 1 points to an alternative for all those that are ranked below, α 2 points for those ranked incomparable, and α 3 points for those alternatives that are in the neutral set (negative points if the alternative is in the negative set).

Note that no point is given to entities for which an individual has a neutral sentiment or for which she does not have any opinion. We are hence assuming that all score variables are initialized to 0, while an equivalent formulation could leave unspecified the score of alternatives for which no opinion has been extracted. The main difference between alternatives in Z and alternatives in X \ (P ∪ N ∪ Z) is that the former do contribute to the score of alternatives in the positive or in the negative set via the parameter α 3 , while the latter are not taken into consideration when assigning scores to alternatives.

The use of a score may at first seems counterintuitive given our discussion in Section 3 on the interpersonal incomparability of preferential information. However, what is being represented in the s * α -score is purely ordinal information about the number of alternatives being more or less preferred to others, and should not be confused with the intensity of preference that could have been expressed in the individual data via the scoring function σ i .

To exemplify the flexibility of our setting, we can consider several assumptions on the α vector that the modeler can choose, depending on the application at hand. For instance, assuming α 1 > α 2 and α 3 > α 2 will make sure that more points are given to alternatives that are strictly preferred to others than to those that are incomparable. Another possibility is to assume that the score difference between two successive elements in the positive or negative part should be less than the score difference between the least positive and the best negative elements, for instance when 2α 4 > α 1 . If these two figures were equal, then the s * α -score would be equivalent to the classical Borda score when the set Z is empty, disregarding the sentiment information.

Definition 11. The score of an entity c ∈ X in the profile of SP-structures S = {S i = (P i , N i , Z i ) | i ∈ I} is defined as follows:

S * α (c, S) = i∈I s * α (c, S i )
where s * α (c, S i ) is s * α -score of alternative c in the SP-structure S i . The winners of the B * α rule are the candidates with maximal total score:

B * α (S) = argmax c∈X S * α (c, S)
Example 6. Let the parameters in α be α 1 = α 4 = 2 and α 2 = α 3 = 1, and therefore let the corresponding score be as follows

s * (2,1,1,2) (c, S) =      2 × | down P (c)| + | inc P (c)| + |Z| + 2 if c ∈ P i -2 × | up N (c)| -| inc N (c)| -|Z| -2 if c ∈ N i 0 if c ∈ P i ∪ N i
The winner of B * (2,1,1,2) on the profile of SP-structures associated with Example 2 is R. Indeed, the score s *

Axiomatic analysis

We begin by showing that our Borda count generalizes the existing approaches used by sentiment analysis and preference aggregation. Let us first introduce some notation. Call a profile purely preferential if, for all i ∈ I, the set P i is equal to X and is linearly ordered, i.e., P i is anti-symmetric, transitive and complete. Call a profile purely sentimental if for all i ∈ I the two sets P i and Z i form a partition of X , and the candidates in P i are all incomparable, i.e., the relation P i is empty, and the set N i is also empty. We now show that B * α coincides with the Borda rule on purely preferential profiles, and that it coincides with approval voting on purely sentimental ones.

Theorem 1. If a profile S is purely preferential, then for all α we have that B * α (S) = Borda(S). If a profile S is purely sentimental, then for all α such that α 2 = α 3 we have that B * α (S) = Approval(S).

Proof. Let S be a purely preferential profile, i.e., all individuals are expressing a linear order over entities in X which are all in P. Let S B (c, B) be the classical Borda score, i.e., the number of candidates ranked below c. Since in a purely preferential profile there are no alternatives that are incomparable to each other, and the sets N and Z are empty, the score S * α (c) = α 1 S B (c) + α 4 n, where n is the number of voters. Since n is constant then the two rules elect the same candidates, no matter the value of α 1 and α 4 .

Let now S be a purely sentimental profile and let S A (c) be the approval score of an entity c, i.e., the number of individuals approving c. Since all alternatives in P i are incomparable, every approved entity in each single SP-structure gets a score equal to α 2 (|X | -1) + α 4 . To see this, it is sufficient to observe that alternatives in Z give α 3 points to alternatives in P and α 2 = α 3 , and moreover in a purely sentimental profile the two sets P and Z form a partition of X . Hence, we obtain that S * α (c) = (α 2 (|X |-1)+α 4 )•S A (c) and thus B * α elects the same candidates as approval voting.

Theorem 1 formalizes the fact that our proposed Borda count is a generalization of both approaches at the extreme of the spectrum described in Section 3: a pure sentiment analysis approach, which uses approval voting, and a pure preference aggregation approach, as described by the Borda rule. The result of Theorem 1 can be generalized to profiles of partial orders to show that B * α extends the partial Borda count defined by Cullinan, Hsiao and Polett ( 16) as well as the bucket averaging method of Fagin et al. [START_REF] Fagin | Comparing partial rankings[END_REF].

We now show that our proposed Borda count for collective sentiment analysis satisfies all the axiomatic properties presented in Section 4.1.

Theorem 2. B *

α satisfies consistency, neutrality, anonymity, voters participation, rank participation, and cancellation for all α. If we assume that α 1 α 2 , then B * α also satisfies weak-Pareto.

Proof. For the sake of clarity we omit the reference to α where it is not necessary. To prove that B * α satisfies consistency it is sufficient to observe that S * S1+S2 (c) = S * S1 (c) + S * S2 (c). Those entities with maximal score in both S 1 and S 2 are then the entities with maximal score in S 1 + S 2 . Neutrality and anonymity are straightforward consequences of our definition of S * α . A simple monotonicity argument can be used to prove both versions of participation. Consider first voters-participation. Let w ∈ B * α (S), and let S n+1 be the additional SP-structure. We show that the winner of the joint profile w is not worse in n + 1's ranking than w. Since we have only added information from n + 1, w must have received strictly more points than w to become the new winner, and this can only happen if agent n + 1 prefers w to w. The same argument can be straightforwardly adapted to the case of rank-participation.

Finally, to prove that B * α satisfies cancellation we observe that in a symmetric profile all entities have score 0, since S * α is symmetric with respect to P and N . For weak-Pareto, there are four cases for an individual to rank a above b, and we can show that in all cases s * α (a) > s * α (b) and thus that b cannot be in the winning set. Recall that we assumed α 1 We conclude this section by comparing B * α with another rule, introduced in previous work by Brams and Sanver [START_REF] Brams | Voting systems that combine approval and preference[END_REF], that aims at combining approval voting with preference aggregation: fallback voting. Under this rule, each voter approves a subset (which could be empty) of candidates and ranks them in a linear order. The winner of fallback voting is obtained in an iterative way, by first checking whether there is a candidate that is top-ranked by a majority of voters. If such a candidate does not exist, then the first and the second ranked candidates in each voters' preference are considered, and once again it is checked if there is a candidate that is ranked first or second by a majority of the voters. The process goes on adding the third and subsequently ranked candidates until an alternative obtains a majority of approvals. The structures used by fallback voting to combine approvals with comparative preferences can be seen as a special case of SP-structures, with no neutral nor negative sets and linearly ordered items. Fallback voting may result in a different outcome than B * α . A detailed study of the difference between these two rules is left as future work. While fallback voting constitutes an interesting voting rule when individuals have incentives to express their preferences, in applications such as sentiment analysis the individual data that is collected will rarely be complete (see Section 3). Hence the need for rules that are able to handle incomplete profiles, such as our proposed B * α .

Algorithmic properties of B * α

In this section we analyze the algorithmic aspects of our proposed Borda count for collective sentiment analysis. Given the envisioned application, it is important that the basic problem of computing the most preferred alternative in a given profile be tractable, i.e. that the computational complexity of winner determination be solvable in polynomial time. We also provide an exact bound on the minimum number of bits required to compute the outcome of B * α (aka. its communication complexity) and we show that it can be computed with an incremental algorithm.

Let us first make some considerations about the size of representing an SPstructure. Recall that we start from a set of m alternatives or entities X , and n individuals. We assume that the sets N , P and Z are encoded with a vector of length m containing for each alternative in X a label of 2 bits for the set to which it belongs to. Since the set N and P are disjoint, the two preorders P and N can be represented as binary relations on an m × m matrix, indicating for every pair (a, b) whether a P b or a N b. The size of a profile of SP-structures with n individuals is therefore O(nm 2 ).

The problem of winner determination is the algorithmic task of deciding whether a designed alternative a ∈ X is in the winning set of a given profile of SP-structures S. This problem has been widely studied in voting theory [START_REF] Brandt | Computational social choice[END_REF], where its tractability is often considered a requirement for a rule to be considered of practical interest. We now show that the winner of our proposed Borda count can be computed in polynomial time:

Theorem 3. The winner of B * α can be computed in time O(nm 2 ), hence in time linear in the size of the input.

Proof. Given a single SP-structure S i , the s * α -score of an alternative a can be computed in the following way. First check whether a ∈ Z i , a ∈ P i , or a ∈ N i , which can be done in constant time. If a ∈ Z i then its score is 0. Otherwise we can compute its score by first counting how many alternatives are in Z i , which can be done in O(m), and then counting how many alternatives are ranked below a, in case a ∈ P i , or how many alternatives are ranked above a, if a ∈ N i , and finally how many alternatives are incomparable to a. All these operations can be done in O(m). We repeat this process for each alternative a and for each individual i, obtaining the upper bound O(nm 2 ).

A further important algorithmic property of a voting procedure is its communication complexity, i.e. the minimal amount of bits that needs to be expressed by the individuals in order to compute the most preferred alternatives. Previous work [START_REF] Conitzer | Common voting rules as maximum likelihood estimators[END_REF] provided lower and upper bounds for many voting procedures including the Borda rule, showing that the communication complexity of computing the Borda winner is Θ(nm log m), i.e., lower and upper bounds are both equal, up to multiplication by a constant, to the function nm log m.Since our Borda count for collective sentiment analysis generalizes the classical Borda rule (see Theorem 1), the communication complexity could in principle be higher, but as we show in the following result we simply move from a polylogarithmic to a polynomial factor:

Theorem 4. The communication complexity of B * α is in Θ(nm 2 ).
Proof. An upper bound is easy to obtain, since it is sufficient for each individual to specify their SP-structure to be able to compute the winner of B * α . Given our representation of SP-structures, a profile can be specified in O(nm 2 ) bits. A lower bound can instead be obtained by adapting the same bound for the classical Borda rule provided in [START_REF] Conitzer | Common voting rules as maximum likelihood estimators[END_REF]. We conclude the section by proposing a notion of incremental complexity that should capture the feasibility of computing the result of an aggregation procedure in an on-line fashion. This is a very important aspect when data is examined incrementally or when using methods such as map-reduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] to deal with large quantities of data. Recall the two participation axioms we introduced in Section 4.1: they imply that the result of an aggregation procedure should take into consideration the additional information collected from the individuals. A good aggregation procedure that can be used to define a notion of collective sentiment should not only take care of this additional information, but also be able to update the outcome in little time.

Let X be a set of alternatives. An individual expression P over X is a preference, a vote, an opinion, or an SP-structure defined on X . Given a profile of individual expressions (P 1 , . . . , P n ) -be it a profile of linear orders, of approval sets or of SPstructures -a generalized voting rule F is a function that outputs a set of most preferred alternatives F (P 1 , . . . , P n ) ⊆ X . If we denote with PR the space of all possible profiles for all finite n, then F : PR → 2 X . The Borda rule, approval voting, fallback voting and B * α are all generalized voting rules. We give the following definition:

Definition 12. An generalized voting rule F is incremental if there exists a representation of profiles r : PR → {0, 1} * and a function F : {0, 1} * × PR 1 → 2 X , where PR 1 is the set of all individual expressions, such that:

• F (P 1 , . . . , P n+1 ) = F (r(P 1 , . . . , P n ), P n+1 ) for all profiles (P 1 , . . . , P n+1 ) ∈ PR and all finite n;

• for every sequence of individual expressions {P i | i ∈ N}, the following holds:

lim n→+∞ size[r(P 1 , . . . , P n )] size[(P 1 , . . . , P n )] = 0
A generalized voting rule is incremental if its outcome, i.e. the set of most preferred candidates, can be computed by receiving the individuals expressions in a sequence, at each step computing the new outcome and storing a minimal amount of information that is needed to compute the outcome of the following step. Moreover, we require that the information stored at each step using function r be much smaller than the full representation of a profile as n grows.

Let us first show that both the Borda rule and approval voting are incremental. The Borda rule can be computed incrementally by storing the total Borda score of each alternative, and this can be done in space O(m log(nm)) since n × (m -1) is the maximal Borda score that an alternative can obtain. When additional information is collected in the form of a linear order P n+1 , the total Borda scores can simply be updated with the additional scores computed. Since the size of a profile of linear orders is O(nm log m), the requirement on the size of the representation holds: Approval voting receives as input a profile of sets of approved candidates, which has size O(nm). An incremental procedure for its computation stores the number of approvals received by any candidate, and updates them when a new voter submits her ballots. Hence size[r(P 1 , . . . , P n )] = O(m log n), showing that approval voting is also an incremental aggregation procedure.

Let us conclude by showing that B * α is incremental for any α. In the same way as the Borda rule, the total score obtained by each alternative in a profile of SP-structures S can be stored in space O(m log(nm)), since the maximal S * α -score is a linear function of n × m. When a new SP-structure S is extracted, the total scores can be updated and the new outcome computed. Since a profile of SP-structures is represented in space O(nm 2 ) we obtain the following:

lim n→+∞ size[r(P 1 , . . . , P n )] size[(P 1 , . . . , P n )] = m log(nm) nm 2 = 0
We conjecture that all anonymous voting rules are incremental by Definition 12. In fact, if a voting rule is anonymous then the information contained in a profile with n voters can be summarized by using an amount of space that grows sub-linearly with n. However, our definition measures an important characteristic of a generalized voting rule, one that is particularly useful in applications that deal with large numbers of individuals. The notion of incrementality we proposed resembles the on-line time discussed by Maudet et Al. [START_REF] Maudet | Compiling the votes of a subelectorate[END_REF], which however focuses mostly on space complexity requirements. A complete study of the notion of incrementality in generalized voting rules is beyond the scope of this paper, but the above discussion may serve as a starting point for further work on this topic.

Empirical Analysis

This section reports on our experimental evaluation of the B * α rule proposed in Section 4. The problem we face in this section is two-fold: First, in order to assess the relevance of preferential ordering information in determining the collectively preferred alternatives, we present experiments showing that there is a significant difference between the classical definition used by sentiment analysis and the result of the B * α rule. Second, given the information sparsity which is characteristic of sentiment analysis domains, we evaluate the accuracy of the B * α rule in situations of incompleteness, showing that its accuracy grows linearly with the amount of information available. In all our experiments we fix the parameters of the B * α rule to α = (2, 1, 1, 2).

Sentiment Analysis and Borda Count

A crucial factor supporting our claim that more complex models of preferences and aggregation procedures should be used in the definition of collective sentiment is that the classical sentiment analysis method (equivalent to approval voting) and B * α output different results over the same data. In fact, if they did not differ enough, it would mean that the ordering information (not considered by approval/sentiment analysis) is not relevant for determining the winner. Thus there would be no point in extracting ordering information from individuals.

Figure 2 reports on our experiments on the simplest case of 2 candidates. We enumerated all profiles of totally ordered SP-structures with n voters, with n from 2 to 90, where a totally ordered SP-structure is an ordering over the two candidates (that is, a over b or b over a), plus a threshold which associates to each candidate either a positive or a negative sentiment. Thus, there are 6 possible such SP-structures. We have computed the winning candidates according to sentiment analysis (i.e, approval voting) and according to B * α , which in the case of 2 candidates is equivalent to using the majority rule, and we have counted the percentage of profiles on which the two winners are different. Figure 2 shows that such percentage stabilizes at around 30%.

We have also varied the number of candidates from 2 to 100, keeping the number of voters fixed at 10, in which case however we did not enumerate all possibilities but we generated 10.000 profiles of complete SP-structures with the impartial culture assumption, i.e., we sampled profiles with uniform distribution. Figure 3 shows that the percentage of cases where B * α yields a different result than sentiment analysis grows with the number of candidates reaching more than 60%.

Incomplete Data

In practical applications individuals are likely to express their opinions over a small subset of the alternatives under considerations, as observed, e.g., in the studies conducted on the Netflix dataset [START_REF] Bennett | The Netflix prize[END_REF]. It is therefore important to assess the behavior of our proposed Borda count on incomplete profiles.

To do this we generated profiles of complete SP-structures with 10 candidates and 100 voters, and we deleted a certain percentage of information to obtain an incomplete version of the profile. More precisely, we generated incomplete profiles in the following way: we first generated complete profiles and then we picked randomly a voter and a candidate, which is either positive or negative for that voter, and we changed the SP-structure of that voter to have no opinion on the selected candidate. With n voters and c candidates, nc corresponds to 100% of the information. Thus deleting x% of the information means performing the above described modification of the profile (xnc)/100 times. We then compared the winner (according to B * α ) in the complete profile and in the incomplete one, by computing the absolute value of the difference between their S * α -scores, and we normalized it by dividing by the maximal error in the complete profile. Finally, we averaged over 10.000 profiles, obtaining the mean error introduced by the incompleteness of the profile. Figure 4 shows the trend in the error depending on the completeness of the profiles (mean error and variance). We also show the error of the random procedure, which outputs a candidate with uniform probability.

It is easy to see that Borda* always behaves better than the random procedure in identifying the winner in the complete profile, and moreover that its shape shows that accuracy quickly grows when the completeness of the profile increases.

Future Work

This work opens several directions for future work, and we conclude the paper by listing a number of challenges that arise from the use of techniques from preference aggregation and voting theory for collective sentiment analysis.

More refined models of opinions. As already noted in Section 2, our analysis of preference and opinion extraction disregarded two important parameters:

• Time. Individual opinions are expressed at a given point in time and are also subject to change or updates. Hence, temporal information plays an important role in defining a coherent individual view. We believe that the literature on knowledge representation [START_REF] Van Harmelen | Handbook of Knowledge Representation[END_REF], in particular belief revision and merging, provides useful tools for the analysis and summarization of conflicting information that can be applied to the modeling of this problem.

• Features. Entities or items are usually described by means of features, i.e., they may be elements of a product space. Techniques from natural language processing can be used to extract the relevant features and thus build the set of entities. However, in this setting preferences and opinions may compare features rather than entities, requiring a more elaborate framework for its extraction and representation. Moreover, the combinatorial explosion resulting from a large set of features may give rise to computational problems that require an adequate compact representation framework for preferences. The literature on social choice in combinatorial domains [START_REF] Lang | Voting in combinatorial domains[END_REF] and in particular on judgment aggregation [START_REF] Endriss | Judgment aggregation[END_REF] is highly relevant to this problem.

Validation of aggregation rules. Since the variety of preference aggregation methods that can be defined is very large, of which a prime example is the B * α rule depending on the values given to its parameters α, a natural question is how to make a choice among them. Two options are possible, depending on the use of sentiment analysis techniques as a predictor for real-world events or as a tool for decision-making. First, if methods of collective sentiment analysis are used over time, tested for several settings and items, and employed in the context of predicting the result of real-world processes (such as elections or the evolution of a market, see, e.g., (2)), then machine learning techniques can be used to learn the best aggregation method, that is, the one that has proven to be the most accurate. Work on voting rules seen as maximum likelihood estimators can also be useful in this respect [START_REF] Conitzer | Common voting rules as maximum likelihood estimators[END_REF]. Alternatively, as in classical voting theory and as performed in this paper, axiomatic properties as well as results about the computational complexity of aggregation rules could guide the choice of some aggregation methods over others.

Strategic behavior in sentiment analysis. The individuals composing a society, as well as the agents in a multiagent system, are very often connected by interpersonal ties, e.g., when individuals are organised in a network. In this case, individual preferences and opinions are not only the result of personal reflection but may also take into consideration the position taken by influential individuals or simply by agents that are close to them in the network. The field of social network analysis (29; 19) is a burgeoning research area which has the potential of generating highly interesting results once combined with techniques of preference and sentiment analysis. Sentiment analysis techniques are moreover not immune to strategic manipulation. A rising phenomenon is the creation of web services proposing the opening of thousands of fake Twitter accounts to be used as followers of the manipulator's account, or the publishing of big volumes of positive posts related to the manipulator's products. This represents a prime example of strategic behavior in collective choice problems, and the whole body of literature published on this topic may be put to test with real world data once the two fields of sentiment analysis and preference aggregation have been put together to their full potential. While the problem of manipulation for a single agent is computationally easy for the classical case of the Borda rule, we conjecture that for B * α this is not the case, given the higher amount of possibilities that an agent has to manipulate the election. However, single-agent manipulation is unlikely to occur in sentiment analysis applications, given the high number of individuals concerned and the absence of a well-defined elicitation protocol. Instead, an interesting direction for future work is the study of coalitional manipulation, which was recently shown intractable even for the classical Borda rule (17; 8).

Big data and collective sentiment analysis. When the aggregation operation is relatively simple (e.g., the majority rule), it is possible to use straightforward techniques such as Hadoop MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] to perform computations in parallel. The mapping phase can be used to run sentiment classifiers on text corpora in parallel; the resulting data objects can be combined/reduced in parallel. However, with more complex structures (e.g., conditional preference networks when the set of entities is described by means of features), the combination procedure may be more combinatorial in nature and may require non-trivial parallel processing. In this context, modern scale-out programming languages such as X10 can be particularly valuable [START_REF] Charles | X10: an object-oriented approach to non-uniform cluster computing[END_REF], making it easy to write code that runs over thousands of cores and deals with hundreds of gigabytes of main memory data. Of particular interest is developing incremental parallel algorithms that can update collective sentiments as new utterances stream in and need to be processed.

Figure 1 :

 1 Figure 1: SP-structures associated with Example 2.

( 2 , 1 , 1 , 2 )

 2112 (R) = 4 since there are 2 elements ranked below R in the positive part by the first individual (4 + 2 points), and R is ranked in the negative side by individual 2 (-2 point). G follows with a score of 1 since there is one element incomparable in the positive part by the first individual (1 + 2 points), G is ranked in the positive side by individual 2 (+2 point) and G is ranked in the negative side by individual 3 with 2 elements in the neutral set (-2-2 points). B is the worst preferred alternative with a score of -1, obtaining 3 points by individual one, -4 points by the second individual and 0 points by the third individual.

α 2 .

 2 Assume that b P i a and a P i b. If a third alternative c is ranked below b then by transitivity c is also ranked below a, and hence a and b get the same points from c. If c ∈ inc Pi (b) or c ∈ Z i then this also gives the same points to a (or more, if c is ranked below a since α 1 α 2 ). Finally, down Pi (b) ⊂ down Pi (a) and thus a gets α 1 more points than b. The case in which a and b are both in N i is treated symmetrically: just consider alternatives ranked above the two and the set up Ni (a) rather than down Pi (a). If we instead assume that a ∈ P i and b ∈ Z i ∪ N i , then it is easy to observe that s * α (a) > 0 while s * α (b) 0 and thus that also in this case s * α (a) > s * α (b). Finally, if a ∈ Z i and b ∈ N i then s * α (a) = 0 but s * α (b) < 0 since b ∈ N i gets -α 4 points and any other alternatives c ∈ N i can only decrease the score of b.

  lim n→+∞ size[r(P 1 , . . . , P n )] size[(P 1 , . . . , P n )] = lim n→∞ O(m log(nm)) O(nm log m)

Figure 2 :

 2 Figure 2: Percentage of profiles where sentiment analysis and B * α differ (2 candidates).

Figure 3 :

 3 Figure 3: Percentage of profiles where sentiment analysis and B * α differ (10 voters).

Figure 4 :

 4 Figure 4: Mean error of B * α on incomplete profiles in terms of S * α -score.

Inclusions of SP-structures is defined as inclusions of preorders, and S -n represents profile S without SP-structure Sn.


Isabela Maganha
email: isabela.maganha@student.dem.uc.pt

Cristovao Silva

Nathalie Klement
email: nathalie.klement@ensam.eu

Amélie Beauville Dit Eynaud

Laurent Durville

Samuel Moniz

Cemmpre

Hybrid optimisation approach for sequencing and assignment decision-making in reconfigurable assembly lines

Keywords: Reconfigurable assembly systems, Scheduling problem, Meta-heuristics, Hybrid optimisation

Technological advances, promoted by the Industry 4.0 paradigm, attempt to support the reconfigurability of manufacturing systems and to contribute to adaptive operational conditions. These systems must be responsive to significant changes in demand volume and product mix. In this paper, a hybrid optimisation approach is suggested to solve sequencing and assignment problems of reconfigurable assembly lines, where mobile robots collaborate with human operators. The objectives are: i) to define a schedule of jobs, ii) to assign tasks to the mobile robots, and iii) to decide the allocation of robots to workstations, in order to minimise the number of robots required. Preliminary results show that the proposed methodology can make an efficient robot allocation under high demand variety. In addition to that, the hybrid optimisation approach can be adapted to other configurations of assembly systems, which demonstrates its applicability to solve problems in other contexts.

INTRODUCTION

Manufacturing systems face a volatile demand with varying customer needs in terms of volume and product mix [START_REF] Beauville Dit Eynaud | Identification of reconfigurability enablers and weighting of reconfigurability characteristics based on a case study[END_REF]. These systems must be increasingly reconfigurable to react to these variations in a rapid and cost-effective manner [START_REF] Koren | Value creation through design for scalability of reconfigurable manufacturing systems[END_REF]. In this context, reconfigurable manufacturing systems (RMS) have been widely acknowledged as suitable for handling situations where responsiveness and productivity are of vital importance. Indeed, RMS provide a way to achieve a rapid and adaptive response to changes in volume and product mix [START_REF] Leitao | Bio-inspired multi-agent systems for reconfigurable manufacturing systems[END_REF].

Here, planning and scheduling aim is to determine when and how to set a new configuration of the assembly line. The problem consists in deciding: i) which resources should be used to manufacture a single unit of product, and ii) the sequence the jobs should follow [START_REF] Bensmaine | A new heuristic for integrated process planning and scheduling in reconfigurable manufacturing systems[END_REF][START_REF] Nehzati | Research Outline on Reconfigurable Manufacturing System Production Scheduling Employing Fuzzy Logic[END_REF]. In short, solving this problem involves determining the optimal resources allocation and the job sequence. Although RMS is an active research field, and planning and scheduling have been widely investigated, these problems need to be studied under the Industry 4.0 paradigm. More specifically, attention should be given to the planning and scheduling of manufacturing systems, considering the introduction of novel technologies, such as mobile collaborative robots. First, by developing new modelling approaches for better understanding how new robotic technologies can be applied to design and run reconfigurable assembly systems (RAS). Second, addressing the modelling complexity of scheduling problems and the associated computational burden, through the development of alternative solution approaches, such as hybrid optimisation [START_REF] Li | A robust scheduling for reconfigurable manufacturing system using petri nets and genetic algorithm[END_REF].

The objective of this paper is to present a hybrid optimisation approach, that combines a constructive heuristic and a meta-heuristic, to solve sequencing and tasks assignment in reconfigurable assembly lines (RAL), where tasks can be divided between humans and collaborative robots that share the same workstation. The remainder of this paper is organised as follows. Section 2 discusses some existing works on planning and scheduling problems in RMS. Section 3 describes with more detail the problem addressed. Section 4 presents the proposed solution approach. The results are presented and discussed in Section 5. Section 6 presents some final remarks and future research work.

RELATED WORKS

Reconfigurability is an important ability that determines the ease and cost of reconfiguration. To enable reconfigurability, manufacturing companies must implement some core characteristics, such as modularity, integrability, diagnosability, adaptability and customisation. They facilitate the design of manufacturing systems to be reconfigurable, using hardware and software modules that can be integrated quickly and reliably [START_REF] Koren | Reconfigurable manufacturing systems[END_REF]. They also allow achieving the system's functionality and scalability required for the production of a product family to meet market demands [START_REF] Maganha | Understanding reconfigurability of manufacturing systems: An empirical analysis[END_REF]. Without them, the reconfiguration process will be lengthy or even impracticable [START_REF] Koren | Reconfigurable manufacturing systems[END_REF]. The core characteristics of reconfigurability are outlined in Table 1. In a nutshell, modularity provides more adjustable production resources, capable of responding to unpredictable market demand. Integrability, on the other hand, allows the rapid integration of these available resources [START_REF] Koren | Design of reconfigurable manufacturing systems[END_REF]. Diagnosability enables the fast detection of the quality problems after reconfiguration and contribute to reduce reconfiguration ramp-up time [START_REF] Koren | The rapid responsiveness of RMS[END_REF]. Implementing adaptability is essential to cope with the scheduling function in RMS, since it allows adjustments in the capacity and functionality of the manufacturing system, by means of an adjustable structure [START_REF] Maganha | Understanding reconfigurability of manufacturing systems: An empirical analysis[END_REF]. In other words, it allows the modification of production capacity by adding/removing resources or changing system components [START_REF] Koren | Reconfigurable manufacturing systems[END_REF]. The same authors referred that diagnosability and adaptability complement each other, because scaling-up of an existing system to cope with changing demand requires a subsequent ramp-up period that can be reduced dramatically by implementing diagnosability. Finally, customisation aims at reducing the reconfiguration cost [START_REF] Koren | The rapid responsiveness of RMS[END_REF]. These works suggest that there is the opportunity to apply optimisation approaches so as to improve the reconfigurability of assembly lines, by linking the core characteristics of reconfigurability with optimised planning and/or scheduling decision-making.

Recently, [START_REF] Bortolini | Reconfigurable manufacturing systems: Literature review and research trend[END_REF] presented a structured and updated literature review on RMS, highlighting some works that have proposed solution approaches to solve scheduling problems in this context. [START_REF] Li | A robust scheduling for reconfigurable manufacturing system using petri nets and genetic algorithm[END_REF] applied genetic algorithm (GA) embedded with extended time-placed Petri nets (ETPN) for RMS scheduling, aiming to optimise reconfiguration costs and balanced pro-duction. [START_REF] Galan | Hybrid Heuristic Approaches for Scheduling in Reconfigurable Manufacturing Systems[END_REF] proposed a meta-heuristic approach to group products into families and then schedule these families, minimising the total cost. [START_REF] Prasoon | An algorithm portfolio approach to reconfigurable set-up planning[END_REF] used a two-step optimisation approach to determine a reconfigurable set-up plan. The aim was to minimise costs and time of production, and achieve customers' specifications as closely as possible. [START_REF] Valente | Development of multi-level adaptive control and scheduling solutions for shop-floor automation in reconfigurable manufacturing systems[END_REF] proposed a dynamic algorithm to schedule automation tasks over time in RMS. The objective was to determine the sequence of automation tasks to be executed, in order to optimise the resource utilisation, considering deadline constraints. [START_REF] Chaube | An adapted NSGA-2 algorithm based dynamic process plan generation for a reconfigurable manufacturing system[END_REF] proposed an adapted non-dominated sorting genetic algorithm II (NSGA-II) to generate a dynamic process plan for RMS. The authors considered a multi objective scenario, aiming at reducing manufacturing costs and time. Nehzati et al. ( 2012) used a fuzzy-based scheduling model to deal with the job assignment problem in RMS. In the model, the fuzzy logic system integrates dispatching rules and scheduling expertise to guide a dynamic selection of dispatching rules in job shops, minimising the total weighted. [START_REF] Azab | Modelling the problem of production scheduling for reconfigurable manufacturing systems[END_REF] considered the problem of scheduling jobs in RMS.

The authors applied a mixed integer linear programming (MILP) model, in order to determine the configuration and job sequence to minimise makespan. Hybrid optimisation approaches have been also used to solve this problem [START_REF] Azab | Modelling the problem of production scheduling for reconfigurable manufacturing systems[END_REF][START_REF] Li | A robust scheduling for reconfigurable manufacturing system using petri nets and genetic algorithm[END_REF][START_REF] Prasad | Reconfigurability consideration and scheduling of products in a manufacturing industry[END_REF].

Increased attention has been given to planning and scheduling problems in RAS. For instance, [START_REF] Meng | Modeling of common organizational structure for reconfigurable assembly system[END_REF] proposed a scheduling approach to realise the scalability and robustness of RAS. [START_REF] Gyulai | Capacity planning and resource allocation in assembly systems consisting of dedicated and reconfigurable lines[END_REF] combined discrete-event simulation and machine learning techniques to handle the complex aspects of the planning problem of RAS. The goal was minimising the cost of production. [START_REF] Kumar | Optimal sequence planning for multi-model reconfigurable assembly systems[END_REF] applied meta-heuristic optimisation techniques to address sequencing problems in RAS. Three objectives were considered: i) optimise the reconfiguration time and costs, ii) fulfil products due dates, and iii) fulfil the workload balance amongst the workstations.

However, despite the relevant contributions in this field, there is a dearth of literature considering manufacturing environments where the resources are assumed to be mobile and where robots collaborate with human operators. Research work in this field have been pursued by several authors [START_REF] Giordani | A decentralized scheduling policy for a dynamically reconfigurable production system[END_REF][START_REF] Mosallaeipour | Mobile robot scheduling for cycle time optimization in flow-shop cells, a case study[END_REF][START_REF] Nejad | A mathematical model and simulated annealing algorithm for solving the cyclic scheduling problem of a flexible robotic cell[END_REF][START_REF] Vieira | Simulation-optimization approach for the decision-support on the planning and scheduling of automated assembly lines[END_REF][START_REF] Yan | A dynamic scheduling approach for optimizing the material handling operations in a robotic cell[END_REF]. Our foremost contribution relies in a general hybrid optimisation approach to solve sequencing and task assignment in RAL, where human and mobile robots collaborate to manufacture products.

PROBLEM DESCRIPTION

The problem presented has been motivated by a manufacturing company that manufactures two different types of products (A and B). The products are assembled in a RAL composed of 10 workstations and mobile robots that can move among the workstations whenever necessary. The workstations follow a U-shaped layout,

The assembly of the products require the execution of a set of tasks, each one with a given processing time and precedence constraints. Both product types have tasks that are performed by humans and mobile robots. Tasks performed by humans are common to both products, while tasks performed by robots are specific to each product type. There is one human operator in each workstation to perform the common tasks. All specific tasks are performed by multitasking mobile robots that can coexist with humans in a workstation. The displacement time of robots among workstations is considered negligible. More than one robot is allowed at a workstation, at a time. Nevertheless, a robot cannot perform more than one task at a time and pre-emption is not allowed.

The production plan of the assembly line is defined in a weekly basis, containing the list of products to be manufactured. Thus, the weekly demand plan of products required to feed the assembly line represents a list of jobs to be produced, including the quantity to be produced in the week, the list of tasks to be performed in each workstation, the set of precedence constraints of tasks of each product, and the corresponding processing times of each task. The workstation line cycle time is determined by the tasks performed by the human operators. This means that, in each workstation, the time taken by the robot(s) to perform their operations must be equal or lower than the time required to the human to perform its operations.

The problem can be stated as follows -a set of jobs, i.e., a set of products, has to be assembled in the line. Each job is composed by a set of specific tasks to be performed by mobile robots in each workstation. The problem consists in determining the sequence of jobs and assigning tasks to robots, minimising the number of robots required to achieve the cycle time desired. To address the problem, the main process data considered, for the workstation 1 (WS1) is shown in Table 2. Task 0 is the transportation time between the initial buffer and WS1 or between two consecutive workstations. This time is constant for all workstations. This means that, after leaving a given workstation the product will take 4.8s to reach the next one. Then, the human operator can begin the execution of the set of common tasks, which were allocated to it (task 100). The set of tasks allocated to humans on each workstation have a common total processing time (30s), corresponding to the assembly line cycle time desired. While the human operator is performing the common tasks, one or more collaborative robots are called to the workstation to perform, in parallel, the product specific tasks.

PROPOSED APPROACH

The proposed hybrid optimisation approach uses a metaheuristic and a list algorithm. The principle of the method is given in Fig. 1. The encoding used by the meta-heuristic is a list Y of jobs. The list algorithm considers the jobs in the list order and assign their tasks to the required mobile robot, respecting the problem constraints. This builds the solution X. The objective function H evaluates the solution X. According to this evaluation, the solution is chosen or not by the meta-heuristic. At the end of the running, the solution given by the hybridisation is the best list (sequence) of jobs: the one that optimises the objective function by applying the list algorithm [START_REF] Klement | A Generic Decision Support Tool to Planning and Assignment Problems: Industrial Application & Industry 4.0[END_REF].

Fig. 1. Hybridisation of a meta-heuristic and a list algorithm

Several planning and scheduling problems have already been solved with this hybrid optimisation approach (Klement et al., 2017a;[START_REF] Mazar | Optimization of Robotized Tasks for the UV-C Treatment of Diseases in Horticulture[END_REF][START_REF] Silva | A Generic Decision Support Tool for Lot-Sizing and Scheduling Problems with Setup and Due Dates[END_REF]. This demonstrates that this approach can be adapted to several problems variants [START_REF] Silva | Solving a Multi-periods Job-shop Scheduling Problem using a Generic Decision Support Tool[END_REF].

Meta-heuristic

The stochastic descent was the based meta-heuristics chosen, due to the easiness of application, thus, speeding up the development process [START_REF] Silva | Solving a Multi-periods Job-shop Scheduling Problem using a Generic Decision Support Tool[END_REF].

The objective was to obtain results rapidly, to evaluate the ability of the proposed approach to solve the tasks assignment and sequencing problems of the RAL studied.

In detail, the meta-heuristic performs in the set of all lists Y . An initial solution is randomly computed: a list of jobs randomly sorted between one and the number of jobs. A neighbourhood is used to visit the set of solutions, allowing to go from one solution to another. The neighbourhood V is a permutation of two jobs in list Y : the job at position i permutes with the job at position j, with i and j being two different random numbers.

List algorithm

This hybridisation can be used to solve many problems, provided that the list algorithm and the objective function are adapted according to the problem considered, by integrating the different constraints that rule the problem and the objective to be improved. The list algorithm is used to build the solution X from the list Y : it assigns the tasks to the mobile robots over the horizon planning, according to the problem constraints. List scheduling algorithms are one-pass heuristics that are widely used to make schedules. It is important to work with a list algorithm, because the meta-heuristic browses the set of lists Y . So the used algorithm needs to consider the order of the list to assign the tasks to resources over the planning horizon [START_REF] Klement | A Generic Decision Support Tool to Planning and Assignment Problems: Industrial Application & Industry 4.0[END_REF]. The list algorithm developed is outlined in Algorithm 1.

Algorithm 1 List algorithm

Input: list of products, list of tasks, processing times of each task Output: sequence of jobs, assignment of tasks to robots, allocation of robots to workstations

1: for all products in the list do 2:

for all workstations do 3:

for the list of tasks do 4:

while there are tasks to be performed do

5:

if the task requires a robot then

6:

if there are no robot in the workstation then

7:

for all robots do 8:

if the robot is available then

9:

Call the robot to the workstation 10:

Assign the task to the robot

11:

Update robot's release time

12:

else 13:

Update the list of tasks to be performed

14:

else 15:

if the robot is available then

16:

Assign the task to the robot

17:

Update robot's release time

18:

else

19:

for all robots do 20:

if the robot is available then

21:

Call the robot to the workstation

22:

Assign the task to the robot

23:

Update robot's release time

24:

else 25:

Update the list of tasks to be performed

Objective function

Solutions are compared according to an objective function that characterises the quality of the solution. The aim is to find the solution X that minimises the number of robots required to achieve the cycle time desired. The set of all lists Y of jobs is browsed thanks to the meta-heuristic, using the neighbourhood V . Lists are compared by the list algorithm and the objective function. According to an acceptance criterion, some lists are selected. At the end, the meta-heuristic gives the best list Y found.

PRELIMINARY RESULTS

In Table 3, the demand generated for each product for a sequence of 4 weeks is presented. The makespan and the number of robots obtained for each week are presented in Table 4.

Given the dimension of the problem and the number of specific tasks for each product, only a sample of the assignment of tasks to the robots is presented in Table 5.

Table 6 presents a small part (15 consecutive jobs) of the sequence obtained in each week. It can be seen that the optimal job sequence seems to be more impacted by job product mix than by production volume. In fact, the sequence obtained for week 1 and 4 with same product mix but different production volumes are equal, but different from sequences for week 2 and 3 which have different product mixes.

The RAL studied was designed to assemble a single product family, composed by products A and B. In Table 3, the product's demand fluctuates during the four weeks: from week 1 to week 2, it decreases 42%; from week 2 to week 3, it increases 28%; and from week 3 to week 4, it increases 22%. The percentage of the product mix also vary: in weeks 1 and 4, there is a demand of 50% of product A and 50% of product B; in week 2, 60% of A and 40% of B; and in week 3, 40% of A and 60% of B. This RAL can cope with all these frequent changes in market demand and product mix. This means that the RAL can adjust its capacity and functionality to abrupt changes on market demand. Indeed, the multitasking mobile robots characterise highly adjustable resources, which can change their functionality whenever necessary, in order to cope with changes in demand or product mix. Furthermore, to move from one workstation to another, these robots must be integrated. These are evidences that this RAL has four of the five core characteristics of reconfigurability implemented: customisation, adaptability, modularity and integrability.

In weeks 1, 3 and 4, the highest volumes are required, but the lowest number of robots is needed. In these weeks, the product mix varies between 50% of A and 50% of B, and 40% of A and 60% of B. In week 2, the lowest volume is required, but the highest number of robots is needed. Thus, when the mix of product includes more than 50% of products A, more robots are required. However, when the product mix includes more than 50% of products B, the number of robots needed does not increase. This may be justified by the number of specific tasks of each type of product; product A has 19 specific tasks and product As can be seen, the utilisation percentage of robots is around 40%. Therefore, in this RAL, managers should analyse the trade-off between achieving the minimum makespan and investing in mobile robots that might have low utilisation percentages.

CONCLUSION

Results show that the RAL proposed can cope with high demand variety in terms of mix and volume. In this case, the demand variety can be accommodated by changing the number of collaborative robots in use and the tasks allocated to each one.

To solve the sequencing and assignment problems in the RAL, this paper proposes a hybrid optimisation approach, that combines a list algorithm with a meta-heuristic. This approach allowed to obtain a good sequence of products, the number of robots needed and the assignment of tasks to the robots that minimise the number of robots required. The proposed approach was tested using a large-scale instance, showing its ability to solve real-world problems.

The metaheuristic used was the stochastic descent. The encoding of more efficient meta-heuristics, e.g. simulated annealing, is envisaged as a development. Previous research work in the field of RMS has shown that simulated annealing may provide interesting solutions in reduced computational time [START_REF] Rabbani | Reconfigurable dynamic cellular manufacturing system: a new bi-objective mathematical model[END_REF].

Future research should consider further constraints, such as considering displacement time for robots in the assembly line, and setup times when the robot change from one task to another, to obtain a more realistic approach of the problem. Moreover, the integration of robots assistance in manufacturing is a relevant research concern [START_REF] Giordani | A decentralized scheduling policy for a dynamically reconfigurable production system[END_REF]. Evaluating these and other evolvable aspects of the Industry 4.0 paradigm will allow the design and operation of quite efficient RAL.

Fig. 2 .

 2 Fig. 2. Utilisation percentage of robots in each week B has 15. Thereby, while product demand impacts on the makespan (the highest the volume, the highest the makespan), product mix impacts on the number of robots needed to perform the specific tasks The utilisation percentage of robots are presented in Fig. 2.

Table 1 .

 1 Core characteristics of reconfigurability

	Characteristic	Description
	Modularity	Modular major components that can be reused
		and exchanged
	Integrability	Ready integration of components and future
		integration of new technologies
	Diagnosability	Detect and diagnose causes of unacceptable
		quality of products and reliability problems
	Adaptability	Adapt system's capacity and functionality by
		means of an adjustable structure to changed or
		new situations
	Customisation Manufacturing systems are designed to produce
		a particular family of products

Table 2 .

 2 Data of tasks to be performed in WS1

	Product	Task ID	Task	WS1 Processing	Precedent task
			type	time (s)
		task 0	transport	4.8
		task 1	specific	9.0	task 0
	A	task 2 task 3	specific specific	3.0 6.0	task 1 task 1
		task 5	specific	1.8	task 3
		task 100	common	30.0
		task 0	transport	4.8
		task 4	specific	4.8	task 0
		task 21	specific	7.2	task 0
	B	task 22 task 23	specific specific	7.2 7.2	task 0 task 21, task 22
		task 24	specific	7.2	task 21, task 22
		task 25	specific	9.0	task 23, task 24
		task 100	common	30.0

Table 3 .

 3 Demand of products (in units)

	Product	Week 1	Week 2	Week 3	Week 4
	A	256	178	190	304
	B	256	118	284	304
	Total	512	296	474	608

Table 4 .

 4 Results obtained using the hybrid approach

	Item	Week 1	Week 2	Week 3	Week 4
	Makespan	15630	9150	14490	18510
	Number of robots	13	15	13	13

Table 5 .

 5 Results: assignment of tasks to robots

	Robot Product WS	Task	Starting time Release time
	1	1	1	1	4.8	13.8
	1	1	1	2	13.8	16.8
	2	1	1	3	13.8	19.8
	...	...	...	...	...	...
	2	511	10	34	15583.8	15598.8
	Table 6. Part of the sequences obtained for
				each week
	Week				Sequence
	1		[A,

B,A,B,A,B,A,B,A,B,A,B,A,B,A,...] 2 [B,A,B,B,A,B,B,B,A,A,A,B,A,A,A,...] 3 [B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,...] 4 [A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,...]

ACKNOWLEDGEMENTS

This research was supported by Portugal 2020 project DM4Manufacturing POCI-01-0145-FEDER-016418 by UE/ FEDER through the program COMPETE2020.