Understanding How Feature Structure Transfers in Transfer Learning

1 Introduction

Transfer learning is motivated by human learning. When humans encounter a continual stream of learning tasks, we do not just learn concepts, but also biases, and we are capable to transfer them to new tasks. Transfer learning is therefore referred to as extracting knowledge from source domains and applying it to improve the learning performance in a target domain.

The last decade has witnessed the success of various transfer learning algorithms [Shao et al., 2014; Long et al., 2015; Li et al., 2015; Liu et al., 2016; Shao et al., 2016] in exploiting the transfer of knowledge across domains. Selftaught learning [Raina et al., 2007], domain adaptation [BenDavid et al., 2007] (sometimes called transfer learning [Maurer et al., 2013] or lifelong learning [Pentina and Lampert, 2014]), and learning to learn [Baxter, 2000] (sometimes called multi-task learning [Ando and Zhang, 2005]) have achieved great successes in a variety of tasks [Si et al., 2010; Luo et al., 2014]. For additional references, the interested reader is referred to the survey [Pan and Yang, 2010].

Domain adaptation solves the problem in which the joint distributions Pxy over the source and target domains are different but related, where x denotes the feature and y the label. Most algorithms for domain adaptation try to (appropriately) correct the source domain distribution so that its knowledge can be transferred to the target domain. Covariate shift (Px differs across domains) [Huang et al., 2006], model shift (Py|x differs across domains) [Wang and Schneider, 2014], target shift (Py differs across domains) [Zhang et al., 2013] and conditional shift (Px|y differs across domains) [Zhang et al., 2013] are the representative and notable models for domain adaptation. All these models will succeed only when the conditional distributions Py|x (or the labeling functions) across domains are (or can be corrected to be) identical (or at least nearly identical). Most of the existing theoretical analyses [Ben-David et al., 2007; Blitzer et al., 2008; Mansour et al., 2009; Ben-David et al., 2010; Zhang et al., 2015; Gong et al., 2016] for domain adaptation are based upon this condition, and cannot explain the success of the applications where the conditional distributions Py|x differ significantly (or even arbitrarily) across the source and target domains.

Learning to learn was introduced by [Baxter, 2000] who defined the task environment as a probability measure on a set of related tasks. Most algorithms commonly assume that parameters for modeling different tasks are partially shared. Most of the existing theoretical analyses [Baxter, 2000; Maurer, 2009; Kuzborskij and Orabona, 2013; Maurer et al., 2013] for learning to learn focus on this assumption. For example, [Maurer et al., 2013] assumed that the task parameters are well approximated by sparse linear combinations of the atoms in a dictionary and provided a theoretical justification for the success. The corresponding theoretical results are therefore based upon the condition that the conditional distributions Py|x across domains are related and limited in the environment and cannot differ arbitrarily.

Can transfer learning work when the conditional distributions Py|x differ arbitrarily across domains? The answer is positive. One well-known successful example is self-taught learning [Raina et al., 2007]. Given a large amount of unlabeled data (e.g., randomly collected from the Internet), selftaught learning extracts domain invariant visual structure (or feature structure defined in this paper) to significantly improve the classification accuracy in the task domain. It does not require the source data to follow the same class labels or generative distribution as the target domain data, so its conditional distributions Py|x of source and target domains can differ very much, or even arbitrarily. Feature structures generally represent common knowledge across different domains, so they are transferrable regardless of the change of the conditional distributions Py|x across domains.

In this paper, motivated by self-taught learning, we define the feature structure of a domain as a set of bases which can (approximately) reconstruct any observation in the domain, and say an algorithm is a feature structure transfer learning algorithm if it transfers feature structure from the source domain to the target domain. For example, a self-taught learning algorithm is a feature structure transfer learning algorithm, in which the transferred feature structure is a set of sparse coding bases. However, to the best of our knowledge, theoretical justification for the success of feature structure transfer learning remains elusive.

Motivated by that self-taught learning can be formulated as a Tikhonov regularized learning in the target domain, where the Tikhonov matrix contains the feature structure extracted from the source domains, we first provide a theoretical justification for feature structure transfer learning from the perspective of regularization. We show that if the feature structures of the source and target domains are similar (i.e., for any target domain observation xt , it holds that xt ≈ Bα, where B denotes the extracted source domain feature structure and α a reconstruction coefficient), the source domain data will provide a regularization matrix and enable feature structure transfer learning algorithms to be uniformly stable [Bousquet and Elisseeff, 2002] and to learn desirable accurate predictors from small fractions of labeled examples, which provides insight as to why those algorithms achieve their empirical successes.

In contrast to the existing theoretical analyses, we focus on justifying how feature structure can be transferred to improve classification performance from the perspective of regularization. Specifically, our analyses show that if the source domain observations can be a feature structure for the target domain and the employed loss function is strongly convex, the source domain observations can be interpreted to function as a regularization matrix, which benefits the learning process of the target domain task. We prove that existing learning algorithms, such as domain adaptation and learning to learn, for learning the target predictors are feature structure transfer learning algorithms and therefore are uniformly stable, which are indispensable complements for the existing theoretical analyses.

Organization of the paper. We describe the learning setup in Section 2. In Section 3, we introduce our motivation that self-taught learning transfers feature structure and is uniformly stable. We provide theoretical justifications for the transfer of feature structure in the algorithms of domain adaptation and learning to learn in Sections 4 and 5, respectively. Finally, we draw conclusions and discuss future work in Section 6. We present the proof of our assertion in Section A.

2 Preliminaries

We start by introducing the notation that will be used throughout this paper. Let H denote the separable real Hilbert space with the inner product 〈·, ·〉 and norm ‖ · ‖. Let z = (x, y) ∈ H × {-1, 1} be a training example and S = {z1, . . . , zn} an i.i.d. training sample. We denote the i.i.d. training samples of the source and target domains by Ss = {zs 1 , . . . , z sns } = {(xs1 , ys 1 ), . . . , (xsns , ysns )} and St = {zt1 , . . . , z tnt } = {(xt1 , yt1 ), . . . , (xtnt , ytnt )}, respectively. Let H be a linear hypothesis class and ℓ(y, h(x)) a loss function measuring the risk that is incurred by predicting h(x) when the true label is y. We denote the expected and empirical risks by R(h) = Eℓ(y, h(x)) and Rn(h) = 1n ∑ni=1 ℓ(yi, h(xi)), respectively. A learning algorithm discovers a mapping that maps a training sample S to a hypothesis function hS ∈ H. The defect R(hS) -Rn(hS) is called the generalization error, which is usually exploited to measure the "goodness" of learning algorithms. A small generalization error implies that the algorithm could generalize well on unseen data.

Intuitively, given a larger training sample, a learning algorithm will learn a more accurate predictor. However, in practice, for a specific target domain, the training examples may be limited. Fortunately, we often have a large number of additional training examples, drawn from closely related source domains, which contain information that can improve the learning performance of the target domain task. Transfer learning is therefore defined as learning algorithms that employ the additional source domain examples to improve the learning performance in the target domain.

We define a set of bases B as a feature structure of a domain X × {-1, 1} if for any observation x ∈ X, x ≈ Bα, where α is the reconstruction coefficient. In this paper, we consider the transfer learning algorithms where feature structures are transferable across domains to improve the learning performance, which we call feature structure transfer learning.

To theoretically justify feature structure transfer learning, we introduce the stability framework proposed by [Bousquet and Elisseeff, 2002].

Definition 1 (Uniform stability) An algorithm has uniform stability β with respect to the loss function ℓ and a specific domain Z ⊂ H×{-1, 1} if for any independently distributed training sample S ∈ Z n , any i ∈ {1, ..., n} and any z ∈ Z, the following holds:

where Si denotes the training sample S with the i-th example zi being replaced by an i.i.d. example z′i .

[Bousquet and Elisseeff, 2002] also proved the following generalization error bound.

Theorem 1 Let the learning algorithm be β-stable and let S be a training sample with n independent random examples. Assume that the loss function ℓ is bounded by M. Then, for any δ > 0, with probability at least 1-δ, the following holds:

In this paper, we will illustrate that the transfer of feature structure enables transfer learning algorithms to be uniformly stable, as a result of which the generalization errors will be small.

3 Self-taught Learning andMotivation

In this section, we show that feature structure will have a Tikhonov regularization property in self-taught learning. Motivated by this, we will show in the following sections that feature structure transfer exists widely in existing transfer learning algorithms.

Self-taught learning introduced by [Raina et al., 2007] exploits the unlabeled data in the source domain to improve classification performance in the target domain. It first extracts a feature structure by learning a set of sparse coding bases B and then approximately reconstructs each target domain observation as a sparse linear combination of the bases B, i.e., xti = Bαi + ηi, ‖α‖1 ≤ r1, i = 1, . . . , nt, where ηi is the corresponding residual satisfying that ‖ηi‖ is small (because B can be over-completed), αi encodes the reconstruction coefficient for this target domain observation, and r1 is a constant. Lastly, self-taught learning learns a predictor by minimizing the following regularized objective function:

where λ is a regularization parameter.

We explicitly emphasize the function of the coding bases B and reformulate (3) as

Optimization problems (3) and (4) are equivalent if we write v = BT w.

If the residuals ηi, i = 1, . . . , nt are small, Bαi will be approximately equal to the target domain observations xti . Thus, self-taught learning can be viewed as learning algorithms that minimize the following regularized objective function:

By regularizing the parameter with respect to the featurestructure-based regularization matrix B, self-taught learning algorithms that solve the optimization problems (3) and (4) are uniformly stable.

As discussed in [Bousquet and Elisseeff, 2002], to show regularized learning algorithm is uniformly stable, we need the employed loss function to be admissible (a Lipschitz-like condition, which has been widely used [Mohri et al., 2012]).

Definition 2 (σ-admissible) A loss function ℓ is σadmissible with respect to the hypothesis class H if there exists a σ > 0 such that for any two hypotheses h, h′ ∈ H and any example z ∈ H × {-1, 1}, the following inequality holds:

Theorem 2 Let the loss function ℓ be convex and σadmissible. Algorithms that minimize the objective functions in (3) and (4) are uniformly stable with respect to the target domain. For any (xt , yt ), xt = Bα+η1, in the target domain, the following inequality holds for problem (4):

The proof method of Theorem 2 is the same as that in [Bousquet and Elisseeff, 2002].

Problems (4) and (5) are the well-known Tikhonov regularized empirical risk minimization, where ‖BT w‖2 is the Tikhonov regularization and BT is the Tikhonov matrix (also known as the regularization matrix). The frequently used ℓ2regularization ‖w‖2 is a special case of Tikhonov regularization by setting B = I. For particular problems, it would be more reasonable to find a suitable regularization matrix B than simply setting B = I. Self-taught learning provides a way to find a suitable regularization matrix B and its success has been empirically proven.

Our analyses show that self-taught learning extracts a feature structure B form the source domain data. It then transfers the feature structure to improve the target task performance by regularizing the learning parameter using the extracted feature structure as a regularization matrix. Theorem 2 proves that self-taught learning algorithms are uniformly stable. It therefore has a small generalization error according to Theorem 1. Motivated by the feature structure transfer procedure of self-taught learning, we will show in the following sections that a similar feature structure transfer procedure exists widely in the traditional transfer learning algorithms.

We note here that feature structure transfer learning differs very much from the pre-processing technique that represents the target domain observations onto a subspace. For example, the feature structure B could be over-completed. Moreover, we will show in the following sections that feature structures can be transferred in a general form of a set of source domain observations for domain adaptation and learning to learn problems, where we do not need to specifically learn the coding bases B.

4 Domain Adaptation

Often, domain adaptation studies the transfer learning problem where the target domain has a small amount of data, or even no label information, while the source domain has relatively sufficient data. However, in this paper, we consider the situation where the target domain has a number of labeled examples, which often happens in practice.

We study the domain adaption algorithms proposed by [Blitzer et al., 2008] which minimize a convex combination of the source and target empirical risk:

where α ∈ (0, 1). By setting a proper value for α, i.e., α = nt/(ns +nt), the objective function in (8) includes the objective function of the traditional domain adaptation algorithm

as a special case.

In the following, we will show that if the source and target domains have similar feature structures, uniform stability can be derived for the learning algorithms that minimize (8) by interpreting the function of the source data as a regularization matrix.

The source domain observations can function as a transferable feature structure for improving the target domain task if the following assumption holds:

Assumption 1 For any target domain observation xt , we have xt = ∑ns j=1 γjxsj + η2, where ‖γ‖ ≤ r2, {xs1 , . . . , xsns } are the source domain observations, and η2 is a small residual that ‖η2‖ ≤ ε2.

To interpret the function of source domain observations as a regularization, we need the employed loss function to be strongly convex.

Definition 3 (c-strongly convex) A differentiable loss function ℓ(y, h(x)) is called c-strongly convex with respect to ‖ · ‖ if the following inequality holds for any z = (x, y) in its domain and any h, h′ ∈ H:

where c > 0 and ∇ℓ(y, h(x)) denotes the gradient of the loss function ℓ(y, h(x)) with respect to the predictor h(x).

Strong convexity and strong smoothness are dual properties. Strongly convex programming algorithms have many benign properties, both in the speed of optimization and the quality of generalization [Kakade and Tewari, 2009].

The square loss function is 2-strongly convex and has been widely used. Many other frequently used loss functions, such as hinge loss and logistic loss, are only convex but not strongly convex. However, they may be strongly convex when h(x) is restricted to a compact set. For example, the logistic loss ℓ(y, h(x)) = log(1 + exp(-yh(x))) is exp(-U)/4-strongly convex when h(x) is restricted to the interval [-U,U], because d2 ℓ(y, h(x))/d2h(x) = exp(yh(x))/(exp(yh(x)) + 1)2 ≥ exp(-U)/4. They can also be revised as strongly convex by adding a strongly convex regularization, e.g., the ℓ2-regularization.

The goal of domain adaptation is to modify the source domain distribution so that the learned predictor can perform well on the target domain. We now show that the feature structure provided by the source domain data can be transferred to enable domain adaptation algorithms to be uniformly stable with respect to the target domain.

Theorem 3 Suppose Assumption 1 holds. Let the loss function ℓ be c-strongly convex and σ-admissible. Then, algorithms that solve optimization problem (8) are uniformly stable with respect to the target domain. For any (xt , yt ) drawn from the target domain, we have:

When ε2 = 0, which means that the target observations can be perfectly reconstructed by the source observations or that the source domain observations can serve as a feature structure for the target domain, we have

See the proof in the Appendix.

Inequalities (11) and (12) in Theorem 3 show that the upper bound of the uniform stability will decrease fast with a an order of O(1/nt), where nt is the sample size of the target domain. This means that the target learning algorithm can generalize fast on unseen data.

The empirical study in [Blitzer et al., 2008] shows that for some real-world datasets, tuning the parameter α can greatly improve transfer learning performance. They also derived upper bound and discussed that by choosing different values of α, we can effectively trade off the small amount of target data against the large amount of less relevant source data. This is in accordance with our analyses, where α has been interpreted as a regularization parameter. Such a tuning parameter is necessary for the transfer of feature structure by balancing the different feature structure scales across domains.

In the proof of Theorem 3, we have interpreted the source domain observations Xs = [xs1 , . . . , xsns ] as a transferable feature structure, which function as a regularization matrix for the learning algorithm that learns the target domain task; while in self-taught learning, the coding bases B is a transferable feature structure functioning as a regularization matrix for the learning algorithm that learns the target domain task. Although the source domain data are labeled, we have not exploited the label information during the proof procedure, and thus our theoretical justification for feature structure transfer depends on the marginal distribution Px and is independent of the change of the conditional distribution Py|x over domains. This makes sense because we observed that feature structure can be transferred even though the conditional distribution differs arbitrarily across domains.

The obtained generalization error bound in Theorem 1 has a fast convergence rate with respect to the target domain training sample size nt, of order O(1/nt). However, no benefit for increasing the source training sample size ns is shown. This is because we have theoretically focused on justifying the transfer of feature structure, but not the transfer of labeling information, and we have assumed that the target domain feature structure is already given by the source domain training sample; under this circumstance, increasing the size of the source domain training sample may help little. In practice, however, more source domain training examples will provide a more completed feature structure and more labeling information. A large source domain training sample is therefore preferred.

In the rest of the paper, for simplicity, we will consider the case that the residual is zero, which occurs if the feature structure is perfectly provided by the source domain observations (i.e., the source domain observations can exactly reconstruct the target domain data). However, similar to the results shown in Theorem 3, our results can be easily extended to the case in which the residual ε ̸= 0.

5 Learning to Learn

Learning to learn was formulated by [Baxter, 2000], where a probability measure E known as the environment was introduced on a set of related tasks. It aims to find learning algorithm that performs well on all of the tasks in the environment.

Let µl be the probability measure of the example zl = (xl, yl) in the context of the task l. We will use Sl = {(xl,1, yl,1), . . . , (xl,nl , yl,nl )} to denote the training sample of the task l. Let hD,Sl denote the predictor computed by a learning algorithm AD using the training sample Sl, where D is a learning parameter for the learning algorithm AD. The notion of expected transfer risk [Maurer et al., 2013] associated with the learning algorithm AD is defined as follows:

The expected transfer risk can be estimated by the empirical transfer risk of a finite set of tasks. Many learning to learn algorithms therefore minimize the expected transfer risk by alternatively minimizing the empirical transfer risk of N tasks that have been drawn independently from the environment E:

The learning parameter D can be of many different forms, e.g., either a matrix or a vector. [Maurer et al., 2013] defined D to be a matrix as a set of dictionary bases. [Evgeniou and Pontil, 2004] assumed D to be a vector as the overlap of the parameters among multiple tasks. Specifically, they assumed that all task parameters wl can be written as wl = w0 + vl 1 . We have proven that in this setting tasks could regularize tasks [Liu et al., 2017b] and therefore the algorithms generalize fast [Liu et al., 2017a].

In this paper, we consider the matrix case, where hD,Sl (xl) = 〈Dγ, xl〉. Then, the empirical risk minimization algorithm becomes [Maurer et al., 2013]

where Dk is a set of k-dimensional dictionaries, every D ∈ Dk is a linear map from Rk to the hypothesis class H, and Cγ is a set of code vectors in Rk satisfying some properties, such as sparsity.

We apply our analysis scheme to learning to learn by focusing on the performance of one particular task. For simplicity, we assume there are two tasks. Let denote the domain of the focused task as the target domain and the other one the source domain. Learning to learn algorithms then solve the following optimization problem:

1 Constraints are needed to control a trade-off between w0 and vl. Many algorithms encourage w0 to be large.

Let the non-zero parts of the target parameter γ t and source parameter γ s have an overlap γ0, i.e., γ t = γ0 +∆γ t . Using a proof method similar to that of Theorem 3, we show that "source" domain observations can be transferred as a feature structure to the "target" domain and function as a regularization matrix, which enables learning to learn algorithms to be uniformly stable with respect to the target domain.

Theorem 4 Suppose Assumption 1 holds and ε2 = 0. Let the loss function ℓ be c-strongly convex and σ-admissible. Algorithms that solve problem (16) are uniformly stable with respect to the target domain. For any learned γ0,∆γ t ∈ H and any (xt , yt ) drawn from the target domain, the following holds:

The proof method of Theorem 4 is the same as that of Theorem 3.

Theorem 4 shows that the learning of the overlapping information between source and target tasks will be benefit from feature structure transfer learning. The discussions on domain adaptation apply to learning to learn as well.

6 Conclusion

This paper studied the feature structure transfer learning problem. We theoretically justified that feature structure can be transferred, independently of the change of Py|x over domains, to improve the learning performance in the target domain. Motivated by self-taught learning, we discussed how feature structure can be transferred in domain adaptation and learning to learn settings from a regularization perspective. Our analysis implies that a tuning parameter is necessary to help transfer feature structure information from the source domain to the target domain. We believe that our analysis scheme applies to many other existing transfer learning settings as well.

The theoretical analyses in this paper stimulate our future work in two related directions. First, as we have interpreted the function of the transferred feature structure as regularization, we will consider introducing proper regularization parameters to improve the performance of existing transfer learning applications. Second, we plan to learn feature representation for (semi-supervised) feature structure transfer learning algorithms by designing a new criterion to match feature structure.

Acknowledgments

Liu and Tao were partially supported by Australian Research Council Projects FT-130101457, DP-140102164, LP150100671.

A Appendix

A.1 Used Tool

We introduce Bregman divergence [Mohri et al., 2012] to help upper bound the uniform stability.

Definition 4 (Bregman divergence) Let f : H → R be a convex function. For all s, t ∈ H, we have

where ∇f(t) denotes the gradient of function f(t).

Bregman divergence has the following properties. Detailed discussions can be found in [Mohri et al., 2012].

Lemma 1 Bregman divergence is additive and non-negative. If f = f1 + f2, and both f1 and f2 are convex, for any s, t ∈ H, we have

A.2 Proof of Theorem 3

In this subsection, we prove that algorithms solving the following optimization problem:

are uniformly stable with respect to the target domain.

Let

and

By abusing the notation a little bit without confusion, we let w be the solution to optimization problem (20) when the input training sample is St and w′ be the solution when the input training sample is Si t . Since the employed loss function is convex. According to the non-negative and additive properties of Bregman divergence, we have

To upper bound the left-hand side of inequality (24), we have

To lower bound the right-hand side of inequality (24), we consider two different forms of loss function: (i) ℓ(y, 〈w, x〉) = ℓ(y - 〈w, x〉) and (ii) ℓ(y, 〈w, x〉) = ℓ(y 〈w, x〉). When the loss function is of form (i), we have

When the loss function is of form (ii), we have

Combining (24), (25), (26) and (27), we have

Thus, for any training sample S ∈ (H × R)n , any i ∈ {1, ..., n} and any z ∈ H × R, xt = ∑ns j=1 γjxsj + η2, the following holds:

This completes the proof of Theorem 4.

■