summaries: The paper introduces a non-parametric approach, STAM, for unsupervised progressive learning (UPL), a variant of continual unsupervised learning with a single-stream requirement. STAM is developed for visual tasks. It comprises several components: (1) online clustering of hierarchical visual features (2) novelty detection (3) dual-memory for prototypical features. Experiments show STAM performs better than GEM, MAS in specific scenarios.  The authors propose an approach (architecture + algorithms) to unsupervised progressive learning in a non-stationary environment (the number of classes grows gradually) by keeping centroids at several hierarchies, using a combination of techniques from online clustering, via computing and updating centroids, with novelty detection, and dropping (forgetting those deemed outliers).  A variety of experiments are performed on several image datasets (MNIST, EMNIST, SVHN, CIFAR-10) with comparisons to other adapted methods. They evaluate performance in a supervised setting where they describe how they learn centroid to label(s) mappings. This paper presents an "Unsupervised progressive learning" (UPL) problem, where a model is exposed to data in an non-iid manner, and each training example is presented once. Simple to continual learning, but a little more explicit in the connections to the way biological agents learn. They present a model that uses clustering and long-term memory (buffered) and compare on a few UPL tasks with additional supervision signal (classification) or unsupervised (clustering).
abstractText: We first pose the Unsupervised Progressive Learning (UPL) problem: learning salient representations from a non-stationary stream of unlabeled data in which the number of object classes increases with time. If some limited labeled data is also available, those representations can be associated with specific classes, thus enabling classification tasks. To solve the UPL problem, we propose an architecture that involves an online clustering module, called Self-Taught Associative Memory (STAM). Layered hierarchies of STAM modules learn based on a combination of online clustering, novelty detection, forgetting outliers, and storing only prototypical representations rather than specific examples. The goal of this paper is to introduce the UPL problem, describe the STAM architecture, and evaluate the latter in the UPL context.
references.authors: F. Gregory Ashby W. Todd Maddox
references.title: Human category learning
references.venue: Annu. Rev. Psychol.,
references.authors: Yoshua Bengio Aaron Courville Pascal Vincent
references.title: Representation learning: A review and new perspectives
references.venue: IEEE Trans. Pattern Anal. Mach. Intell.,
references.authors: Kevin S. Beyer Jonathan Goldstein Raghu Ramakrishnan Uri Shaft
references.title: When is ”nearest neighbor
references.venue: Proceedings of the 7th International Conference on Database Theory, ICDT
references.authors: Mathilde Caron Piotr Bojanowski Armand Joulin Matthijs Douze
references.title: Deep clustering for unsupervised learning of visual features
references.venue: In The European Conference on Computer Vision (ECCV),
references.authors: Adam Coates Andrew Y Ng
references.title: Learning feature representations with k-means, pages 561–580
references.authors: Adam Coates Andrew Ng Honglak Lee
references.title: An analysis of single-layer networks in unsupervised feature learning
references.venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,
references.authors: Gregory Cohen Saeed Afshar Jonathan Tapson André van Schaik
references.title: Emnist: an extension of mnist to handwritten letters
references.venue: ArXiv,
references.authors: Yuwei Cui Subutai Ahmad Jeff Hawkins
references.title: Continuous online sequence learning with an unsupervised neural network model
references.venue: Neural Comput.,
references.authors: S.M. Ali Eslami Nicolas Heess Theophane Weber Yuval Tassa David Szepesvari Koray Kavukcuoglu Geoffrey E. Hinton
references.title: Attend, infer, repeat: Fast scene understanding with generative models
references.venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,
references.authors: Li Fei-Fei R. Fergus P. Perona
references.title: One-shot learning of object categories
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: In Proceedings of the 34th International Conference on Machine Learning Volume 70,
references.authors: R. Geirhos P. Rubisch C. Michaelis M. Bethge F.A. Wichmann W. Brendel
references.title: Imagenettrained cnns are biased towards texture; increasing shape bias improves accuracy and robustness
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Alexander Gepperth Cem Karaoguz
references.title: Incremental learning with self-organizing maps
references.venue: Visualization (WSOM),
references.authors: Robert L Goldstone
references.title: Perceptual learning
references.venue: Annual review of psychology,
references.authors: Alexander Hinneburg Charu C. Aggarwal Daniel A. Keim
references.title: What is the nearest neighbor in high dimensional spaces
references.venue: In Proceedings of the 26th International Conference on Very Large Data Bases,
references.authors: Devon Hjelm Alex Fedorov Samuel Lavoie-Marchildon Karan Grewal Phil Bachman Adam Trischler Yoshua Bengio
references.title: Learning deep representations by mutual information estimation and maximization
references.venue: In ICLR 2019
references.authors: Yen-Chang Hsu Yen-Cheng Liu Anita Ramasamy Zsolt Kira
references.title: Re-evaluating continual learning scenarios: A categorization and case for strong baselines
references.venue: In NeurIPS Continual learning Workshop,
references.authors: Gabriel Huang Hugo Larochelle Simon Lacoste-Julien
references.title: Centroid networks for few-shot clustering and unsupervised few-shot classification
references.authors: X. Ji J. Henriques A. Vedaldi
references.title: Invariant infromation clustering for unsupervised image classification and segmentation
references.venue: In Proceedings of the International Conference on Computer Vision (ICCV),
references.authors: Zhuxi Jiang Yin Zheng Huachun Tan Bangsheng Tang Hanning Zhou
references.title: Variational deep embedding: An unsupervised and generative approach to clustering
references.venue: In Proceedings of the 26th International Joint Conference on Artificial Intelligence,
references.authors: Ronald Kemker Marc McClure Angelina Abitino Tyler Hayes Christopher Kanan
references.title: Measuring catastrophic forgetting in neural networks
references.venue: AAAI Conference on Artificial Intelligence,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization, 2014. cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations
references.venue: San Diego,
references.authors: Diederik P. Kingma Danilo J. Rezende Shakir Mohamed Max Welling
references.title: Semi-supervised learning with deep generative models
references.venue: In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2,
references.authors: Adam Kosiorek Hyunjik Kim Yee Whye Teh Ingmar Posner
references.title: Sequential attend, infer, repeat: Generative modelling of moving objects
references.venue: Advances in Neural Information Processing Systems
references.authors: Dharshan Kumaran Demis Hassabis James L McClelland
references.title: What learning systems do intelligent agents need? complementary learning systems theory updated
references.venue: Trends in cognitive sciences,
references.authors: Y. Lecun L. Bottou Y. Bengio P. Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: David Lopez-Paz Marc’Aurelio Ranzato
references.title: Gradient episodic memory for continual learning
references.venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,
references.authors: Takeru Miyato Shin-ichi Maeda Shin Ishii Masanori Koyama
references.title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning
references.venue: IEEE transactions on pattern analysis and machine intelligence,
references.authors: Yuval Netzer Tao Wang Adam Coates Alessandro Bissacco Bo Wu Andrew Y. Ng
references.title: Reading digits in natural images with unsupervised feature learning
references.venue: In NIPS Workshop on Deep Learning and Unsupervised Feature Learning
references.authors: Avital Oliver Augustus Odena Colin Raffel Ekin D. Cubuk Ian J. Goodfellow
references.title: Realistic evaluation of deep semi-supervised learning algorithms
references.authors: German I. Parisi Ronald Kemker Jose L. Part Christopher Kanan Stefan Wermter
references.title: Continual lifelong learning with neural networks: A review
references.venue: Neural Networks,
references.authors: Cengiz Pehlevan Alexander Genkin Dmitri B Chklovskii
references.title: A clustering neural network model of insect olfaction
references.venue: 51st Asilomar Conference on Signals, Systems, and Computers,
references.authors: Sylvestre-Alvise Rebuffi Alexander Kolesnikov Georg Sperl Christoph H. Lampert
references.title: icarl: Incremental classifier and representation learning
references.venue: IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Mengye Ren Eleni Triantafillou Sachin Ravi Jake Snell Kevin Swersky Joshua B. Tenenbaum Hugo Larochelle Richard S. Zemel
references.title: Meta-learning for semi-supervised few-shot classification
references.venue: In Proceedings of 6th International Conference on Learning Representations ICLR,
references.authors: Andrei A. Rusu Neil C. Rabinowitz Guillaume Desjardins Hubert Soyer James Kirkpatrick Koray Kavukcuoglu Razvan Pascanu Raia Hadsell
references.title: Progressive neural networks, 2016
references.authors: Hanul Shin Jung Kwon Lee Jaehong Kim Jiwon Kim
references.title: Continual learning with deep generative replay
references.venue: Advances in Neural Information Processing Systems
references.authors: Jake Snell Kevin Swersky Richard S. Zemel
references.title: Prototypical networks for few-shot learning
references.authors: Jost Tobias Springenberg
references.title: Unsupervised and semi-supervised learning with categorical generative adversarial networks
references.authors: Gido M. van de Ven Andreas S. Tolias
references.title: Three scenarios for continual learning
references.authors: Rajasekar Venkatesan Meng Joo Er
references.title: A novel progressive learning technique for multi-class classification
references.venue: Neurocomput.,
references.authors: Takeo Watanabe José E Náñez Yuka Sasaki
references.title: Perceptual learning without perception
references.venue: Nature, 413(6858):844,
references.authors: Jason Yosinski Jeff Clune Yoshua Bengio Hod Lipson
references.title: How transferable are features in deep neural networks
references.venue: Advances in Neural Information Processing Systems
references.authors: Chen Zeno Itay Golan Elad Hoffer Daniel Soudry
references.title: Task agnostic continual learning using online variational Bayes, 2018
sections.heading: 1 INTRODUCTION
sections.text: We start by posing a challenging problem, referred to as Unsupervised Progressive Learning (UPL) (see Figure 1). In the UPL problem, the agent observes a sequence (or stream) of unlabeled data vectors {xt}t∈N with xt ∈ Rn. Each vector xt is associated with a class k(xt) and the vectors of class k follow a distribution Fk. The class information, however, is hidden from the agent. Occasionally, the agent may be given a small number of labeled examples of one or more classes. These examples are meant to associate “names” (i.e., class labels) with the learned representations enabling classification tasks in which the set of output classes stays constant (“persistent tasks”) or increases (“expanding tasks”).
  We denote asLt the set of class labels the agent has seen up to time t. This set is gradually increasing, meaning that the agent progressively learns about more classes. In the UPL context, the goal is to learn in an online manner salient representations of the unlabeled input stream so that the agent can, at any point in time t, classify a given set of test data based on the set of classes Lt it knows about so far. We require an online learner for pragmatic reasons: it would not be possible or desirable in practice to store and/or process all previously seen data and learn a new model offline every time there is a change in Lt. The online nature of the problem constraints the solution space: methods that require multiple passes over the training data and/or randomly sampled minibatches are not applicable in the UPL context.
  We assume that the distribution Fk associated with class k may also change with time – but this is a slow and gradual process so that an online learner can track changes in Fk. Abrupt changes would require that the agent forgets what was previously learned about class k – we do not consider that possibility in this paper.
  We do not add any further constraints on the structure of the data sequence. For instance, it is possible that the learner first observes a labeled example of class k at time t (and so k ∈ Lt) even though it has not seen any unlabeled examples of that class prior to t – this would require a transfer-learning capability so that the learner can classify k based on representations it has previously learned from other classes. Another interesting scenario is when the unlabeled data arrive in separated class phases, which are unknown to the agent, so that each phase includes data from only few new classes – this is a challenging task from the perspective of catastrophic forgetting because the learner should not forget previously learned classes for which it does not see any new examples. We consider such UPL scenarios in Section 3.
  It is plausible that UPL represents how animals learn, at least in the case of perceptual learning (Goldstone, 1998): they observe their environment, which is predominantly “unlabeled”, and so they learn to gradually distinguish between a growing number of different object categories even when they do not have a way yet to name them. Later, some of those classes may be associated with words (in the case of humans) (Ashby and Maddox, 2005), or more generally, with a specific taste, odor, reward, fear, etc. (Watanabe et al., 2001).
sections.heading: 1.1 UPL VERSUS SIMILAR LEARNING PARADIGMS
sections.text: 1. Unsupervised and self-supervised learning: There have been great strides recently in learning data representations (Bengio et al., 2013) via clustering (Caron et al., 2018), generative models (Jiang et al., 2017; Eslami et al., 2016; Kosiorek et al., 2018; 2019), and information theory (Hjelm et al., 2019; Ji et al., 2019). While these methods can learn representations without data labels, they still require prior information about the number of classes present in a given dataset (to set the number of cluster centroids or class outputs) and, in the continual learning case, they suffer from catastrophic forgetting unless some form of replay is used.
  2. Few-shot learning (FSL) and Meta-learning: Such methods attempt to recognize object classes not seen in a training set with only a single (or handful) of labeled examples (Fei-Fei et al., 2006; Snell et al., 2017; Finn et al., 2017; Ren et al., 2018). FSL requires labeled data to learn good representations - whereas UPL only requires labeled data to associate already learned representations with new classes.
  3. Semi-supervised learning (SSL): SSL addresses scarcity of available labeled data for model training by leveraging large amounts of unlabeled training data to boost performance (Springenberg, 2015; Oliver et al., 2018; Miyato et al., 2018; Kingma et al., 2014). SSL requires both labeled and unlabeled data during the training process and in most cases it needs to store and process the labeled data repeatedly during the training process.
  4: Continual learning (CL): Most CL methods rely on labeled data and knowledge of which tasks are learned or performed at any point in time(Hsu et al., 2018; Parisi et al., 2019; Kemker et al., 2018; van de Ven and Tolias, 2019; Lopez-Paz and Ranzato, 2017). Further, the most effective CL mechanisms address catastrophic forgetting using stored examples or generative replay (Gepperth and Karaoguz, 2017; Shin et al., 2017).
  5. Transfer learning (TL): Such methods require pre-training on a large labeled dataset and so they are not applicable to UPL (Yosinski et al., 2014).
  6. Progressive learning/networks: In (labeled) progressive learning, a supervised classification model must be able to learn in an online manner without prior knowledge of the number of classes (Venkatesan and Er, 2016; Rusu et al., 2016). However, the existing approaches in this area require supervision when a new class appears, and they suffer from catastrophic forgetting if they do not see data from a previous class for long periods of time.
sections.heading: 2 STAM ARCHITECTURE AND LEARNING ALGORITHM
sections.text: The learning approach that we pursue in this work is based on online clustering, novelty detection, two separate short-term and long-term memories, and storing only prototypical representations rather than specific examples. In the following, we describe the STAM architecture as a sequence of its seven major components.
  The notation is summarized in Appendix A. The image preprocessing pipeline is minimal and is described in Appendix B. The reasons we decided to not pursue a deep learning approach are discussed in Appendix C.
  1. Hierarchy of increasing receptive fields: An input vector xt ∈ Rn (an image in all subsequent examples) is analyzed through a hierarchy of Λ layers. Instead of neurons or hidden-layer units, each layer consists of STAM units – in its simplest form a STAM unit functions as an online clustering module. Each STAM processes one ρl × ρl patch (subvector) of the input at that layer. The patches are overlapping, with a small stride (set to one pixel in our experiments), to accomplish translation invariance (similar to CNNs). The patch dimension ρl increases in higher layers – the idea is that the first layer learns the smallest and most elementary patterns while the top layer learns the largest and most complex patterns.
  2. Online clustering: Every patch of each layer is clustered, in an online manner, to a set of centroids. These time-varying centroids form the prototypical patterns that the STAM architecture gradually learns at that layer. All STAM units of layer l share the same set of centroids Cl(t) – again for translation invariance.1 Given the m’th input patch xl,m at layer l, the nearest centroid of Cl selected for xl,m is
  cl.j = arg min c∈Cl d(xl,m, c) (1)
  where d(xl,m, c) is the Euclidean distance between the patch xl,m and centroid c.2 The selected centroid is updated based on a learning rate parameter α, as follows:
  cl,j = αxl,m + (1− α)cl,j, 0 < α < 1 (2) A higher α value makes the learning process faster but less predictable. We do not use a decreasing value of α because the goal is to keep learning in a non-stationary environment rather than convergence to a stable centroid. If the centroid cl,j is selected by more than one patches of the same input, the centroid is updated based on the closest patch to that centroid.
  An online clustering algorithm that is similar to our approach (and asymptotically equivalent to k-means) can be implemented with a simple recurrent neural network of excitatory and inhibitory spiking neurons using strictly Hebbian learning, as shown recently (Pehlevan et al., 2017).
  3. Novelty detection: When an input patch xl,m at layer l is significantly different than all centroids at that layer (i.e., its distance to the nearest centroid is a statistical outlier), a new centroid is created in Cl based on xl,m. We refer to this event as Novelty Detection (ND). This function is necessary so that the architecture can learn centroids associated with new classes after they appear in the unlabeled data stream.
  To do so, we estimate in an online manner the distribution of the Euclidean distance between input patches and their nearest centroid (separately for each layer). We sample a randomly chosen patch from each input vector, only considering the last 1000 inputs. The novelty detection threshold at layer l is denoted by D̂l and it is defined as the 95-th percentile (β = 0.95) of the distance distribution.
  1We drop the time index t from this point on but it is still implied that the centroids are dynamically learned over time.
  2We have also experimented with the L1 distance metric with only minimal differences.
  4. Dual-memory organization: New centroids are stored temporarily in a Short-Term Memory (STM) of limited capacity ∆ (separate for each layer). Every time a centroid is selected as the nearest neighbor of an input patch, it is updated based on (2). If an STM centroid cl,j is selected sl,j > θ times, it is copied to the Long-Term Memory (LTM) for that layer. We refer to this event as memory consolidation. The LTM has (practically) unlimited capacity and the learning rate is much smaller (in our experiments, set to zero).
  This memory organization is inspired by the Complementary Learning Systems framework (Kumaran et al., 2016), where the STM role is played by the hippocampus and the LTM role by the cortex. This dual-memory scheme is necessary to distinguish between infrequently seen patterns that can be forgotten, and new patterns that are frequently seen after they first appear.
  We initialize the pool of STM centroids at each layer using randomly sampled patches from the unlabeled stream (a single patch from each image to maximize diversity).
  When the STM pool of centroids at a layer is full, the introduction of a new centroid (created through novelty detection) causes the removal of an earlier centroid. We use the Least-Recently Used (LRU) policy to remove atypical centroids that have not been recently selected by any input. Figure 2 illustrates this dual-memory organization.
  5. Associating centroids with classes: Suppose that we have seen some labeled examples XL(t) from a set of classes L(t) up to time t. In the UPL context, we only use such labeled examples to associate existing LTM centroids at time t (learned strictly from unlabeled data) with the set of classes in L(t).
  Given a labeled example of class k, suppose that there is a patch x in that example for which the nearest centroid is c. That patch contributes the following association between centroid c and class k:
  fx,c(k) = e −d(x,c)/D̄l (3)
  where D̄l is a normalization constant (calculated as the average distance between input patches and centroids).
  The class-association vector gc between centroid c and any class k is computed aggregating all such associations, across all labeled examples in XL:
  gc(k) =
  ∑ x∈XL(k) fx,c(k)∑
  k′∈L(t) ∑ x∈XL(k′) fx,c(k ′) , k = 1 . . . L(t) (4)
  Note that ∑
  k gc(k)=1.
  6. Class informative centroids: If a centroid is associated with only one class k (gc(k) = 1), only labeled examples of that class select that centroid. At the other extreme, if a centroid is equally likely to be selected by examples of any labeled class, (gc(k) ≈ 1/|L(t)|), the selection of that centroid does not provide any significant information for the class of the corresponding input.
  We identify the centroids that are Class INformative (CIN) as those that are associated with at least one class more than expected by chance. Specifically, a centroid c is CIN if
  max k∈L(t)
  gc(k) > 1
  |L(t)| + γ (5)
  where 1|L(t)| is the chance term and γ is an additional significance term.
  7. Classification using a hierarchy of centroids: At test time, we are given an input x of class k(x) and infer its class as k̂(x). The classification task is a “biased voting” process in which every patch of x, at any layer, votes for a single class as long as that patch selects a CIN centroid.
  Specifically, if a patch xl,m of layer l selects a CIN centroid c, then that patch votes vl,m(k) = maxk∈L(t) gc(k) for the class k that has the highest association with c, and zero for all other classes. If c is not a CIN centroid, the vote of that patch is vl,m(k) = 0 for all classes.
  The vote of layer l for class k is the average vote across all patches in layer l (as illustrated in Figure 3):
  vl(k) =
  ∑ m∈Ml vl,m(k)
  |Ml| (6)
  where Ml is the set of patches in layer l. The final inference for input x is the class with the highest cumulative vote across all layers:
  k̂(x) = arg max k′ Λ∑ l=1 vl(k) (7)
sections.heading: 3 EVALUATION
sections.text: To evaluate the STAM architecture in the UPL context, we consider two different scenarios: Incremental UPL and Uniform UPL. In the Incremental UPL case, small groups of classes appear in successive phases. In the following results, new classes are introduced two at a time in each phase, and they are only seen in that phase. STAMs must be able to both recognize new classes when they are first seen in the stream, and to also remember all previously learned classes without catastrophic forgetting. In the Uniform UPL case, all classes appear with equal probability in the stream. The Uniform UPL scenario is more relevant when the distribution Fk of each class k may gradually change over time. The results for the Uniform scenario are presented in Appendix D.
  The classification task that we focus on in the Incremental UPL case is expanding, meaning that in each phase we need to classify all classes seen so far. Given a few labeled examples for the classes that have been present in the stream up to time t, the algorithm is asked to perform object classification on a 1000-image test dataset. The datasets we evaluate on are MNIST (Lecun et al., 1998), EMNIST (balanced split with 47 classes) (Cohen et al., 2017), and SVHN (Netzer et al., 2011).
  For each classification task, we average results over five trials (different unlabeled data streams). In each trial, we have a randomly sampled hold-out set of 1500 images. Then, we sample from the remaining data to form the unlabeled stream. We perform each classification task five times, using randomly sampled test inputs from the hold-out set. So, each result is the average of 25 classification evaluations.
  We use a 3-layer STAM hierarchy – all hyperparameters values are reported in Appendix A. The robustness of the results as we vary these hyperparameter values is shown in Appendix E.
sections.heading: 3.1 INCREMENTAL UPL
sections.text: As we introduce new classes to the incremental UPL stream (see Figure 4), the architecture recognizes previously learned classes without any major degradation in classification accuracy (left column). The average accuracy per phase is decreasing, which is due to the increasingly difficult expanding classification task. For EMNIST, we only show the average accuracy because there are 47 total classes. In all datasets, we observe that layer-3 (corresponding to the largest receptive field) contains the highest fraction of CIN centroids (center column). The ability to recognize new classes
  is perhaps best visualized in the LTM centroid count (right column). During each phase the LTM count stabilizes until a sharp spike occurs at the start of the next phase when new classes are introduced. This reinforces the claim that the LTM pool of centroids (i) is stable when there are no new classes, and (ii) is able to recognize new classes via novelty detection when they appear. In the EMNIST experiment, as the number of classes increases towards 47, we gradually see fewer “spikes” in the LTM centroids for the lower receptive fields, which is expected given the repetition of patterns at that small patch size. However, the highly CIN layer-3 continues to recognize new classes and create centroids, even when the last few classes are introduced.
sections.heading: 3.2 ABLATIONS
sections.text: Several ablations are presented in Figure 5. On the left, we remove the LTM capabilities and only use STM centroids for classification. During the first two phases, there is little (if any) difference in classification accuracy. However, we see a clear dropoff during phases 3-5. This suggests that, without the LTM mechanisms, patterns from classes that are no longer seen in the stream are forgotten over time, and STAMs can only successfully classify classes that have been recently seen. We also investigate the importance of having static LTM centroids rather than dynamic centroids (center). Specifically, we replace the static LTM with a dynamic LTM in which the centroids are adjusted with the same learning rate parameter α, as in STM. The accuracy suffers drastically because the introduction of new classes “takes over” LTM centroids of previously learned classes, after the latter are removed from the stream. Similar to the removal of LTM, we do not see the effects of “forgetting” until phases 3-5. Note that the degradation due to a dynamic LTM is less severe than that from removing LTM completely. Finally, we look at the effects of removing layers from the STAM hierarchy (right). We see a small drop in accuracy after removing layer 3, and a large drop in accuracy after also removing layer 2. The importance of having a deeper hierarchy would be more pronounced in datasets with higher-resolution images or videos, potentially showing multiple objects in the same frame. In such cases, CIN centroids can appear at any layer, starting from the lowest to the highest.
sections.heading: 3.3 EFFECT OF UNLABELED AND LABELED DATA
sections.text: We next examine the effects of unlabeled and labeled data on the STAM architecture (Figure 6). As we vary the length of the unlabeled data stream (left), we see that STAMs can actually perform well even with much less unlabeled data. This suggests that the STAM architecture may be applicable even where the datastream is much shorter than in the experiments of this paper. A longer stream would be needed however if there are many classes and some of them are infrequent. The accuracy “saturation” observed by increasing the unlabeled data from 20000 to 60000 can be explained based on the memory mechanism, which does not update centroids after they move to LTM. As showed in the ablation studies, this is necessary to avoid forgetting classes that no longer appear in the stream. The effect of varying the number of labeled examples per class (right) is much more pronounced.
  We see that the STAM architecture can perform well above chance even in the extreme case of only a single (or small handful of) labeled examples per class.
sections.heading: 4 RELATED WORK AND DISCUSSION
sections.text: Even though clustering has been used successfully in the past as a representation learning scheme (Coates et al., 2011; Coates and Ng, 2012), its effectiveness gradually drops as the input dimensionality increases (Hinneburg et al., 2000; Beyer et al., 1999). In the STAM architecture, we avoid this issue by clustering smaller subvectors (patches) of the input data. If those subvectors are still of high dimensionality, another approach is to reduce the intrinsic dimensionality of the input data at each layer by reconstructing that input using representations (selected centroids) from the previous layer – we have experimented with this approach but not included it here because it is not required in the datasets and tasks we work with in this paper.
  This paper does not compare the performance of STAMs with other methods because, to the extent of our knowledge, none of the existing approaches in the literature are directly applicable to the UPL problem. In a follow-up study, we plan to adapt the most relevant approaches so that they can be applied in the UPL context. One of these approaches is Incremental Classifier and Representation Learning (iCaRL) (Rebuffi et al., 2017), which learns representations and classifiers from a progressive stream of labeled data and stores training examples for each class. In (Huang et al., 2019), the goal is to do unsupervised few-shot classification and the authors evaluate various methods in a similar manner to UPL but without learning from a non-stationary stream. FearNet (Kemker et al., 2018) replaces the storage of training examples with a generative model but still processes a labeled stream for both the classifier and generator. Bayesian Gradient Descent (BGD) (Zeno et al., 2018) is a method for preventing catastrophic forgetting when the learner is unaware of the task schedule and so it cannot take any special action when the input data distribution changes. A comparison of methods for continuous online sequence learning, including the Hierarchical Temporal Memory model, was conducted by Cui et al. (Cui et al., 2016) – those methods do not address the UPL problem however.
  We firmly believe that in order to mimic human intelligence, learning methods should be able to learn in a streaming manner and in the absence of supervision. Animals do not “save off” labeled examples to train in parallel with unlabeled data, they do not know how many classes exist in their environment, and they do not have to replay/dream periodically all their past experiences to avoid forgetting them. The proposed STAM architecture addresses the desiderata that is often associated with Lifelong Learning:
  1. Online learning: STAMs constantly update their centroids with every example. There is no separate training stage, and there is no specific task for which the network optimizes the features it learns. Any tasks that require classification will of course require one or few labeled examples so that the corresponding clusters that were formed previously are now associated with the name of a class. However, STAMs do not need these labeled examples to learn efficient data representations.
  2. Transfer learning: The hierarchical nature of the proposed architecture means that features learned (in an unsupervised manner) at lower-level STAMs can be reused in different tasks that higher-level STAMs perform.
  3. Resistance to catastrophic forgetting: The introduction of a new class or prototype will lead to the creation of new clusters at some STAMs in the hierarchy (e.g., layer-1 STAMs will learn new elementary visual features if we start feeding them natural images instead of MNIST examples – while a STAM at a higher-level would create a new cluster when it first starts seeing examples of scooters but without affecting the cluster associated with bicycles).
  4. Expanding learning capacity: The learning capacity of a STAM architecture depends on two factors: the number of STAMs and the maximum number of centroids that each STAM can store in STM and LTM. The limited capacity constraint in the STM pool requires to forget recently created centroids that have not been recently updated with new examples. The unlimited capacity of the LTM pool of centroids, on the other hand, allows the system to gradually learn an unlimited number of classes, even if it does not see examples of all classes learned earlier.
  5. No direct access to previous experience: A STAM only needs to store the centroids of the clusters it has learned so far. Those centroids correspond to prototypes, allowing the STAM to generalize. All previously seen exemplars are discarded.
sections.heading: A STAM NOTATION AND HYPERPARAMETERS
sections.text: Table 3: MNIST/EMNIST Architecture
  Layer ρl ∆ (incremental) ∆ (uniform)
  1 8 400 2000 2 13 400 2000 3 20 400 2000
  Table 4: SVHN Architecture
  Layer ρl ∆ (incremental) ∆ (uniform)
  1 10 2000 10000 2 14 2000 10000 3 18 2000 10000
  B IMAGE PREPROCESSING
  Given that each STAM operates on individual image patches, we perform patch normalization rather than image normalization. We chose a normalization operation that helps to identify similar patterns despite variations in the brightness and contrast: every patch is transformed to zero-mean, unit variance before clustering.At least for the datasets we consider in this paper, grayscale images result in higher classification accuracy than color.
  We have also experimented with ZCA whitening and Sobel filtering. ZCA whitening did not work well because it requires estimating a transformation from an entire image dataset (and so it is not compatible with the online nature of the UPL problem). Sobel filtering did not work well because STAM clustering works better with filled shapes rather than the fine edges produced by Sobel filters.
sections.heading: C WHY NOT USE DEEP LEARNING?
sections.text: Given that deep neural networks have become the new orthodoxy in machine learning, we need to address the question: why not use a deep learning approach to solve the UPL problem? Why to rely on online clustering instead?
  1) With few exceptions, deep learning approaches have a fixed architecture and capacity (measured in terms of their hidden unit parameters) and so they are not able to automatically grow as the network is presented with new classes or tasks. Methods such as Progressive Networks (Snell et al., 2017) allow the network to grow but only when instructed that a new task/class is given – and by a pre-determined growth factor. The STAM architecture, on the other hand, grows by creating new centroids only when needed and by a growth factor that is determined in a self-supervised manner by the “degree of novelty” in the data.
  2) Deep learning approaches require multiple passes over the training data, and thus they would need to either store and replay previously seen data or to learn a generative model that synthesizes realistic data when needed. Especially in semi-supervised methods such as VAT (Miyato et al., 2018), it is critical that the limited given labeled data are processed repeatedly. In the STAM architecture, data is never stored both because that may be impractical and because the data distribution in the UPL context may gradually shift – storing old data can be misleading.
  3) A neural network (deep or shallow) learns a nonlinear embedding of the input data in a lowdimensional continuous space in which it is more efficient, presumably, to perform classification, clustering, generative modeling, or other tasks. This compression of the input dimensionality however comes at a high cost: the latent features learned by a neural net are not interpretable, they may be derived from properties that are unrelated to the causal/defining properties of the corresponding classes (Geirhos et al., 2019), and they can make the network susceptible to adversarial attacks. STAMs, on the other hand, use clustering to learn common patterns at a hierarchy of increasing receptive fields. These patterns can be easily interpreted by humans because they represent prototypes (common patterns) at each layer.
  4) The embedding that a neural network learns is typically assumed to be time-invariant. This is problematic in the UPL context because the number of classes or tasks increases with time, without external supervision whenever that happens. It is not clear how to gradually adjust an embedding in an online manner without any external supervision when the classes/tasks change.
  5) Learning in deep neural networks requires iterative nonconvex optimization processes, such as SGD, that can get stuck in local minima. Online clustering is a much simpler computation in which we only need to compute a certain distance metric between the input vector and all existing centroids – and then to update the nearest centroid based on the corresponding input.
sections.heading: D UNIFORM UPL
sections.text: In order to examine if the STAM architecture can learn all classes simultaneously, but without knowing how many classes exist, we also evaluate the STAM architecture in a uniform UPL scenario (Figure 5). Note that LTM centroids converge to a constant value, at least at the top layer, Each class is recognized at a different level of accuracy, depending on the similarity between that class and others.
  E ADDITIONAL HYPERPARAMETER SWEEPS AND ABLATIONS
  We examine the effects of STAM hyperparameters in Figure 8. (a) As we decrease the rate of α, we see a degradation in performance. This is likely due to the static nature of the LTM centroids - with low α values, the LTM centroids will primarily represent the patch they were intialized as. (b) As we vary the rates of γ, there is little difference in our final classification rates. This suggests that the maximum gl,j(k) values are quite high, which may not be the case in other datasets besides SVHN. (c) We observe that STAM is robust to changes in Θ. (d,e) The STM size ∆ has a major effect on the number of learned LTM centroids and on classification accuracy. (e) The accuracy in
  phase-5 for different numbers of layer-3 LTM centroids (and correspnding ∆ values). The accuracy shows diminishing returns after we have about 1000 LTM centroids at layer-3. (g,h) As β increases the number of LTM centroids increases (due to a lower rate of novelty detection); if β ≥ 0.9 the classification accuracy is about the same.
sections.heading: F COMPARISON WITH AUTO-ENCODER APPROACH
sections.text: Even though the goal of this paper is not to present an extensive comparison between STAM and deep-learning methods, in this section we perform a limited such comparison with a simple autoencoder. Specifically, we train a convolutional autoencoder (CAE) with the images from the unlabeled data stream. The number of training epochs and the batch size are both set to 1, so that each unlabeled example is only used once. The encoder consists of three convolution layers with ReLU activations, embedding inputs into a 64-dimension latent space. The decoder consists of three transposed convolution layers with ReLU activations. The final layer uses linear activations and the network is trained to optimize Euclidean reconstruction error. The representations at the 64-dimension latent space are used to perform K nearest-neighbor (KNN) classification. The CAE architecture, given in Figure 10, is trained using Adam optimization (Kingma and Ba, 2014) with a learning rate of 1−4 and no decay.
  The STAM architecture outperforms the CAE approach by a large margin (Figure 9, Incremental UPL, SVHN dataset). In follow-up work we plan to develop more sophisticated deep learning approaches for solving the UPL problem and compare them with STAMs under different conditions.
sections.heading: G MEMORY FOOTPRINT ANALYSIS
sections.text: The memory requirement of the STAM model can be calculated as:
  M = Λ∑ l=1 ρ2l · (|Cl|+ ∆) (8)
  For the 3-layer SVHN architecture with |Cl| ≈ 3000 LTM centroids in every layer and ∆ = 2000, the memory footprint is 5, 064, 000 pixels, equivalent to roughly 5000 grayscale SVHN digits. This memory requirement can be significantly reduced however. Figure 8(f) shows that the accuracy remains almost the same when ∆ = 500 and |Cl| ≈ 1000. With these values the memory footprint reduces to about 950,000 pixels, equivalent to roughly 930 grayscale SVHN digits.
  By comparison, the CAE architecture has 4, 683, 425 trainable parameters, which should be stored at floating-point precision. With four bytes per weight, then STAM model would require 9500004683425×4 ≈ 5% of the CAE’s memory footprint. Future work can decrease the STAM memory requirement further by merging similar LTM centroids.