Multitask Coactive Learning

1 Introduction

Coactive learning [Raman et al., 2013a; 2012; 2013b; Shivaswamy and Joachims, 2012] is a Machine Learning framework where the learner is presented with a sequence of problems and for each problem constructs a candidate solution. The expert then attempts to improve the solution if it is not of sufficient quality and shows the improved solution to the learner. The learner needs to discover a good utility function to reflect the expert's preferences over potential solutions, ultimately leading to a decrease in the amount of effort the expert needs to spend on improving candidate solutions. For example, consider a route planner which tries to adapt to the specific user's preferences over whether to take fast routes, easy routes or scenic routes. The system presents the user with a candidate solution and the user can then modify this trajectory according to their personal preferences. The learner then attempts to learn those preferences to improve future performance.

For a task such as route planning, the same systemmight be used by a number of different users who might have similar but non-identical utility functions. Also, one could consider different types of tasks: people might have different preferences for routes for different purposes (e.g. business vs. pleasure). Ideally, the system should learn each individual user's preferences, or learn to solve each individual task, while taking advantage of the similarities between the users and tasks to learn quickly.

The above motivates the study of coactive learning in a multitask setting. Specifically, in this paper, it is assumed that the sequence of tasks is generated by individuals from a user population. The learner is provided with the user identifier for each task, which can be used to customize task solutions to individuals. A trivial approach to this multitask learning problem would be to have an independent coactive learner for each user. However, when the preferences of different users have similarities, some amount of generalization can be expected to improve overall performance compared to independent learning. At the same time, if the users have little in common we would like the multitask learner to not perform much worse than independent learning.

The main contribution of this paper is to present and analyze a Perceptron algorithm for multitask coactive learning (the MCL algorithm). This is the first such algorithm that meets both of the above goals. Our bounds on the average expert cost during learning show that the algorithm is able to guarantee convergence to optimal solutions for individual experts, even when experts are not similar. At the same time, the algorithm can be expected to benefit from generalization across the expert population when experts are sufficiently similar. We also provide bounds for two extreme algorithms: one that treats all experts as if they are a single expert, and a second that learns independently for each expert. These bounds provide insight into when generalization can be beneficial compared to independent learning. The theoretical bounds are confirmed by our experimental evaluation in three domains. These experiments show that the balanced Perceptron algorithm is robust across experts of varying similarity and can significantly improve on the baseline algorithms.

Prasad Tadepalli

2 RelatedWork

The most closely related prior work considered a multiuser coactive learning setting [Raman and Joachims, 2013]. However, the learner was not provided with a user identifier and simply treated all tasks as if coming from a single user. In general, such an approach will not be able to converge to a solution that works well for all users, especially when user groups have very different preferences. Rather, in our setting, by providing the learner with user identifiers, it is possible to converge to optimal solutions for individual users, while also exploiting commonalities when possible.

Multitask learning has been more widely studied outside of the coactive framework (e.g. classification). However, in most of the existing work it is either assumed that an entire dataset of examples is given (offline setting) [Evgeniou et al., 2005; Evgeniou and Pontil, 2004] which allows for estimating the extent to which the tasks are similar, so that highly similar tasks can be clustered and learned together, or (as in [Cavallanti et al., 2010]) the assumption is made that a matrix is given expressing the similarity between tasks. This matrix is used as a regularizer for an online linear classification algorithm. In this paper, since we do not assume any domain knowledge to be given regarding the similarity of individual users, we will focus on algorithms that attempt to generalize across users, while proving worst-case bounds that are not much worse than independent learning, even when users have no similarities.

In recent work, online approaches for multitask classification learning have been studied to learn and leverage task similarities in a way that is closely related to sparse coding [Ruvolo and Eaton, 2013; Maurer et al., 2013; Ruvolo and Eaton, 2014]. Extensions of these approaches have been demonstrated in the context of temporal difference learning [Sreenivasan et al., 2014] and policy gradient reinforcement learning [Bou-Ammar et al., 2014]. However, none of these algorithms have been applied to coactive learning, where the optimization criterion is to reduce the user effort in improving the system's solutions. In this paper, we study an alternative approach based on Perceptron-style online learning.

3 Problem Statement and Notation

We consider a problem-solving setting, where X is a set of problem instances, and Y is a set of candidate solutions. A problem-solution pair will be described by a feature vector ⃗φ : X × Y → RD where D is the dimension of the feature vectors. We assume that ∀x, y : ||⃗φ(x, y)|| ≤ R. We consider a multitask setting where there are M experts, or users, who will be providing problems to our learner. Each expert has a linear preference function, such that the preference of expert i for solution y to problem x is given by ⃗u∗i · ⃗φ(x, y), where we assume that ||⃗u∗i || = 1. Note that this same framework can be used for a single expert, solving a sequence of tasks having M task types. We assume that there is a black-box problemsolver solve(x, ⃗w) = argmaxy ⃗φ(x, y) · ⃗w available, which takes a problem x ∈ X, an estimated weight vector ⃗w and returns a candidate solution y ∈ Y , which is optimal for the given estimate of the utility function 1 .

At time-step t, the learning algorithm receives a problem instance xt ∈ X and an expert index a(t). We assume the expert indices are sampled from an (unknown) fixed multinomial distribution P(i). The algorithm uses its current estimate ⃗wta(t) of expert a(t)'s weight vector to construct a solution, yt = solve(xt, ⃗wta(t) ).

The candidate solution yt is presented to expert a(t), who either accepts it as good enough (at no cost) or spends an amount of effort improving the solution, obtaining a solution y′t for which ⃗u∗a(t) · ⃗φ(xt, y′t ) ≥ ⃗u∗a(t) · ⃗φ(xt, yt)+κCt, where Ct is the cost, reflecting the amount of effort spent, and κ is a constant indicating the minimal return on investment, the minimal improvement in solution quality to vindicate the effort spent. We assume that Ct ≥ 0. In this paper, the notation ⃗∆t is used to indicate ⃗φ(xt, y′t ) - ⃗φ(xt, yt), so we get: ⃗u∗a(t) · ⃗∆t ≥ κCt. Since we have the bound of R on the feature vectors, we know that ||⃗∆t|| ≤ 2R. The task is to minimize the average effort 1 T ∑Tt=1 Ct.

We characterize the similarity of experts by a parameter δ that satisfies: ∀i, j : ⃗u∗i · ⃗u∗j ≥ 1 - δ. Lower values of δ mean that the experts are more similar. We will denote the difference between expert preference weight vectors by ⃗ ξi,j = ⃗u∗i - ⃗u∗j . It will be useful to note that ∀i, j : ||⃗ ξi,j || ≤ √2δ, which follows from the law of cosines.

4 Balanced Perceptron-based Learner

In our framework, the learning problem consists of learning appropriate preference functions represented by weight vectors for all experts. In this section, we focus on learning algorithms that attempt to generalize across all experts. The performance of such algorithms will naturally depend on the similarity of experts as characterized by δ.

Each of the algorithms we consider are instances of a single algorithm, called Multitask Coactive Learner (MCL) (see algorithm 1) that is parameterized by parameters α and β, which control the amount of generalization across experts. The MCL algorithm maintains and updates a single global weight vector ⃗wG and expert-specific weight vectors ⃗wi. Intuitively ⃗wG is intended to capture the commonality among experts in order to support generalization, while ⃗wi is intended to capture user-specific preference variations. After a problem instance for expert i is processed, resulting in feedback from expert i, the weight vector ⃗wi is updated along with the global weight vector ⃗wG (details below). The MCL algorithm starts with all expert-specific vectors and global vectors ⃗w1 i = ⃗w1G = ⃗0. Whenever we need to estimate the weight vector for expert i at time t, in order to produce a solution, the sum α⃗wi + β ⃗wG is used.

1 Using an analysis similar to that presented in [Goetschalckx et al., 2014], this can be changed into a locally optimal solver, where the precise definition of "locally optimal" depends on both the blackbox solver and the possible expert improvements. In the "path planning" experiments presented in this paper, only such local optimality is practical. The theoretical results in Section 5 still hold given the extra assumptions from [Goetschalckx et al., 2014].

⃗wG ← ⃗0 ∀i : ⃗wi ←⃗0 loop (x, a(t)) ← new problem instance and userID y ← solve(x, α ⃗wa(t) + β ⃗wG) y′ ← improvea(t)(x, y) ⃗∆ ← φ(x, y′ ) - φ(x, y) if ⃗∆ · (α⃗wa(t) + β ⃗wG) ≤ 0 then ⃗wa(t) ← ⃗wa(t) + ⃗∆ ⃗wG ← ⃗wG + ⃗∆ end if end loop

It remains to specify how the weights are updated by the algorithm. When a problem instance is processed with ⃗∆t ̸= ⃗0 (i.e., the expert was able to improve the learner's returned solution), both the active expert a(t)'s weight vector and the global weight vector are updated by a weighted Perceptron update ⃗wt+1 a(t) = ⃗wta(t) + ⃗∆t and ⃗wt+1 G = ⃗wtG + ⃗∆t. Thus, in addition to updating the total weight vector of user a(t), the update impacts the total weight vectors of other users through the adjustment to ⃗wG. 2

In general, the specific values used for α and β allow for a range of algorithms. We consider the following cases.

• global (α = 0, β = 1). In this case, all experts are treated as if they were the same. This results in the perceptron-based approach presented as Algorithm 2 in [Raman and Joachims, 2013]. Clearly, unless all expert preferences are identical or the multinomial distribution P(·) is degenerate, meaning the same expert is always selected, this approach can never converge to the actual weight vectors.
• individual (α = 1, β = 0). This means no generalization is performed, and we essentially have M independent perceptron-based coactive learners as presented in [Shivaswamy and Joachims, 2012]. This is guaranteed to learn the optimal weights eventually, but ignores any potential similarity between experts.
• balanced (α = β = 1). This leads to a combined approach, both generalizing over different users yet at the same time specializing per user. This is equal to a coactive variant of the algorithm based on Section 3.2 of [Cavallanti et al., 2010].

5 Average Cost Bounds

In this section, bounds on the average cost (expert effort) 1 T ∑Tt=1 Ct will be presented for the algorithms described in Section 4.

2 In the case where solve is not guaranteed to give the local optimum (see Footnote 1), the update should only be performed if 〈α⃗wta(t) + β⃗wtG, ⃗∆t〉 ≤ 0); in the case where solve gives the global optimum, this condition is always satisfied.

5.1 global

We first consider bounding the average cost of global, which does not attempt to distinguish among different experts. In this case, it is impossible to converge to a solution with average effort equal to 0, unless all experts are exactly the same. The badness of the learned weight vector depends on the number of experts (M) and the difference between experts (δ) as quantified by the following result.

Theorem 1. Using the global algorithm, the average effort for the first T examples is bound by 1 T ∑Tt=1 Ct ≤ 2R κ ( 1 √T + √2δ M-1 M ).

Proof. First, an upper bound on ||⃗wT+1 G ||2 ≤ 4R2T can be shown similar to the work in [Shivaswamy and Joachims, 2012]. Let ⃗u∗G = ∑i ⃗u∗i . We can prove a lower bound on ⃗wT +1 G · ⃗u∗G:

Composing with the upper bound and applying the Cauchy-Schwarz inequality gives us Mκ ∑Tt=1 Ct - T2R√2δ(M - 1) ≤ 2R√TM, which proves the claim.

This bound shows that when δ > 0 and M > 1, the average effort will not necessarily converge to 0. This makes sense, since differences between individual experts can never be learned.

5.2 individual

For the single expert setting, the results in [Goetschalckx et al., 2014] give an average cost bound of 1 T ∑Tt=1 Ct ≤ 2R κ√T for a Perceptron-based algorithm. Here we consider how this average cost depends on the number of experts M for M > 1, when we treat each expert as an independent learning problem (i.e. the individual algorithm). The following result shows that while individual will be guaranteed to converge to a perfect solution, ignoring existing similarities among experts can slow down learning.

First, it is useful to note that, if Ti gives the number of iterations where expert i was the active user, (so T = ∑i Ti)

then we have that

and this bound is obtained with equality when all experts are selected equally often.

Theorem 2. Using algorithm individual, the average effort spent during the first T iterations is bound by 1 T ∑Tt=1 Ct ≤ 2R κ√T √M.

Proof. From a slight variation of the results in [Shivaswamy and Joachims, 2012], we observe that a Perceptron-based algorithm for a single user will have the bound 1 T ∑Tt=1 Ct ≤ 2R κ√T .

In the multi-user setting, each expert i will be responsible for Ti examples. This means that expert j will have a total cost bound by ∑t,a(t)=j Ct ≤ 2R√Tj κ . The total cost for all experts will be bound by

From inequality (1) we obtain the result: 1 T ∑Tt=1 Ct ≤ 2R κ√T √M.

This result shows that there is a multiplicative penalty of √M compared to the single expert case, which is due to the fact that each independent learner is learning from fewer examples. By considering the bounds for global and individual we can see that during the early stages of learning, when T = O( Mδ ), global will have a smaller worst case regret than individual, but for larger T individual will have a smaller worst case regret. This agrees with the intuition that generalization helps the most when there are larger numbers of users that are more similar, but eventually generalization will hurt performance in the limit.

5.3 General Case

We now show that the general MCL algorithm (with α > 0) strikes a balance between global and individual. In particular, we would like an algorithm that can take advantage of generalization (unlike individual), but also converge to perfect solutions for each expert in the limit (unlike global).

For MCL with any β ≥ 0 and α > 0, we have the following bound:

Theorem 3. Using the MCL algorithm with α > 0 and β ≥ 0, the average effort of the first T iterations is bound

√α2+β2 √M

Proof. We work with (M + 1)D-dimensional vectors, where all the user vectors are combined into the vector ⃗u = [⃗0; ⃗u∗1 ; ⃗u∗2 ; . . . ; ⃗u∗M ], and all the learned weights are combined into the vector ⃗wT = [⃗wTG; ⃗wT 1 ; . . . ; ⃗wTM ]. If we define ⃗∆T = [β⃗∆T ;⃗0; . . . ; α⃗∆T ; . . . ;⃗0] where the occurence of α⃗∆T occurs at the a(T)'th position (a(T) is the index of the expert responsible for the example at time T). Note that 〈⃗U, ⃗∆T 〉 = α〈⃗u∗a(T) , ⃗∆T 〉 ≥ ακCT and 〈⃗wT , ⃗∆T 〉 is the prediction that the MCL algorithm would make at time T, so we know that 〈⃗wT , ⃗∆T 〉 ≤ 0 if there was an update performed at time T. Using this notation, we can use the standard analysis for a perceptron algorithm for coactive learning. We get that ||⃗wT+1 ||2 ≤ (α2 + β2 )4R2T and ακ ∑Tt=1 Ct ≤ 〈⃗U, ⃗wT+1 〉 ≤ 2R√α2 + β2√T √M, which proves the bound.

This proof shows that MCL using any value β ≥ 0 and any α > 0 is guaranteed to converge to an optimal solution for all users, as is the case for individual (in fact, Theorem 2 is a special case of Theorem 3, with α = 1, β = 0). However, it is expected that allowing the algorithm to generalize over the different users will result in a large boost during the early stages, as is the case for global. In the next section, we will empirically verify this behavior for the specific setting of α = β = 1, the balanced algorithm, resulting in a bound of 1 T ∑Tt=1 Ct ≤ 2R κ √2M √T .

6 Experiments

The algorithms are evaluated on two synthetic and one realworld domain. All reported results are averages over 10 runs.

The synthetic domains have feature vectors of dimension 10. A base vector was generated with all coefficients generated from a uniform [0, 1] distribution. All experiments used 50 experts. For each expert a user vector is generated by perturbing the base vector by a vector drawn from a normal distribution with mean ⃗0 and diagonal covariance matrix σI10 and then normalizing. Experiments were performed with σ = 0.01, 0.05 and 0.25, resulting in values of δ of about 0.001, 0.02 and 0.38. At each iteration, an expert is selected according to a uniform multinomial.

6.1 Domains

Ranking.

Here, for each problem, the learner is presented with 30 vectors ⃗vi and needs to sort them in order of estimated utility, where utility is given by ⃗vi · ⃗wi. The expert tries to improve on the ranking according to their utility function by iteratively switching the positions of two subsequent items in the list if the true utility of the former is more than κ higher than the utility of the latter vector. In the experiment, the value κ = 0.1 was used. Each such switch added 1 to the total effort spent. The feature vector for a candidate solution is constructed as ∑29 i=1 ∑30 j=i+1 (⃗vj - ⃗vi).

Path Planning.

Here, for each problem, the environment consists of a 7dimensional hypercube, where each edge is described by a 10-dimensional feature vector, and the solver needs to find the optimal path of length 7 from one corner to the diagonally opposite corner. The cost of a path consisting of edges with feature vectors ⃗v1 . . .⃗v7 is given by ⃗wi · ∑j ⃗ vj. There are 7! such possible paths.

The solver uses a simple 2 step lookahead search. The expert can improve this trajectory by looking at three subsequent moves and reordering them, if any such reordering gives an improvement of at least κ = 0.1, until no such improvement is possible.

Spam Detection.

The third domain is a real-world domain, namely the spam detection dataset as presented in the 2006 ECML/PKDD Discovery Challenge [Bickel, 2008], task b. This task has 15 users, and for each user a set of 400 e-mail messages, represented by bag-of-word (150000-dimensional) feature vectors. Each e-mail has a classification of either being a spam e-mail or a clean e-mail.

In this paper we treat this dataset as a ranking task. At each step a user is randomly selected, and 10 e-mails are randomly selected from their set. The learner needs to present them to the user, ordered by whether they are thought to be spam or not. The user will then move non-spam e-mails to the top of the list until the list is properly sorted, the number of such moves is the measured cost. The feature vectors are constructed similar to the feature vectors of the ranking domain.

6.2 Results

The goal of the experiments is to observe the behavior of global, individual and balanced when applied to problems of varying expert similarity. We applied the algorithms to the artificial domains, with values of σ set to 0.01, 0.05 or 0.25.

Results are shown in Figures 1-6. Some things are very noticeable. Both global and balanced have a dramatic drop in average cost after just a few examples. When the experts are highly similar (σ = 0.01 and σ = 0.05) global outperforms individual by large margins, though the advantage diminishes for large T as expected.

The opposite is true for the case where experts are quite different (σ = 0.25), where generalizing from other experts hurts performance. The average cost of global drops fast for the first few examples, but then remains at the same level.

In both of these cases, balanced behaves similarly to the better of the two algorithms, showing that balanced is a robust way to allow for generalization while not sacrificing convergence when generalization is not possible. When facing a problem where it is not known beforehand what magnitude δ might have, balanced provides a safe option, guaranteeing that individual preferences will be learned yet also exploiting similarities between users.

Figure 7 shows results on the ECML/PKDD 2006 Discovery Challenge Spam detection dataset. We see that for this data set global outperforms individual, especially early in learning, indicating that there is a significant benefit from generalization across users in this domain. We also see here that balanced behaves similarly to global, but does outperform it by a small margin, especially later in the learning curve. This again shows that balanced is a robust approach for taking advantage of generalization opportunities.

7 Conclusions

In this paper, we presented and evaluated algorithms for multitask co-active learning. One of the main contributions is the MCL algorithm, which is the first coactive learning algorithm that can both take advantage of generalization opportunities across experts, and guarantee convergence to zero average cost. A theoretical bound was derived to show that it will eventually converge to predictions which are tailored to the specific experts or tasks.

Our empirical results show that MCL is able to strike a balance between generality and specificity. Both balanced and global (which ignores expert identifiers and treats them all as 1 expert) have a large drop in average cost over the first few examples, where individual (an algorithm which does not generalize over users) cannot share experience between users, and needs to have a larger amount of data per user to improve. On the other hand, global stops improving after just a handful of examples. It does not converge to an optimal solution, since it cannot learn any specific differences between different experts or tasks. The individual and balanced algorithms do not have this problem and eventually converge to optimal weight vectors for each expert.

When encountering a novel problem where it is not known to what extent different tasks or experts can be expected to share utility functions, choosing either the individual or global algorithms might be dangerous. Since balanced combines the strengths of both, and has performance close to the best of either in any given situation, it presents a safe choice.

Acknowledgements

The authors acknowledge support of the ONR ATL program N00014-11-1-0106.