Year: 2019

Abstract:
Gradient Episodic Memory (GEM) is an effective model for continual learning, where each gradient update for the current task is formulated as a quadratic program problem with inequality constraints that alleviate catastrophic forgetting of previous tasks. However, practical use of GEM is impeded by several limitations: (1) the data examples stored in the episodic memory may not be representative of past tasks; (2) the inequality constraints appear to be rather restrictive for competing or conflicting tasks; (3) the inequality constraints can only avoid catastrophic forgetting but can not assure positive backward transfer. To address these issues, in this paper we aim at improving the original GEM model via three handy techniques without extra computational cost. Experiments on MNIST Permutations and incremental CIFAR100 datasets demonstrate that our techniques enhance the performance of GEM remarkably. On CIFAR100 the average accuracy is improved from 66.48% to 68.76%, along with the backward (knowledge) transfer growing from 1.38% to 4.03%.

heading: 1 INTRODUCTION
text: Catastrophic forgetting (McCloskey & Cohen, 1989) is a common phenomenon in deep learning that the model performance over past tasks can be harmed by the training process of a current task when we employ one single neural network to learn consecutive tasks. Continual learning (Ring, 1994), also known as lifelong learning (Thrun, 1994), is a specific research field in AI that focuses on avoiding or alleviating catastrophic forgetting. It is well known that humans and large primates can continually learn new skills and accumulate knowledge throughout their lifetime (Fagot & Cook, 2006).
Gradient Episodic Memory (GEM) (Lopez-Paz & Ranzato, 2017) is a significant method for continual learning. The basic idea is to modify each gradient of the current task such that the losses at the memories (data examples) from previously solved tasks will not increase, hence allowing positive backward knowledge transfer. The problem is formulated as a Quadratic Program with inequality constraints, and then solving its dual problem provides an efficient computation for a small number of dual variables. GEM outperforms two state-of-the-art methods, Elastic Weight Consolidation (EWC) (Kirkpatrick et al., 2017) and iCARL (Rebuffi et al., 2017) on variants of the MNIST and CIFAR100 datasets.
Despite the elegance of its mathematical formulation and the computational efficiency in solving the dual problem, the GEM model has following drawbacks for practical use.
1. The episodic memory is simply populated with the last m = M/T examples from each task in their current implementation, where M is the total budget size of memory locations for totally T tasks. The authors of GEM mentioned that better memory update strategies could be employed to obtain a representative set of examples for past tasks, such as building a coreset per task (Lucic et al., 2018).
2. The inequality constraints of gradients appear to be quite restrictive, requiring that the gradient update can not increase any loss of all previously solved tasks. When two tasks are competing or conflicting in the gradient update directions, especially with a large number of past tasks, these constraints have to be violated and the feasible solution might be null.
3. The gradient constraints only assure to avoid catastrophic forgetting, but might not promote positive backward knowledge transfer in some scenarios. For instance, we may obtain a gradient vector orthogonal to all gradients of previous tasks in the constrained optimization problem. In this case, GEM is greedy in minimizing the loss of the current task, overlooking the need of backward transfer to previous tasks. An ideal model for continual learning should consider a better trade-off between optimizing performance of the current task and backward transfer to previously solved tasks.
To address these issues, in this paper we propose three techniques that improve the performance of GEM. These techniques come from successful practice in Support Vector Machines (SVMs) and deep learning approaches. In concrete, we use the notion of margins to select representative data points as episodic memories. We also leverage slack variables to allow violations of the constraints, and aggressively encourage backward knowledge transfer to previous tasks. Experiments on MNIST and CIFAR100 datasets corroborate the improvements of our techniques over the original GEM model. Also our methods increase little overhead in computational efforts.
The paper is organized as follows. In Section 2, we first survey several recent methods on continual learning and explain why we focus on improving GEM. Section 3 offers a brief review of the GEM algorithm. In Section 4, we elaborate our three improvements and discuss the underlying motivations. Section 5 presents the experimental results and comparison analysis, and Section 6 concludes the paper.

heading: 2 RELATED WORK
text: According to Xu & Zhu (2018), recent methods for continual learning can be roughly classified into two large categories, distinguished by whether the network architecture changes through a continuum of tasks.
The first category attempts to modify the network architecture to alleviate catastrophic forgetting. Fernando et al. (2017) proposed a neural network model called PathNet, in which there are ten or twenty modules in each layer and for one task only three or four modules are dynamically chosen in each layer using an evolutionary approach. Progressive neural networks (Rusu et al., 2016) aims at accommodate the new coming task by dynamically expand the architecture with a fixed size of nodes or layers, leading to an extremely large network structure with high redundancy. In Dynamically Expandable Network (DEN) (Yoon et al., 2017) this issue is slightly alleviated by employing group sparsity regularization when expanding the networks. However many hyperparameters are involved, including various regularization and thresholds, and careful tuning is challenging. Xu & Zhu (2018) proposed Reinforced Continual Learning (RCL) approach that searches for the best neural architecture for each coming task via reinforcement learning strategies. Like other expandable networks, this approach still suffers from higher model complexity than non-expandable networks. Also reducing its training time is a major concern.
Another category maintain a fixed network architecture with large capacity through learning. Oquab et al. (2014) proposed a weight transfer method by freezing early layers while cloning and finetuning later layers on the new task. In “synaptic” memory methods (Kirkpatrick et al., 2017; Zenke et al., 2017), learning rates are adjusted to minimize updates in weights important for previous tasks. Lee et al. (2017) proposed to incrementally match the moment of the posterior distribution of the neural network trained on the first and the second task, respectively. In Zeng et al. (2018) an Orthogonal Weights Modification (OWM) was proposed to ensure that new learning processes will not interfere with previously learned tasks, but can not enable backward knowledge transfer. In Shin et al. (2017); Kemker & Kanan (2018) previously acquired knowledge can be acquired by replaying of pseudo-data generated by Generative Adversarial Networks (GANs) or generative autoencoders, without revisiting actual past data for the coming task. Several “episodic” memory approaches (Jung et al., 2016; Li & Hoiem, 2016; Triki et al., 2017; Rebuffi et al., 2017) aim at storing and replaying examples from past tasks to keep predictions invariant via distillation (Hinton et al., 2015). GEM (Lopez-Paz & Ranzato, 2017) belongs to this class of episodic memory approaches, but unlike prior work, allows for backward transfer.
Comparing to these recent approaches on continual learning, GEM is relatively lightweight, computationally efficient and capable of achieving high accuracies. However, there is still room to improve GEM with respect to the limitations stated in Section 1.

heading: 3 A BRIEF REVIEW OF GEM
text: Most of the literature on continual learning (Rusu et al., 2016; Fernando et al., 2017; Kirkpatrick et al., 2017; Rebuffi et al., 2017) focused on a traditional setting: (1) the number of tasks is small; (2) the number of examples per task is large; (3) the learner allows for several passes over the examples per task; (4) the average performance across all tasks serves as the only metric. In contrast, a “more human-like” setting was considered in GEM: (1) the number of tasks is large; (2) the number of training examples is small for each task; (3) the learner observes the examples of per task only once; (4) knowledge transfer in backward and forward directions is assessed. Therefore following this new setting, the learner will observe the continuum of data in a manner of example by example
(x1, t1, y1), . . . , (xi, ti, yi), . . . , (xn, tn, yn),
where each triplet (xi, ti, yi) contains a input vector, a task index, and a target vector. Note that any order on the tasks can be allowed.
The optimizing problem of GEM (Lopez-Paz & Ranzato, 2017) is
min w
1 2 ‖g − w‖22
s.t. 〈w, gk〉 ≥ 0, ∀k < t, (1)
where g is the gradient vector calculated on the batch data of the current task, and gk here is the gradient on the episodic memory Mk of the past task k. Note that the episodic memory Mk stores a subset of the observed examples from task k. If the gradient update g of the current batch fulfills all the constraints, the learner directly uses it to update like the usual gradient descent method. Otherwise, we should find a projection of g in L2-norm distance to satisfy any constraint related each previous task, and then use the solution w to update the network weights.
We obtain a standard form of Quadratic Program (QP) by expanding the squared objective and discarding the constant term gT g:
min w
1 2 wTw − gTw
s.t. Gw ≥ 0, (2)
where G = (g1, . . . , gt−1). The primal QP problem can be translated into its dual problem (Dorn, 1960), which is the final optimizing problem:
min α
1 2 αTGGTα + (Gg)Tα
s.t. α ≥ 0, (3)
We can recover the projected gradient update as w∗ = GTα∗ + g where α∗ is the solution to the dual problem. Note that solving the dual problem is computationally efficient since there are only t− 1 variables in α, much smaller than the number of weights in a neural network.

heading: 4 OUR IMPROVEMENTS
text: We propose three improvements to GEM: a technique to choose examples which can represent the past tasks better — support examples; a technique to tolerant some slight violation in gradient constraints on past tasks — soft gradient constraints; a technique to aggressively encourage gradient descend over previous tasks — positive backward transfer.

heading: 4.1 SUPPORT EXAMPLES
text: The first improvement is inspired from the idea of margins in Support Vector Machines (SVMs) (Williams, 2003). Due to the KKT theorem, a small set of support vectors obtained from a Quadratic
Program determines the decision boundary of SVM for binary classification. In the context of continual learning, the decision is crucial to identify what samples should be chosen in the episodic memory, since we can only store a limited budget of representative samples from previous task. In SVMs support vectors arise naturally as a solution from the QP problem of SVM; however such optimization problem does not apply to neural networks. In GEM a simple method is adopted, that is, the last m examples of task t are stored into the episodic memory Mt. Also the examples are shuffled randomly, which means that the storage is essentially random and ad hoc.
In this work, we propose an idea of choosing samples based on the notion of margins. We assume that the problem to solve here is multi-class classification, so the prediction from the network’s forward propagation can be available. Suppose the output prediction h(x, t, y) on a triplet example (x, t, y) is computed through a softmax activation function, with value falling in the range [0, 1]. The following gives the definition of margins:
margin := h(x, t, y)−max y′ 6=y
h(x, t, y′). (4)
When the classifier h makes a correct prediction, the margin is positive. Otherwise when h misclassifies the example, we have margin ≤ 0. A margin value indicates the confidence of the prediction of an triplet example: larger the margin is in magnitude, more confidence we have in the prediction.
In order to alleviate catastrophic forgetting, the most important thing is to ensure that the examples of past tasks can be correctly classified to retain the prediction performance. Usually we have a much smaller budget for the episodic memory than the number of examples per task. For instance, in experiment on CIFAR100, the number of total samples is 2500 per task, while the episodic memory is 256 per task. On the one hand, we can not afford to assign the memory to the examples whose margins are smaller than 0, which means they could not be classified correctly in the past task or even these examples are outliers. On the other hand, for the examples whose margins are relatively large, indicating that the network can classify them with a strong confidence, these example should not be put into the memory either. We define the Support Examples as those examples being classified correctly but with a limited confidence. In experiments we simply use a confidence interval to select the support examples (we specify the interval as hyperparameters per task). In this way, the episodic memory can be used more efficiently, and at the same time, we argue that the chosen support examples can represent the past tasks better.

heading: 4.2 SOFT GRADIENT CONSTRAINTS
text: This idea is inspired by the soft-margin technique in SVMs, which is a compromise to some wrongly classified examples by linear classifiers. In continual learning, the difficulty of optimizing the gradient to be consistent to every gradient direction of past tasks is increasing along the process of learning new tasks. The constraints in (2) mean that we want the optimized gradient must have a similar direction with all of the gradients of past tasks, which is too restrictive, especially when the number of tasks is large or the tasks are competing or conflicting.
So we propose the following soft gradient constraints:
min w
1 2 wTw − gTw + CΣt−1k=1ξk,
s.t. Gw ≥ −ξ, ξk ≥ 0 ∀k < t, (5)
ξ = (ξ1, . . . , ξt−1) is the slack vector, C is the trade-off parameter (the bigger, the stricter for w to satisfy the constraints). Once any original constraint in Gw ≥ 0 is violated, we impose a penalty in the objective. With the KKT theorem, we have the following dual problem as α is the Lagrange multiplier vector:
min α
1 2 αTGGTα + (Gg)Tα,
s.t. 0 ≤ α ≤ C1n. (6)
Like in SVMs, the hyperparameter C needs to be tuned. For the first several tasks, it is relatively easy to make the gradient update completely satisfy the constraints on all the past tasks. When the number of past tasks is increasing, it is much more difficult to have the similar direction to all the past tasks’ gradient simultaneously. So we need to loose the constraint to some extent.
Here, we propose a method just like the learning rate decay in neural network training: we can initialize C to a relatively big value, which should ensure a very strict constraint for first several tasks, while let C decay along the process of training. In other words, after finishing training a certain number of tasks, we set C smaller to tolerant more freedoms in constraint violations. This trick will maintain a good performance, and at the same time make the model more robust.
The authors of GEM claimed that adding a small offset γ ≥ 0 to the Lagrangian multipliers in (2) can enable the network to perform better. However, this is an ad-hoc practice and lacks rationality: it is not faithfully follow their mathematical formulation. In our method, we can just avoid this ad-hoc practice and guarantee that just use the original constraints with slack variables will produce a good performance. Our soft constraints offer a better explanation to this issue.

heading: 4.2.1 POSITIVE BACKWARD TRANSFER
text: GEM assumes that if the inner product of the proposed gradient update and the gradients of past tasks is no less than zero, the current update will not cause catastrophic forgetting. Some extreme scenarios might occur that the found gradient projection is orthogonal to all the gradients of previous tasks, indicating that there is no contribution to backward transfer. Further, the non-negative constraints in inner products only require the angles between two gradient vectors lying in the interval [−90◦, 90◦], totally ignoring the cosine similarity in magnitude. In our opinion, we should specify the magnitude of the inner products of two gradient vectors for enhancing positive backward transfer to previously solved tasks. We can modify (2) to impose magnitude penalties:
min w
1 2 ‖g − w‖22
s.t. 〈w, gk〉 ≥ ε‖w‖‖gk‖, ∀ k < t, ε ≥ 0.
This new constraint imposes cosine similarity actually, so it can represent the angle and the magnitude simultaneously. Because we do not know ‖w‖ in advance, we can use ‖g‖ as a proxy since w is the projection of g:
min w
1 2 ‖g − w‖22
s.t. 〈w, gk〉 ≥ ε‖g‖‖gk‖, ∀ k < t, ε ≥ 0. (7)
Similarly we get the final dual optimizing problem, which includes soft gradient constraints.
min α
1 2 αTGGTα + (Gg + ε‖g‖‖gk‖1n)Tα,
s.t. 0 ≤ α ≤ C1n. (8)
After we solve α, which has the variables equal to the number of past tasks, we can use w = GTα + g to get the modified gradient and use it to update current network.
Here ε is a hyperparameter. Similarly, the first several tasks are easier for network to enable positive backward transfer. And when the number of tasks increase, we can reuse the idea of ‘decay’ to weaken the magnitude of inner-product similarity, approaching zero gradually.

heading: 5 EXPERIMENTS

heading: 5.1 DATASETS AND SETTINGS
text: We do experiments on two dataset same to GEM (Lopez-Paz & Ranzato, 2017): MNIST Permutations (Kirkpatrick et al., 2017) and Incremental CIFAR100 (Rebuffi et al., 2017). Besides, we also do experiment on MNIST Mix (Xu & Zhu, 2018),
1. The MNIST Permutations dataset is derived from the famous dataset on handwritten digits (LeCun et al., 1998), which randomly generates different pattern of pixel permutation for each task to exchange the position of the original images of MNIST.
2. The Incremental CIFAR100 dataset is derived from CIFAR100 (Krizhevsky, 2009), which averagely devides the whole classes in CIFAR100 into T parts, and T here is the number of tasks. So in each task, there is 100/T different classes that are not included in other tasks.
3. The MNIST Mix dataset is also derived from MNIST, which has 10 MNIST Permutations (P1, P2, ..., P10) and 10 MNIST Rotations (R1, R2, ..., R10) (Lopez-Paz & Ranzato, 2017), whose image is rotated by a fixed angle from original image of MNIST. The consecutive tasks are arranged in the order P1, R1, P2, R2, ..., P10, R10.
To compare our method to the original GEM, we use the same settings on datasets. The number of tasks is set as T = 20. On the MNIST Permutations dataset there are 1000 examples per task and On the Incremental CIFAR100 dataset there are 2500 examples per task. In the basic comparison, the size of the total budget on episodic memory is set as 5120, which means that we can store 256 examples for each task.
The network architectures are also same to the experiments of the original GEM: for MNIST Permutations, we use fully-connected neural networks with two hidden layers of 100 ReLU units; for Incremental CIFAR100, we use a smaller version of ResNet18 (He et al., 2016), which has three times less feature maps for each layer than the orginal ResNet18 and has a final linear classifier for each task.

heading: 5.2 COMPETING METHODS
text: To solve the optimizing problem of soft gradient constraint, we have to change the toolbox in original code of GEM as cvxpy. So we conduct experiments both on our run of the original GEM and the GEM with the cvxpy toolbox.
Besides, we compare with other several methods:
1. Single, a single predictor for all the tasks.
2. Multimodal, a multimodal predictor, whose architecture is same to “single” and has a dedicated input layer for each task (only tested on MNIST Permutations dataset).
3. Independent, a network that there is a specific independent predictor for each task which has the same architecture as “single” while the number of hidden units are T times less than “single”.
4. Elastic Weight Consolidation (EWC) (Kirkpatrick et al., 2017).
5. iCARL (Rebuffi et al., 2017), the class-incremental learner uses episodic memory and a nearestexemplar algorithm (tested only on Incremental CIFAR100).
These compared methods are same to the settings in (Lopez-Paz & Ranzato, 2017). In Basic Comparison, we report the results reported in original paper of GEM, as well as our run of the original GEM, the GEM using cvxpy toolbox and our improved method. In other experiments, the method GEM is always the version of using cvxpy.

heading: 5.3 EVALUATION METRICS
text: The evaluations we use are average accuracy and positive backward transfer. The backward transfer can be calculated as:
Backward Transfer := 1
T − 1 T−1∑ i=1 (ATi −Aii)
where Aij is the accuracy of task j after learning of task i.

heading: 5.4 BASIC COMPARISON
text: Table 1 shows the basic comparison results. To be succinct, MNIST Permutation is denoted by MNIST P and MNIST Mix is denoted by MNIST M. We can see that our method can perform better both on average accuracy and positive backward transfer than the original GEM on all three datasets. For example on CIFAR100, our method improves from 66.48% (our run of GEM) to
68.76%, with backward transfer growing from 1.38% to 4.03%. Table 2 lists the hyperparamters used in experiments.
Figure 1 reports the evolution curves of average accuracy for all tasks and the accuracy of the first task as well. The details of numerical values are given in Appendix A. The evolution of average accuracy of all tasks indicates the comprehensive performance of the method. Our method perform best comparing to all other methods on average accuracies. Also on all three datasets, our method keeps a relatively stable performance on the first task and always has improvements through the whole learning process. We think the performance evolution of the first task only provide an small aspect of the comparison; improvements of average accuracy could be more important.

heading: 5.5 PERFORMANCE ON DIFFERENT MEMORIES
text: We also do some experiments on different budget of memories for the three datasets, with results shown in Table 3. We can see that larger budgets of memories can enhance the accuracy, and our method improves the original GEM on all settings. Table 4 shows the hyperprameters for our method.

heading: 5.6 ABLATION STUDY
text: We conduct ablation study to figure out the contribution of each improvements, with results shown in Figure 2. The details of numerical results are reported in Appendix B.
We can see that using the positive backward transfer separately can give an improvement, but the support examples and soft gradient constraint can not independently improve the performance. However, support examples can give an improvement combined with soft gradient constraint or positive backward transfer, while soft gradient constraint can probably produce a further promotion with the combination to the other two methods. So the combination of support examples and positive backward transfer can provide stable improvements, whereas the contribution of soft gradient constraint depends on the dataset.

heading: 6 CONCLUSION
text: We notice the fact of the precious space of memories in continual learning and the incremental difficulty through progressive learning. The GEM model is relatively lightweight, computationally fast and robust to yield high accuracy, so we propose three techniques to improve GEM. Specifically, we propose support examples to make good use of memories, formulate soft gradient constraints to accommodate competing tasks, present cosine similarity to encourage positive backward transfer over previously solved tasks. From experiments we can see the performance improvements of our techniques over the original GEM, obtaining better average accuracy and higher backward transfer. Also our method increase little computational burdens, with the cost of several hyper-parameters needing to tune. Therefore we argue that our improvements can promote GEM to be applied to more practical applications.

heading: A A RESULTS IN ALL TASKS’ AVERAGE ACCURACY AND THE ACCURACY OF THE FIRST TASK

heading: B B ACCURACY IN ABLATION

Review summaries:
Paper proposes three improvements upon the gradient episodic memory (GEM) method [Lopez-Paz,2017]. The three improvements address 1. A way of selecting which exemplars to store (originally random), 2. The strictness of the constraints is loosened by considering slack vectors, 3. The update is improved by promoting positive backward transfer, not only limiting the gradient to the constraints imposed by exemplars of previous tasks, but aiming to improve also for previous tasks by preferring gradients which have high cosine similarity with the gradients on exemplars. Results on CIFAR 100 and MNIST permuted are presented. Noteworthy is the improved backward transfer on CIFAR 100 when compared with GEM.