In the continual learning setting, we wish to efficiently learn a sequence of tasks without forgetting how to perform previously learned tasks. Many approaches have been proposed to address this problem, with recent work focused mainly on deep learning (Kirkpatrick et al., 2017;Rebuffi et al., 2017;Yoon et al., 2018). While these approaches boast impressive predictive power, they are limited by a host of drawbacks including high computational costs, large memory requirements, and poor performance on nontrivial continual learning benchmarks with long task sequences and task-identification information withheld (Farquhar & Gal, 2018;Díaz-Rodríguez et al., 2018).
We propose an alternative, matching-based algorithm which combines ideas from ART with IPCA to improve predictive performance for high-dimensional data. ART is an attractive solution to continual learning because of its proven stability guarantees which imply that catastrophic forgetting will not occur with respect to the training data (Grossberg, 2020). PCA is a well-known linear dimensionality reduction technique which can be effectively used as a data preprocessing step for both supervised and unsupervised learning tasks. Many incremental versions of PCA have been proposed to efficiently update principal component estimates without recomputing eigenvectors from the full covariance matrix (Weng et al., 2003;Zhao et al., 2006;Ross et al., 2008).
We begin by formally defining our notation and problem statement. We are given a set of tasks T 1 . . . T T where each task T i has a corresponding dataset D i = (X i , y i ). We focus on supervised classification tasks with features X i ∈ R ni×d and categorical labels y i ∈ N ni×1 , though our proposed model can easily be extended to unsupervised clustering. We reduce our data's dimension from d → k using IPCA matrix P ∈ R k×d whose rows consist of the top-k estimated eigenvectors of the data's covariance matrix. The weights in the original space and IPCA reduced space are denoted by w org ∈ R d×1 and w red ∈ R k×1 respectively, with w i red = P i w org denoting the weight in reduced space under iteration i of IPCA.
Our proposed model does not require task identifiers, though this information may be optionally included to improve performance. It is applicable to class-incremental, task-incremental, and domainincremental learning, and only requires that features have consistent dimensionality across all tasks. Algorithm 1 describes the training procedure while the inference procedure and intuition behind the model are discussed in Appendix A.1. Time and space complexity are given in Appendix A.2. We answer this question by observing that the updated version of IPCA can be applied to transform the model's weights (learned in the original space) since the weights are simply a linear combination of training samples. In other words, learning in the current IPCA reduced space results in the same weights as previously learning in the original space, then applying the current version of IPCA. This argument is formalized in Proposition 1 with proof and further explanation in Appendix A.3. Proposition 1. Let x 1 . . . x m be the training samples which have matched to weight w under some previous IPCA transformation(s) P 1 . . . P i-1
foot_0 . Assuming that these samples x 1 . . . x m still match to weight w under the current IPCA transformation P i , then learning the weight w i red in the reduced space is equivalent to first learning the weight w org in the original space, then applying IPCA P i .
We evaluate our proposed algorithm on the Split MNIST and Split Fashion-MNIST benchmarks in the single-headed setting with task identifiers unavailable at inference. Our proposed IPCA model is compared against two variations: (1) with no PCA and (2) with static PCA learned on the entire dataset (serving as expected lower and upper bounds for IPCA performance). The results in the top half of Table 1 are consistent with these expectations. To contextualize our model's performance, we include results from Sokar et al. (2021) A verbal description of Algorithm 1 is as follows. Each time a new task arrives, the IPCA matrix is updated using all of the task's data. Sequentially, for each training sample in the task, the bestmatching weight is computed using a similarity metric in the IPCA reduced space of dimension k.
If the best-matching weight is sufficiently similar to the sample and it corresponds to the correct class, then the weight is updated in the original space of dimension d. Otherwise, a new weight is initialized to the current sample in the original space, with its corresponding class label recorded. At inference, simply compute similarity scores between the test sample and all learned weights in the reduced space, then predict the class corresponding to the weight with the largest similarity score.
The main idea behind our proposed algorithm is to learn weights in the original space and perform matching in the IPCA reduced space. Storing the weights in the original space allows the model to adapt to changes in the input representation caused by IPCA updates. This adaptation is done by simply applying the current version of IPCA to the previously learned weights.
The space complexity of our model during training is O(kd + W d) where W is the total number of learned weights. During training, both the current IPCA matrix and weights in the original space must be stored. The time complexity for training is O(N kd + T W kd + N W k) given N total training samples and T tasks. This consists of the time required for learning/applying IPCA updates to the data, applying IPCA updates to the weights, and performing matching.
The space complexity of our trained model is O(kd + W k). The time complexity for inference on a single sample is also O(kd + W k). This is because the IPCA matrix and learned weights must be stored in order to transform new data and compute matches at inference. These bounds assume that the learned weights are stored in the reduced space of dimension k after all training is completethis is a small implementation detail included in the time complexity given above for training. Note that the number of weights W can be controlled by setting the vigilance parameter ρ, with smaller values of ρ resulting in fewer weights and coarser granularity.
Proposition 1 attempts to establish an equivalence between learning incrementally in the original space and learning statically in the reduced space. If Proposition 1 holds for all weights w ∈ W and for all iterations i = 1 . . . T , then the weights learned in the IPCA reduced space will be equivalent to those learned in the static PCA reduced space, modulo the approximation error incurred by IPCA.
Here, "static PCA" refers to first learning and applying PCA to all of the training data, then learning the weights solely in the PCA reduced space.
Proof of Proposition 1. This equivalence can be easily shown using linearity, with coefficients α determined by the learning rate:
The top line in 1 represents learning in the current reduced space, while the bottom two lines represent previously learning in the original space, then applying the current version of IPCA.
In practice, it is unlikely that Proposition 1 will hold due to its strong assumption that matches will be the same across various iterations of IPCA. However, we do expect matches to be similar (though not exactly the same) across iterations of IPCA. Our experimental results in Table 1 demonstrate that this approximate equivalence holds in practice.
Our proposed algorithm is inspired by ART, and essentially performs incremental winner-take-all clustering. However, there are several differences between our algorithm and ART-based algorithms.
Our algorithm differs from ART as it (1) does not include distinct bottom-up and top-down matching phases, (2) uses linear rather than fuzzy intersection weight updates, and (3) avoids match tracking. Specifically, our algorithm uses the alternative to match tracking described in Anagnostopoulos & Georgiopoulos (2003) which satisfies Fuzzy ARTMAP's incremental learning principle.
Because of these differences, some of ART's properties do not apply to our proposed algorithm. For example, the use of fuzzy intersection weight updates ensures that categories only shrink, implying that weights do not repeat previously held values (Carpenter et al., 1992). (We do not use fuzzy intersection as it is nonlinear, thus incompatible with Proposition 1). Still, our algorithm retains arguably the most important property of ART: the use of competition to protect previously learned knowledge. For further details on the ART framework and its applications in machine learning, we direct readers to this review article (Grossberg, 2020) and survey (da Silva et al., 2019).
A.5 DETAILS AND DISCUSSION OF EMPIRICAL RESULTS
We evaluate our model on the commonly used Split-MNIST and Split-Fashion-MNIST datasets in Tables 1 and2. Each dataset has 10 classes, divided into 5 binary classification problems: classify 0 vs 1, 2 vs 3, 4 vs 5, 6 vs 7, and 8 vs 9. Results are reported as the average performance across each of the 5 tasks after learning all tasks sequentially (i.e. tasks 1 -5 are first learned in order, then task 1 is evaluated, then task 2 is evaluated, etc).
Our evaluation was conducted in the single-headed setting with task-identifiers unavailable to the model. In our setting, this is equivalent to class-incremental learning (CIL). We chose this setting because it satisfies rigorous definitions of continual learning and is significantly more challenging than the multi-headed setting (Farquhar & Gal, 2018) in which task identifiers are provided at inference. Note that the multi-headed setting can be trivially solved by training isolated models for each task. For completeness, we include our proposed model's performance in the multi-headed setting, equivalent to task-incremental learning (TIL), in Table 2. Many continual deep learning approaches achieve comparably strong performance in this easier setting (Hsu et al., 2018). 2, we compare our proposed IPCA model against variations with no form of PCA and with static PCA trained on the entire dataset. Assuming that PCA improves matching performance, we expect the "No PCA" and "Static PCA" models to serve as approximate lower and upper bounds for "IPCA" model performance. In the single-headed setting, we find that our proposed model with IPCA significantly the model learned without PCA and does not significantly differ from the model learned with static PCA (using paired t-tests with significance level α = 0.05). In the easier multi-headed setting, we find that all models offer strong performance.
To understand our proposed model's performance in the context of recent work on continual learning, we include three deep learning baselines in the bottom half of Table 1. We include one method from each of the three main categories of continual learning approaches. Elastic weight consolidation (EWC) (Kirkpatrick et al., 2017) is a regularization-based approach, incremental classifier and representation learning (iCaRL) (Rebuffi et al., 2017) is a rehearsal-based approach, and dynamically expandable networks (DEN) (Yoon et al., 2018) is an architecture-based approach. These results are adopted from Sokar et al. (2021), which includes results from Hsu et al. (2018) and van de Ven & Tolias (2019). We include these baselines to contextualize our model's performance. While we do not expect our model to outperform all deep learning methods in terms of predictive accuracy, our results show that we achieve comparable performance with a much simpler approach.
The following describes how we evaluated our proposed algorithm in Tables 1 and2. We use 2000 train samples and 500 test samples of each class. Our results are computed over 25 trials. In each trial, the training data is randomly shuffled, resulting in different presentation orderings across trials -this is the only source of randomness in our algorithm. We use PCA/IPCA to reduce to dimensions k = 200 for the MNIST dataset and k = 250 for the Fashion-MNIST dataset, which corresponds to preserving slightly more than 95% of the variance in the training data. Both datasets have original dimension d = 784. We use vigilance parameter ρ = 0.5, cosine similarity function S(•, •), and adaptive learning rate 1/n s where n s denotes the total number of samples which have matched with the winning weight (i.e. the weights are simply an average of their corresponding samples). These values were determined through basic hyperparameter tuning on a validation set with 500 samples per class. We use the scikit-learn (Pedregosa et al., 2011) implementation of IPCA based on Ross et al. (2008).
There are several potential extensions of our proposed algorithm. First, note that the main idea behind Algorithm 1 in Proposition 1 could conceivably be applied to other types of incremental learning algorithms beyond IPCA and ART. For example, an incremental version of linear discriminant analysis (LDA) (Pang et al., 2005) could be used as an alternative to IPCA.
Second, it would be interesting to consider hierarchical extensions of IPCA. This is a way to perform local dimensionality reduction (Chakrabarti & Mehrotra, 2000) to increase the amount of retained variance at lower dimensions. Specifically, a global version of IPCA could be applied when clustering data with ART in an unsupervised manner, then local versions of IPCA could be applied to the data within each cluster. This process can be repeated to achieve hierarchical representation learning or hierarchical clustering. Proposition 1 allows this to be done in the continual learning setting as data arrives sequentially through time.
Finally, it would be interesting to further explore methods like ART for continual learning. Recent work on continual learning is focused on retrofitting deep learning methods in order to avoid catastrophic forgetting. ART is able to avoid catastrophic forgetting due to the inherent properties of its architectures and algorithm. A deeper understanding of these properties could lead to innovative variants and extensions of ART for continual learning.
The phrase "sample x matches to weight w" means that w is the weight with the maximum similarity score with respect to x in line 7 of Algorithm 1. Weight w is also referred to as the "winner" of ART's competition.