RECOMMENDER SYSTEMS RESEARCH 117 higher for personalized predictions than for all-user average ratings(Konstan et al., 1997) These results reinforce the hypothesis that not all users are interested in the same articles even within a certain newsgroup(e. g, consider a vegetarian vs a meat-eater in rec food Konstan et al. (1997)state that 'predictive utility is the difference between potential ben- efit and risk. The potential benefit of making predictions is the value of hits and correct rejections. The risk involved in making predictions is the cost of misses and false positives Konstan et al. identify many of the approaches to increasing rating coverage in explicit user modeling discussed above, such as filter-bots- programs that automatically read and rate all articles(Sarwar et al., 1998). They also identify implicit declarations of quality such as the time spent reading an article. Konstan et al. recognize that some users are more effusive withtheirratingsthanothersThedevelopersofGrouplensbeganNetPerceptions(http:// www.netperceptions.com),acompanyemployingcollaborativefilteringtoprovideperson alization solutions tb. Balabanovic and Shoham(1997)take an agent-oriented approach to web document recommendation in Fab, which grew out of a Stanford University digital library project. Peo- ple are modeled in Fab through explicit(and some implicit) techniques resulting in ratings and profiles. The construction of accurate user profiles drive various agents in dynami- cally adapting the system. Fab is therefore a representative illustration of the importance and power of user modeling. The hybrid approach to recommendation in Fab retains the advantages of both a content-based and collaborative approach while addressing the disad vantages of each. Moreover the synergy yields new benefits. Fab treats each single focus (pure) approach to recommendation as a special case of its hybrid of the two. 'If the content analysis component returns just a unique identifier rather than extracting any features, then it reduces to pure collaborative recommendation; if there is only a single user, it reduces to pure content-based recommendation(Balabanovic and Shoham, 1997) Fab consists of two processes: collection and selection. During the collection phase, agents gather web sources on topics discovered from clustering user profiles In the selection process, an agent matches a user profile against what the collection agent has gathered Thus, one user may be matched against many topics and multiple users may be interested in the same topic. Users proceed to rate results. A user's ratings modifies his profile and concomitantly helps the collection agent harvest more relevant information for an updated profile. Fab uses the overlaps between users' interests in more than just collaborative selection. The design of the adapting population of collection agents takes advantage of these overlaps to dynamically converge on topics of interest . and providing the possibility of significant resource savings when increasing the numbers of users and documents'(Balabanovic and Shoham, 1997) Fab connects two users if a collection agent has clustered their profiles in order to collect more web sources of the central theme of the cluster
RECOMMENDER SYSTEMS RESEARCH 117 higher for personalized predictions than for all-user average ratings’ (Konstan et al., 1997). These results reinforce the hypothesis that not all users are interested in the same articles even within a certain newsgroup (e.g., consider a vegetarian vs. a meat-eater in rec.food. recipes). Konstan et al. (1997) state that ‘predictive utility is the difference between potential benefit and risk’. The potential benefit of making predictions is the value of hits and correct rejections. The risk involved in making predictions is the cost of misses and false positives. Konstan et al. identify many of the approaches to increasing rating coverage in explicit user modeling discussed above, such as filter-bots – programs that automatically read and rate all articles (Sarwar et al., 1998). They also identify implicit declarations of quality such as the time spent reading an article. Konstan et al. recognize that some users are more effusive with their ratings than others. The developers of GroupLens began NetPerceptions (http:// www.netperceptions.com), a company employing collaborative filtering to provide personalization solutions. Fab. Balabanovi´c and Shoham (1997) take an agent-oriented approach to web document recommendation in Fab, which grew out of a Stanford University digital library project. People are modeled in Fab through explicit (and some implicit) techniques resulting in ratings and profiles. The construction of accurate user profiles drive various agents in dynamically adapting the system. Fab is therefore a representative illustration of the importance and power of user modeling. The hybrid approach to recommendation in Fab retains the advantages of both a content-based and collaborative approach while addressing the disadvantages of each. Moreover the synergy yields new benefits. Fab treats each single focus (pure) approach to recommendation as a special case of its hybrid of the two. ‘If the content analysis component returns just a unique identifier rather than extracting any features, then it reduces to pure collaborative recommendation; if there is only a single user, it reduces to pure content-based recommendation’ (Balabanovi´c and Shoham, 1997). Fab consists of two processes: collection and selection. During the collection phase, agents gather web sources on topics discovered from clustering user profiles. In the selection process, an agent matches a user profile against what the collection agent has gathered. Thus, one user may be matched against many topics and multiple users may be interested in the same topic. Users proceed to rate results. A user’s ratings modifies his profile and concomitantly helps the collection agent harvest more relevant information for an updated profile. Fab uses ‘the overlaps between users’ interests in more than just collaborative selection. The design of the adapting population of collection agents takes advantage of these overlaps to dynamically converge on topics of interest . . . and providing the possibility of significant resource savings when increasing the numbers of users and documents’ (Balabanovi´c and Shoham, 1997). Fab connects two users if a collection agent has clustered their profiles in order to collect more web sources of the central theme of the cluster
PERUGINI, GONCALVES AND FOX Intelligent recommendation algorithm. A graph-theoretic collaborative filtering algorithm developed as part of the suite of recommendation engines in the Intelligent Recommendation Algorithm(IRA)program at IBM Research is presented in Aggarwal et al. (1999). The algorithm is motivated by sparsity; Aggarwal et al. contend that most collaborative filtering algorithms, such as those for Firefly, LikeMinds, and GroupLens, rely on too many ratings to be successful because they connect users directly(e. g, users A and B are connected if their ratings for at least n items are correlated). These algorithms compute closeness by takin a weighted average of only immediate neighbors. Rather than viewing sparsity as a vice, Aggarwal et al. exploit it in their algorithm. The greatest contribution of their algorithm is its use of functional indirection, i.e., it allows recommendations to propagate, via more than one intermediary, from a user to another who has not rated common items. The idea is to form and maintain a directed graph, where vertices represent users and edges represent predictability Since the graph is directed, recommendations are anti-symmetric. When one user predicts another, ratings propagate in this model. The ultimate idea is that predicted rating of item j for user i can be computed as weighted averages computed via a few reasonably ort directed paths joining multiple users'(Aggarwal et al., 1999). This effectively makes predictability more general then closeness and addresses the effusivity of ratings Aggarwal et al. also partition the presentation of resulting recommendations into hot and cold sets. The hot set, which is two orders of magnitude smaller than the cold, is intended to increase commonality to provide better recommendations while the cold set is intended to foster more exploration and increase the rating coverage of objects. While most of the collaborative filtering systems with explicit user modeling deliver predictable recommen- dations, this approach encourages creative links which violate pre-existing hierarchical classifications to introduce the possibility of serendipitous recommendations. Aggarw et al. evaluated their algorithm as well as that for GroupLens, Firefly, and LikeMinds, for accuracy against synthetic data 4. Discovering extant social networks Recognition of implicit declarations of user interest is a precursor to discovering exist ng communities of people. Implicit modeling techniques are a natural extension of those addressed in the previous section. We begin by discussing projects which mine declara tions of interest in news (Terveen et al., 1997)and bookmark(Rcuker and Polano, 1997) datasets to cast recommendations and discover connections. Although these systems foster communities(as do all recommender systems), they do not make social network identi- fication salient. While active effort is required when extracting declarations of interest to identify connections, natural connectivity among people is self-evident in data. We therefore next discuss mining connections implicit in communication(Schwartz and Wood, 1993) and news(Kautz et al., 1997) logs to induce existing social networks to exploit for recom- mendation. We then discuss mining and modeling social structure in movie ratings datasets (Mirza et al, 2003)and on the web(Kleinberg, 1999)via link analysis to help identify cyber-communities. We conclude by discussing small-worlds(Watts and Strogatz, 1998), a new class of social networks which present compelling opportunities for serendipitous recommendation. Table 3 outlines the landscape of research showcased in this section
118 PERUGINI, GONC¸ ALVES AND FOX Intelligent recommendation algorithm. A graph-theoretic collaborative filtering algorithm developed as part of the suite of recommendation engines in the Intelligent Recommendation Algorithm (IRA) program at IBM Research is presented in Aggarwal et al. (1999). The algorithm is motivated by sparsity; Aggarwal et al. contend that most collaborative filtering algorithms, such as those for Firefly, LikeMinds, and GroupLens, rely on too many ratings to be successful because they connect users directly (e.g., users A and B are connected if their ratings for at least n items are correlated). These algorithms compute closeness by taking a weighted average of only immediate neighbors. Rather than viewing sparsity as a vice, Aggarwal et al. exploit it in their algorithm. The greatest contribution of their algorithm is its use of functional indirection, i.e., it allows recommendations to propagate, via more than one intermediary, from a user to another who has not rated common items. The idea is to form and maintain a directed graph, where vertices represent users and edges represent predictability. Since the graph is directed, recommendations are anti-symmetric. When one user predicts another, ratings propagate in this model. ‘The ultimate idea is that predicted rating of item j for user i can be computed as weighted averages computed via a few reasonably short directed paths joining multiple users’ (Aggarwal et al., 1999). This effectively makes predictability more general then closeness and addresses the effusivity of ratings. Aggarwal et al. also partition the presentation of resulting recommendations into hot and cold sets. The hot set, which is two orders of magnitude smaller than the cold, is intended to increase commonality to provide better recommendations while the cold set is intended to foster more exploration and increase the rating coverage of objects. While most of the collaborative filtering systems with explicit user modeling deliver predictable recommendations, this approach encourages creative links which violate pre-existing hierarchical classifications to introduce the possibility of serendipitous recommendations. Aggarwal et al. evaluated their algorithm as well as that for GroupLens, Firefly, and LikeMinds, for accuracy against synthetic data. 4. Discovering extant social networks Recognition of implicit declarations of user interest is a precursor to discovering existing communities of people. Implicit modeling techniques are a natural extension of those addressed in the previous section. We begin by discussing projects which mine declarations of interest in news (Terveen et al., 1997) and bookmark (Rcuker and Polano, 1997) datasets to cast recommendations and discover connections. Although these systems foster communities (as do all recommender systems), they do not make social network identi- fication salient. While active effort is required when extracting declarations of interest to identify connections, natural connectivity among people is self-evident in data. We therefore next discuss mining connections implicit in communication (Schwartz and Wood, 1993) and news (Kautz et al., 1997) logs to induce existing social networks to exploit for recommendation. We then discuss mining and modeling social structure in movie ratings datasets (Mirza et al., 2003) and on the web (Kleinberg, 1999) via link analysis to help identify cyber-communities. We conclude by discussing small-worlds (Watts and Strogatz, 1998), a new class of social networks which present compelling opportunities for serendipitous recommendation. Table 3 outlines the landscape of research showcased in this section
RECOMMENDER SYSTEMS RESEARCH 119 Table 3. Recommender systems research focused on discovering existing social networks Implicit declaration of interest System Traditional Approaches to Implicit URLs in Usenet news PHOAKS User Modeling bookmarks Link Analysis and Cyber-Communities Discovering shared Interests web documents Mining and Exploiting Structure Movie ratings datasets Jumping Connections hits-buffs half bow-tie web link topology TS HIT authorities and hubs CLEVER Small- World Networks Actor collaborations author collaborations infectious disease The left column contains modeling concepts, while the center column contains examples of implicit declarations of interest or connections mined from the systems in the right column. Notice that each ystem relies solely on structural, rather than semantic, information. Note also that the emtpy cell in the lower right hand corner of this matrix is a reflection that few systems take advantage of small-world 4.1. Traditional approaches to implicit user modeling Implicit approaches toward modeling users were developed in response to the pervasive re- uctance to evaluate recommended artifacts and, although less emphasized, the possibility of building richer representations than with explicit approaches. The idea is to glean user preferences, often secretively, by observation, to serve as surrogates for explicit ratings A cold-start is less evident in this approach as implicit ratings bootstrap the model and system. Most of the techniques for implicitly gathering and exploiting user information are based on methods and algorithms from machine learning(Papatheodorou, 2001; Pazzani and Billsus, 1997; Webb et aL., 2001)and data mining, which attempt to discover interestin patterns or trends from large and diverse data sources. These techniques are largely based on heuristics. Data mining algorithms also have been subsequently used to make recommen dations. Their expensive time and space complexity is acceptable for user modeling which can be conducted offline Using data mining techniques for recommendation is a challenge because recommendations must often be delivered in real time(Linden et al., 2003 ). In addition, although not the focus here, inexpensive and less complex techniques for comput ing recommendations(e.g, correlating user ratings)are relatively effective. Sophisticated approaches to recommendation also suffer from yielding recommendations which are dif- ficult to explain or believe; recommendation explainability and believability are desired properties(Herlocker et al., 2000)(see Section 5) A variety of data sources exist, teeming with and useful for gleaning information about a user's interests and background. Persistent keywords can be extracted from previous user queries Clickstream data, such as(web) access logs, are invaluable for monitoring, captur- ing, and chartering a user's interaction with a system, also called'footprints'(Wexelblat an
RECOMMENDER SYSTEMS RESEARCH 119 Table 3. Recommender systems research focused on discovering existing social networks. Concept Implicit declaration of interest System Traditional Approaches to Implicit URLs in Usenet news PHOAKS User Modeling bookmarks Siteseer Link Analysis and Cyber-Communities e-mail logs Discovering Shared Interests web documents Referral Web Mining and Exploiting Structure Movie ratings datasets Jumping Connections hits-buffs, half bow-tie web link topology HITS authorities and hubs CLEVER bow-tie Small-World Networks Actor collaborations author collaborations infectious disease the web The left column contains modeling concepts, while the center column contains examples of implicit declarations of interest or connections mined from the systems in the right column. Notice that each system relies solely on structural, rather than semantic, information. Note also that the emtpy cell in the lower right hand corner of this matrix is a reflection that few systems take advantage of small-world properties. 4.1. Traditional approaches to implicit user modeling Implicit approaches toward modeling users were developed in response to the pervasive reluctance to evaluate recommended artifacts and, although less emphasized, the possibility of building richer representations than with explicit approaches. The idea is to glean user preferences, often secretively, by observation, to serve as surrogates for explicit ratings. A cold-start is less evident in this approach as implicit ratings bootstrap the model and system. Most of the techniques for implicitly gathering and exploiting user information are based on methods and algorithms from machine learning (Papatheodorou, 2001; Pazzani and Billsus, 1997; Webb et al., 2001) and data mining, which attempt to discover interesting patterns or trends from large and diverse data sources. These techniques are largely based on heuristics. Data mining algorithms also have been subsequently used to make recommendations. Their expensive time and space complexity is acceptable for user modeling which can be conducted offline. Using data mining techniques for recommendation is a challenge because recommendations must often be delivered in real time (Linden et al., 2003). In addition, although not the focus here, inexpensive and less complex techniques for computing recommendations (e.g., correlating user ratings) are relatively effective. Sophisticated approaches to recommendation also suffer from yielding recommendations which are dif- ficult to explain or believe; recommendation explainability and believability are desired properties (Herlocker et al., 2000) (see Section 5). A variety of data sources exist, teeming with and useful for gleaning information about a user’s interests and background. Persistent keywords can be extracted from previous user queries. Clickstream data, such as (web) access logs, are invaluable for monitoring, capturing, and chartering a user’s interaction with a system, also called ‘footprints’ (Wexelblat and