multi-Task Feature Learning: Difference between revisions
Line 145: | Line 145: | ||
* The performance of the authors' algorithm is moderate for low-dimensionality data, but it increases as the number of irrelevant dimensions increases. | * The performance of the authors' algorithm is moderate for low-dimensionality data, but it increases as the number of irrelevant dimensions increases. | ||
==Conjoint analysis experiment== | |||
NOT DONE YET. PLEASE DO NOT CONTRIBUTE. THANKS. | NOT DONE YET. PLEASE DO NOT CONTRIBUTE. THANKS. |
Revision as of 18:03, 28 November 2010
Introduction
It has been both empirically as well as theoretically shown that learning multiple related tasks simultaneously often significantly improves performance as compared to learning each task independently. Learning multiple related tasks simultaneously is especially beneficial when we only have a few data per task; and this benefit comes from pooling together data across many related tasks. One way that tasks can be related to each other is that some tasks share a common underlying representation; for example, people make product choices (e.g. of books, music CDs, etc.) using a common set of features describing these products. In this paper, the authors explored a way to learn a low-dimensional representation this is shared across multiple related tasks.
Learning sparse multi-task representations
Notations
Let [math]\displaystyle{ \,R }[/math] be the set of real numbers and [math]\displaystyle{ \,R_{+} (R_{++}) }[/math] the non-negative ones. Let T be the number of tasks and let the tasks as [math]\displaystyle{ \,N_T := {1,\dots,T} }[/math]. For each task [math]\displaystyle{ \,t \in N_T }[/math], we have [math]\displaystyle{ \,m }[/math] input/output examples [math]\displaystyle{ \,(x_{t1}; y_{t1}),\dots,(x_{tm}; y_{tm}) \in R^d \times R }[/math]. The goal is then to estimate [math]\displaystyle{ \,T }[/math] functions [math]\displaystyle{ \,f_t : R^d \mapsto R, t \in N_T }[/math], that approximate well the training data and are also statistically predictive for new data.
If [math]\displaystyle{ \,w, u \in R^d }[/math], [math]\displaystyle{ \,\lt w, u\gt \; := \sum_{i=1}^d w_i u_i }[/math] is their standard inner product in [math]\displaystyle{ \,R^d }[/math]. For every [math]\displaystyle{ \,p \ge 1 }[/math], [math]\displaystyle{ \,||w||_p \; := \; (\sum_{i=1}^d |w_i|^p)^\frac{1}{p} }[/math] is the [math]\displaystyle{ \,p }[/math]-norm of vector [math]\displaystyle{ \,w }[/math]. If [math]\displaystyle{ \,A }[/math] is a [math]\displaystyle{ \,d \times T }[/math] matrix, then [math]\displaystyle{ \,a^i \in R^T }[/math] and [math]\displaystyle{ \,a_j \in R^d }[/math] are the [math]\displaystyle{ \,i }[/math]th row and the [math]\displaystyle{ \,j }[/math]th column of [math]\displaystyle{ \,A }[/math], respectively. For every [math]\displaystyle{ \,r, \; p \ge 1 }[/math], [math]\displaystyle{ \,||A||_{r,p} := (\sum_{i=1}^d ||a^i||_r^p)^\frac{1}{p} }[/math] is the [math]\displaystyle{ \,(r,p) }[/math] -norm of [math]\displaystyle{ \,A }[/math].
[math]\displaystyle{ \,S^d }[/math] is the set of [math]\displaystyle{ \,d \times d }[/math] real symmetric matrices and [math]\displaystyle{ \,S_{+}^d }[/math] is the subset of positive semidefinite ones. If [math]\displaystyle{ \,D }[/math] is a [math]\displaystyle{ \,d \times d }[/math] matrix, then trace([math]\displaystyle{ \,D }[/math]) [math]\displaystyle{ \; :=\sum_{i=1}^d D_{ii} }[/math]. If [math]\displaystyle{ \,X }[/math] is a [math]\displaystyle{ \,p \times q }[/math] real matrix, then range([math]\displaystyle{ \,X }[/math]) is the set [math]\displaystyle{ \,\{x \in R^p \; : \; x = Xz }[/math], for some [math]\displaystyle{ \,z \in R^q\} }[/math]. [math]\displaystyle{ \,O^d }[/math] is the set of [math]\displaystyle{ \,d \times d }[/math] orthogonal matrices. [math]\displaystyle{ \,D^+ }[/math] is the pseudoinverse of a matrix [math]\displaystyle{ \,D }[/math].
Problem formulation
It is assumed that the functions [math]\displaystyle{ \,f_t }[/math] are related to each other, so they all share a small set of features. Formally, the hypothesis is that the functions [math]\displaystyle{ \,f_t }[/math] can be expressed as: [math]\displaystyle{ \, f_t(x) = \sum_{i=1}^d a_{it}h_i(x), \;\; t \in N_T \;\;\; (2.1) }[/math]
In [math]\displaystyle{ \,(1) }[/math], [math]\displaystyle{ \,h_i : R^d \mapsto R }[/math] are the features and [math]\displaystyle{ \,a_{it} \in R }[/math] are the regression parameters.
The main assumption is that the vast majority of the features have zero coefficients across all the tasks.
For simplicity, the authors focused on linear features, i.e. [math]\displaystyle{ \,h_i(x) = \lt u_i, x\gt }[/math], where [math]\displaystyle{ \,u_i \in R^d }[/math] and [math]\displaystyle{ \,u_i }[/math] are assumed to be orthonormal. They noted that extensions to non-linear functions may be done, for example, by using kernels; however, they did not focus on these extensions in their paper. Furthermore, the functions [math]\displaystyle{ \,f_t }[/math] are also linear, i.e. [math]\displaystyle{ \,f_t(x) = \lt w_t, x\gt }[/math], where [math]\displaystyle{ \, w_t = \Sigma_i \;a_{it} u_i }[/math].
[math]\displaystyle{ \,W }[/math] the [math]\displaystyle{ \,d \times T }[/math] matrix whose columns are the vectors [math]\displaystyle{ \,w_t }[/math]. [math]\displaystyle{ \,A }[/math] the [math]\displaystyle{ \,d \times T }[/math] matrix whose elements are the [math]\displaystyle{ \,a_{it} }[/math]. The authors then obtained that [math]\displaystyle{ \,W = UA }[/math].
The assumption that the tasks share a small set of features implies that [math]\displaystyle{ \,A }[/math] has many rows which are identically equal to zero. This, in turn, implies that the corresponding features, which are the columns of [math]\displaystyle{ \,U }[/math], will not be used to represent the task parameters, which are the columns of [math]\displaystyle{ \,W }[/math]. [math]\displaystyle{ \,W }[/math], thus, is a low-rank matrix.
The authors' goal was to find the feature vectors [math]\displaystyle{ \,u_i }[/math] and the parameters [math]\displaystyle{ \,a_{it} }[/math].
As a starting point, the authors considered the problem in which there is only one task (referred to as task [math]\displaystyle{ \,t }[/math]) and the features [math]\displaystyle{ \,u_i }[/math] are fixed. In this problem, the aim was to learn the parameter vector [math]\displaystyle{ \,a_t \in R^d }[/math] from data [math]\displaystyle{ \,\{(x_{ti}, y_{ti})\}_{i=1}^m }[/math]. The authors expressed this unconstrained problem as:
In [math]\displaystyle{ \,(2) }[/math], [math]\displaystyle{ \,\gamma \gt 0 }[/math] is the regularization parameter.
It is well-known that using the 1-norm regularization results in a sparse solution to [math]\displaystyle{ \,(2) }[/math], i.e. many elements of the learned [math]\displaystyle{ \,a_t }[/math] are zero.
Before generalizing [math]\displaystyle{ \,(2) }[/math] to the multi-task case, the authors introduced the following regularization error function:
In [math]\displaystyle{ \,(3) }[/math], the first term is the average empirical error across the tasks, and the second term is a regularization term that penalizes the [math]\displaystyle{ \,(2, 1) }[/math] -norm of [math]\displaystyle{ \,A }[/math].
However, since the authors did not simply want to select the features, but rather they also wanted to learn them, they further minimized the function [math]\displaystyle{ \,\Epsilon\gt }[/math] over [math]\displaystyle{ \,U }[/math], i.e. they considered the following optimization problem:
Solving [math]\displaystyle{ \,(4) }[/math] results in learning a low-dimensional representation which is shared across the tasks.
In addition, when [math]\displaystyle{ \,U }[/math] is not learned and is set to [math]\displaystyle{ \,I_{d \times d} }[/math], solving [math]\displaystyle{ \,(4) }[/math] finds a common set of variables across the tasks. Under this condition for [math]\displaystyle{ \,U }[/math], [math]\displaystyle{ \,(4) }[/math] can be re-expressed as the following convex optimization problem:
Equivalent convex optimization formulation
[math]\displaystyle{ \,(2.4) }[/math] is difficult to solve due to the following two reasons:
- It is not convex ( although it is separately convex in each of [math]\displaystyle{ \,\{A, U\} }[/math] ).
- [math]\displaystyle{ \,||A||_{2,1} }[/math] is not smooth.
However, [math]\displaystyle{ \,(2.4) }[/math] can be re-expressed as an equivalent convex problem. Before doing so, for every [math]\displaystyle{ \,W \in \mathbb{R}^{d \times T} and \lt math\gt \,D \in S_+^d }[/math], the authors defined the following function:
Theorem 3.1 (a detailed proof is given in the authors' paper listed in Reference) states that [math]\displaystyle{ \,(2.4) }[/math] is equivalent to the following problem:
The rank of [math]\displaystyle{ \,D }[/math] gives the number of common relevant features shared by the tasks.
By defining the function [math]\displaystyle{ \,f(w,D) = \left\{\begin{matrix} {w^TD^+w} &\text{, if } D \in S_+^d \; and \; w \in range(D) \\ +\infty &\text{, if otherwise } \end{matrix}\right. }[/math], the authors showed (details are available in the authors' paper listed in Reference) that the function [math]\displaystyle{ \,R }[/math] in [math]\displaystyle{ \,(3.1) }[/math] is jointly convex in both [math]\displaystyle{ \,W }[/math] and [math]\displaystyle{ \,D }[/math].
Learning algorithm
The authors solved [math]\displaystyle{ \,(3.2) }[/math] by alternately minimizing the function [math]\displaystyle{ \,R }[/math] with respect to [math]\displaystyle{ \,D }[/math] and the [math]\displaystyle{ \,w_t }[/math] ( (the [math]\displaystyle{ \,t }[/math]-th column of [math]\displaystyle{ \,W }[/math]).
When [math]\displaystyle{ \,D }[/math] was held fixed, [math]\displaystyle{ \,w_t }[/math] was minimized by learning its parameters independently by a regularization method such as an SVM. When [math]\displaystyle{ \,w_t }[/math] was held fixed, [math]\displaystyle{ \,D }[/math] was learned by solving the following optimization problem:
Theorem 4.1 (whose proof is given in the authors' paper listed in Reference) states that the optimal solution of [math]\displaystyle{ \,(4.1) }[/math] is [math]\displaystyle{ \,D = \frac {(WW^T)^\frac{1}{2}} {trace(WW^T)^\frac{1}{2}} \;\;\; (4.2) }[/math] .
In their paper, the authors' referred to their algorithm for multi-task feature learning as Algorithm 1, which is reproduced below for your convenience:
In [math]\displaystyle{ \,(4.2) }[/math], [math]\displaystyle{ \,trace(WW^T)^\frac{1}{2} }[/math] is the sum of the singular values of [math]\displaystyle{ \,W }[/math], and thus it is sometimes called the trace norm (this work by Jason D. M. Rennie provides how the trace norm of a matrix can be expressed in a number of different ways). Using the trace norm, [math]\displaystyle{ \,(3.2) }[/math] is reduced to a regularization problem that depends only on [math]\displaystyle{ \,W }[/math]. However, the trace norm is not smooth. As a result, the authors cited that their algorithm (Algorithm 1) that uses an alternating minimization strategy is beneficial in that it is:
- simple to implement
- has a natural interpretation
The authors further noted that Algorithm 1 alternately performs a supervised step and an unsupervised step; in the unsupervised step, common representations across the tasks are learned and, in the supervised step, task-specific functions are learned using these representations.
The authors further noted that if [math]\displaystyle{ \,D }[/math] in [math]\displaystyle{ \,(3.2) }[/math] is additionally constrained to be diagonal, then [math]\displaystyle{ \,(3.2) }[/math] reduces to [math]\displaystyle{ \,(2.5) }[/math].
Experiments
The authors performed their experiments on a synthetic data set and a real data set, and they used the square loss function and tuned the regularization parameter using leave-one-out cross validation.
Synthetic Experiments
Details regarding the authors' synthetic data can be found in the paper listed in Reference.
The following figure (taken from the authors' paper listed in Reference) shows the performance of the authors' algorithm for [math]\displaystyle{ \,T = }[/math] 10, 25, 100, and 200 tasks and the performance of 200 independent standard ridge regressions on the data:
As is also demonstrated by past empirical and theoretical works, the authors' experiment on synthetic data demonstrated that learning multiple
tasks together results in significant improvements over learning the tasks independently. Furthermore, this experiment demonstrated the following two key points:
- The performance of the authors' algorithm improves as the number of tasks increases, i.e. adding more tasks results in better estimates of the underlying features.
- The performance of the authors' algorithm is moderate for low-dimensionality data, but it increases as the number of irrelevant dimensions increases.
Conjoint analysis experiment
NOT DONE YET. PLEASE DO NOT CONTRIBUTE. THANKS.