Consider an evaluator, or an assessor, who needs to assess a large amount of information. For instance, think of a tutor in a massive open online course with thousands of enrolled students, a senior program committee member in a large peer review process who needs to decide what are the final marks of reviewed papers, or a user in an e-commerce scenario where the user needs to build up its opinion about products evaluated by others. When assessing a large number of objects, sometimes it is simply unfeasible to evaluate them all and often one may need to rely on the opinions of others. In this paper we provide a model that uses peer assessments to generate expected assessments and tune them for a particular assessor. Furthermore, we are able to provide a measure of the uncertainty of our computed assessments and a ranking of the objects that should be assessed next in order to decrease the overall uncertainty of the calculated assessments.
Consider an assessor who needs to assess a large amount of information. For instance, think of a tutor in a massive open online course with thousands of enrolled students, a senior program committee member in a large peer review process who needs to decide what are the final marks of reviewed papers, or a user in an e-commerce scenario where the user needs to build up its opinion about products evaluated by others. When assessing a large number of objects, sometimes it is simply unfeasible to evaluate them all and often one may need to rely on the opinions of others. In the process of building up our opinion, some questions need to be answered, such as: How much should I trust the opinion of a peer? What should I believe given a peer’s opinion? What should I believe when many peers give their different opinions? Which objects should be assessed next, such that the certainty of my belief improves?
This paper addresses these questions through the Personalised Automated ASsessment model (PAAS). PAAS uses peer assessment to calculate and predict assessments. However, what is fundamentally different from many previous works [Piech et al., 2013; de Alfaro and Shavlovsky, 2013;
Walsh, 2014; Wu et al., 2015] is that the computed peer-based assessment is tuned to the perspective of a specific community member. PAAS aggregates peer assessments giving more weight to those peers that are trusted by the specific community member whom the automated assessments are computed for. How much this specific member trusts a peer is then based on the similarity or evaluation rate between his (past) assessments and the peer’s (past) assessments over the same assignments. To compute such a trust measure, we build a trust network conformed of direct and indirect trust values among community members. Direct trust values are derived from common assessments while indirect trust is based in the notion of transitivity. We clarify that our target is not consensus building, but to accurately estimate unknown assessments from a specific member’s point of view, based on the peers’ assessments and reliability.
Finally, we are also able to provide a measure of the uncertainty of our calculated assessments and a ranking of the objects that should be assessed next in order to decrease the overall uncertainty of those calculated assessments. 2 2.1
Let represent an assessor who needs to assess a large set of objects I, and let P be a set of peers that are able to assess objects in I.
We understand assessments as probability distributions over an evaluation space E at a given moment in time. For example, one can define a set of elements for the evaluation space for the quality of an English classroom homework as E = fpoor; good; excellentg. The assessment fpoor 7! 0; good 7! 0; excellent 7! 1g would represent the highest assessment possible, whereas the assessment fpoor 7! 0; good 7! 1=2; excellent 7! 1=2g would represent that the quality of the homework is most probably between good and excellent, and so on.
We define an assessment ei (also referred to as evaluation or opinion) as a probability distribution over the evaluation space E , where 2 I is the object being evaluated and i 2 f [ Pg is the evaluator. We say ei =fx1 7! v1; : : : ; xn 7! vng, where fx1; : : : ; xng = E and vi 2 [0; 1] represents the value assigned to each element xi 2 E , with the condition . .
i2jEj
Finally, we define L as the history of all assessments performed, and O L as the set of past peer assessments over the object .
The ultimate goal of our work is to compute the probability distribution of ’s evaluation over a certain object , given the evaluations of several peers over that same object . In other words, what is the probability that ’s evaluation is x given the set of peers’ evaluations O ? Such expectation can be formalized with the conditional probability as follows: p(X=x j O )
To calculate the above conditional probability, we take into account every particular evaluation in O . In other words, expectations (or probabilities) are calculated for each individual evaluation in O , before those expectations are aggregated into p(X=x j O ). The probability that ’s assessment is x given a particular evaluation e 2 O is formalized as follows:
p(X=x j e )
The more general probability p(X=x j O ) is then defined as an aggregation of the individual probabilities:
p(X=x j O )=p(X=x j e ) where the exact definition of the aggregation is presented later on in Section 2.4.
We strongly base the intuition behind the computation of the individual conditional probabilities on the notion of trust between peers based on previous experiences, where trust is understood in this context as the expected similarity between the assessments given by those peers. In other words, our intuition is that we expect will tend to agree with ’s assessments if his trust on is high. Otherwise, ’s evaluation will probably be different. We perform then a sort of analogical reasoning: if in the past gave opinions that were a certain degree dissimilar from ’s opinions, then this will probably happen again now.
The remainder of this section is divided accordingly. We first describe in detail how the measure of trust between peers is calculated (Section 2.2). Then, we illustrate how to calculate ’s assessment on an object given ’s assessment over and ’s trust in ’s assessments (Section 2.3). In other words, we present an approach for calculating the individual probability p(X=x j e ). We then illustrate how to combine those probabilities to build the probability distribution of ’s assessments given the assessments of several peers (Section 2.4). In other words, we present an approach for calculating the probability p(X=x j O ). Finally, we provide a measure of the uncertainty of the computed assessments and a ranking of the objects that should be assessed next by in order to decrease that uncertainty (Section 2.5). 2.2
needs to decide how much can he or she trust the assessment of a peer . We define this trust measure based on the following two intuitions. Our first intuition states that if and have both assessed the same object, then the similarity of their assessments can give a hint of how close their judgments are. However, cases may arise where there are simply no objects evaluated by both and . In such a case, one may think of simply neglecting ’s assessment, as would not know how much to trust ’s assessment. Our second intuition, however, proposes an alternative approach for such cases, where we approximate that unknown trust between and by looking into a chain of trust between and through other peers. Roughly speaking, we relay on the transitive notion: “if trusts , and trusts 0, then will likely trust 0”. In the following, we define these two intuitions through two different types of trust relations: direct trust and indirect trust.
Direct trust is the trust relation that emerges between evaluators that have assessed one or more objects in common. One possible approach is to measure such relation as aggregations of their evaluations’ similarity over those objects assessed in common. For instance, let the set Ai;j = f j ei ; ej 2 Lg be the set of objects that have been assessed by both evaluators i and j. Then different definitions for the direct trust between i and j based on the similarity between two assessments (sim(ej ; ej )) may be adopted, such as as: The average of the similarities for all commonly assessed objects:
TD(i; j)= 2Ai;j
X sim(ei ; ej )
jAi;j j The conjunction of the similarities for all commonly assessed objects:
TD(i; j)= ^
sim(ei ; ej ) 2Ai;j The Pearson coefficient [Upton and Cook, 2008], or linear correlation between i and j, for all commonly assessed objects: TD(i; j)=s
X sim(ei ; ei) sim(ej ; ej ) 2Ai;j X sim(ei ; ei)2s 2Ai;j
X 2Ai;j sim(ej ; ej )2 where ei, ej are the means of the evaluations performed over the set Ai;j by i and j respectively.
However when we calculate such aggregations we loose relevant information. For instance, we are not able to tell if j usually under rates with respect to i, if it usually over rates, or neither. We are also not able to tell if the dissimilarities between i and j’s evaluations are highly variable or not.
To cope with such loss of information, we define the direct trust between two peers i and j as a probability distribution TDi;j : [0; 1] ! [0; 1] built from the historical data of previous evaluations performed by i and j. This probability distribution describes, as we will explain shortly, the expected similarity or the expected evaluation rate between i and j’s assessments. The support of the distribution is [0; 1] since both the expected similarity and the expected evaluation rate are in the range [0; 1], as we will see shortly, and the range of the distribution is [0; 1] as this is a probability distribution and the range of any probability is [0; 1]. Note that we do not consider here any summarizing measure for trust that would translate that distribution into a single value, although a number of measures could be used, such as the average similarity (as the center of gravity of the distribution) or entropy (as a measure of the uncertainty of the distribution).
When defining TDi;j we distinguish two cases: (1) a first case with a non-ordered evaluation space, such as E = fvisionary; original; soundg; and (2) a second case with an ordered evaluation space, such as=fbad; good; excellentg. In the second case, we are interested in maintaining information about whether a peer under rates or over rates with respect to another peer, therefore we are interested in the expected evaluation rate between i and j. In the first case, this is not an issue as assessments cannot be ordered and therefore the notion of under/over rating does not exist, therefore we are rather interested in the expected similarity between i and j’s assessments. Next we detail the trust probability distributions TDi;j built for both cases.
In the non-ordered case, we are interested in the similarity between i and j’s assessments. As such, the support of the distribution representing i’s direct trust on j (i.e. the x-axis of TDi;j ) consists of the possible degrees of similarity between i and j’s assessments.
Trust distribution TDi;j (x) then describes the probability that peers i and j evaluate an object with a similarity x (or the probability that the similarity of their evaluations is x).
In the ordered case, we are interested in the evaluation rate ej=ei between evaluations made by peers i and j. If ej=ei = 1, this means that i and j provide the same evaluation. If ej=ei > 1, this meas that j over rates with respect to i. If ej=ei < 1, this means that j under rates with respect to i.
We normalize the evaluation rate to values between 0 and 1. To do so, we require a non decreasing function r : R ! [0; 1] such that limx!1 r(x)=1, and for convenience we constraint r(1)=0:5. We adopt the following normalized evaluation rate function that satisfies these properties: r(x)=eln 1=2=x (1) As such, the support of the distribution representing i’s direct trust on j (i.e. the x-axis of TDi;j ) consists of the possible normalized evaluation rates between i and j. Trust distribution TDi;j (x) then describes the probability that i and j would assess an object with a normalized evaluation rate x.
In what follows, we explain how we build direct trust distributions computationally, based on previous experiences.
Initially, the direct trust distribution between any two peers
is the uniform distribution F=f1=n; : : : ; 1=ng (describing
ignorance), where n is the size of the distribution’s support.
Every new assessment made would then update the trust
distributions accordingly. Consider a new assessment ei . The
distribution TDi;j 8j s.t. Ai;j 6= ; is updated as follows:
1. We find the element x in TDi;j ’s support whose
probability needs to be adjusted. So we calculate x=sim(ej ; ei )
in the ordered case
TDi;j (X) = arg min X p(X=x0) log
P0(X) x0 such that fp(X=x) = p0(X=x)g p(X=x0) p0(X=x0) (3) where p(X =x0) is a probability value in TDi;j , p0(X = x0) is a probability value in P0, and fp(X=x) = p0(X= x)g specifies the constraint that needs to be satisfied by the resulting distribution.
Given a direct trust relation between peers i and j and between peers j and k, the question now is: What can we say about the indirect trust between peers i and k when i and k have no objects assessed in common? In other words, given the direct trust distributions TDi;j and TDj;k, what can we say about the indirect trust distribution TIi;k?
As with direct trust distributions, we distinguish two cases: a first case where assessments cannot be ordered and thus trust is based on a similarity measure sim; and a second case where assessments can be ordered and thus trust is based on a normalized evaluation rate function r(x)=eln 1=2=x.
In this case, we want to preserve the fundamental triangular inequality property of similarity functions that says that: T-norm(sim(a; b); sim(b; c)) sim(a; c).
As with TDi;k, the support (or the x-axis) of TIi;k consists of the possible degrees of similarity between i and k’s assessments. But since these degrees of similarity should satisfy the T-norm, the support is defined as the set: supp(TIi;k)=fxik=T-norm(xij ; xjk) j xij 2 supp(TDi;j ) i to m and m to k), we obtain multiple indirect trust distribu^xjk 2 supp(TDj;k)g tions (one from every chain). In those cases, we pick the re
sulting distribution which is most optimistic. In other words, where supp represents the support of a distribution. while our approach to calculate the indirect trust follows the We then compute the probabilities of the expectations of pessimistic approach (through our choice of the product operTIi;k as follows: ator in Equations 4 and 5), we now choose the most optimistic of the pessimistic outcomes. To do that, we choose the distrifp(X=xik=T-norm(xij ; xjk))=TDi;j (xij ) TDj;k(xjk) j bution that is closest to the equivalence distribution, which is xij 2 supp(TDi;j ) ^ xjk 2 supp(TDj(;4k))g a distribution that describes that the evaluations of two peers This could result in more than one probability computed are equivalent. In the non-ordered case, the equivalence disfor the same expectation xik. As such, we then add up all tribution is PE(1)=1; that is, the similarity between two peers the probabilities that correspond to the same expectation is maximum. In the non-ordered case, the equivalence distribution is PE(0:5) = 1; that is, the normalized evaluation rate between two peers is 0.5, which implies that they always provide the same evaluation. The distance between an indirect trust distribution TIi;k and the equivalence distribution PE can be calculated as:
The calculations presented above provide an approach for calculating indirect trust between two peers i and k when those peers are linked through a direct trust chain passing through only one intermediate peer j. For direct trust chains of increasing length between i and k, the previous process is iterated. For instance, if there is a direct trust chain linking i to j, j to m, and m to k, then we first compute the indirect trust distribution TIi;m from the direct trust distributions TDi;j and TDj;m, and then we compute the indirect trust distribution TIi;k from the direct/indirect trust distributions TIi;m and TDm;k, following the same approach as above.
When multiple chains of direct trust connect two peers (e.g.
say a chain linking i to j and j to k, and another chain linking xik.
We note that we follow a conservative approach by adopting the product operator (Equation 4), which is a T-norm that gives the smallest possible values, as we prefer not to overrate indirect trust values since they are not inferred directly from historical data. Of course, other operators could also be used, such as the min function.
In this case, we want to preserve the property: ej=ei ek=ej=ek=ei with respect to the evaluations performed by i, j and k. For instance, if the evaluation rate between ej and ei is 0.5 (j under rates a 50% with respect to i) and the evaluation rate between ek and ej is 0.5 (k under rates a 50 % with respect to j) then the evaluation rate between ek and ei should be 0.25 (then k under rates a 75 % with respect to i).
As above, the support (or the x-axis) of TIi;k consists of the possible degrees of similarity between i and k’s assessments. The support us then defined as the set: supp(TIi;k) = fxik=xij xjk j xij 2 supp(TDi;j ) ^xjk 2 supp(TDj;k)g We then compute the probabilities of the expectations of TIi;k as follows: fp(X=xik=xij
xjk) = TDi;j (xij ) TDj;k(xjk) j xij 2 supp(TDi;j ) ^ xjk 2 supp(TDj;k)g (5)
Again, this could result in more than one probability computed for the same expectation xik. As such, we then add up all the probabilities that correspond to the same expectation xik. emd(TIi;k; PE) (6) where emd is the earth mover’s distance which calculates the distance between two probability distributions [Rubner et al., 1998].1 We note that the range of emd is [0,1], where 0 represents the minimum distance and 1 represents the maximum possible distance.
In the remainder of this paper, when we refer explicitly to a direct or indirect trust distribution between peers i and j, we refer to such distribution as TDi;j or TIi;j , respectively. Whereas when we refer generically to a trust distribution that could either be the direct or indirect trust distribution, we refer to such a distribution as Ti;j .
Direct and indirect trust relations in a community can be represented by a weighted directed graph. We define a community’s trust graph as:
G=hN; E; wi 1If probability distributions are viewed as piles of dirt, then the earth mover’s distance measures the minimum cost for transforming one pile into the other. This cost is equivalent to the ‘amount of dirt’ times the distance by which it is moved, or the distance between elements of the probability distribution’s support. where the set of nodes N is the set of evaluators in f [ Pg, E N N are edges between evaluators with direct or indirect trust relations, and w : E 7! [0; 1]n is the weight of an edge, described as a trust probability distribution.
D E is the set of edges that link evaluators with direct trust relations: D = f(i; j) 2 E j TDi;j 6= ?g. Similarly, I E is the set of edges that connect evaluators with indirect trust relations: I = f(i; j) 2 E j TIi;j 6= ?g n D. We note that the set of edges E is then composed of the union of the set of direct and indirect edges: E = D [ I. Weights in w describe direct and indirect trust probability distributions and are defined as follows: w(i; j) = TDi;j , if (i; j) 2 D
TIi;j , if (i; j) 2 I Our goal is to determine how much a particular evaluator can trust a peer . So the trust graph is constructed with respect to ’s point of view only. Therefore, we maintain a trust graph of the whole community containing all the direct edges between peers (as they are needed to calculate indirect trust relations), but we only maintain the indirect edges that connect with the rest of the peers.
An important notion in our proposal is the notion of the decay of information. We say the integrity of information decreases with time. In other words, the information provided by a trust probability distribution should lose its value over time and decay towards a default value. We refer to this default value as the decay limit distribution D. For instance, D may be the uniform distribution, which describes that trust information learned from past experiences tends to ignorance over time.
To implement such a decay mechanism, we need to: 1. Record all evaluations ei 2 L made at time t with a timestamp t, noted ei t . 2. Record all direct trust distributions TDi;j with a timestamp t, noted TDit;j , where t is the timestamp of the last evaluation that modified the trust distribution. The first time TDi;j is calculated, t is the timestamp of the latest evaluation amongst the two evaluations leading to this calculation. (Recall that it is the similarity between two evaluations or the evaluation rate that updates the probability distribution.) Then, every time a new evaluation with timestamp t0 > t is considered to update TDit;j , TDit;j is first decayed from t to t0 before the distribution is updated. 3. Record all indirect trust distributions TIi;j with a timestamp t, noted TIit;j , where t is the time the distribution is calculated. Every time TIi;j is calculated, all probability distributions involved in this calculation will first need to be decayed to the time of calculation t. The time of calculation is usually the latest timestamp amongst the timestamps of the distributions involved in this calculation.
Information in a trust probability distribution Ti;j decays from t to t0 (where t0 > t) as follows:
t t0 = (D; Tit;j ) Ti;j (7) where lim t0!1
is the decay function satisfying the property: Tit;j t0 = D. One possible definition for could be: t t0 = Ti;j
t t;t0 Ti;j + (1 t;t0 )D (8) where is the decay rate, and: t;t0 =
The definition of t;t0 above serves the purpose of establishing a minimum grace period, determined by the parameter !, during which the information does not decay, and that once reached the information starts decaying. The parameter tmax, which may be defined in terms of multiples of !, controls the pace of decay. The main idea behind this is that after the grace period, the decay happens very slowly; in other words, t;t0 decreases very slowly. Given a peer assessment e , the question now is how to compute the probability distribution of ’s evaluation. In other words, what is the probability that ’s evaluation of is x given that evaluated with e . As illustrated earlier, this is expressed as the conditional probability:
P(X=x j e )
To calculate this conditional probability, the intuition is that would tend to agree with ’s evaluation if his trust on (that is, the expected similarity between their assessments or the expected evaluation rate between their assessments) is high. Otherwise, ’s evaluation would probably be different. We perform then a sort of analogical reasoning: if in the past gave assessments that were a certain degree dissimilar from ’s opinions, or with a certain evaluation rate with respect to , then this will probably happen again now.
We then calculate the above conditional probability based on the following desired properties:
If T ; is a flat distribution (i.e. a distribution representing ignorance), then P(X j e ) should also be a flat distribution. That is, the closer ’s trust on is to ignorance, the less information is giving to with his/her assessment.
The degree of belief e = x should increase for those points x whose similarity (or evaluation rate, in the case of the ordered case) to e is high (i.e. for higher values of T ; ).
The degree of belief e = x should decrease for those points x whose similarity (or evaluation rate, in the case of the ordered case) to e is low trust (i.e. for lower values of T ; ).
Formally, these properties are achieved by defining the probabilities accordingly (where the denominator of the following two equations, Equations 9 and 10, is used for normalisation to ensure that the resulting distribution is a probability distribution): x02E x02E
p(X=x j e ) = X eT ; (sim(e ;x0)) I(T ; ) eT ; (sim(e ;x)) I(T ; )
p(X=x j e ) = X eT ; (r(e =x0)) I(T ; )
eT ; (r(e =x)) I(T ; ) where I(T ; ) is a measure of how informative the probability distribution T ; is. We calculate I(T ; ) as:
I(T ; ) = 1
H(T ; ) where H describes the entropy of a probability distribution. In other words, the lower the entropy of the distributions then the more informative it is, and vice versa.
We finally define the probability distribution of ’s expected evaluation given ’s opinion accordingly: P(X j e ), where X varies over the evaluation space E . 2.4
In the previous section we computed P(X j e ). That is, the probability distribution of ’s evaluation on given the evaluation of a peer on . But what does do when there is more than one peer assessing ?
Given the set of opinions O describing a set of peer evaluations over the object , we define the probability of ’s assessment being x as follows:
Y p(X=x j e ) p(X=x j O )) = X2OY p(X=x0 j e )
x02E 2O
In other words, the probability of ’s assessment on being x given the set of opinions over is an aggregation (a product in this case) of the probabilities of ’s assessment on being x given each evaluation e 2 O .
We then define the probability distribution of ’s expected evaluation given all opinions in O as P(X j O ), where X varies over the evaluation space E .
We note that instead of the product operator Q other connectives could be used, for instance the min operator might be used. However, we note that using the minimum operator does not take into account the number of assessments made. That is, having assessments of 20 peers could be equivalent to having the assessment of just one peer. In fact, the proposed aggregation of Equation 12 ensures that: (12) The larger the number of identical opinions, the less uncertain the final probability distribution is, and The more trusted the opinions, the less uncertain the final probability distribution is. (9) (10) (11)
Finally, to translate the final assessment from a probability distribution P(X j O ) into a single value, we calculate the mean (average) of the distribution and select the closest mark to that mean. 2.5
The previous three steps have provided a model to calculate automated assessments of objects that have not been assessed by , based on peers opinions. The level of uncertainty of the automated assessments generated by our model can be calculated as the uncertainty of the probability distribution of ’s expected evaluation based on those peers opinions P(X j O ). This level of uncertainty is measured by the distribution’s entropy:
H(P(X j O ))
The question that naturally arises then is what objects can be assessed next by to decrease such uncertainties? For example, how many more assignments should a tutor evaluate so that the uncertainty of the calculated assessments becomes acceptable. We suggest to evaluate objects with maximum uncertainty, or maximum entropic value. The ranking of objects with respect to their entropic value is then defined as follows:
Rank( ) = 1 H(P(X j O )) = 1 + X p(X=x j O ) ln p(x j O ) (13) x2X can then continue to evaluate objects one by one until the uncertainty of the automated assessments becomes less than some predefined acceptable uncertainty threshold. 3
In this paper we have presented the personalised automated assessments model (PAAS), a trust-based assessment service that helps compute group assessments from the perspective of a specific community member. This computation essentially aggregates peer assessments, giving more weight to those peers that are trusted by the specific community member whom the automated assessments are computed for. How much this specific member trusts a peer is then based on the similarity or evaluation rate between his (past) assessments and the peer’s (past) assessments over the same assignments.
The proposed work is an extension of the work carried out in [Gutierrez et al., submitted for publication]. In fact, the COMAS model is a much more simplified model of the nonordered case. It is much more simplified as it assumes that the probability of the similarity between two assessors is 1 for the aggregation of the similarities of past evaluations over the same objects. PAAS’ use of probability distribution makes it a richer and more informative model as much more information is preserved in the calculations. Furthermore, PAAS computes the uncertainty of the automated assessments, helping suggesting which objects should be evaluated next in order to decrease the overall uncertainty of PAAS’ calculations.
In COMAS, experimental results were conducted on a real classroom datasets as well as simulated data that considers different social network topologies (where we say students assess some assignments of socially connected students). Results show that the COMAS method 1) is sound, i.e. the error of the suggested assessments decreases for increasing numbers of tutor assessments; and 2) scales for large numbers of students.
Future work on PAAS should follow a similar approach for evaluation, where the same real classroom datasets can be used as the groundtruth of marks, and we can then compare PAAS’ automated assessments to that groundtruth.
Additionally, we could also test the ranking of marks (Section 2.5) by running experiments in a real classroom where we ask the tutor to evaluate assignments once in a random order and another time following the suggested ranking. This could help us check whether the error decreases faster in the latter case. Also, we expect to find that for a given acceptable uncertainty threshold, the tutor should evaluate less assignments in order to reach that threshold than evaluating randomly.
This work is supported by the CollectiveMind project