Year: 2020

Abstract:
Continual learning could shift the machine learning paradigm from data centric to model centric. A continual learning model needs to scale efficiently to handle semantically different datasets, while avoiding unnecessary growth. We introduce hash-routed convolutional neural networks: a group of convolutional units where data flows dynamically. Feature maps are compared using feature hashing and similar data is routed to the same units. A hash-routed network provides excellent plasticity thanks to its routed nature, while generating stable features through the use of orthogonal feature hashing. Each unit evolves separately and new units can be added (to be used only when necessary). Hash-routed networks achieve excellent performance across a variety of typical continual learning benchmarks without storing raw data and train using only gradient descent. Besides providing a continual learning framework for supervised tasks with encouraging results, our model can be used for unsupervised or reinforcement learning.

text: Continual learning could shift the machine learning paradigm from data centric to model centric. A continual learning model needs to scale efficiently to handle semantically different datasets, while avoiding unnecessary growth. We introduce hash-routed convolutional neural networks: a group of convolutional units where data flows dynamically. Feature maps are compared using feature hashing and similar data is routed to the same units. A hash-routed network provides excellent plasticity thanks to its routed nature, while generating stable features through the use of orthogonal feature hashing. Each unit evolves separately and new units can be added (to be used only when necessary). Hash-routed networks achieve excellent performance across a variety of typical continual learning benchmarks without storing raw data and train using only gradient descent. Besides providing a continual learning framework for supervised tasks with encouraging results, our model can be used for unsupervised or reinforcement learning.

heading: 1 INTRODUCTION
text: When faced with a new modeling challenge, a data scientist will typically train a model from a class of models based on her/his expert knowledge and retain the best performing one. The trained model is often useless when faced with different data. Retraining it on new data will result in poor performance when trying to reuse the model on the original data. This is what is known as catastrophic forgetting (McCloskey & Cohen, 1989). Although transfer learning avoids retraining networks from scratch, keeping the acquired knowledge in a trained model and using it to learn new tasks is not straightforward. The real knowledge remains with the human expert. Model training is usually a data centric task. Continual learning (Thrun, 1995) makes model training a model centric task by maintaining acquired knowledge in previous learning tasks. Recent work in continual (or lifelong) learning has focused on supervised classification tasks and most of the developed algorithms do not generate stable features that could be used for unsupervised learning tasks, as would a more generic algorithm such as the one we present. Models should also be able to adapt and scale reasonably to accommodate different learning tasks without using an exponential amount of resources, and preferably with little data scientist intervention. To tackle this challenge, we introduce hash-routed networks (HRN). A HRN is composed of multiple independent processing units. Unlike typical convolutional neural networks (CNN), the data flow between these units is determined dynamically by measuring similarity between hashed feature maps. The generated feature maps are stable. Scalability is insured through unit evolution and by increasing the number of available units, while avoiding exponential memory use. This new type of network maintains stable performance across a variety of tasks (including semantically different tasks). We describe expansion, update and regularization algorithms for continual learning. We validate our approach using multiple publicly available datasets, by comparing supervised classification performance. Benchmarks include Pairwise-MNIST, MNIST/Fashion-MNIST (Xiao et al., 2017) and SVHN/incremental-Cifar100 (Netzer et al., 2011; Krizhevsky et al., 2009). Relevant background is introduced in section 2. Section 3 details the hash-routing algorithm and discusses its key attributes. Section 4 compares our work with other continual learning and dynamic network studies. A large set of experiments is carried out in section 5.

heading: 2 FEATURE HASHING BACKGROUND
text: Feature hashing, also known as the hashing trick (Weinberger et al., 2009) is a dimension reduction transformation with key properties for our work: inner product conservation and quasi-orthogonality. A feature hashing function φ : RN → Rs, can be built using two uniform hash functions h : N→ {1, 2..., s} and ξ : N→ {−1, 1}, as such:
φi(x) = ∑
j∈[[1,N ]] j:h(j)=i
ξ(j)xj
where φi denotes the ith component of φ. Inner product is preserved as E[φ(a)Tφ(b)] = aTb. φ provides an unbiased estimator of the inner product. It can also be shown that if ||a||2 = ||b||2 = 1, then σa,b = O( 1s ). Two different hash functions φ and φ′ (e.g. h 6= h′ or ξ 6= ξ′) are orthogonal. In other words, ∀(v,w) ∈ Im(φ)× Im(φ′),E[vTw] ≈ 0. Furthermore, Weinberger et al. (2009) details the inner product bounds, given v ∈ Im(φ) and x ∈ RN :
Pr(|vTφ′(x)| > ) ≤ 2 exp ( −
2/2
s−1 ‖v‖22 ‖x‖ 2 2 + ‖v‖∞ ‖x‖∞ /3
) (1)
Eq.1 shows that approximate orthogonality is better when φ′ handles bounded vectors. Data independent bounds can be obtained by setting ‖x‖∞ = 1 and replacing v by
v ‖v‖2 , which leads to
‖x‖22 ≤ N and ‖v‖∞ ≤ 1, hence:
Pr(|vTφ′(x)| > ) ≤ 2 exp ( −
2/2
s−1 ‖x‖22 + ‖v‖∞ /3
) ≤ 2 exp ( −
2/2
N/s+ /3
) (2)
Better approximate orthogonality significantly reduces correlation when summing feature vectors generated by different hashing functions, as is done in hash-routed networks.

heading: 3 HASH-ROUTED NETWORKS

heading: 3.1 STRUCTURE
text: A hash-routed network maps input data to a feature vector of size s that is stable across successive learning tasks. An HRN exploits inner product preservation to insure that similarity between generated feature vectors reflect the similarity between input samples. Quasi-orthogonality of different feature hashing functions is used to reduce correlation between the output’s components, as it is the sum of individual hashed feature vectors. An HRN H is composed of M units {U1, ...,UM}. Each unit Uk is composed of:
• A series of convolution operations fk. It is characterized by a number of input channels and a number of output channels, resulting in a vector of trainable parameters wk. Note that fk can also include pooling operations.
• An orthonormal projection basis Bk. It contains a maximum of m non-zeros orthogonal vectors of size s. Each basis is filled with zero vectors at first. These will be replaced by non-zero vectors during training.
• A feature hashing function φk that maps a feature vector of any size to a vector of size s.
The network also has an independent feature hashing function φ0. All the feature hashing functions are different but generate feature vectors of size s.

heading: 3.2 OPERATION

heading: 3.2.1 HASH-ROUTING ALGORITHM
text: H maps an input sample x to a feature vectorH(x) of size s. In a vanilla CNN, x would go through a series of deterministic convolutional layers to generate feature maps of growing size. In a HRN,
the convolutional layers that will be involved will vary depending on intermediate results. Feature hashing is used to route operations. Since feature hashing preserves the inner product in the hashed features space, similar samples will be processed similarly. Intermediate features are hashed and projected upon the units’ projection bases. The unit where the projection’s magnitude is the highest is selected for the next operation. Operations continue until a maximum depth d is reached (i.e. there is a limit of d − 1 chained operations), or when the projection residue is below a given threshold τd. H(x) is the sum of all residues. Let {Ui1 ,Ui2 , ...,Uid−1} be the ordered set of units involved in processing x (assuming the final projection residue’s magnitude is greater than τd). Operation 0 simply involves hashing the (flattened) input sample using φ0. Let xik = fik ◦ fik−1 ◦ ... ◦ fi1(x) be the intermediate features obtained at operation k. The normalized hashed features vector after operation k is computed as such:
hik =
φik ( xik ‖xik‖∞ ) ∥∥∥∥φik ( xik‖xik‖∞ )∥∥∥∥ 2
(3)
For operation 0, hi0 is computed using x and φ0. pik = Bik+1hik and rik = hik − pik are the projection vector and residue vector over basis Bik+1 resp. As explained earlier, this means that:
ik+1 = argmax j∈I\{i1,...,ik} ‖Bjhik‖2 (4)
where I is the subset of initialized units (i.e. units with bases containing at least one non-zero vector). Finally, H(x) = ∑
j∈{i0,...,id−1}
rj (5)
The full inference algorithm is summarized in Algorithm 1 and an example is given in Figure 1.

heading: 3.2.2 ANALYSIS
text: The output of a typical CNN is a feature map with a dimension that depends on the number of output channels used in each convolutional layer. In a HRN, this would lead to a variable dimension output as the final feature map depends on the routing. In a continual learning setup, dealing with variable dimension feature maps would be impractical. Feature hashing circumvents these problems by generating feature vectors of fixed dimension. Similar feature maps get to be processed by the same units, as a consequence of using feature hashing
Algorithm 1: Hash-routed inference Input: x Output: H = H(x) h0 = φ0(x); J = ∅ H ← 0; h← h0; y ← x for j = 1, ..., d− 1 do
ij = argmaxk∈I\J ‖Bkh‖2 ; // select the best unit r← h−Bijh ; // compute new residue H ← H + r ; // accumulate residue for output J ← J ∪ {ij} ; // update set of used units if ‖r‖2 < τd then
break ; // stop processing when residue is too low else
y ← fij (y) ; // compute feature map h← φij ( y ‖y‖∞
)∥∥∥φij ( y‖y‖∞ )∥∥∥2 ; // new hash vector using flattened feature map end
end
for routing. In this context, similarity is measured by the inner product of flattened feature maps, projected onto different orthogonal subspaces (each unit basis span). Another consequence is that unit weights become specialized in processing a certain type of features, rather than having to adapt to task specific features. This provides the kind of stability needed for continual learning. For a given unit Uk, rank(Bk) ≤ m << s. Hence, it is reasonable to consider that the orthogonal subspace’s contribution to total variance is much more important than that of Bk. This is whyH(x) only contains projection residues. Note that in Eq.3 , hik ∈ Im(φik) and ‖hik‖2 = 1. The operand under φik has an infinite norm of 1, which under Eq.2 leads to inner product bounds independent of input data when considering orthogonality. Moreover, due to the approximate orthogonality of different feature hashing functions, summing the residues will not lead to much information loss as each residue vector rik is in Im(φik−1) but this also explains why each unit can only be selected once. The residues’ `1-norms are added to the loss function to induce sparsity. Denoting LT the specific loss for task T (e.g. KL-divergence for supervised classification), the final loss L is:
L = LT + λ ∑
j∈{i0,...,id−1}
‖rj‖1 (6)

heading: 3.3 ONLINE BASIS EXPANSION AND UPDATE
text: The following paragraphs explain a unit’s evolution during training. The described algorithms run each time a unit is selected in Algorithm 1, requiring no external action.

heading: 3.3.1 INITIALIZATION AND EXPANSION
text: Units projection bases are at the heart of the hash-routing algorithm. As explained in section 3.2.1, bases are initially empty and undergo expansion during training. A hash vector (Eq.3) is used to select a unit according to Eq.4. When all units are still empty, a unit is picked randomly and its basis is initialized using the hash vector. Let I denote the subset of initialized units. When I 6= ∅ but some units are still empty, units are still selected according to Eq.4 under the condition that the projection’s magnitude is above a minimal threshold τempty . When τempty is not surpassed, a random unit from the remaining empty units is selected instead. Assuming a unit has been selected as the best for a given hash vector, its basis can expand when the projection’s magnitude is below the expansion threshold τexpand. The normalized projection’s residue is used as the next basis element. This follows a Gram-Schmidt orthonormalising process to maintain orthonormal basis for each unit. Each basis has a maximum size of m beyond which it cannot expand. The unit selection and expansion algorithms are summarized in Appendix.A.

heading: 3.3.2 UPDATE
text: Once a unit basis is full (i.e. it does not contain any zero vector), it still needs to evolve to accommodate routing needs. As the network trains, hashed features will also change and routing might need adjustment. If nothing is done to update full basis, the network might get ”stuck” in a bad configuration. Network weights would then need to change in order to compensate for improper routing, resulting in a decrease in performance. Nevertheless, bases should not be updated too frequently as this would lead to instability and units would then need to learn to deal with too many routing configurations. An aging mechanism can be used to stabilize basis update as training progresses. Each time a unit is selected, a counter is incremented and when it reaches its maximum age, it is updated. The maximum age can then be increased by means of a geometric progression. Using the aging mechanism, it becomes possible to apply the update process to bases that are not yet full, thus adding more flexibility. Hence, some bases can expand to include new vectors and update existing ones. Bases can be updated by replacing vectors that lead to routing instability. Each non-zero basis vector vk has a low projection counter ck. During training, when a unit has been selected, the basis vector with the lowest projection magnitude sees its low projection counter incremented. The update algorithm is summarized in Algorithm 2.
Algorithm 2: Unit update Input: Current basis (excluding zero-vectors): B = (v1, ...,vm), Current low projection counters: (c1, ..., cm), Current age: a, Current maximum age: α, Aging rate: ρ > 1, Latest hash vector h Output: Updated basis if a = α then
i = argmax{cj}; // find basis vector to replace vi ← h−B−ih; // remove projection on the reduced basis B−i (without vi) vi ← vi‖vi‖2 α← ρα; // update maximum age a← 0; // reset age counter ci ← 0; // reset low projection counter
else a← a+ 1; // increment current age i = argmin ∥∥vTj h∥∥2; // find low projection counter to increment ci ← ci + 1

heading: 3.4 TRAINING AND SCALABILITY
text: HRNs generate feature vectors that can be used for a variety of learning tasks. Given a learning task, optimal network weights can be computed via gradient descent. Feature vectors can be used as input to a fully connected network, to match a given label distribution in the case of supervised learning. As explained in Algorithm 1, each input sample is processed differently and can lead to a different computation graph. Batching is still possible and weight updates only apply to units involved in processing batch data. Weight updates is regularized using the residue vector’s norm at each unit level. Low magnitude residue vectors have little contribution to the network’s output thus their impact on training of downstream units should be limited. Denoting L a learning task loss function, r the hash vector projection residue over a unit’s basis, w the vector of the unit’s trainable weights and γ a learning rate, regularized weight update of w becomes:
w← w − γmin(1, ‖r‖2)∇L(w) (7) An HRN can scale simply by adding extra units. Note that adding units between each learning task is not always necessary to insure optimal performance. In our experiments, units were manually added after some learning tasks but this expansion process could be made automatic. Indeed, one or more extra unit(s) could be automatically added whenever all bases have been completely filled. Its architecture could be a copy of an existing unit (chosen randomly).

heading: 4 RELATED WORK
text: Dynamic networks Using handcrafted rigid models has obvious limits in terms of scalability. Tanno et al. (2018) builds a binary tree CNN with a routed dataflow. Routing heuristics requires intermediate evaluation on training data. It uses fully connected layers to select a branch. Spring & Shrivastava (2017) builds LSH (Gionis et al., 1999) hash tables of fully connected layer weights to select relevant activations but this does not apply to CNN. Rosenbaum et al. (2017)’s algorithm is closer to our setup. Each sample is processed by different blocks until a maximum processing depth is reached. It uses reinforcement learning to train a router that selects the best processing block at each level, based on a supervised classification scheme. However, their network is task-aware and blocks at each level cannot be used at other levels (unlike HRN units).
Continual learning Parisi et al. (2019) offers a thorough review of state-of-the-art continual learning techniques and algorithms, insisting on a key trade-off: stability vs plasticity. Lomonaco & Maltoni (2017) groups continual learning algorithms into 3 categories: regularization, architectural and rehearsal. Kirkpatrick et al. (2017) introduces a regularization technique using the Fisher information matrix to avoid updating important network weights. Zenke et al. (2017) achieves the same goal by measuring weight importance through its contribution to overall loss evolution across a given number of updates. Rannen et al. (2017) is closer to our setup. The authors continuously train an encoder with different decoders for each task while keeping a stable feature map. Knowledge distillation (Hinton et al., 2015) is used to avoid significant changes to the generated features between each task. A key limitation of this technique is, as mentioned in Rannen et al. (2017), that the encoder will never evolve beyond its inherent capacity as its architecture is frozen. Serra et al. (2018) learns attention nearly-binary masks to avoid updating parts of the network when training for a new task. Similarly, Beaulieu et al. (2020) uses a primary model to modulate the update and response of a secondary model. In both cases, scalability is again limited by the chosen architecture. Li & Hoiem (2017) also uses knowledge distillation in a supervised learning setup but systematically enlarges the last layers to handle new classes. Yoon et al. (2017) limits network expansion by enforcing sparsity when training with extra neurons. Useless neurons are then removed. Xu & Zhu (2018) uses reinforcement learning to optimize network expansion but does not fully take advantage of the inherent network capacity as network weights are frozen before each new task. Lopez-Paz & Ranzato (2017); Rebuffi et al. (2017); Hayes et al. (2019) store data from previous tasks in various ways to be reused during the current task (rehearsal). Shin et al. (2017); van de Ven & Tolias (2018); Rios & Itti (2018) make use of generative networks to regenerate data from previous tasks. Kamra et al. (2017); Parisi et al. (2018); Kemker & Kanan (2017) use neuroscience inspired concepts such as short-term/long-term memories and a fear mechanism to selectively store data during learning tasks, whereas we store a limited number of hashed feature maps in each unit basis, updated using an aging mechanism.

heading: 5 EXPERIMENTS

heading: 5.1 SETUP
text: We test our approach in scenarios of increasing complexity and using semantically different datasets. Supervised classification scenarios involve a single HRN that is used across all tasks to generate a feature vector that is fed to different classifiers (one classifier per task). Each classifier is trained only during the task at hand, along with the common HRN. Once the HRN has finished training for a given task, test data from previous tasks is re-encoded using the latest version of the HRN. The new feature vectors are fed into the trained (and frozen) classifiers and accuracy for previous tasks is measured once more. We compare our approach against 3 other algorithms: a vanilla convolutional network (VC) for feature generation with a different classifier per task; Elastic Weight Consolidation (EWC) (Kirkpatrick et al., 2017), a typical benchmark for continual learning. Elastic weight consolidation is applied only to a feature generator that feeds into a different classifier per task; Encoder Based Lifelong learning (ELL) (Rannen et al., 2017), involving a common feature generator with a different classifier per task. For a fair comparison, we used the same number of epochs per task and the same architecture for classifiers and convolutional layers. For VC, EWC and ELL, the convolutional encoder is equivalent to the unit combination in HRN leading to the largest feature map. Feature codes used in ELL
autoencoders (see Rannen et al. (2017) for more detail) have the same size as the hashed-feature vectors in HRN. For all experiments, we show the evolution of accuracy for the first task (T0) after each task training. This is a clear measure of catastrophic forgetting. We also show the overall accuracy after each task training.
The following scenarios were considered (implementation details can be found in Appendix.C): Pairwise-MNIST Each task is a binary classification of handwritten digits: 0/1, 2/3, ...etc, for a total of 5 tasks (5 epochs each). In this case, tasks are semantically comparable. A 4 units HRN with a depth of 3 was used. MNIST/Fashion-MNIST There are two 10-classes supervised classification tasks, first the FashionMNIST dataset, then the MNIST dataset. This a 2 tasks scenario with semantically different datasets. A 6 units HRN (depth of 3) was used for the first task and 2 units were added for the second task. SVHN/incremental-Cifar100 This is an 11 tasks scenario, where each task is a 10-classes supervised classification. Task 0 (8 epochs) involves the SVHN dataset. Tasks 1 to 10 (15 epochs each), involve 10 classes out of the 100 classes available in the Cifar100 dataset (new classes are introduced incrementally by groups of 10). All datasets are semantically different, especially task 0 and the others. A HRN of 6 units (depth of 3) was used for the SVHN task and 2 extra units were added before the 10 Cifar100 tasks series. For this experiment, we provide the accuracy drop for each task between its first training and the final task. This is a clear measure of catastrophic forgetting. We also provide the top accuracy score for each task. This measures the network’s ability to learn new tasks.

heading: 5.2 COMPARATIVE ANALYSIS
text: Figure 2 shows that HRN maintains a stable performance for the initial task, in comparison to other techniques, even in the most complex scenario. Global accuracy plots show that HRN performance degradation for all tasks is very low (even slightly positive in some cases). Moreover, figure 3 shows that catastrophic forgetting is higher with other algorithms, and almost non-existent with HRN. However, 3 also shows that maximum accuracy for each task is often slightly lower in comparison to other algorithms. Indeed, units in a HRN are not systematically updated at each training step and
would hence, require a few more epochs to reach top task accuracy as with VC. Furthermore, the trade-off between plasticity and stability can be controlled through the λ parameter (see Eq.6) as the ablation study has shown (see B for more detail). Plasticity can also be increased by adding extra units to an HRN.

heading: 5.3 ROUTING AND NETWORK ANALYSIS
text: After a few epochs, we observe that some units are used more frequently than others. However, we observe significant changes in usage ratios especially when changing tasks and datasets (see Figure 4). This clearly shows the network’s adaptability when dealing with new data. Moreover, some units are almost never used (e.g. U6 in Figure 4). This shows that the HRN only uses what it needs and that adding extra units does not necessarily lead to better performance.

heading: 5.4 HYPERPARAMETERS AND ABLATION
text: Appendix B details the impact of key hyperparameters. Most importantly, the `1-norm constraint over the residue vectors (see Eq.6) plays a crucial role in keeping long-term performance but slightly reduces short-term performance. This can be compensated by increasing the number of epochs per task. We have also considered keeping the projection vectors in the output of HRN (the output would be the sum of projection vectors concatenated with the sum of residue vectors) but we saw no significant impact on performance.

heading: 6 CONCLUSION AND FUTURE WORK
text: We have introduced the use of feature hashing to generate dynamic configurations in modular convolutional neural networks. Hash-routed convolutional networks generate stable features that exhibit excellent stability and plasticity across a variety of semantically different datasets. Results show excellent feature generation stability, surpassing typical and comparable continual learning benchmarks. Continual supervised learning using HRN still involves the use of different classifiers, even though compression techniques (such as (Chen et al., 2015)) can reduce required memory. This limitation is also a design choice, as it does not limit the use of HRN to supervised classification. Future work will explore the use of HRN in unsupervised and reinforcement learning setups.

heading: A APPENDIX

heading: A SELECTION AND EXPANSION ALGORITHMS
text: Algorithm 3: Unit selection and initialization Input: Hash vector h, Initialized units subset I (I{ is the subset of empty units), Used units subset J Output: Selected unit Ui if I = ∅ then
Select a random unit Ui Bi ← (h) ; // initialize its basis using h
else if I{ = ∅ or maxj∈I\J ‖Bjh‖2 ≥ τempty then
Select unit according to Eq.4 else
Select a random unit Ui from the remaining empty units Bi ← (h) ; // initialize its basis using h
Algorithm 4: Unit expansion Input: Hash vector h, initialized unit Ui p = Bih r = h− p if ‖p‖2 < τexpand and nonzero(Bi) < m then
Bi ← (Bi, r‖r‖ ) ; //replace a zero vector with the normalized residue

heading: B HYPERPARAMETERS AND ABLATION EXPERIMENTS
text: C IMPLEMENTATION DETAILS
This section details the network architectures and hyperparameters that were used for each experiment.

heading: D RUNTIME PERFORMANCE
text: This section compares the training and inference run times of each algorithm, considering the SVHN/incremental-Cifar100 experiment. All runs were performed on a 32 CPUs machine with an Nvidia P100 GPU and 16 GB of RAM. Performance figures have been averaged over 10 runs. Batch size is 16 for all runs and algorithms. Note that one training (resp. test) epoch for SVHN corresponds to 73257 (resp. 26032) samples; 1 training (resp. test) epoch for incremental-Cifar100 corresponds to 5000 (resp. 1000) samples. HRN typically require more time for training and in-
ference compared to a classical convolutional neural network. This is due to dynamic routing, as it is hardly compatible with batch processing and therefore exhibits poor performance on GPU. Each batch is split into individual samples and each sample is processed differently in the dynamic network. A more adequate processing backend would be a Many-cores/Network-On-Chip processor or an FPGA.

Review summaries:
This paper studies the problem of continual learning and proposes a new learning framework named hash-routed convolutional neural networks (HRN). HRN has a set of convolutional units and hashes similar data to the same unit. With this design, the paper claims three key contributions. (1) HRN provides excellent plasticity and more stable features. (2) HRN achieves excellent performance on a variety of benchmarks. (3) HRN can be used for unsupervised or reinforcement learning. 

For a learning model to learn continuously, it needs to handle new datasets without catastrophic forgetting or requiring the model to grow larger. This paper proposes a hash-routed convolution neural network where a different set of convolution filters are used depending on the data. New convolution filters can be added to the network without increasing the computational cost of the network.

Ok, but not good enough. The authors present Hash-Routed Convolutional Neural Networks (HRNs), intended to enable learning of stable representations for continual learning, i.e. representations that change little for previously-learned tasks as more tasks are learned. The authors benchmark HRNs against several baselines in a number of tasks. Overall, the proposed method does not appear as conceptually and empirically convincing as those of other papers at ICLR and similar conferences.