Score Aggregation via Spectral Method

1 Introduction

In a score aggregation system, several agents give scores to a set of candidates independently based on its own personal criteria, and we are going to combine the individual scores to get a final score for each candidate. It is a fundamental process that is integral in everything and intrinsic in our daily life. For example, in schools, each student has scores on different courses and we want to use a single score, such as GPA, to evaluate the overall performance of the student. It has direct application in scoring-based rank aggregation problems. Score aggregation not only plays an important role in social choice theory [Moulin et al., 2016], but also receives a wide range of applications in multi-agent system [Ephrati and Rosenschein, 1991], spam detection [Dwork et al., 2001], bioinformatics, graph drawing [Jackson et al., 2008], database [Fagin et al., 2003] and so on.

In a score aggregation system, agents' criteria may be different and the score profile of each candidates may also differ under different criteria. Score aggregation methods try to make a tradeoff among these different attitudes. In score aggregation problems, usually we investigate methods and mechanisms to get reasonable scores from agents and then take the simple sum (or average) value as the aggregate score. There are several methods developing rules for scoring candidates based on preference rankings [Brams and Fishburn, 2002] [Caragiannis et al., 2017]. In a positional scoring rule, a scoring vector s = (s1, s2, · · · , sm) of m candidates is given, and a candidate receives a score of sk from an agent if it is ranked at position k in the agent's preference ranking. The well-known Borda method [Borda, 1781] [Arrow et al., 2010] uses the positional scoring rule by letting the scoring vector be s = (m- 1,m- 2, · · · , 0). There are also many other models, such as plurality rule [Feddersen and Wright, 1990], k-approval rule [Brams and Fishburn, 2007], veto [Spitzer and Fisher, 1988] and so on. The main difference among them boils down to the way the agent gives the score. For some cases where the scores are given, people may study methods to modify the scores to make them of the same commensurability by using normalization or weighted methods. The weighted sum-up method is to set a weight to each agent and use the weighted sum scores as the final result. The weights of the agents should reflect the attitudes or differences of the agents. All above investigations are focusing on how to give or adjust the scores to the same measure. After these, the second step is to simply sum up (or average) the adjusted scores.

∗The work was supported by the National Natural Science Foundation of China (61370071), and the Fundamental Research Funds for the Central Universities (ZYGX2015J057).

Actually, the second step is the real operation of 'aggregation'. However, except the simple sum-up (average) method, we are not aware of any other score aggregation methods in social choices. In this paper, we consider the real 'aggregation' operation and introduce a nontrivial mechanism for score aggregations. In our models, we always assume that the scores (data) from agents are of the same measure, or we have done something (such as normalizations) to make them of the same measure, or there is no way to know whether or not the scores from different agents mean the same thing. Under this assumption, we may also be able to regard the model as a 'noise model': there is a ground truth scoring of the candidates, and each agent's score is a noisy estimate of the ground truth. In real life, there are many factors contribute to the noise, such as the bias from each agent, different criteria of each agent, the fluctuation of the candidate's performance, and so on. The Central Limit Theorem says that the sum of many independent random variables will tend towards the Gaussian distribution. If all the effects causing noises are independent, we can believe that the sum of them approximately obeys the Gaussian distribution by the Central Limit Theorem. In the noise models, it is nature to employ a score aggregation method that finds a result most likely to coincide with the ground truth. The simple sum-up or average method may not always return an optimal result. This also motivates the study of this paper.

In social choices, the noise models have been studied in rank aggregations, especially for rules under pairwise comparisons [Procaccia et al., 2012][Shah et al., 2015][Xia et al., 2010][Caragiannis et al., 2014][Conitzer et al., 2009][Mao et al., 2013]. For example, in a noise model for the rank aggregation problem, there is a correct ranking of the candidates and every voter has a noisy perception of this correct ranking. Roughly speaking, each voter ranks each pair of alternatives in the correct order with probability p > 1/2, and in the wrong order with probability 1 - p. In this model, the Kemeny rule can be interpreted as a maximum likelihood estimator of the correct ranking. Many other rules have been also studied in the literature.

In this paper, we focus on score aggregations and try to find an aggregate result most likely to coincide with the ground truth. To do this, we define the 'noise information' as the total squared distances between the original score and the corresponding aggregate score for each candidate, and use a spectral method to find a solution that minimizes the noise information. Note that when the noises obey the Gaussian distribution, minimizing the noise information is equal to maximizing the likelihood function. Our spectral method first conducts an eigenvalue decomposition to the judgment matrix of the score data and then uses the eigenvector corresponding to the largest eigenvalue as the synthesized preferences of the agents. The linear expression of the score matrix on this eigenvector will be used as the final scores of the candidates. Furthermore, it is easy to evaluate the validity of the aggregate scoring or the consistency of the agents. In order to describe it in a clear way, we will give both algebraic and geometric explanations for score aggregation and begin with the simple sum-up method.

2 The Problem

We consider settings with a set of n agents A and a set of m candidates C. Each agent gives a score within the range of the scoring standard to each candidate according to the performance of the candidate and the preference of the agent. A score is a real nonnegative number. Our goal is to get a reasonable consensus scoring over all the candidates as close to the score profile given by the agents as possible.

The score profile can be presented by a matrix, named the score matrix, which is formally defined below.

Definition 1. (Score Matrix) A score matrix of n agents on m candidates is an m × n matrix

where xij is the score of candidate i obtained from agent j.

The score matrix is also written as follows:

where the row vector ci = (xi1, xi2, · · · , xin) is the scores of candidate i obtained from all the agents and the column vector aTj = (x1j , x2j , · · · , xmj) is the score of all candidates given by agent j.

The score aggregation problem is to find an m×1 vector v to represent the score matrix Xm×n, where the ith element in v is the final score of the ith candidate. What kinds of vectors v are good? There is no formal definition. Different problem models give different optimal objects and yield different optimal algorithms. We aim at constructing a reasonable problem model with a clear objective and design an algorithm that can find an optimal solution under our model.

Firstly, we view the score aggregation problem from a geometric perspective. We consider the vector space A with the basis vectors being a1, a2, · · · , an, representing the n agents. Each candidate is presented by a point ci = (xi1, xi2, · · · , xin) in the vector space such that the scalar xij on axis aj is the score of candidate i given by agent j. Figure 1 shows a two-dimensional vector space with 2 agents a1 and a2 and 5 candidates ci. The score matrix of the candidates is

The score aggregation problem is to map the m points (candidates) in the n-dimensional vector space A into m points in a one-dimensional vector space e, called the object vector space. There are two things we need to do: the first is to decide which one-dimensional vector e to be mapped onto (we will only be interested in the direction of the vector and consider the unit vector e so that eeT = 1 by ignoring the magnitude of it); and the second is to decide the rules of how to map a point in A into a point in e. Next, we show how the two steps work on the sum-up and average methods.

3 The Sum-up and Average Methods

The sum-up and average methods are simple and widely used in practice. The sum-up method is to use the sum of all scores of a candidate as the final score profile of the candidate, and it returns the vector

The average method, a special case of the weighted sum-up method, is to use average score of a candidate as its final score profile, and it returns the vector

The results of the two methods can be transferred to each other by dividing or multiplying by a factor n. So these two methods are essentially the same.

Without loss of generality, we look at the average method. The output of this method is obtained by multiplying a vector e = (1/n, 1/n, · · · , 1/n)T to the score matrix Xm×n, i.e.,

.

The geometric explanation of the above formula is to project the m points ci = (xi1, xi2, · · · , xin) for i = 1, · · · ,m in the vector space A onto the object vector space eT = (1/n, 1/n, · · · , 1/n)T . For the purpose of presentation, we always consider the vector e to be mapped onto as a unit vector so that eeT = 1. Then we assume that we project the m points onto the unit vector e′ = (1/√n, 1/√n, · · · , 1/√n) and will multiple a scalar ||e|| = 1/√n in the final result. We use ˆ ci to denote the projection point of the original point ci onto the unit vector e′ . Figure 2 illustrates the projection in a two-dimensional space with n = 2. We will show that the score of each candidate i obtained by the average method is the coordinate of ˆ ci in the vector space e′ multiplying the scalar ||e|| = 1/√n.

We prove a general result. Let e be an object vector and a = Xm×n · e be the aggregate score. Let e = ||e|| · e′ , where e′ is a unit vector. Let ˆ ci be the projection of ci on the vector e, and pi be the projection length of ci.

Theorem 1. Let a(i) denote the ith element in a, i.e., the aggregate score of candidate i. It holds that

Proof. We consider candidate i and the point ci = (xi1, xi2, · · · , xin) in the vector space A. Let θ be the angle between ci (taking it as a vector) and the vector e. It holds that

The projection length of the point ci onto the vector e is

The theorem holds.

For the sum-up method, we multiply a a vector e′′ = (1, 1, · · · , 1) by the score matrix Xm×n. The object vector is e′′ = (1, 1, · · · , 1) = √n · e′ , where e′ is the same unit vector as that in the average method. So the score of each candidate i obtained by the sum-up method is the projection length of the point ci multiplying the scalar ||e′′ || = √n.

The sum-up and average methods are essentially the same if we ignore the stretching factor. They select the unit vector e′ = (1/√n, 1/√n, · · · , 1/√n) (after ignoring the stretching factor) as the object vector to be mapped onto; and then map each original point ci to a point ˆ ci on the object vector such that the total noise information E is minimized, which is defined as the total least squared distance between the original data points and the mapped points, i.e.,

Since ˆ ci is the projection of ci on e′ , we know that ˆ ci is the point on e′ such that || ˆ ci - ci|| is minimum. However, we prefer to use the squared distance as the object to be optimized since the squared distance has more good properties and is commonly used in the literature. Furthermore, when the noises obey Gaussian distribution, to minimize the squared distance is equal to maximize the likelihood function.

4 The Spectral Method

The sum-up and average methods fix the object vector e′ = (1/√n, 1/√n, · · · , 1/√n) and then map the points onto it to minimize the total least squared distance. The second step is reasonable, since the total least squared distance is a standard measure widely used. However, why always choose e′ = (1/√n, 1/√n, · · · , 1/√n) as the object vector to be projected? This method seems to always treat all agents as equally important without clear reasons. In Figure 3, if we select the object vector as e∗ = (2/√5, 1/√5) instead of e′ = (1/√2, 1/√2) to be projected, we can get projection points with a smaller noise information E. We can see that the total squared distance by selecting e∗ = (2/√5, 1/√5) as the object vector is less than that of selecting e′ = (1/√2, 1/√2). See Figure 3 for an illustration.

Here arises a question how to find the optimal object vector e∗ to minimize the total least square distance? We will answer this question by giving a simple algorithm that calculates the aggregate scores by minimizing the total squared distance. In our algorithm, we do not solve lots of functions to find the optimal object vector and to compute the solution. Instead, we use a spectral method, which is simple to implement and easy to analyze. It is surprising that the spectral method matches all these well.

Our algorithm computes the judgement matrix (defined below) and then uses the eigenvector corresponding to the largest eigenvalue of the judgement matrix as our object vector.

Definition 2. (Judgement Matrix) Given a score matrix Xm×n, a judgement matrix of Xm×n is an n × n matrix

The main steps of our algorithm are listed below.

Algorithm SPECTRAL

Input: A score matrix X

Output: A vector corresponding to the aggregate scores of candidates

1. Compute the judgement matrix Z = XT ×X;
2. Conduct eigenvalue decomposition to Z, let λmax be the largest eigenvalue and e be the eigenvector corresponding to it;
3. Return v =X ×e.

By Theorem 1, we know that the aggregate score of candidate i by our algorithm is the projection length of the point ci multiplied by the scalar ||e||. Next, we prove the following theorem to show the optimality of our algorithm.

Theorem 2. The eigenvector e corresponding to the largest eigenvalue of the judgement matrix Z is a vector to be projected onto such that the total squared distance E reaches the minimum value.

Proof. Assume e is the optimal object vector that minimizes the total squared distance E. Let ˆ ci = pie denote the mapped points on e, where pi is its coordinate. The total squared distance between the original points and the projection points is

Consider the minimization with respect to pi, setting the partial derivative of E with respect to pi to zero, we obtain

The above equivalent implies that the scalar pi is the projection onto the direction e. If we substitute for pi in (1) by using (2), we obtain

Note that ∑mi=1 ||ci||2 is a constant and

is exactly the judgement matrix. To minimize E is then to maximize

We will add a constraint eeT = 1 to maximize J, which requires the vector e being an unit vector and then constrains the solution.

We use a Lagrange multiplier λ to enforce the constraint, and then make an unconstrained maximization of

Setting the derivation with respect to e to zero, we see that this quantity will have a stationary point when

which says that eT must be an eigenvector of Z. To minimize E or maximize J, the eigenvector that corresponds to the maximum eigenvalue should be chosen.

5 Consistency Analysis

The spectral method can always output an aggregate scoring to candidates. However, how much credit we can put on to this scoring or how consistent this scoring is with the agents? We want to use a measure to evaluate the unconsistency of the input data, which can also be recognized as the noise. The total squared distance E defined above is a nice indicator. However, there exists no absolute scale for the total squared noises, but rather all these are quantified relati to the original scores. These is a famous indicator, called the signal-to-noise ratio (SNR), frequently used in industry and real life, which is defined as the follows

A high SNR (≫ 1) indicates a good extraction of the data, while a low SNR indicates a poor measurement. In our model, the extracted information is the total squared projection distance and the error is the total squared distance between the original data points and the projection data points. Thus, in our problem,

where pi is the projection distance of point ci. We suggest to use SNR as the consistency indicator. For some data, our SNR is not large, which means that the scores given by the agents are not consistent. For this case, if the score aggregation is used to rank the candidates, then we know that the input data is not enough to get any reliable order of the candidates due to the very different attitudes of the agents. How to set the threshold of SNR is worthy of deep studying, which should differ for different types of data and applications.

Another advantage of adopting SNR is that there is a simple way to compute the value of SNR in our method. It is enough to calculate the eigenvalues of the judgement matrix.

Theorem3. Let λ1, λ2, · · · , λn denote the eigenvalues of the judgement matrix Z, where λi ≥ λj for i > j. The consistency indicator of the scoring obtained by the spectral method is

Proof. Let e denote the eigenvector corresponding to the largest eigenvalue of the judgement matrix Z. Note that cieT = ecTi = pi is the projection distance of point ci on the direction e. We have that

On the other hand, since e is the eigenvector corresponding to the largest eigenvalue of Z, it holds that

Thus, we have

Next, we only need to prove that

Note that for a judgement matrix Z, it holds that

Since ˆ ci is the projection of ci onto e, it holds that

Then,

The theorem holds.

6 Relations with TheWeighted Sum-up Method

The weighted sum-up method is to set a weight wj to agent j and use the weighted score ∑nj=1 wj xij as the final score for candidate i. Therefore, the weighted sum-up method outputs

It is to project the points onto the object vector (w1,w2, · · · ,wn). For the weighted sum-upmethod, the crucial part is to set the weights wi to agents. Traditionally, we set the weights according to experiences or some other given information. The purpose is to make the agents of the same commensurability.

Our spectral method, however, assumes that all the agents are almost of the same commensurability, uses the eigenvector e corresponding to the largest eigenvalue of the judgement matrix Z as the object vector, and sets the weights of agents as the eigenvector e. Our method can be regarded as a self-adapted step to set the weights of agents to minimize the noise information. Our method can combine with the traditional weighted sum-up method well: we first set a weight to agents artificially to make the agents of almost the same commensurability and then apply our spectral method on the adjusted scores to get the second weight. The second weight can also be used to adjust the first weight.

7 Computational Examples and Applications

Here we give computational results on some real word data as examples. The first example is about scoring movies. Our data is from GroupLens Research (https://grouplens.org/datasets/movielens/), which collects the rating data for movies from the web site MovieLens (http://movielens.org) [Harper and Konstan, 2016]. The database we used is ml-latest-small, which describes 5-star rating for movies by users from movieLens. Ratings are made on a 5-star scale, with half-star increments (0.5 stars - 5.0 stars). Users are represented by an ID without other information. Here we give a simple example with a small number of movies and users. We randomly choose six famous movies and six users who had seen more than 500 movies (including all the six movies). The movies are Forrest Gump (1994), Star Wars: Episode IV - A New Hope (1977), Toy Story (1995), Dead Men Don't Wear Plaid (1982), The Fugitive, (1993), Seven (1995), and the userID are 15, 23, 30, 73, 212, 213. We obtain the following score matrix

.

We run our algorithm on this score matrix, the final scores of these six movies are v1 = {3.40, 4.12, 3.71, 3.88, 4.07, 4.44}1 , while the final scores of the average method is v2 = {3.33, 4.08, 3.58, 3.83, 4.08, 4.50}. The signal-to-noise ratio SNR of our result is 21.7, which is greater than 18.8 for the average method. This is a computational example on a small number of samples to show the computational steps of our algorithm and compare the results. Next, we give an example on a big date set.

The next example is about ranking universities according to the publications. Our data is from the web site of CWTS Leiden Ranking (http://www.leidenranking.com/). The CWTS Leiden Ranking 2016 offers key insights into the scientific performance over 800 major universities worldwide. A sophisticated set of bibliometric indicators provide statistics on the scientific impact of universities and on universities involvement in scientific collaboration. We focus on the indicator called 'top 10% P', which is the number of a university's publications belong to the top 10%most frequently cited in the year. CWTS Leiden Ranking 2016 collected the data from the following five main fields of science: Biomedical and health sciences (Bio), Life and earth sciences (Life), Mathematics and computer science (M&C), Physical sciences and engineering (P&E), and Social sciences and humanities (Soc). The default way is to use the sum of the top 10% cited publications in all the five fields as the indicator of the university, i.e., the sum-up method. We use our method to obtain a result. The first 15 universities under our method are listed in Table 1.

In this table, the column 'ours' is the results of our method, comparing the column 'total' of the results of the sum-up method. In these two columns, the number in the bracket is the final score obtained by the corresponding method and the number out of the bracket is the position ranked by using these scores. The next five columns denote the numbers of top 10% cited publications of these universities on the five main fields.

From the table we can see that some universities with a smaller number of total top 10% cited publications are ranked higher in our method, for examples, Johns Hopkins Univ. and UC-San Francisco. These universities have a large number of top 10% cited publications in some fields say Bio. and a small top cited publication number in other fields. Our method rank these universities higher because the major fields of these universities are strong, although they may not be strong in every field. We think this is reasonable and even can be regarded as an advantage of our method. We should encourage universities (agents) to develop some strong fields, instead of all fields with a middle level.

1 In fact, the scores were divided by √n = √6 to make them of the same stretching factor as the average method.

We also note that MIT is not ranked very high in our method, although it has the largest numbers of top 10% cited publications in two fields M&C and P&E. The reason is that the total numbers of top 10% cited publications in these two fields are not large. If we normalize all fields to reduce the differences among them, the situation will be better. Now we apply our method directly without any normalization, which indicates that we assume all fields are of the same commensurability. Under this assumption, small total numbers of top 10% cited publications in the two fields M&C and P&E will indicate small influences of these two fields. It is reasonable.

8 Conclusion

This paper suggests a new method for score aggregation, which uses spectral analysis. Our method assumes that all the agents are of the same commensurability and finds an 'optimal' aggregate scoring minimizing the 'noise' part. The new method may open up a new dimension along which scoring rules could be defined and evaluated. It also gives rise to many interesting problems in social choice for further study.

For the method itself, there are also some important issues worthy of further study. For example, this paper only considers projecting scores on vectors which begin with the origin. Could we get better results if we consider other vectors as well? It is possible. However, we may get strange results for some extreme cases. Here is an example of two candidates with scores (1, 3) and (3, 1) from two agents, the global optimal vector of which will pass through these two points. For this case, it is hard to explain the meaning of the projection. It will also be interesting to study more properties and types of vectors to be projected on.