1Foundations of Artificial IntelligenceLearning Ranking Functions for Search EnginesCS472 – Fall 2007Thorsten JoachimsJoint work with: Filip Radlinski, Geri Gay, Laura Granka, Helene Hembrooke, Bing PangAdaptive Search Engines• Current Search Engines– One-size-fits-all– Hand-tuned retrieval function• Hypothesis– Different users need different retrieval functions– Different collections need different retrieval functions• Machine Learning– Learn improved retrieval functions– User Feedback as training dataOverview• How can we get training data for learning improved retrieval functions?– Explicit vs. implicit feedback– User study with eye-tracking and relevance judgments– Absolute vs. relative feedback– Accuracy of implicit feedback• What learning algorithms can use this training data effectively?– Ranking Support Vector Machine– User study with meta-search engineSources of Feedback• Explicit Feedback– Overhead for user– Only few users give feedback => not representative• Implicit Feedback– Queries, clicks, time, mousing, scrolling, etc.– No Overhead– More difficult to interpretFeedback from Clickthrough Data1. Kernel Machines http://svm.first.gmd.de/2. Support Vector Machinehttp://jbolivar.freeservers.com/3. SVM-Light Support Vector Machine http://ais.gmd.de/~thorsten/svm light/4. An Introduction to Support Vector Machineshttp://www.support-vector.net/5. Support Vector Machine and Kernel ... Referenceshttp://svm.research.bell-labs.com/SVMrefs.html6. Archives of SUPPORT-VECTOR-MACHINES ...http://www.jiscmail.ac.uk/lists/SUPPORT...7. Lucent Technologies: SVM demo applet http://svm.research.bell-labs.com/SVT/SVMsvt.html8. Royal Holloway Support Vector Machine http://svm.dcs.rhbnc.ac.uk(3 < 2),(7 < 2), (7 < 4), (7 < 5), (7 < 6)Rel(1),NotRel(2), Rel(3),NotRel(4),NotRel(5),NotRel(6),Rel(7)Relative Feedback: Clicks reflect preference between observed links.Absolute Feedback: The clicked links are relevant to the query.Is Implicit Feedback Reliable?How do users choose where to click?• How many abstracts do users evaluate before clicking?• Do users scan abstracts from top to bottom?• Do users view all abstracts above a click?• Do users look below a clicked abstract?How do clicks relate to relevance?• Absolute Feedback: Are clicked links relevant? Are not clicked links not relevant?• Relative Feedback:Are clicked links more relevant than not clicked links?1. Kernel Machines http://www.kernel-machines.org/2. Support Vector Machinehttp://jbolivar.freeservers.com/3. SVM-Light Support Vector Machine http://ais.gmd.de/~thorsten/svm light/4. An Introduction to SVMshttp://www.support-vector.net/5. Support Vector Machine and ... http://svm.bell-labs.com/SVMrefs.html6. Archives of SUPPORT-VECTOR...http://www.jisc.ac.uk/lists/SUPPORT...7. Lucent Technologies: SVM demo applet http://svm.bell-labs.com/SVMsvt.html8. Royal Holloway SVM http://svm.dcs.rhbnc.ac.uk9. SVM Worldhttp://www.svmworld.com10. Fraunhofer FIRST SVM page http://svm.first.gmd.de2User Study: Eye-Tracking and Relevance• Scenario– WWW search– Google search engine– Subjects were not restricted– Answer 10 questions• Eye-Tracking– Record the sequence of eye movements– Analyze how users scan the results page of Google• Relevance Judgements– Ask relevance judges to explicitly judge the relevance of all pages encountered– Compare implicit feedback from clicks to explicit judgmentsWhat is Eye-Tracking?Device to detect and record where and what people look at – Fixations: ~200-300ms; information is acquired– Saccades: extremely rapid movements between fixations – Pupil dilation: size of pupil indicates interest, arousalEye tracking device“Scanpath” output depicts pattern of movement throughout screen. Black markers represent fixations.How Many Links do Users View?Total number of abstracts viewed per page02040608010012012345678910Total number of abstracts viewedfrequencyMean: 3.07 Median/Mode: 2.00In Which Order are the Results Viewed?=> Users tend to read the results in orderInstance of arrival to each result051015202512345678910Rank of resultmean fixation value of arrivalLooking vs. Clicking=> Users view links one and two more thoroughly / often=> Users click most frequently on link one0204060801001201401601801234567891011Rank of result# times rank selected00.10.20.30.40.50.60.70.80.91mean time (s)# times result selectedtime spent in abstractConclusion: Decision Process• Users most frequently view two abstracts• Users typically view results in order from top to bottom• Users view links one and two more thoroughly and often• Users click most frequently on link one• Users typically do not look at links below before they click (except maybe the next link)=> Design strategies for interpreting clickthrough data that respect these properties!3Strategies for Generating Relative FeedbackStrategies• “Click > Skip Above”– (3>2), (5>2), (5>4)• “Last Click > Skip Above”– (5>2), (5>4)• “Click > Earlier Click”– (3>1), (5>1), (5>3)• “Click > Skip Previous”– (3>2), (5>4)• “Click > Skip Next”– (1>2), (3>4), (5>6)1. Kernel Machines http://www.kernel-machines.org/2. Support Vector Machinehttp://jbolivar.freeservers.com/3. SVM-Light Support Vector Machine http://ais.gmd.de/~thorsten/svm light/4. An Introduction to SVMshttp://www.support-vector.net/5. Support Vector Machine and ... http://svm.bell-labs.com/SVMrefs.html6. Archives of SUPPORT-VECTOR...http://www.jisc.ac.uk/lists/SUPPORT...7. Lucent Technologies: SVM demo applet http://svm.bell-labs.com/SVMsvt.html8. Royal Holloway SVM http://svm.dcs.rhbnc.ac.uk9. SVM Worldhttp://www.svmworld.com10. Fraunhofer FIRST SVM page http://svm.first.gmd.deComparison with Explicit Feedback=> All but “Click > Earlier Click” appear accurateOverview• How can we get training data for learning improved retrieval functions?– Explicit vs. implicit feedback– User study with eye-tracking and relevance judgments– Absolute vs. relative feedback– Accuracy of implicit feedback• What learning algorithms can use this training data effectively?– Ranking Support Vector Machine– User study with meta-search engineLearning Retrieval Functions from Pairwise PreferencesIdea: Learn a ranking function, so that number of violated pair-wise training preferences is minimized.Form of Ranking Function: sort by rsv(q,di) = w1* (#of query words in title of di)+ w2* (#of query words in