Modeling Trust for Recommender Systems using Similarity metrics Georgios Pitsilis and Lindsay F. marshall Abstract. In this paper we present novel techniques for modeling trust relationships that can be used in recommender systems. Such environments exist with the volun- tary collaboration of the community members who have as a common purpose the provision of accurate recommendations to each other. The performance of such sys- tems can be enhanced if the potential trust between the members is properly ex- ploited. This requires that trust relationships are appropriately established betweer them. Our model provides a link between the existing knowledge, expressed in simi larity metrics, and beliefs which are required for establishing a trust community. Al- though we explore this challenge using an empirical approach, we attempt a com parison 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 1 Introduction Recommender systems have become popular nowadays as they are widely used in e- commerce. Examples of services which use recommender systems for helping user 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 rat of services that a user wants to know about, lists of services that users might find of interest. The effectiveness of a Recommender system can be measure by the accuracy of the predictions that it makes. Collaborative filtering(CF)[4] is os Pitsilis and Lindsay F. M: of Computing Science, Univ Newcastle Upon-Tyne, Newcastle Upon Tyne, NEI K, e-mail: Georgios. Pitsil Please arse the following farma when citing this chapter
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