Yann Bernard
email: yann.bernard@loria.fr

Nicolas Hueber
email: nicolas.hueber@isl.eu

Bernard Girau
email: bernard.girau@loria.fr

A fast algorithm to find Best Matching Units in Self-Organizing Maps

Keywords: Self-Organizing Maps, Vector Quantization, Dimensionality Reduction

Self-Organizing Maps (SOM) are well-known unsupervised neural networks able to perform vector quantization while mapping an underlying regular neighbourhood structure onto the codebook. They are used in a wide range of applications. As with most properly trained neural networks models, increasing the number of neurons in a SOM leads to better results or new emerging properties. Therefore highly efficient algorithms for learning and evaluation are key to improve the performance of such models. In this paper, we propose a faster alternative to compute the Winner Takes All component of SOM that scales better with a large number of neurons. We present our algorithm to find the so-called best matching unit (BMU) in a SOM, and we theoretically analyze its computational complexity. Statistical results on various synthetic and real-world datasets confirm this analysis and show an even more significant improvement in computing time with a minimal degradation of performance. With our method, we explore a new approach for optimizing SOM that can be combined with other optimization methods commonly used in these models for an even faster computation in both learning and recall phases.

Introduction

Self-organizing maps (SOM) are widely used algorithms that feature vector quantization with dimensionality reduction properties. An explanation of how they work can be found in [START_REF] Kohonen | Kohonen network[END_REF]. They are used in numerous fields like image processing, automatic text and language processing, and for visualization, analysis and classification of all kinds of highly dimensional datasets. Many applications examples are depicted in [START_REF] Cottrell | Self-OrganizingMaps, theory and applications[END_REF]. However, the amount of computations required by SOMs linearly increases with the number of neurons, the number of elements in the dataset and the dimensionality of the input, in both learning and recall phases. Therefore applying SOMs on datasets with huge numbers of elements and with a high number of neurons to precisely represent the input induces a significant computational cost that may exceed some constraints such as real-time computation or low power consumption.

With the goal of reducing the required computational time of SOMs in mind, variants of the classical SOM algorithm have been developed. The most wellknown SOM modification is the Batch Learning algorithm, as explained in [START_REF] Cottrell | Self-OrganizingMaps, theory and applications[END_REF]. Contrary to the classical online learning, the batch learning averages the modifications over multiple training vectors before updating the neurons weights. Similar efforts have been made in [START_REF] Fiannaca | Simulated annealing technique for fast learning of som networks[END_REF] or in [START_REF] Oyana | The new and computationally efficient mil-som algorithm: potential benefits for visualization and analysis of a large-scale highdimensional clinically acquired geographic data[END_REF]. However, all those variants are only focusing on reducing the convergence time of the SOM training. To the best of our knowledge, no work has been carried out to reduce the time required for each iteration. This can be partially explained by the highly parallel nature of the computations inside each iterations, in so far as when a fast real world implementation is required, parallel solutions are proposed, like the use of an FPGA substrate with each neuron having its own circuitry, as in [START_REF] Abadi | A scalable and adaptable hardware noc-based self organizing map[END_REF] and in [START_REF] Huang | A hardwareefficient vector quantizer based on self-organizing map for high-speed image compression[END_REF]. However, parallel solutions should not lead to a lack of effort in optimizing the algorithms, as the majority of SOM training is performed on CPU, and parallel hardware can be costly and difficult to program. Furthermore one can parallelise multiple iterations within an epoch instead of inside the iteration itself, and therefore can benefit from our improvements on parallel hardware.

A SOM training iteration consists of two major parts, a competitive part which searches the Best Matching Unit (or winner neuron), and a cooperative part which updates all the neurons weights proportionally to their distance with the BMU. In the classic SOM, both steps have the same algorithmic complexity (number of neurons multiplied by the dimensionality of the data) and take roughly the same time (depending on implementation details). In this paper we focus on improving the competitive part by reducing the number of neurons evaluated to find the BMU. This optimization also applies to the recall phase.

After a brief description of the standard SOM model in section 2, section 3 defines the proposed method to speed up the computation of BMU, before analyzing its computational complexity. The experimental setup is described in section 4, and the corresponding results are discussed in section 5.

Self-Organizing Maps

Vector quantization

Vector quantization (VQ) is a lossy source coding technique in which blocks of samples are quantized together [START_REF] Vasuki | A review of vector quantization techniques[END_REF]. It consists in approximating the probability density of the input space (which is split in blocks of samples) with a finite set of prototype vectors. A prototype vector is often referred to as a codeword and the set of codewords as the codebook. Many VQ techniques exist such as kmeans [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF], self-organizing maps (SOM) [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF], neural gas (NG) [START_REF] Martinetz | Neural-gas network for vector quantization and its application to time-series prediction[END_REF], growing neural gas (GNG) [START_REF] Fritzke | A Growing Neural Gas Network Learns Topologies[END_REF]. Algorithms such as NG or GNG present good performance in terms of minimization of the quantization error which is measured by the mean squared error. However this performance is often related to the creation in the network of a very large number of new prototypes and/or connections between prototypes, thus inducing a significant increase in computational cost. On the contrary SOM are based on a static underlying topology and a fixed number of codewords (neuron weight vectors). Moreover, in a SOM each prototype has an associated position in a map of a predefined topology (usually a 2D lattice). This spatial arrangement of the prototypes in the map makes it able to capture the topographic relationships (i.e. the similarities) between the inputs, in such a way that similar blocks of samples tend to be represented by spatially close neurons in the map. As a matter of fact, the SOM is a well-known and biologically plausible model of the topographical mapping of the visual sensors onto the cortex [START_REF] Yin | The Self-Organizing Maps: Background, Theories, Extensions and Applications[END_REF].

Kohonen SOM

The neurons of a Kohonen SOM [START_REF] Kohonen | Essentials of the self-organizing map[END_REF] are spatially arranged in a discrete map that usually consists of a two-dimensional grid (see figure 1), or with hexagonal tiling. Each neuron n is connected the input and has a weight vector w n , or codeword, whose dimension is equal to the size of the input vectors (or input dimension).

At the beginning of the learning algorithm, all codewords are initialized with random weights. The training of the SOM lasts several epochs. One epoch includes enough training iterations such that the whole training dataset has been used once for learning. For each training iteration, a training vector v is picked among the inputs. The best matching unit (BMU) g is then found, it corresponds to the neuron with the minimal distance (usually L 2 ) between w g and v. Then the weights of all neurons are updated according to the following equation:

w i (t + 1) = w i (t) + (t) • Θ(σ(t), d i,g ) • (v -w i (t)) (1)
where and σ are time functions (see below for details), and d i,g is the normalized distance between neuron i and the BMU in the map (not in the input space). Θ is a normalized centered Gaussian function with standard deviation σ.

Figure 1 illustrates how a SOM unfolds in the input space (here simply with 2D vector sizes): the codewords that are learned are shown as red points in the input space (from which random inputs are drawn, see blue points), and red links are showing the connections between the direct neighbouring neurons in the map. σ(t) is a parameter that influences the neighbourhood function. The higher it is, the more the BMU influences other neurons. In our experiments, we have set it to start at 0.5 and linearly decrease to a final value of 0.001, so that at the beginning of the training all neurons are significantly influenced by the BMU (unfolding the SOM), and at the end, nearly none except the BMU are (optimizing the quantization). (t) is the learning parameter, it starts at 0.6 and linearly decreases to a final value of 0.05. In our tests, we ran the SOM for 10 epochs.

An iterative batch version of SOM learning exists. Instead of using a single input vector at a time, the whole dataset (batch) is presented to the map before updating any weight [START_REF] Kohonen | The self-organizing map[END_REF]. This algorithm is deterministic, and the limit states of the prototypes depend only on the initial choices. However, this batch version is far less used than the above "on-line" learning version, and it can not be used in the applications where the dataset dynamically evolves. Therefore we will describe and discuss our efficient method to compute the BMU in the context of the standard on-line learning algorithm.

3 Fast-BMU

Algorithm

We present here our new algorithm for searching the Best Matching Unit (BMU) in the SOM. It is traditionally determined by means of an exhaustive search by comparing all the distances between the input vector and the neurons weights. This method, while able to always find the correct minimum of the map, is computationally inefficient. The dimensionality reduction property of the SOM means that close neurons in the SOM topology represent close vectors in the input space. Therefore when an input vector is presented to the SOM, a pseudocontinuous gradient appears in the SOM when considering the distances between the neuron weights and the input vector whose minimum is located at the BMU.

In our algorithm we use this progressive reduction of distances to perform a discretized gradient descent to find the Best Matching Unit. The pseudo-code is shown in Algorithm 1, and illustrated in figure 2 (left). The algorithm starts at an arbitrarily selected position in the map. For this example let us consider that it starts at coordinates (0, 0) (top left corner). This neuron has two neighbours, one to the east (1,0) and one to the south (0,1). We evaluate the distances to the input vector of these three neurons to find the next step in the gradient descent. If the smallest distance is found where we are currently positioned, then we consider this is a local minimum. On the contrary if one of the neighbouring neurons gives the smallest distance, then the gradient descent goes in the direction of this particular neuron, that becomes the next selected position from which we repeat this process until we find a local minimum. In our example the smallest distance is measured for the eastern neuron in (1,0). Thus the search process moves one step to the east, and this neuron has three neighbours, one to the south (1,1), one to the east (2,0) and one to the west that we come from (and thus we ignore it). We compare the three distances again, and move towards the lowest distance (south). This process iterates until it reaches a local minimum at position [START_REF] Huang | A hardwareefficient vector quantizer based on self-organizing map for high-speed image compression[END_REF][START_REF] Fritzke | A Growing Neural Gas Network Learns Topologies[END_REF], where all neighbouring neurons have a higher distance to the input vector than the selected neuron. In order to ensure that the local minimum that has been found is the best one in the local neighbourhood, we then perform a search of the local space by continuing the gradient descent from all directly neighbouring neurons that are still unexplored. If this search finds a better local minimum, then this local minimum is considered as the BMU. This part of the algorithm aims at circumventing problems that may arise from the topology. In a grid topology for instance, we can only look at orthogonal axes. But sometimes, the gradient is oriented towards a diagonal direction, and by extending the search from a local minimum, we are able to still follow this gradient towards a potential BMU.

Another problem that can arise with the particle algorithm is edge effects. When mapping high dimensional data onto a 2D map, the map sometimes become twisted no gradient between the top left neuron and the bottom right neuron. Imagine a net that is thrown onto a ball and nearly completely enveloping it: the shortest path between one corner of the net and the opposite corner of the net does not follow the mesh of the net. If in the learning phase, the Fig. 2. Left: Example of the execution of one particle. Each cell represents one neuron. The arrow in each cell points towards the best neighbour (where a lower distance can be found). A star represents a local minimum. The green colored cells are the neurons who have been explored during the search, and the blue cells are the neurons whose distance to the input has been computed but that have not been explored by the algorithm. After having found a local minimum, new particles are created (in red) and continue the gradient descent by exploring the local neighbourhood. The cell in Yellow is the BMU, and the global minimum of the map. Right: Execution of the four particles.

particle ends up in the wrong corner of the SOM, it will find a terrible BMU and the following weight update will locally break the neighbourhood continuity, and create a negative feedback loop that will remove all dimensionality reduction properties from the SOM. Thankfully there is an easy way to avoid this, by simply starting 4 particles, one in each corner of the SOM, and selecting the smallest BMU found. This technique preserves the continuity of the SOM and makes the Fast-BMU algorithm more robust to local discontinuities in the gradient, especially at the beginning of the training process, when the map is not yet well unfolded. In the case where there is no clear gradient present in the SOM (typically when the SOM is randomly initialized before training), this algorithm will fail to find the correct BMU. However it is not a problem at the start of training as the neighborhood function will create a gradient by unfolding the SOM regardless of which neuron is initially selected. The result of a full Fast-BMU execution is shown in figure 2 (right).

Complexity analysis

The execution time of the Fast-BMU algorithm depends on the shape and size of the neural map, and on the input vector. As our algorithm relies on the dimensionality reduction property of the SOM, we will hypothesise that there is always some kind of continuity in the neural map in our analysis, because if not, our algorithm would not work anyways. In order to estimate the complexity of our algorithm, we have to estimate the number of steps that each of the four particles takes before finding a potential Best Matching Unit (BMU). We assume that: 1) all particles follow paths that do not significantly differ from shortest XY paths until their destination (thus minimizing the number of steps), and 2) they do not stop early in some local minimum (thus maximizing the number of steps). We will call this kind of best-worst-case complexity: Expected Complexity. Let us consider that the BMU is located at position x, y of the SOM :

-The top left particle with coordinates (0, 0) needs x steps in the width dimension, and y steps in the height dimension in order to get to the BMU. -Similarly, the top right particle with coordinates (w, 0) will take w -x steps for the width and y steps for the height. -For the bottom left (0, h), it will be x and h -y steps.

-For the bottom right (w, h), it will be w -x and h -y steps.

To get the total number of steps for one execution, we sum the steps from all particles together as shown in equation 2:

NbSteps = (x + y) + (w -x + y) + (x + h -y) + (w -x + h -y) (2)
The x and y cancel out, and the resulting number of steps only depends on the width and the height of the map. The total number of steps taken by our algorithm is consequently equal to (2w + 2h). We can therefore derive equation 3, which defines the expected complexity of our algorithm.

EC(w

, h) = 2 × (w + h) × N brEvalP erStep (3)
with w, h the width and height of the SOM respectively and N brEvalP erStep the number of new distances to compute on each step of a particle. Its value depends on the topology. It is at most 3 with a grid (4 neighbours minus the neuron from the previous step) and also 3 with a hexagonal topology (6 neighbours minus the neuron from the previous step and 2 neurons that were neighbours of the previous neuron and consequently have already been evaluated).

From an analytical point of view, we can estimate that our Fast-BMU algorithm (EC(w, h) = 6(w + h) in the worst case in a standard grid configuration) is significantly faster than the current exhaustive search algorithm (O(w, h) = wh) when the number of neurons in the map is substantial. For instance, it is twice as fast with 24 by 24 SOMs, and 10 times faster with 120 by 120 SOMs. An experimental evaluation of the speed difference is reported in section 5.

Experimental Setup

To evaluate the robustness of our algorithm with various kinds of data, we have selected 6 datasets aimed at being representative of the kind of data SOMs are usually trained on. For the 2D case, we have generated data with different properties (uniform distribution and a highly non-convex shape), for 3D data we use a uniformly distributed cube shape and the pixel color values of an image. For the high dimensional case, we consider an image compression application [START_REF] Amerijckx | Image compression using self-organizing maps[END_REF] with 10 by 10 sub-images as training vectors (100 pixels with 3 colors each, resulting in 300 dimensions), and the Free Spoken Digits Dataset [START_REF] Jackson | Jakobovski/freespoken-digit-dataset[END_REF] which uses soundwaves that we have reduced to 1000 dimensions.

Our algorithm is mostly designed for a 2 dimensional SOM, although adaptations to higher dimensions can be easily defined by just adapting the neighbourhood and the number of initial particles, even leading to possibly greater gains in computational cost. We tested it with a grid and a hexagonal shaped 2D topology, which are the most commonly used in SOM applications.

In order to evaluate the differences between all tested models, we used three metrics. The first one is the standard Mean Squared Quantization Error (MSQE) which estimates the Vector Quantization quality of the tested algorithm. The Mean Squared Distance to Neurons (MSDtN) which computes the average squared codeword distance between neurons and all of their direct neighbours. The lower this value is, the more closely related neighbouring neurons are, and the better the dimensional reduction property is. Numerous metrics exist in the SOM literature to estimate the topographical mapping of the SOM, but MSDtN has the advantage of being easy to compute, without parameters and only dependent on the neurons weights. For all metrics, lower is better.

MSQE = 1 V V i=1 ||v i -w bmu(i) || 2 (4) MSDtN = 1 N N i=1 N j=1 ||w i -w j || 2 , if dist(i, j) = 1 0, otherwise (5)
With V the number of vectors in the dataset, v i the weights of the i th vector of the dataset, and bmu(i) is the index of the neuron which is the best matching unit for the i th vector of the dataset. Similarly N is the number of neurons and w i the weights of the i th neuron, while dist(i, j) is the number of links in the shortest path between neurons i and j in the neural map.

Results

In this section, we explore the differences in quality of learning and recall between the standard version and our fast version for the computation of the BMU in a SOM. We also look at the practical differences in the amount of computations required for the two versions and we compare it with the previously presented complexity analysis. Quality tests were performed on a 32 × 32 SOM (1024 neurons). For each combination of dataset and model (choice of topology and BMU algorithm), we ran 50 executions with different random seeds which affect the datasets that are generated, the initialization of the neuron weights (who are all randomly initialised with no pre-existing gradient) and the order in which the training vectors are presented. Results are shown in table 1.

The algorithm column of the table shows the combination of BMU finding algorithm and topology that was used for training. The MSDtN (see section 4) is calculated on the trained neurons weights. The MSQE S (Standard) is the Table 1. Results with a 32x32 neurons SOM, averaged over 50 executions. The Algorithm column specifies with which algorithm and topology the SOM was trained, FastG and FastH stand respectively for Fast Grid and Fast Hexagonal. MSQE S is the MSQE calculated with the standard (exhaustive) BMU algorithm whereas MSQE F uses the Fast-BMU version. Differences of MSQE S between different algorithms reflect the quality of the training phase. The mismatch is the proportion of BMU that are differently selected by the two algorithms.

Data Algorithm MSDtN MSQE S MSQE F Mismatch

Experimental results

We first observe that the distance between neurons after learning (MSDtN) is lower with the grid topology than with the hexagonal one, but this difference could be attributed to the different number of neighbours between the two topologies and therefore should only be used to compare the standard and Fast-BMU algorithms, and not topologies. We also remark that the Fast algorithm does not make any significant mismatch on the Square and Shape datasets, and therefore MSQE S and MSQE F have similar recall results on these datasets.

The mismatch percentages vary greatly between the datasets. From 0 to 6% for the Images and Colors Datasets, 3 to 10% for the Cube and 13 to 33% for the Spoken Digits dataset. Such differences could be explained by the distribution of the data in the datasets, as Images and Colors feature data that are closely related together. In pictures for instance, there are usually a few dominant colors with a lot of color gradients that make the continuities in the distribution easier to learn for the SOM, thus improving the performance of our Fast-BMU algorithm. The Spoken Digits dataset on the other hand has high mismatch values, which seems to indicate that a strong continuity in the neurons weights is not present after learning the SOM. The hexagonal topology also performs better with the Fast-BMU algorithm than the grid topology as mismatches are significantly lower with it. Finally the dimensionality of the dataset does not seem to play a key role here, as the Image dataset (300 dimensions) has lower mismatches than the Cube dataset (3 dimensions).

For the vector quantization part, the hexagonal topology leads again to the lowest error values. What is more surprising is that the Fast-BMU version has quantization results that are very similar to the standard version. Even with high mismatches (30% with Digits using a grid-based SOM) the MSQE is only around 5% higher, and even less when only training is compared. The only significantly higher MSQE values with Fast-BMU is with the Cube dataset where the algorithm selects quite bad BMU choices in the recall phase while being able to correctly train the SOM. In most cases, a difference in the topology of the SOM has more impact on the resulting MSQE than the use of the Fast-BMU algorithm.

Computational gains

To evaluate the computational gains that are induced by the use of the Fast-BMU algorithm independently from implementation techniques, we compared the percentage of neurons that must be evaluated in order to find the BMU. The results are shown in figure 3. The standard SOM is evaluating all neurons by definition, so the percentage is always 100%. The complexity curve for Fast-BMU plots the function defined in section 3.2. To obtain the Fast-measured curve, we ran tests with n × n SOM, where n is every even number between 10 and 50 (21 tests in total). Each test featured all datasets and all topologies (so 12 executions per test). With these results, we can observe significant improvements in the required computational time. Our algorithm is twice as fast with (16 × 16) Number of neurons in the map Percentage of evaluated neurons per iteration Fig. 3. Evaluation of performance gains with the number of neurons. All results were calculated on square maps. The blue line is the standard SOM, in green is the analytical value and in red the measured value. Additionally, the purple dots are the percentage of correct BMU in an execution on the Image dataset.

SOMs, four times faster with 1000 neurons (32×32). The (50×50) SOM evaluates approximately 375 neurons per iteration, which is similar to the 400 neurons a standard (20×20) SOM has to evaluate. We can also observe that the complexity curve follows a similar shape to the measured curve, while overestimating the required number of evaluated neurons by approximately 75%.

Conclusion

We have presented a novel method to find the Best Matching Unit in Self-Organizing Maps by taking advantage of their ability to preserve their underlying topology within the codebook. Our algorithm is significantly faster to compute while performing barely worse than the standard approach in vector quantization. This result makes SOM with a high number of neurons a more viable solution for many applications. We expect future improvements of this algorithm, or new approaches to further reduce the computational cost of SOM by modifying the BMU searching algorithm. We also study how the Fast-BMU approach can reduce the bandwidth demands in a fully parallel implementation on a manycore substrate, where all neurons are simultaneously evaluated but the BMU selection uses the simple unicast propagation of particles instead of full broadcast-reduce schemes. Finally it must be pointed out that the computational gains offered by our Fast-BMU algorithm specifically rely on preservation of neighbourhood relations when mapping the input space onto the neural map. This property is not present when using more conventional VQ models such as k-means, so that the use of SOM could be extended to more applications where their specific mapping properties would not be useful for the application itself, but would induce potential computational gains out of reach for other models.

Fig. 1 .

 1 Fig. 1. Top : Typical SOM architecture. Bottom : A Kohonen SOM learning uniformly distributed random data in [0, 1] 2 .

  Algorithm 1 Particle Input: pos : current position Parameters: values: global table of distances, eval: global history of evaluations Output: bmu : best matching unit's index 1: if eval(pos) is True then 2: return pos 3: end if 4: eval[pos] ← -True 5: Let new pos take the index of the closest not evaluated neighbour to the input vector (ignoring neighbours p such that eval(p) =True) 6: if values[new pos] ≤ values[pos] then 7: return Particle(new pos) 8: end if 9: return The index of the smallest value between pos and the returned indexes by execution of Particle() on all direct neighbours of pos.

  Comparing the different MSQE S values for a standard version and a fast version gives an indication of the influence of the Fast-BMU algorithm on training quality only, as it always selects the real BMU in the recall phase. The MSQE F (Fast) metric measures the vector quantization error with the BMU selection done by the Fast-BMU algorithm. If the training was performed on the standard SOM, it gives an indication of the influence of the Fast-BMU algorithm on recall accuracy only; if it was trained on a Fast version, it represents the MSQE result of a SOM that only uses the Fast-BMU algorithm. The mismatch column gives the proportion of BMU that are selected differently by the two algorithms.

	Square Grid	1.94e-4 2.22e-4 2.22e-4	0%
	FastG	1.93e-4 2.23e-4 2.23e-4	0%
	Hex	2.39e-4 2.12e-4 2.12e-4	0%
	FastH	2.38e-4 2.15e-4 2.15e-4	0%
	Shape Grid	1.38e-4 1.40e-4 1.40e-4	>0%
	FastG	1.38e-4 1.40e-4 1.40e-4	>0%
	Hex	1.65e-4 1.31e-4 1.31e-4	>0%
	FastH	1.65e-4 1.31e-4 1.31e-4	>0%
	Cube Grid	4.48e-4 2.21e-3 2.50e-3	4.8%
	FastG	4.61e-4 2.25e-3 3.21e-3	9.8%
	Hex	5.29e-4 2.09e-3 2.34e-3	3.1%
	FastH	5.38e-4 2.11e-3 2.79e-3	7.6%
	Colors Grid	1.15e-4 8.64e-5 8.80e-5	4.4%
	FastG	1.19e-4 8.91e-5 9.08e-5	5.4%
	Hex	1.33e-4 8.29e-5 8.30e-5	0.4%
	FastH	1.35e-4 8.26e-5 8.29e-5	0.7%
	Digits Grid	2.02e-4 1.42e-2 1.49e-2	31.3%
	FastG	1.93e-4 1.44e-2 1.51e-2	32.2%
	Hex	2.29e-4 1.41e-2 1.45e-2	19.8%
	FastH	2.25e-4 1.42e-2 1.45e-2	13.3%
	Image Grid	1.64e-4 1.80e-3 1.83e-3	4.2%
	FastG	1.65e-4 1.82e-3 1.85e-3	4.4%
	Hex	1.97e-4 1.75e-3 1.77e-3	1.2%
	FastH	1.99e-4 1.75e-3 1.76e-3	1.2%
	quantization error in the recall phase (after learning) when using the standard
	BMU algorithm.

Acknowledgements :

The authors thank the French AID agency (Agence de l'Innovation pour la Défense) for funding the DGA-2018 60 0017 contract. The code is available at github.com/yabernar/FastBMU.


Yann Bernard
email: yann.bernard@loria.fr

Nicolas Hueber
email: nicolas.hueber@isl.eu

Bernard Girau
email: bernard.girau@loria.fr

Novelty Detection in Images Using Vector Quantization with Topological Learning

Keywords:

Novelty detection is a key component of biological vision systems, where its role is to extract critical elements for the agents survival from the massive amount of information present in his visual environment. Current vision based embedded systems, such as surveillance cameras, are facing similar challenges as they have to handle a significant amount of sensory data, with limited computing power and memory bandwidth available. In order to perform artificial novelty detection in these systems, it is necessary to have a model able to learn the local visual environment without having any prior knowledge. This study explores bio-inspired unsupervised neural networks models, more precisely self-organizing maps, which are good candidates for this task. We present an original approach consisting of performing novelty detection based on vector quantization and topological learning.

I. INTRODUCTION

A. Novelty Detection

Apart from being an important feature of the human visual cortex, novelty detection has been widely studied in machine learning for its usefulness in many applications like cybersecurity, healthcare, damage detection and video surveillance [START_REF] Marco | A review of novelty detection[END_REF]. The principle relies on defining a set of data that will be considered as "normal" and where the novelty detection model is trained on. The model is then given the task to discriminate for any new datapoint if it is part of the "normal" class or if it is a new element (an outlier). It should be noted that there is no objective way to discern between an outlier and a "normal" datapoint, therefore what is considered "new" is always subject to interpretation, i.e. how close it has to be to the normal data to be included in it.

In this paper, we are interested in visual novelty detection for embedded systems, with video surveillance as target application. The challenges with this application are the high dimensionality of the data (images), the naturally high variability in the background and the requirement to precisely locate the novelty in the images. This task has the advantage of having a complete and well maintained dataset available called CDNET2014 [START_REF] Wang | CDnet2014: An Expanded Change Detection Benchmark Dataset[END_REF].

The authors thank the French AID agency (Agence de l'Innovation pour la Défense) for funding the DGA-2018 60 0017 contract.

B. Topological vector quantization

Vector quantization (VQ) is a technique that aims at representing a dataset with a codebook. Each codeword in the codebook is representing a cluster of similar datapoints in the dataset. The codebook can then be used to perform clustering or data compression. The positions of the codewords in the input space are generally found during a competition-based training (as in k-means for instance).

Topological learning algorithms are models that are able to create a topology from their codebook. The topology is a network that connects codewords based on their proximity to each other, so that neighbouring codewords in the topology are also close together in the input space.

Models like self-organizing maps (SOM) [START_REF] Cottrell | Villa-Vialaneix, Self-Organizing Maps, theory and applications[END_REF] and growing neural gases (GNG) [START_REF] Fritzke | A Growing Neural Gas Network Learns Topologies[END_REF] and their variants are able to both perform VQ and create a topology that defines neighbourhood relationships between their codewords. The self-organizing map starts with a fixed topology (usually a 2D grid) and "projects" the dataset on this topology during learning. For growing neural gases, the topology is created in the learning phase, so that the neural gases topology closely mimics the datasets shape in the input space. In this paper we will present our novelty detection methods for self-organizing maps, but which could also be applied to all models that perform both vector quantization and topological learning.

Many variants of the SOM exist in the literature. One version of particular interest here is the Cellular SOM [START_REF] Girau | Cellular Self-Organising Maps -CSOM[END_REF]. In addition to its faster convergence time, it is designed to take into account hardware constraints. Using a cellular computing approach, CSOM can be efficiently implemented into embedded systems as CSOM neurons only need to interact with immediate neighbouring nodes, thus inducing the potential of massively parallel and scalable computing. The methods of novelty detection presented in this paper are compatible with CSOM and they can be combined into an efficient SOM based novelty detection in embedded systems.

In the following sections, we will present how SOMs work, and how to learn from images. Then we will present two methods for novelty detection in images, one using VQ by SOM, and the other the SOM's topology. We will finish with experimental results, and a discussion about further work.

II. SELF-ORGANIZING MAPS A. Learning algorithm

A self-organizing map is a discrete map that spatially arranges neurons (or nodes), usually in a two-dimensional grid. Each neuron n is also connected to the input and has a weight vector w n , or codeword, whose dimension is equal to the input dimension. First, all codewords are initialized with random weights. The training of the SOM lasts a certain number of epochs (100 in our case). One epoch includes enough training iterations such that the whole training dataset has been used once for learning. For each training iteration, a training vector v is picked among the inputs. The best matching unit (BMU) g is then found, it corresponds to the neuron with the minimal L 2 distance between w g and v. Then the weights of all neurons are updated according to the following equation:

w i (t + 1) = w i (t) + (t) • Θ(σ(t), d i,g ) • (v -w i (t)) (1)
with d i,g is the normalized distance between node i and the BMU in the topology (not in the input space). Θ is a normalized centered Gaussian function with standard deviation σ(t). σ(t) is a parameter that influences the neighbourhood function. The higher it is, the more the BMU influences other neurons. In our experiments, we have set it to start at 0.5 and linearly decrease to a final value of 0.001, so that at the beginning of the training all neurons are significantly influenced by the BMU (unfolding the SOM), and at the end, nearly none except the BMU are optimizing the quantization.

(t) is the learning parameter, it starts at 0.6 and linearly decreases to a final value of 0.05.

B. Learning images

The SOM has first to learn its visual environment, or the scene background in order to perform the novelty detection. The background can be represented by an image, or a sequence of images considered as the "usual" visual environment. These images first have to go through a tiling, or mosaic, process before learning or reconstruction by the SOM. Each image is tiled into smaller sub-images with a parametrable size usually ranging from 5 by 5 pixels to 30 by 30 (all sizes being square for convenience). These sub-images are meant to represent local features of the image. They are then flattened into vectors and used as the input data for the SOM. For instance a 420 by 360 image with 20 by 20 sub-images will be tiled into 378 sub-images (18 rows and 21 columns), and generate the same amount of input vectors for the SOM with sizes of 400 (20 × 20) if it is a grayscale image, or 1200 if it is RGB.

Once we have those input vectors, we can train the SOM in the usual way. This will result in the SOM's codewords being a representation of the features of the learned image. Once trained, the learned image can be reconstructed with only the codebook, and the list of the best matching unit indices associated to each sub-image location. By replacing each sub-image by the codeword of its the best matching unit, we obtain a reconstructed version of the image. This process is commonly used in lossy image compression with self-organizing maps [START_REF] Amerijckx | Image Compression using self-Organizing Maps[END_REF]. III. NOVELTY DETECTION WITH VECTOR QUANTIZATION Fig. 1. The process of novelty detection with vector quantization. The SOM is shown with all their codewords put together at their topological places. We can observe that there has been two changes between the background and the perceived image : a plane has appeared and the clouds have moved. The clouds, already present in the background are well reconstructed, the plane however is new, and is not well reconstructed, therefore the difference between the perceived image and the reconstruction highlights the plane more than the clouds (contrary to a simple difference between background and perceived image, where both would be prominent).

In this section, we present the first unsupervised novelty detection method explained with more details in [START_REF] Bernard | Novelty detection with self-organizing maps for autonomous extraction of salient tracking features[END_REF]. In order to perform novelty detection with vector quantization, we use the difference between the sub-images of the new image from the sensor and the corresponding best matching unit codewords found in the codebook of the SOM learned on the background image. There are two cases to consider; either the new image from the sensor is similar to any portion of the trained background, or something new is present in the image. In the first case, by reconstructing the new image with the previously trained SOM and comparing it with the new image, the learned codewords should be close to the new image's sub-images (especially if the camera is static). Therefore the difference between the new image and the reconstructed image should be minimal (but still present because of lossy compression and natural changes in the visual environment). However in the second case, we expect the image to be well reconstructed except where the novelty appeared. Because the novelty is by definition something that was not in the background and therefore something that the SOM has not learned. Consequently the sub-images where the novelty is present should be far from their best matching unit's codeword. This in turn will lead to a significant difference when performing the difference between the new image and the reconstructed new image at the place of the novelty. This process is shown in figure 1. This process has the advantage of being precise at the pixel level in highlighting changes, and location independent for novelty detection. However it can be noisy due to imperfect VQ learning and natural variability in the environment.

IV. NOVELTY DETECTION WITH TOPOLOGY

The new approach we propose is based on the topological properties of the learned map to find novelty in an image. We presented in section I-B how topology links the different codewords of the SOM codebook together by closeness: close neurons in the map topology learn similar codewords. We can use this property to detect novelty in a complementary manner to the method we have described above.

After learning the SOM, we memorize the list of the positions in the map of the best matching units found for all sub-images. When a new image is presented from the sensor, we perform the reconstruction process as in the first novelty detection method, but we are also interested in the list of positions in the map of the best matching units found for all sub-images of the new image. By comparing the two lists we can find changes in the selected BMU positions (in the map) for each sub-image location (in the image). If the BMU is the same between the background and the new image at one location, then there is probably no novelty at this place. If there is a difference in the two BMUs, then there may be some novelty at this position. To quantify the difference between the two BMUs we can compute the topological distance between them in the map. The topological distance is defined by the number of nodes that are crossed in the shortest path between the two BMUs in the map topology. In the classical grid-based SOM, it is simply the L1 distance.

With theses distances we can create a saliency map where high distances in the topology mean significant changes in the image, because closeness in the topology means closeness in the input space. This method results in a more robust saliency map, with less level of "noise". But contrary to VQ novelty, the precision is limited to the sub-images size and there is no inhibition of already known elements that have moved. The process is shown in figure 2.

V. EXPERIMENTAL EVALUATION

A. Combination of VQ and Topology Novelty detection

The two above methods have different and complementary properties in their novelty detection. We combined them to obtain the result we show in this section. The combination works by normalizing the two issued saliency maps and multiplying them together to obtain the final saliency map. This straightforward operation does not require any hyperparameter. Furthermore the new fused model architecture is computationally efficient as it shares the same SOM codebook and the same reconstruction.

B. Experimental protocol

Experiments were performed on the CDNET14 database. It is featuring a varied number of situations and environments that are particularly challenging for novelty detection. We removed three categories from the dataset (Pan Tilt Zoom, low FPS and Intermittent object motion) because one or more of their videos featured a behavior that is not compatible with our novelty detection task (i.e. where the object to be detected is already present at the start of the sequence and part of the background). We generated a background image for each video by computing the median pixels of the sequence so that the model is trained without perturbations from the targets.

For each video, we used a single 20 by 20 SOM with 20 by 20 sub-images. The saliency map generated by our model is binarized with a threshold at 10 (all pixels over 10 are positive). These values were set after optimizing for the global best F-measure. It should be noted that there is a lot of variability between the videos, and optimizing those parameters for each video can lead to a significant performance improvement (for instance some pedestrian videos have better results with smaller sub-images, while other car heavy videos work best with bigger sub-images). Measured results on the different categories of CDNET are shown in table I and figure 3 shows the results of our novelty detection on different examples. F-measure is a metric regrouping precision (number of true positives over all positives) and recall (number of true positives over true positives and false negatives) with the following formula:

C. Results on CDNET's change detection dataset

F-measure = (2 × Precision × Recall) Precision + Recall (2)
The values displayed in table I are an average result of 10 runs. Therefore the F-measure shown may seem inconsistent with the precision and recall values and equation 2, as the average F-measure is different from the F-measure of the averages of precision and recall.

We can observe that precision is always the limiting factor of performance, especially in the Dynamic background and Turbulence categories. Both of these having significant and continuous variations from the initial background, which in turn causes a lot of false positives (as shown in figure 3). Recall is ranging from 40% to 65%, which seems to indicate that approximately half of the pixels that should be positive are found. However, the objects that we are able to detect often are not completely overcast, and with a lot of black spot inside detected objects. This implies that we actually detect more objects than what the recall indicates, as some part of false negatives result from already detected objects that are not well detoured. the groundtruth and (c) our model. We can see the sub-images we use in our novelty detection appear in the resulting saliency map, which gives it its "blocky" look. The novel objects are mostly detected although some of their parts are missing. We can also observe that the model struggles when the background is too changing.

VI. CONSIDERATIONS FOR EMBEDDED SYSTEMS USE

Self-organizing maps are known for their high computational cost, most of it coming from the search for the BMU where all neurons in the map have to be evaluated. However SOMs are naturally parallelisable, and it is thus possible to drastically reduce the time necessary for an iteration. Recent developments presented in [START_REF] Girau | Cellular Self-Organising Maps -CSOM[END_REF] show that the use of a cellular computing approach can lead to significant benefits for embedded SOMs, like faster convergence time which in turn makes online learning much more feasible. In CSOM, when the BMU is identified, weight updates propagate in a cellular way from the BMU so that each neuron is "influenced" by the weight vector of a neighbouring neuron that has been updated before, instead of getting closer to the input vector. Current versions of CSOM are cellular and parallel: several input vectors are simultaneously learned, each cellular weight update process being initiated at the level of the corresponding BMU. The hardware device targeted by CSOM is a multi-FPGA Selfconfigurable Cellular Adaptive Platform (SCALP) [START_REF] Vannel | SCALP: Self-configurable 3-D Cellular Adaptive Platform[END_REF].

In [START_REF] Bernard | A fast algorithm to find Best Matching Units in Self-Organizing Maps[END_REF], the authors are presenting an algorithm for searching the BMU with the help of the SOMs topological continuity with a lower complexity than the traditional exhaustive search. The principle is to follow a path from any neuron to the BMU by "descending" the computed distances between the input and each neuron weight vector. A similar approach can be used in a cellular way for our application, as inspired by CSOM: several sub-images (input vectors) can be handled simultaneously, sent in a unicast way to the corresponding stored BMU for the initial background image, and each BMU initiates a descending path towards the BMU of the corresponding subimage in the new image. Following this approach, several topological distances (length of the descending paths) can be computed simultaneously, and with a minimized risk of communication bottlenecks.

VII. CONCLUSION

We have presented an original approach to novelty detection using both vector quantization and topological learning properties of SOMs. Contrary to typical change detection algorithms, these methods rely exclusively on unsupervised learning and are able to perform without any prior knowledge. Our methods could also be applied to any model performing both vector quantization and topological learning like growing neural gases and its variants. However further improvements and the addition of post-processing are needed in order to match state of the art performance on this application (which can be found on CDNET's website). Further work in improving the hardware implementation of SOMs and cellular computing would benefit our approach, potentially leading to a completely cellular embedded system performing novelty detection and that could be used as a base to more complex bio-inspired visual processing.

Fig. 2 .

 2 Fig. 2. Topological novelty detection. The process shown here is for one position in the image, and it is repeated on the whole image.

Fig. 3 .

 3 Fig. 3. Results on different scenarios from CDNET. (a) is the input, (b)the groundtruth and (c) our model. We can see the sub-images we use in our novelty detection appear in the resulting saliency map, which gives it its "blocky" look. The novel objects are mostly detected although some of their parts are missing. We can also observe that the model struggles when the background is too changing.