《电子商务 E-business》阅读文献：Modeling Trust for Recommender_Systems using Similarity Metrics.pdf_大学文库

Modeling Trust for Recommender Systems using Similarity Metrics Georgios Pitsilis and Lindsay F. Marshall1 Abstract. In this paper we present novel techniques for modeling trust relationships that can be used in recommender systems. Such environments exist with the voluntary collaboration of the community members who have as a common purpose the provision of accurate recommendations to each other. The performance of such systems can be enhanced if the potential trust between the members is properly exploited. This requires that trust relationships are appropriately established between them. Our model provides a link between the existing knowledge, expressed in similarity metrics, and beliefs which are required for establishing a trust community. Although we explore this challenge using an empirical approach, we attempt a comparison between the alternative candidate formulas with the aim of finding the optimal one. A statistical analysis of the evaluation results shows which one is the best. We also compare our new model with existing techniques that can be used for the same purpose. 1 Introduction Recommender systems have become popular nowadays as they are widely used in ecommerce. Examples of services which use recommender systems for helping users to choose products they might like are epinions [1], eBay [2] and Amazon [3]. The contribution of recommender systems comes in two forms, either as predicted ratings of services that a user wants to know about, or as lists of services that users might find of interest. The effectiveness of a Recommender system can be measured by the accuracy of the predictions that it makes. Collaborative filtering (CF) [4] is Georgios Pitsilis and Lindsay F. Marshall School of Computing Science, University of Newcastle Upon-Tyne, Newcastle Upon Tyne, NE1 7RU, U.K., e-mail: Georgios.Pitsilis@ncl.ac.uk Please use the following format when citing this chapter: Pitsilis, G. and Marshall, L. F., 2008, in IFIP International Federation for Information Processing, Volume 263; Trust Management II; Yücel Karabulut, John Mitchell, Peter Herrmann, Christian Damsgaard Jensen; (Boston: Springer), pp. 103–118

the most widely known technique used in Recommender systems and is based or the idea of making predictions using similarity metrics to correlate users However, Recommender Systems and particularly Collaborative Filtering are not perfect and as it is well known that they appear to have weaknesses such as a low uality of predictions( known as the false negatives and false positives problems 5D), caused by sparsity in the dataset. Also, the architectural characteristics of CF are known to be vulnerable to attacks from malicious and libelous users. CF systems employ statistical techniques to develop virtual relationships between users, and in this way, neighborhoods of users can be formed consisting of those who have a his- tory of agreeing and who are thus assumed to be similar. The virtual relationships are built upon a metric that is used for correlating the users based on their expe- riences and is called Similarity. In order to know how similar two users are with each other, a number of common experiences must exist Trust has been investigated by many researchers of recommender systems in the past [23] and proposed also as a potential solution to alleviate the previously men- tioned problems of recommender systems [6, 7]. Trust can also express integrity in relationships between entities and so can be used to express the quality of service providers. So, service consumers should be able to assess reliably the quality of ser- vices before they decide to depend on a particular instance. In order to know the trustworthiness of a service provider evidence needs to be provided to potential con- sumers from which they can derive their own trust for the provider Under appropriate circumstances(with regard to a common purpose), trust rela- tionships can also support transitivity [8] whereas similarity generally does not. In order to benefit from the special characteristics of trust such as the ability to propa gate along chains of trusted users, a formula for deriving it from similarity and vice versa is needed. In this way user entities that cannot be correlated due to lack of common experiences can benefit from each other and thus extend the and/or the quality of predictions they can make about their future choices tribution to this research problem is the provision of appropriate formulas be used for converting trust to similarity The rest of the paper is organized as follows. In the next section, there is a more detailed description of the problem. Section 3 includes related work in the field and section 4 we analyze our approach to the problem, showing the formulas we have introduced. Next in section 5 we present the evaluation we performed and some comparative resul ts which show the best candidate. Finally, in section 6 we discuss some future issues concerning the applicability of the proposed method 2 Motivation The main idea of collaborative filtering is to make predictions of scores based on the heuristic that two people who agreed (or disagreed) in the past will probably agree agree)again. A typical collaborative filtering system runs as a centralized ser- vice and the information it holds can be represented by a matrix of users and items Each value of the matrix represents the score that a particular user has given to some item. The number of empty cells is known as sparsity and as we mentioned in the previous section, it is the main reason that recommender systems behave poorly, be

the most widely known technique used in Recommender systems and is based on the idea of making predictions using similarity metrics to correlate users. However, Recommender Systems and particularly Collaborative Filtering are not perfect and as it is well known that they appear to have weaknesses such as a low quality of predictions ( known as the false negatives and false positives problems [5]), caused by sparsity in the dataset. Also, the architectural characteristics of CF are known to be vulnerable to attacks from malicious and libelous users. CF systems employ statistical techniques to develop virtual relationships between users, and in this way, neighborhoods of users can be formed consisting of those who have a history of agreeing and who are thus assumed to be similar. The virtual relationships are built upon a metric that is used for correlating the users based on their experiences and is called Similarity. In order to know how similar two users are with each other, a number of common experiences must exist. Trust has been investigated by many researchers of recommender systems in the past [23] and proposed also as a potential solution to alleviate the previously mentioned problems of recommender systems [6,7]. Trust can also express integrity in relationships between entities and so can be used to express the quality of service providers. So, service consumers should be able to assess reliably the quality of services before they decide to depend on a particular instance. In order to know the trustworthiness of a service provider evidence needs to be provided to potential consumers from which they can derive their own trust for the provider. Under appropriate circumstances (with regard to a common purpose), trust relationships can also support transitivity [8] whereas similarity generally does not. In order to benefit from the special characteristics of trust such as the ability to propagate along chains of trusted users, a formula for deriving it from similarity and vice versa is needed. In this way user entities that cannot be correlated due to lack of common experiences can benefit from each other and thus extend the quantity and/or the quality of predictions they can make about their future choices. Our contribution to this research problem is the provision of appropriate formulas that can be used for converting trust to similarity. The rest of the paper is organized as follows. In the next section, there is a more detailed description of the problem. Section 3 includes related work in the field and in section 4 we analyze our approach to the problem, showing the formulas we have introduced. Next in section 5 we present the evaluation we performed and some comparative results which show the best candidate. Finally, in section 6 we discuss some future issues concerning the applicability of the proposed method. 2 Motivation The main idea of collaborative filtering is to make predictions of scores based on the heuristic that two people who agreed (or disagreed) in the past will probably agree (disagree) again. A typical collaborative filtering system runs as a centralized service and the information it holds can be represented by a matrix of users and items. Each value of the matrix represents the score that a particular user has given to some item. The number of empty cells is known as sparsity and as we mentioned in the previous section, it is the main reason that recommender systems behave poorly, be- 104 G. Pitsilis et al

Modeling Trust for Recommender Systems using Similarity Metrics 105 cause not much evidence can be gathered to support a recommendation. This is usually because users themselves are unwilling to invest much time or effort in rat ng items. In existing CF systems users can only be correlated through their com- mon experiences, so in the presence of limited data they turn out to be unable to make accurate predictions. The idea to enhance the neighboring base of users, by using the potentially developed trust relationships between them, could make it possible to reach other members of the community through them. Assuming that the potential trust between the users could help in reducing the number of empty cells in the matrix by allowing missing values to be predicted from xisting ones, finding a way of computing that trust from the existing data(user ex- periences) might help to alleviate the problem. For such an idea to be applicable, it is necessary that, somehow, users must be able to place trust on their neighbors. In some centralized consumer opinion sites [11 it is a requirement that this trust measure should be provided by the users them selves. However, this requires that users should have developed some instinct in judging things accurately, and this cannot be assured. Poor judging abilities intro- duce the danger of establishing relationships with wrong counterparts. Our approach to this issue is to introduce a technique for mapping between similarity measures and trust, and which will be done automatically on behalf of the users In our model we use ordinary measures of similarity taken from CF to form the potential trust between the correlated entities which would be propagated in a simi lar way to the word-of-mouth scheme. In that scheme the trust that the first entity should place on the distant one is derived through a trust graph. Finally, by trans forming the value back into similarity measure terms it could be made appropriate for use in CF algorithms. However, to our knowledge, today there is no standard pproach for modeling trust from such type of existing evidence. In this work as well as in a previous one [9] we express trust in the form of opinions as they are modeled in Subjective Logic [10]. In this theory trust is considered as a subjective measure and introduces the important idea that there is always imperfect knowledge when judging things. The latter is expressed with a notion called uncertainty and is present when trust is based on user observations. Another interesting point of sub- jective logic is that it provides an algebra for combining direct and indirect trust along chains of users. Direct trust is considered the trust that is built upon first hand evidence or else derived from experience with the trustee. Indirect trust is built upon recommendations from others when first hand evidence is not present The use of trust in transitive chains requires the existence of a common [8] which needs recommender trust to be derived or given from a specific tra chain. This has either to be modeled from relevant evidence or. somehow must be enabled to derive it from past experiences Our work in this paper is concerned with the construction of trust re Ising first hand evidence, which in our case is the users'ratings. More specifically we try various similarity-to-trust transformation formulas with the purpose of find- ng the most suitable one. In the future we aim to evaluate the accuracy of a whole recommender system that employs the proposed transformation formula

cause not much evidence can be gathered to support a recommendation. This is usually because users themselves are unwilling to invest much time or effort in rating items. In existing CF systems users can only be correlated through their common experiences, so in the presence of limited data they turn out to be unable to make accurate predictions. The idea to enhance the neighboring base of users, by using the potentially developed trust relationships between them, could make it possible to reach other members of the community through them. Assuming that the potential trust between the users could help in reducing the number of empty cells in the matrix by allowing missing values to be predicted from existing ones, finding a way of computing that trust from the existing data (user experiences) might help to alleviate the problem. For such an idea to be applicable, it is necessary that, somehow, users must be able to place trust on their neighbors. In some centralized consumer opinion sites [1] it is a requirement that this trust measure should be provided by the users themselves. However, this requires that users should have developed some instinct in judging things accurately, and this cannot be assured. Poor judging abilities introduce the danger of establishing relationships with wrong counterparts. Our approach to this issue is to introduce a technique for mapping between similarity measures and trust, and which will be done automatically on behalf of the users. In our model we use ordinary measures of similarity taken from CF to form the potential trust between the correlated entities which would be propagated in a similar way to the word-of-mouth scheme. In that scheme the trust that the first entity should place on the distant one is derived through a trust graph. Finally, by transforming the value back into similarity measure terms it could be made appropriate for use in CF algorithms. However, to our knowledge, today there is no standard approach for modeling trust from such type of existing evidence. In this work as well as in a previous one [9] we express trust in the form of opinions as they are modeled in Subjective Logic [10]. In this theory trust is considered as a subjective measure and introduces the important idea that there is always imperfect knowledge when judging things. The latter is expressed with a notion called uncertainty and is present when trust is based on user observations. Another interesting point of subjective logic is that it provides an algebra for combining direct and indirect trust along chains of users. Direct trust is considered the trust that is built upon first hand evidence or else derived from experience with the trustee. Indirect trust is built upon recommendations from others when first hand evidence is not present. The use of trust in transitive chains requires the existence of a common purpose [8] which needs recommender trust to be derived or given from a specific transitive chain. This has either to be modeled from relevant evidence or, somehow, trustors must be enabled to derive it from past experiences. Our work in this paper is concerned with the construction of trust relationships using first hand evidence, which in our case is the users’ ratings. More specifically we try various similarity-to-trust transformation formulas with the purpose of finding the most suitable one. In the future we aim to evaluate the accuracy of a whole recommender system that employs the proposed transformation formula. Modeling Trust for Recommender Systems using Similarity Metrics 105

106 G. Pitsilis et al 3 Background research Trust has long been a concern for scientists and much work has been done to for malize it in computing environments [11, 12- As well as being context specific,it has important characteristics such as asymmetry, subjectivity, and under specific circumstances, transitivity. It is also related to tasks in the sense that entities are trusted to perform a particular task. A simplistic approach would be to determine the evels of trust and distrust that should be placed on some entity from its probabilistic behavior as seen from trustor's point of view. In this sense, trust can be thought of as the level of belief established between two entities in relation to a certain context In uncertain probabilities theory [13] the metric which expresses the belief is called opinion. Because there is always imperfect knowledge as opinions are based on ob servations, lack of knowledge should be considered when assessing them. Subjective Logic framework deals with the absence of both trust and distrust by introducing the uncertainty property in opinions. This framework uses a simple intuitive representa tion of uncertain probabilities by using a three dimensional metric that comprises belief(b), disbelief (d)and uncertainty(u). Between b, d and u the following equa- tion holds b+d+u=l which is known as the Belief Function Additivity Theorem Building up opinions requires the existence of evidence, but even though opinions in the form(b, d, u) are better manageable due to the quite flexible calculus that opi nion space provides, evidence is usually available only in other forms, that are es- entially more understandable to humans Having this in mind, we could use the ratings given by the users as evidence, also called behavioral data, for forming trust relationships between them in a CF system. The Beta Distribution Probability Function can offer an al ternative representation of uncertain probabilities [14], making it possible to approximate opinions from be- havioral data. However, data in that evidence space are considered as sets of obser vations and therefore must be provided strictly in binary form representing the poss- ible two outcomes of a process, x or x. So, a behavior is described by the number of x and x that derives from the set of observations. In [10] there is a mapping be tween Evidence Spaces and Opinion Spaces where the uncertainty property(u)is solely dependent on the quantity of observations. In contrast, other similarity based pproaches such as that in [15] are based on the idea of linking users indirectly us ing predictability measures, but, to our knowledge, these have not been tested in real environments As we mentioned above, the requirement for trust to become transitive in long chains is that a common purpose exists along the chain. According to this, only the last relationship should be concerned with trust for a certain purpose and all the oth- er trust relationships in the chain should be with respect to the ability to recommend for the given purpose. The former is called functional trust and the latter recom- mender trust. It is worth mentioning the existence of other approaches to making re- commander systems trust-enabled such as [16] where there is no distinction between functional and recommender trust. Also in some other solutions [17 that are used for predicting scores in recommender systems using webs of trust, the notion of trust is confused with similarity even though they are essentially different. Subjective logic provides a useful algebra for calculating trust in long chains of neighbors but it requires that opinions be expressed in(b, d, u) format which existing modeling tech

3 Background Research Trust has long been a concern for scientists and much work has been done to formalize it in computing environments [11,12]. As well as being context specific, it has important characteristics such as asymmetry, subjectivity, and under specific circumstances, transitivity. It is also related to tasks in the sense that entities are trusted to perform a particular task. A simplistic approach would be to determine the levels of trust and distrust that should be placed on some entity from its probabilistic behavior as seen from trustor’s point of view. In this sense, trust can be thought of as the level of belief established between two entities in relation to a certain context. In uncertain probabilities theory [13] the metric which expresses the belief is called opinion. Because there is always imperfect knowledge as opinions are based on observations, lack of knowledge should be considered when assessing them. Subjective Logic framework deals with the absence of both trust and distrust by introducing the uncertainty property in opinions. This framework uses a simple intuitive representation of uncertain probabilities by using a three dimensional metric that comprises belief (b), disbelief (d) and uncertainty (u). Between b,d and u the following equation holds b+d+u=1 which is known as the Belief Function Additivity Theorem. Building up opinions requires the existence of evidence, but even though opinions in the form (b,d,u) are better manageable due to the quite flexible calculus that opinion space provides, evidence is usually available only in other forms, that are essentially more understandable to humans. Having this in mind, we could use the ratings given by the users as evidence, also called behavioral data, for forming trust relationships between them in a CF system. The Beta Distribution Probability Function can offer an alternative representation of uncertain probabilities [14], making it possible to approximate opinions from behavioral data. However, data in that evidence space are considered as sets of observations and therefore must be provided strictly in binary form representing the possible two outcomes of a process, x or x . So, a behavior is described by the number of x and x that derives from the set of observations. In [10] there is a mapping between Evidence Spaces and Opinion Spaces where the uncertainty property (u) is solely dependent on the quantity of observations. In contrast, other similarity based approaches such as that in [15] are based on the idea of linking users indirectly using predictability measures, but, to our knowledge, these have not been tested in real environments. As we mentioned above, the requirement for trust to become transitive in long chains is that a common purpose exists along the chain. According to this, only the last relationship should be concerned with trust for a certain purpose and all the other trust relationships in the chain should be with respect to the ability to recommend for the given purpose. The former is called functional trust and the latter recommender trust. It is worth mentioning the existence of other approaches to making recommender systems trust-enabled such as [16] where there is no distinction between functional and recommender trust. Also in some other solutions [17] that are used for predicting scores in recommender systems using webs of trust, the notion of trust is confused with similarity even though they are essentially different. Subjective logic provides a useful algebra for calculating trust in long chains of neighbors but it requires that opinions be expressed in (b,d,u) format which existing modeling tech- 106 G. Pitsilis et al

Modeling Trust for Recommender Systems using Similarity Metrics 107 niques are not suitable to handle. This is because existing solutions for encoding trust either deal with data in an unsuitable form(see[ 14] beta pdf) or do not provide links to similarity. In our opinion it is not appropriate for users to be asked to pro- vide trust measures for others, mainly because this requires skills and adequate ex- perience that not all users have 4 Our Approaches In general, trust models are used to enable the parties involved in a trust relationship to know how much reliance to place on each other. Our model aims to provide a method for estimating how much trust two entities can place in each other, given the similarities between them. The problem that emerges when Trust is to be used in a recommender system is the fact that the entities invol ved usually provide their views in the form of ratings about items and not as their trust estimates about other entities. That means to bene fit from such model it is required that all user ratings be transformed into trust val ues. We are contributing to sol ving this issue by proposing and comparing various formulas for encoding direct trust. The first formula we propose in paragraph 4 has already been used in an experimental P2P recommender system which has been studied in [18]. The other new modeling approaches we propose are extensions of the same idea. The significant difference, though, between the existing and the new approaches is found in the way we model the uncertainty property. In all the new approaches we keep the main method of modeling uncertainty the same but we change the way that the remaining properties(belief and disbelief) are shaped 4.1 The existing appro Unlike the other modeling concepts we discussed above, such as beta pdf modeling, in our first approach we use both quantitative and qualitative criteria on the evi dence to derive uncertainty. In order to achieve this, we consider the ratings that us- rs have given to items as the behavioral data required for the composition of opi- nions. In order to capture this requirement in our model we assume that the level of trust that develops between every pair of entities is based on how similar they perce ive each others choices to be. We used the pearson coefficient, as this is the best known and most suitable coefficient for this type of application. It can take values between-I and I where two entities are considered as having higher similarity when their Pearson values are close to I and as completely dissimilar when the Pearson Coefficient is-1. A value of0 would mean that there is no relationship between the two entities at all. Bearing in mind the idea that those entities whose ratings can be accurately predicted should be considered as trustworthy sources of information, the uncertainty in such relationships should be lower Thus, in this approach we have re-defined the perception of Uncertainty as the inability of some entity to make accurate predictions about the choices of the other

niques are not suitable to handle. This is because existing solutions for encoding trust either deal with data in an unsuitable form (see [14] beta pdf) or do not provide links to similarity. In our opinion it is not appropriate for users to be asked to provide trust measures for others, mainly because this requires skills and adequate experience that not all users have. 4 Our Approaches In general, trust models are used to enable the parties involved in a trust relationship to know how much reliance to place on each other. Our model aims to provide a method for estimating how much trust two entities can place in each other, given the similarities between them. The problem that emerges when Trust is to be used in a recommender system is the fact that the entities involved usually provide their views in the form of ratings about items and not as their trust estimates about other entities. That means, to benefit from such model it is required that all user ratings be transformed into trust values. We are contributing to solving this issue by proposing and comparing various formulas for encoding direct trust. The first formula we propose in paragraph 4.1 has already been used in an experimental P2P recommender system which has been studied in [18]. The other new modeling approaches we propose are extensions of the same idea. The significant difference, though, between the existing and the new approaches is found in the way we model the uncertainty property. In all the new approaches we keep the main method of modeling uncertainty the same but we change the way that the remaining properties (belief and disbelief) are shaped. 4.1 The existing approach Unlike the other modeling concepts we discussed above, such as beta pdf modeling, in our first approach we use both quantitative and qualitative criteria on the evidence to derive uncertainty. In order to achieve this, we consider the ratings that users have given to items as the behavioral data required for the composition of opinions. In order to capture this requirement in our model we assume that the level of trust that develops between every pair of entities is based on how similar they perceive each other’s choices to be. We used the Pearson coefficient, as this is the best known and most suitable coefficient for this type of application. It can take values between -1 and 1 where two entities are considered as having higher similarity when their Pearson values are close to 1 and as completely dissimilar when the Pearson Coefficient is -1. A value of 0 would mean that there is no relationship between the two entities at all. Bearing in mind the idea that those entities whose ratings can be accurately predicted should be considered as trustworthy sources of information, the uncertainty in such relationships should be lower. Thus, in this approach we have re-defined the perception of Uncertainty as the inability of some entity to make accurate predictions about the choices of the other Modeling Trust for Recommender Systems using Similarity Metrics 107

counterpart in the relationship. A low ability value should result from the existence of conflicting data and this should make the observer unable to fill in the uncertainty gap. When there are not enough observations to distinguish rating trends data might ppear to be highly conflicting. We propose the following formula to model uncertainty from prediction error where k is the number of common experiences(ratings)of the two entities that form a relationship, Pr is the predicted rating of item x calculated using some prediction calculation formula and Ix is the real rate that the entity has given to item x. m represents the maximum value that a rating can take and it is used here as a measure of rating. As can be seen, uncertainty is inversely proportional to the number of ex periences. This agrees with the definition of uncertainty we presented in the pre- vious section The logical reasoning for deriving formula(4.1) for Uncertainty is the following. Incertainty is proportional to the prediction error for every user's single experience, therefore the numerator represents the absolute error between the predicted value (using a rating prediction formula) and the real (rated) value. The denominator m has been used for normalizing the error to the range 0-1. The summing symbol has been used to include all the experiences(k in number) of a particular user. Finally, the division by the total number of experiences(k)is done to get the average norma lized error. In the sum we take every pair of common ratings and try to predict what the rate p would be. Therefore it is assumed that on every prediction calculation all but the real rating of the value that is to be predicted exist Unlike Beta mapping [14 where u tends to 0 as the number of experiences grows, in our model the trend remains quite uncertain because u is also dependent on the average prediction error. In the extreme case where there is high controversy in the data, u will reach a value close to 1, leaving a small space for belief and dis- belief. Another interesting characteristic of our model is the asymmetry in the trust relationships produced, which adheres to the natural form of relationships since the levels of trust that two entities place on each other may not be necessarily the same As regards the other two properties b(belief) and d(disbelief), we set them up in such a way that they are dependent on the value of the Correlation Coefficient CC We made the following two assumptions The belief (disbelief) property reaches its maximum value(1-u) when CC=l(or The belief (disbelief) property reaches its minimum value(1-u) when CC=-1(or CC=l respectively) which are expressed by the two formulae b=(1-)a+CC) (4.3)

counterpart in the relationship. A low ability value should result from the existence of conflicting data and this should make the observer unable to fill in the uncertainty gap. When there are not enough observations to distinguish rating trends data might appear to be highly conflicting. We propose the following formula to model uncertainty from prediction error: ¦ k x xx m rp k u 1 1 (4.1) where k is the number of common experiences (ratings) of the two entities that form a relationship, px is the predicted rating of item x calculated using some prediction calculation formula and rx is the real rate that the entity has given to item x. m represents the maximum value that a rating can take and it is used here as a measure of rating. As can be seen, uncertainty is inversely proportional to the number of experiences. This agrees with the definition of uncertainty we presented in the previous section. The logical reasoning for deriving formula (4.1) for Uncertainty is the following: Uncertainty is proportional to the prediction error for every user’s single experience; therefore the numerator represents the absolute error between the predicted value (using a rating prediction formula) and the real (rated) value. The denominator m has been used for normalizing the error to the range 0-1. The summing symbol has been used to include all the experiences (k in number) of a particular user. Finally, the division by the total number of experiences (k) is done to get the average normalized error. In the sum we take every pair of common ratings and try to predict what the rate p would be. Therefore it is assumed that on every prediction calculation all but the real rating of the value that is to be predicted exist. Unlike Beta mapping [14] where u tends to 0 as the number of experiences grows, in our model the trend remains quite uncertain because u is also dependent on the average prediction error. In the extreme case where there is high controversy in the data, u will reach a value close to 1, leaving a small space for belief and disbelief. Another interesting characteristic of our model is the asymmetry in the trust relationships produced, which adheres to the natural form of relationships since the levels of trust that two entities place on each other may not be necessarily the same. As regards the other two properties b (belief) and d (disbelief), we set them up in such a way that they are dependent on the value of the Correlation Coefficient CC. We made the following two assumptions: x The belief (disbelief) property reaches its maximum value (1-u) when CC=1 (or CC=-1 respectively) x The belief (disbelief) property reaches its minimum value (1-u) when CC= -1 (or CC=1 respectively) which are expressed by the two formulae: )1( 2 )1( CC u b (4.2) )1( 2 )1( CC u d (4.3) 108 G. Pitsilis et al

Modeling Trust for Recommender Systems using Similarity Metrics As can be seen, the ratio of belief and disbelief is shaped by the CC value. In this ay, a positive Correlation Coefficient would be expected to strengthen the belief property at the expense of disbelief. In the same way, disbelief appears to be strong er than belief between entities that are negatively correlated (CC<o) These two formulae can be used in the opposite way too: for estimating how similar the two entities should consider each other, given their trust properties. The asymmetry in the trust relationships is mainly responsible for having unequal simi arities between the original one and the one derived from the backward application of the formula. The different points of view are responsible for this difference as well as the formula used to work out the predictions px in(4. 1). The formulas pro- posed in [15] as well as Resnick's[ 19] empirical one built for the Grouplens CF system can be used for the calculation of p As we can see in this proposed model, belief/disbelief increases/decreases linear- ly with the Correlation Coefficient and in terms of computational complexity, the uncertainty formula is O(n). This seems to be a significant drawback to this method be repeated whenever a new score is entered by any of the two parte i to run for n because the calculation of uncertainty requires the prediction formula times which in turn requires the calculation of similarity value k times. This has to 4.2 The new proposed model Since the above formula is found to be computationally intensive we came up with other less complex alternative formulas for modeling the same notions The first thing that we changed was the calculation of uncertainty. In contrast to the old approach, in the new design it is calculated exclusively from the quantity of experiences similarly as is done in the beta pdf mapping in Josang's approach[141 However, in our new model we propose that every pair of common scores is counted as a different experience and for the uncertainty calculation we use the for mula:u=(n+1), where n is the number of common scores non-linear and circular. Amongst the pros of the alternative formulas is the signifi- cantly lower complexity O(n) which means lower calculation time since it is now dependent only on the number of common ratings For a linear approach to shaping belief and disbelief the formulae used should be the same as before in the original model expressed in(4.2)and(4.3). For non-linear approaches we tried equations which are shown as figures of various skewnesses The belief property alternatives are expressed in table 1. To save space, the formulas from which disbelief (d) is derived are not presented but for all cases d is considered as the remainder since d=1-b-u and it is symmetric to belief. In addition to the two assumptions we made for the linear mapping shown in the previous paragraph, we included a third which is A zero correlation coefficient(CC=0)should mean that belief equals disbelief

As can be seen, the ratio of belief and disbelief is shaped by the CC value. In this way, a positive Correlation Coefficient would be expected to strengthen the belief property at the expense of disbelief. In the same way, disbelief appears to be stronger than belief between entities that are negatively correlated (CC<0). similar the two entities should consider each other, given their trust properties. The asymmetry in the trust relationships is mainly responsible for having unequal similarities between the original one and the one derived from the backward application of the formula. The different points of view are responsible for this difference as well as the formula used to work out the predictions px in (4.1). The formulas proposed in [15] as well as Resnick’s [19] empirical one built for the Grouplens CF system can be used for the calculation of x p . As we can see in this proposed model, belief/disbelief increases/decreases linearly with the Correlation Coefficient and in terms of computational complexity, the uncertainty formula is O(n2 ). This seems to be a significant drawback to this method because the calculation of uncertainty requires the prediction formula to run for n times which in turn requires the calculation of similarity value k times. This has to be repeated whenever a new score is entered by any of the two parties. 4.2 The new proposed model Since the above formula is found to be computationally intensive we came up with other less complex alternative formulas for modeling the same notions. The first thing that we changed was the calculation of uncertainty. In contrast to the old approach, in the new design it is calculated exclusively from the quantity of experiences similarly as is done in the beta pdf mapping in Josang’s approach [14]. However, in our new model we propose that every pair of common scores is counted as a different experience and for the uncertainty calculation we use the formula: 1 )1( nu , where n is the number of common scores. As to belief and disbelief we tried various associations with CC such as linear, non-linear and circular. Amongst the pros of the alternative formulas is the significantly lower complexity O(n) which means lower calculation time since it is now dependent only on the number of common ratings. For a linear approach to shaping belief and disbelief the formulae used should be the same as before in the original model expressed in (4.2) and (4.3). For non-linear approaches we tried equations which are shown as figures of various skewnesses. The belief property alternatives are expressed in table 1. To save space, the formulas from which disbelief (d) is derived are not presented but for all cases d is considered as the remainder since d = 1 – b – u and it is symmetric to belief. In addition to the two assumptions we made for the linear mapping shown in the previous paragraph, we included a third which is: x A zero correlation coefficient (CC=0) should mean that belief equals disbelief. Modeling Trust for Recommender Systems using Similarity Metrics 109 These two formulae can be used in the opposite way too: for estimating how

5 Evaluation When carrying out this experiment we faced the challenge of how to evaluate every alternative formula and what measures to use for comparing the accuracy of our modeling approach. Therefore, we developed and applied the following plan. 5.1 The plan Since the goal was to test the accuracy of each candidate formula we considered as the best scenario comparing a known and accepted value of similarity against one that is derived by applying our trust derivation mechanism. More specifically, for each pair of users, lets call them A and B, we first calculated how similar they are, applying Pearson’s CC formula over the common experiences of A and B, and then we calculated the indirect trust between them. Next, this trust value was converted to a similarity metric using our formula and, finally, the derived value was compared against the original similarity we calculated first. The latter similarity is derived from the resulting indirect trust between A and B when subjective logic rules are applied to the graph built by the trust relationships that exist between A and B. (see figure 2.) In order to accomplish this, the primary trust between every pair of users has to be built pro-actively when making up the trust graph. Figure 2 is a pictorial representation of the entities involved in the evaluation scheme. We call SA,B the similarity that is derived from the common experiences between A and B, and S’A,B the similarity that is derived from the indirect trust of A for B. In the evaluation we compare these two values and we calculate the mean error. Fig. 2. .The evaluation diagram. TA,C and TA,D are two of the direct trust values that are used for calculating the indirect (or secondary) trust of A for B. Due to the fact that Pearson’s coefficient has unstable behavior when there is a low number of common experiences between two parties, we considered as similar neighbors those who have at least 10 common experiences and we choose to perform the evaluation test on these pairs of entities as Pearson’s similarity is calculable. TA,B A B S’A,B TA,C TC,B C SA,B D E TA,D Modeling Trust for Recommender Systems using Similarity Metrics 111

To measure the accuracy we calculated the Mean Absolute Error between the directly calculated similarity S and the one derived from the transitive trust S’. We use the following formula in which Cmax and Cmin are the maximum/minimum values of the Correlation Coefficient (1 and -1 respectively): max min ' CC SS MAE (5.1) The evaluation algorithm can be described in pseudo-code as in fig. 3. Let us call dti,,j the direct trust between entities i and j and iti,,j the indirect one. Assuming that j is within 2 hops of i in the constructed trust graph, the indirect trust of i for j can be calculated using subjective logic in two steps: First, the derived trust of every alternative path that begins from i and ends to j is calculated separately as a transitive relationship using the suggestion operator . Then all the values of the alternative paths along with dTi,,j are combined together using the consensus operator which gives the value of iTi,,j. In general the consensus is expressed in the following formula where A and B are two different agents which hold about the statement p respectively the opinions A Z p and B Z p . Fig. 3. The evaluation algorithm The consensus opinion held by an imaginary agent A,B is: },,{ , ,,, BA p BA p BA p B p A p BA p ZZZ udb (5.2) More about this can be found in [20]. In our particular case the statement p is the trustworthiness of the target j. A, B represent the alternative paths from i to j. The algorithm for calculating the indirect trust between the origin i and the target j is shown in figure 4. Let K be the set of all users Let R be the set of all ratings over items Let RuR be the set of the ratings of some user u Let KiK : Ru t10 * Cardinality of set of ratings of user i * For i in Ki Let Ei R * The set of ratings of user i * Let MKi : pM , EpR and EE pi t 10 For j in M do * p has 10 common ratings with i m CCS ji ),( * Pearson’s similarity * m iTrustT ji ),( * Derived Indirect trust * )( ' m TfS * Derived Similarity from our formula f * max min ' CC SS MAE m * Absolute Mean Error value * End For j End For i Average(MAE) 112 G. Pitsilis et al