Browse Prior Art Database

Method and System for Learning Online Trends for Interactive Query Auto-Completion

IP.com Disclosure Number: IPCOM000240683D
Publication Date: 2015-Feb-18
Document File: 6 page(s) / 2M

Publishing Venue

The IP.com Prior Art Database

Related People

Hua Ouyang: INVENTOR [+3]

Abstract

A method and system is disclosed for formulating Query Auto-Completion (QAC) as an online decision making problem such that Multi-Armed Bandits (MAB) setting can be applied efficiently. The method and system proposes to use Bayesian inference and Thompson Sampling to solve the MAB problem to better utilize prior knowledge derived from query logs.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Method and System for Learning Online Trends for Interactive Query Auto-Completion

Abstract

A method and system is disclosed for formulating Query Auto-Completion (QAC) as an online decision making problem such that Multi-Armed Bandits (MAB) setting can be applied efficiently.  The method and system proposes to use Bayesian inference and Thompson Sampling to solve the MAB problem to better utilize prior knowledge derived from query logs.  

Description

Query Auto-Completion (QAC) is widely used by modern search engines to assist users by predicting their intended queries.  Most QAC approaches face two challenges.  First, the QAC approaches rely on deterministic batch learning algorithms, where completion suggestions are ranked by their long term or short time popularities collected from previous query logs.  However, query popularities keep changing all the time, and ideally QAC are timely and adaptive enough to reflect time-sensitive changes in an online fashion.  Since QAC operates in a real-time scenario, where users interact with the search engine continually, a more natural approach is learning while doing.  Second, due to the vertical position bias, a query suggestion with a higher rank tends to attract more clicks regardless of the user’s original intention.  Hence, in the long run it is important to place some lower ranked yet potentially more relevant queries to higher positions, such that more valuable user feedbacks are collected.

Disclosed is a method and system for formulating QAC as an online decision making problem such that Multi-Armed Bandits (MAB) setting can be applied efficiently.  MAB is a sequential decision making setting defined over a set of  actions.  At each time step , a learner chooses an action  and observes some payoff  from environment.  The learner then updates knowledge based on payoff.  The goal is to maximize the commutative payoff obtained in a sequence of  allocations over time, or equivalently minimizing regret as per equation (1):

 

 

(1)

MAB is an instance of sequential decision making problems with partial feedback that naturally addresses the fundamental trade-off between exploration and exploitation.  The learner must balance the exploitation of actions that performed well in the past and the exploration of less played actions that could potentially yield higher payoffs in future.  In stochastic MAB, the reward of each arm is assumed to be drawn from some unknown probability distribution while in adversarial bandits no assumption is made about reward sequence.

In QAC, a user  comes at time  and types in a prefix of length .  After th keystroke, relevant candidates obtained by string matching construct the possible action set , where  is the pool of all the submitted queries in the past and can be grown by adding unseen words.  The QAC then presents a ranked suggestion list of  queries  with .  The user considers the suggestions in sequence and clicks up to one query.  An expe...