Efficient Bayesian Task-Level Transfer Learning

1 Introduction

In machine learning, we are often confronted with multiple, related data sets and asked to make predictions. For example, in spam filtering, a typical data set consists of thousands of labeled emails belonging to a collection of users. In this sense, we have multiple data sets-one for each user. Should we combine the data sets and ignore the prior knowledge that different users labeled each email? If we combine the data from a group of users who roughly agree on the definition of spam, we will have increased the available training data from which to make predictions. However, if the preferences within a population of users are heterogeneous, then we should expect that simply collapsing the data into an undifferentiated collection will make our predictions worse.

The process of using data from unrelated or partially related tasks is known as transfer learning or multi-task learning and has a growing literature (Baxter, 2000; Guestrin et al., 2003; Thrun, 1996; Xue et al., 2005). While humans effortlessly use experience from related tasks to improve their performance at novel tasks, machines must be given precise instructions on how to make such connections. In this paper, we introduce such a set of instructions, based on the statistical assumption that there exists some partition of the tasks into clusters such that the data for all tasks in a cluster are identically distributed. Ultimately, any such model of sharing must be evaluated on real data, and, to that end, we evaluate the resulting model in a meeting domain. The learned system decides, based on training data for a user, whether to accept or reject the request on his or her behalf. The model that shares data outperforms its no-sharing counterpart by using data from other users to influence its predictions.

When faced with a classification task on a single data set, well-studied techniques abound (Boser et al., 1992; Lafferty et al., 2001). A popular classifier that works well in practice, despite its simplicity, is the Naive Bayes classifier (Maron, 1961). We can extend this classifier to the multi-task setting by training one classifier for each cluster in the latent partition. To handle uncertainty in the number of clusters and their membership, we define a generative process for data sets that induces clustering. At the heart of this process is a non-parametric prior known as the Dirichlet Process. This prior couples the parameters of the Naive Bayes classifiers attached to each data set. This approach extends the applicability of the Naive Bayes classifier to the domain of multi-task learning when the tasks are defined over the same input space.

Bayesian inference under this clustered Naive Bayes model combines the contribution of every partition of the data sets, weighing each by the partition's posterior probability. However, the sum over partitions is intractable and, therefore, we employ recent work by Heller and Ghahramani (2005a) to implement an approximate inference algorithm. The result is efficient, task-level transfer learning.

2 Models

In this paper, we concentrate on classification settings where the features Xf , f = 1, . . . , F and labels Y are drawn from finite sets Vf ,L, respectively. Our goal is to learn the relationship between the input features and output labels in order to predict a label given an unseen combination of features.

Consider U tasks, each with Nu training examples composed of a label Y and a feature vector X. To make the discussion more concrete, assume each task is associated with a different user performing some common task. Therefore, we will write D(u) to represent the feature vectors X (u,i) and corresponding labels Y (u,i) , i = 1, . . . ,Nu, associated with the u-th user. Then D is the entire collection of data across all users, and D(u,j) = (X (u,j) , Y (u,j) ) is the j-th data point for the u-th user.

Let mu,y denote the number of data points labeled y ∈ L in the data set associated with the u-th user and let nu,y,f,x denote the number of instances in the u-th data set where the f -th feature takes the value x ∈ Vf when its parent label takes value y ∈ L. Let θu,y,f,x ≜ P(X (u) f = x | Y (u) = y), and φu,y ≜ P(Y (u) = y). We can now write the general form of the probability mass function of the data conditioned on the parameters θ and φ of the Naive Bayes model:

In (a), p(D|θ, φ) is expanded into a product of terms, one for each data set, reflecting that the data sets are independent conditioned on the parameterization. Step (b) assumes the data points are exchangeable; in particular, the label/feature pairs are independent of one another given the parameterization. In step (c), we have made use of the Naive Bayes assumption that the features are conditionally independent given the label. Finally, in step (d), we have used the fact that the distributions are multinomials. The maximum likelihood parameterizations are

Because each data set is parameterized separately, it is no surprise that the maximum likelihood parameterization for each data set depends only on the data in that data set. In order to induce sharing, we must somehow constrain the parameterization across users. In the Bayesian setting, the prior distribution F (θ, φ) can be used to enforce such constraints. Given a prior, the resulting joint distribution on the data is

Both models introduced in this section are completely specified by a prior distribution over the parameters of the Naive Bayes model. As we will see, different priors result in different types of sharing.

2.1 No-Sharing Baseline Model

We have already seen that a ML parameterization of the Naive Bayes model ignores related data sets. In the Bayesian setting, any prior density f over the entire set of parameters that factors into densities for each user's parameters will result in no sharing. In particular,

is equivalent to the statement that the parameters for each user are independent of the parameters for other users. Under this assumption of independence, training the entire collection of models is identical to training each model separately on its own data set. We therefore call this model the no-sharing model.

Having specified that the prior factors into parameter distributions for each user, we must specify the actual parameter distributions for each user. A reasonable (and tractable) class of distributions over multinomial parameters are the Dirichlet distributions which are conjugate to the multinomials. Therefore, the distribution over φu, which takes values in the |L|- simplex, is

Similarly, the distribution over θu,y,f , which takes values in |Vf |-simplex, is

We can write the resulting model compactly as a generative process: 1

The No-Sharing model will function as a baseline against which we can compare alternative models that induce sharing. We turn now to specifying a model that induces sharing.

1 The ∼ symbol denotes that the variable to the left is distributed according to the distribution specified on the right. It should be noted that the Dirichlet distribution requires an ordered set of parameters. We therefore define an arbitrary ordering of the elements of L, Vf .

2.2 The Clustered Naive Bayes Model

A plausible assumption about a collection of related data sets is that they can be clustered into closely-related groups. To make this more precise, we will consider two tasks t1 and t2 over some space X × Y to be related if the data associated with both tasks are identically distributed. While this is a very coarse model of relatedness, it leads to improved predictive performance with limited training data.

As a first step we must specify a distribution over partitions of tasks. There are several properties we would like this distribution to have: first, we want exchangeability of tasks (users); e.g., the probability should not depend on the ordering (i.e. identity) of the tasks (users); second, we want exchangeability of clusters; e.g., the probability should not depend on the ordering/naming of the clusters; finally, we want consistency; e.g., a priori, the (hypothetical) existence of an unobserved task should not affect the probability that any group of tasks are clustered together.

The Chinese Restaurant Process (CRP) is a stochastic process that induces a distribution over partitions that satisfies all these requirements (Aldous, 1985). The following metaphor was used to define the process: imagine a restaurant with a countably infinite number of indistinguishable tables. The first customer sits at an arbitrary empty table. Subsequent customers sit at an occupied table with probability proportional to the number of customers already seated at that table and sit at an arbitrary, new table with probability proportional to a parameter α > 0. The resulting "seating chart" partitions the customers. It can be shown that, in expectation, the number of occupied tables after n customers is Θ(log n) (Antoniak, 1974; Navarro et al., 2006).

The tasks within each cluster of the partition will share the same parameterization. Extending our generative model, imagine that when a new user enters the restaurant and sits at a new table, they draw a complete parameterization of their Naive Bayes model from some base distribution. This parameterization is then associated with their table. If a user sits at an occupied table, they adopt the parameterization already associated with the table. Therefore, everyone at the same table uses the same rules for predicting.

This generative process corresponds with the well known Dirichlet Process mixture model (DPM) and has been used very successfully to model latent groups (Ferguson, 1973). The underlying Dirichlet process has two parameters, a mixing parameter α, which corresponds to the same parameter of the CRP, and a base distribution, from which the parameters are drawn at each new table. It is important to specify that we draw a complete parameterization of all the feature distributions, θy,f , at each table. We have decided not to share the marginal distributions, φ, because we are most interested in knowledge relating the features and labels.

Again, we can represent the model compactly by specifying the generative process:

f The discrete measure G is a draw from the Dirichlet Process; in practice, this random variable is marginalized over. Because the tasks are being clustered, we have named this model the Clustered Naive Bayes model (and denote its distribution function over the parameters as FCNB). We now explain how to use the model to make predictions given training data.

3 Approximate Inference

Given labelled training data D(u) = {Y (u,i) , X (u,i)}1≤i≤Nu for all tasks u ∈ {1, 2, . . . , U} and an unlabeled feature vector X ∗ ≜ X (v,Nv+1) for some task v, we would like to compute the posterior distribution of its label Y ∗ ≜ Y (v,Nv+1) . Using Bayes rule, and ignoring normalization constants,

where D′ is the data set where we imagine that the (v,Nv + 1)-th data point has label y. Therefore, Bayesian inference requires that we marginalize over the parameters, including the latent partitions of the Dirichlet process. Having chosen conjugate priors, the base distribution can be analytically marginalized. However, the sum over all partitions makes exact inference under the Dirichlet Process mixture model intractable. While Markov Chain Monte Carlo and variational techniques are the most popular approaches, this paper uses a simple, recently-proposed approximation to the DPM known as Bayesian Hierarchical Clustering (BHC) (Heller and Ghahramani, 2005a), which approximates the sum over all partitions by first greedily generating a hierarchical clustering of the tasks and then efficiently summing over the exponential number of partitions "consistent" with this hierarchy. This approach leads to a simple, yet efficient, algorithm for achieving task-level transfer.

Consider a rooted binary tree T where each task is associated with a leaf. It will be convenient to identify each internal node, Tn, with the set of leaves descending from that node. A tree-consistent partition of the tasks is any partition such that each subset corresponds exactly with a node in the graph (Figure 2). It can seen that, given any rooted tree over more than two objects, the set of all tree-consistent partitions is a strict subset of the set of all partitions. Exact inference under the DPM requires that we marginalize over the latent partition, requiring a sum over the super-exponential number of partitions. The BHC approximation works by efficiently computing the sum over the exponential number of tree-consistent partitions, using a divide-and-conquer approach to combine the results from each subtree. Intuitively, if the tree is chosen carefully, then the set of tree-consistent partitions will capture most of the mass in the posterior. BHC tries to find such a tree by combining Bayesian model selection with a greedy heuristic.

Just as in classic, agglomerative clustering (Duda et al., 2001), BHC starts with all objects assigned to their own cluster and then merges these clusters one by one, implicitly forming a tree that records which merges were performed. However, instead of using a distance metric and merging the nearest clusters, BHC merges the two clusters that maximize a statistical hypothesis test. At each step, the algorithmmust determine which pair in the set of clusters T1, T2, . . . , Tm to merge next. Consider two particular clusters Ti and Tj and let Di and Dj be the set of tasks in each respectively. The BHC algorithm calculates the posterior probability that these two clusters are in fact a single cluster Tk = Ti + Tj. Specifically, the hypothesis Hk is that the data in Dk = Di ∪ Dj are identically distributed with respect to the base model (in this case, some Naive Bayes model). The probability of the data in this new cluster under Hk, p(Dk|Hk) is simply the marginal likelihood of the data.

The alternative hypothesis, ¯Hk is that the data Di and Dj are, in fact, split into two or more clusters. Computing the probability associated with this hypothesis would normally require a sum over the super-exponential number of partitions associated with the tasks in Di and Dj. However, the clever trick of the BHC algorithm is to restrict its attention to treeconsistent partitions. Therefore, the probability of the data Dk = Di ∪Dj under ¯Hk, p(Dk| ¯Hk) = p(Di|Ti) p(Dj |Tj ), where p(Di|Ti) is the probability of the data associated with the tree Ti. Let πk = p(Hk) be the prior probability of the cluster Tk. Then, we can write p(Dk|Tk) recursively

Then the posterior probability of Hk is

We now present the BHC algorithm, whose output is sufficient for approximate Bayesian predictions under our model.

model p(X|Y, θ) and prior density f (θ)

initialize number of clusters c=n, and

Find the pair Di and Dj with the highest posterior probability of Hk where Tk = Ti + Tj .

end while Heller and Ghahramani (2005a) show that a specific choice of the prior πk = p(Hk) leads to an approximate inference scheme for the DPM. Let α be the corresponding parameter from the DPM. Then, we can calculate the prior probability for each cluster Tj in the tree built by BHC.

end for

Having built a tree that approximates the posterior distribution over partitions, we can use the tree to compute the posterior probability of an unseen label. Assume we have an unlabeled example Xk associated with the k-th task. Let Ak be the set of nodes along the path from the node k to the root in the tree generated by the BHC algorithm (e.g. in Figure 2, A5 = {5, 7, 8, 9}). Note that the elements Ti ∈ Ak correspond to all clusters that task k participates in across all treeconsistent partitions. Our predictive distribution for Y will then be the weighted average of the predictive distributions for each partition:

where wk = rk ∏i∈Ak/{k} (1 - ri) and p(Yk|Xk,Dk) is the predictive distribution under the base model after combining the data from all the tasks in cluster k.

While the computational complexity of posterior computation is quadratic in the number of tasks, Heller and Ghahramani (2005b) have proposed O(n log n) and O(n) randomized variants.

4 Results

The utility of the type of sharing that the Clustered Naive Bayes supports can only be assessed on real data sets. To that end, we evaluated the model's predictions on a meeting classification data set collected by Rosenstein et al. (2005). The data set is split across 21 users frommultiple universities, an industry lab and a military training exercise. In total, there are 3966 labeled meeting requests, with 100-400 meeting requests per user. In the meeting acceptance task, we aim to predict whether a user would accept or reject an unseen meeting request based on a small set of features that describe various aspects of the meeting.

To evaluate the clustered model, we assessed its predictive performance in a transfer learning setting, predicting labels for a user with sparse data, having observed all the labeled data for the remaining users. In particular, we calculated the receiver-operator characteristic (ROC) curve having trained on 1,2,4,8,16,32,64, and 128 training examples for each user (conditioned on knowledge of all labels for the remaining users). Each curve was generated according to results from twenty random partitions of the users' data into training and testing sets. Figure 3 plots the area under the ROC curve as a measure of classification performance versus the number of training examples.

From the 21 users, we have selected five representative samples. The first three examples (users 1, 3 and 20) show how the model performs when it is able to use related user's data to make predictions. With a single labeled data point, the model groups user 1 with two other military personnel (users 5 and 8). While at each step the model makes predictions by averaging over all tree-consistent partitions, the MAP partition listed in the figure has the largest contribution. For user 1, the MAP partition changes at each step, providing superior predictive performance. However, for the third user in the second figure, the model chooses and sticks with the MAP partition that groups the first and third user. In the third example, User 20 is grouped with user 9 initially, and then again later on. Roughly one third of the users witnessed improved initial performance that tapered off as the number of examples grew.

The fourth example (user 17) illustrates that, in some cases, the initial performance for a user with very few samples is not improved because there are no good candidate related users with which to cluster. Finally, the last example shows one of the four cases where predictions using the clustered model leads to worse performance. In this specific case, the model groups the user 7 with user 1. It is not until 128 samples that the model recovers from this mistake and achieves equal performance.

Figure 4 shows the trees and corresponding partitions recovered by the BHC algorithm as the number of training examples for each user is increased. Inspecting the partitions, they fall along understandable lines; military personnel are most often grouped with other military personnel, and professors and SRI researchers are grouped together until there is enough data to warrant splitting them apart.

Figure 5 shows the relative performance of the clustered versus standard Naive Bayes model. The clustered variant outperforms the standard model when faced with very few examples. After 32 examples, the models perform roughly equivalently, although the standard model enjoys a slight advantage that does not grow with more examples.

5 RelatedWork

Some of the earliest work related to transfer learning focused on sequential transfer in neural networks, using weights from networks trained on related data to bias the learning of networks on novel tasks (Caruana, 1997; Pratt, 1993). More recently, these ideas have been applied to modern supervised learning algorithms, like support vector machines (Wu and Dietterich, 2004). More work must be done to understand the connection between these approaches and the kind of sharing one can expect from the Clustered Naive Bayes model.

This work is related to a large body of transfer learning research conducted in the hierarchical Bayesian framework, in which common prior distributions are used to tie together model components across multiple data sets. The clustered model can be seen as an extension of the model first presented by Rosenstein et al. (2005) for achieving transfer with the Naive Bayes model. In that work, they fit a Dirichlet distribution for each shared parameter across all users. Unfortunately, because the Dirichlet distribution cannot fit arbitrary bimodal distributions, the model cannot handle more than one cluster, i.e. each parameter is shared completely on not at all. The model presented in this paper can handle any number of users by modelling the density over parameters using a Dirichlet Process prior. It is possible to loosely interpret the resulting Clustered Naive Bayes model as grouping tasks based on a marginal likelihood metric. From this viewpoint, this work is related to transfer-learning research which aims to first determine which tasks are relevant before attempting transfer (Thrun and O'Sullivan, 1996).

Ferguson (1973) was the first to study the Dirichlet Process and show that it can, simply speaking, model any other distribution arbitrarily closely. The Dirichlet Process has been successfully applied to generative models of documents (Blei et al., 2004), genes (Dahl, 2003), and visual scenes (Sudderth et al., 2005). Teh et al. (2006) introduced the Hierarchical Dirichlet Process, which achieves transfer in document modeling across multiple corpora. The work closest in spirit to this paper was presented recently by Xue et al. (2005). They investigate coupling the parameters of multiple logistic regression models together using the Dirichlet Process prior and derive a variational method for performing inference. In the same way, the Clustered Naive Bayes model we introduce uses a Dirichlet Process prior to tie the parameters of several Naive Bayes models together for the purpose of transfer learning. There are several important differences: first, the logistic regression model is discriminative, meaning that it does not model the distribution of the inputs. Instead, it only models the distribution of the output labels conditioned on the inputs. As a result, it cannot take advantage of unlabeled data. Second, in the Clustered Naive Bayes model, the data sets are clustered with respect to a generative model which defines a probability distribution over both the inputs. As a result, the Clustered Naive Bayes model could be used in a semi-supervised setting. Implicit in this choice is the assumption that similar feature distributions are associated with similar predictive distributions. This assumption must be judged for each task: for the meeting acceptance task, the generative model of sharing is appropriate and leads to improved results.

6 Conclusion

The central goal of this paper was to evaluate the Clustered Naive Bayes model in a transfer-learning setting. To evaluate the model, we measured its performance on a real-world meeting acceptance task, and showed that the clustered model can use related users' data to provide better prediction even with very few examples.

The Clustered Naive Bayes model uses a Dirichlet Process prior to couple the parameters of several models applied to separate tasks. This approach is immediately applicable to any collection of tasks whose data are modelled by the same parameterized family of distributions, whether those models are generative or discriminative. This paper suggests that clustering parameters with the Dirichlet Process is worthwhile and can improve prediction performance in situations where we are presented with multiple, related tasks. A theoretical question that deserves attention is whether we can get improved generalization bounds using this technique. A logical next step is to investigate this model of sharing on more sophisticated base models and to relax the assumption that users are exactly identical.