1、Interactively Optimizing Information Retrieval Systems as a Dueling Bandits Problem,ICML 2009Yisong Yue Thorsten Joachims Cornell University,Learning To Rank,Supervised Learning Problem Extension of classification/regression Relatively well understood High applicability in Information RetrievalRequi
2、res explicitly labeled data Expensive to obtain Expert judged labels = search user utility? Doesnt generalize to other search domains.,Our Contribution,Learn from implicit feedback (users clicks) Reduce labeling cost More representative of end user information needsLearn using pairwise comparisons H
3、umans are more adept at making pairwise judgments Via Interleaving Radlinski et al., 2008On-line framework (Dueling Bandits Problem) We leverage users when exploring new retrieval functions Exploration vs exploitation tradeoff (regret),Team-Game Interleaving,1. Kernel Machines http:/svm.first.gmd.de
4、/ 2. Support Vector Machine http:/ 3. An Introduction to Support Vector Machines http:/www.support- 4. Archives of SUPPORT-VECTOR-MACHINES . http:/www.jiscmail.ac.uk/lists/SUPPORT. 5. SVM-Light Support Vector Machine http:/ais.gmd.de/thorsten/svm light/,1. Kernel Machines http:/svm.first.gmd.de/ 2.
5、SVM-Light Support Vector Machine http:/ais.gmd.de/thorsten/svm light/ 3. Support Vector Machine and Kernel . References http:/svm.research.bell- 4. Lucent Technologies: SVM demo applet http:/svm.research.bell- 5. Royal Holloway Support Vector Machine http:/svm.dcs.rhbnc.ac.uk,1. Kernel Machines T2 h
6、ttp:/svm.first.gmd.de/ 2. Support Vector Machine T1 http:/ 3. SVM-Light Support Vector Machine T2 http:/ais.gmd.de/thorsten/svm light/ 4. An Introduction to Support Vector Machines T1 http:/www.support- 5. Support Vector Machine and Kernel . References T2 http:/svm.research.bell- 6. Archives of SUPP
7、ORT-VECTOR-MACHINES . T1 http:/www.jiscmail.ac.uk/lists/SUPPORT. 7. Lucent Technologies: SVM demo applet T2 http:/svm.research.bell- r1,f2(u,q) r2,Interleaving(r1,r2),(u=thorsten, q=“svm”),Interpretation: (r2 r1) clicks(T2) clicks(T1),Invariant: For all k, in expectation same number of team members
8、in top k from each team.,NEXT PICK,Radlinski, Kurup, Joachims; CIKM 2008,Dueling Bandits Problem,Continuous space bandits F E.g., parameter space of retrieval functions (i.e., weight vectors) Each time step compares two bandits E.g., interleaving test on two retrieval functions Comparison is noisy &
9、 independent,Dueling Bandits Problem,Continuous space bandits F E.g., parameter space of retrieval functions (i.e., weight vectors) Each time step compares two bandits E.g., interleaving test on two retrieval functions Comparison is noisy & independentChoose pair (ft, ft) to minimize regret:(% users
10、 who prefer best bandit over chosen ones),Example 1 P(f* f) = 0.9 P(f* f) = 0.8 Incurred Regret = 0.7Example 2 P(f* f) = 0.7 P(f* f) = 0.6 Incurred Regret = 0.3Example 3 P(f* f) = 0.51 P(f* f) = 0.55 Incurred Regret = 0.06,Modeling Assumptions,Each bandit f 2F has intrinsic value v(f) Never observed
11、 directly Assume v(f) is strictly concave ( unique f* )Comparisons based on v(f) P(f f) = ( v(f) v(f) ) P is L-LipschitzFor example:,Probability Functions,Dueling Bandit Gradient Descent,Maintain ft Compare with ft (close to ft - defined by step size) Update if ft wins comparisonExpectation of updat
12、e close to gradient of P(ft f) Builds on Bandit Gradient Descent Flaxman et al., 2005, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Ba
13、ndit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Curre
14、nt point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradi
15、ent Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent, explore step size exploit step size Current point Losing candidate Winning candidate,Dueling Bandit Gradient Descent,Analysis (Sketch),Dueling Bandit Gradient Descent Se
16、quence of partially convex functions ct(f) = P(ft f) Random binary updates (expectation close to gradient)Bandit Gradient Descent Flaxman et al., SODA 2005 Sequence of convex functions Use randomized update (expectation close to gradient) Can be extended to our setting,(Assumes more information),Ana
17、lysis (Sketch),Convex functions satisfyBoth additive and multiplicative error Depends on exploration step size Main analytical contribution: bounding multiplicative error,Regret Bound,Regret grows as O(T3/4):Average regret shrinks as O(T-1/4) In the limit, we do as well as knowing f* in hindsight, =
18、 O(1/T-1/4 ) = O(1/T-1/2 ),Practical Considerations,Need to set step size parameters Depends on P(f f)Cannot be set optimally We dont know the specifics of P(f f) Algorithm should be robust to parameter settingsSet parameters approximately in experiments,50 dimensional parameter space Value function
19、 v(x) = -xTx Logistic transfer function Random point has regret almost 1,More experiments in paper.,Web Search Simulation,Leverage web search dataset 1000 Training Queries, 367 DimensionsSimulate “users” issuing queries Value function based on NDCG10 (ranking measure) Use logistic to make probabilis
20、tic comparisonsUse linear ranking function.Not intended to compete with supervised learning Feasibility check for online learning w/ users Supervised labels difficult to acquire “in the wild”,Chose parameters with best final performance Curves basically identical for validation and test sets (no ove
21、r-fitting) Sampling multiple queries makes no difference,What Next?,Better simulation environments More realistic user modeling assumptionsDBGD simple and extensible Incorporate pairwise document preferences Deal with ranking discontinuitiesTest on real search systems Varying scales of user communit
22、ies Sheds on insight / guides future development,Extra Slides,Active vs Passive Learning,Passive Data Collection (offline) Biased by current retrieval functionPoint-wise Evaluation Design retrieval function offline Evaluate onlineActive Learning (online) Automatically propose new rankings to evaluat
23、e Our approach,Relative vs Absolute Metrics,Our framework based on relative metrics E.g., comparing pairs of results or rankings Relatively recent developmentAbsolute Metrics E.g., absolute click-through rate More common in literature Suffers from presentation bias Less robust to the many different
24、sources of noise,What Results do Users View/Click?,Joachims et al., TOIS 2007,Analysis (Sketch),Convex functions satisfyWe have both multiplicative and additive error Depends on exploration step size Main technical contribution: bounding multiplicative error,Existing results yields sub-linear bounds
25、 on:,Analysis (Sketch),We know how to bound Regret:We can show using Lipschitz and symmetry of :,More Simulation Experiments,Logistic transfer function (x) = 1/(1+exp(-x) 4 choices of value functions, set approximately,NDCG,Normalized Discounted Cumulative Gain Multiple Levels of RelevanceDCG: contr
26、ibution of ith rank position: Ex: has DCG score ofNDCG is normalized DCG best possible ranking as score NDCG = 1,Considerations,NDCG is discontinuous w.r.t. function parameters Try larger values of , Try sampling multiple queries per updateHomogenous user values NDCG10 Not an optimization concern Modeling limitationNot intended to compete with supervised learning Sanity check of feasibility for online learning w/ users,
