Continual Backprop: Stochastic Gradient Descent with Persistent Randomness — part 2/3
Cleaned-text code points [15709, 31652). Bibliography omitted here; source.md includes it.
The weights of the learning network are different at the beginning and after a few gradient-based updates. In the beginning, they were small random weights; however, after learning for some time, the weights became optimized to reduce the error for the most recent input distribution. Thus, the starting weights to get to the next solution have changed. As this difference in the weights is the only difference in the learning algorithm across time, the initial weight distribution must have some special properties that allow the learning network to adapt fast. The initial random distribution might have many properties that allow fast adaptation, like diversity of features, non-saturated features, small weight magnitude etc.
## 4 Continual Backprop
The benefits of initializing with small random numbers in Backprop are only present initially, as initialization with small random weights only happens at the start. This special initialization makes Backprop temporally asymmetric as it does a special computation at the beginning which is not continued later. But continually learning algorithms should be temporally symmetric as they should do similar computations at all times.
One way to extend the benefits of initialization throughout learning is by continually injecting random features. A feature refers to a hidden unit in a network. However, we are interested in continually learning methods that have similar memory requirements at all times because methods whose memory requirements grow with the amount of data are not scalable. So we also need to remove some features without affecting the already learned function too much. The features to be replaced can be chosen either randomly or using some measure of utility.
Continually replacing low utility features with new random features is a natural way to extend the benefits of initialization to all times while using constant memory. We use a generate-and-test process to continually replace low utility features with new random features. This process has two parts. First is a generator that provides new random features from the initial distribution. The second is a tester that finds low utility features and replaces them with features proposed by the generator. Our generate-and-test process is applicable to arbitrary feed-forward networks, modern activations, and optimizers. While the prior algorithm (Mahmood & Sutton, 2013) was limited to learning networks with a single hidden layer, only one output, LTU activation and could only use SGD to learn.
The generator creates new features by randomly sampling from the distribution that was used to initialize the weights in the layer. When a new feature is added, its outgoing weights are initialized to zero. Initializing as zero ensures that the newly added feature does not affect the already learned function. However, initializing the outgoing weight to zero makes it vulnerable to immediate replacement. The new features are protected for maturity-threshold , m m , number of updates.
The tester finds low utility features and replaces them. At every time-step, replacement-rate , ρ \rho , fraction of features are replaced in every layer. Our utility measure has two parts: first measures the contribution of the feature to the next features, and second measures features’ ability to adapt.
The contribution-utility is defined for each connection or weight and for each feature. The basic intuition behind the contribution part is that magnitude of the product of feature activation, and outgoing weight gives information about how useful this connection is to the next feature. If the features contribution to the next feature is small, it can be overwhelmed by contributions from other features. Then the current feature is not useful for the consumer. The same measure of connection utility was proposed by Hu et al. (2016) for the network pruning problem. We define the contribution-utility of a feature as the sum of the utilities of all its outgoing connections. The contribution-utility is measured as a running average with a decay rate, η \eta . In a feed-forward neural network, the contribution-utility, c l , i , t c_{l,i,t} , of the i i th features in layer l l at time t t is updated as c l , i , t \displaystyle c_{l,i,t} = ( 1 − η ) ∗ | h l , i , t | ∗ ∑ k = 1 n l + 1 | w l , i , k , t | + η ∗ c l , i , t − 1 , \displaystyle=(1-\eta)*|h_{l,i,t}|*\sum_{k=1}^{n_{l+1}}|w_{l,i,k,t}|+\eta*c_{l,i,t-1}, (1) where h l , i , t h_{l,i,t} is the output of the i i th feature in layer l l at time t t , w l , i , k , t w_{l,i,k,t} is the weight connecting the i i th unit in layer l l to the k k th unit in layer l + 1 l+1 at time t t , n l + 1 n_{l+1} is the number of units is layer l + 1 l+1 .
In the network pruning problem, the connections are removed after learning is done. However, generate-and-test is used during learning, so we need to consider the effect of the learning process on the contribution. Specifically, we need to consider the part of the contribution that will be transferred to the bias when a feature is removed. When a feature is removed, SGD will transfer the average part of the contribution to the bias unit over time. We define, the mean-corrected contribution utility, z l , i , t z_{l,i,t} , is the magnitude of the product of connecting weight and input minus its average value, f l , i , t \displaystyle f_{l,i,t} = ( 1 − η ) ∗ h l , i , t + η ∗ f l , i , t − 1 , \displaystyle=(1-\eta)*h_{l,i,t}+\eta*f_{l,i,t-1}, (2) f ^ l , i , t \displaystyle\hat{f}_{l,i,t} = f l , i , t − 1 1 − η a l , i , t , \displaystyle=\frac{f_{l,i,t-1}}{1-\eta^{a_{l,i,t}}}, (3) z l , i , t \displaystyle z_{l,i,t} = ( 1 − η ) ∗ | h l , i , t − f ^ l , i , t | ∗ ∑ k = 1 n l + 1 | w l , i , k , t | \displaystyle=(1-\eta)*|h_{l,i,t}-\hat{f}_{l,i,t}|*\sum_{k=1}^{n_{l+1}}|w_{l,i,k,t}| + η ∗ z l , i , t − 1 , \displaystyle+\eta*z_{l,i,t-1}, (4)
where h l , i , t h_{l,i,t} is features’ output, w l , i , k , t w_{l,i,k,t} is the weight connecting the feature to the k k th unit in layer l + 1 l+1 , n l + 1 n_{l+1} is the number of units is layer l + 1 l+1 , a l , i , t a_{l,i,t} is the age of the feature at time t t . Here, f l , i , t f_{l,i,t} is a running average of h l , i , t h_{l,i,t} and f ^ l , i , t \hat{f}_{l,i,t} is the bias-corrected estimate.
We define the adaptation-utility as the inverse of the average magnitude of the features’ input weights. The adaptation-utility captures how fast a feature can adapt. The inverse of the weight magnitude is a reasonable measure for the speed of adaptation for Adam-type optimizers. In Adam, the change in a weight in a single update is either upper bounded by the step-size parameter or a small multiple of the step-size parameter (Kingma and Ba, 2015). So, during each update, smaller weights can have a larger relative change in the function they are representing.
We define the overall utility of a feature as the bias-corrected running average of the product of its contribution-utility and adaptation-utility. The overall utility, u ^ l , i , t \hat{u}_{l,i,t} , becomes y l , i , t \displaystyle y_{l,i,t} = | h l , i , t − f ^ l , i , t | ∗ ∑ k = 1 n l + 1 | w l , i , k , t | ∑ j = 1 n l − 1 | w l − 1 , j , i , t | \displaystyle=\frac{|h_{l,i,t}-\hat{f}_{l,i,t}|*\sum_{k=1}^{n_{l+1}}|w_{l,i,k,t}|}{\sum_{j=1}^{n_{l-1}}|w_{l-1,j,i,t}|} (5) u l , i , t \displaystyle u_{l,i,t} = ( 1 − η ) ∗ y l , i , t + η ∗ u l , i , t − 1 , \displaystyle=(1-\eta)*y_{l,i,t}+\eta*u_{l,i,t-1}, (6) u ^ l , i , t \displaystyle\hat{u}_{l,i,t} = u l , i , t − 1 1 − η a l , i , t . \displaystyle=\frac{u_{l,i,t-1}}{1-\eta^{a_{l,i,t}}}. (7)
Figure 4 describes the utility for a feature. Our utility measure is more general than the one proposed by Mahmood and Sutton (2013), as ours applies to networks where features have multiple outgoing connections. In contrast, theirs was limited to the case when features with one outgoing connection.
The final algorithm combines Backprop with our generate-and-test algorithm to continually inject random features from the initial distribution. We refer to this algorithm as Continual Backprop (CBP). CBP performs a gradient-descent and a generate-and-test step at every time step. Algorithm 1 specifies the CBP algorithm for a feed-forward neural network. We describe CBP with Adam in Appendix B which contains adam specific details. The name “Continual” Backprop comes from an algorithmic perspective. The Backprop algorithm, as proposed by Rumelhart et al. (1987), had two parts, initialization with small random numbers and gradient descent. However, initialization only happens initially, so Backprop is not a continual algorithm as it does not do similar computation at all times. On the other hand, CBP is continual as it performs similar computation at all times.
Continual Backprop in semi-stationary problems
The most common ways to keep the weight distribution close to the initial distribution are L2 regularization and BatchNorm. So, we use these two methods along with BP and compare them to CBP on semi-stationary problems. As we study online problems and we consider incremental updates, we used OnlineNorm (Chiley et al., 2019), an online variant of BatchNorm.
Figure 5 shows the online squared error for various learning algorithms with tanh and Relu networks. The online error is binned into bins of size 20k. The results are averaged over 100 runs. For all configurations of parameters for all algorithms, we used the same data: they had the same sequences of input-output pairs. All algorithms used SGD with step-size 0.01. For CBP and BP+L2, we used replacement-rate and weight-decay values that had the least total error over 1M examples. Figure 5 also shows the sensitivity of CBP and BP+L2 to replacement-rate and weight-decay respectively. OnlineNorm has two main parameters; they are used for computing running averages. The default values of these parameters are 0.99 and 0.999. We chose the best set of parameters from { 0.9 , 0.99 , 0.999 , 0.9999 } ∗ { 0.9 , 0.99 , 0.999 , 0.9999 } \{0.9,0.99,0.999,0.9999\}*\{0.9,0.99,0.999,0.9999\} . In Appendix A, we show the performance of these algorithms with other activation functions. In Appendix B, we also show the performance of these algorithms using Adam. For all the experiments with CBP we use η = 0.99 \eta=0.99 and m = 100 m=100 .
Figure 5 shows that all three algorithms: CBP, BP+L2, and BP+OnlineNorm, perform significantly better than BP. However, BP+OnlineNorm is not stable for any of the activations as its performance degrades over time. In comparison, BP+L2 regularization is stable for the tanh network but not the ReLU network. The parameter-sensitivity plot in Figure 5 shows that CBP and BP+L2 perform better than BP for most values of replacement-rate and weight-decay. And that CBP is much less sensitive to the parameter values than L2. For ReLU, CBP significantly outperformed BP+L2.
In Appendix C, we do an ablation study for different parts of our utility measure and compare it to other baselines like random utility and weight magnitude based utility (Mahmood and Sutton, 2013). We find that all the components of our utility measure are needed for best performance.
Figure 7 shows the performance of various learning algorithms on Permuted MNIST. We used SGD with a step size of 0.003. We binned the online accuracy into bins of size 60,000. The results are averaged over ten runs. And, for OnlineNorm, we did a parameter sweep for { 0.9 , 0.99 , 0.999 , 0.9999 } ∗ { 0.9 , 0.99 , 0.999 , 0.9999 } \{0.9,0.99,0.999,0.9999\}*\{0.9,0.99,0.999,0.9999\} . For L2, we chose the best weight-decay among { 1 e − 3 , 1 e − 4 , 1 e − 5 , 1 e − 6 } \{1e-3,1e-4,1e-5,1e-6\} .
Figure 7 show that among all the algorithms, only CBP is stable as its performance does not degrade over time. The performance of all the other algorithms degrades over time.
Figure 8 shows that the average weight magnitude in the last layer increases over time for BP. Large weight magnitudes are problematic for both SGD and Adam. For SGD, large weights lead to blown-up gradients for the inner layer, which leads to unstable learning and saturated features. On the other hand, Adam has an upper bound on the weight change in a single update. Due to this upper limit on the effective change in each weight, the relative change in the function is smaller when the weights are large, which means slower adaptation. Both Adam and SGD on their own are unsuitable for Continual learning.
Continual Learning in a non-stationary RL problem
We used the PPO algorithm as described by Schaulman et al. (2017). We used separate networks for policy and value function, and both had two hidden layers with 256 hidden units. We used tanh activation as it performs the best with on-policy algorithms like PPO (Andrychowicz et al., 2020).
To use CBP with PPO, we use CBP instead of BP to update the networks’ weights. Whenever the weights are updated using Adam, we also update them using generate-and-test. We call the resulting algorithm Continual PPO , we describe it in Appendix D.
Figure 8 shows the performance of PPO, PPO+L2, and Continual PPO (CPPO) for Lecun initialization (Lecun et al., 1998) on Slippery Ant. For L2, we chose the best weight-decay, and for CPPO we chose the best replacement-rate, maturity-threshold pair. All other parameters were the same in PPO, PPO+L2, and CPPO. We describe the parameters in Appendix D. In the figure, the episodic return is binned among bins of 40,000 time-steps.
Figure 8 shows that the performance of PPO degrades a lot in our non-stationary RL problem. This degradation is similar to the degradation of Backprop’s performance on semi-stationary problems, where it performed well initially, but its performance got worse over time. Figure 8 shows that both CPPO and PPO+L2 perform substantially better than PPO, and CPPO performed best, where it continually performed as well as it did initially.
## 5 Related works
Continual learning or lifelong learning has been studied for a long time from several different perspectives. Ring (1998) considered it as a reinforcement learning problem in a non-Markovian environment. On the other hand, Caruana (1998) considered it as a sequence of tasks. There are two major goals in continual learning: memorizing useful information and adapting to the changes in the data stream changes by finding new useful information. Memorizing useful information is difficult for current deep-learning methods as they tend to forget previously learned information (McCloskey and Cohen 1989, French 1997, Parisi et al. 2019). Various ingenious methods have been proposed to tackle the forgetting issue (Kirkpatrick et al. 2017, Aljundi et al. 2018, Riemer et al. 2019, Javed et al. 2019); however, it still remains an unsolved problem. In this work, we focused on continually finding useful information but not on remembering useful information.
Multiple recent works have focused on adapting to the changes in the data stream by finding new useful information (Rusu et al. 2016, Finn et al. 2017, Wang et al. 2017; Nagabandi et al. 2019, Finn et al. 2019). However, none of the prior works studied problems with thousands of non-stationarities. The problem settings in most works were offline as they had two separate phases, one for learning and the other for evaluation. And in the evaluation phase, there were only a handful of non-stationarities. On the other hand, Finn et al. (2019) studied the fully online problem setting. Although this works investigated the interesting, fully online case, there were still a small number of non-stationarities. Also, the algorithms proposed by Finn et al. (2019) are not scalable as they require storing all the data seen so far. The closest work to ours is by Rahman (2021), where they studied learning in supervised learning problems where the target function changes over time.