summaries: This paper proposes a framework for few-sample knowledge distillation of convolution neural networks. The basic idea is to fit the output of the student network and that of the teacher network layer-wisely. Such a regression problem is parameterized by a 1x1 point-wise convolution per layer (i.e. minimizing the fitting objective over the parameters of 1x1 convolutions). The author claims such an approach, called FSKD, is much more sample-efficient than previous works on knowledge distillation. Besides, it is also fast to finish the alignment procedure as the number of parameters is smaller than that in previous works. The sample efficiency is confirmed in the experiments on CIFAR-10, CIFAR-100 and ImageNet with various pruning techniques. In particular, FSKD outperforms the FitNet and fine-tuning by non-trivial margins if only small amount of samples are provided (e.g. 100).

summaries: In this paper, an efficient re-training algorithm for neural networks is proposed. The essence is like Hinton's distillation, but in addition to use the output of the last layer, the outputs of intermediate layers are also used. The core idea is to add 1x1 convolutions to the end of each layer and train them by fixing other parameters. Since the number of parameters to train is small, it performs well with the small number of samples such as 500 samples.

abstractText: Current knowledge distillation methods require full training data to distill knowledge from a large "teacher" network to a compact "student" network by matching certain statistics between "teacher" and "student" such as softmax outputs and feature responses. This is not only time-consuming but also inconsistent with human cognition in which children can learn knowledge from adults with few examples. This paper proposes a novel and simple method for knowledge distillation from few samples. Taking the assumption that both "teacher" and "student" have the same feature map sizes at each corresponding block, we add a 1× 1 conv-layer at the end of each block in the student-net, and align the block-level outputs between "teacher" and "student" by estimating the parameters of the added layer with limited samples. We prove that the added layer can be absorbed/merged into the previous conv-layer to formulate a new conv-layer with the same size of parameters and computation cost as the previous one. Experiments verify that the proposed method is very efficient and effective to distill knowledge from teacher-net to student-net constructing in different ways on various datasets.

authors:
Jimmy Ba
Rich Caruana

title: Do deep nets really need to be deep

venue: In NIPS,

authors:
Evgeniy Bart
Shimon Ullman

title: Cross-generalization: Learning novel classes from a single example by feature replacement

authors:
Tianqi Chen
Ian Goodfellow
Jonathon Shlens

title: Net2net: Accelerating learning via knowledge transfer

venue: In ICLR,

title: Xception: Deep learning with depthwise separable convolutions

venue: arXiv preprint arXiv:1610.02357,

authors:
M. Courbariaux
Y. Bengio
Jean-Pierre David

title: Binarynet: Training deep neural networks with weights and activations constrained to +1 or -1

authors:
Elliot J Crowley
Gavin Gray
Amos Storkey

title: Moonshine: Distilling with cheap convolutions

venue: arXiv preprint arXiv:1711.02613,

authors:
Emily Denton
Zaremba
Yann Lecun

title: Exploiting linear structure within convolutional networks for efficient evaluation

authors:
Li Fei-Fei
Rob Fergus
Pietro Perona

title: One-shot learning of object categories

venue: IEEE Trans PAMI,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In ICML,

authors:
Jianbo Guo
Yuxi Li
Weiyao Lin
Yurong Chen
Jianguo Li

title: Network decoupling: From regular to depthwise separable convolutions

authors:
Suyog Gupta
Ankur Agrawal
Kailash Gopalakrishnan

title: Deep learning with limited numerical precision

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

authors:
Song Han
Huizi Mao
Bill Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

authors:
K. He
X. Zhang
J. Sun

title: Deep residual learning for image recognition

authors:
G. Hinton
O. Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Geoffrey Hinton
Li Deng
Dong Yu

title: Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups

venue: IEEE Signal Processing Magazine,

authors:
Mingyi Hong
Xiangfeng Wang
Meisam Razaviyayn
Zhi-Quan Luo

title: Iteration complexity analysis of block coordinate descent methods

venue: Mathematical Programming,

authors:
Gao Huang
Zhuang Liu
Kilian Q Weinberger
Laurens van der Maaten

title: Densely connected convolutional networks

authors:
Zehao Huang
Naiyan Wang

title: Like what you like: Knowledge distill via neuron selectivity transfer

venue: arXiv preprint arXiv:1707.01219,

authors:
M. Jaderberg
A. Vedaldi
A. Zisserman

title: Speeding up convolutional neural networks with low rank expansions

venue: In BMVC,

authors:
Y. Kim
E. Park
S. Yoo

title: Compression of deep convolutional neural networks for fast and low power mobile applications

authors:
Akisato Kimura
Zoubin Ghahramani
Koh Takeuchi

title: Few-shot learning of neural networks from scratch by pseudo example optimization

authors:
A. Krizhevsky
G. Hinton

title: Imagenet classification with deep convolutional neural networks

authors:
Brenden Lake
Ruslan Salakhutdinov
Jason Gross

title: One shot learning of simple visual concepts

venue: In Proceedings of the Annual Meeting of the Cognitive Science Society,

authors:
Hao Li
Asim Kadav
Durdanovic I

title: Pruning filters for efficient convnets

venue: arXiv preprint arXiv:1608.08710,

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen

title: Learning efficient convolutional networks through network slimming

venue: In ICCV,

authors:
Raphael Gontijo Lopes
Stefano Fenu
Thad Starner

title: Data-free knowledge distillation for deep neural networks

venue: arXiv preprint arXiv:1710.07535,

authors:
J. Luo
J. Wu
W. Lin

title: Thinet: A filter level pruning method for deep neural network compression

authors:
Tomáš Mikolov
Martin Karafiát
Lukáš Burget

title: Recurrent neural network based language model

venue: In INTERSPECH,

authors:
Vinod Nair
Geoffrey Hinton

title: Rectified linear units improve restricted boltzmann machines

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

venue: In ECCV,

authors:
Sachin Ravi
Hugo Larochelle

title: Optimization as a model for few-shot learning

authors:
Adriana Romero
Nicolas Ballas
Samira Ebrahimi Kahou

title: Fitnets: Hints for thin deep nets

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

authors:
Leslie N Smith
Emily M Hand
Timothy Doster

title: Gradual dropin of layers to train very deep neural networks

authors:
Suraj Srinivas
Francois Fleuret

title: Knowledge transfer with jacobian matching

venue: arXiv preprint arXiv:1803.00443,

authors:
Oriol Vinyals
Charles Blundell
Tim Lillicrap

title: Matching networks for one shot learning

authors:
Junho Yim
Donggyu Joo
Jihoon Bae

title: A gift from knowledge distillation: Fast optimization, network minimization and transfer learning

authors:
X. Zhang
J. Zou
J. Sun

title: Accelerating very deep convolutional networks for classification and detection

venue: IEEE TPAMI,

authors:
Ying Zhang
Tao Xiang
Timothy Hospedales

title: Deep mutual learning

authors:
B. Zoph
Quoc V Le

title: Neural architecture search with reinforcement learning

heading: 1 INTRODUCTION

text:
Deep neural networks (DNNs) have demonstrated extraordinary success in a variety of fields such as computer vision (Krizhevsky & Hinton, 2012; He et al., 2016), speech recognition (Hinton et al., 2012), and natural language processing (Mikolov et al., 2010). However, DNNs are resource-hungry which hinders their wide deployment to some resource-limited scenarios, especially low-power embedded devices in the emerging Internet-of-Things (IoT) domain. To address this limitation, extensive works have been done to accelerate or compress deep neural networks. Putting those works on designing (Chollet, 2016) or automatically searching efficient network architecture aside (Zoph & Le, 2016), most studies try to optimize DNNs from four perspectives: network pruning (Han et al., 2016; Li et al., 2016), network decomposition (Denton et al., 2014; Jaderberg et al., 2014), network quantization (or low-precision networks) (Gupta et al., 2015; Courbariaux et al., 2016; Rastegari et al., 2016) and knowledge distillation (Hinton et al., 2015; Romero et al., 2015).
Among these method categories, knowledge distillation is somewhat different due to the utilization of information from the pre-trained teacher-net. The concept was proposed by (Bucila et al., 2006; Ba & Caruana, 2014; Hinton et al., 2015) for transferring knowledge from a large "teacher" model to a compact yet efficient "student" model by matching certain statistics between "teacher" and "student". Further research introduced various kinds of matching mechanisms in the field of DNN optimization. The distillation procedure designs a loss function based on the matching mechanisms and enforces the loss during a full training process. Hence, all these methods usually require time-consuming training procedure along with fully annotated large-scale training dataset.
Meanwhile, some network pruning (Li et al., 2016; Liu et al., 2017) and decomposition (Zhang et al., 2016; Kim et al., 2016) methods can produce extremely small networks, but with large accuracy drops so that time-consuming fine-tuning is required for possible accuracy recovery. Usually, it may still not be able to recover the accuracy drops with the original cross-entropy loss due to its low representation capacity. Hence, knowledge distillation may be used to alleviate the problem, since the compact student-net can sometimes be trained to match the performance of the teacher-net. For instance, Crowley et al. (2017) uses cheap group convolutions and pointwise convolutions to build a small student-net and adopts knowledge distillation to transfer knowledge from a full-sized "teacher-net" to the "student-net". However, it still suffers from high training cost.
As is known, children can learn knowledge concept from adults with few examples. This cognition phenomenon has motivated the development of the few-shot learning (Fei-Fei et al., 2006; Bart & Ullman, 2005), which aims to learn information about object categories from a few training samples, and focuses more on image classification task. Nevertheless, it inspires people to consider the possibility of knowledge distillation from few samples. Some recent works on knowledge distillation address this problem by constructing "pseudo" training data (Kimura et al., 2018; Lopes et al., 2017) with complicated heuristics and heavy engineering, which are still costly.
This paper proposes a novel and simple three-step method for few-sample knowledge distillation (FSKD) as illustrated in Figure 1, including student-net design, teacher-student alignment, and absorbing added conv-layer. We assume that both "teacher" and "student" nets have the same feature map sizes at each corresponding block. However, the relatively small student-net can be obtained in various ways, such as pruning/decomposing the teacher-net, and fully redesigned network with random initialization. We add a 1×1 conv-layer at the end of each block of the student-net and align the block-level outputs between "teacher" and "student", which is done by estimating the parameters of the added layer with few samples using least square regression. Since the added 1×1 conv-layers have relatively few parameters, we can get a good approximation from a small number of samples. We further prove that the added 1×1 conv-layer can be absorbed/merged into the previous conv-layer when certain conditions fulfill, so that the new conv-layer has the same number of parameters and computation cost as the older/previous one.
We argue that FSKD has many potential applications, especially when fine-tuning or full training is not feasible in practice. We just name a few such cases below. First, edge devices have limited computing resources, while FSKD offers the possibility of on-device learning to compress deep models with a limited number of samples. Second, FSKD may help software/hardware vendors optimizing the deep models from their customers when full training data is unavailable due to privacy or confidential issues. Third, FSKD enables fast model deployment optimization when there is a strict time budget. Our major contributions can be summarized as follows:
(1) To the best of our knowledge, we are the first to show that knowledge distillation can be done with few samples within minutes on a desktop PC.
(2) The proposed FSKD method is widely applicable not only for fully redesigned student-nets but also for compressed networks from pruning and decomposition-based methods.
(3) We demonstrate significant performance improvement of the student-net by FSKD, comparing to existing distillation techniques on various datasets and network structures.

heading: 2 RELATED WORK

text:
Knowledge Distillation (KD) transfers knowledge from a pre-trained large "teacher" network (or even an ensemble of networks) to a small "student" network, for facilitating the deployment at test time. Originally, this is done by regressing the softmax output of the teacher model (Hinton et al., 2015). The soft continuous regression loss used here provides richer information than the label based loss, so that the distilled model can be more accurate than training on labeled data with cross-entropy loss. Later, various works have extended this approach by matching other statistics, including intermediate feature responses (Romero et al., 2015; Chen et al., 2016), gradient (Srinivas & Fleuret, 2018), distribution (Huang & Wang, 2017), Gram matrix (Yim et al., 2017), etc. Deep mutual learning (Zhang et al., 2018) trains a cohort of student-nets and teaches each other collaboratively with model distillation throughout the training process. All these methods require a large amount of
data (known as the “transfer set”) to transfer the knowledge, whereas we aim to provide a solution with a limited number of samples. We need emphasize that FSKD has a quite different philosophy on aligning intermediate responses to the closest knowledge distillation method FitNet (Romero et al., 2015). FitNet re-trains the whole student-net with intermediate supervision using a larger amount of data, while FSKD only estimates parameters for the added 1× 1 conv-layer with few samples. We will verify in experiments that FSKD is not only more efficient but also more accurate than FitNet.
Network Pruning methods obtain a small network by pruning weights from a trained larger network, which can keep the accuracy of the larger model if the prune ratio is set properly. Han et al. (2015) proposes to prune the individual weights that are near zero. Recently, channel pruning has become increasingly popular thanks to its better compatibility with off-the-shelf computing libraries, compared with weights pruning. Different criteria have been proposed to select the channel to be pruned, including norm of weights (Li et al., 2016), scales of multiplicative coefficients (Liu et al., 2017), statistics of next layer (Luo et al., 2017), etc. It is usually required iterative loop between pruning and fine-tuning for achieving better pruning ratio and speedup. Similar gradually adjusting trick is also applied to train very-deep neural networks (Smith et al., 2016). Meanwhile, Network Decomposition methods try to factorize heavy layers in DNNs into multiple lightweight ones. For instance, it may adopt low-rank decomposition to fully-connection layers (Denton et al., 2014), and different kinds of tensor decomposition to conv-layers (Zhang et al., 2016; Kim et al., 2016). However, aggressive network pruning or network decomposition usually lead to large accuracy drops, thus fine-tuning is required to alleviate those drops (Li et al., 2016; Liu et al., 2017; Zhang et al., 2016). As aforementioned, KD is more accurate than directly training on labeled data, it is of great interest to explore KD on extremely pruned or decomposed networks, especially under the few-sample setting.
Learning with few samples has been extensively studied under the concept of one-shot or few-shot learning. One category of methods directly model few-shot samples with generative models (Fei-Fei et al., 2006; Lake et al., 2011), while most others study the problem under the notion of transfer learning (Bart & Ullman, 2005; Ravi & Larochelle, 2017). In the latter category, meta-learning methods (Vinyals et al., 2016; Finn et al., 2017) solve the problem in a learning to learn fashion, which has been recently gaining momentum due to their application versatility. Most studies are devoted to the image classification task, while it is still less-explored for knowledge distillation from few samples. Recently, some works tried to address this problem. Kimura et al. (2018) constructs pseudo-examples using the inducing point method, and develops a complicated algorithm to optimize the model and pseudo-examples alternatively. Lopes et al. (2017) records per-layer meta-data for the teacher-net in order to reconstruct a training set, and then adopts a standard training procedure to obtain the student-net. Both are very costly due to the complicated and heavy training procedure. On the contrary, we aim for a simple solution for knowledge distillation from few samples.

heading: 3 FEW-SAMPLE KNOWLEDGE DISTILLATION (FSKD)

heading: 3.1 OVERVIEW

text:
Our FSKD method consists of three steps as shown in Figure 1. First, we design a student-net either by pruning/decomposing the teacher-net, or by fully redesigning a small student-net with random initialization. Second, we add a 1×1 conv-layer at the end of each block of the student-net and align the block-level outputs between "teacher" and "student" by estimating the parameters for the added layer from few samples. Third, we absorb the added 1×1 conv-layer into the previous conv-layer without introducing extra parameters and computations into the student-net.
Two reasons make this idea work efficiently. First, the 1×1 conv-layers have relatively few parameters, which do not require too many data for the estimation. Second, the block-level output from teacher-net provides rich information as shown in FitNet (Romero et al., 2015). Below, we will first provide the theoretical derivation why the added 1×1 conv-layer could be absorbed/merged into the previous conv-layer. Then we provide details on how we do the block-level output alignment.

heading: 3.2 ABSORBABLE 1× 1 CONV-LAYER

text:
Let’s first give some mathematic notions for different kinds of convolutions before moving to the theoretical derivation. A regular convolution consists of multi-channel and multi-kernel filters which build both cross-channel correlations and spatial correlations. Formally, a regular convolution layer
can be represented by a 4-dimensional tensor W ∈ Rno×ni×k×k, where no and ni are the number of output and input channels respectively, and k × k is the squared spatial kernel size. The point-wise (PW) convolution, also known as 1× 1 convolution (Lin et al., 2014) can be represented by a tensor P ∈ Rno×ni×1×1, which is actually degraded from a 4-dimensional tensor to a 2-dimensional matrix. The depth-wise (DW) convolution (Chollet, 2016) does per-channel 2D convolution for each input channel, so that it can be represented by a tensor D ∈ R1×ni×k×k. Due to no-correlation among output channels, it usually follows by a point-wise convolution to model their correlations. This combination (DW + PW) is also named as depth-wise separable convolution by Chollet (2016).
Theorem 1. A pointwise convolution with tensor Q ∈ Rn′o×n′i×1×1 can be absorbed into the previous convolution layer with tensor W ∈ Rno×ni×1×1 to obtain the absorbed tensor W′ = Q◦W, where ◦ is absorbing operator and W′ ∈ Rn′o×ni×k×k if the following conditions are satisfied.
c1. The output channel number of W equals to the input channel number of Q, i.e., no = n′i. c2. No non-linear activation layer like ReLU (Nair & Hinton, 2010) between W and Q.
Due to the space limitation, we put the proof and the detailed form of the absorbing operator in Appendix-A. The number of output channels of W′ is n′o, which is different from that of W (i.e., no). It is easy to have the following corollary. Corollary 1. When the following condition is satisfied for Q,
c3. the number of input and output channels of Q equals to the number of output channel of W, i.e., n′i = n ′ o = no, Q ∈ Rno×no×1×1, the absorbed convolution tensor W′ has the same parameters and computation cost as W, i.e. both W′,W ∈ Rno×ni×k×k.
This condition is required not only for ensuring the same parameter size and computing cost, but also for ensuring current layer output size matching/connectable to next layer input size.

heading: 3.3 BLOCK-LEVEL ALIGNMENT AND ABSORBING

text:
Now we consider the knowledge distillation problem. Suppose Xs,Xt ∈ Rno×d are the block-level output in matrix form for the student-net and teacher-net respectively, where d is the per-channel feature map resolution size. We add a 1 × 1 conv-layer Q at the end of each block of student-net before non-linear activation, which satisfies condition c1 ∼ c3. As Q is degraded to the matrix form, it can be estimated with least squared regression as
Q∗ = argmin Q ∑N i=1 ‖Q ∗Xsi −Xti‖, (1)
where N is the number of samples used, and "*" here means matrix product. The number of parameters of Q is no × no, where no is the number of output channels in the block, which is usually not too large so that we can estimate Q with a limited number of samples.
Suppose there are M corresponding blocks in the teacher and student networks required to align, to achieve our goal, we need minimize the following loss function
L(Qj) = M∑ j=1 N∑ i=1 ‖Qj ∗Xsij −Xtij‖F , (2)
where Qj is the tensor for the added 1× 1 conv-layer of the j-th block. In practice, we optimize this loss with a block-coordinate descent (BCD) algorithm (Hong et al., 2017), which greedy handles each of the M terms/blocks in Equation 2 in the student-net sequentially as shown in algorithm 1 at Appendix-B, instead of optimizing this loss all together using standard SGD. The BCD algorithm for FSKD has the following advantages:
(1) The BCD algorithm processes each block greedy with a sequential update rule, and each Q can be solved much cheaper with a small number of samples by aligning the block-level responses between teacher and student networks, while SGD considers {Qj} all together which theoretically requires more data.
(2) The alignment procedure is very efficient, which can be usually done within several minutes for the entire network.
(3) The alignment procedure itself does not require class label information of input data due to its regression nature. However, if we fully redesign the student-net from scratch with random weights, we may leverage SGD on a few labeled samples to initialize the network. Our FSKD can still produce significant performance gains over SGD in this case.
(4) Our FSKD works extremely well for student-net obtained by aggressively pruning/decomposing the teacher-net. It beats the standard fine-tuning based solution on the number of data required, processing speed, and accuracy of the output student-net.

heading: 4 EXPERIMENT

text: We perform extensive experiments on different image classification datasets to verify the effectiveness of FSKD on various student-net construction methods. Student-nets can be obtained either from compressing the teacher-net or redesigning network structure with random initialization (termed “zero student network”). For the former case, we evaluate FSKD on three well-known compression methods, filter pruning (Li et al., 2016), network slimming (Liu et al., 2017), and network decoupling (Guo et al., 2018). We implement the code with PyTorch, and conduct experiments on a desktop PC with Intel i7-7700K CPU and one NVidia 1080TI GPU.

heading: 4.1 STUDENT NETWORK FROM COMPRESSING TEACHER NETWORK

heading: FILTER PRUNING

text:
We first obtain the student-nets using the filter pruning method (Li et al., 2016), which prunes out conv-filters according to the L1 norm of their weights. The L1 norm of filter weights are sorted and the smallest portion of filters will be pruned to reduce the number of filter-channels in a conv-layer.
We make a comprehensive study of VGG-16 (Simonyan & Zisserman, 2015) on CIFAR-10 dataset to evaluate the performance of FSKD along with different configuration settings. Following Li et al. (2016), we first prune half of the filters in conv1_1, conv4_1, conv4_2, conv4_3, conv5_1, conv5_2, conv5_3 while keeps the other layer unchanged (scheme-A). We also propose another more aggressive pruning scheme named scheme-B, which pruned 10% more filters in the aforementioned layers, and also pruned 20% filters for the remaining layers. Scheme-A prunes 64% of total parameters with 7% accuracy drop. Scheme-B prunes 77% of total parameters with almost 50% accuracy drop. We use those two pruned networks as student-nets in this study. 1
We illustrate in Figure 6 in Appendix-C how teacher and student are aligned at block-level. For the few-sample setting, we randomly select 100 (10 for each category) and 500 (50 for each category) images from the CIFAR-10 training set, and keep them fixed in all experiments. Table 1 lists the results of different methods of recovering a pruned network, including FitNet (Romero et al., 2015), fine-tuning with limited data and full training data (Li et al., 2016). Note that we optimize FSKD with two algorithms: FSKD-BCD uses the BCD algorithm on block-level and FSKD-SGD optimizes the loss (Equation 2) all together with SGD algorithm. In the BCD algorithm, we do not observe benefit for the iteration number T > 1 over T = 1, so that we set T = 1 in all our following experiments. This is consistent with the finding by (Hong et al., 2017) that the convergence is sublinear when each
1An extremely pruned case "scheme-C" is also provided in Appendix-D.
block is minimized exactly (here due to linear structure). Regarding the processing speed, FSKDBCD can be done in 19.3 seconds for student-net from scheme-B with 500 samples, while FitNet requires 157.3 seconds when converged, which is about 8.1× slower. This verifies our previous claim that FSKD is more efficient than FitNet. It can be seen that in the few-sample setting, FSKD-BCD provides better accuracy recovery than both FitNet and the fine-tuning procedure adopted in Li et al. (2016). For instance, for scheme-B with only 500 samples, FSKD can recover the accuracy from 47.9% to 91.2%, while few-sample fine-tuning can only recover the accuracy to 83.36%. When full training set available, it will take about 30 minutes for full fine-tuning to reach similar accuracy as FSKD. This demonstrates the big advantages of FSKD over full fine-tuning based solutions.
Figure 2 further studies the performance with different amount of training samples available. It can be observed that our FSKD-BCD keep outperforming FSKD-SGD, FitNet under the same training samples. In particular, FSKD-SGD and FitNet experience a noticeable accuracy drop when the number of samples is less than 100, while FSKD-BCD can still recover the accuracy of the pruned network to a high level. It is also interesting to note that fine-tuning experiences even larger accuracy drops than FitNet when the data amount is limited. This verifies that knowledge distillation methods like FitNet provide richer information than fine-tuning/re-training with label based loss.
As is shown, FSKD-BCD performs better and tends to be more sample-efficient than FSKD-SGD. Therefore, we choose it as the default algorithm, and denote it as FSKD for simplification in the following studies. We further illustrate the per-layer (block) feature responses difference between teacher and student before and after using FSKD in Figure 3a. Before applying FSKD, the correlation between teacher and student is broken due to the aggressive compression. However, after FSKD, the per-layer correlations between teacher and student are restored. This verifies the ability of FSKD for recovering lost information. We do see a decreasing trend with layer depth increased, which is possibly due to error accumulation through multiple convolutional layers. We also show the accuracy change during sequentially block-level alignment in Figure 3b, which clearly demonstrate the effectiveness of our sequentially block-by-block update in the BCD algorithm.

heading: NETWORK SLIMMING

text:
We then study the student-net from another channel pruning method named network slimming (Liu et al., 2017), which removes insignificant filter channels and corresponding feature maps using sparsified channel scaling factors. Network slimming consists of three steps: sparse regularized training, pruning and fine-tuning. Here, we replace the time-consuming fine-tuning step with our
FSKD, and follow the original paper (Liu et al., 2017) to conduct experiments to prune different networks on different datasets. We apply FSKD on networks pruned from VGG-19, ResNet-164, and DenseNet-40 (Huang et al., 2017), on both CIFAR-10 and CIFAR-100 datasets. Table 2 lists results on CIFAR-10, while Table 3 lists results on CIFAR-100. Note that the channel-prune-ratio (like 70% in Table 2) means the portion of channels that are removed in comparison to the total number of channels in the network. It shows that FSKD consistently outperforms FitNet and fine-tuning with a notable margin under the few-sample setting on all evaluated networks and datasets.

heading: NETWORK DECOUPLING

text:
Network decoupling (Guo et al., 2018) decomposes a regular convolution layer into the sum of several blocks, where each block consists of a depth-wise (DW) convolution layer and a point-wise (PW, 1×1) convolution layer. The ratio of compression increases as the number of blocks decreases, but the accuracy of the compressed model will also drop. Since each decoupled block ends with a 1×1 convolution, we can apply FSKD at the end of each decoupled block.
Following (Guo et al., 2018), we obtain student-nets by decoupling VGG-16 and ResNet-18 pretrained on ImageNet with different T values, where T stands for the number of DW + PW blocks that a conv-layer decouples out. Figure 7 in Appendix-C illustrates how teacher and student are aligned at block-level in this case. For VGG-16, we also decouple half of the conv-layer with T = 1 and the other half T = 2, and denote the case as "T = 1mix". We evaluate the resulted network performance on the validation set of the ImageNet classification task. We randomly select one image from each of the 1000 classes in ImageNet training set to obtain 1000 samples as our FSKD training set. Table 4 shows the top-1 accuracy of student-net before and after applying FSKD on VGG-16 and ResNet-18.
It is quite interesting to see that in the case of T = 1mix for VGG-16 and T = 2 for ResNet-18, we can recover the accuracy of student-net from nearly random guess (0.12%, 0.21%) to a much higher level (51.3% and 49.5%) with only 1000 samples. In all the other cases, FSKD can recover the accuracy of a highly-compressed network to be comparable with the original network. One possible explanation is that the highly-compressed networks still inherit some representation power from the teacher-net i.e., the depth-wise 3×3 convolution, while lacking the ability to output meaningful predictions due to the inaccurate/degraded 1 × 1 convolution. The FSKD calibrates the 1 × 1 convolution by aligning the block-level responses between "teacher" and "student" so that the lost information in 1× 1 convolution is compensated, and reasonable recovery is achieved 2.
2We thus make a bold hypothesis that point-wise is more critical for performance than depthwise, so that even depthwise 3× 3 conv-layers are initialized to be orthogonal from random data, training only pointwise conv-layers could provide enough accurate results. We verify this in Appendix-E.

heading: 4.2 ZERO STUDENT NETWORK

text:
Finally, we evaluate FSKD on fully redesigned student-net with a different structure from the teacher and random initialized parameters (named as zero student-net). We conduct experiments on CIFAR10 and CIFAR-100 with VGG-19 as the teacher-net and a shallower VGG-13 as the student-net. Due to the similar structure between VGG-13 and VGG-19, they can be easily aligned in block-level.
The random initialized network does not contain any information about the training set. Simply training this network using SGD with few samples will lead to poor generalization ability, as shown in Figure 4. We propose two schemes to combine FSKD in the training procedure: SGD+FSKD and FitNet+FSKD. In the SGD+FSKD case, we first use SGD to train the student-net (without using teacher-net information) on the given few labeled samples with 150 epochs (multi-step learning-rate decay at every 50 epochs from 0.01 to 0.0001), and then apply FSKD to the obtained student-net using the same few-sample set. We repeat these two steps until the training loss converges. In the FitNet+FSKD case, we keep the same few-sample set, and simply replace the SGD with FitNet (using teacher-net information) to add supervision on intermediate responses during training.
We compare the results from four different recovery methods: running SGD until convergence, SGD+FSKD, running FitNet until convergence, and FitNet+FSKD. In order to better simulate the few-sample setting, we do not apply data augmentation to the training set. We randomly pick 100, 200, 500, 1000 samples from the CIFAR-10 training set, and 500, 1000, 1500, 2000 samples from the CIFAR-100 training set, and keep these few-sample sets fixed in this study. Figure 4 shows the comparison results on the four methods and four few-sample sets. It shows that FSKD+SGD takes a big jump over pure SGD, and FSKD+FitNet also takes a big jump over pure FitNet. FSKD+SGD performs much better than FitNet on CIFAR-10, while this is not true on CIFAR-100. There are two possible reasons. First, we did not enable data augmentation so that few-sample SGD is underfitting, which provides much less information than what the student-net can get from the teacher-net in FitNet. Second, CIFAR-100 is much more difficult than CIFAR-10 so that the performance is more sensitive to the number of samples. However, FSKD+SGD can still achieve accuracy on par with FitNet. We should also note here that the zero-student-nets have accuracy gaps with the fully-trained teacher-nets on both CIFAR-10 and CIFAR-100. This is reasonable and acceptable, considering that we did not use data augmentation and trained the model with very few samples. Nevertheless, it still demonstrates the advantages of our FSKD over SGD and FitNet based methods. To further illustrate the benefit of FSKD over SGD, we visualize the convolution kernel (in terms of decoupled pointwise convolutions) before SGD, after SGD, and after SGD+FSKD in Appendix-F.

heading: 5 CONCLUSION

text: We proposed a novel and simple method for knowledge distillation from few samples (FSKD). The method works for student-nets constructed in various ways, including compression from teachernets and fully redesigned networks with random initialization on various datasets. Experiments demonstrate that FSKD outperforms existing knowledge distillation methods by a large margin in the few-sample setting, while requires significantly less computation budget. This advantage will bring many potential applications and extensions for FSKD.

heading: APPENDIX-A: PROOF OF THEOREM 1

text:
Proof. When W is a point-wise convolution with tensor W ∈ Rno×ni×1×1, both W and Q are degraded into matrix form. It is obvious that when condition c1 ∼ c3 satisfied, the theorem holds with W′ = Q ∗W in this case, where ∗ indicates matrix multiplication. When W is a regular convolution with tensor W ∈ Rno×ni×k×k, the proof is non-trivial. Fortunately, recent work on network decoupling (Guo et al., 2018) presents an important theoretic result as the basis of our derivation. Lemma 1. Regular convolution can be exactly expanded to a sum of several depth-wise separable convolutions. Formally, ∀W ∈ Rno×ni×k×k, ∃ {Pk,Dk}Kk=1, where Pk ∈ Rno×ni×1×1, Dk ∈ R1×ni×k×k,
s.t. (a)K ≤ k2; (b)W = ∑K
k=1 Pk ◦Dk,
(3)
where ◦ is the compound operation, which means performing Dk before Pk.
Please refer to Guo et al. (2018) for the details of proof for this Lemma. When W is applied to an input patch x ∈ Rni×k×k, we obtain a response vector y ∈ Rno as
y = W ⊗ x, (4) where yo = ∑ni
i=1 Wo,i ⊗ xi, o ∈ [no], i ∈ [ni], and ⊗ here means convolution operation. Wo,i = W[o, i, :, :] is a tensor slice along the i-th input and o-th output channels, xi = x[i, :, :] is a tensor slice along the i-th channel of 3D tensor x.
When point-wise convolution Q is added after Q without non-linear activation between them, we have y′ = Q ◦ (W ⊗ x). (5) With Lemma-1, we have
y′ = (Q ◦ ∑K
k=1 Pk ◦Dk)⊗ x = ( ∑K k=1 (Q ∗Pk) ◦Dk)⊗ x (6)
As both Q and Pk are degraded into matrix form, denoting P ′ k = Q∗Pk and W′ = ∑K k=1 P ′
k ◦Dk, we have y′ = W′ ◦ x. This proves the case when W is a regular convolution.

heading: APPENDIX-B: ALGORITHM OF BLOCK-LEVEL ALIGNMENT FOR FSKD

text:
The block-level alignment algorithm for FSKD is in fact a block-coordinate descent (BCD) algorithm with greedy sequential block-level update rule, as shown in algorithm 1.
Algorithm 1: Block-coordinate descent algorithm for FSKD 1 Data: Given student-net s and teacher-net t and input data {Xi}Ni=1, 2 number of aligned blocks M , number of iterations T 3 for k = 1 : T do 4 Random flip input dataset to obtain {X ′i}Ni=1; 5 for j = 1 : M do 6 Feed {X ′i}Ni=1 to the end of j-th block for teacher-net t and and current student-net s; 7 Obtain response {Xtij} and {Xsij} from j-th block; 8 Add 1× 1 conv-layer with tensor Qj to the end of j-th block of student-net s (before ReLU); 9 Solve Qj with least-square regression based on Equation 1;
10 Merge Qj into previous conv-layer Lj with tensor Wj to obtain new tensor W′j based on Theorem 1 for student-net; 11 Update j-th block of current student-net s; 12 end 13 end 14 Result: Absorbed conv-layers {W′j}Mj=1 and updated student-net s′.
student-net
teacher-net
Decoupling
L2-loss 3x3
3x3
3x3
3x3
1x1
1x1
Conv: W Rn×m×3×3
Added 1x1DW PW
Figure 7: Illustration of FSKD on network decoupling. At each block, we decouple regular-conv in teacher-net into a sum of depthwise + pointwise conv-layers as the block of student-net, and align the feature maps of student-net to that of teacher-net by adding a 1×1 convlayer (red-color) with L2-loss. The added 1× 1 can be merged into previous the pointwise layer in student-net.
The accuracy of FSKD-BCD versus the number of iterations T is illustrated in Figure 5, which shows that more iterations do not bring noticeable performance gain. This is because in each iteration, the sub-problem is a linear optimization problem so that we can find exact minimization. This is consistent with the finding by (Hong et al., 2017). Therefore, in the paper, we only report the accuracy of T = 1 for FSKD-BCD.
APPENDIX-C: ILLUSTRATION OF FSKD ON PRUNING AND DECOUPLING
Figure 6 illustrates how FSKD work for block-level alignment on the filter pruning (Li et al., 2016) and network slimming (Liu et al., 2017) cases. Figure 7 illustrates how FSKD works for block-level alignment on the network decoupling (Guo et al., 2018) case.
APPENDIX-D: ITERATIVE PRUNING AND FSKD
Previous works show that one time extremely pruning may yield the pruned network unable to recovery from fine-tuning, while the iteratively pruning and fine-tuning procedure is observed effective to obtain extreme model compression (Han et al., 2016; Li et al., 2016; Liu et al., 2017). Inspired by these works, we proposed the iteratively pruning and FSKD procedure as described in algorithm 2 to achieve extremely compression rate. This solution is still much more efficient than iteratively pruning and fine-tuning due to the great efficiency of FSKD over fine-tuning.
Based on this procedure, we extremely prune VGG-16 on CIFAR-10 by 88% total parameters. Table 5 list the results comparison to fine-tuning, FitNet, etc. It verfies the effectiveness of our FSKD on this extremely pruned case.

heading: APPENDIX-E: TRAINING ONLY POINTWISE CONV-LAYER IS ACCURATE ENOUGH

text:
People may challenge that learning 1 × 1-conv may loss representation power and ask why the added 1× 1 convolution works so well with such few samples. According to the network decoupling theory (Lemma-1), any regular conv-layer could be decomposed into a sum of depthwise separable blocks, where each depthwise separable block consists of a depthwise (DW) convolution (for spatial correlation modeling) followed by a pointwise (PW) convolution (for cross-channel correlation modeling). The added 1× 1 conv-layer is absorbed/merged into the previous PW layer finally. The decoupling yields that the number of parameters in PW-layer occupies most (>=80%) parameters of the whole network. We argue that learning 1 × 1-conv is still very powerful, and make a bold hypothesis in subsection 4.1 that PW conv-layer is more critical for performance than DW convlayer. To verify this hypothesis, we make experiments on VGG16 and ResNet50 on CIFAR-10 and CIFAR-100 under below different settings.
(1) We train the network from random initialization with 150 epoches. (2) We start from a random initialized network (VGG16 or ResNet50), and do full rank de-
coupling (K = k2 in Equation 3) so that channels in DW layers are orthogonal, and PW layers are still fully random. Note that Lemma-1 ensures the network before and after decoupling are equivalent (i.e., able to transfer back and force from each other). We keep all the DW-layers fixed (with random orthogonal basis), and train only the PW layers with 150 epochs. We denote this scheme as ND-1*1.
Note that except the setting explicitly described, all the other configurations (including training epochs, hyper-parameters, hardware platform, etc) are kept the same on both experimental cases. Table 6 lists the experimental results on these two cases on both datasets with two different network structures. It is obvious that the 2nd case (ND-1*1) clearly outperforms the 1st case. This verifies our
hypothesis that when keeping DW channels orthogonal, training only the pointwise (1×1) conv-layer is accurate enough, or even better than training all the parameters together.

heading: APPENDIX-F: FILTER VISUALIZATION ON ZERO STUDENT-NET

text:
To help better understanding how FSKD impacts the filters, we try to visualize the filter kernels. As the regular conv-layer kernel size is just 3× 3 in the zero student-net (VGG13), it is hard to see a difference in such a small kernel-size. Instead, we consider visualizing the pointwise convolution tensor (degraded to matrix form) in Figure 8 for the following three cases:
(a) We initialize VGG13 with the MSRA initialization method, and then decouple one layer (64 input channels and 64 output channels) to obtain the PW conv-layer. For simplicity, we only visualize the PW tensor of the first decoupling block (in the left), which has size 64× 64;
(b) We run SGD on few samples for VGG13 from random initialization until convergence, and then decouple the same layer to obtain the first-rank PW tensor (visualized in the middle);
(c) We further run FSKD on few samples for VGG13 already optimized by SGD, and then decouple the same layer to obtain the first-rank PW tensor (visualized in the right).
It shows that the tensor before SGD is fairly random on the value range, the tensor after SGD is less random, while the tensor after FSKD further shows some regular patterns, which indicates that there are some strong correlations among depthwise channels.


summaries: The paper proposes the H score H(f), a quantity that measure the goodness of feature f(x) for predicting some target y. This heavily builds on Makur et al. (2015) who introduce information vectors, the error exponent, and the DTM matrix. The paper connects H(f) with these quantities to justify the proposal (e.g., H(f) is proportional to the error exponent (Theorem 1)). The actual transferability is measured by the ratio between H(f) and H(f_opt) where the latter can be computed using the approach of Makur et al.

summaries: In this paper, the authors considered a source domain selection problem in transfer learning. Given a feature representation function f, the H-score is defined as the normalized correlation between the output f(X) and the label Y. The transferability is then measured by the ratio of H-score on the target domain and the optimal one. The authors introduced the information-theoretic and statistical meaning of the H-score. Validation of H-score was confirmed by numerical experimenters with image data.

abstractText: 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.

authors:
Andreas Argyriou
Theodoros Evgeniou
Massimiliano Pontil

title: Multi-task feature learning

venue: In Advances in neural information processing systems,

title: A model of inductive bias learning

venue: Journal of artificial intelligence research,

authors:
Shai Ben-David
Reba Schuller

title: Exploiting task relatedness for multiple task learning

venue: Lecture notes in computer science,

authors:
Edwin V Bonilla
Kian M Chai
Christopher Williams

title: Multi-task gaussian process prediction

authors:
Leo Breiman
Jerome H Friedman

title: Estimating optimal transformations for multiple regression and correlation

venue: Journal of the American statistical Association,

authors:
Alexis Conneau
Douwe Kiela
Holger Schwenk
Loic Barrault
Antoine Bordes

title: Supervised learning of universal sentence representations from natural language inference data

venue: arXiv preprint arXiv:1705.02364,

authors:
Jeff Donahue
Yangqing Jia
Oriol Vinyals
Judy Hoffman
Ning Zhang
Eric Tzeng
Trevor Darrell

title: Decaf: A deep convolutional activation feature for generic visual recognition

venue: In International conference on machine learning,

authors:
Marylou Gabrié
Andre Manoel
Clément Luneau
Jean Barbier
Nicolas Macris
Florent Krzakala
Lenka Zdeborová

title: Entropy and mutual information in models of deep neural networks

title: Das statistische problem der korrelation als variations-und eigenwertproblem und sein zusammenhang mit der ausgleichsrechnung

venue: ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik,

title: Correlation-based feature selection for machine learning

title: A connection between correlation and contingency

venue: Mathematical Proceedings of the Cambridge Philosophical Society,

authors:
Shao-Lun Huang
Anuran Makur
Lizhong Zheng
Gregory W Wornell

title: An information-theoretic approach to universal feature selection in high-dimensional inference

venue: In Information Theory (ISIT),

authors:
Laurent Jacob
Jean-philippe Vert
Francis R Bach

title: Clustered multi-task learning: A convex formulation

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Xuejun Liao
Lawrence Carin

title: Radial basis function network for multi-task learning

venue: In Advances in Neural Information Processing Systems,

authors:
Anuran Makur
Fabián Kozynski
Shao-Lun Huang
Lizhong Zheng

title: An efficient algorithm for information decomposition and extraction

venue: In Communication, Control, and Computing (Allerton),

title: Transfer bounds for linear feature learning

venue: Machine learning,

authors:
Hanchuan Peng
Fuhui Long
Chris Ding

title: Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy

venue: IEEE Transactions on pattern analysis and machine intelligence,

authors:
Anastasia Pentina
Christoph H. Lampert

title: A pac-bayesian bound for lifelong learning

venue: In International Conference on International Conference on Machine Learning, pp

title: Discriminability-based transfer between neural networks

title: On measures of dependence

venue: Acta mathematica hungarica,

authors:
C.K. Shie
C.H. Chuang
C.N. Chou
M.H. Wu
E.Y. Chang

title: Transfer representation learning for medical image analysis

venue: In 2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC),

authors:
Lisa Torrey
Jude Shavlik

title: Transfer learning. In Handbook of research on machine learning applications and trends: algorithms, methods, and techniques, pp. 242–264

venue: IGI Global,

authors:
Lichen Wang
Jiaxiang Wu
Shao-Lun Huang
Lizhong Zheng
Xiangxiang Xu
Lin Zhang
Junzhou Huang

title: An efficient approach to informative feature extraction from multimodal data

authors:
Mei Wang
Weihong Deng

title: Deep visual domain adaptation: A survey

authors:
Ya Xue
Xuejun Liao
Lawrence Carin
Balaji Krishnapuram

title: Multi-task learning for classification with dirichlet process priors

venue: Journal of Machine Learning Research,

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

authors:
Amir Zamir
Alexander Sax
William Shen
Leonidas Guibas
Jitendra Malik
Silvio Savarese

title: Taskonomy: Disentangling task transfer learning

venue: Computer Vision and Pattern Recognition

title: Heterogeneous-neighborhood-based multi-task local learning algorithms. In Advances in neural information processing

heading: 1 INTRODUCTION

text:
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 TT , instead of learning a model from scratch, we can initialize the parameters from a previously trained model for some related source task TS . 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.

heading: 2 BACKGROUND

text:
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 PX represent a random variable, a value, the alphabet and the probability distribution respectively. √ PX denotes the vector with entries √ PX(x) and [ √ PX ] the diagonal matrix of√
PX(X). For joint distribution PY X , PY 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, PXY ), where X is the training features and Y is the training label, and PXY the joint probability (possibly unknown). Subscripts S and T are used to distinguish the source task from the target task.

heading: 2.1 LOCAL INFORMATION GEOMETRY AND HYPOTHESIS TESTING

text:
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 xm = {x(i)}mi=1 are drawn from distribution P1 or distribution P2, where P1, P2 belong to an -neighborhood N (P0) , {P | ∑ x∈X (P (x)−P0(x))2 P0(x) ≤ 2} centered at a reference distributon P0. And denote φi = Pi(x)−P0(x) √ P0(x) as the information vector corresponding to Pi for i = 1, 2.
Given k normalized feature functions f(x) = [f1(x), . . . , fk(x)], let Ξ(x) = [ξ1(x), . . . , ξk(x)] be the matrix of feature vectors ξi(x) = √ P0(x)fi(x). Given observations xm, feature f is associated
with a k-dimensional statistics l(xm) = 1m ∑m i=1(f(x
(i))) for the binary hypothesis testing problem. Let Ef be the error exponent of decision region {xm | l(xm) > T} for T ≥ 0, which characterizes the asymptotic error probability Pe of l (i.e. limm→∞− 1m log(Pe) = E k f ). Ef can be written as the squared length of a projection:
Ekf = k∑ i=1 Efi = 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 Ekf = ∑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.

heading: 2.2 DIVERGENCE TRANSITION MATRIX

text:
Definition 1. Matrix B̃ is the Divergence Transition Matrix (DTM) of a joint probability PY X if B̃ = [√ PY ]−1 PY X [√ PX ]−1 −√PY√PXT.
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)√ PX(x) and g∗i (y) = ψi(y)√ PY (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); Rényi (1959), defined as follows:
ρ(X;Y ) = sup f : X → Rk, g : Y → Rk E[f(X)] = E[g(Y )] = 0 E[f(X)f(X)T ] = I
E[f(X)T g(Y )] (2)
The maximal HGR problem finds the K strongest, independent modes in PXY 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.

heading: 3 MEASURING THE EFFECTIVENESS OF FEATURES IN CLASSIFICATION TASKS

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

heading: 3.1 H-SCORE

text:
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 ∈ Rm×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 PY X is:
H(f) = tr(cov(f(X))−1cov(EPX|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(EPX|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.

heading: 3.2 OPERATIONAL MEANING OF H-SCORE

text:
Without loss of generality, we consider the binary classification task as a hypothesis testing problem defined in Section 2.1, with P1 = PX|Y=0, and P2 = PX|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 Ekf . Theorem 1. Given PX|Y=0, PX|Y=1 ∈ NX (P0,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 Ekf = cH(f).
See Appendix C for the proof. The above theorem shows that H-scoreH(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 fS(x)− E[fS(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̃Ξ‖2F , 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) = [f1(x), . . . , fk(x)], its H-score satisfies H(f) ≤∑k i=1 σ 2 i ≤ k, where σi is the ith singular value of B̃.
The first inequality is achieved when Ξ is composed of the right singular vectors of B̃, i.e. maxΞ ||B̃Ξ||2F = ||B̃T ||2F . The corresponding feature functions fopt(X)is in fact the same as the universal minimum error probability features from the maximum HGR correlation problem. The final inequality in Corollary 1 is due to the fact all singular values of B̃ are less than or equal to 1.

heading: 4 TRANSFERABILITY

text: 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.

heading: 4.1 TASK TRANSFERABILITY

text:
A typical way to transfer knowledge from the source task TS to target task TT is to train the target task using source feature representation fS(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 TS and target task TT , and trained source feature representation fS(x), the transferability from TS to TT is T(S, T ) , HT (fS)HT (fTopt ) , where fTopt(x) is the minimum error probability feature of the target task.
The statement T(S, T ) = r means the error exponent of transfering from TS via feature representation fS is 1r of the optimal error exponent for predicting the target label YT . This definition also implies 0 ≤ T(S, T ) ≤ 1, which satisfies the data processing inequality if we consider the transferred feature fS(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.

heading: 4.2 EFFICIENT COMPUTATION OF TRANSFERABILITY

text:
With a known f , computing H-score from m sample data only takes O(mk2) 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 fTopt efficiently. We use the fact thatHT (fopt) = ||B̃T ||2F = E[f(X)Tg(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 fopt through a different formulation of the HGR maximal
W YT
fS(x)
input X
Ys
source task
target taskfS(x)W
gs(y)
gs(y) X
Y
f (x)
f encoder
g encoder
g(y)
! " # $% & − 1 2 *+(-./(" # -./ % &
L
(a) (b)
Figure 2: a) Network topology of linear feature transfer. b) Architecture for the neural network implementation of the soft HGR problem 1 2 3 4 5 6 dim(f(x))
0.0
0.1
0.2
0.3
H-score: HY(f(x)) 2I(X; Y)
Figure 3: H-score and mutual information.
correlation problem:
max f :X→Rk,g:Y→Rk E[f(X)Tg(Y )]− 1 2 tr(cov(f(X))cov(g(Y )))
s.t. E[f(X)] = 0, E[g(Y )] = 0 (3)
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(mk2), 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 PY,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 HT (fopt) can even be skipped entirely, such as the problem below:
Definition 4 (Source task selection). Given N source tasks TS1 , . . . , TSN with labels YS1 , . . . , YSN and a target task TT with label YT . Let fS1 , . . . , fSN be the minimum error probability feature functions of the source tasks. Find the source task TSi that maximizes the testing accuracy of predicting YT with feature fSi .
We can solve this problem by selecting the source task with the largest transferability to TT . 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. argmaxi T(Si, T ) = argmaxi(HT (fSi,opt)/HT (fTopt) = argmaxiH(fSi).

heading: 4.3 RELATIONSHIP WITH MUTUAL INFORMATION

text:
Under the local assumption that PX|Y ∈ N (PX), 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 YT , 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 fS(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 (Gabrié et al. (2018)). On the other hand, H-score only needs to estimate conditional expectations, which requires less samples.

heading: 5 EXPERIMENTS

text: 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.

heading: 5.1 VALIDATION OF TRANSFER PERFORMANCE

text:
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.
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).
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.

heading: 5.2 TASK TRANSFER FOR 3D SCENE UNDERSTANDING

text:
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
1Test data and code can be found at https://goo.gl/uoXj8m
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.
Feature Extraction and Data Preprocessing. For each task, Zamir et al. (2018) trained a fully supervised network with an encoder-decoder structure. When testing the transfer performance from TS to TT , the encoder output of TS is used for training the decoder of TT . For a fair comparison, we use the same trained encoders to extract source features. The output dimension of all encoders are 16× 16× 8 and we flatten the output into a vector of length 2048. To reduce the computational complexity, we also resize the ground truth images into 64× 64. For classification tasks, H-score can be easily calculated given the source features. But for pixel-topixel tasks such as Edges and Depth, their ground truths are represented as images, which can not be quantized easily. As a workaround, we cluster the pixel values in the ground truth images into a palette of 16 colors. Then compute the H-score of the source features with respect to each pixel, before aggregating them into a final score by averaging over the whole image.
We ran the experiment on a workstation with 3.40 GHz ×8 CPU and 16 GB memory. Each pairwise H-score computation finished in less than one hour including preprocessing. Then we rank the source tasks according to their H-scores of a given target task and compare the ranking with that in Zamir et al. (2018).
Tasks k Output Quantize -level
2D Edges 2048 images 16 3D Occlusion Edges 2048 images 16 2D Keypoints 2048 images 16 3D Keypoints 2048 images 16 Reshading 2048 images 16 Depth 2048 images 16
Object Class. 2048 labels none Scene Class. 2048 labels none
Figure 6: Task descriptions
Transferability Task Hierarchy Affinity Ranking Correlation
DCG
Figure 7: Ranking comparison between transferability and affinity score.
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.

heading: 6 RELATED WORKS

text:
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.

heading: 7 CONCLUSION

text:
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.

heading: APPENDIX A INFERENCE USING LOCAL INFORMATION GEOMETRY

text:
Further, using Sannov’s theorem, we have that asymptotically the probability of type I error
α = P1(A c) ≈ 2−mD(P ∗ 1 ||P1)
where P ∗1 = argminP∈Ac D(P ||P1) and Ac(T ) = {xm : D(Pxm ||P2)−D(Pxm ||P1) < 1m log T} denotes the rejection region. Similarly, for type II error
β = P2(A) ≈ 2−mD(P ∗ 2 ||P2)
where P ∗2 = argminP∈AD(P ||P2) and A = {xm : D(Pxm ||P2) − D(Pxm ||P1) > 1m log T} represents the acceptance region. (See Figure 10) The overall probability of error is P (m)e = αPr(H0) + βPr(H1) and the best achievable exponent in the Bayesian probability of error (a.k.a. Chernoff exponent) is defined as:
E = lim m→∞ min A⊆Xm − 1 m logP (m)e
See Cover & Thomas (1991) for more background information on error exponents and its related theorems.
A.2 LOCAL INFORMATION GEOMETRY
Now consider the same binary hypothesis testing problem, but with the local constraint P1, P2 ∈ N (PX0 ). Let φi =
Pi(x)−PX0 (x) √ PX0 (x) denote the information vectors corresponding to Pi 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 = 1m ∑m i=1(f(x (i))) is
Ef = 2
8 〈ξ, φ1 − φ2〉2 + o( 2)
where ξ(x) = √ P0(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) = [f1(x), . . . , fk(x)], such that E[fi(X)] = 0 for all i, and cov(f(X)) = I , we define a k-d statistics of the form lk = (l1, ..., lk) where li = 1 m ∑m l=1 fi(x
(l)). Let Ξ(x) = [ξ1(x), . . . , ξk(x)] be the corresponding feature vectors with ξi(x) = √ PX(x)fi(x).
Ekf = k∑ i=1 Efi = k∑ i=l 2 8 〈ξi, φ1 − φ2〉2 + o( 2) (4)
Proof. According to Cramér’s theorem, the error exponent under Pi is
Ei(λ) = min P∈δ(λ)
D(P ||Pi)
where δ (λ) , { P : EP [f(X)k] = λEP1 [f(X)k] + (1− λ)EP2 [f(X)k] } . With the techniques developed in local information geometry, the above above problem is equivalent to the following problem:
Ei(λ) = 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) √ P0(x)+o( ) and the equation α(θk) = o( 2), it is easy to show that E1(λ) = E1(λ) when λ = 12 . Then the overall error probability has the exponent as shown in Equation (1).

heading: APPENDIX B HGR MAXIMAL CORRELATION AND THE ACE ALGORITHM

text:
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 Ré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 PY 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) ∈ Rk,∀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 ]− 12 ,∀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 ]− 12 ,∀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 Ê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 PY X , if X and Y are not independent, then for any f : X → R and g : Y → R such that E[f2(X)] = E[g2(Y )] = 1, we have that
− lim ∆→0+
1
δ2 lim m→∞
1 m log
[ P {∣∣∣∣∣ Ê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.

heading: APPENDIX C PROOF OF THEOREM 1

text:
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̃ξ||2F = EPY [(E[f(X)|Y ])2] where ξ is the feature vector corresponding to f . Proof. Since ξ(x) = √ PX(x)f(x), we have
||B̃ξ||2F = ξTB̃TB̃ξ
= ∑ y∈Y (∑ x∈X ( PY X(y, x)√ PX(x) √ PY (y) − √ PX(x) √ PY (y) ) · √ PX(x)f(x) )2 = ∑ y∈Y (∑ x∈X PY X(y, x) PY (y) · f(x)− ∑ x∈X f(x)PX(x) )2 · PY (y)
= ∑ y∈Y (E[f(X)|Y = y]− E[f(x)])2 · PY (y)
= EPY [(E[f(X)|Y ])2] The last equality uses the assumption that E[f(x)] = 0.
Theorem 3 (1D version of Theorem 1). Given PX|Y=0, PX|Y=1 ∈ NX (P0,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
Ef = c‖B̃ξ‖2F (5)
Proof. From E[f(X)] = PY (0)E[f(X)|Y = 0] + PY (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] = − ( PY (0)
PY (1)
) E[f(X)|Y = 0]
E[f(X)|Y = 0] = − ( PY (1)
PY (0)
) E[f(X)|Y = 1]
On the R.H.S. of Equation 5, we apply Lemma 4 to write ‖B̃ξ‖2F = EPY [ (E [f(X)|Y ])2 ] = PY (0)PY (1) + PY (1) 2
PY (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) =
c0〈ξ, φ1 − φ2〉2 for some constant c0.
c0 〈ξ, φP1 − φP2〉 2
=c0 (∑ x∈X PX|Y=0(x)− PX|Y=1(x)√ PX(x) · √ PX(x)f(x) )2 =c0 (E [f(X)|Y = 0]− E [f(X)|Y = 1])2
=c0 − (PY (0) + PY (1))2
PY (0)PY (1) · (E [f(X)|Y = 1])(E [f(X)|Y = 0])
=c0
( PY (0) + PY (1)
PY (0)
)2 · (E [f(X)|Y = 1])2
=c0 PY (0) + PY (1)
PY (0)PY (1)
( PY (0)PY (1) + PY (1) 2
PY (0)
) · (E [f(X)|Y = 1])2
=c ||B̃ξ||2F
For k ≥ 2, Lemma 4 can be restated as follows: Lemma 5. Let f : X → Rk be a k-dimensional feature function of X , where f(x) = [f1(x), . . . , fk(x)]. Further we assume that E[f(X)] = 0 and cov(f(X)) = E[f(X)Tf(X)] = I . Then ||B̂Ξ||2F = tr(cov(E[f(X)|Y ])) where columns of Ξ are the information vectors corresponding to f1(x), . . . , fk(x).
Proof. First, note that
B̃Ξ = ([√ PY ]−1 PY X [√ PX ]−1 − √ PY √ PX T )[√ PX ] f(X)
= [√
PY ] ( [PY ] −1 PY 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̃Ξ = [√
PY ] ( [PY ] −1 PY X f(X) ) It follows that
||B̃Ξ||2F =tr(ΞTB̃TB̃Ξ) =tr (( [PY ] −1 PY X f(X) )T [PY ] ( [PY ] −1 PY X f(X) ))
=tr ( EPY [ (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̃Ξ||2F =tr (cov(E[f(X)|Y ])) =tr ( EPY [ (E[f(X)|Y ]]T)T(E[f(X)|Y ]]T) ]) =PY (0)E[f(X)|Y = 0]]TE[f(X)|Y = 0]] + PY (1)E[f(X)|Y = 1]]TE[f(X)|Y = 1]]
= PY (0)PY (1) + PY (1)
2
PY (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 Ekf = c0 ∑k i=l 〈ξi, φ1 − φ2〉
2 for some constant c0. It follows that
c0 k∑ i=l 〈ξi, φ1 − φ2〉2
=c0 ((( PX|Y=0 − PX|Y=1 ))T f(X) )((( PX|Y=0 − PX|Y=1 ))T f(X) )T =c0 (E[f(X)|Y = 0]− E[f(X)|Y = 1])T (E[f(X)|Y = 0]− E[f(X)|Y = 1])
=c0 PY (0) + PY (1)
PY (0)PY (1)
( PY (0)PY (1) + PY (1) 2
PY (0)
) · E [f(X)|Y = 1]T E [f(X)|Y = 1]
=c ‖B̃Ξ‖2F

heading: APPENDIX D GENERALIZATION OF H-SCORE FOR ARBITRARY FEATURE SET

text:
Since Ξ = [√ PX ] f(X) and E[f(X)] = 0, we have
ΞTΞ = ([√
PX
] f(X) )T ([√ PX ] f(X) ) = E[f(X)Tf(X)] = cov(f(X)) (6)
Equation (6) gives a more understandable expression of the normalization term. We can also write B̃Ξ as follows:
B̃Ξ = ([√ PY ]−1 PY X [√ PX ]−1 − √ PY √ PX T )[√ PX ] f(X)
= [√
PY ] ( [PY ] −1 PY X f(X)− 1 · E[f(X)]T ) where 1 is a column vector with all entries 1 and length |Y|, we have
ΞTB̃TB̃Ξ = ( [PY ] −1 PY X f(X)− 1 · E[f(X)]T )T [PY ] ( [PY ] −1 PY X f(X)− 1 · E[f(X)]T )
=EPY [ (E[f(X)|Y ]− 1 · E[f(X)]T)T(E[f(X)|Y ]− 1 · E[f(X)]T) ] =cov (E[f(X)|Y ]) (7)
On the other hand, ||B̃Ξ(ΞTΞ)− 12 ||2F =tr ( (ΞTΞ)− 1 2 ΞTB̃TB̃Ξ(ΞTΞ)− 1 2 ) =tr ( (ΞTΞ)−1ΞTB̃TB̃Ξ )
(8) =tr ( cov(f(X))−1cov(E[f(X)|Y ]) ) The last equality is derived by substituting (6) and (7) into (8).

heading: APPENDIX E H-SCORE AND SOFTMAX REGRESSION

text:
In softmax regression, given m training examples {(x(i), y(i))}mi=1, the cross-entropy loss of the model is
`(f, θ) =− m∑ i=1 |Y|∑ k=1 1{y(i) = k} log e −θTk f(x (i))∑C j=1 e −θTj f(x(i)) (9)
,− m∑ i=1 logQY |X(y (i)|x(i)) (10)
=− EPYX [logQY |X(Y |X)] (11) Minimizing ` is equivalent to minimizing D ( PY X ||PXQY |X ) where PY X is the joint empirical distribution of (X,Y ).
Using information geometry, it can be shown that under a local assumption
argmin f,θ
D ( PY X ||PXQY |X ) = argmin
Ψ,Φ
1 2 ‖B̃ −ΨΦT‖2F + 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‖2F 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.
min Ψ ‖B̃T −ΨΦTS‖ (13)
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
Ψ∗ = B̃TΦS(Φ T SΦS) −1 (14)
Substituting (14) in the Objective of (13), we can derive the following close-form solution for the log loss.
‖B̃TT B̃T ‖2F − ‖B̃TΦS(ΦTSΦS)− 1 2 ‖2F (15)
The first term in (15) is fixed given TT 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 PY0|X , and 20 source tasks are generated with the conditional probability matrix PYi|X = PY0|X + iλI for some positive constant λ.
The universal minimum error probability features for each source task are used as the source features fSi(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.

heading: APPENDIX F DTM AND MUTUAL INFORMATION

text:
Proposition 1. Under the local assumption that PX|Y ∈ N (PX), 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|Yy (x) = PX|Y (x|y)−PX(x)
√ PX(x) and let ΦX|Y ∈ R|X |×|Y| denote its matrix version. Then we have
ΦX|Y [ √ PY ] = [ √ PX ] −1(PXY − PX)[ √ PY ] = B̃ T
Next, we express the mutual information in terms of information vector φX|Y , I(X;Y ) = I(Y ;X) = ∑ y∈Y PY (y)DKL(PX|Y ||PX)
= 2
2 ∑ y∈Y PY (y)||φX|Yy ||2 + o( 2)
= 1
2 || ΦX|Y [
√ PY ]||2F + o( 2)
= 1
2 ||B̃||2F + o( 2)

heading: APPENDIX G SUPPLEMENTARY RESULTS ON EXPERIMENT 5.2

text:
G.1 COMPARISON OF H-SCORES AND AFFINITIES
Table 1, 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 in Zamir et al. (2018). Score values are included in parenteses.
Here we present 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 Figure 12 and 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.
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.