Title: AN INFORMATION-THEORETIC METRIC OF TRANSFERABILITY FOR TASK TRANSFER LEARNING

Abstract: An important question in task transfer learning is to determine task transferability, i.e. given a common input domain, estimating to what extent representations learned from a source task can help in learning a target task. Typically, transferability is either measured experimentally or inferred through task relatedness, which is often defined without a clear operational meaning. In this paper, we present a novel metric, H-score, an easily-computable evaluation function that estimates the performance of transferred representations from one task to another in classification problems. Inspired by a principled information theoretic approach, H-score has a direct connection to the asymptotic error probability of the decision function based on the transferred feature. This formulation of transferability can further be used to select a suitable set of source tasks in task transfer learning problems or to devise efficient transfer learning policies. Experiments using both synthetic and real image data show that not only our formulation of transferability is meaningful in practice, but also it can generalize to inference problems beyond classification, such as recognition tasks for 3D indoor-scene understanding.

1. INTRODUCTION:

Transfer learning is a learning paradigm that exploits relatedness between different learning tasks in order to gain certain benefits, e.g. reducing the demand for supervision (Pratt (1993) ). In task transfer learning, we assume that the input domain of the different tasks are the same. Then for a target task T T , instead of learning a model from scratch, we can initialize the parameters from a previously trained model for some related source task T S . For example, deep convolutional neural networks trained for the ImageNet classification task have been used as the source network in transfer learning for target tasks with fewer labeled data (Donahue et al. (2014) ), such as medical image analysis (Shie et al. (2015) ) and structural damage recognition in buildings (Gao & Mosalam) .

An imperative question in task transfer learning is transferability, i.e. when a transfer may work and to what extent. Given a metric capable of efficiently and accurately measuring transferability across arbitrary tasks, the problem of task transfer learning, to a large extent, is simplified to search procedures over potential transfer sources and targets as quantified by the metric. Traditionally, transferability is measured purely empirically using model loss or accuracy on the validation set (Yosinski et al. (2014) ; Zamir et al. (2018) ; Conneau et al. (2017) ). There have been theoretical studies that focus on task relatedness (Baxter (2000) ; Maurer (2009) ; Pentina & Lampert (2014) ; Ben-David et al. (2003) ). However, they either cannot be computed explicitly from data or do not directly explain task transfer performance. In this study, we aim to estimate transferability analytically, directly from the training data.

We quantify the transferability of feature representations across tasks via an approach grounded in statistics and information theory. The key idea of our method is to show that the error probability of using a feature of the input data to solve a learning task can be characterized by a linear projection of this feature between the input and output domains. Hence we adopt the projection length as a metric of the feature's effectiveness for the given task, and refer to it as the H-score of the feature. More generally, H-score can be applied to evaluate the performance of features in different tasks, and is particularly useful to quantify feature transferability among tasks. Using this idea, we define task transferability as the normalized H-score of the optimal source feature with respect to the target task.

As we demonstrate in this paper, the advantage of our transferability metric is threefold. (i) it has a strong operational meaning rooted in statistics and information theory; (ii) it can be computed directly and efficiently from the input data, with fewer samples than those needed for empirical learning; (iii) it can be shown to be strongly consistent with empirical transferability measurements.

In this paper, we will first present the theoretical results of the proposed transferability metric in Section 2-4. Section 5 presents several experiments on real image data , including image classificaton tasks using the Cifar 100 dataset and 3D indoor scene understanding tasks using the Taskonomy dataset created by Zamir et al. (2018) . A brief review of the related works is included in Section 6.

2. BACKGROUND:

In this section, we will introduce the notations used throughout this paper, as well as some related concepts in Euclidean information theory and statistics.

X, x, X and P X represent a random variable, a value, the alphabet and the probability distribution respectively.

√ P X denotes the vector with entries P X (x) and [ √ P X ] the diagonal matrix of P X (X). For joint distribution P Y X , P Y X represents the |Y| × |X | probability matrix. Depending on the context, f(X) is either a |X |-dimensional vector whose entries are f (x), or a |X | × k feature matrix. Further, we define a task to be a tuple T = (X, Y, P XY ), where X is the training features and Y is the training label, and P XY the joint probability (possibly unknown). Subscripts S and T are used to distinguish the source task from the target task.

2.1. LOCAL INFORMATION GEOMETRY AND HYPOTHESIS TESTING:

Our definiton of transferability uses concepts in local information geometry developed by Makur et al. (2015) , which characterizes probability distributions as vectors in the information space. Consider the following binary hypothesis testing problem: test whether i.i.d. samples x m = {x (i) } m i=1 are drawn from distribution P 1 or distribution P 2 , where P 1 , P 2 belong to an -neighborhood

N (P 0 ) {P | x∈X (P (x)-P0(x)) 2 P0(x)

≤ 2 } centered at a reference distributon P 0 . And denote

φ i = Pi(x)-P0(x) √ P0(x)

as the information vector corresponding to P i for i = 1, 2.

Given k normalized feature functions f (x) = [f 1 (x), . . . , f k (x)], let Ξ(x) = [ξ 1 (x), . . . , ξ k (x)] be the matrix of feature vectors ξ i (x) = P 0 (x)f i (x). Given observations x m , feature f is associated with a k-dimensional statistics l(x m ) = 1 m m i=1 (f (x (i)

)) for the binary hypothesis testing problem. Let E f be the error exponent of decision region {x m | l(x m ) > T } for T ≥ 0, which characterizes the asymptotic error probability P e of l (i.e. lim m→∞ -1 m log(P e ) = E k f ). E f can be written as the squared length of a projection:

E k f = k i=1 E fi = k i=l 2 8 ξ i , φ 1 -φ 2 2 + o( 2 ) (1) When f (x) = log P1(x) P2(x)

is the log likelihood ratio, l is the minimum sufficient statistics that achieves the largest error exponent

E k f = k i=1 2 8 ||φ 1 -φ 2 || 2 + o( 2 )

by the Chernoff theorem. (See Appendix A for details.) In the rest of this paper, we assume is small.

2.2. DIVERGENCE TRANSITION MATRIX:

Definition 1. Matrix B is the Divergence Transition Matrix (DTM) of a joint probability P Y X if B = √ P Y -1 P Y X √ P X -1 - √ P Y √ P X T .

The singular values of B satisfy that

1 ≥ σ 1 ≥ • • • ≥ σ K = 0, K min{|X |, |Y|}. Let Ψ = [ψ 1 , . . . , ψ K ] and Φ = [φ 1 , . . . , φ K ] be the left and right singular vectors of B. Define functions f * i (x) = φi(x) √ P X (x)

and

g * i (y) = ψi(y) √ P Y (y)

for each i = 1, . . . , K -1. Makur et al. (2015) further proved that f * i and g * i are solutions to the maximal HGR correlation problem studied by Hirschfeld (1935); Gebelein (1941) ; Rényi (1959) , defined as follows:

EQUATION

The maximal HGR problem finds the K strongest, independent modes in P XY from data. It can be solved efficiently using the Alternating Conditional Expectation (ACE) algorithm with provable error bound (see Appendix B). Huang et al. ( 2017) further showed that f * and g * are the universal minimum error probability features in the sense that they can achieve the smallest error probability over all possible inference tasks.

3. MEASURING THE EFFECTIVENESS OF FEATURES IN CLASSIFICATION TASKS:

In this section, we present a performance metric of a given feature representation for a learning task.

3.1. H-SCORE:

For a classification task involving input variable X and label Y , most learning algorithms work by finding a k-dimensional functional representation f (x) of X that is most discriminative for the classification. To measure how effective f (x) is in predicting Y , rather than train the model via gradient descent and evaluate its accuracy, we present an analytical approach based on the definition below: Definition 2. Given data matrix X ∈ R m×d and label Y ∈ {1, . . . , |Y|}. Let f (x) be a kdimensional, zero-mean feature function. The H-Score of f (x) with respect to the learning task represented by P Y X is:

H(f ) = tr(cov(f (X)) -1 cov(E P X|Y [f (X)|Y ]))

This definition is intuitive from a nearest neighbor search perspective. i.e. a high H-score implies the inter-class variance cov(E P X|Y [f (X)|Y ]) of f is large, while feature redundancy tr(cov(f (X))) is small. Such a feature is discriminative and efficient for learning label Y. More importantly, H(f ) has a deeper operational meaning related to the asymptotic error probability for a decision rule based on f in the hypothesis testing context, discussed in the next section.

3.2. OPERATIONAL MEANING OF H-SCORE:

Without loss of generality, we consider the binary classification task as a hypothesis testing problem defined in Section 2.1, with P 1 = P X|Y =0 , and P 2 = P X|Y =1 . For any k-dimensional feature representation f (x), we can quantify its performance with respect to the learning task using its error exponent E k f . Theorem 1. Given P X|Y =0 , P X|Y =1 ∈ N X (P 0,X ) and features f such that E [f (X)] = 0 and

E[f (X)f (X) T ] = I, there exists some constant c independent of f such that E k f = cH(f ).

See Appendix C for the proof. The above theorem shows that H-score H(f ) is proportional to the error exponent of the decision region based on f (x) when f (x) is zero-mean with identity covariance.

To compute the H-score of arbitrary f , we can center the features f S (x) -E[f S (x)], and incorporate normalization into the computation of the error exponent, which results in Definition 2. The details are presented in Appendix D.

The proof for Theorem 1 uses the fact that

H(f ) = BΞ 2 F , where B is the DTM matrix, Ξ [ξ 1 • • • ξ k ]

is the matrix composed of information vectors ξ i and c is a constant. This allows us to infer an upper bound for the H-score of a given learning task:

Corollary 1. For all normalized feature f (x) = [f 1 (x), . . . , f k (x)], its H-score satisfies H(f ) ≤ k i=1 σ 2 i ≤ k

, where σ i is the ith singular value of B. 

4. TRANSFERABILITY:

Next, we apply H-score to efficiently measure the effectiveness of task transfer learning. We will also discuss how this approach can be used to solve the source task selection problem.

4.1. TASK TRANSFERABILITY:

A typical way to transfer knowledge from the source task T S to target task T T is to train the target task using source feature representation f S (x). In a neural network setting, this idea can be implemented by copying the parameters from the first N layers in the trained source model to the target model, assuming the model architecture on those layers are the same. The target classifier then can be trained while freezing parameters in the copied layers (Figure 1 ). Under this model, a natural way to quantify transferability is as follows: Definition 3 (Task transferability). Given source task T S and target task T T , and trained source feature representation f S (x), the transferability from T S to T T is T(S, T )

H T (f S ) H T (f T opt )

, where f Topt (x) is the minimum error probability feature of the target task.

The statement T(S, T ) = r means the error exponent of transfering from T S via feature representation f S is 1 r of the optimal error exponent for predicting the target label Y T . This definition also implies 0 ≤ T(S, T ) ≤ 1, which satisfies the data processing inequality if we consider the transferred feature f S (X) as post-processing of input X for solving the target task. And it can not increase information about predicting the target task T .

A common technique in task transfer learning is fine-tuning, which adds before the target classifier additional free layers, whose parameters are optimized with respect to the target label. For the operational meaning of transferability to hold exactly, we require the fine tuning layers consist of only linear transformations, such as the model illustrated in Figure 2 .a. It can be shown that under the local assumption, H-score is equivalent to the log-loss of the linear transfer model up to a constant offset (Appendix E). Nevertheless, later we will demonstrate empirically that this transferability metric can still be used for comparing the relative task transferability with fine-tuning.

4.2. EFFICIENT COMPUTATION OF TRANSFERABILITY:

With a known f , computing H-score from m sample data only takes O(mk 2 ) time, where k is the dimension of f (x) for k < m. The majority of the computation time is spent on computing the sample covariance matrix cov(f (X)).

The remaining question is how to obtain f Topt efficiently. We use the fact that

H T (f opt ) = || BT || 2 F = E[f (X) T g(Y )],

where f and g are the solutions of the HGR-Maximum Correlation problem. This problem can be solved efficiently using the ACE algorithm for discrete variable X. For a continuous random variable X, we can obtain f opt through a different formulation of the HGR maximal correlation problem:

EQUATION

This is also known as the soft HGR problem studied by Wang et al. (2019) , who reformulated the original maximal HGR correlation objective to eliminate the whitening constraints while having theoretically equivalent solution. In practice, we can utilize neural network layers to model functions f and g, as shown in Figure 2 .b. Given two branches of k output units for both f and g, the loss function can be evaluated in O(mk 2 ), where m is the batch size. Makur et al. (2015) showed that the sample complexity of ACE is only 1/k of the complexity of estimating P Y,X directly. This result also applies to the soft HGR problem due to their theoretical equivalence. Hence transferability can be computed with much less samples than actually training the transfer network.

It's also worth noting that, when f is fixed, maximizing the objective in Equation 3 with respect to zero-mean function g results in the definition of H-score. In many cases though, the computation of H T (f opt ) can even be skipped entirely, such as the problem below:

Definition 4 (Source task selection). Given N source tasks T S1 , . . . , T S N with labels Y S1 , . . . , Y S N and a target task T T with label Y T . Let f S1 , . . . , f S N be the minimum error probability feature functions of the source tasks. Find the source task T Si that maximizes the testing accuracy of predicting Y T with feature f Si .

We can solve this problem by selecting the source task with the largest transferability to T T . In fact, we only need to compute the numerator in the transferability definition since the denominator is the same for all source tasks, i.e.

argmax i T(S i , T ) = argmax i (H T (f Si,opt )/H T (f Topt ) = argmax i H(f Si ).

4.3. RELATIONSHIP WITH MUTUAL INFORMATION:

Under the local assumption that P X|Y ∈ N (P X ), we can show that mutual information

I(X; Y ) = 1 2 ||B|| 2 F + o( 2 ). (See Appendix F for details.

) Hence H-score is related to mutual information by H(f (x)) ≤ 2I(X; Y ) for any zero-mean features f (x) satisfying the aforementioned conditions.

Figure 3 compares the optimal H-score of a synthesized task when |Y| = 6 with the mutual information between input and output variables, when the feature dimension k changes. The value of H-score increases as k increases, but reaches the upper bound when k ≥ 6, since the rank of the joint probability between X and Y T , as well as the rank of its DTM is 6. As expected, the H-score values are below 2I(X; Y ), with a gap due to the constant o( 2 ). This relationship shows that H-score is consistent with mutual information with a sufficiently large feature dimension k.

In practice, H-score is much easier to compute than mutual information when the input variable X (or f S (X)) is continous, as mutual information are either computed based on binning, which has extra bias due to bin size, or more sophisticated methods such as kernel density estimation or neural networks (Gabrié et al. (2018) ). On the other hand, H-score only needs to estimate conditional expectations, which requires less samples.

5. EXPERIMENTS:

In this section, we validate and analyze our transferability metric through experiments on real image data. 1 The tasks considered cover both object classification and non-classification tasks in computer vision, such as depth estimation and 3D (occlusion) edge detection.

5.1. VALIDATION OF TRANSFER PERFORMANCE:

To demonstrate that our transferability metric is indeed a suitable measurement for task transfer performance, we compare it with the empirical performance of transfering features learned from ImageNet 1000-class classification (Krizhevsky et al. (2012) ) to Cifar 100-class classification (Krizhevsky & Hinton (2009) ), using a network similar to Figure 1 . Comparing to ImageNet-1000, Cifar-100 has smaller sample size and its images have lower resolution. Therefore it is considered to be a more challenging task than ImageNet, making it a suitable case for transfer learning. In addition, we use a pretrained ResNet-50 as the source model due to its high performance and regular structure.

Validation of H-score. The training data for the target task in this experiemnt consists of 20, 000 images randomly sampled from Cifar-100. It is further split 9:1 into a training set and a testing set. The transfer network was trained using stochastic gradient descent with batch size 20, 000 for 100 epochs. This experiment also showed another potential application of H-score for selecting the most suitable layer for fine-tuning in transfer learning. In the example, transfer performance is better when an upper layer of the source networks is transferred. This could be because the target task and the source task are inherently similar such that the representation learned for one task can still be discriminative for the other. Validation of Transferability. We further tested our transferability metric for selecting the best target task for a given source task. In particular, we constructed 4 target classification tasks with 3, 5, 10, and 20 object categories from the Cifar-100 dataset. We then computed the transferability from ImageNet-1000 (using the feature representation of layer 4f) to the target tasks. The results are compared to the empirical transfer performance trained with batch size 64 for 50 epochs in Figure4.c. We observe a similar behavior as the H-score in the case of a single target task in Figure 4 .a, showing that transferability can directly predict the empirical transfer performance.

5.2. TASK TRANSFER FOR 3D SCENE UNDERSTANDING:

In this experiment, we solve the source task selection problem for a collection of 3D sceneunderstanding tasks using the Taskonomy dataset from Zamir et al. ( 2018). In the following, we will introduce the experiment setting and explain how we adapt the transferability metric to pixel-to-pixel recognition tasks. Then we compare transferability with task affinity, an empirical transferability metric proposed by Zamir et al. (2018) .

Data and Tasks. The Taskonomy dataset contains 4,000,000 images of indoor scenes of 600 buildings. Every image has annotations for 26 computer vision tasks. We randomly sampled 20, 000 images as training data. Eight tasks were chosen for this experiment, covering both classifications and lower-level pixel-to-pixel tasks. Table 6 summaries the specifications of these tasks and sample outputs are shown in Figure 5 . Pairwise Transfer Results. Source task ranking results using transferability and affinity are visualized side by side in Figure 7 , with columns representing source tasks and rows representing target tasks. For classification tasks (the bottom two rows in the transferability matrix), the top two transferable source tasks are identical for both methods. The best source task is the target task itself, as the encoder is trained on a task-specific network with much larger sample size. Scene Class. and Object Class. are ranked second for each other, as they are semantically related. Similar observations can be found in 2D pixel-to-pixel tasks (top two rows). The results on lower rankings are noisier.

A slightly larger difference between the two rankings can be found in 3D pixel-to-pixel tasks, especially 3D Occlusion Edges and 3D Keypoints. Though the top four ranked tasks of both methods are exactly the four 3D tasks. It could indicate that these low level vision tasks are closely related to each other so that the transferability among them are inherently ambiguous. We also computed the ranking correlations between transferability and affinity using Spearman's R and Discounted Cumulative Gain (DCG). Both criterion show positive correlations for all target tasks. The correlation is especially strong with DCG as higher ranking entities are given larger weights.

The above observations inspire us to define a notion of task relatedness, as some tasks are frequently ranked high for each other. Specifically, we represent each task with a vector consisting of H-scores of all the source tasks, then apply agglomerative clustering over the task vectors. As shown in the dendrogram in Figure 7 , 2D tasks and most 3D tasks are grouped into different clusters, but on a higher level, all pixel-to-pixel tasks are considered one category compared to the classifications tasks. Higher Order Transfer. Sometimes we need to combine features from two or more source tasks for better transfer performance. A common way to combine features from multiple models in deep neural networks is feature concatenation. For such problems, our transferability definition can be easily adapted to high order feature transfer, by computing the H-score of the concatenated features.

Figure 8 shows the ranking results of all combinations of source task pairs for each target task. For all tasks except for 3D Occlusion Edges and Depth, the best seond-order source feature is the combination of the top two tasks of the first-order ranking. We examine the exception in Figure 9 , by visualizing the pixel-by-pixel H-scores of first and second order transfers to Depth using a heatmap (lighter color implies a higher H-score). Note that different source tasks can be good at predicting different parts of the image. The top row shows the results of combining tasks with two different "transferability patterns" while the bottom row shows those with similar patterns. Combining tasks with different transferability patterns has a more significant improvement to the overall performance of the target task.

6. RELATED WORKS:

Transfer learning. Transfer learning can be devided into two categories: domain adaptation, where knowledge transfer is achieved by making representations learned from one input domain work on a different input domain, e.g. adapt models for RGB images to infrared images (Wang & Deng (2018) ); and task transfer learning, where knowledge is transferred between different tasks on the same input domain (Torrey & Shavlik (2010) ). Our paper focus on the latter prolem.

Empirical studies on transferability. Yosinski et al. ( 2014) compared the transfer accuracy of features from different layers in a neural network between image classification tasks. A similar study was performed for NLP tasks by Conneau et al. (2017) . Zamir et al. ( 2018) determined the optimal transfer hierarchy over a collection of perceptual indoor scene understanidng tasks, while transferability was measured by a non-parameteric score called "task affinity" derived from neural network transfer losses coupled with an ordinal normalization scheme.

Task relatedness. One approach to define task relatedness is based on task generation. Generalization bounds have been derived for multi-task learning (Baxter (2000) ), learning-to-learn (Maurer (2009) ) and life-long learning (Pentina & Lampert (2014) ). Although these studies show theoretical results on transferability, it is hard to infer from data whether the assumptions are satisfied. Another approach is estimating task relatedness from data, either explicitly (Bonilla et al. (2008) ; Zhang (2013)) or implicitly as a regularization term on the network weights (Xue et al. (2007) ; Jacob et al. (2009) ). Most works in this category are limited to shallow ones in terms of the model parameters.

Representation learning and evaluation. Selecting optimal features for a given task is traditionally performed via feature subset selection or feature weight learning. Subset selection chooses features with maximal relevance and minimal redundancy according to information theoretic or statistical criteria (Peng et al. (2005) ; Hall (1999)). The feature weight approach learns the task while regularizing feature weights with sparsity constraints, which is common in multi-task learningLiao & Carin (2006); Argyriou et al. (2007) . In a different perspective, Huang et al. ( 2017) consider the universal feature selection problem, which finds the most informative features from data when the exact inference problem is unknown. When the target task is given, the universal feature is equivalent to the minimum error probability feature used in this work.

7. CONCLUSION:

In this paper, we presented H-score, an information theoretic approach to estimating the performance of features when transferred across classification tasks. Then we used it to define a notion of task transferability in multi-task transfer learning problems, that is both time and sample complexity efficient. The resulting transferability metric also has a strong operational meaning as the ratio between the best achievable error exponent of the transferred representation and the minium error exponent of the target task.

Our transferability score successfully predicted the performance for transfering features from ImageNet-1000 classification task to Cifar-100 task. Moreover, we showed how the transferability metric can be applied to a set of diverse computer vision tasks using the Taskonomy dataset.

In future works, we plan to extend our theoretical results to non-classification tasks, as well as relaxing the local assumptions on the conditional distributions of the tasks. We will also investigate properties of higher order transferability, developing more scalable algorithms that avoid computing the H-score of all task pairs. On the application side, as transferability tells us how different tasks are related, we hope to use this information to design better task hierarchies for transfer learning. x m with the following hypotheses: H 0 : x m ∼ P 1 or H 1 : x m ∼ P 2 . Let P x m be the empirical distribution of the samples. The optimal test, i.e., the log likelihood ratio test can be stated in terms of information-theoretic quantities as follows: Further, using Sannov's theorem, we have that asymptotically the probability of type I error See Cover & Thomas (1991) for more background information on error exponents and its related theorems.

log P 1 (x m ) P 2 (x m ) = m[D(P x m ||P 2 ) -D(P x m ||P 1 )] H0 ≷ H1 log T H 0 : P 1 H 1 : P 2 β = P 2 (A) α = P 1 (A c

EQUATION

A.2 LOCAL INFORMATION GEOMETRY:

Now consider the same binary hypothesis testing problem, but with the local constraint P 1 , P 2 ∈ N (P X 0 ).

Let φ i = Pi(x)-P X 0 (x) √ P X 0 (x)

denote the information vectors corresponding to P i for i = 1, 2. Makur et al. (2015) uses local information geometry to connect the error exponent in hypothesis testing to the length of certain information vectors, summarized in the following two lemmas. Lemma 1. Given zero-mean, unit variance feature function f (x) : X → R, the optimal error exponent (a.k.a. Chernoff exponent) of this hypothesis testing problem is

E = 2 8 φ 1 -φ 2 2 + o( 2 )

Lemma 2. Given zero-mean, unit variance feature function f (x) : X → R, the error exponent of a mismatched decision function of the form

l = 1 m m i=1 (f (x (i) )) is E f = 2 8 ξ, φ 1 -φ 2 2 + o( 2 )

where ξ(x) = P 0 (x)f (x) is the feature vector associated with f (x).

As our discussion of transferability mostly concerns with multi-dimensional features, we present the k-dimensional generalization of Lemma 2 below: (Equation 1 in the main paper.)

Lemma 3. Given k normalized feature functions f (x) = [f 1 (x), . . . , f k (x)], such that E[f i (X)] = 0

for all i, and cov(f (X)) = I , we define a k-d statistics of the form l k = (l 1 , ..., l k ) where

EQUATION

Proof. According to Cramér's theorem, the error exponent under P i is

E i (λ) = min P ∈δ(λ) D(P ||P i )

where δ (λ)

P : E P [f (X) k ] = λE P1 [f (X) k ] + (1 -λ)E P2 [f (X) k ] .

With the techniques developed in local information geometry, the above above problem is equivalent to the following problem:

E i (λ) = min φθ k ∈σ(λ) 1 2 φθ k -φ i 2 where σ(λ) φθ k : φθ k , ξ l = λφ 1 + (1 -λ)φ 2 , ξ l , l = 1, ..., k and i = 1, 2. Further, using the equation φθ k (x) = k l=1 θ l ξ l (x)+φ i (x)-α(θ k ) P 0 (x)+o( ) and the equation α(θ k ) = o( 2 ), it is easy to show that E 1 (λ) = E 1 (λ) when λ = 1 2 .

Then the overall error probability has the exponent as shown in Equation (1).

APPENDIX B HGR MAXIMAL CORRELATION AND THE ACE ALGORITHM:

Given random variables X and Y , the HGR maximal correlation ρ(X; Y ) defined in Equation 2 is a generalization of the Pearson's correlation coefficient to capture non-linear dependence between random variables. According to Rényi (1959) , it satisfies all seven natural postulates of a suitable dependence measure. Some notable properties are listed below:

1. ρ(X; Y ) is defined for any pair of random variables X and Y 2. 0 ≤ ρ(X; Y ) ≤ 1; 3. ρ(X; Y ) = 0 if and only if X and Y are independent 4. ρ(X; Y ) = 1 if and only if X and Y are strictly dependent.

When the feature dimension is 1, the solution of the maximal HGR correlation is ρ(X; Y ) = σ 1 , the largest singular value of the DTM matrix B. For k-dimensional features, ρ(X; Y ) = k i (σ i ). However, computing B requires estimating the joint probability P Y X from data, which is inpractical in real applications. Breiman & Friedman (1985) proposed an efficient algorithm, alternating condition expectation (ACE), inspired by the power method for computing matrix singular values.

Algorithm 1 The ACE algorithm:

Require: training samples {((x (i) , y (i) 

) : i = 1, . . . , m} 1: Initialize g(y) ∈ R k , ∀y ∈ Y randomly 2: Center g(y) ← g(y) -E[g(y)] 3: repeat 4: f (x) ← E[g(Y ) | X = x], ∀x ∈ X 5: f (x) ← f (x)E[f (X)f (X) T ] -1 2 , ∀x ∈ X {Normalize f (x)} 6: g(y) ← E[f (X) | Y = y], ∀y ∈ Y 7: g(y) ← g(x)E[g(Y )g(Y ) T ] -1 2 , ∀y ∈ Y {Normalize g(y)} 8: until E[f (X) T g(Y )] stops increasing

In Algorithm 1, we first initialize g as a random k-dimensional zero-mean function. Then iteratively update f (x) and g(y) for all x ∈ X and y ∈ Y . The conditional distributions on Line 4 and 6 are computed as the empirical average over m samples. The normalization steps on Lines 5 and 7 can also be implemented using the Gram-Schmidt process. Note that the ACE algorithm has several variations in previous works, including a kernel-smoothed version (Breiman & Friedman (1985) ) and a parallel version with improved efficiency (Huang et al. (2017) ). An alternative formulation that supports continuous X and large feature dimension k has also been proposed recently (Wang et al. (2019) ).

Next we look at the convergence property of the ACE algorithm. Let f (X), g(Y ) be the true maximal correlation functions, and let f (X), g(Y ) be estimations computed with Algorithm 1 from m i.i.d. sampled training data. Similarly, denote by E[f (X)g(Y )] and Êm [ f (X)g(Y )] the true and estimated maximal correlations, respectively. Using Sanov's Theorem, we can show that for a small ∆ > 0, the probability that the ratio between the true and estimated maximal correlation is within 1 ± ∆ drops exponentially as the number of samples increases. Hence the ACE algorithm converges in exponential time. The following theorem gives the precise sampling complexity for k = 1. Theorem 2. For any random variables X and Y with joint probability distribution P Y X , if X and Y are not independent, then for any f : X → R and g :

Y → R such that E[f 2 (X)] = E[g 2 (Y )] = 1, we have that -lim ∆→0 + 1 δ 2 lim m→∞ 1 m log P Êm [ f (X)g(Y )] E[f (X)g(Y )] -1 ≥ ∆ = 1 2 E[f (X)g(Y )] 2 var[f (X)g(Y )]

for any given ∆ > 0.

APPENDIX C PROOF OF THEOREM 1:

To simplify the proof, we first consider the case when the feature function is 1-dimensional.i.e. f : X → R. We have the following lemma:

Lemma 4. Let f : X → R be an arbitrary feature function of X such that E[f (X)] = 0 and E[f (X) 2 ] = 1 , then || Bξ|| 2 F = E P Y [(E[f (X)|Y ]) 2 ]

where ξ is the feature vector corresponding to f . Proof. Since ξ(x) = P X (x)f (x), we have

|| Bξ|| 2 F = ξ T BT Bξ = y∈Y x∈X P Y X (y, x) P X (x) P Y (y) -P X (x) P Y (y) • P X (x)f (x) 2 = y∈Y x∈X P Y X (y, x) P Y (y) • f (x) - x∈X f (x)P X (x) 2 • P Y (y) = y∈Y (E[f (X)|Y = y] -E[f (x)]) 2 • P Y (y) = E P Y [(E[f (X)|Y ]) 2 ]

The last equality uses the assumption that E[f (x)] = 0.

Theorem 3 (1D version of Theorem 1). Given P X|Y =0 , P X|Y =1 ∈ N X (P 0,X ) and features f :

X → R such that E [f (X)] = 0 and E[f (X) 2 ] = 1, then there exists some constant c independent of f such that E f = c Bξ 2 F (5) Proof. From E[f (X)] = P Y (0)E[f (X)|Y = 0] + P Y (1)E[f (X)|Y = 1] = 0,

we first derive the following properties of the conditional expectations of f (x):

E[f (X)|Y = 1] = - P Y (0) P Y (1) E[f (X)|Y = 0] E[f (X)|Y = 0] = - P Y (1) P Y (0) E[f (X)|Y = 1]

On the R.H.S. of Equation 5, we apply Lemma 4 to write

Bξ 2 F = E P Y (E [f (X)|Y ]) 2 = P Y (0)P Y (1) + P Y (1) 2 P Y (0) (E [f (X)|Y = 1]) 2

Next consider the L.H.S. of the equation, by Lemma 2, we have

E(h) = 2 8 ξ, φ 1 -φ 2 2 + o( 2 ) = c 0 ξ, φ 1 -φ 2 2 for some constant c 0 . c 0 ξ, φ P1 -φ P2 2 =c 0 x∈X P X|Y =0 (x) -P X|Y =1 (x) P X (x) • P X (x)f (x) 2 =c 0 (E [f (X)|Y = 0] -E [f (X)|Y = 1]) 2 =c 0 -(P Y (0) + P Y (1)) 2 P Y (0)P Y (1) • (E [f (X)|Y = 1])(E [f (X)|Y = 0]) =c 0 P Y (0) + P Y (1) P Y (0) 2 • (E [f (X)|Y = 1]) 2 =c 0 P Y (0) + P Y (1) P Y (0)P Y (1) P Y (0)P Y (1) + P Y (1) 2 P Y (0) • (E [f (X)|Y = 1]) 2 =c || Bξ|| 2 F

For k ≥ 2, Lemma 4 can be restated as follows:

Lemma 5. Let f : X → R k be a k-dimensional feature function of X, where f (x) = [f 1 (x), . . . , f k (x)]. Further we assume that E[f (X)] = 0 and cov(f

(X)) = E[f (X) T f (X)] = I . Then || BΞ|| 2 F = tr(cov(E[f (X)|Y ]))

where columns of Ξ are the information vectors corresponding to f 1 (x), . . . , f k (x).

Proof. First, note that

BΞ = P Y -1 P Y X P X -1 -P Y P X T P X f(X) = P Y [P Y ] -1 P Y X f(X) -1 • E[f (X)] T

where 1 is a column vector with all entries 1 and length |Y|. Since E[f (X)] = 0, we have

BΞ = P Y [P Y ] -1 P Y X f(X)

It follows that

|| BΞ|| 2 F =tr(Ξ T BT BΞ) =tr [P Y ] -1 P Y X f(X) T [P Y ] [P Y ] -1 P Y X f(X) =tr E P Y (E[f (X)|Y ]] T ) T (E[f (X)|Y ]] T ) =tr (cov(E[f (X)|Y ]))

Finally, we derive the multi-dimensional case for Theorem 1.

Proof of Theorem 1. Using Lemma 5 and a similar argument as in the simplified proof, the R.H.S of the equation becomes

|| BΞ|| 2 F =tr (cov(E[f (X)|Y ])) =tr E P Y (E[f (X)|Y ]] T ) T (E[f (X)|Y ]] T ) =P Y (0)E[f (X)|Y = 0]] T E[f (X)|Y = 0]] + P Y (1)E[f (X)|Y = 1]] T E[f (X)|Y = 1]] = P Y (0)P Y (1) + P Y (1) 2 P Y (0) (E [f (X)|Y = 1]) T (E [f (X)|Y = 1])

By Lemma 3, the L.H.S. of the equation can be written as

EQUATION

Equation ( 6) gives a more understandable expression of the normalization term. We can also write BΞ as follows:

BΞ = P Y -1 P Y X P X -1 -P Y P X T P X f(X) = P Y [P Y ] -1 P Y X f(X) -1 • E[f (X)] T

where 1 is a column vector with all entries 1 and length |Y|, we have

EQUATION

On the other hand,

|| BΞ(Ξ T Ξ) -1 2 || 2 F =tr (Ξ T Ξ) -1 2 Ξ T BT BΞ(Ξ T Ξ) -1 2 =tr (Ξ T Ξ) -1 Ξ T BT BΞ (8) =tr cov(f (X)) -1 cov(E[f (X)|Y ])

The last equality is derived by substituting ( 6) and ( 7) into (8).

APPENDIX E H-SCORE AND SOFTMAX REGRESSION:

In softmax regression, given m training examples {(x (i) , y (i) )} m i=1 , the cross-entropy loss of the model is

EQUATION

Minimizing is equivalent to minimizing D P Y X ||P X Q Y |X where P Y X is the joint empirical distribution of (X, Y ).

Using information geometry, it can be shown that under a local assumption

argmin f,θ D P Y X ||P X Q Y |X = argmin Ψ,Φ 1 2 B -ΨΦ T 2 F + o( 2 ) (12)

which reveals a close connection between log loss and the modal decomposition of B. In consequence, it is reasonable to measure the classification performance with B -ΨΦ T 2 F given a pair of (f, θ) associated with (Ψ, Φ).

In the context of estimating transferability, we are interested in a one-sided problem, where Φ S is given by the source feature and Ψ becomes the only variable. Training the network is equivalent to finding the optimal weight Ψ * that minimizes the log-loss. By taking the derivative of the Objective function with respect to Ψ, we get

EQUATION

Substituting ( 14) in the Objective of ( 13), we can derive the following close-form solution for the log loss.

BT T BT 2 F -BT Φ S (Φ T S Φ S ) -1 2 2 F (15)

The first term in ( 15) is fixed given T T while the second term has exactly the form of H-score. This implies that log loss is negatively linearly related to H-score.

We demonstrates this relationship experimentally, using a collection of synthesized tasks (Figure 11 ).

In particular, the target task is generated based on a random stochastic matrix P Y0|X , and 20 source tasks are generated with the conditional probability matrix P Yi|X = P Y0|X + iλI for some positive constant λ.

The universal minimum error probability features for each source task are used as the source features f Si (x), while the respective log-loss are obtained through training a simple neural network in Figure 2 with cross-entropy loss. The relationship is clearly linear with a constant offset.

APPENDIX F DTM AND MUTUAL INFORMATION:

Proposition 1. Under the local assumption that P X|Y ∈ N (P X ), mutual information I(X

; Y ) = 1 2 || B|| 2 F + o( 2 )

, where B of the DTM matrix of X and Y .

Proof. First, we define φ X|Y y

(x) = P X|Y (x|y)-P X (x) √ P X (x)

and let Φ X|Y ∈ R |X |×|Y| denote its matrix version. Then we have

Φ X|Y [ P Y ] = [ P X ] -1 (P XY -P X )[ P Y ] = BT

Next, we express the mutual information in terms of information vector φ X|Y ,

I(X; Y ) = I(Y ; X) = y∈Y P Y (y)D KL (P X|Y ||P X ) = 2 2 y∈Y P Y (y)||φ X|Y y || 2 + o( 2 ) = 1 2 || Φ X|Y [ P Y ]|| 2 F + o( 2 ) = 1 2 || B|| 2 F + o( 2 )

APPENDIX G SUPPLEMENTARY RESULTS ON EXPERIMENT 5.2 

G.2 LABEL QUANTIZATION:

During the quantization process of the pixel-to-pixel task labels (ground truth images), we are primarily concerned with two factors: computational complexity and information loss. Too much information loss will lead to bad approximation of the original problems. On the other hand, having little information loss requires larger cluster size and computation cost.

Figure (14) shows that even after quantization, much of the information in the images are retained.

To test the sensitivity of the cluster size, we used cluster centroids to recover the ground truth image pixel-by-pixel. The 3D occlusion Edge detection results on a sample image is shown in Figure 15 .

When the cluster number is set to N = 5 (right), most detected Edges in the ground truth image (left) are lost. We found that N = 16 strikes a good balance between recoverability and computation cost. 

:

Test data and code can be found at https://goo.gl/uoXj8m

Figures and Tables:

Figure 1: A simple neural network topology for transfer learning

Figure 2: a) Network topology of linear feature transfer. b) Architecture for the neural network implementation of the soft HGR problem

Figure 4.a compares the H-score of transferring from five different layers (4a-4f) in the source network with the target log-loss and test accuracy of the respective features. As H-score increases, log-loss of the target network decreases almost linearly while the training and testing accuracy increase. Such behavior is consistent with our expectation that H-score reflects the learning performance of the target task. We also demonstrated that target sample size does not affect the relationship between H-score and log-loss (Figure 4.b).

Figure 4: H-score and transferability vs. the empirical transfer performance measured by log-loss, training and testing accuracy. a.) Performance of ImageNet-1000 features from layers 4a-4f for Cifar-100 classification. b.) Effect of sample size (5K-50K) on H-score for Cifar 100. c.): Transferability from ImageNet-1000 to 4 different target tasks based on Cifar-100.

Figure 5: Ground truth of different tasks for a given query image.

Figure 6: Task descriptions

Figure 8: Ranking of second order transferability for all recognition tasks Figure 9: First and second order pixel-wise transferability to Depth.

Figure10: The binary hypothesis testing problem. The blue curves shows the probility density functions for P 1 and P 2 . The rejection region and the acceptance region are highlighted in red and blue, respectively. The vertical line indicates the decision threshold.

||P1) where P * 1 = argmin P ∈A c D(P ||P 1 ) and A c (T ) = {x m : D(P x m ||P 2 ) -D(P x m ||P 1 ) < 1 m log T } denotes the rejection region. Similarly, for type II error β = P 2 (A) ≈ 2 -mD(P * 2 ||P2) where P * 2 = argmin P ∈A D(P ||P 2 ) and A = {x m : D(P x m ||P 2 ) -D(P x m ||P 1 ) > 1 m log T } represents the acceptance region. (See Figure 10) The overall probability of error is P (m) e = αP r(H 0 ) + βP r(H 1 ) and the best achievable exponent in the Bayesian probability of error (a.k.a. Chernoff exponent) is defined as: E = lim m→∞ min A⊆X m -1 m log P (m) e

Figure 11: Comparing task transferability (H-score) and transfer log-loss on synthesized tasks.

some detailed results on the comparison between H-score and the affinity score in Zamir et al. (2018) for pairwise transfer.The results of the classification tasks are shown in Figure12and the results of Depth is shown in 13. We can see in general, although affinity and transferability have totally different value ranges, they tend to agree on the top few ranked tasks.

Figure 12: Source task transferability ranking for classification tasks. For each target task, the left figure shows H-score results, and the right figure shows task affinity results.

Figure 13: Comparison between source task rankings for Depth. with H-score results on the left and affinity scores Zamir et al. (2018) on the right. The Top 3 transferable source tasks in both methods are the same: Depth, Image Reshading and 3D Occlusion Edges.

Figure 14: Quantization. Recover is done with the centroid of corresponding cluster of each pixel.

Figure 15: Effect of quantization cluster size for 3D occlusion Edge detection.

Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Advances in neural information processing systems, pp. 3320-3328, 2014. Amir Zamir, Alexander Sax, William Shen, Leonidas Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. Computer Vision and Pattern Recognition (CVPR), 2018.

Table content: <table><tr><td>Yu Zhang. Heterogeneous-neighborhood-based multi-task local learning algorithms. In Advances in</td></tr><tr><td>neural information processing systems, pp. 1896-1904, 2013.</td></tr><tr><td>APPENDIX A INFERENCE USING LOCAL INFORMATION GEOMETRY</td></tr><tr><td>A.1 A PRIMER ON ERROR EXPONENTS</td></tr><tr><td>To begin with, consider the binary hypothesis testing problem over m i.i.d. sampled observations</td></tr><tr><td>{x (i) } m i=1</td></tr></table>

G.1 COMPARISON OF H-SCORES AND AFFINITIESTable1, with columns representing source tasks and rows representing target tasks. For each target task, the upper row shows our results while the lower one shows the results inZamir et al. (2018). Score values are included in parenteses. Transferability ranking comparison, between H-score's estimation and task affinity

Table content: <table><tr><td>Tasks</td><td>2D Edges</td><td colspan="2">2D Keypoints 3D Edges</td><td colspan="2">3D Keypoints Reshading</td><td>Depth</td><td colspan="2">Object Class. Scene Class.</td></tr><tr><td>2D Edges</td><td>1 (1.8216)</td><td>2 (1.7334)</td><td>5 (1.5704)</td><td>6 (1.5696)</td><td>4 (1.6146)</td><td>3 (1.6201)</td><td>7 (1.5097)</td><td>8 (1.4402)</td></tr><tr><td/><td>1 (0.0389)</td><td>2 (0.0117)</td><td colspan="6">4 (5.8920e-5) 3 (8.8011e-5) 7 (2.9001e-5) 8 (2.2110e-5) 5 (4.9141e-5) 6 (4.8720e-5)</td></tr><tr><td>2D Keypoints</td><td>2 (1.6698)</td><td>1 (1.7859)</td><td>7 (1.5248)</td><td>5 (1.5287)</td><td>4 (1.5481)</td><td>3 (1.5632)</td><td>6 (1.5253)</td><td>8 (1.4725)</td></tr><tr><td/><td>2 (0.0002)</td><td>1 (0.0542)</td><td colspan="5">7 (7.7797e-5) 5 (8.1029e-5) 6 (7.8464e-5) 8 (7.2724e-5) 3 (0.0002)</td><td>4 (0.0001)</td></tr><tr><td>3D Edges</td><td>5 (1.4828)</td><td>4 (1.4910)</td><td>3 (1.5167)</td><td>7 (1.4701)</td><td>2 (1.5405)</td><td>1 (1.6739)</td><td>8 (1.4644)</td><td>6 (1.4730)</td></tr><tr><td/><td>6 (0.0117)</td><td>7 (0.0108)</td><td>1 (0.1179)</td><td>2 (0.0734)</td><td>4 (0.0622)</td><td>3 (0.0636)</td><td>8 (0.0094)</td><td>5 (0.0151)</td></tr><tr><td>3D Keypoints</td><td>6 (1.5375)</td><td>5 (1.5466)</td><td>4 (1.5910)</td><td>3 (1.6456)</td><td>1 (1.7198)</td><td>2 (1.7122)</td><td>7 (1.4709)</td><td>8 (1.4121)</td></tr><tr><td/><td>5 (0.0141)</td><td>6 (0.0136)</td><td>2 (0.0531)</td><td>1(0.1275)</td><td>3 (0.0400)</td><td>4 (0.0247)</td><td>7 (0.0132)</td><td>8 (0.0121)</td></tr><tr><td>Reshading</td><td>5 (1.5504)</td><td>6 (1.5426)</td><td>3 (1.8174)</td><td>4 (1.7990)</td><td>1 (2.2339)</td><td>2 (2.1200)</td><td>7 (1.4774)</td><td>8 (1.3804)</td></tr><tr><td/><td>6 (0.0147)</td><td>8 (0.0143)</td><td>2 (0.0781)</td><td>4(0.0545)</td><td>1 (0.1121)</td><td>3 (0.0765)</td><td>7 (0.0144)</td><td>5 (0.0174)</td></tr><tr><td>Depth</td><td>6 (1.6542)</td><td>5 (1.6870)</td><td>3 (1.8504)</td><td>4 (1.8176)</td><td>2 (2.1700)</td><td>1 (2.2441)</td><td>7 (1.6008)</td><td>8 (1.5099)</td></tr><tr><td/><td>7 (0.0175)</td><td>8 (0.0154)</td><td>3 (0.0595)</td><td>4 (0.0617)</td><td>2 (0.0867)</td><td>1 (0.0989)</td><td>6 (0.0217)</td><td>5 (0.0237)</td></tr><tr><td>Object Class.</td><td>5 (22.866)</td><td>4 (23.627)</td><td>7 (22.371)</td><td>8 (21.950)</td><td>6 (22.452)</td><td>3 (23.697)</td><td>1 (33.468)</td><td>2 (28.013)</td></tr><tr><td/><td>7 (0.0205)</td><td>6 (0.0217)</td><td>3 (0.0350)</td><td>4 (0.0318)</td><td>5 (0.0286)</td><td>8 (0.0147)</td><td>1 (0.0959)</td><td>2 (0.0774)</td></tr><tr><td>Scene Class.</td><td>5 (14.575)</td><td>4 (15.074)</td><td>7 (14.206)</td><td>8 (13.801)</td><td>6 (14.332)</td><td>3 (15.</td><td/><td/></tr></table>

Peer review (iclr2019):
 The authors propose an information theoretic metric to determine a priori if a representation learned from a source task can be useful when learning another task. This is a timely topic and being able to compute such as metric between tasks upfront would be of great interest. While the motivation and contributions of the paper are clearly stated, a number of questions remain. Central concepts like error exponent or maximal HGR correlation are mentioned in passing. The former is important to understand whether (1) makes sense and the latter is a fundamental quantity for this work. The surprising fact is that HGR is not discussed at all, nor is there any intuition provided of what this quantity represents. While the proposed H-score is attractive when a source task has to be selected, as the denominator of the task transferability itself does not need to be computed, it is not straightforward to compute this quantity in general. The authors suggest to use the alternative conditional expectation (ACE) algorithm in order to optimize (2). ACE is not discussed in any detail (e.g., how accurate is this procedure; what are the choices and/or trade-offs if any?) and (2) is not justified. Overall, I felt section 4.2 was relatively inaccessible, but important as it indicates whether the proposed metric is of any use in practice. Finally, I did not understand the argument that says the H-score is to be prepared over the mutual information. To me the mutual information is still the golden standard. It was also not clear why the proposed approach would not straightforwardly apply to non classification problems as suggested in the future work.