From Wiki Course Notes

Revision as of 02:09, 23 December 2010 by Laleh Ghoraie (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

1 Introduction
2 Learning sparse multi-task representations
- 2.1 Notation
- 2.2 Problem formulation
3 Equivalent convex optimization formulation
4 Learning algorithm
- 4.1 Algorithm 1: Multi-Task Feature Learning
5 Experiments
- 5.1 Synthetic Experiments
- 5.2 Conjoint analysis experiment
6 Conclusion
7 Reference

Introduction

Imagine that a user wishes to perform some task, such as shopping for a book. If the user does not have much experience shopping for books, he or she may draw upon his or her knowledge of shopping for some other product, like music CDs. The tasks are not exactly the same, but there are similarities. The user may recognize that books are made by authors, music by artists. Both have different genres, and perhaps appeal to different demographics.

Multi-task feature learning aims to model this paradigm. Statistically, we wonder if there is some common set of features a user may apply in order to do some abstract task (returning to the example, the common task is shopping). And, specifically, can we learn multiple related tasks simultaneously, as opposed to independently?

Multi-task feature learning is especially relevant to situations where the number of observations may be small. This creates a need for finding shared structures between the tasks, so that observations can be aggregated to learn many tasks simultaneously. The search for these shared structures can be seen as a dimensionality reduction, or alternatively a regularization, problem.

The authors generalize the idea of 1-norm regularization that presents a low dimensional representation of a single task to learn the shared representation across multiple tasks. Regularization parameter controls the number of learned common features. They present an equivalent convex optimization problem to their original formulation, and propose an algorithm to solve this problem.

The learning part of the algorithm simultaneously learns both the features and the task functions through two alternating steps. The first step which is supervised includes independently learning the parameters of the tasks regression or classification functions. In the second step, which is unsupervised, a low-dimensional representation for these task parameters is found, which the authors show is equivalent to learning common features across the tasks.

Learning sparse multi-task representations

Notation

For simplicity, we will first define the following notation:

Let $\,R$ be the set of real numbers, $\,R_{+}$ the non-negative ones and $\,R_{++}$ the positive ones.
Let $\,T$ be the number of tasks and let the set of tasks be $\,N_T := {1,\dots,T}$ .
For each task $\,t \in N_T$ , we have $\,m$ input/output examples $\,(x_{t1}, y_{t1}),\dots ,(x_{tm}, y_{tm}) \in R^d \times R$ .
The goal is then to estimate $\,T$ functions $\,f_t : R^d \mapsto R, t \in N_T$ , that approximate the training data well and are also statistically predictive for new data.
If $\,w, u \in R^d$ , $\,<w, u> \; := \sum_{i=1}^d w_i u_i$ is their standard inner product in $\,R^d$ .
For every $\,p \ge 1$ , $\,||w||_p \; := \; (\sum_{i=1}^d |w_i|^p)^\frac{1}{p}$ is the $\,p$ -norm of vector $\,w$ .
If $\,A$ is a $\,d \times T$ matrix, then $\,a^i \in R^T$ and $\,a_j \in R^d$ are the $\,i$ th row and the $\,j$ th column of $\,A$ , respectively.
For every $\,r, \; p \ge 1$ , $\,||A||_{r,p} := (\sum_{i=1}^d ||a^i||_r^p)^\frac{1}{p}$ is the $\,(r,p)$ -norm of $\,A$ .
$\,S^d$ is the set of $\,d \times d$ real symmetric matrices and $\,S_{+}^d$ is the subset of positive semidefinite ones.
If $\,D$ is a $\,d \times d$ matrix, then $\,tr(D):=\sum_{i=1}^d D_{ii}$ .
If $\,X$ is a $\,p \times q$ real matrix, then range( $\,X$ ) is the set $\,\{x \in R^p \; : \; x = Xz$ , for some $\,z \in R^q\}$ .
$\,O^d$ is the set of $\,d \times d$ orthogonal matrices.
$\,D^+$ is the pseudoinverse of a matrix $\,D$ .

Problem formulation

It is assumed that the functions $\,f_t$ are related to each other, so they all share a small set of features. Formally, the hypothesis is that the functions $\,f_t$ can be expressed as:

$\, f_t(x) = \sum_{i=1}^d a_{it}h_i(x), \;\; t \in N_T \;\;\; (1)$

In the above equation, $\,h_i : R^d \mapsto R$ are the features and $\,a_{it} \in R$ 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. $\,h_i(x) = <u_i, x>$ , where $\,u_i \in R^d$ and $\,u_i$ 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 $\,f_t$ are also linear, i.e. $\,f_t(x) = <w_t, x>$ , where $\, w_t = \Sigma_i \;a_{it} u_i$ .

$\,W$ is the $\,d \times T$ matrix whose columns are the vectors $\,w_t$ . $\,A$ is the $\,d \times T$ matrix whose elements are the $\,a_{it}$ . The authors then obtained that $\,W = UA$ where $U \in O^d$ .

The assumption that the tasks share a small set of features implies that $\,A$ has many rows which are identically equal to zero. This, in turn, implies that the corresponding features, which are the columns of $\,U$ , will not be used to represent the task parameters, which are the columns of $\,W$ . Thus, $\,W$ is a low-rank matrix.

The authors' goal was to find the feature vectors $\,u_i$ and the parameters $\,a_{it}$ .

As a starting point, the authors considered the problem in which there is only one task (referred to as task $\,t$ ) and the features $\,u_i$ are fixed. In this problem, the aim was to learn the parameter vector $\,a_t \in R^d$ from data $\,\{(x_{ti}, y_{ti})\}_{i=1}^m$ .

This unconstrained problem is expressed as:

$\, \min_{a_t} \; \{ \; \sum_{i=1}^m L(y_{ti}, <a_t,U^T x_{ti}>) + \gamma ||a_t||_1^2 \; : \; a_t \; \in \; R^d \; \} \;\;\; (2)$

In which, $\,\gamma > 0$ is the regularization parameter. The fact that using the 1-norm regularization results in a sparse solution to $\,(2)$ (i.e. many elements of the learned $\,a_t$ are zero) is well known.

To expand the problem to the multi-task case, the authors introduced the following regularization error function:

$\, \mathcal{E}(A,U) = \sum_{t=1}^T \sum_{i=1}^m L(y_{ti}, <a_t,U^T x_{ti}>) + \gamma ||A||_{2,1}^2 \;\;\; (3)$

The first term in $\,(3)$ is the average empirical error across the tasks, and the second term is a regularization term that penalizes the $\,(2, 1)$ -norm of $\,A$ . The $\,(2, 1)$ -norm of $\,A$ is computed by first computing the 2-norm of the rows of $\,A$ and then the 1-norm of the vector $\,b(A) = (\|a^1\|_2,\ldots,\|a^d\|_2)$ . The regularization term in $\,(3)$ ensures that $\,b(A)$ will likely be sparse and since each row of $\,A$ represents a feature this regularization limits the number of common features.

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 $\,\mathcal{E}$ over $\,U$ , i.e. they considered the following optimization problem:

$\,\min \; \{\; \mathcal{E}(A,U) \; : \; U \in O^d, A \in \mathbb{R}^{d \times T} \; \} \;\;\; (4)$

Solving the above optimization problem, results in learning a low-dimensional representation which is shared across the tasks.

In addition, when $\,U$ is not learned and is set to $\,I_{d \times d}$ , solving $\,(4)$ finds a common set of variables across the tasks. Under this condition for $\,U$ , $\,(4)$ can be re-expressed as the following convex optimization problem:

$\, \min \; \{\; \sum_{t=1}^T \sum_{i=1}^m L(y_{ti}, <a_t, x_{ti}>) + \gamma ||A||_{2,1}^2 \; : \; A \in \mathbb{R}^{d \times T} \; \} \;\;\; (5)$

Equivalent convex optimization formulation

Equation $\,4$ is difficult to solve due to the following two reasons:

It is not convex ( although it is separately convex in each of $\,\{A, U\}$ ).
$\,||A||_{2,1}$ is not smooth, which makes optimization more difficult.

However, $\,(4)$ can be re-expressed as an equivalent convex problem.

Before doing so, for every $\,W \in \mathbb{R}^{d \times T}$ and $\,D \in S_+^d$ , the authors defined the following function:

$\, R(W,D) = \sum_{t=1}^T \sum_{i=1}^m \; L(y_{ti} , <w_t,x_ti)>) + \gamma \sum_{t=1}^T \; <w_t,D^+w_t> \;\;\; (6)$

Theorem 3.1 (A detailed proof is given in the authors' paper listed in Reference) Problem $\,(4)$ is equivalent to the following problem:

$\, \min \; \{ \; R(W,D) \; : \; W \in \mathbb{R}^{d \times T}, \; D \in S_+^d, \; tr(D) \le 1, \; range(W) \subseteq range(D) \; \} \;\;\; (7)$

That is $(\hat{A},\hat(U))$ is an optimal solution for $\,(4)$ if and only if $(\hat{W},\hat{D}) = (\hat{U}\hat{A},\hat{U}\textrm{Diag}(\hat{\lambda})\hat{U}^T)$ is an optimal solution for $\,(7)$ , where

$\hat{\lambda} := \frac{\|a^i\|_2}{\|\hat{A}\|_{2,1}}.$

Since the rank of $\,D$ is determined by the number of nonzero eigenvalues, we can see from the above definition of $\hat{\lambda}$ that the rank of $\,D$ gives the number of common relevant features shared by the tasks.

By defining the function

$\,f(w,D) = \begin{cases} w^TD^+w &\text{if } w \in \textrm{range}(D) \;\; \textrm{and} \;\; D \in S_+^d , \\ +\infty &\text{otherwise } . \end{cases}$

and showing that it is jointly convex in both $\,W$ and $\,D$ the authors show (details are available in the authors' paper listed in the Reference section) that the function $\,R$ in $\,(6)$ is jointly convex in both $\,W$ and $\,D$ .

Learning algorithm

The authors solved $\,(7)$ by alternately minimizing the function $\,R$ with respect to $\,D$ and the $\,w_t$ ( (the $\,t$ -th column of $\,W$ ).

When $\,D$ is held fixed, $\,w_t$ is found by learning its parameters independently using a regularization method such as an SVM. When $\,w_t$ is held fixed, $\,D$ is found by solving the following optimization problem:

$\,\min \; \{ \; \sum_{t=1}^T \; <w_t , D^+ w_t> \; : \; D \in S_+^d, \; tr(D) \le 1, \; \textrm{range}(W) \subseteq \textrm{range}(D) \; \} \;\;\; (8)$

Theorem 4.1 (The proof is given in the authors' paper listed in the Reference section) The optimal solution of $\,(8)$ is $\,D = \frac {(WW^T)^\frac{1}{2}} {tr(WW^T)^\frac{1}{2}}. \;\;\; (9)$

Now, we have enough theory to describe an algorithm.

Algorithm 1: Multi-Task Feature Learning

Input: $\{x_{ti}, y_{ti}\}_{i=1}^m, t \in N_t$
Parameters: $γ$
Output $d \times d$ matrix $D$ and $d \times T$ matrix $W$
Initial Value: $D = \frac{I_d}{d}$
while convergence condition not met:
- for :
  - find $w_t = \arg\min \{\sum_{i=1}^m L(y_{ti} , <w_t,x_{ti})>) + \gamma <w_t,D^+w_t>$ with $w \in R^d$ and $w \in \textrm{range}(D)$
- end for
set $D = \frac{(WW^T)^{1/2}}{tr(WW^T)^{1/2}}$
end while

In $\,(9)$ , $\,tr(WW^T)^\frac{1}{2}$ is the sum of the singular values of $\,W$ , and thus it is sometimes called the trace norm (this work by Jason D. M. Rennie shows how the trace norm of a matrix can be expressed in a number of different ways). Using the trace norm, $\,(7)$ is reduced to a regularization problem that depends only on $\,W$ . However, the trace norm is not smooth. As a result, the authors argue 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 note 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 note that if $\,D$ in $\,(7)$ is additionally constrained to be diagonal, then $\,(7)$ reduces to $\,(5)$ .

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

The authors created synthetic data sets by generating $\,T$ = 200 task parameters $\,w_t$ from a $\,5$ -dimensional Gaussian distribution with zero mean and covariance equal to $\,Diag(1, 0.25, 0.1, 0.05, 0.01)$ . More 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 $\,T =$ 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

The authors then tested their method using a real data set that contained 180 persons' ratings regarding their propensities for purchasing one of 20 different personal computers. More details regarding this data can be found in the paper listed in Reference. In this data set, the people corresponded to tasks and the PC models corresponded to training instances.

The following figure (taken from the authors' paper listed in Reference) shows that the performance of the authors' algorithm improves as the number of tasks increases.

The authors also showed that their algorithm performs much better than independent ridge regressions.

The plot in the middle shows that there is a single most important feature that is shared by all people. This feature seems to capture how people weigh the technical characteristics of a computer (such as RAM, CPU, and CD-ROM) against the computer's price. The authors thus concluded that their algorithm is able to find interesting patterns in people’s purchasing decision processes.

Conclusion

The authors have presented an algorithm that learns common sparse function representations across a pool of related tasks. In this algorithm, the number of learned features is not a parameter, and it is instead controlled by the algorithm's regularization parameter. This algorithm also appears to be the first convex optimization formulation for multi-task feature learning.

Reference

Andreas Argyriou. Theodoros Evgeniou. Massimiliano Pontil. Multi-Task Feature Learning.

Multi-Task Feature Learning

From Wiki Course Notes

Contents