Tomáš Tunys

Jan Šedivý�

LEARNING TO RANK

FROM

IMPLICIT USER FEEDBACK

dissertation thesis proposal

Presentation Outline

• Introduction and Motivation
• Learning To Rank Overview
• Learning to Rank formulation, algorithms, and evaluation
• Training data quality/quantity problem
• Learning To Rank from Implicit feedback
• Passive vs Active learning
• Current and Future Work

Introduction and Motivation

Needles in the Haystack

“With No Signs of Slowing, the Data Keeps Growing”

• The global Internet population grew 6.59 % from 2010 to 2011 and now represents

​

2.1 BILLION PEOPLE

​

source: http://www.domo.com/learn/

Needles in the Haystack

“With No Signs of Slowing, the Data Keeps Growing”

• The global Internet population grew 14.3 % from 2011 to 2013 and now represents

​

2.4 BILLION PEOPLE

​

source: http://www.domo.com/learn/

Corollary: Satisfying Information Needs Becomes Harder

Corollary: Satisfying Information Needs Becomes Harder

What is Learning To Rank?

Learning To Rank

Searching for relevant documents

Documents

​

Document d₁

Document d₂

Document d₃

Document d₄

Document d₅

Feature Vectors

​

(... q + d₁ …)

(... q + d₂ …)

(... q + d₃ …)

(... q + d₄ …)

(... q + d₅ …)

Query q

Relevance Labels

​

relevance y₁

relevance y₂

relevance y₃

relevance y₄

relevance y₅

Learning To Rank

Searching for relevant documents

Documents

​

Document d₁

Document d₂

Document d₃

Document d₄

Document d₅

Feature Vectors

​

(... q + d₁ …)

(... q + d₂ …)

(... q + d₃ …)

(... q + d₄ …)

(... q + d₅ …)

Query q

Relevance Labels

​

relevance y₁

relevance y₂

relevance y₃

relevance y₄

relevance y₅

?

?

Learning To Rank

Searching for relevant documents

Documents

​

Document d₁

Document d₂

Document d₃

Document d₄

Document d₅

Feature Vectors

​

(... q + d₁ …)

(... q + d₂ …)

(... q + d₃ …)

(... q + d₄ …)

(... q + d₅ …)

Query q

Relevance Labels

​

relevance y₁

relevance y₂

relevance y₃

relevance y₄

relevance y₅

Ranking Model

Learning phase

Learning To Rank

Searching for relevant documents

Documents

​

Document d₁

Document d₂

Document d₃

Document d₄

Document d₅

Feature Vectors

​

(... q + d₁ …)

(... q + d₂ …)

(... q + d₃ …)

(... q + d₄ …)

(... q + d₅ …)

Query q

Ranking Model

(inference)

score s₁

score s₂

score s₃

score s₄

score s₅

Production phase

Learning to Rank

Formulation, Evaluation, Algorithms

Learning To Rank: Problem Formulation

Empirical Risk Minimization

• Given a labeled dataset S = {(q_i, D_i, y_i)}_{i = 1}, where q_i is a query, D_i are associated documents, and y_i are the corresponding relevances of documents to the query.
• The goal is to find a ranker f: R^N→R such that when the documents are sorted according to ranking scores, then such permutation π(f, q_i, D_i) will leave the documents sorted in descending order according to their relevance to the query.

​

​

​

​

​

​

​

​

Q

performance measure

Evaluation Measures

Normalized Discounted Cumulative Gain

• One of the most frequently used measures. It is based on positional model.

​

Evaluation Measures

• All (interesting) performance measures are non-convex, non-differentiable, and discontinuous functions of the ranking scores.
• Pose huge challenges for direct optimization.�Sidestepped by:
• non-convex optimization techniques.
• convex approximation measures
• surrogate measures

​

Training Data Problem

• The performance “bottleneck” - the quality and quantity matters “much more” than in case of ordinary classification or regression.

​

Very expensive, time consuming, and of disputable quality.

Learning To Rank

• Pointwise algorithms (PRank):
• Based on reducing the problem of ranking to classification or regression.
• Pros: computational complexity (linear)
• Cons: often does not work!
• Pairwise algorithms (RankSVM):
• Reduces the problem to binary classification on pairs of documents.
• Pros: decoupling from relevance scores
• Cons: computational complexity (quadratic)

​

Types of Algorithms

Learning To Rank

• Listwise algorithms (LambdaMART):
• Current state of the art in Learning To Rank.
• Lambda “trick” + MART
• Pros: directly optimizes performance measures! computational complexity (in production)
• Cons: computational complexity (in training)

​

Types of Algorithms

Learning To Rank From Implicit Feedback

Learning To Rank

• The relevance of documents to queries are willingly judged by trained people - annotators.
• Ordinary people hardly ever provide this kind of explicit feedback (if they are asked).
• But query logs store enormous amount of data which can be exploited to assess the relevance of documents to queries - user implicit feedback:
• clickthrough data
• dwell time
• query reformulations

​

Exploiting User Implicit Feedback

Learning To Rank

• Implicit Feedback data can enter into the process of training in several different ways:
• new features in query-document vectors
• optimization constraints (RankSVM)
• enlarging document sets for queries (reformulations)
• improve quality of training data
• clustering queries according to their type/user intents
• interleaving evaluation (active learning/bandits)
• Potential problems: noisy data, biased in different ways

​

Exploiting User Implicit Feedback

Learning To Rank

• Use of implicit feedback = a huge frontier of unexplored potential. Reason - query log data unavailability (starting to change - Living Labs for IR Evaluation)

​

Exploiting User Implicit Feedback

Current and Future Work

• Currently I am participating on a project from University of Amsterdam led by dr. Masrour Zoghi (ILPS).
• Preliminary goals:
• Use clickthrough data to identify important features and cluster queries according to trained (linear) rankers for them (using DBGD + click models)
• Design and train ensemble of query-cluster specific rankers.
• Plan to visit UvA for 4 months this semester.

​

Current and Future Work

• The biggest supporter of this research is Seznam.cz. It provides data and computational infrastructure:
• It has just entered into Living Labs project:
• Provide researchers access to real-time/real-world environment and possibility to benchmark their algorithm against participating systems.
• My task is to test the functionality of their implementation of the LLC API.

​

Current and Future Work

• Improve our implementation of LambdaMART and introduce clickthrough data into the training process.

​