3.9 Learning curves for l-pref users comparing a single iter ation of gradient descent to relevance feedback 70 5.1 The Fab interface 5.2 Hypot hetical system design: single user, many collection agents 5.3 Hypot hetical system design: many users, single collect ion agent 5.4 Model underlying system design: many-to-many mapping between users and topics 5.5 Selection and collection agents 5.6 Select ion agents and collection agents lin ked via central router 5.7 Select ion agents and collection agents showing explicit collabor ation links ts of implemented Fab archit 5.9 Dist ance between actual and predicted ran kings, aver aged at each eval u ation doint 110 5.10 For each source, dist ance bet ween user rankings and its ideal ranking averaged over all users at each evaluat ion point 111 6.1 The three positions of the exploration/exploit ation select or, as seen in 119 6.2 Exploit ation vs. explor ation do cument selection strategies for 1-pref users. Graph shows ndpm values averaged over all 10 possible users, 1 measured at test iterations(every fift h iteration 6.3 Composition of documents in recommen ded sets for 1-pref 100% exploit at ion and 100% explor ation strategies. Recor ded for every train ing step, and averaged over all 10 possible user
3.9 Learning curves for 1-pref users comparing a single iteration of gradient descent to relevance feedback. ...................... 70 5.1 The Fab interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.2 Hypothetical system design: single user, many collection agents ... 83 5.3 Hypothetical system design: many users, single collection agent ... 84 5.4 Model underlying system design: many-to-many mapping between users and topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.5 Selection and collection agents . . . . . . . . . . . . . . . . . . . . . . 86 5.6 Selection agents and collection agents linked via central router . . . . 87 5.7 Selection agents and collection agents showing explicit collaboration links .................................... 96 5.8 Components of implemented Fab architecture ............. 100 5.9 Distance between actual and predicted rankings, averaged at each evaluation point. ............................... 110 5.10 For each source, distance between user rankings and its ideal ranking, averaged over all users at each evaluation point. . . . . . . . . . . . . 111 6.1 The three positions of the exploration/exploitation selector, as seen in the user interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2 Exploitation vs. exploration document selection strategies for 1-pref users. Graph shows ndpm values averaged over all 10 possible users, measured at test iterations (every fth iteration). ........... 121 6.3 Composition of documents in recommended sets for 1-pref users: 100% exploitation and 100% exploration strategies. Recorded for every training step, and averaged over all 10 possible users. . . . . . . . . . . . . 122 xvi
6. 4 Explor ation vs. exploit ation document select ion strategies for 3-pref users. Graph shows ndpm values averaged over 500 randomly selected users, measured at test steps every fifth iteration 6.5 Composition of do cuments in re commended set s for 3-pref users: 100% exploit ation, 50%6/50% mix and 100% explor ation strategies. Recorded for every training step, and averaged over 500 ran domly selected users. 123 6.6 Learning curves for users with in cre asingly complex preferences 6.7 Exploit at ion vs. explorat ion document select ion strategies for 1-pref users where preferences change before iter ation 35. Graph show s ndpm values averaged over all 10 possible users 6. 8 Slider inter face. 1 of 6 6.9 Slider interface. 2 of 6 6.10 Slider inter face, 3 of 6 6.11 Slider inter face. 4 of 6 6.12 Slider inter face, 5 of 6 6.13 Slider interface. 6 of 6 143
6.4 Exploration vs. exploitation document selection strategies for 3-pref users. Graph shows ndpm values averaged over 500 randomly selected users, measured at test steps every fth iteration. ........... 123 6.5 Composition of documents in recommended sets for 3-pref users: 100% exploitation, 50%/50% mix and 100% exploration strategies. Recorded for every training step, and averaged over 500 randomly selected users. 123 6.6 Learning curves for users with increasingly complex preferences. ... 124 6.7 Exploitation vs. exploration document selection strategies for 1-pref users where preferences change before iteration 35. Graph shows ndpm values averaged over all 10 possible users. . . . . . . . . . . . . . . . . 125 6.8 Slider interface, 1 of 6 .......................... 133 6.9 Slider interface, 2 of 6 .......................... 135 6.10 Slider interface, 3 of 6 .......................... 137 6.11 Slider interface, 4 of 6 .......................... 139 6.12 Slider interface, 5 of 6 .......................... 141 6.13 Slider interface, 6 of 6 .......................... 143 xvii
xviii
In t ro duct CORFE(n) An object which is almost totally indistinguishable from a newspaper, the one crucial difference being that it belongs to somebody else and is unaccount ably much more interesting that your owThwhid may otherwise appear to be in all respects identical Though it is a rule of life that a train or other public place may contain any number of cortes but only one newspaper, it is quite possible to transform your own perfectly ordinary newspaper into a corfe by the simple expedient of letting somebody else read from A dams and Lloyd, 1984 Imagine a new spaper that is personalized for your tastes. Instead of a selection of articles and fe atures chosen for a general audience by a human editor, a software agent picks items just for you, covering your particul ar topics of interest. You would be right in thinking that today's technology limits an elect ronic personalized newspaper It cannot compete with it s human-edited equivalent when it comes to complet eness of coverage for a large audience. However there are in format ion needs that a more personalized, automated new spaper can successfully meet. This thesis is about how to design such per son alized newspaper Con sider some of the problems in creating a tert recommender system, a soft ware
Chapter 1 Introduction CORFE (n.) An object which is almost totally indistinguishable from a newspaper, the one crucial di erence being that it belongs to somebody else and is unaccountably much more interesting that your own|which may otherwise appear to be in all respects identical. Though it is a rule of life that a train or other public place may contain any number of corfes but only one newspaper, it is quite possible to transform your own perfectly ordinary newspaper into a corfe by the simple expedient of letting somebody else read it. from [Adams and Lloyd, 1984] Imagine a newspaper that is personalized for your tastes. Instead of a selection of articles and features chosen for a general audience byahuman editor, a software agent picks items just for you, covering your particular topics of interest. You would be right in thinking that today's technology limits an electronic personalized newspaper. It cannot compete with its human-edited equivalent when it comes to completeness of coverage for a large audience. However there are information needs that a more personalized, automated newspaper can successfully meet. This thesis is about how to design such personalized newspapers. Consider some of the problems in creating a text recommender system, a software 1
CHAPTER. INTRODUCTION system that recommends do cuments for readers. First, it must discover potentially relevant documents. Unlike a major print new spaper, our electronic version has no cadres of journalist s at its disposal. Inst ead it is restricted to select ing among docu ments avail able on public net works, and in particular the World-Wide Web. Luckily the exponential increase in size of the Web over the last few years has made available a wealth of material, including, for inst ance, up-to-the minute news articles on a wide variety of topics. Nevert heless it is a resource-intensive t ask to track down do cument s that might be of interest to a particul ar reader ship, and this KG ph ase is one focus of the resear ch reported here But take a step back: how does a computer system even know which document might be of interest to its readers? Just as a friend would learn of your likes and dislikes from your comment s and behavior, a computer system can gat her feedback concerning previously recommended documents. This can take the form of ep l-it elk, where readers indicate, for inst ance, their degree of satisfact ion with a par ticular document on some kind of scale. Or it could be mp h-itfelak wh inferences are made from observations of a re aders actions, for in st an ce in using soft ware to browse through or read re commen ded documents. What is a computer to do with such feedback? Perhaps you indicate that you particularly enjoyed todays article about the new bordeaux vintage. should tomorrow s personalized newspaper be completely concentrated on Bordeaux and wines? Is there a place for an article about a new strain of flu, when the computer knows not hing of your interests re- garding health-rel ated stories? What about a feature on Tuscany which has proven to be very popular with others who enjoyed the bordeaux article? These questions concern the composition of the Cmedatio st the collection of documents de- livered in a single iteration, a single edition of the person alized newspaper. Method of gathering reader feedback, and resulting tradeoffs and choices when composing the re commen dation set are bot h import ant areas of investigation undert aken in this
2 CHAPTER 1. INTRODUCTION system that recommends documents for readers. First, it must discover potentially relevant documents. Unlike a ma jor print newspaper, our electronic version has no cadres of journalists at its disposal. Instead it is restricted to selecting among documents available on public networks, and in particular the World-Wide Web. Luckily the exponential increase in size of the Web over the last few years has made available a wealth of material, including, for instance, up-to-the minute news articles on a wide variety of topics. Nevertheless it is a resource-intensive task to track down documents that might be of interest to a particular readership, and this col lection phase is one focus of the research reported here. But take a step back: how does a computer system even know which documents might be of interest to its readers? Just as a friend would learn of your likes and dislikes from your comments and behavior, a computer system can gather feedback concerning previously recommended documents. This can take the form of explicit feedback, where readers indicate, for instance, their degree of satisfaction with a particular document on some kind of scale. Or it could be implicit feedback, where inferences are made from observations of a reader's actions, for instance in using software to browse through or read recommended documents. What is a computer to do with such feedback? Perhaps you indicate that you particularly enjoyed today's article about the new Bordeaux vintage. Should tomorrow's personalized newspaper be completely concentrated on Bordeaux and wines? Is there a place for an article about a new strain of u, when the computer knows nothing of your interests regarding health-related stories? What about a feature on Tuscany which has proven to be very popular with others who enjoyed the Bordeaux article? These questions concern the composition of the recommendation set, the collection of documents delivered in a single iteration, a single edition of the personalized newspaper. Methods of gathering reader feedback, and resulting tradeo s and choices when composing the recommendation set are both important areas of investigation undertaken in this