Incremental learning algorithms and applications

Abstract. Incremental learning refers to learning from streaming data, which arrive over time, with limited memory resources and, ideally, without sacrificing model accuracy. This setting fits different application scenarios where lifelong learning is relevant, e.g. due to changing environments, and it offers an elegant scheme for big data processing by means of its sequential treatment. In this contribution, we formalise the concept of incremental learning, we discuss particular challenges which arise in this setting, and we give an overview about popular approaches, its theoretical foundations, and applications which emerged in the last years.

1 What is incremental learning?

Machine learning methods offer particularly powerful technologies to infer structural information from given digital data; still, the majority of current applications restrict to the classical batch setting: data are given prior to training, hence meta-parameter optimisation and model selection can be based on the full data set, and training can rely on the assumption that the data and its underlying structure are static. Lifelong learning, in contrast, refers to the situation of continuous model adaptation based on a constantly arriving data stream [START_REF] Eaton | Lifelong Machine Learning[END_REF][START_REF] Silver | Machine lifelong learning: Challenges and benefits for artificial general intelligence[END_REF]. This setting is present whenever systems act autonomously such as in autonomous robotics or driving [START_REF] Thrun | Toward robotic cars[END_REF][START_REF] Amirat | Assistance and service robotics in a human environment[END_REF][START_REF] Menegatti | Special issue on intelligent autonomous systems[END_REF][START_REF] Hammer | Special issue on autonomous learning[END_REF]. Further, online learning becomes necessary in any interactive scenario where training examples are provided based on human feedback over time [START_REF] Rico-Juan | Adaptive training set reduction for nearest neighbor classification[END_REF]. Finally, many digital data sets, albeit static, can become so big that they are de facto dealt with as a data stream, i.e. one incremental pass over the full data set [START_REF] Morales | Samoa: Scalable advanced massive online analysis[END_REF]. Incremental learning investigates how to learn in such a streaming setting. It comes in various forms in the literature, and the use of the term is not always consistent. Therefore, first, we give a meaning to the terms online learning, incremental learning, and concept drift, giving particular attention to the supervised learning paradigm.

Online learning methods

In supervised learning, data D = (( x 1 , y 1 ), ( x 2 , y 2 ), ( x 3 , y 3 ), . . . , ( x m , y m )) are available with input signals x i and outputs y i . The task is to infer a model M ≈ p(y| x) from such data. Machine learning algorithms are often trained in a batch mode, i.e., they use all examples ( x i , y i ) at the same time, irrespective of their (temporal) order, to perform, e.g., a model optimisation step.

Challenge 1: Online model parameter adaptation. In many application examples, data D are not available priorly, but examples arrive over time, and the task is to infer a reliable model M t after every time step based on the example ( x t , y t ) and the previous model M t-1 only. This is realised by online learning approaches, which use training samples one by one, without knowing their number in advance, to optimise their internal cost function. There is a continuum of possibilities here, ranging from fully online approaches that adapt their internal model immediately upon processing of a single sample, over socalled mini-batch techniques that accumulate a small number of samples, to batch learning approaches, which store all samples internally.

Online learning is easily achieved by stochastic optimisation techniques such as online back-propagation, but there are also extensions of the support vector machine (SVM) [START_REF] Wen | Incremental learning of support vector machines by classifier combining[END_REF]. Prototype-based models such as vector quantisation, radial basis function networks (RBF), supervised learning vector quantisation, and self-organising maps (SOM) all naturally realise online learning schemes since they rely on a (approximate) stochastic gradient technique [START_REF] Runkler | Data Analytics Models and Algorithms for Intelligent Data Analysis[END_REF][START_REF] Moody | Fast learning in networks of locally tuned processing units[END_REF][START_REF] Biehl | Dynamics and generalization ability of LVQ algorithms[END_REF][START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF]. Second order numeric optimisation methods and advanced optimisation schemes can be extended as well, such as variational Bayes, convex optimization, second order perceptron learning based on higher order statistics in primal or dual space, and online realisations of the quasi-Newton Broyden-Fletcher-Goldfarb-Shanno technique [START_REF] Mokhtari | Global convergence of online limited memory BFGS[END_REF][START_REF] Moroshko | Second-order non-stationary online learning for regression[END_REF][START_REF] Gentile | On higher-order perceptron algorithms[END_REF][START_REF] Penalver | Entropy-based incremental variational bayes learning of gaussian mixtures[END_REF][START_REF] Hall | Online convex optimization in dynamic environments[END_REF]. Stochastic optimization schemes can be developed also for non-decomposable cost function, [START_REF] Kar | Online and stochastic gradient methods for non-decomposable loss functions[END_REF]. Further, lazy learners such as k-nearest neighbour (k-NN) methods lend itself to online scenarios by their design [START_REF] Runkler | Data Analytics Models and Algorithms for Intelligent Data Analysis[END_REF]. Interestingly, online learning has already very early been accompanied by their exact mathematical investigations [START_REF] Watkin | The Statistical Mechanics of Learning a Rule[END_REF].

Incremental learning methods

Incremental learning refers to online learning strategies which work with limited memory resources. This rules out approaches which essentially work in batch mode for the inference of M t by storing all examples up to time step t in memory; rather, incremental learning has to rely on a compact representation of the already observed signals, such as an efficient statistics of the data, an alternative compact memory model, or an implicit data representation in terms of the model parameters itself. At the same time, it has to provide accurate results for all relevant settings, despite its limited memory resources. Challenge 2: Concept drift. Incremental learning shares quite a number of challenges with online learning, with memory limitations adding quite a few extras. One prominent problem consists in the fact that, when the temporal structure of data samples is taken into account, one can observe changes in data statistics that occur over time, i.e. samples ( x i , y i ) are not i.i.d. Changes in the data distribution over time are commonly referred to as concept drift [START_REF] Kulkarni | Incremental learning from unbalanced data with concept class, concept drift and missing features: a review[END_REF][START_REF]The problem of concept drift: definitions and related work[END_REF][START_REF] Ditzler | Learning in nonstationary environments: A survey[END_REF][START_REF] Polikar | Guest editorial learning in nonstationary and evolving environments[END_REF]. Different types of concept drift can be distinguished: changes in the input distribution p( x) only, referred to as virtual concept drift or covariate shift, or changes in the underlying functionality itself p(y| x), referred to as real concept drift. Further, concept drift can be gradual or abrupt. In the latter case one often uses the term concept shift. The term local concept drift characterises changes of the data statistics only in a specific region of data space [START_REF]The problem of concept drift: definitions and related work[END_REF]. A prominent example is the addition of a new, visually dissimilar object class to a classification problem. Real concept drift is problematic since it leads to conflicts in the classification, for example when a new but visually similar class appears in the data: this will in any event have an impact on classification performance until the model can be re-adapted accordingly.

Challenge 3: The stability-plasticity dilemma. In particular for noisy environments or concept drift, a second challenge consists in the question when and how to adapt the current model. A quick update enables a rapid adaptation according to new information, but old information is forgotten equally quickly. On the other hand, adaption can be performed slowly, in which case old information is retained longer but the reactivity of the system is decreased. The dilemma behind this trade-off is usually denoted the stability-plasticity dilemma, which is a well-known constraint for artificial as well as biological learning systems [START_REF] Mermillod | The stability-plasticity dilemma: investigating the continuum from catastrophic forgetting to age-limited learning effects[END_REF]. Incremental learning techniques, which adapt learned models to concept drift only in those regions of the data space where concept drift actually occurs, offer a partial remedy to this problem. Many online learning methods alone, albeit dealing with limited resources, are not able to solve this dilemma since they exhibit a so-called catastrophic forgetting behaviour [START_REF] Mccloskey | Catastrophic interference in connectionist networks: the sequential learning problem[END_REF][START_REF] Ratcliff | Connectionist models of recognition memory: constraints imposed by learning and forgetting functions[END_REF][START_REF] French | Semi-distributed representations and catastrophic forgetting in connectionist networks[END_REF][START_REF] French | Connectionist models of recognition memory: constraints imposed by learning and forgetting functions[END_REF][START_REF] Nj | Catastrophic interference in connectionist networks: the sequential learning problem[END_REF] even when the new data statistics do not invalidate the old ones.

One approach to deal with the stability-plasticity dilemma consists in the enhancement of the learning rules by explicit meta-strategies, when and how to learn. This is at the core of popular incremental models such as ART networks [START_REF] Impedovo | A novel prototype generation technique for handwriting digit recognition[END_REF][START_REF] Grossberg | Adaptive resonance theory: How a brain learns to consciously attend, learn, and recognize a changing world[END_REF], or meta-strategies to deal with concept drift such as the just-in-time classifier JIT [START_REF] Alippi | Just in time classifiers: Managing the slow drift case[END_REF], or hybrid online/offline methods [START_REF] Nguyen | Combining online and offline learning for tracking a talking face in video[END_REF][START_REF] Fischer | Combining offline and online classifiers for life-long learning[END_REF]. One major ingredient of such strategies consist in a confidence estimation of the actual model prediction, such as statistical tests, efficient surrogates, or some notion of selfevaluation [START_REF] Bae | Robust online multi-object tracking based on tracklet confidence and online discriminative appearance learning[END_REF][START_REF] Fischer | Combining offline and online classifiers for life-long learning[END_REF][START_REF] Jauffret | How can a robot evaluate its own behavior? a neural model for self-assessment[END_REF]. Such techniques can be enhanced to complex incremental schemes for interactive learning or learning scaffolding [START_REF] Pratama | An incremental meta-cognitive-based scaffolding fuzzy neural network[END_REF][START_REF] Kompella | Explore to see, learn to perceive, get the actions for free: Skillability[END_REF].

Challenge 4: Adaptive model complexity and meta-parameters. For incremental learning, model complexity must be variable, since it is impossible to estimate the model complexity in advance if the data are unknown. Depending on the occurrence of concept drift events, an increased model complexity might become necessary. On the other hand, the overall model complexity is usually bounded from above by the limitation of the available resources. This requires the intelligent reallocation of ressources whenever this limit is reached. Quite a number of approaches propose intelligent adaptation methods for the model complexity such as incremental architectures [START_REF] Wu | A hybrid constructive algorithm for single-layer feedforward networks learning[END_REF], self-adjustment of the number of basic units in extreme learning machines [START_REF] Ding | Improved incremental regularized extreme learning machine algorithm and its application in two-motor decoupling control[END_REF][START_REF] Zhang | Universal approximation of extreme learning machine with adaptive growth of hidden nodes[END_REF] or prototype-based models [START_REF] Impedovo | A novel prototype generation technique for handwriting digit recognition[END_REF][START_REF] Schleif | Sparse conformal prediction for dissimilarity data[END_REF][START_REF] Losing | Interactive online learning for obstacle classification on a mobile robot[END_REF], incremental base function selection for a sufficiently powerful data representation [START_REF] Chen | Efficient probabilistic classification vector machine with incremental basis function selection[END_REF], or self-adjusting cluster numbers in unsupervised learning [START_REF] Kalogeratos | Dip-means: An incremental clustering method for estimating the number of clusters[END_REF]. Such strategies can be put into the more general context of self-evolving systems, see e.g. [START_REF] Lemos | Evolving intelligent systems: Methods, algorithms and applications[END_REF] for an overview. An incremental model complexity is not only mandatory whenever concept drift is observed, hence a possibly changing model complexity is present, but it can also dramatically speed-up learning in batch scenarios, since it makes often tedious model selection superfluous.

In batch learning, not only the model complexity, but also essential metaparameters such as learning rate, degree of error, regularisation constants, etc. are determined prior to training. Often, time consuming cross-validation is used in batch learning, whereby first promising result how to automate the process have been presented [START_REF] Thornton | Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms[END_REF]. However, these are not suited for incremental learning scenarios: Concept drift turns critical meta-parameters such as the learning rate into model parameters, since their choice has to be adapted according to the (changing) data characteristics. Due to this fact, incremental techniques often rely on models with robust meta-parameters (such as ensembles), or they use meta-heuristics how to adapt these quantities during training.

Challenge 5: Efficient memory models. Due to their limited resources, incremental learning models have to store the information provided by the observed data in compact form. This can be done via suitable system invariants (such as the classification error for explicit drift detection models [START_REF] Ditzler | Learning in nonstationary environments: A survey[END_REF]), via the model parameters in implicit form (such as prototypes for distance-based models [START_REF] Hammer | Topographic mapping of large dissimilarity datasets[END_REF]), or via an explicit memory model [START_REF] Liu | Robotic cognitive behavior control based on biology-inspired episodic memory[END_REF][START_REF] Losing | Interactive online learning for obstacle classification on a mobile robot[END_REF]. Some machine learning models offer a seamless transfer of model parameters and memory models, such as prototype-or exemplar-based models, which store the information in the form of typical examples [START_REF] Hammer | Topographic mapping of large dissimilarity datasets[END_REF]. Explicit memory models can rely on a finite window of characteristic training examples, or represent the memory in the form of a parametric model. For both settings, a careful design of the memory adaptation is crucial since it directly mirrors the stability-plasticity dilemma [START_REF] Liu | Robotic cognitive behavior control based on biology-inspired episodic memory[END_REF][START_REF] Losing | Interactive online learning for obstacle classification on a mobile robot[END_REF].

Challenge 6: Model benchmarking. There exist two fundamentally different possibilities to assess the performance of incremental learning algorithms:

(1) Incremental -vs-non-incremental: In particular in the absence of concept drift, the aim of learning consists in the inference of the stationary distribution p(y| x) for typical data characterised by p( x). This setting occurs e.g. whenever incremental algorithms are used for big data sets, where they compete with often parallelised batch algorithms. In such settings, the method of choice evaluate the classification accuracy of the final model M t on a test set, or within a crossvalidation. While incremental learning should attain results in the same range as batch variants, one must take into account that they deal with restricted knowledge due to their streaming data access. It has been shown, as an example, that incremental clustering algorithms cannot reach the same accuracy as batch versions if restricted in terms of their resources [START_REF] Ackerman | Incremental clustering: The case for extra clusters[END_REF].

(2) Incremental -vs-incremental: When facing concept drift, different cost functions can be of interest. Virtual concept drift aims for the inference of a stationary model p(y| x) with drifting probability p( x) of the inputs. In such settings, the robustness of the model when evaluated on test data which follow a possibly skewed distribution is of interest. Such settings can easily be generated e.g. by enforcing imbalanced label distributions for test and training data [START_REF] Hoens | Learning in non-stationary environments with class imbalance[END_REF]. Whenever real confidence drift is present, the online behaviour of the classification error M t ( x t+1 ) -y t+1 for the next data point is usually the method of choice; thereby, a simple average of these errors can be accompanied by a detailed inspection of the overall shape of the online error, since it provides insight into the rates of convergence e.g. for abrupt concept drift.

(3) Formal guarantees on the generalisation behaviour: Since many classical algorithms such as the simple perceptron or large margin methods have been proposed as online algorithms, there exists an extensive body of work investigating their learning behaviour, convergence speed, and generalisation ability, classically relying on the assumption of data being i.i.d. [START_REF] Watkin | The Statistical Mechanics of Learning a Rule[END_REF]. Some results weaken the i.i.d. assumption e.g. requiring only interchangeability [START_REF] Shafer | A tutorial on conformal prediction[END_REF]. Re-cently, popular settings such as learning a (generalised) linear regression could be accompanied by convergence guarantees for arbitrary distributions p( x) by taking a game theoretic point of view: in such settings, classifier M t and training example x t+1 can be taken in an adversial manner, still allowing fast convergence rates in relevant situations [START_REF] Van Erven | Fast rates in statistical and online learning[END_REF][START_REF] Rakhlin | Online learning via sequential complexities[END_REF][START_REF] Kuhn | Analysis of the tdlms algorithm operating in a nonstationary environment[END_REF][START_REF] Sugiyama | Learning under nonstationarity: covariate shift and classbalance change[END_REF] The approach [START_REF] Moroshko | Second-order non-stationary online learning for regression[END_REF] even provides first theoretical results for real context drift, i.e. not only the input distribution, but also the conditional distribution p(y| x) can follow mild changes.

Incremental learning models

Incremental learning comes in various forms in the literature, and the use of the term is not always consistent; for some settings, as an example, a memory limitation cannot be guaranteed, or models are designed for stationary distributions only. We will give an overview over popular models in this context. Thereby, we will mostly focus on supervised methods due to its popularity. Online or incremental learning techniques have also been developed for alternative tasks such as clustering [START_REF] Mehrkanoon | Incremental multi-class semi-supervised clustering regularized by kalman filtering[END_REF][START_REF] Langone | Incremental kernel spectral clustering for online learning of non-stationary data[END_REF], dimensionality reduction [START_REF] Cui | Merging model-based two-dimensional principal component analysis[END_REF][START_REF] Bassiou | Online PLSA: Batch updating techniques including out-of-vocabulary words[END_REF][START_REF] Choi | Incremental two-dimensional kernel principal component analysis[END_REF][START_REF] Joseph | A fast incremental kernel principal component analysis for data streams[END_REF][START_REF] Ozawa | Adaptive incremental principal component analysis in nonstationary online learning environments[END_REF][START_REF] Leng | Locally linear embedding algorithm based on omp for incremental learning[END_REF], feature selection and data representation [START_REF] Zuniga | Hierarchical and incremental event learning approach based on concept formation models[END_REF][START_REF] Guan | Online nonnegative matrix factorization with robust stochastic[END_REF][START_REF] Ferreira | Incremental filter and wrapper approaches for feature discretization[END_REF][START_REF] Zeng | Incremental partial least squares analysis of big streaming data[END_REF][START_REF] Degeest | Feature ranking in changing environments where new features are introduced[END_REF][START_REF] He | Dynamic feature subspaces selection for decision in a nonstationary environment[END_REF], reinforcement learning [START_REF] Barreto | On-line reinforcement learning using incremental kernel-based stochastic factorization[END_REF][START_REF] Guan | From minimax value to low-regret algorithms for online markov decision processes[END_REF], mining and inference [START_REF] Gomes | Mining recurring concepts in a dynamic feature space[END_REF][START_REF] Pratama | Panfis: A novel incremental learning machine[END_REF].

Explicit treatment of concept drift. Dealing with concept drift at execution time constitutes a challenging task [START_REF] Kulkarni | Incremental learning from unbalanced data with concept class, concept drift and missing features: a review[END_REF][START_REF]The problem of concept drift: definitions and related work[END_REF][START_REF] Ditzler | Learning in nonstationary environments: A survey[END_REF][START_REF] Polikar | Guest editorial learning in nonstationary and evolving environments[END_REF]. There exist different techniques to address concept drift, depending on its type. Mere concept shift is often addressed by so-called passive methods, i.e. learning technologies which smoothly adapt model parameters such that the current distribution is reliably represented by the model. Rapid concept changes, however, often require active methods, which detect concept drift and react accordingly.

Virtual concept drift, which concerns the input distribution only, can easily occur e.g. due to highly imbalanced classes over time. One popular state-ofthe-art technology accounts for this fact by so-called importance weighting, i.e. strategies which explicitly or implicitly reweight the observed samples such that a greater robustness is achieved [START_REF] Kawakubo | Computationally efficient class-prior estimation under class balance change using energy distance[END_REF][START_REF] Balzi | Importance-weighted covariance estimation for robust common spatial pattern[END_REF][START_REF] Hoens | Learning in non-stationary environments with class imbalance[END_REF]. Alternatively, concept shift can have its reason in novelty within the data or even new classes. Such settings can naturally be incorporated into local models provided they offer an adaptive model complexity [START_REF] Schleif | Sparse conformal prediction for dissimilarity data[END_REF][START_REF] Fischer | Combining offline and online classifiers for life-long learning[END_REF][START_REF] Grossberg | Adaptive resonance theory: How a brain learns to consciously attend, learn, and recognize a changing world[END_REF][START_REF] Reiner | Efficient incremental construction of rbf networks using quasi-gradient method[END_REF][START_REF] Lu | Using self-organizing incremental neural network (soinn) for radial basis function networks[END_REF].

Real concept drift can be detected by its effect on characteristic features of the model such as the classification accuracy. Such quantitative features can be accompanied by statistical tests which can judge the significance of their chance, hence concept drift. Tests can rely on well-known statistics such as the Hoeffding bound [START_REF] Frias-Blanco | Online and non-parametric drift detection methods based on Hoeffding's bounds[END_REF], or alternatively on suitable distances such as the Hellinger distance, which can measure the characteristics of value distributions of such characteristic features. When integrated into robust classifiers such as ensemble techniques, models which can simultaneously deal with different types of drift result [START_REF] Brzezinski | Reacting to different types of concept drift: The accuracy updated ensemble algorithm[END_REF].

Support vector machines and generalised linear models. Several incremental SVM models exist [START_REF] Wen | Incremental learning of support vector machines by classifier combining[END_REF]. Some rely on heuristics, like retraining a model with all support vectors plus a new "incremental" batch of data [START_REF] Domeniconi | Incremental support vector machine construction[END_REF][START_REF] Syed | Incremental learning with support vector machines[END_REF], but without theoretical guarantees. Other incorporate modification of the SVM cost function to facilitate incrementality [START_REF] Ruping | Incremental learning with support vector machines[END_REF] and also possibly control complexity [START_REF] Gu | Incremental learning for ν-support vector regression[END_REF][START_REF] Gu | Incremental support vector learning for ordinal regression[END_REF]. Still, their resources are not strictly limited. As an alternative, adiabatically SVM training has been proposed, i.e., presenting one example at a time while maintaining the relevant optimality conditions on all previously seen examples. However this requires all previously seen samples need to be stored, although the approach can considerably simplify SVM training. Ensemble learning algorithms based on SVM [START_REF] Polikar | Learn++: An incremental learning algorithm for supervised neural networks[END_REF][START_REF] Wen | Incremental learning of support vector machines by classifier combining[END_REF] achieve incremental learning by training new classifiers for new batches of data, and combining all existing classifiers only for decision making. Another hybrid scheme combines a SVM classifier with a protoype-based data representation, whereby the latter can be designed as an online model based on which training examples for SVM can be generated [START_REF] Xing | L3-SVM: A lifelong learning method for SVM[END_REF]. Alternatively, SVMs can directly be trained in primal space, where online learning is immediate [START_REF] Chapelle | Training a support vector machine in the primal[END_REF]. Online versions have also been proposed for more complex generalised linear models such as Gaussian Process regression [START_REF] Gijsberts | Real-time model learning using incremental sparse spectrum gaussian process regression[END_REF][START_REF] Meier | Incremental local Gaussian regression[END_REF], whereby none of these models can yet easily deal with concept drift.

Connectionist models. As the problem of catastrophic forgetting was first remarked for multilayer perceptrons (MLP) [START_REF] Mccloskey | Catastrophic interference in connectionist networks: the sequential learning problem[END_REF][START_REF] Ratcliff | Connectionist models of recognition memory: constraints imposed by learning and forgetting functions[END_REF], it is hardly surprising that there exists significant work how to avoid it in connectionist systems. Initial consensus traced catastrophic forgetting back to their distributed information representation [START_REF] French | Catastrophic forgetting in connectionist networks[END_REF]. Indeed, localist connectionist models such as radial basis function (RBF) networks can work reliably in incremental settings [START_REF] Reiner | Efficient incremental construction of rbf networks using quasi-gradient method[END_REF][START_REF] Lu | Using self-organizing incremental neural network (soinn) for radial basis function networks[END_REF], whereby care has to be taken to guarantee their generalisation performance [START_REF] Sharkey | An analysis of catastrophic interference[END_REF]. Both capabilities are combined in semi-distributed representations. A number of algorithmic modifications of the MLP model has been proposed, such as sparsification [START_REF] French | Semi-distributed representations and catastrophic forgetting in connectionist networks[END_REF], orthogonalization of internal node weights [START_REF] French | Dynamically constraining connectionist networks to produce distributed, orthogonal representations to reduce catastrophic interference[END_REF][START_REF] Murre | The effects of pattern presentation on interference in backpropagation networks[END_REF], reduction of representational overlap while training [START_REF] Kortge | Episodic memory in connectionist networks[END_REF], or specific regularisation [START_REF] Goodfellow | An empirical investigation of catastrophic forgeting in gradient-based neural networks[END_REF]. These are successful in mitigating but not eliminating catastrophic forgetting [START_REF] Sharkey | An analysis of catastrophic interference[END_REF]. Recently, there has been an increased interest in extreme learning machines (ELM), which combine a random mapping with a trained linear readout. Due to their simple training, incremental variants can easily be formulated, whereby their reservoir naturally represents rich potential concepts [START_REF] Zhou | Online regularized and kernelized extreme learning machines with forgetting mechanism[END_REF][START_REF] Ding | Improved incremental regularized extreme learning machine algorithm and its application in two-motor decoupling control[END_REF][START_REF] Van Schaik | Online and adaptive pseudoinverse solutions for elm weights[END_REF][START_REF] Guo | An incremental extreme learning machine for online sequential learning problems[END_REF].

Furthermore, there exist attempts to modify the system design of MLPs [START_REF] Krushke | ALCOVE: An exemplar-based model of category learning[END_REF][START_REF] Sloman | Reducing interference in distributed memories through episodic gating[END_REF] which are more in the line of generative learning; they incorporate novelty detection and use different representational resources for new samples. Elaborate connectionist models feature different memory subsystems for long-and shortterm learning [START_REF] Rueckl | Jumpnet: A multiple-memory connectionist architecture[END_REF][START_REF] Ans | Avoiding catastrophic forgetting by coupling two reverberating neural networks[END_REF], as well as explicit replay and re-learning of previous samples to alleviate forgetting [START_REF] Robins | Catastrophic forgetting, rehearsal, and pseudorehearsal[END_REF]. These approaches reduce the problem of catastrophic forgetting at the price of vastly more complex model. Contrarily to other modern approaches, inspiration is taken primarily from biology and thus its solid mathematical understanding is yet lacking.

Explicit partitioning approaches. Many modern incremental learers rely on a local partitioning of the input space, and a separate classification/regression model for each partition [START_REF] Vijayakumar | Locally weighted projection regression: An o(n) algorithm for incremental real time learning in high-dimensional spaces[END_REF][START_REF] Nguyen-Tuong | Local gaussian processes regression for real-time model-based robot control[END_REF][START_REF] Sigaud | On-line regression algorithms for learning mechanical models of robots: A survey[END_REF][START_REF] Butz | Computational complexity of the xcs classifier system[END_REF][START_REF] Cederborg | Incremental local online gaussian mixture regression for imitation learning of multiple tasks[END_REF]. The manner of performing this partitioning is very diverse, ranging from kd-trees [START_REF] Cederborg | Incremental local online gaussian mixture regression for imitation learning of multiple tasks[END_REF] to genetic algorithms [START_REF] Butz | Computational complexity of the xcs classifier system[END_REF] and adaptive Gaussian receptive fields [START_REF] Vijayakumar | Locally weighted projection regression: An o(n) algorithm for incremental real time learning in high-dimensional spaces[END_REF]. Equally, the choice of local models varies between linear models [START_REF] Vijayakumar | Locally weighted projection regression: An o(n) algorithm for incremental real time learning in high-dimensional spaces[END_REF], Gaussian mixture regression [START_REF] Cederborg | Incremental local online gaussian mixture regression for imitation learning of multiple tasks[END_REF] or Gaussian Processes [START_REF] Nguyen-Tuong | Local gaussian processes regression for real-time model-based robot control[END_REF]. For high-dimensional problems such as occur in perception, the partitioning of the input space constitutes the bottleneck as concerns memory consumption. Covariance matrices as used in [START_REF] Vijayakumar | Locally weighted projection regression: An o(n) algorithm for incremental real time learning in high-dimensional spaces[END_REF], for example, are quadratic in the number of input dimensions, hence prohibitive for high dimensional data.

Decision trees partially alleviate this problem insofar as they cut along one dimension only, disregarding feature correlations. Quite a number of incremental tree builders have been proposed for classification or regression [START_REF] Fan | Cost-sensitive learning of hierarchical tree classifiers for large-scale image classification and novel category detection[END_REF][START_REF] Salperwyck | Incremental decision tree based on order statistics[END_REF][START_REF] Gholipour | An adaptive regression tree for non-stationary data streams[END_REF], with a particular focus on when to split, how to avoid overly large trees while ensuring incremental growth, and how to reliably deal with imbalanced classes [START_REF] Hapfelmeier | Pruning incremental linear model trees with approximate lookahead[END_REF][START_REF] Rosa | Splitting with confidence in decision trees with application to stream mining[END_REF][START_REF] Lyon | Hellinger distance trees for imbalanced streams[END_REF]. Interestingly, there do exist tree classifiers which result is entirely invariant to the ordering of the training data, but at the price of unlimited resources [START_REF] Lakshminarayanan | Mondrian forests: Efficient online random forests[END_REF].

Ensemble methods. Ensemble methods combine a collection of different models by a suitable weighting strategy. As such, they are ideally suited to implicitly represent even partially contradictory concepts in parallel and mediate the current output according to the observed data statistics at hand. Ensemble methods have proved particularly useful when dealing with concept drift, with a few popular models ranging from incremental random forests [START_REF] Ma | Compound exemplar based object detection by incremental random forest[END_REF], ensembles of bipartite graph classifiers [START_REF] Bertini | Ensemble of complete P-partite graph classifiers for nonstationary environments[END_REF], up to advanced weighting schemes suitable for different types of concept drift and recurring concepts [START_REF] Yin | DE2: Dynamic ensemble of ensembles for learning nonstationary data[END_REF][START_REF] Mejri | An ensemble method for concept drift in nonstationary environment[END_REF][START_REF] Li | Learning concept-drifting data streams with random ensemble decision trees[END_REF][START_REF] Yin | DE2: Dynamic ensemble of ensembles for learning nonstationary data[END_REF][START_REF] Ditzler | Incremental learning of concept drift from streaming imbalanced data[END_REF][START_REF] Elwell | Incremental learning of concept drift in nonstationary environments[END_REF].

Prototype-based methods. Prototype-based machine learning has its counterpart in cognitive psychology [START_REF] Rosch | Cognitive reference points[END_REF] which hypothesises that semantic categories in the human mind are represented by specific examples for these categories. In machine learning approaches, a class is represented by a number of representatives, and class membership is defined based on the distance of the data from these prototypes. For high dimensional data, adaptive low-rank metric learning schemes can dramatically improve classification accuracy and efficiency [START_REF] Bunte | Limited rank matrix learning, discriminative dimension reduction and visualization[END_REF][START_REF] Schneider | Adaptive relevance matrices in learning vector quantization[END_REF]. Prototype-based methods are a natural continuation of the work on localist or semi-distributed representations in early connectionist models, and thus share many properties. They have the advantage of an easily adaptive model complexity. One disadvantage is that the number of prototypes can become large whenever complex class boundaries are present.

Prototype-based models are closely connected to the non-parametric k-NN classifier (all training points act as prototypes) and the RBF model [START_REF] Runkler | Data Analytics Models and Algorithms for Intelligent Data Analysis[END_REF]. A popular supervised method is given by learning vector quantisation (LVQ) and recent variants which can be substantiated by a cost function [START_REF] Biehl | Dynamics and generalization ability of LVQ algorithms[END_REF]. A number of incremental variants and methods capable of dealing with concept drift have been proposed, such as dynamic prototype inversion / deletion schemes [START_REF] Losing | Interactive online learning for obstacle classification on a mobile robot[END_REF][START_REF] Schleif | Sparse conformal prediction for dissimilarity data[END_REF], or techniques with fixed model complexity, but intelligent source redistribution strategies [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF]. Similar unsupervised incremental models exist [START_REF] Hammer | Topographic mapping of large dissimilarity datasets[END_REF][START_REF] Cai | Imbalanced evolving self-organizing learning[END_REF][START_REF] Zhang | A load-balancing self-organizing incremental neural network[END_REF].

Insights into biological incremental learning. As biological incremental learning has reached a high degree of perfection, biological paradigms can provide inspiration how to set up artificial incremental systems. There is evidence that sensory representations in the neocortex are prototype-based, whereby neurons are topologically arranged by similarity [START_REF] Tanaka | Inferotemporal cortex and object vision[END_REF][START_REF] Leopold | Norm-based face encoding by single neurons in the monkey inferotemporal cortex[END_REF][START_REF] Ross | Not just the norm: Exemplar-based models also predict face aftereffects[END_REF][START_REF] Erickson | Clustering of perirhinal neurons with similar properties following visual experience in adult monkeys[END_REF]. Learning acts on these representations in a task-specific way insofar as the density of neurons is correlated to sensory regions which require finer discrimination [START_REF] Polley | Perceptual learning directs auditory cortical map reorganization through top-down influences[END_REF], i.e., where more errors occur. Here, learning is conceivably enhanced through acetylcholine release in case of task failures [START_REF] Weinberger | The nucleus basalis and memory codes: Auditory cortical plasticity and the induction of specific, associative behavioral memory[END_REF][START_REF] Hasselmo | The role of acetylcholine in learning and memory[END_REF]. Learning respects the topological layout by changing only a small subset of neural selectivities [START_REF] Rolls | The effect of learning on the face selective responses of neurons in the cortex in the superior temporal sulcus of the monkey[END_REF] at each learning event, corresponding to regions around the best matching unit [START_REF] Erickson | Clustering of perirhinal neurons with similar properties following visual experience in adult monkeys[END_REF].

Beyond the single-neuron level, there is a large body of literature investigating the roles of the hippocampal and neocortical areas of the brain in learning at the architectural level. Generally speaking, the hippocampus employs a rapid learning rate with separated representations whereas the neocortex learns slowly, building overlapping representations of the learned task [START_REF] Ŕeilly | The division of labor between the neocortex and hippocampus[END_REF]. A well-established model of the interplay between the hippocampus and the neocortex suggests that recent memories are first stored in the hippocampal system and played back to the neocortex over time [START_REF] Mcclelland | Why there are complementary learning systems in the hippocampus and neocortex: Insights from the successes and failures of connectionist models of learning and memory[END_REF]. This accommodates the execution of new tasks that have not been recently performed as well as the transfer of new task representations from the hippocampus (short-term memory) to the neocortical areas (long-term memory) through slow synaptic changes, i.e. it provides an architecture which is capable of facing the stability-plasticity dilemma.

Applications

We would like to conclude this overview by a glimpse on typical application scenarios where incremental learning plays a major role.

Data analytics and big data processing.

There is an increasing interest in single-pass limited-memory models which enable a treatment of big data within a streaming setting [START_REF] Hammer | Learning and modeling big data[END_REF]. Their aim is to reach the capability of offline techniques, and conditions are less strict as concerns e.g. the presence of concept drift. Recent approaches extend, for example, extreme learning machines in this way [START_REF] Xin | Elastic extreme learning machine for big data classification[END_REF]. Domains, where this approach is taken, include image processing [START_REF] Doan | Parallel incremental svm for classifying million images with very highdimensional signatures into thousand classes[END_REF][START_REF] Liu | Describing and learning of related parts based on latent structural model in big data[END_REF], data visualisation [START_REF] Malik | An online generalized eigenvalue version of laplacian eigenmaps for visual big data[END_REF], and processing of networked data [START_REF] Dhanjal | Efficient eigen-updating for spectral graph clustering[END_REF].

Robotics. Autonomous robotics and human-machine-interaction are inherently incremental, since they are open-ended, and data arrive as a stream of signals with possibly strong drift. Incremental learning paradigms have been designed in the realm of autonomous control [START_REF] Wang | Learning from adaptive neural dynamic surface control of strict-feedback systems[END_REF], service robotics [START_REF] Amirat | Assistance and service robotics in a human environment[END_REF], computer vision [START_REF] Zhang | Adaptive incremental learning of image semantics with application to social robot[END_REF], self-localisation [START_REF] Khan | Ibuild: Incremental bag of binary words for appearance based loop closure detection[END_REF], or interactive kinesthetic teaching [START_REF] Saveriano | Incremental kinesthetic teaching of end-effector and null-space motion primitives[END_REF][START_REF] Ghalamzan | An incremental approach to learning generalizable robot tasks from human demonstration[END_REF]. Further, the domain of autonomous driving is gaining enormous speed [START_REF] Thrun | Toward robotic cars[END_REF][START_REF] Mozaffari | A robust safety-oriented autonomous cruise control scheme for electric vehicles based on model predictive control and online sequential extreme learning machine with a hyper-level fault tolerance-based supervisor[END_REF][START_REF] Allamaraju | Human aware UAS path planning in urban environments using nonstationary MDPs[END_REF], with enacted autonomous vehicle legislation in already eight states in the US (Dec. 2015). Another emerging area, caused by ubiquitous sensors within smart phones, addresses activity recognition and modeling [START_REF] Hasan | Incremental learning of human activity models from videos[END_REF][START_REF] Abdallah | Adaptive mobile activity recognition system with evolving data streams[END_REF][START_REF] Kviatkovsky | Online action recognition using covariance of shape and motion[END_REF][START_REF] Hu | An incremental dpmm-based method for trajectory clustering, modeling, and retrieval[END_REF][START_REF] Loy | Incremental activity modeling in multiple disjoint cameras[END_REF][START_REF] Hasan | Incremental activity modeling and recognition in streaming videos[END_REF].

Image processing. Image and video data are often gathered in a streaming fashion, lending itself to incremental learning. Typical problems in this context range from object recognition [START_REF] Dou | Moving object detection based on incremental learning low rank representation and spatial constraint[END_REF][START_REF] Bai | An incremental structured part model for object recognition[END_REF][START_REF] Losing | Interactive online learning for obstacle classification on a mobile robot[END_REF], image segmentation [START_REF] Dou | Moving object detection based on incremental learning low rank representation and spatial constraint[END_REF][START_REF] He | Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video[END_REF], and image representation [START_REF] Diaz-Chito | Incremental generalized discriminative common vectors for image classification[END_REF][START_REF] Wu | Inexact and incremental bilinear Lanczos components algorithms for high dimensionality reduction and image reconstruction[END_REF], up to video surveillance, person identification, and visual tracking [START_REF] Tao | Recursive non-rigid structure from motion with online learned shape prior[END_REF][START_REF] Dewan | Adaptive appearance model tracking for still-to-video face recognition[END_REF][START_REF] Xi-Zhao | Architecture selection for networks trained with extreme learning machine using localized generalization error model[END_REF][START_REF] Ma | Two dimensional hashing for visual tracking[END_REF][START_REF] Dou | Robust visual tracking based on incremental discriminative projective non-negative matrix factorization[END_REF][START_REF] Rico-Juan | Adaptive training set reduction for nearest neighbor classification[END_REF][START_REF] Zhang | Robust visual tracking via incremental low-rank features learning[END_REF][START_REF] Lu | Application of an incremental svm algorithm for on-line human recognition from video surveillance using texture and color features[END_REF]. Automated annotation. One important process consists in the automated annotation or tagging of digital data. This requires incremental learning aproaches as soon as data arrive over time; example systems are presented in the approaches [START_REF] Huang | Online semi-supervised annotation via proxy-based local consistency propagation[END_REF][START_REF] Bianco | An interactive tool for manual, semi-automatic and automatic video annotation[END_REF][START_REF] Carneiro | Multilingual part-of-speech tagging with weightless neural networks[END_REF] for video and speech tagging.

Outlier detection. Automated surveillance of technical systems equipped with sensors sensors constitutes an important task in different domains, starting from process monitoring [START_REF] Hartert | Dynamic supervised classification method for online monitoring in non-stationary environments[END_REF] fault diagnosis in technical systems [START_REF] Yin | Online fault diagnosis method based on incremental support vector data description and extreme learning machine with incremental output structure[END_REF][START_REF] Huang | Network-traffic anomaly detection with incremental majority learning[END_REF][START_REF] Yang | A very fast decision tree algorithm for real-time data mining of imperfect data streams in a distributed wireless sensor network[END_REF], up to cyber-security [START_REF] Pang | A federated network online network traffics analysis engine for cybersecurity[END_REF]. Typically, a strong drift is present in such settings, hence there is a demand for advanced incremental learning techniques.

Alexander Gepperth 1 ,

 1 Barbara Hammer 2 * 1-U2IS, ENSTA ParisTech U2IS, ENSTA ParisTech, Inria, Université Paris-Saclay 828 Bvd des Maréchaux, 91762 Palaiseau Cedex, France 2-Bielefeld University, CITEC centre of excellence Universitätsstrasse 21-23 D-33594 Bielefeld, Germany

* This research/work was supported by the Cluster of Excellence Cognitive Interaction Technology 'CITEC' (EXC 277) at Bielefeld University, which is funded by the German Research Foundation (DFG).


Thomas Hecht

Alexander Gepperth

Towards incremental deep learning: multi-level change detection in a hierarchical recognition architecture

We present a trainable hierarchical architecture capable of detecting newness (or outliers) at all hierarchical levels. This contribution paves the way for deep neural architectures that are able to learn in an incremental fashion, for which the ability to detect newness is an indispensable prerequisite. We verify the ability to detect newness by conducting experiments on the MNIST database, where we introduce either localized changes, by adding noise to a small patch of the input, or global changes, by changing the global arrangement of local patterns which is not detectable at the local level.

Introduction

This study is conducted in the context of hierarchical incremental learning algorithms. It is a proof-of-concept type study, showing the capacity to detect newness (or outliers) in a minimal hierarchical architecture operating on a semirealistic but widely known and accepted benchmark database in machine learning, the MNIST dataset [START_REF] Lecun | Mnist handwritten digit database[END_REF].

Incremental learning algorithms are, roughly speaking, algorithms that can take examples one by one, without knowing their number in advance, and which can deal with changes in the input statistics without requiring a complete retraining with all data. An important prerequisite for incremental learning is the detection of newness or change: if an algorithm is supposed to track changing data statistics, it first of all needs to be able to detect change [START_REF] Kulkarni | Incremental learning from unbalanced data with concept class, concept drift and missing features: a review[END_REF]. To our knowledge, all existing incremental learning algorithms possess this property (see [START_REF] Sigaud | On-line regression algorithms for learning mechanical models of robots: a survey[END_REF] for a review): some algorithms achieve it by an adaptive subdivision of the input space, e.g., [START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF][START_REF] Nguyen-Tuong | Local gaussian processes regression for real-time modelbased robot control[END_REF][START_REF] Cederborg | Incremental local online gaussian mixture regression for imitation learning of multiple tasks[END_REF][START_REF] Butz | Computational complexity of the xcs classifier system[END_REF], where local models are learned in each sub-volume, other achieve this by using prototypes to directly approximate the data distribution in input space [START_REF] Fischer | Certainty-based prototype insertion/deletion for classification with metric adaptation[END_REF][START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF].

On the other hand, while hierarchical learning algorithms are currently showing very promising perspectives, all existing incremental learning algorithms are, to our knowledge, "flat" architectures: Although the input space is decomposed into sub-volumes, the input vectors themselves are not, such as convolutional Fig. 1: The minimalist hierarchical system used in this study, composed of input layer, hidden layer and top layer.

neural networks do when they analyze their inputs by local receptive fields. Especially prototype-based incremental learning methods [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF][START_REF] Fischer | Certainty-based prototype insertion/deletion for classification with metric adaptation[END_REF] could profit greatly from hierarchies namely by strongly reduced memory requirements for storing prototypes. In this case, change detection would have to work on all levels of a hierarchical incremental architecture, apart from the issue of learning rules that would react to such changes which will not be treated here. The goal of this contribution is finally to demonstrate multi-level change detection in a minimalist hierarchical extension of the prototype-based incremental architecture proposed in [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF]. This architecture, for which excellent performance on real-world benchmarks has been demonstrated [START_REF] Hecht | A generative learning approach to sensor fusion and change detection[END_REF][START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], is closely related to other prototype-based methods such as GMLVQ [START_REF] Schneider | Adaptive relevance matrices in learning vector quantization[END_REF] and notably ioLVQ [START_REF] Fischer | Certainty-based prototype insertion/deletion for classification with metric adaptation[END_REF].

The architecture contains three layers as depicted in Fig. 1, where separate hidden-layer maps try to represent local receptive fields in the input, and the top-layer map aims at representing the union of all hidden-layer map activities 1 .

Change detection should be activated in different layers depending on the type of change that occurs: if it exclusively occurs inside a local receptive field, the hidden layer activities responsible for this receptive field should signal change, whereas the top layer should react in case of global changes. Such global changes may not even be detectable in the hidden layer because they can leave hidden-layer statistics completely unaffected.

Methods

For representing both hidden and top layer inputs, we use a prototype-based learning algorithm which is loosely based on the self-organizing map model, see [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF]. Inputs are represented by graded neural activities arranged in maps of n × n units, organized on a two-dimensional grid lattice. Each unit's associated weight vector (its prototype) is updated using the learning rule and good practices proposed by Kohonen[12] which decreases learning rate (t) and Gaussian neighborhood radius σ(t) from initially large values to their asymptotic values ∞ , σ ∞ . Since the hidden-layer map activities are inputs to the top layer, they need to be fully converged before top-layer selectivities are learned, which needs to be ensured by a proper temporal organization of the training phase, see Sec. 3.

For any map X, the map activity z X ij (t) at position (i, j) is derived from the Euclidean distance between the unit prototype w X ij (t) and the current input x(t):

z X ij (t) = TF g κ ||w Z ij (t) -x(t)|| (1)
where, as described in [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], g κ (•) is a Gaussian function with an adaptive parameter κ that converts distances into the [0, 1] interval, and TF(•) is a transfer function. Differently from [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], we chose a transfer function that just keeps the activity of the best-matching unit at coordinates (i * , j * ):

TF(x, i, j) = x if (i, j) = (i * , j * ) 0 otherwise (2)
3 Experiments

We fix the sizes of all hidden-layer maps to n × n = 6 × 6; whereas the top-layer map has size 10 × 10. As we apply our architecture to the MNIST database [START_REF] Lecun | Mnist handwritten digit database[END_REF], the original sample size is 28 × 28 pixels. We use non-overlapping receptive fields of 14 × 14 pixels (see Fig. 2), which leads to 2x2=4 hidden-layer maps.

The asymptotic values of learning rate and neighbourhood radius are ∞ = 0.001 and σ ∞ = 0.1 for all maps in the system. The principal quantity investigated in this study is the activity of the best-matching unit for a map X, denoted z * X (t), which is inversely related to the Euclidean distance between sample and best-matching prototype. A significant deviation of z * X (t) from its long-term average value is interpreted as an indication of change.

Protocol

An experiment consists of T = 200000 random pattern presentations and is conducted in three phases: Hidden layer training From step 0 to 45.000, each hidden-layer map is trained with while top-layer learning and adaptive distance κ updating, see [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], is disabled.

Top layer training From step 45.000 to 140.000, hidden-layer learning and adaptive distance κ updating, see [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], is disabled and the top-layer map is trained using the concatenation of hidden-layer map activations.

Testing From step 140.000 to the end, the data distribution is artificially changed, without any prototype or adaptive distance adaptation.

Changes in data distribution can be either at the local level or the global level, see Fig. Local changes are produced by adding uniform noise, U(0, 1), to a single 14 × 14 pixels RF content. Global changes are obtained by concatenating the left and right half of two randomly chosen input samples, giving again a 28 × 28 sample. Whether the neural architecture is fed with locally or globally modified inputs starting at t = 140.000, the architecture clearly detects that a change occurred in the data distribution, see Figs. 4,3. Furthermore, the hierarchical organization of the architecture allows to more accurately identify the type of change: Fig. 4 shows that a high-level change (see Fig 2) can be detected in the top-level map while hidden-layer activations stay unchanged. For local changes (see Fig 2), the reverse is the case: best-matching unit activations in the hidden-layer map associated with the noised signal are severely affected. We observe a slight change in average top-level layer activity as well, which is understandable as top-level activations directly depend hidden-layer activations, so a change in the former affects the latter. With a finer subdivision into receptive fields, a local change in one RF would not have such a significant impact on top-level activations.

Results

Discussion, conclusion, perspectives

This study has, first of all, outlined how a prototype-based incremental learning architecture that is "flat" could be generalized to a hierarchical architecture. In this generalized architecture, we showed that it is possible to detect changes in input statistics at all levels of the hierarchy. As change detection is an important prerequisite for incremental learning, see Sec. 1, we remove an important conceptual obstacle to using hierarchical prototype-based architectures in an incremental fashion. This in turn is a desirable thing as prototype-based methods are particularly suited for incremental learning [START_REF] Fischer | Certainty-based prototype insertion/deletion for classification with metric adaptation[END_REF][START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF].

Hierarchical prototype-based methods might also remove another major obstacle to wide-spread use: the curse of dimensionality. For difficult problems in high-dimensional spaces, it stands to reason that a very high number of prototypes might be required to accurately map data distributions. If however a problem is partly factorisable, i.e., can be simplified by subdividing the input into receptive fields whose content is approximately independent (as it is often the case in visual processing), the size of the prototypes to be stored reduces dramatically. If we denote the number of top-level units in the presented architecture by T = 100, the number of hidden layer maps (each composed of h units) by H = 4, and the input dimensionality by I = 784, we obtain for the total number of weights W = h(I + T H) = 50.400. For a comparable "flat" system without hidden layer we would need W = IT = 78400 connections already. This difference between these two quantities can be increased by varying the free parameter h: with maps of size h = 4 × 4 = 16 in the hidden layer, we obtain W = 22400. If recognition performance is maintained, this offers a promising way around the curse of dimensionality for prototype-based methods in general.

In future work, will wish to explore precisely these questions: can the presented (non-incremental) architecture obtain comparable classification results (for MNIST, this seems to be the case but tests on other problems are needed)? How far can we reduce h without sacrificing performance? And, most importantly, we will investigate learning rules that can in a hierarchical incremental learning architecture, with the goal of pushing the capacities of incremental learning architectures beyond the current state of the art.

Fig. 2 :

 2 Fig. 2: Illustration of the experimental protocol. Left: partitioning of a 28x28 MNIST sample into 2x2 receptive fields (RFs) of 14x14 pixels each. Middle: application of a local change, replacing a single RF by white noise. Right: application of global change, by mixing the left and right halves of different MNIST samples. The local patterns inside the RFs are not, statistically speaking, affected by this operation.

2

 2

  . The former corresponds to a localized change within an RF which should be detectable mainly by the hidden-layer maps. The latter should affect the top-level map alone as only the global arrangement of patterns within each RF changes w.r.t. the learning phase but not the local patterns themselves.

Fig. 3 :

 3 Fig. 3: Detection of low-level change. Shown are best-matching unit activations over time for all four hidden-layer maps (left) and top-layer map (right). Time series have been post-processed by exponential smoothing with a parameter of α = 0.005 for better visualization. Dotted lines indicate the case of no change.

Fig. 4 :

 4 Fig. 4: Detection of high-level change. Shown are best-matching unit activations over time for all four hidden-layer maps (left) and top-layer map (right). Time series have been post-processed by exponential smoothing with a parameter of α = 0.005 for better visualization. Dotted lines indicate the case of no change.

Normally, the top layer would be connected to a readout mechanism inferring class attributes as in[START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], but, as classification performance on the MNIST database has already been demonstrated in[START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF] for the "flat" system, we omit it here and focus on change detection.

* Dr. Alexander Gepperth is with Inria Flowers. Thomas Hecht gratefully acknowledges funding support by the "Direction Générale de l'Armement" (DGA) and École Polytechnique.


Thomas Hecht

Alexander Gepperth

Computational advantages of deep prototype-based learning

Keywords: prototype-based learning, pattern recognition, deep learning, incremental learning

We present a deep prototype-based learning architecture which achieves a performance that is competitive to a conventional, shallow prototype-based model but at a fraction of the computational cost, especially w.r.t. memory requirements. As prototype-based classification and regression methods are typically plagued by the exploding number of prototypes necessary to solve complex problems, this is an important step towards efficient prototype-based classification and regression. We demonstrate these claims by benchmarking our deep prototype-based model on the well-known MNIST dataset.

Introduction

This study is conducted in the field of prototype-based machine learning, and especially regarding the question how to render such machine learning approaches more efficient w.r.t. memory consumption. In prototype-based learning, the probability distribution in data space is not expressed in parametric form but by a learned set of samples, the so-called prototypes. Prototype-based machine learning methods were originally motivated by prototype theory from cognitive psychology (see, e.g., [START_REF] Rosch | Cognitive reference points[END_REF]) which claims that semantic categories in the human mind are represented by a set of "most typical" examples (or prototypes) for these categories. Well-known prototype-based approaches are the learning vector quantization (LVQ) model [START_REF] Biehl | Fast learning in networks of locally tuned processing units[END_REF], the RBF model [3] or the self-organizing map (SOM) model [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF]. A very popular prototype-based method in computer vision in is particle filtering [START_REF] Sanjeev | A tutorial on particle filters for online nonlinear/non-gaussian bayesian tracking[END_REF], where a continuous, evolving probability density function is described and updated as a set of prototypes (here denoted particles) whose local density represents local probability density. Prototype-based methods are well suited for incremental learning [START_REF] Losing | Interactive Online Learning for Obstacle Classification on a Mobile Robot[END_REF][START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF] since prototypes have a very obvious interpretation, and can thus be manipulated easily, e.g., by adding, adapting or removing prototypes (see [START_REF] Gepperth | Incremental learning algorithms and applications[END_REF] for a precise definition of incremental learning).

Thomas Hecht gratefully acknowledges funding support by the "Direction Générale de l'Armement" (DGA) and Ecole Polytechnique. Prototype-based learning usually has a "flat" architecture (such as the RBF or the LVQ models) with one hidden layer between input and output, where hidden layer weights (the prototypes) describe the input distribution. An obvious problem of such flat architectures is the curse of dimensionality: complex probability distributions in high-dimensional spaces may conceivably require a great number of prototypes to be well approximated, so the memory requirements of flat prototype-based learning can become excessive depending on the problem at hand [START_REF] Carse | Parallel Problem Solving from Nature -PPSN IV: International Conference on Evolutionary Computation -The 4th International Conference on Parallel Problem Solving from Nature[END_REF]. This study generalizes "flat" prototype-based learning as presented in [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF] to a "deep" architecture (see Fig. 1), with localized receptive fields in the lower layers, just as it is the case in convolutional neural networks (CNNs, see [START_REF] Sermanet | Pedestrian detection with unsupervised multi-stage feature learning[END_REF]). This makes use of the probabilistic structure of images whose distant parts (receptive fields) are often approximately independent. In this case, it is far more efficient to model their distributions independently as well. If this is done by prototypes, the curse of dimensionality is reversed: as the required number of prototypes can increase exponentially with dimensionality, it can also decrease exponentially since the dimension of receptive fields is small. In its simplest form, this comes down to a deep four-layer architecture (see Fig. 1), where the first hidden layer now contains prototype activities related to local descriptions of the input, which are subsequently integrated into a global representation in the second hidden layer.

The goal of this study is to show that such a deep prototype-based classifier can achieve a performance that is comparable to its flat counterpart but at a dramatically reduced number of connection weights, which reduces memory consumption and training time. For this purpose, we use the well-known MNIST dataset [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] which is an accepted benchmark in the field of machine learning, and offers the advantage of comparing the absolute performances of both flat and deep architecture to the results of other methods on MNIST.

Methods

For representing both first and second hidden layers inputs of the architecture shown in Fig. 1, we use a prototype-based learning algorithm which is loosely based on the self-organizing map model, see [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF]. Inputs are represented by graded neural activities arranged in maps organized on a two-dimensional grid lattice. Each unit (i, j) of the map X is associated with a weight vector w X ij ∈ W X which is called prototype.

Each map of the M h1 first hidden-layer maps has the same size N 1 = n h1 × n h1 units and receives a crop from the system input data of size n crop × n crop . M h1 is determined by the size of non-overlapping receptive fields in the input layer: the the smaller the receptive fields (each associated with a map in h1) is, the greater is M h1 . The single map in the second hidden-layer h2, of size n h2 × n h2 , receives a concatenation of activities in the M h1 maps of h1. The toplayer (output) consists of a linear regression module that computes the prediction W top (t) T • Z h2 (t) of the system concerning its current input with W top the linear regression factors and Z h2 (t) the output activities of the second hidden-layer h2.

Because we wish to work in an on-line fashion, weights vectors of all layer are updated at the same time (in contrast to conventional deep architectures which require layer-wise training). Prototypes of the two hidden layers are updated following the Kohonen rule. Each unit's associated weight vector (its prototype) is updated using the learning rule and good practices proposed by [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF] which decreases learning rate (t) and Gaussian neighborhood radius σ(t) from initially large values to their asymptotic values ∞ , σ ∞ . For each iteration step t <= T , prototypes of maps (W X ) are updated depending on the current input x with the following rule :

W X (t + 1) ← W X (t) + (t) • Φ(t) • (x(t) -w X (t)) (1)
where is the learning rate and Φ(t) = φ(w X (t), σ(t)) is a discretized Gaussian kernel with σ variance, centered on the current best-matching w X unit and representing the neighborhood influence of the weights adaptation.

For any map X, the map activity z X ij ∈ Z X at position (i, j) is then derived from the Euclidean distance between the unit prototype w X ij and the current input x: where, as described in [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF], g κ (•) is a Gaussian function with an adaptive parameter κ that converts distances into the [0, 1] interval, and f(•) is a monotonous non-linear transfer function, defined as :

z X ij (t) = f g κ ||w X ij (t) -x(t)|| (2)
m 0 = max y zP (y, t) m 1 = max y z P (y, t) 20 f (z P (y) = m 0 z P (y) 20 m 1 (3)
The top-layer weights vector is updated following an on-line stochastic gradient descent mechanism with a fixed learning rate η over time by comparison of its own prediction and the current ground truth label of the current input data. Because we apply our system to classification tasks, labels y and predictions p are not scalars but vectors of c values where the position of the maximum indicates respectively the target class label and the system decision (population coding).

W top (t + 1) ← W top (t) -η • (y(t) -p(t)) • Z h2 (t) (4)
We use two indicators to assess performance: mean classification errors and total number of connection weights.

Mean classification error

This indicator is a commonly used measure for comparing performances of a classification system. During the testing phase, when all the learning processes (i.e. weights updates) are stopped, classification errors are logged on the MNIST test set following the simple rule : γ = 0. if argmax(y(t)) equals argmax(p(t)) and γ = 1. otherwise. Then, we just compute the mean for all these errors µ = 1

T test • T test t=1 γ.
Total number of weighted connexions This indicator is a simple means to compare our hierarchical architecture and a "flat" architecture, only composed of a huge map and a linear regression module, in terms of number of connexions. Let M h1 be the number of maps in the first hidden layer each composed of N 1 = n h1 * n h1 units and M h2 = 1 the number of maps in the second hidden layer, composed of N 2 = n h2 * n h2 units. Because connexions between the second hidden layer and the top layer are negligible in the two architectures, we do not take them into account. The total number of weighted connexions is then computed as : K = N 1 * (d+N 2 * M h1 ) for a hierarchical architecture and K = d * N 2 for a "flat" one. By example, an architecture with 4 hidden maps of 4 × 4 units receiving crops extracted from 784 pixels images (such as MNIST images), followed by a hidden map of 10 × 10 units followed by the linear regression module gives K = (4 × 4) * (784 + (10 × 10) * 4) = 18 944. For a comparable "flat" system without the first hidden layer, we would need K = 784 * (10 × 10) = 78 400 connexions.

Experiments

Protocol

Each experiment run consists of T train = 1 000 000 training iterations followed by T test = 50 000 testing iterations. For all self-organizing maps, we use exponentially decreased values of learning rate and neighbourhood radius and a fixed linear regression learning rate : 0 = 0.25, ∞ = 0.001, σ 0 = 0.5 * n X , σ ∞ = 0.085 and η = 0.009. Both self-organizing maps and linear regression weight vectors are initialized to random uniform values between -0.001 and 0.001. Samples are always randomly and uniformly picked and are provided to the system as input data x and ground truth y. Results presented below are averaged measures over 10 runs. Datasets targets are split into c different classes and each input data is d dimensional.

We use the publicly available MNIST classification benchmark as described in [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]. It contains c = 10 classes, corresponding to the 10 handwritten digits from "0" to "9" and comes separated into a well-defined train set and a smaller test set. Each sample has a dimensionality of d = 28 × 28 = 784.

Results

As shown in Table 1, our hierarchical system with 4 hidden layer maps can achieve comparable performances with less connexions involved. When comparing mean classification errors in the hierarchical case (µ) and in the "flat" one (μ), it seems that, with respect to the same parameters set, there is no need to add hidden layers. But when looking at the total number of weighted connexions, K is always smaller than K : by example, with M h1 = 4 maps of N 1 = 6 × 6 units in the first hidden layer and one map of N 2 = 20 × 20 unit in the second hidden layer, after T train on-line iterations the hierarchical system can achieve, in average, equivalent classification performances than a system only composed of a single 20 × 20 self-organizing map but with three times less connexions.

If we try with another number of hidden layer maps -by instance with M h1 = 16 and n crop = 7 -it seems that performances drop down and that the ratio K/ K is no longer a real advantage. Because we are dealing with raw pixels and no extracted features on this dataset, the system is extremly sensible to the size of the receptive fields. It seems to us that there is an interessant research question about the well suited n crop : what is the link with the dataset distribution, are overlapping receptive fields a good idea or can the system adapt itself this parameter during the incremental learning paradigm ? This article has shown that a deep prototype-based architecture is capable of achieving performances comparable to those of a flat architecture of the same type, while drastically reducing the number of connection weights, and therefore memory usage and processing time. We believe that this effect may be observed for any prototype-based method (notably LVQ) if approximatye independence relations hold between separate parts of the input. As stated in Sec. 1, this is almost always the case if inputs are visual images, although of course the right parameters have to be found in the form of receptive field sizes and overlaps. However to be fair, this parameter search would also have to be performed for convolutional neural network (CNN) and is a property of all deep architectures based on local receptive fields.

Given that prototype-based methods in machine learning have a number of highly desirable properties, such as online and incremental learning capacity [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF][START_REF] Losing | Interactive Online Learning for Obstacle Classification on a Mobile Robot[END_REF], a simple probabilistic interpretation [START_REF] Schneider | Hyperparameter learning in probabilistic prototype-based models[END_REF] and a natural way of processing multi-class problems, the reduction of resource requirements even when treating complex visual problems seems an important step towards wide-spread use of prototype-based machine learning methods.

Fig. 1 :

 1 Fig. 1: The hierarchical system used in this study, composed of one input layer, two hidden layers and one top layer.

Fig. 2 :

 2 Fig. 2: An overview of prototypes in 4 maps of the first hidden layer h1 corresponding to 2 × 2 receptive fields of 14 × 14 pixels over MNIST inputs.

Table 1 :

 1 MNIST mean classification errors

		n crop = 14, M h1 = 2 × 2
	n h1 n h2	µ	μ	K	K
	4 10 10.8 (±0.7) 9.1 (±0.5) 18'944 78'400
	6 10 9.4 (±0.8) 9.1 (±0.5) 42'624 78'400
	8 10 11.2 (±0.6) 9.1 (±0.5) 75'776 78'400
	4 20 6.7 (±0.4) 6.3 (±0.6) 38'144 313'600
	6 20 5.9 (±0.3) 6.3 (±0.6) 85'824 313'600
	8 20 6.4 (±0.6) 6.3 (±0.6) 152'576 313'600
		n crop = 7, M h1 = 4 × 4
	n h1 n h2	µ	μ	K	K
	4 10 12.9 (±0.9) 9.1 (±0.5) 38'144 78'400
	6 10 11.1 (±0.8) 9.1 (±0.5) 85'824 78'400
	8 10 11.0 (±0.9) 9.1 (±0.5) 152'576 78'400
	4 20 10.5 (±0.6) 6.3 (±0.6) 114'944 313'600
	6 20 10.1 (±0.5) 6.3 (±0.6) 258'624 313'600
	8 20 10.8 (±0.5) 6.3 (±0.6) 459'776 313'600
	4 Discussion, conclusion, perspectives