Online Structured Prediction via Coactive Learning

By Pannagadatta K. Shivaswamy, Thorsten Joachims. 2012

66 citations recorded by the source corpus.

We propose Coactive Learning as a model of interaction between a learning system and a human user, where both have the common goal of providing results of maximum utility to the user. At each step, the system (e.g. search engine) receives a context (e.g. query) and predicts an object (e.g. ranking). The user responds by correcting the system if necessary, providing a slightly improved - but not necessarily optimal - object as feedback. We argue that such feedback can often be inferred from observable user behavior, for example, from clicks in web-search. Evaluating predictions by their cardinal utility to the user, we propose efficient learning algorithms that have O(1/√T) average regret, even though the learning algorithm never observes cardinal utility values as in conventional online learning. We demonstrate the applicability of our model and learning algorithms on a movie recommendation task, as well as ranking for web-search.

Subfields: Artificial Intelligence, Management Science and Operations Research, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Natural Language Processing

Citations in the corpus

Learning Trajectory Preferences for Manipulators via Iterative Improvement (2013, methodology): “Despite its simplicity and even though the algorithm typically does not receive the optimal trajectory y∗ t = arg maxy s (xt, y) as feedback, the TPP enjoys guarantees on the regret [31].”
Human Effort and Machine Learnability in Computer Aided Translation (2014, background): “Our learning approach is related to coactive learning (Shivaswamy and Joachims, 2012).”
Programming by Feedback (2014, background): “Another trend is investigated in the ML ﬁeld, speciﬁ-cally aimed at information retrieval (Viappiani & Boutilier, 2010; Yue & Joachims, 2009; Shivaswamy & Joachims, 2012) and reinforcement learning (Wilson et al., 2012; Akrour et al., 2012; Knox et al., 2013; Jain et al., 2013) (more in section 2).”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, methodology): “Our regret analysis takes inspiration from the information-theoretic perspective on Thompson sampling introduced in Russo and Van Roy (2016), a framework for quantifying Bayesian regret in terms of the information gained at each step about the optimal action.”
Online learning to diversify from implicit feedback (2012, methodology): “For the case of modular utility (LIN), β = 0 and the above bound resembles the bound in [14].”
Coactive Learning (2015, background): “Coactive learning was first proposed by Shivaswamy and Joachims (2012); this paper serves as a journal extension of that paper, adding a complete discussion of batch updates and expected feedback, the exponentiated gradient algorithm, the O(log(T )/T ) algorithm for λ-strongly convex loss…”
Learning preferences for manipulation tasks from online coactive feedback (2015, methodology): “l. [57], Schulman et al. [50]) a priori. In this work we propose an algorithm for learning user preferences over trajectories through interactive feedback from the user in a coactive learning setting [51]. In this setting the robot learns through iterations of user feedback. At each iteration robot ”