Repositorio Institucional de Documentos

2014 25 Enrique Pelayo Campillos Magnitude Sensitive Competitive Neural Networks Departamento Director/es Ingeniería Electrónica y Comunicaciones Buldain Pérez, Julio David Orrite Uruñuela, Carlos Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Enrique Pelayo Campillos MAGNITUDE SENSITIVE COMPETITIVE NEURAL NETWORKS Director/es Ingeniería Electrónica y Comunicaciones Buldain Pérez, Julio David Orrite Uruñuela, Carlos Tesis Doctoral Autor 2014 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Magnitude Sensitive Competitive Neural Networks By Enrique Pelayo Campillos Dissertation presented to the Department of Departamento de Ingenier´ıa Electr´onica y Comunicacionesin partial fulfillment of the requirements for the degree of Doctor of Philosophiae PhD Advisors: David Buldain P´erez Carlos Orrite Uru˜nuela (Co-director) At Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza, 2014 Abstract Competitive Learning is a kind of unsupervised learning commonly used to find a solution to the approach of Vector Quantization (VQ) task. VQ tries to generate a reduced representation of the vector-data distribution used in its training process. There are many Competitive Learning algorithms, but most of them share the property of distributing their centroids over the data with a density proportional to the probability density function of the data. That results in modeling representations that tend to concentrate centroids in the densest areas of the data distribution. However, some quantization applications may require an inverse relation between the codewords density and the data density, as in many biological systems. It is not just that, sometimes it is required a codeword distribution independent of data density. In this Thesis it is presented a set of Neural Networks called Magnitude Sensitive Competitive Neural Networks (MSCNNs). They are a set of neural competitive learning algorithms, that include a magnitude term as a modulation factor of the distance used for the unit competition. As other competitive methods, MSCNNs perform a vector quantization of the data, however the magnitude factor leads centroids to represent with higher detail any desired zones, defined by this factor. This distribution is improved with the use of independent learning factor for each unit, calculated form the magnitude, as it will be explained in the description of the algorithms. Two MSCNNs neural networks are developed: MSCL (Magnitude Sensitive Competitive Learning) a hard competitive algorithm, and MS-SOM (Magnitude Sensitive Self Organizing Maps) a soft competitive algorithm, that shares with MSCL its capability of allocating centroids in data-distribution zones according to an arbitrary magnitude, but additionally preserves topological information of the data. Both algorithms are analysed, as well as their ’masked’ versions (implementation that may be trained with data samples 2 3 containing invalid components). MS-INITis a new codebook initialization algorithm, developed as a generalization of the known KKZ and K-Means++, but taking into account the magnitude. MSCL, MS-SOM and MS-INIT(in their different implementations) were compared with other vector quantization approaches in several examples of interpolation, image color quantization, surface modelling, classification, and some simple artificial examples. Additionally it is presented a new image compression algorithm, MSIC (Magnitude Sensitive Image Compression) that make use of these new algorithms, and achieves a level of compression different along the image according to the user defined magnitude. Results show that the new MSCNNs are more versatile than other competitive learning algorithms in certain tasks, and present a clear improvement in vector quantization over them when data is weighted by a magnitude that marks the ’interest’ of each sample. Resumen El aprendizaje competitivo (Competitive Learning, CL) es un tipo de aprendizaje no supervisado que se usa habitualmente para encontrar una soluci´on al problema de cuantificaci´on vectorial (Vector Quantization, VQ). En este tipo de tareas el problema consiste en conseguir una representaci´on reducida de la distribuci´on de datos de entrada usada en el proceso de entrenamiento. Hay muchos tipos de algoritmos de competitivo, pero la mayor´ıa de ellos comparten la propiedad de distribuir sus centroides sobre los datos con una densidad proporcional a la funci´on de densidad de probabilidad de los datos. Como resultado, los centroides se concentran en las zonas m´as densas de la distribuci´on de datos. Sin embargo, algunas aplicaciones de cuantizaci´on de datos requieren una relaci´on inversa entre la densidad de los datos y de los centroides, como sucede en muchos sistemas biol´ogicos. Y no solo eso, algunas veces se requiere una distribuci´on que sea totalmente independiente de los datos. En esta Tesis se presentan un conjunto de redes neuronales llamadas: Magnitude Sensitive Competitive Neural Networks (MSCNNs). Se trata de un conjunto de algoritmos de Competitive Learning que incluyen un t´ermino de magnitud como un factor de modulaci´on de la distancia usada en la competici´on. Al igual que otros m´etodos competitivos, MSCNNs realizan la cuantizaci´on vectorial de los datos, pero el t´ermino de magnitud gu´ıa el entrenamiento de los centroides de modo que se representan con alto detalle las zonas deseadas, definidas por la magnitud. Esta distribuci´on de las unidades se mejora con el uso de un coeficiente de aprendizaje independiente para cada unidad, calculado a partir de la magnitud, tal y como se explicar´a a lo largo de la descripci´on de los algoritmos. Se han desarrollado dos redes neuronales de tipo MSCNN: MSCL (Magnitude Sensitive Competitive Learning), algoritmo de tipo ’hard competitive’ y MS-SOM (Magnitude Sensi4 5 tive Self Organizing Maps), un algoritmo donde la competici´on es de tipo ’soft competitive’, que comparte con MSCL su capacidad de ubicar centroides en determinadas zonas de la distribuci´on de datos de acuerdo a una magnitud arbitraria, pero adicionalmente, consigue mantener mantener en el mapa de la red neuronal las propiedades topol´ogicas de los datos. En la Tesis he desarrollado y estudiado en profundidad ambos algoritmos, y sus versiones ’enmascaradas’ (Estas versiones permiten que el entrenamiento se realice con muestras que incluyen alguna componente inv´alida). Tambi´en se muestra un nuevo algoritmo de inicializaci´on del codebook, MS-INIT, que es una generalizaci´on de los conocidos KKZ and K-Means++, pero teniendo en cuenta la magnitud. MSCL, MS-SOM y MS-INIT(en sus distintas implementaciones) se comparan con otros algoritmos de cuantizaci´on vectorial en diversos ejemplos de interpolaci´on, reducci´on de color, modelado de superficies, clasificaci´on, y varios ejemplos sencillos de demostraci´on. Adem´as se introduce un nuevo algoritmo de compresi´on de im´agenes, MSIC (Magnitude Sensitive Image Compression), que hace uso de los algoritmos mencionados previamente, y que consigue una compresi´on de la imagen variable seg´un una magnitud definida por el usuario. Los resultados muestran que las nuevas redes neuronales MSCNNs son m´as vers´atiles que otros algoritmos de aprendizaje competitivo, y presentan una clara mejora en cuantizaci´on vectorial sobre ellos cuando el dato est´a sopesado por una magnitud que indica el ’inter´es’ de cada muestra. Dedicatoria Por tu bondad y sacrificio me inspiraste a ser mejor y ahora puedo decir que esta tesis lleva mucho de t´ı, gracias por estar siempre a mi lado, Gloria. 6 Contents 13 B.3 The magnitude function .............................163 B.3.1 Use of the magnitude function .....................163 B.3.2 List of magnitude function examples ..................166 B.4 Demos .......................................166 Bibliography 167 List of Figures 2.1 Competitive neural network architecture ................... 33 3.1 Architecture of the MSCL neural network using two alternative definitions of the magnitude function: a) as a magnitude map evaluated into units, or b) as an external magnitude vector associated to data patterns. . . . . . . . 42 3.2 MSCL flowchart ................................. 44 3.3 Example of Voronoi regions corresponding to 30 units. (a) Centroids and magnitude, abs(x2). It can be appreciated how the density of centroids increases as x2becomes higher, as higher magnitude zones attract more units to be represented. (b) Voronoi sets of each unit: Samples assigned to centroids using distance weighted by magnitude defined in a, (c) Voronoi regions for Euclidean distance, (d) Voronoi regions for distance weighted by magnitude defined in a.............................. 50 3.4 Example of representation of a trained MSCL with connections obtained after training. ................................... 51 3.5 Evolution of WMSE (black) and normalized Weighted Entropy (red) during training of a MSCL with 50 units along 5 cycles of 10 epochs each. As expected, WMSE decreases during training, while the normalized Weighted Entropy tends to a constant value of 1. ..................... 53 3.6 Effect of the value of γduring training a MSCL. Higher values enhance the importance of the magnitude during competition. In the figure we represented the following values for it: (a)γ= 0, (b)γ= 0.2, (c)γ= 1 (normal situation) and (d)γ= 5. Units are colored according the value of mum(t)γ (black means near zero values, and red the highest one). ........... 56 14 List of Figures 15 3.7 Analysis of the MSCL behavior for different K values in networks with 50 units. Three magnitude functions were explored: first row of graphs shows results for MSCL with magnitude in equation 3.26 (absolute value of x2), second row of graphs show MSCL emulating FSCL, and the third row shows results for MSCL with Q-error. Graphs show the averaged final values (wide blue line) of the quality measures (WMSE, Entropy and DB-index) and the standard deviation values (narrow blue lines). The networks were simulated 10 times for averaging and were trained along 10 cycles with the syntheticGaussian problem. Horizontal coordinate is the value of K used in each experiment. It is clear that K=2 shows the most reasonable behaviour, and if K is too high (K=50), the behavior becomes unstable. .......... 58 3.8 Example of representation with 80 units (trained with MSCL for mean Qerror as magnitude function) used to estimate the data density. The centred black points indicate the units corresponding to the dense-zone codewords (ωdense), while the rest unit prototypes are assigned to the sparse-zone codewords (ωsparse). The color bar represents the normalized-density (magnitude) values. ................................... 60 3.9 Gaussian example. Resulting representations of MSCL for contraction magnitude functions are shown in figures aand b, MSCL with expansion magnitude functions in cand dMSCL with Q-err in fand FSCL in figure e. The color bar represents the magnitude values assigned to the units. Black points represent the initial codebook for density estimation of the data, separated by Otsu method into dense (shown in figures band c) and sparse (shown in figures aand d) sub-representations. Contract1 and Expansion1 (aand c) present magnitude functions that force units to avoid the corresponding black points. Contract2 and Expansion2 (band d) present magnitude functions that force units to approximate to the black points. . . . . . . . 61 3.10 Evolution along training process during 50 cycles of the averages in 30 simulations of the DB-Index, Normalized Entropy and Weighted Mean Squared Error. The left column shows the evolution for methods: MSCL with Qerror, FSCL, FCM, NG, SOM and K-means. The right column shows also MSCL with Q-error and K-means as comparison, with the results for the different MSCL in contract-expansion examples. ............... 64 List of Figures 16 3.11 Interpolation example showing the FSCL and MSCL representations of the data series. The red line represents the magnitude value along the data series. FSCL does not represent the data in the high frequency perturbation as well as MSCL. ................................ 67 4.1 Gaussian example. (a) U-matrix and Magnitude map of MS-SOM using MF4as magnitude function. (b) Trained SOM. MS-SOM trained with MF1 (c), with MF2(d), with MF3(e) and trained with MF4(d). . . . . . . . . 74 4.2 Classification results for MS-SOM. Iris example: (a)map with colours depending on the classes for each unit (interpolating colours mean that a unit has samples from different classes), (b) map with the final assigned class for each unit, and (c) magnitude associated to each unit (clearer grey means higher magnitude). In this representation, the map size (10x6 units) was bigger than the one used in the comparative to highlight the value of the magnitude in zones of high class confusion. Glass example: (d)Results of training a (17x11) grid with SOM. (e) Corresponding results of MS-SOM. . 79 5.1 Dataset matrix (left) and corresponding mask(right). This dataset corresponds to the three 3D Gaussian distributions. Mask matrix indicates valid components of each sample (in white), or invalid (30% of components, in black). ....................................... 85 5.2 Final results of a trained MSCL with 10 units using two magnitude functions. On top, row figures represent direct training without taking the mask into consideration. Bottom shows masked version of MSCL (using mask shown in figure 5.1). Left column uses constant magnitude function equal to one. Right column uses as magnitude function the absolute value of first component of each sample. ........................... 86 5.3 Final results of a trained MS-SOM with 10 units using two magnitude functions. On top, row figures represent direct training without taking the mask into consideration. Bottom shows masked version of MS-SOM (using mask shown in figure 5.1). Left column uses constant magnitude function equal to one. Right column uses as magnitude function the absolute value of first component of each sample. ........................... 88 List of Figures 17 6.1 (a) Dataset used in the examples of this chapter (with color coding according to the magnitude associated to each sample) and codebooks of 80 units initialized with the different methods: (b) Random init, (c) KKZ algorithm, (d) Kmeans++ algorithm, (e) MS-INITmax algorithm and (f) MS-INITprob algorithm. ..................................... 93 6.2 Final results after training with K-means a codebook with 80 units, using different initialization methods: (a) KKZ algorithm, (b) Kmeans++ algorithm, (c) MS-INITmax algorithm and (d) MS-INITprob algorithm. . . . . . 96 6.3 Final results after training a MSCL with 80 units, using different initialization methods: (a) KKZ algorithm, (b) Kmeans++ algorithm, (c) MSINITmax algorithm and (d) MS-INITprob algorithm. .............. 98 7.1 Problem formulation of Color Quantization: pixels are considered 3-dimensional vectors that are processed as inputs for a competitive neural network with many units as colors in the palette. Magnitude value can be associated to the pixel, as another input to the network, or be associated to the units, as an internal parameter. ..............................101 7.2 Original Tiger image (top-left) and its reconstruction using 8 colors applying: ADU (top-right), Homogeneous MSCL (bottom-left) and Centered MSCL (bottom-right). ..................................103 7.3 Original images used in the example of MSCL avoiding dominant colors and one example of the corresponding dominant color palettes (from 1 to 8 colors).106 7.4 Representation of a fraction of the pixels in the color distribution for the fish image. The large red circles represent the regions close to the two dominant colors of the image. The 8 blue circles represent the 8-color palette obtained for MSCL avoiding those dominant colors. MSCL uses three palette-colors for the orange colors of the fish, two colors for the white tones, and only three colors dedicated to the background colors. ................108 7.5 Results of color quantization for the fish example using an 8-color palette with different methods: a) MSCL avoiding two dominant colors, b) NG, c) FSCL, d) FCM, e) K-MEANS, f) SOM. The corresponding color palettes are shown in the right of each image. As can be appreciated, MSCL gets a more vivid palette for the fish and presents a lower number of colors in the palette dedicated to the background with the anemone. . . . . . . . . . . . 109 List of Figures 18 7.6 Saliency example. Top row, from left to right: Original image, saliency map (clearer values for high saliency), the mask binary image used for MSE measurement and (bottom row, from left to right) the reconstructed image with an 8-colors palette from: SOM, FS-SOM and MSCL focused on the saliency. .....................................111 7.7 Binarization example: in top row (a) original image, (b) Otsu method, (c) filtering with Laplacian operator, and (d) its binarization with Otsu; in bottom row (e) SOM, (f) MSCL in homogeneous grey quantization, (g) MSCL with two features, and (h) Otsu binarization of (g). .............112 7.8 The top four graphs correspond to each example image, when dealing with generation of 8-color palettes. The averaged Sum Square Error in the High Magnitude Region (HMR), divided by the total SSE in the image (SSE-ratio) is represented for the different algorithms (FSCL, FCM, NG, K-MEANS, SOM and MSCL). The abscissas in the graphs show several numbers of dominant colors, from 1 to 5. MSCL always presents a smaller SSE-ratio, for all the images and different number of dominant colors. The bottom graph represents the evolution of the averaged HMR-ratios (number of pixels in HMR divided by total number of pixels) when using from 1 to 20 dominant colors. .......................................114 7.9 Results of CQ of the Fish example in a 8 color palette, avoiding different number of dominant colors: (from top to bottom) with 1 to 8 dominant colors. (In columns): magnitude map, pixels with magnitude value over 50% of the maximum (High Magnitude Region), and MSCL reconstruction for the corresponding number of dominant colors. ...............115 7.10 High Magnitude Regions for different number of dominant colors. Images in rows correspond, from top to bottom, with 1 to 8 dominant colors. Images in the left column show the flower example, the column in the middle the tower and the right column the goat image. ..................116 8.1 Basic idea of Competitive Learning algorithms in the task of image compression for grayscale images. Top: Common CL algorithm. Bottom: MSIC algorithm. Differences with other CL algortihms are the use of a MSCL to get block centers (centers are trained weights of MSCL units), the use of irregular blocks and the masked quantization/deprocessing. . . . . . . . . . 118 List of Figures 19 8.2 Global algorithm for grayscale images. Marked with #n the corresponding subsection with the detailed explanation and, also showing the order of processing steps in the transmitter and receiver. ................120 8.3 Neural networks used in the MSIC algorithm: Top: BMUMC and BMUIC. It is important to mention that this last MSCL is used also in receiver (BMUIC2). Bottom: Block extraction phase. Each block delivers the block limits, the image and a binary mask. MSCLP ICT (l) neural network, where a input sample (vectorized block from the extraction phase) has several masked components. ...............................125 8.4 Examples of MSCLP ICT codebooks. (a) Codebook size l= 4. (b) Codebook size l= 10. These codebooks and others for different sizes are known, in form of library, by the transmitter and the receiver. ............126 8.5 Global algorithm for color images. Each color component is processed separately as in the grayscale method. However this process is exemplified in the text with a different magnitude definition for the saliency map, oriented to preserve the detail of the image for certain colors selected by the user. . 128 8.6 Top in columns: Original image, saliency map, MSIC, JPEG and SOM compression for the test images. Bottom: Lena detail in the three methods. It can be clearly seen that the Lena face, compressed with MSIC shows a more natural view (altmost like painted with Pointillism technique) than the other methods that have square block borders. ..............131 8.7 Original ’Street’ image and the compressed images using MSIC with four different Magnitude Functions. .........................132 8.8 Top in columns: Original color image, saliency map generated for a one or two-color selection (fish with orange and white; flower with dark and clear pink; boat with brown; parachute with pink and black), MSIC and JPEG compression for the test images. Bottom: Fish image detail in both compression methods. ..............................134 9.1 Definition of curvature. The cyan ellipsoid is the Voronoi region of unit marked in red. In yellow they are shown the neighbouring units. Curvature at one unit (ie. the red unit) is defined as the average of the projection of each of the vectors between the neighbours and the unit, over the third principal component calculated at the unit’s Voronoi region. Red arrow represents this third principal component of the red unit. ..........137 List of Figures 20 9.2 In left image, the curvature map for Bunny example obtained with a curvature codebook with 2010 units (after pruning 3 units). In right image, Bunny model visualization from Stanford webpage [73]. It is clear that the curvature map shows enough detail of the model. ...............138 9.3 Bunny modelling with 2013 units for MSCL with curvature, MSCL with Qerror, FSCL and Neural Gas. Bar color represents curvature values assigned to prototypes. MSCL with curvature concentrates prototypes in the curls and folds of the skin, modelling with high detail the eyes, ears and the joining zones of limbs and body. ........................139 9.4 Fandisk modelling with 2397 units for MSCL with curvature, MSCL with Qerror, FSCL and Neural Gas. Bar color represents curvature values assigned to prototypes. MSCL with curvature shows more detailed representation in the vertexes and edges of the piece. .......................140 9.5 Histograms of the curvatures assigned to prototypes in several methods (from left to right and top to bottom: MSCL curvature, MSCL Q-error, FSCL, FCM, NG and SOM) for the Fandisk example. The red vertical line indicates the mean value and the green lines represent the standard deviation range. MSCL with curvature shows the larger number of units in high curvature zones. .................................141 9.6 Surface modelling example.(a) Original image. (b) 3D depth image. (c) Curvature map applying Canny. Zones with higher curvature are also brighter. (d) Final surface models after training dataset with a SOM and (e) a MSSOM following curvature. ............................142 List of Tables 1.1 Summary of notational conventions. ...................... 27 3.1 Comparison of the final values of WMSE and normalized Weighted Entropy in MSCL and a basic CL method, trained with the gaussian dataset and magnitude function of eq. (3.26) for three codebook sizes (25,100 and 400 units). ....................................... 52 3.2 Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 40 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 80 codewords and is shown in figure 3.8. ............................ 65 3.3 Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 80 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 80 codewords and is shown in figure 3.8. ............................ 66 3.4 Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 160 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 160 codewords and is shown in figure 3.8. ............................ 66 4.1 Table shows the mean values in 100 tests of the Weighted Mean Square Error (WMSE) calculated in three codebooks (sizes 40, 80 and 160) after applying SOM and MS-SOM trained with four magnitude functions. WMSE is always lower in MS-SOM independently of the magnitude function used. . . . . . . 75 21 List of Tables 22 4.2 Mean classification error (CE) and Weighted Mean Square Error (WMSE) for SOM (with sub-index S) and MS-SOM (MS) obtained after training both algorithms with the three datasets. Additionally number of samples, number of inputs, classes, and map size is displayed for each problem. . . . 77 6.1 Table shows the mean values in 100 tests of the Weighted Mean Square Error (WMSE) calculated in three codebooks (sizes 40, 80 and 160) after applying five initialization algorithms (Random, KKZ, Kmeans++, MSINITmax and MSINITprob). Each of these codebooks is trained following one of three possibilites: No training / Trained using Kmeans / Trained using MSCL (with the same magnitude funcion as for MS-INIT). ............. 95 6.2 Table shows the mean values in 100 tests of the normalized Weighted Entropy calculated in three codebooks (sizes 40, 80 and 160) after applying five initialization algorithms (Random, KKZ, Kmeans++, MSINITmax and MSINITprob). Each of these codebooks is trained following one of three possibilites: No training / Trained using Kmeans / Trained using MSCL (with the same magnitude funcion as for MS-INIT). ................ 95 7.1 MSE calculated in the whole image and in the image center. . . . . . . . . . 104 8.1 Mean MSE for the whole image as well as for areas with saliency over 50% (grayscale example). Standard deviation is also shown (in brackets). . . . . 129 8.2 Mean MSE for the whole image as well as for areas with saliency over 50% (color example). Standard deviation is also shown (in brackets). . . . . . . . 133 A.1 List of abreviations ................................157 Chapter 2 Competitive Learning Neural Networks 2.1 Introduction Unsupervised learning concerns the problem of trying to find hidden structures in unlabelled data. Competitive Learning is a form of unsupervised learning based on artificial neural networks, in which nodes compete for the right to respond to a subset of the input data. A common goal of those algorithms is to distribute a certain number of vectors (prototypes or centroids) in the input data space. The distribution of these vectors should reflect (in one of several possible ways) the probability distribution of the input signals which in general is not given explicitly but only through sample vectors. Competitive Learning Neural Networks usually contain an unique layer of neurons with unit weights wi∈RDwhich is commonly known as ’competitive layer’. The training process is usually divided in two steps: 1. Competition phase: For every input vector x, neurons ’compete’ with each other to see which one of them is the most similar to that particular input vector (that unit is called ’winner’). 2. Weights updating phase: In this step, one or more of the units move towards the input sample. There are two paradigms of Competitive Learning algorithms depending on which of the units are updated. Hard competitive learning (a.k.a. winner-take-all learning) comprises methods where each input signal only determines the adaptation of one unit, the winner. A general problem occurring with hard competitive learning is the possible existence of ’dead units’. Another problem of hard competitive learning is that different 29 Chapter 2. Competitive Learning Neural Networks 30 random initializations may lead to very different results. The second paradigm is called Soft competitive learning (a.k.a. winner-take-more learning). In this case not only the winner but also some other units move towards the sample input. Unit adaptation is different depending on similarity of each unit to the winner unit or the input data, being always greater for winner. Training can be obtained by performing either batch or on-line update. In batch methods all possible input signals (which must come from a finite set in this case) are evaluated first, before any adaptation is done. This is iterated a number of times. On-line methods, on the other hand, perform an update step directly after each input signal. The possibility of this on-line training, in conjunction with the simplicity of the method is an advantage over other unsupervised learning algorithms. CL neural networks are used for different applications depending on the goal of the used CL method . Main applications are: 1. Vector quantization: Vector Quantization is a classical quantization technique which allows the modelling of probability of the density of a dataset by the distribution of a set prototype vectors. Input dataset is divided into groups having approximately the same number of points closest to them. Each group is represented by a prototype vector (codeword). The goal in Vector Quantization is the minimization of the expected quantization (or distortion) error between that codeword and the input vectors that it represent. Correspondingly, in the case of a finite data set Dthe Mean Squared Error has to be minimized: MSE(X;M) = 1 | X | ·X um∈M x∈Rm kx−wmk2(2.1) 2. Entropy maximization: If we interpret the generation of an input signal and the subsequent mapping onto the nearest unit in Mas random experiment which assigns a value u∈ M to the random variable X, the Shannon entropy (a measure of the information content in the codification), is defined as: H(X) = −X um∈M p(um) log p(um) (2.2) Here, p(um) is the probability mass function of outcome um, that is, the probability Chapter 2. Competitive Learning Neural Networks 31 that input signal is assigned to unit um: p(um) = | Rm| | X | (2.3) Therefore, the entropy becomes: H(X) = −X um∈M | Rm| | X | log | Rm| | X | (2.4) When the goal of the CL algorithm is entropy maximization, ensuring that all the codewords are used with equal frequency, the probability p(u) tends to the following value as the neural network is trained: p(um) = 1 | X | (2.5) 3. Clustering: Another possible application of CL algorithms is clustering, where a partition of the dataset into subgroups or clusters is sought, such that data samples in the same group (called cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters). Clustering is widely used for pattern recognition, feature extraction, image segmentation, function approximation, and data mining. 4. Feature mapping: Sometimes it is necessary to produce a low-dimensional representation of the input space of the training samples in such a way, that some similarity relations present in the original data are still present after mapping. This process has been denoted feature mapping and can be useful for data visualization. It requires a neural network with fixed dimensionality such as SOM (it will be explained later). 5. Novelty detection. The goal is the determination whether or not a unknown data sample xis well represented by a previously trained CL neural network . The sample is said to be ’known’ if the distance from the sample to its BMU (wj) in the CL neural network is less than a pre defined threshold Th: kx−wjk< Th (2.6) Otherwise it is a ’new’ sample. The value of Th is usually defined from the mean and standard deviation of the quantitation error reached during the neural network Chapter 2. Competitive Learning Neural Networks 32 training. In this chapter we will analyse some of the existing Competitive Learning algorithms. The remainder of this chapter is organized as follows: Next section describes the basic Competitive Learning Algorithm. Section 2.3 explains some of the most common CL algorithms. Finally, last section describes some other algorithms related to the Magnitude Sensitive Competitive Neural Networks described in this Thesis. 2.2 Basic Competitive Learning Algorithm Here we present the basic Competitive Learning Algorithm in an online training mode. It follows these steps: 1. The codebook set is initialized to contain M units, with codewords wiinitialized with samples randomly selected from the dataset D: M={u1, u2,...,uM}(2.7) 2. Selection at random of an input signal x(t) from the dataset X. 3. Determination of winner unit ujas: j= argmin um∈M (kx(t)−wm(t)k) (2.8) 4. Adaptation the codeword of the winner towards the input sample: wj(t+ 1) = wj(t) + α(t)·(x(t)−wj(t)) (2.9) where α(t) is the learning factor. It takes a constant value or decreases during training. 5. Step 2 is repeated until a stopping condition is reached (e.g. a pre-defined number of iterations). This CL algorithm is the basis of other algorithm that will be explained in this chapter. Its implementation in batch mode is called LBG (or generalized Lloyd) algorithm. Chapter 2. Competitive Learning Neural Networks 33 Figure 2.1: Competitive neural network architecture 2.3 Usual Competitive Learning Algorithms Here we will describe some of the most extended competitive learning algorithms. 2.3.1 K-Means K-means algorithm ([49]) is the basic CL algorithm, using different values for αfor each unit: αm=1 tm (2.10) In this case, tmstands for the number of input signals for which unit umhas been winner so far. Doing so, codeword wm(t) is always the exact arithmetic mean of the input signals it has been winner for. The number of units is K, what originates its name. k-means is rather easy to implement and apply even on large data sets, and therefore it has been widely used in clustering. As such, it has been successfully used in various topics, ranging from market segmentation, computer vision, geostatistics and astronomy. The algorithm has two main drawbacks: 1. It requires to define the number of codewords, what may be a problem in clustering Chapter 2. Competitive Learning Neural Networks 34 when it is unknown the number of clusters in advance. 2. K-means is sensitive to initialization as it is a Hard Learning algorithm. 2.3.2 Neural Gas This algorithm is named ’neural gas’ because of the dynamics of the feature vectors during the adaptation process, which distribute themselves like a gas within the data space. The algorithm follows the Soft Competing paradigm, what means that all of the units move through the input sample with a step size decreasing with the increase of the distance order. This adaptation of the whole codebook yields to a robust convergence, but on the other hand processing is more time consuming than K-means. Neural Gas follows same steps than the basic CL algorithm, but it changes in steps 3 and 4: 3. The distance order of the feature vectors to the given data vector xis determined. i0 denotes the index of the closest feature vector (wi0), i1the index of the second closest feature vector (wi1), . . . , and iN−1the index of the feature vector most distant to x. 4. In the adaptation step, each codeword wik(k= 0,...,M −1) is adapted according to: wik(t+ 1) = wik(t) + α(t)·e−k/λ(t)·(x(t)−wik(t)) (2.11) Both α(t), and λ(t), the so-called neighborhood range, are reduced with increasing time t. Growing neural gas ( Fritzke, 1994b, 1995a) is a variant of this algorithm where the number of units is increased during training (beginning with very few units) until the global quantization error measures lower a pre-defined value. This version of Neural Gas has the advantage that it does not require to define in advance the number of units as a parameter. 2.3.3 Self-Organizing Feature Map Self-Organizing Feature Map (also called SOM) is a is a type of CL neural network that has the capability of mapping the D-dimensional input space (being Darbitrarily large) to a lower dimension structure (usually called map), while preserving the topological properties of the input space. This makes it possible to get a representation of the data which may be used for visualization purposes (in this case it uses a 2D or 3D representation). Chapter 2. Competitive Learning Neural Networks 35 The SOM is also a Soft Competive Algorithm that follows the basic CL algorithm excepting in step 3, as all of the units (not only the winner) are updated. 3. For each unit ui∈ M: wm(t+ 1) = wm(t) + α(t)·hmj(t)·(x(t)−wm(t)) (2.12) In this equation, hmj(t) is the neighborhood function that depends on the lattice distance between the BMU (uj) and unit um. A Gaussian function is a common choice for this neighborhood function. The advantage of SOM against other CL algorithms is the ordered topological structure of neurons in data space. SOM may be considered a nonlinear generalization of Principal Components Analysis (PCA) [84]. It has been shown, using both artificial and real geophysical data, that SOM has many advantages over it ([46], [47] ). Due of these advantages, SOM has been widely used in several machine learning applications. They include image and video processing; density or spectrum profile modeling; text/document mining and management systems; gene expression data analysis and discovery; and high dimensional data visualization. Being such a popular unsupervised learning algorithm, it has several variants. Some of them are: •Time adaptive self-organizing map (TASOM) network ([72]) is an extension of the basic SOM. TASOM employs adaptive learning rates and neighborhood functions. It also includes a scaling parameter to make the network invariant to scaling, translation and rotation of the input space. The TASOM and its variants have been used in several applications including adaptive clustering, multilevel thresholding, input space approximation, and active contour modeling. •Growing self-organizing map (GSOM, [3]) is a growing variant of the self-organizing map. GSOM was developed to address the issue of identifying a suitable map size for the SOM. It starts with a minimal number of nodes and grows new nodes during training. By using a value called the spread factor, the data analyst has the ability to control the growth of the GSOM. •There are also several temporal extensions of the SOM to have into account the effect of the temporal occurrence of the input samples. Temporal Kohonen Map (TKM, Chapter 2. Competitive Learning Neural Networks 36 [15]) and Recurrent Self-Organizing Map (RSOM, [78]), incorporate leaky integrator memory to preserve the temporal context of the input signals. •Other variants are related with the number of neural networks used simultaneously as in the case of Hierarchical SOMs, where, at some stage, one of the SOMs receives as inputs the outputs of another SOM. 2.4 Most related methods There are several methods highly related to MSCL or MS-SOM. Here we explain some of them. 2.4.1 Frequency Sensitive Competitive Learning The most similar one is the FSCL method [1], that basically follows the same structure as MSCL if we use the winning frequency of the units as magnitude. The FSCL introduces during the competition phase a parameter, named the relative winning frequency or ’conscience’. The centres chance to win the competition is directly proportional to the relative winning frequency. The learning rate of the frequent winners is reduced, as their chance to win the competition does. By this additional ’conscience’ term, it circumvents the ’dead units’ problem usually present in the k-means algorithm. FSCL uses the basic implementation of CL, with a modified criterion for selection of the best-matching unit by adding the ’conscience’ term F, that depends on the number of hits that every unit has received up to the moment (wm). Therefore, step 3 is different: j= argmin um∈M (F(wm)· kx(t)−wm(t)k) (2.13) where usually F(wm) takes an exponential form: F(wm) = (wm)γ(2.14) Some successful applications of the FSCL algorithm are feature extraction [13] and image compression [14]. Some variants of FSCL has been developed for clustering tasks, as the Rival Penalized Competitive Learning algorithm RPCL [12]. This algorithm rewards the winning center and penalizes with a de-learning rate the second winner, named rival. Chapter 2. Competitive Learning Neural Networks 37 2.4.2 Energy Based Competitive Learning Energy Based Competitive Learning [82] is an algorithm that addresses the three important issues associated with competitive learning clustering. Auto-initialization is achieved by extracting samples of high energy to form a core point set, whereby connected components are obtained as initial clusters. To adapt to clusters of different size and sparsity, a novel competition mechanism, uses for each prototype a definition of energy multiplied by distance, to select a winner prototype. For eliminating the disturbance caused by outliers, adaptive learning rate based on samples’ energy is proposed to update the winner. The reason of using energy is to select a number of prototypes to cluster the data distributions optimally according to its density, so that it differs considerably from MSCL, that is formulated as a magnitude-oriented VQ method. 2.4.3 K-Harmonic Means and Weighted K-means Two methods based on K-means, K-Harmonic Means [86] and Weighted K-means [37], use the modulation of the distance by factors as MSCL does with magnitude. The first method replaces the minimum distance from a data point to the centroids, used in K-means, by the Harmonic Averages of the distances from the data point to all centroids. The main goal of this algorithm is that the K-means becomes less sensitive to the initialization of the centroids. However authors claim that the method significantly improves the quality of clustering results comparing with both K-Means and Expectation Maximization [22]. The Weighted K-means uses the same structure of K-Harmonic Means, introducing membership function for the centroids, but replacing the Harmonic Averages of the distances by weights obtained from a density-biased reservoir sampling algorithm, that represents the density of the original data points. Both methods are oriented to specific tasks by means of their weighted distance, but basically do not define an open method to any desired target in the VQ processing as MSCL does. 2.4.4 Magnification control After training a CL neural network, the achieved weight vector density ρ(w) is in relation to the data density P(D) following: P(X)∝ρ(w)α(2.15) The exponent αis called magnification exponent or magnification factor. Controlling this factor it is possible to modify the magnification properties of the vector quantizer as Chapter 2. Competitive Learning Neural Networks 38 it may be required in different application tasks. Magnification and its control is related to biological phenomena like the ’perceptual magnet effect’. In 1992, Kuhl, introduced this phenomenon, which demonstrated that as a second language is acquired, the brain gradually groups sounds according to their similarity with phonemes in the native language. That was due to the fact that rarely occurring stimuli are differentiated with high precision whereas frequent stimuli are distinguished only in a rough manner ([39]; [40]). It is a kind of attention-based learning with inverted magnification, where rarely occurring input samples are emphasized by an increased learning gain. This effect is also beneficial in technical systems. For instance in remote-sensing image analysis, seldomly found ground cover classes should be detected, whereas usual (frequent) classes with broad variance should be suppressed ([54], [80]). Also anomaly detection in industrial processes or intrusion detection in computer security systems requires that abnormal situations receive more importance during training. Villmann presents in ([81]) a general framework to control the magnification achieved by SOM or NG neural networks. This method works by following one of these learning schemes: 1. Localized learning: Introduction of a multiplicative factor by a local learning rate αm=α(wm) that depends on the stimulus density Pat the position of their weight vectors wmvia hαmi=α0·P(wm)γ,(2.16) where the brackets hi denote the average in time. 2. Winner-relaxing learning: Introduction of winner relaxing by adding a winner-enhancing (relaxing) term R: wj(t+ 1) = wj(t) + α(t)·(x(t)−wj(t)) + R(2.17) 3. Concave-convex learning: Scaling of the learning shift by powers ξin the factor (x−wi)ξ: wj(t+ 1) = wj(t) + α(t)·(x(t)−wj(t))ξ(2.18) Chapter 3. MSCL algorithm 45 Local unit competition In the second step, winner unit with index jis selected from units belonging to Sas the one that minimizes the product of its magnitude value as in equation 3.8a (or the accumulated magnitude, eq. 3.8b) with the distance of its weights to input data vector, following one of these equations j= argmin us∈S (mus(t)γ· kx(t)−ws(t)k),or (3.8a) j= argmin us∈S (maccs(t)γ· kx(t)−ws(t)k),(3.8b) being maccs(t) the accumulated magnitude of unit uscalculated by the equation 3.10 The use of mu in local competition is more adequate than macc when the goal of training is Qerr reduction while macc is better to reduce the entropy. γis an exponential factor to modulate the strength of the magnitude during the competition. Winner update For all units in the map, weights and magnitude are adjusted iteratively for each training sample, following (m= 1 . . . M): mf(t) =    mx(t),if used a magnitude vector (mx). muj(t),otherwise. (3.9) maccj(t+ 1) = maccj(t) + mf(t) (3.10) αm(t) = mf(t) maccm(t+ 1)β (3.11) wj(t+ 1) = wj(t) + αm(t) (x(t)−wj(t)) (3.12) where αis the learning rate calculated for the winner and forced to decay with the magnitude accumulation and βis a scalar value between 0 and 1. Using this definition, when βis equal to one, the value of each unit’s weights become the weighted running mean of the input data samples belonging to its Voronoi region. Chapter 3. MSCL algorithm 46 Magnitude update Only winner’s magnitude is adjusted for each training sample, following: muj(t+ 1) =    muj(t) + αm(t) (mx(t)−muj(t)) ,if mx is used. MF(wj(t+ 1), < j >),otherwise. (3.13) Stopping condition Training finish when a termination condition is reached: it may be the situation when all data samples has been presented to the MSCL neural network along certain number of cycles (if a limited number of samples is used), or the condition of low mean change in unit weights, or any other function that could measure the training stabilization. 3.2.2 Batch implementation of the MSCL algorithm Next subsections describe the algorithm in an batch updating schedule, where units are adjusted after a presentation of a limited number of samples at each epoch or after the complete presentation of the whole dataset. Here we name tep the epoch number. Initialization Initialization is done in the same way than in online MSCL implementation. Random selection of data samples We select a data set Xep ⊂ X formed of Nep randomly selected samples from the dataset: Xep ={x1,x2,...,xNep },xi∈RD(3.14) Global unit competition For each sample in Xep,Kunits with minimum distance from their weights to the input data vector are selected as winners in this first step. These units form the S(t) set, corresponding to input sample x(t) (S(t)⊂ M): Chapter 3. MSCL algorithm 47 S(t) = {us1, us2, ..., usK} kx(t)−ws(t)k<kx(t)−wm(t)k ∀um/∈ S(t)∧us∈ S(t) t= 1 . . . Nep.(3.15) Local unit competition Once again, for each sample in Xep, best matching unit jis selected from units belonging to Sas the one that minimizes the product of its magnitude value as in equation 3.16a (or the accumulated magnitude, eq. 3.16b) by the distance of its weights to input data vector, following one of these equations: j= argmin us∈S(tep) (mus(t)γ· kx(t)−ws(t)k),or (3.16a) j= argmin us∈S(tep) (maccs(t)γ· kx(t)−ws(t)k).(3.16b) Winner update First, the magnitude of input sample at time t, mf(t), is calculated through equation 3.9. Then for each unit um, we calculate the weighted arithmetic mean (xepm) of samples belonging to Xep within its Voronoi Region Rm, using the value of the magnitude mf(t) as the value for weighting the sample x(t): xepm=P k∈Rm mf(k)·x(k) P k∈Rm mf(k)(3.17) being Rm={x∈ Xep |j=um}. The estimated increase of magnitude in the epoch for that unit is: mepm=X k∈Rm mf(k) (3.18) These values are used for calculating the learning rate αm, and update the accumulated magnitude and weight of each unit: Chapter 3. MSCL algorithm 48 maccm(tep + 1) = maccm(tep) + mepm(3.19) αm=mepm maccm(tep + 1)β (3.20) wm(tep + 1) = wm(tep) + αm(xepm−wm(tep)) (3.21) where βis a scalar value between 0 and 1. Magnitude update Each unit umupdates its magnitude. If this value is given by a value associated to each input sample, magnitude at each unit becomes the running weighted mean of the magnitude of all data samples at its Voronoi region: mxepm=P k∈Rm mx(k)2 P k∈Rm mx(k)(3.22) mum(tep + 1) = mum(tep) + αi(mxepm−mum(tep)) (3.23) Otherwise, it is calculated directly with the magnitude function: mum(tep + 1) = MF(wm(tep + 1), < M >) (3.24) Stopping condition Training finish when a termination condition is reached, as in the case of online MSCL implementation. Otherwise the process will be repeated from step 2 every epoch until every data has been presented to the MSCL neural network. 3.3 Algorithm analysis 3.3.1 Resulting Voronoi regions As mentioned in Chapter1, section 3, Voronoi region of a unit umconsists of all points in the Euclidean space where this unit is the Best Matching Unit of these points. Chapter 3. MSCL algorithm 49 When Euclidean distance is used in the competition step in a Competitive Learning algorithm, decision region between adjacent Voronoi regions is formed by hyperplanes. These hyperplanes consist of all the points in the space equidistant to the two nearest unit-prototypes. In this case, Vm={x∈RD| kx−wmk ≤ kx−wkk ∀uk∈ M} (3.25) However, with the magnitude term weighting the distance in a two step competition (as in the MSCL algorithm), the resulting boundaries between Voronoi regions can be more complex and those units with higher magnitude tend to have lower volumes in their Voronoi regions, even if the data density is uniform. Example of figure 3.3(a) shows the result of training 30 units in a two-dimensional synthetic data set consisting of P= 5000 samples generated from a mixture of three Gaussian distributions centered on the points (0,0), (3,4) and (6,0) with covariance matrix [0.1 0; 0 0.1] for all of them. The percentage of samples placed in each cluster is almost the same: 33.3%. We use a magnitude associated to each sample through the function: MF(x) = abs (x2) (3.26) As can be appreciated in the figure, magnitude takes null values in the horizontal line with x2= 0, and takes value 1 in the higher value of the second component of x. This figure, 3.3, shows the Voronoi regions corresponding to Euclidean distance (c) and those corresponding to a magnitude weighted distance (d). Each limit between two neighbouring units are equidistant from both units in the case (c), while it is closer to the unit of lower magnitude in the case (d). 3.3.2 Connections MSCL is a winner-take-all neural network, therefore each unit forms no structure with its neighbouring units. However, for certain applications it is interesting to know what is the neighborhood of a given unit. To do it we define a set of the neighborhood connections between units of the network as: C=M × M (3.27) where two units (ui, uj)⊂ C are ’connected’ if both are first and second BMUs considering Chapter 3. MSCL algorithm 50 Figure 3.3: Example of Voronoi regions corresponding to 30 units. (a) Centroids and magnitude, abs(x2). It can be appreciated how the density of centroids increases as x2becomes higher, as higher magnitude zones attract more units to be represented. (b) Voronoi sets of each unit: Samples assigned to centroids using distance weighted by magnitude defined in a, (c) Voronoi regions for Euclidean distance, (d) Voronoi regions for distance weighted by magnitude defined in a. the euclidean distance: i= argmin uk∈M (kx(t)−wk(t)k) (3.28) j= argmin uk∈M\{ui} (kx(t)−wk(t)k) (3.29) Usually connections set Cis generated once training has finished. This set can also be calculated during the training process. In this case, as units are moving in the data space, connections established during the early stages of training usually does not correspond Chapter 3. MSCL algorithm 51 with the final ones. Therefore, it becomes necessary to remove old connections. We define that two units (ui, uj)6⊂ C if they have not been connected during any of the previous KC input signal presentations, where KCis an integer that usually corresponds to the total number of data samples. Figure 3.4 shows the result of training of a MSCL with 20 units (centroids painted in blue) in the same dataset of previous example, but using abs(x1) as the magnitude. In figure 3.4(a) each sample of the dataset is coloured by the value of the magnitude of its BMU. On the right, it is shown the same figure, but adding the connections between units as it has been explained above. (a) Trained MSCL (b) Trained MSCL with connections Figure 3.4: Example of representation of a trained MSCL with connections obtained after training. 3.3.3 Modified quality measures Two new magnitudes Weighted Mean Squared Error and Weighted Entropy has been defined to measure the quality of training in a Magnitude Sensitive Competitive Neural Network. •Weighted Mean Squared Error: Weighted Mean Square Error (WMSE) is the weighted mean of the quantization squared error, where weights are the values of the magnitude at each sample (normalized by the sum of magnitudes in all the dataset), and it is calculated in a similar way to [66]: WMSE(X;M) = Pum∈M x∈Rm MF(x)· kx−wmk2 Px∈X MF(x)(3.30) Chapter 3. MSCL algorithm 52 Given a finite data set X, and a defined number of units M, the WMSE value is lower as the distribution of centroids are replicating in more detail the magnitude function. •Weighted Entropy: It is also possible to define a value of Weighted Entropy, where weights are the value of the magnitude at each sample. It also follows 2.3, but using a different definition for the probability p(um), that depends on the density of magnitude, instead of the data density. p(um) = P x∈Rm MF(x) P x∈X MF(x)(3.31) By dividing by the maximum entropy (obtained when all units have the same value in eq.3.31), the normalized entropy is expressed as: H(X) = −X um∈M  P x∈Rm MF(x) P x∈X MF(x) log  P x∈Rm MF(x) P x∈X MF(x) /log (| M |) (3.32) Figure 3.5 shows the evolution of WMSE (black line) and Weighted Entropy (red line) during training of a MSCL with 50 units along 5 cycles of 10 epochs each. Both magnitudes present an abrupt change at the beginning of training and they move towards its final values but more slowly. Dataset Xis the three Gaussian example with magnitude function of equation 3.26. Table 3.1 shows a comparison of the final values of WMSE and normalized Weighted Entropy, with a MSCL and the basic CL algorithm. Both test are done with different number of units: 25, 100 and 400. As it can be seen in the table, WMSE is always lower Q measure Algorithm 25 100 400 WMSE MSCL 0.543 0.290 0.142 CL 0.585 0.304 0.145 Weighted Entropy MSLC 0.962 0.947 0.941 CL 0.885 0.912 0.932 Table 3.1: Comparison of the final values of WMSE and normalized Weighted Entropy in MSCL and a basic CL method, trained with the gaussian dataset and magnitude function of eq. (3.26) for three codebook sizes (25,100 and 400 units). Chapter 3. MSCL algorithm 53 0 5 10 15 20 25 30 35 40 45 50 0.4 0.5 0.6 0.7 0.8 0.9 1 Figure 3.5: Evolution of WMSE (black) and normalized Weighted Entropy (red) during training of a MSCL with 50 units along 5 cycles of 10 epochs each. As expected, WMSE decreases during training, while the normalized Weighted Entropy tends to a constant value of 1. in MSCL, and the Weighted Entropy is always higher. This means that MSCL is better than simple CL for all the cases independently if the goal is error minimization or entropy maximization. 3.3.4 Effect of alpha As it has been mentioned in 3.2.1,αis the learning rate, that depends on the magnitude of input samples and is different for each unit. It is assigned a value so that the vector reference wm(t) for unit umis always the exact arithmetic weighted mean of the input signals it has been the winner. This only happens when βis equal to 1 (Next subsection will explain the influence of β). If we name y(t) (t= 1 ... | Rm|) to the successive inputs where umis its BMU, and my(t) the corresponding value of magnitude. The sequence of successive values of wm, Chapter 3. MSCL algorithm 54 when equations 3.10 to 3.12 are applied for beta=1, is the following: wm(0) = y(0) wm(1) = wm(0) + my(1) my(0) + my(1)·(y(1) −wm(0)) =my(0) ·y(0) + my(1) ·y(1) my(0) + my(1) wm(2) = wm(1) + my(2) my(0) + my(1) + my(2)·(y(2) −wm(1)) =my(0) ·y(0) + my(1) ·y(1) + my(2) ·y(2) my(0) + my(1) + my(2) . . . wm(t) = wm(t−1) + my(t) my(0) + my(1) + ...+my(t)·(y(t)−wm(t−1)) =P i=1···t my(i)·y(i) P i=1···t my(i) (3.33) Therefore, as desired, the reference vector becomes the arithmetic weighted mean of samples in its Voronoi region. It should be noted that the set of signals y(t) for which a particular unit umhas been the winner may contain elements which lie outside the final Voronoi region of umdue to changes in the value of wmduring training. 3.3.5 Effect of beta βis an scalar between 0 and 1 (both values are possible) used to add a forgetting factor for unit adaptation during training. As it has been shown in the previous subsection, a value of β= 1 results in reference vectors that are equal to the arithmetic weighted mean of samples in its Voronoi Set. However, usually units change substantially during first epochs of training, while they tend to be stationary at last stages. The parameter βis used precisely to enhance the importance of last samples during training (when units are close to its final position). A low value of β(near zero) gives less weight to initial samples when calculating the weighted arithmetic mean of input samples. In the extreme situation, if β= 0 then α= 1 and: Chapter 3. MSCL algorithm 61 Figure 3.9: Gaussian example. Resulting representations of MSCL for contraction magnitude functions are shown in figures aand b, MSCL with expansion magnitude functions in cand d MSCL with Q-err in fand FSCL in figure e. The color bar represents the magnitude values assigned to the units. Black points represent the initial codebook for density estimation of the data, separated by Otsu method into dense (shown in figures band c) and sparse (shown in figures aand d) sub-representations. Contract1 and Expansion1 (aand c) present magnitude functions that force units to avoid the corresponding black points. Contract2 and Expansion2 (band d) present magnitude functions that force units to approximate to the black points. Chapter 3. MSCL algorithm 62 form, as it was not our objective to determine which is the best selection of magnitude function for each task. Figure 3.9 shows an example of simulation results corresponding to the MSCL algorithm for different contraction and expansion magnitudes. In MSCL example for Contract2, the magnitude function is chosen to concentrate units in data zones with high density, identified by ωdense. First, for each unit umit is calculated its minimal distance (MD) to the zone of the dense-prototypes, Mdense: MDm(t) = min um∈M uk∈Mdense (kωk(t)−wm(t)k) (3.37) And the magnitude function of each unit uses this distance normalized by the maximum for all units: MF(m)(t) = 1 −MDm(t) max um∈M(MDm(t)) (3.38) This magnitude function has maximum value 1 when the unit prototype coincides with one of the dense-prototypes, so units are impelled to compete for placing their prototypes over the black dense-representation, as can be appreciated in figure 3.9(b). We can also force the contraction of the prototypes in dense zones by avoiding the sparse-prototype representation. The magnitude function in this Contract1 approximation is calculated: MDm(t) = min um∈M uk∈Msparse (kωk(t)−wm(t)k) (3.39) MF(m)(t) = MDm(t) max um∈M(MDm(t)) (3.40) This magnitude function has maximum value of 1 in one unit such as its distance to the Msparse set is the maximum from all prototypes, so units are impelled to compete for placing their prototypes far from the black sparse-prototypes in figure 3.9(a). It is worth noting that these prototypes mainly tend to concentrate on the means of data distributions, while external distribution zones, marked with the black sparse-prototypes, are less represented. For the expansion applications we aim to concentrate units in data areas with low data-density. The same magnitude functions used in contraction cases can be used by interchanging dense-prototypes by sparse-prototypes. The Expansion1 case shown in figure Chapter 3. MSCL algorithm 63 3.9(c) is obtained by avoiding the dense-prototypes, while Expansion2 shown in figure 3.9(d) is obtained by approximation to the sparse-prototypes. These expansion cases tend to represent the boundaries of the clusters with more detail. Novelty detection applications can benefit from this behavior, as they precisely need to distinguish these boundaries with more detail, in order to identify if a new data sample belongs to the known data distribution or not. For all methods mentioned before, three tests with 40, 80 and 160 prototypes (M= [40,80,160]) for initial random weights were trained with the dataset during 50 cycles for each algorithm. Along the training process three evaluation measures are calculated to represent their evolution and final values. The three tests were replicated 30 times and their evaluation measures averaged to avoid distortion due to the random initialization. In order to evaluate the performance of the methods in generating a vector quantization task, and considering that data is not labelled in any form, we propose three unsupervised measures for evaluation: Davies-Bouldin Index (DB-index) [20], Shannon’s informational entropy (normalized by the maximum value log2(number of codewords)) and the Weighted Mean Squared Error (WMSE). Figure 3.10 shows the training evolution of the mean DB-index in the different methods (averaged in 30 simulations). The left graph shows the evolution for methods: MSCL with Q-error as magnitude, FSCL, FCM, NG, SOM and K-means. The right graph also shows these two methods as comparison, and the results for the different MSCL in contractexpansion examples. The minimum final values correspond to MSCL with Expansion1 and Q-error as magnitude functions. As expansion examples do not pretend to achieve an optimum VQ of the dataset, their DB-index evolution present final values higher than the other magnitudes. It is interesting to note that DB-indexes of Contract1 and Expansion1 examples that avoid the sparse-prototypes and dense-prototypes, respectively, present lower values than Contract2 and Expansion2 examples that approximate the dense-prototypes and sparse-prototypes respectively. This difference stems surely from the fact that the approximating strategy is less flexible in the prototype distribution (focusing in the fixed black or sparse prototypes) than the avoiding strategy. In the top-left graph of figure 3.10, the MSCL with Q-error generates the lower DBindex, and surprisingly the Expansion1 magnitude function in the top-right graph can generate the minimum value. This magnitude function forces units to avoid the dense codewords in the center of distributions and generates a more detailed representation of the external parts of data distributions. MSCL, with mean Q-error as magnitude function, tends to give the best clustering representations measured by DB-index, that is not Chapter 3. MSCL algorithm 64 0 20 40 60 80 100 0 0.5 1 1.5 2 2.5 3 DB−index Measures Q−error K−Means FSCL FCM NG SOM 0 20 40 60 80 100 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 DB−index Measures Q−error K−Means Contract1 Contract2 Expansion1 Expansion2 0 20 40 60 80 100 0.9 0.92 0.94 0.96 0.98 1 Entropy Measures Q−error K−Means FSCL FCM NG SOM 0 20 40 60 80 100 0.85 0.9 0.95 1 Entropy Measures Q−error K−Means Contract1 Contract2 Expansion1 Expansion2 0 20 40 60 80 100 0.2 0.3 0.4 0.5 0.6 WMSE Measures Q−error K−Means FSCL FCM NG SOM 0 20 40 60 80 100 0.22 0.24 0.26 0.28 0.3 0.32 0.34 0.36 WMSE Measures Q−error K−Means Contract1 Contract2 Expansion1 Expansion2 Figure 3.10: Evolution along training process during 50 cycles of the averages in 30 simulations of the DB-Index, Normalized Entropy and Weighted Mean Squared Error. The left column shows the evolution for methods: MSCL with Q-error, FSCL, FCM, NG, SOM and K-means. The right column shows also MSCL with Q-error and K-means as comparison, with the results for the different MSCL in contract-expansion examples. surprising as DB-index is based on evaluating the homogeneous partition of mean Q-error among prototypes, so MSCL using Q-error as magnitude, which tends to accomplish this desired behavior, becomes the best in this index evaluation. For normalized entropy in graphs of the second row, the best method is FSCL, as it Chapter 3. MSCL algorithm 65 Method BD Mean/Std H Mean/Std WMSE Mean/Std Q-error 0.385 0.070 0.9157 0.0034 0.2743 0.0023 FSCL 0.491 0.188 0.9972 0.0003 0.2247 0.0010 Contract1 0.638 0.382 0.9739 0.0026 0.2186 0.0093 Contract2 0.837 0.425 0.9493 0.0077 0.2497 0.0116 Expansion1 0.492 0.147 0.8157 0.0094 0.3936 0.0124 Expansion2 1.065 0.699 0.8482 0.0080 0.3653 0.0140 FCM 0.673 0.286 0.9934 0.0016 0.2735 0.0052 NG 0.385 0.108 0.9776 0.0013 0.2307 0.0012 K-Means 0.473 0.130 0.9751 0.0027 0.2388 0.0041 SOM 2.093 0.108 0.9423 0.0036 0.5530 0.0124 Table 3.2: Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 40 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 80 codewords and is shown in figure 3.8. was expected. The other standard VQ methods tend to rise their entropies as they are methods focused in data density replication, but MSCL methods do not increase entropies, as their magnitudes are other than data density replication. The bottom graphs represent the Weighted MSE. In this case, the magnitude used for weighting the MSE of each unit of all methods is obtained as the equation 3.38, so all methods who tend to concentrate units in the center of the data distributions will present a decreasing evolution for their WMSEs (as it can be appreciated in the lower-left graph), being the MSCL methods with contract magnitude functions whose present the lower values of all (lower-right graph). However, the MSCL with expansion magnitude functions (Expansion1 and Expansion2) tend to push their units out of the centers of data distributions and the calculated WMSE tends to grow instead of decreasing (lower-right graph). Tables 3.2,3.3 and 3.4 show the mean and standard deviation (30 simulations) for the final values obtained in the three evaluation measures with the different algorithms using 40, 80 and 160 units. For the entropic measure, FSCL is always the best, as was expected by [1]. For the Weighted MSE, as this measure is obtained by applying normalized magnitudes obtained with equation 3.38, the MSCL methods with contracting magnitude functions (Contract1 and Contract2) tend to give the lower values in WMSE. For DB-index measure it is not so clear which method is the best in obtaining the lower value, besides the standard deviation values are quite large compared with those of entropy and WMSE. However, MSCL with Q-error presents in DB-index consistent lower values and standar Chapter 3. MSCL algorithm 66 Method BD Mean/Std H Mean/Std WMSE Mean/Std Q-error 0.3559 0.0639 0.9160 0.0021 0.1404 0.0012 FSCL 0.3842 0.1805 0.9967 0.0003 0.1131 0.0009 Contract1 0.5717 0.4761 0.9738 0.0024 0.1093 0.0053 Contract2 0.7375 0.4298 0.9640 0.0037 0.1041 0.0033 Expansion1 0.3322 0.1503 0.8201 0.0070 0.1962 0.0050 Expansion2 0.7019 0.3268 0.8568 0.0064 0.1794 0.0068 FCM 0.7874 0.4513 0.9910 0.0014 0.1584 0.0035 NG 0.3904 0.1462 0.9768 0.0013 0.1189 0.0007 K-Means 0.4208 0.1743 0.9760 0.0025 0.1233 0.0026 SOM 3.1550 0.1980 0.9451 0.0021 0.4285 0.0073 Table 3.3: Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 80 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 80 codewords and is shown in figure 3.8. Method BD Mean/Std H Mean/Std WMSE Mean/Std Q-error 0.3429 0.1628 0.9337 0.0016 0.0641 0.0004 FSCL 0.3179 0.1570 0.9960 0.0003 0.0544 0.0006 Contract1 0.4487 0.3566 0.9636 0.0022 0.0518 0.0016 Contract2 0.5652 0.3807 0.9622 0.0017 0.0497 0.0009 Expansion1 0.4061 0.1473 0.8373 0.0032 0.0878 0.0017 Expansion2 0.5723 0.4350 0.8794 0.0024 0.0794 0.0057 FCM 0.8428 0.6305 0.9782 0.0018 0.1107 0.0030 NG 0.3443 0.1274 0.9782 0.0012 0.0580 0.0005 K-Means 0.3911 0.1562 0.9830 0.0024 0.0621 0.0014 SOM 3.6653 0.1224 0.9605 0.0015 0.2508 0.0059 Table 3.4: Mean and standard deviation, for 30 tests, of final measures: DB-index, Normalized entropy and WMSE, after training 160 units for the VQ task along 50 cycles. The codebook for the estimation of densities has 160 codewords and is shown in figure 3.8. Chapter 3. MSCL algorithm 67 deviations, as it was expected cause the DB-index is based in Q-error estimation. 3.4.2 Interpolation application 3.4 3.6 3.8 4.0 4.2 −10 −8 −6 −4 −2 0 2 4 6 8 10 X Y Data MSCL FSCL Magnitude Figure 3.11: Interpolation example showing the FSCL and MSCL representations of the data series. The red line represents the magnitude value along the data series. FSCL does not represent the data in the high frequency perturbation as well as MSCL. Next example consists in interpolating a designed data series to show that MSCL can be focused to any characteristic of the data. In this case, we focus the magnitude function to have a detailed representation of high frequency variations that can be found in the data series. Data set was generated by uniformly sampling a function with three piecewise function with a high frequency perturbation: LF(x) = −10 cos (12x) + 12 sin (10x), HF (x) = 2.1 + 6 sin (0.15x), y(x) = (LF(x),∀x∈ {(3.3,3.9],[3.96,4.3)} HF (x), otherwise Chapter 3. MSCL algorithm 68 with x={3.3,...,4.3}. Two networks with 50 units (with a value of βso αini = 0.5, αfinal = 0.01) were trained for 100 cycles with input data vectors (x, y), one with FSCL and the other with MSCL. The selected magnitude function is focused on detecting high frequency peaks. To accomplish it, MF (m) is chosen as the average of the smooth function SM() for data samples assigned to unit umat time t: SM(xk) = smooth(|y(xk)−y(xk−1)|) (3.41) MF(m) = mean(SM(xk)) ∀xk∈ Rm(t) The smooth function generates a 100 point moving average filter of the series of differences of yin two consecutive points. Figure 3.11 shows that MSCL (black circles) is more efficient than FSCL (blue crosses) to represent high frequency peaks. The value of the magnitude function is also represented (red line) showing high values when y(x) presents abrupt changes, and low values when y(x) is almost constant. Chapter 4 MS-SOM algorithm 4.1 Introduction Soft competitive learning comprises a set of methods were more than a single neuron adapt on presentation of a sample pattern. These algorithms possess some features that are advantageous over hard competitive learning methods: avoiding unused (‘dead’) units, accelerating the learning phase, filling empty areas in the dataset space or avoiding local minima. Self Organizing Maps (SOM) [38] is one of these algorithms with the property of generating topographic organization of neurons in a grid of reduced dimension. This makes SOM useful for visualizing low-dimensional views of high-dimensional data, akin to multidimensional scaling. SOM has also been used for data classification (i.e. [51], [7]). On the other hand, Magnitude Sensitive Competitive Learning (MSCL) [61] is a hard competing algorithm which has the capability of distributing the unit centroids following any user defined magnitude that may have no kind of relation with the data density (as it has been demonstrated in the previous chapter). Comparing both algorithms, the main disadvantage of SOM neural networks against MSCL is that SOM only can distribute unit in direct function of the data density. Only magnification control methods ([81], [54]) present an alternative to SOM that allows the modification of the relation between data and weight vector density for a given model. However, it is important to highlight that in this kind of methods, final unit distribution is always somehow related with data density. In this chapter we describe a new algorithm, Magnitude Sensitive Self Organizing Map (MS-SOM), an hybrid between MSCL and SOM, which synthesizes the advantages of both methods. It preserves the topological properties of the input space and additionally, 69 Chapter 4. MS-SOM algorithm 70 distributes units following a target magnitude. The remainder of this chapter is organized as follows. Section 4.2 describes the proposed MS-SOM algorithm. In section 4.3 the new algorithm is applied to three examples: a toy example with Gaussians to show the algorithm capabilities, 3D surface modelling, and data classification. 4.2 Magnitude Sensitive Self Organizing Maps 4.2.1 The algorithm Magnitude definitions: As in the MSCL algorithm, the user-defined magnitude function, MF(), acts as an extra information for the network, forcing neurons to represent with more detail those zones of data space with higher magnitude values. There exists mainly two situations depending on the data dependency of this function MF (): when magnitude is determined exclusively from input data, MF(X), we define a magnitude vector, mx, that is included as an extra input for the neurons of the map, however, when magnitude function also depends on neuron data, MF(wm(t),X), we define for each neuron man internal variable, mum(t). These unit variables can be represented as a magnitude map Mu(t) with the same dimensionality of the map grid. Only in the second situation, the magnitude value of the winning neuron must be feed back to the rest of the neurons for their updating phase. The examples studied in next sections show both situations: 3D-surface example presents magnitude vector associated with input data, while Gaussian and classification examples present magnitude maps associated with neurons. 1. Initialization Initial codebook Mis formed by Mweight vectors wm(m= 1 ···M) initialized linearly, forming a low dimensional grid (usually 2D). For the case when magnitude depends on neurons, we need to initialize the magnitude map in t= 0 with initial values for Mu(0). Their accumulated magnitudes are maccm. Their initial values at t= 0 are: muk(0) = MF(wm(0), m, X) (4.1) macck(0) = muk(0) (4.2) Chapter 4. MS-SOM algorithm 77 3. SOM and MS-SOM are trained using y(t) as data inputs selected randomly. Magnitude function for MS-SOM depends on each unit and has the following value: mum=K·1−max(ξm) (K−1) (4.13) where ξmis the vector formed by the last Kcomponents of weight vector wm. This vector, ξm, acts as a counter of samples of each class captured by unit. By this way, magnitude is 0 if unit only have data samples of one class, or close to 1 in the situation of maximum confusion between the Kclasses. Then, (max(ξm) = 1/K), 4. After training, the class assigned to each unit is: class() = argmax(ξ) (4.14) In this classification comparative, we used three data sets: the Iris Dataset [31] and two downloaded from the Proben1 library [67]. First one consists of 150 samples from three species of Iris (Setosa, Virginica and Versicolor). The second dataset presents 6 types of glasses; defined in terms of their oxide content (i.e. Na, Fe, K, etc). The Third dataset is based on patient data to decide whether or not a Pima Indian individual is diabetes positive. Number of samples, inputs and classes are specified for each problem in Table 4.2. SOM and MS-SOM were trained with the same parameters, with ratios within [3,0.05] using a Gaussian neighbouring function and a decreasing learning factor. Both neural networks received the same linear initialization. Map sizes for all the problems are displayed in column Map of Table 4.2. MS-SOM uses a value of β= 1. Table 4.2 shows the mean classification error (CE) and the mean Weighted MSE (WMSE) averaged in 20 trainings with each dataset. CE is the total number of samProblem Samples/Inputs Classes Map CESCEMS W MSESWMSEMS Iris 150 / 4 3 [ 5x3] 0.012 0.002 0.643 0.556 Glass 214 / 9 6 [ 6x4] 0.244 0.137 1.484 1.306 Diabetes 768 / 8 2 [10x8] 0.076 0.049 1.493 1.366 Table 4.2: Mean classification error (CE) and Weighted Mean Square Error (WMSE) for SOM (with sub-index S) and MS-SOM (MS) obtained after training both algorithms with the three datasets. Additionally number of samples, number of inputs, classes, and map size is displayed for each problem. Chapter 4. MS-SOM algorithm 78 ples associated to an erroneous class after each test, divided by the number of samples in the dataset. Columns CESand CEMS display classification errors for SOM and MS-SOM respectively. Columns W MSESand W MSEMS are the equivalent for the Weighted Mean Square Error. It is clear that in the three problems, MS-SOM with units focused in the limits between classes is able to distinguish more accurately the class to which each sample belongs to (it has lower CE error). The reason is that MS-SOM leave few units in areas with no class confusion (where classification error is null) while many of the units tend to be in the limit between classes. On the other hand, WMSE reflects the quantization error, focussing in areas of high magnitude. This measure is lower in MS-SOM algorithm, what means that its centroid density is higher in the decision regions, giving as result a better performance in the classification task. Figure 4.2 shows a MS-SOM trained with the iris dataset: (a) Map with colours depending on the classes for each unit (interpolating colours mean that a unit has samples from different classes), (b) map with the final assigned class for each unit, and (c) magnitude associated to each unit. In the magnitude map, limits between the three classes are more clearly represented because MS-SOM tends to distribute units in the decision regions between contiguous classes. Chapter 4. MS-SOM algorithm 79 Figure 4.2: Classification results for MS-SOM. Iris example: (a)map with colours depending on the classes for each unit (interpolating colours mean that a unit has samples from different classes), (b) map with the final assigned class for each unit, and (c) magnitude associated to each unit (clearer grey means higher magnitude). In this representation, the map size (10x6 units) was bigger than the one used in the comparative to highlight the value of the magnitude in zones of high class confusion. Glass example: (d)Results of training a (17x11) grid with SOM. (e) Corresponding results of MS-SOM. Chapter 5 Masked MSCL algorithm 5.1 Introduction In chapter 3we have explained the MSCL algorithm in detail. MSCL as many competitive learning algorithms use homogeneous dataset in the sense that each of the samples has to have the same dimension (the number of components), and the trained neural network also has the same dimension. Similar issue affects MS-SOM. However sometimes, due to the nature of the dataset, some of the data samples may have unknown values for any of its components. This forces to some kind of preprocessing that usually introduces undesired artifacts during training. There may be different reasons for the inconsistency in the dataset’s component size. Data collected in different periods of time or by different entities may be inconsistent. For instance meteorological data may lack of some variables as wind velocity when remounting may years ago, or just come from different meteorological stations. Then, it is no possible to process directly this dataset with common competitive learning methods. To do it, incomplete components in some of the samples must be dealt in some way. Another example is statistical information about citizens in different countries. Even though there are international entities that are doing a huge effort to unify measures, they are usually different in some way. Here we present a masked version of MSCL that is able to deal with data samples of different size (we speak of ’masked’ data). To use this algorithm we will consider that each data sample consists in two vectors, x(t) = (x1,...,xD)(t)∈RDthe data vector itself (with the maximal possible dimension of a data sample D), and its corresponding mask msk(t) = (msk1, . . . , mskD)(t)∈RD. The mask is a vector with ones in the valid components of x(t) and zeros for the rest. 80 Chapter 5. Masked MSCL algorithm 81 The new algorithm will imply the use of vectors of length equal to Dinstead of scalars for the accumulated magnitude of each unit (macci(t) = (macci1, . . . , maccin)(t)∈RD), and also for the learning vector (alpha = (α1,...,αn)∈RD). 5.2 The masked MSCL algorithm The next subsections describe the algorithm in an sequential mode, where units are adjusted after a presentation of each sample. 5.2.1 Initialization Initialized the neural network Mto contain M units: M={u1, u2,...,uM}(5.1) with unit weights wm∈RD(corresponding to unit um) the value of randomly selected inputs from the dataset: wm(0) = x(m)m= 1 . . . M (5.2) Then, unit magnitude might be initialized from the magnitude function depending only on unit parameters (equation 5.3a), or alternatively by the value of the magnitude at the selected sample data for each unit (eq. 5.3b). Obviously, this function has to be able to deal with different sized input vectors, and return a scalar value. mum(0) = MF(msk(t)◦wm(0), < m >),(5.3a) mum(0) = mx(m),(5.3b) Finally, initial values for the magnitude accumulated vectors are: maccm(0) = mum(0) ·msk(m) (5.4) 5.2.2 Random selection of data samples A sample data x(t) and its corresponding mask, msk(t) is randomly selected at time t from the dataset. This process will be repeated until every data has been presented to the masked MSCL neural network. Chapter 5. Masked MSCL algorithm 82 5.2.3 Global unit competition Kunits with minimum distance from their masked weights to the masked input data vector are selected as winners in this first step. In this case distance is calculated considering only valid components in msk(t) for both vectors. Once again we form the Sset. S ∈ M such that: kmsk(t)◦(x(t)−ws(t))k<kmsk(t)◦(x(t)−wm(t))k ∀us∈ S ∧ um/∈ S .(5.5) 5.2.4 Local unit competition In the local competition step, winner unit jis selected from units belonging to Sas the one that minimizes the product, component by component, of its magnitude value as in equation 5.6-top or the accumulated magnitude, eq. 5.6-bottom, using the distance of its weights to input data vector calculated in the pvalid components. It follows: j=     argmin us∈S kmuγ m·(msk(t)◦(x(t)−wm(t)))k,or argmin us∈S kmaccm(t)γ◦(x(t)−wm(t)))k (5.6) The use of mu in local competition is more adequate than macc when the goal of training is Qerr reduction while macc is better to reduce the entropy. 5.2.5 Winner update First it is necessary to calculate the value of the magnitude vector associated to the input sample mx(t). It may have two definitions depending if the magnitude function depends directly on the input, or it is calculated from the magnitude at the BMU(t) of the input sample: mx(t) =    MF(msk(t)◦x(t)) ·msk(t),if depends on sample magnitude muj(t)·msk(t),if depends on BMU’s magnitude (5.7) This vector is used to update the accumulated magnitude at winner unit: maccj(t+ 1) = maccj(t) + mx(t) (5.8) Chapter 5. Masked MSCL algorithm 83 Then, only valid components (those with mskd= 1) of winner weights are updated: wjd(t+ 1) = wjd(t) + αd(xd(t)−wjd(t)) , d :mskd= 1 (5.9) where alpha is the learning factor vector for the winner calculated as the element-wise division between mx and maccjpowered to β. Using this definition of alpha(t), only valid components at time tof winner weight are updated. The value of its kcomponent is: αk(t) =   mxk(t) maccjk (t+1) β,if mskk= 1, 0,otherwise (5.10) 5.2.6 Magnitude update Only winner’s magnitude is adjusted iteratively for each training sample, following eq.3.23 if magnitude is given by a value associated to each input sample, or eq.3.24 otherwise. The mean value of alpha in the valid components is used as mujis an scalar: mum(t+ 1) =    mum(t) + mean(alpha(t)) ·(mx(t)−mum(t)) ,if MF(x(t)) is used. MF(wm(t+ 1), < m >),otherwise. (5.11) 5.2.7 Stopping condition Training finish when a termination condition is reached (this condition may be the same as in the MSCL algorithm). 5.3 The masked MS-SOM algorithm The masked MS-SOM algorithm follows the same steps and equations as the masked MSCL algorithm excepting in the following points: •mx takes different values for different units taking into account the unit neighboring function, hij following: mxi(t) =    hij ·MF (msk(t)◦x(t)) ·msk(t) hij ·muj(t)·msk(t) (5.12) Chapter 5. Masked MSCL algorithm 84 Unit neighboring function may be defined depending on the grid distance between each unit iand the winner jin different ways, for instance: hij =exp distance(i, j)2 2σ2(5.13) •alpha and macc are calculated for every unit, not only for the winner. •All units are updated at each step. 5.4 Experimental results We perform a simple example to demonstrate the capability of the MSCL and MS-SOM in their ’masked’ implementation to deal with incomplete data. To do it, we first set up a synthetic data set X, consisting of P= 3000, 3D samples (x(t)∈R3) drawn from a mixture of three Gaussian distributions with means [0,0,0], [1,1,1] and [0 0.35 0.65], and covariance matrix [0.02 0 0; 0 0 0.02; 0 0.02 0] for all of them. All of the three gaussians have 1000 samples. Additionally, we generate a ’mask’ matrix with the same size as X, so that its i-th row vector corresponds to the mask of x(t), to indicate if that component is valid or not. Each component of this mask vector takes a value of 1 (with probability of 70%) or 0 (with probability equal to 30%). Figure 5.1 shows the dataset used in the algorithms, and the corresponding mask. We trained a MSCL and a MS-SOM neural networks in two cases, directly with dataset X, an also using the ’mask’ matrix. Codebooks neural networks have 10 units in both cases. For training, we tested two different magnitude functions. First a constant value equal to one (it is the same than training directly with the basic CL algorithm, and SOM). Tests were repeated using the absolute value of first component of each sample as the magnitude function. Figure 5.2 shows final results for training the MSCL in the four cases (two magnitude functions, and direct(graphs in top row)/masked(graphs in bottom row) training). It can be seen that there is no appreciable difference between the use or not of the mask. Using magnitude equal to one, units spread homogeneously in the three Gaussian distributions in both cases. Using the magnitude funtion as MF(t) = abs(x1(t)), units are mainly allocated in the Gaussian with higher value of first component of each sample. Similar situation can be appreciated in Figure 5.3, that shows final results for training the MS-SOM in the four cases (two magnitude functions, and direct(top)/masked(bottom) Chapter 5. Masked MSCL algorithm 85 Figure 5.1: Dataset matrix (left) and corresponding mask(right). This dataset corresponds to the three 3D Gaussian distributions. Mask matrix indicates valid components of each sample (in white), or invalid (30% of components, in black). Chapter 5. Masked MSCL algorithm 86 0 0.5 1−0.4 −0.2 00.2 0.4 0.6 0.8 11.2 1.4 0 0.5 1 (a) 0 0.5 1−0.4 −0.2 00.2 0.4 0.6 0.8 11.2 1.4 0 0.5 1 (b) 0 0.5 1−0.4 −0.2 00.2 0.4 0.6 0.8 11.2 1.4 0 0.5 1 (c) 0 0.5 1−0.4 −0.2 00.2 0.4 0.6 0.8 11.2 1.4 0 0.5 1 (d) Figure 5.2: Final results of a trained MSCL with 10 units using two magnitude functions. On top, row figures represent direct training without taking the mask into consideration. Bottom shows masked version of MSCL (using mask shown in figure 5.1). Left column uses constant magnitude function equal to one. Right column uses as magnitude function the absolute value of first component of each sample. Chapter 6. Magnitude Sensitive Initialization 93 −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 (a) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (b) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (c) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (d) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (e) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (f) Figure 6.1: (a) Dataset used in the examples of this chapter (with color coding according to the magnitude associated to each sample) and codebooks of 80 units initialized with the different methods: (b) Random init, (c) KKZ algorithm, (d) Kmeans++ algorithm, (e) MS-INITmax algorithm and (f) MS-INITprob algorithm. mx(x) = abs(x2) (6.14) Figure 6.1(b)−(f) shows the results of initializing a codebook of 80 units with the five methods. In blue it is represented the dataset, while unit centers are the coloured circles. 6.4.1 Initialization example In this example, each test consists on the initialization of three codebooks of sizes M = [40,80,160] using the following methods for initialization: •Random init: Directly M samples are selected at random to form the codebook. •KKZ: Implemented with MS-INIT using magnitude = 1, maximizing d(x). •K-Means++: Implemented with MS-INIT using magnitude = 1 and following the probability of d(x) Chapter 6. Magnitude Sensitive Initialization 94 •MS-INITmax: Following equation (6.12b). Therefore, maximizing the product mx(x)· d(x). •MS-INITprob: Following the probability of the product mx(x)·d(x), as indicated in eq. (6.12a). Since all algorithms under test select first unit randomly, what could affect the final result, we ran 100 trials for every case. As a measure of performance quality of the new method we use magnitude-weighted versions of MSE, and normalized Entropy. Table 6.1 shows the means (in 100 trials) of weigthed MSE, while table 6.2 shows the means of weigthed entropy. By rows are ordered three different codebook lengths: 40, 80, and 160 units, and by columns shows results of applying the five initialization algorithms. Every three possible training schemes after each initialization are marked with: None, Kmeans and MSCL. Results of training the neural network after initialization (with different methods) are explained in next section. The number of units affects quantization in a inverse proportion and entropy in a direct way. Higher number of units means lower value for the Weighted MSE and higher Weighted Entropy (that tends to a value of one when normalized). For the None situation in the tables, the representation is obtained with the initialization method without training. Comparing these values the initialization algorithm that yields worse results is random init as expected (except in the case of low number of units where KKZ forces units to take the value of extreme samples in the dataset and therefore the weighted quantization error increases). KKZ tends to distribute codewords uniformly in the data space, so becoming very expansive (some of the reference vectors are in the limits of the three Gaussian distributions). K-means++ also distributes codewords at random but with a unit distribution that tends to follow the data density distribution. However, all of these methods are still worse than MS-INIT when the goal is reducing the quantization error following a magnitude function. When goal is achieving high entropy, worse results are for KKZ and MS-INITmax as none of these two algorithms achieve an uniform probability distribution (as it can be seen in table 6.2 in the rows of training equal to ’None’). In general, implementations of MS-INIT achieve better results, but it is clear that using MS-INITprob is advantageous against the use of MS-INITmax regarding the performance results. In figure 6.1 it can be seen that few more units are distributed in the limits of Gaussian dataset with highest magnitude than in the case of MS-INITprob. Chapter 6. Magnitude Sensitive Initialization 95 Units Training Random KKZ Kmeans++ MSINITmax MSINITprob 40 None 0.678 (0.049) 0.757 (0.038) 0.621 (0.031) 0.655 (0.030) 0.578 (0.019) Kmeans 0.535 (0.024) 0.525 (0.010) 0.528 (0.020) 0.496 (0.006) 0.499 (0.010) MSCL 0.475 (0.010) 0.474 (0.007) 0.470 (0.007) 0.464 (0.006) 0.468 (0.007) 80 None 0.485 (0.039) 0.468 (0.017) 0.433 (0.016) 0.417 (0.012) 0.392 (0.015) Kmeans 0.371 (0.012) 0.365 (0.005) 0.367 (0.011) 0.349 (0.004) 0.339 (0.006) MSCL 0.336 (0.006) 0.337 (0.004) 0.334 (0.006) 0.325 (0.003) 0.322 (0.003) 160 None 0.342 (0.016) 0.300 (0.006) 0.297 (0.010) 0.270 (0.004) 0.267 (0.005) Kmeans 0.245 (0.009) 0.251 (0.004) 0.243 (0.008) 0.229 (0.002) 0.224 (0.003) MSCL 0.231 (0.007) 0.233 (0.002) 0.231 (0.005) 0.220 (0.001) 0.217 (0.002) Table 6.1: Table shows the mean values in 100 tests of the Weighted Mean Square Error (WMSE) calculated in three codebooks (sizes 40, 80 and 160) after applying five initialization algorithms (Random, KKZ, Kmeans++, MSINITmax and MSINITprob). Each of these codebooks is trained following one of three possibilites: No training / Trained using Kmeans / Trained using MSCL (with the same magnitude funcion as for MS-INIT). Units Training Random KKZ Kmeans++ MSINITmax MSINITprob 40 None 0.857 (0.035) 0.752 (0.012) 0.874 (0.021) 0.804 (0.019) 0.914 (0.016) Kmeans 0.890 (0.022) 0.893 (0.007) 0.896 (0.017) 0.927 (0.006) 0.928(0.010) MSCL 0.956 (0.010) 0.954 (0.004) 0.958 (0.008) 0.970 (0.004) 0.970 (0.006) 80 None 0.878 (0.027) 0.804 (0.011) 0.890 (0.014) 0.849 (0.010) 0.940 (0.010) Kmeans 0.900 (0.017) 0.892 (0.006) 0.902 (0.014) 0.925 (0.004) 0.946 (0.009) MSCL 0.948 (0.009) 0.949 (0.005) 0.951 (0.007) 0.976 (0.002) 0.974 (0.006) 160 None 0.900 (0.016) 0.841 (0.006) 0.904 (0.010) 0.886 (0.004) 0.945 (0.005) Kmeans 0.917 (0.009) 0.885 (0.004) 0.913 (0.008) 0.927 (0.002) 0.952 (0.003) MSCL 0.944 (0.007) 0.942 (0.002) 0.944 (0.005) 0.968 (0.001) 0.971 (0.002) Table 6.2: Table shows the mean values in 100 tests of the normalized Weighted Entropy calculated in three codebooks (sizes 40, 80 and 160) after applying five initialization algorithms (Random, KKZ, Kmeans++, MSINITmax and MSINITprob). Each of these codebooks is trained following one of three possibilites: No training / Trained using Kmeans / Trained using MSCL (with the same magnitude funcion as for MS-INIT). Chapter 6. Magnitude Sensitive Initialization 96 −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (a) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (b) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (c) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (d) Figure 6.2: Final results after training with K-means a codebook with 80 units, using different initialization methods: (a) KKZ algorithm, (b) Kmeans++ algorithm, (c) MS-INITmax algorithm and (d) MS-INITprob algorithm. 6.4.2 Training example Next example has been developed to show the effect of different initialization schemes in the final codebook of a competitive neural network after training. To do it we apply the initialization methods used in the previous example to three MSCLs of different size (also 40, 80 and 160 units) and to three K-Means neural networks, with the same number of clusters, K. Performance measures will be the same than in the initialization example. Training is made in batch mode in all the cases using: •K-Means: Repeating training during 10 cycles. Chapter 6. Magnitude Sensitive Initialization 97 •MSCL: Training each neural network during 10 cycles, and 5 epochs each cycle. Selected magnitude function will be the same than the used for MS-INIT. Figure 6.2 shows final training results of 80 centroids using K-means following the initialization methods: KKZ (a), K-Means++ (b), MS-INITmax (c) and MS-INITprob (d). Figure 6.3 shows final training codebook of the MSCL with 80 units, being initialized as in figure 6.2. Tables 6.1 and 6.2 also show the quality results after training the with K-means neural networks and the MSCLs respectively. As in the previous example, neural networks with more units present better results. MS-INIT has lower values in WMSE and higher Weighted Entropy than the other three initialization algorithms. Once again, KKZ and MS-INITmax have lower values for entropy due to the fact that both algorithms tends to select some of the unit weights from data samples in the limits of the distributions. Obviously, as the selected magnitude function for training the MSCL is the same than in the MS-INIT method, MSCL gets better final center representations than K-Means. Finally it is worth noting the fact that optimal values are achieved using MS-INIT and then training a MSCL with the same magnitude function. Besides, it is preferable training a MSCL while using random initialization, than only initializing the codebook with MSINIT and performing no subsequent training. Chapter 6. Magnitude Sensitive Initialization 98 −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (a) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (b) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (c) −2 0 2 4 6 8 −3 −2 −1 0 1 2 3 4 5 6 7 (d) Figure 6.3: Final results after training a MSCL with 80 units, using different initialization methods: (a) KKZ algorithm, (b) Kmeans++ algorithm, (c) MS-INITmax algorithm and (d) MS-INITprob algorithm. Part III APPLICATIONS 99 Chapter 7 Color Quantization with MSCL 7.1 Introduction With the informatics development of society, large amount of scanned documents and images are transmitted and stored, therefore it would be desirable to reduce the number of colors in an image to reduce storage and transmission costs. This is generally achieved by mean of Vector Quantization techniques called Color Quantization (CQ) where each data sample is a vector representing the color of a pixel. They are important in certain applications related to segmentation, compression, and transmission of images. Some of the most common competitive learning methods, or their variants, have already been used in CQ and Color Segmentation tasks. Uchiyama and Arbib [75] developed Adaptive Distributing Units (ADU), a CL algorithm used in Color Segmentation that is based on a simple cluster splitting rule. More recently, Celebi [12] demonstrated that this algorithm outperforms other common algorithms in a CQ task. Fuzzy C-Means (FCM), is a well-known clustering method in which each sample can belong to more than one cluster [10]. In [13], Celebi presented a relevant work using Neural Gas Networks. SOM has also been used in color related applications: in binarization [59], segmentation [43] and CQ [21], [56], [17] and [16] where author presents FS-SOM a frequency sensitive learning scheme including neighborhood adaptation that achieves similar results to SOM, but is less sensitive to the training parameters. One variant of special interest is the neural network Self-Growing and Self-Organized Neural Gas (SGONG) [9], an hybrid algorithm using the GNG mechanism for growing the neural lattice and the SOM leaning adaptation mechanism. Author proved that it is one of the most efficient Color Reduction algorithms, closely followed by SOM and FCM. 100 Chapter 7. Color Quantization with MSCL 101 In this chapter we propose the use of a MSCL neural network in the CQ task. As a result of the training process, units will distribute according to the salient pixels in the image, where different definitions of saliency are used as magnitude functions. Final color palette will therefore enhance salient areas of the image. 7.1.1 Problem formulation Given an image I of size (xmax, ymax), we define a data sample x(t) from the pixel I(x,y) as the color vector of that pixel in the coordinates in the corresponding color space: Figure 7.1: Problem formulation of Color Quantization: pixels are considered 3-dimensional vectors that are processed as inputs for a competitive neural network with many units as colors in the palette. Magnitude value can be associated to the pixel, as another input to the network, or be associated to the units, as an internal parameter. Chapter 7. Color Quantization with MSCL 102 x(t) = Color(I(x, y)), x = 1..xmax and y= 1..ymax (7.1) t= 1..P, where P=xmax ∗ymax .(7.2) Each pixel receives an additional value for the magnitude function, MF(t). This function is proposed as to weight each pixel with a value of interest. As higher is the value of magnitude, more interesting is the pixel. The goal is training a neural network to get units representing the colors of the interesting pixels in higher detail. The prototype of unit m(m= 1 . . . M) is represented by a vector of weights in the 3-dimensional color space. The associated value of the magnitude in that unit, mum(t), can be calculated from the values of MF(t) at samples in its Voronoi region, or can be introduced to the network as the rest of input data. Figure 7.1 shows this process. From one image (tiger example), we get a dataset with the 3-D color coordinates of each pixel. The dataset is presented to the competitive neural network to generate the color palette with as many colors as units in the network. In the bottom of the image, the color distribution of the image using a [R G B] color space is shown. 7.1.2 Proposed approach We propose the use of MSCL neural network, to train this 3-D dataset, taking into account the magnitude function, which can be defined to lead the training process of the palette to accomplish any desired task. 7.1.3 Chapter description The remainder of this chapter is organized as follows: Section 7.2 shows the comparison of the MSCL with some of the well known competitive learning algorithms, using five different examples of applications. The first example gets a color quantization that we call homogeneous quantization (Subsect. 7.2.1). The second example gets a color quantization focused in the image center (Subsect. 7.2.2). The third example is focused on getting a color palette avoiding the dominant colors usually found in image background (Subsect. 7.2.3). Fourth example returns a color palette according with a certain image saliency (Subsect. 7.2.4). Last example shows the use of MSCL in a document image binarization (Subsec. 7.2.5). Chapter 7. Color Quantization with MSCL 109 Figure 7.5: Results of color quantization for the fish example using an 8-color palette with different methods: a) MSCL avoiding two dominant colors, b) NG, c) FSCL, d) FCM, e) K-MEANS, f) SOM. The corresponding color palettes are shown in the right of each image. As can be appreciated, MSCL gets a more vivid palette for the fish and presents a lower number of colors in the palette dedicated to the background with the anemone. Results of experiments avoiding Dominant Colors. The main problem of the method is to determine the optimum number of dominant colors. So, we propose to calculate the amount of pixels in High Magnitude Regions (HMR) as a measure of the level of detail that the MSCL method has to deal with. The HMR in the image can be estimated with a threshold of the magnitude function that is chosen to be the 50% of the maximum magnitude value. Figure 7.9 shows this process for the fish example in an 8-color palette. Images from top to bottom in each column correspond to number Chapter 7. Color Quantization with MSCL 110 of dominant colors from 1 to 8. The first column represents the value of distcol(t) in form of image (the magnitude map). The second column shows the HMR as the corresponding binarization of the magnitude maps. It is worth noting in this col that there are still quite a lot of pixels in HMR considering only one dominant color (corresponding to the fish and the darker areas in the background of the image). However, when two dominant colors are used, HMR extension is quite reduced and corresponds only to certain areas in the fish. Therefore the use of two dominant colors would be a good option for the fish image. The third column of images in this figure shows examples of the MSCL reconstruction for the corresponding number of dominant-colors avoidance. As comparison, Fig. 7.10 shows in three columns the resulting HMRs for the other three images. In the first column, the flower image presents an interesting behavior for four dominant colors. In the tower image we have a similar situation, but for three colors (white, blue and dark grey). However, the goat image tends to keep similar HMR extensions. The most possible reason for this behavior is that the image is quite monochromatic. In order to visualize the effect of the number of dominant colors, we define the HMRratio as the number of pixels in HMR divided by the number of pixels in the image. We generated 50 palettes of dominant colors for each number of colors that varied from 1 to 20. The evolution of the averaged HMR-ratios are shown if the bottom graph of Fig. 7.8. The curves in the graphs have been smothered. The abscissa shows the different number of dominant colors analysed in the four images. The ordinates show the mean value of the HMR-ratio. A lower value in this ratio means that there are fewer pixels in the image far from the dominant colors. Therefore that palette is a good representative of the dominant colors in the image. The evolution of HMR for the fish image shows that there is an abrupt fall in this value from using one or two dominant colors. This ratio tends to keep consistent until 7 dominant colors are used. An explanation of this behavior can be visualized in Fig. 7.9 (image in row 7 and second column) where the dark band in the background is far from any dominant color, which makes the HMR-ratio to grow considerably in the bottom graph of Fig. 7.8. It would be possible to detect the optimum number of dominant colors by analysing the HMR-ratio behavior, like detecting relative minimums or thresholding its variation, which is left for future work, as it is out of the scope of this work. In order to evaluate the performance of the methods in the HMR, we propose to calculate the Sum Square Error of quantization (SSE) in the HMR, divided by the total SSE in the image, that we will call the SSE-ratio. Graphically this can be appreciated Chapter 7. Color Quantization with MSCL 111 in Fig. 7.8 (top four graphs corresponding to the four example images). The abscissas in the graphs show several numbers of dominant colors, from 1 to 5, when dealing with generation of 8-color palettes. The different algorithms (FSCL, FCM, NG, K-MEANS, SOM and MSCL) were simulated 50 times to show the averaged SSE-ratio. As it can be seen, MSCL always presents the smallest SSE-ratio, for all the images and different number of dominant colors. That means that MSCL with dominant-color avoidance is able to maintain a reduced amount of error in the HMR, while the others methods tend to concentrate their SSE reduction in the rest of the image. 7.2.4 CQ Focused in salient colors Figure 7.6: Saliency example. Top row, from left to right: Original image, saliency map (clearer values for high saliency), the mask binary image used for MSE measurement and (bottom row, from left to right) the reconstructed image with an 8-colors palette from: SOM, FS-SOM and MSCL focused on the saliency. The aim of salient feature detection is to find distinctive local events in images. Some works ([77]) exploit the possibility of color distinctiveness in salient detection. This example shows the MSCL algorithm generating a color palette focused on those salient regions. To achieve that, the chosen magnitude function is the mean computational global saliency (defined as in [77]). The magnitude is normalized by the maximum, and varies from one to values near zero in zones with low saliency (see image in Fig. 7.6 in the middle of the top row). We used 8 colors with decreasing learning rates between 0.7 and 0.01 for every Chapter 7. Color Quantization with MSCL 112 algorithm. Figure 7.6 shows an example. The first two algorithms (SOM, FS-SOM) only obtain a red color and present higher MSE values (SOM: 103.21 and FS-SOM: 103.07) in those pixels belonging to the white mask region of saliency (right top image of Fig. 7.6). However, using the global saliency (middle top image of Fig. 7.6) as the magnitude for MSCL, the resulting image shows three red variants and the MSE error is lower (87.5). A drawback is that other colors are under-represented, what means a minor problem if we want to detail the salient regions of the image. 7.2.5 Image binarization Binarization of a text grey-scale image is the process of assigning each pixel of a text image depending of its grey-scale value to one of two classes, one corresponding to the text and the other one to the background. First row of Fig. 7.7 shows the image of a badly illuminated document (image a), and the results of applying classical binarization algorithms: Otsu method (b), filtering of original image with Laplacian operator (c) and its binarization with Otsu (d). Otsu Method definitely fails to get an adequate binarization because of the dark grey values in the right margin of the paper. Filtering with Laplacian operator provides a better result, because it is an edge extraction mask. However, this method does not fill the letters. Figure 7.7: Binarization example: in top row (a) original image, (b) Otsu method, (c) filtering with Laplacian operator, and (d) its binarization with Otsu; in bottom row (e) SOM, (f) MSCL in homogeneous grey quantization, (g) MSCL with two features, and (h) Otsu binarization of (g). Chapter 7. Color Quantization with MSCL 113 Competitive learning can be used for this application by training 2 units to represent two levels of gray-scale, which should correspond to the background and foreground classes. Second row of Fig. 7.7 shows the results with: (e) SOM, (f) MSCL in homogeneous grey quantization, (g) MSCL with two features (explained below), and (h) Otsu binarization of last example. The MSCL in (f) with only two neurons is equivalent to the Otsu Method. The reason is that the mean quantization error for each unit is proportional to the standard deviation of a data class when using as mean of the data the unit weights that represents the class. The quantization result can be improved by using as input a combination of the graylevel values and the result of Laplace filtering. Therefore data samples will be two dimensional vectors combining the values of both features. Then if we apply MSCL using homogeneous quantization to this combined dataset we will get the two-level image (g) in Fig. 7.7 (the same image with binarized pixel intensity can be seen in next image (h)). This result is better than those achieved by other classical methods. Chapter 7. Color Quantization with MSCL 114 Figure 7.8: The top four graphs correspond to each example image, when dealing with generation of 8-color palettes. The averaged Sum Square Error in the High Magnitude Region (HMR), divided by the total SSE in the image (SSE-ratio) is represented for the different algorithms (FSCL, FCM, NG, K-MEANS, SOM and MSCL). The abscissas in the graphs show several numbers of dominant colors, from 1 to 5. MSCL always presents a smaller SSE-ratio, for all the images and different number of dominant colors. The bottom graph represents the evolution of the averaged HMR-ratios (number of pixels in HMR divided by total number of pixels) when using from 1 to 20 dominant colors. Chapter 7. Color Quantization with MSCL 115 Figure 7.9: Results of CQ of the Fish example in a 8 color palette, avoiding different number of dominant colors: (from top to bottom) with 1 to 8 dominant colors. (In columns): magnitude map, pixels with magnitude value over 50% of the maximum (High Magnitude Region), and MSCL reconstruction for the corresponding number of dominant colors. Chapter 7. Color Quantization with MSCL 116 Figure 7.10: High Magnitude Regions for different number of dominant colors. Images in rows correspond, from top to bottom, with 1 to 8 dominant colors. Images in the left column show the flower example, the column in the middle the tower and the right column the goat image. Chapter 8 MSIC: Magnitude Sensitive Image Compression 8.1 Introduction In the human vision system the attention is attracted to visually salient stimuli and therefore only scene regions sufficiently different from their surroundings are processed in detail. This provides the necessary motivation to devise a novel image compression method capable of applying distinct compression ratios to different zones of the image according to their saliency. In this chapter we make use of the Magnitude Sensitive Competitive Learning Algorithm (MSCL) to get a sensitive image compression. Using saliency as the magnitude, units tend to model more accurately the salient areas of an image, and therefore the neural network behaviour imitates the human vision system. In the context of image processing, basic vector quantization consists in dividing the input image into regular blocks of pixels of a pre-defined size, where each block is considered as a D-dimensional vector. Each of these input vectors from the original image is replaced by the index of its nearest codeword, so only this index is stored or transmitted through the media. The whole codebook serves as a database known on the reconstruction site. This approach reduces the transmission rate while maintaining a good visual quality. Figure 8.1(a) shows this procedure. In VQ, compression level depends on two factors, the number of blocks and the level of compression of each block. Both factors are related in an inverse way. Lower number of blocks means that they are higher in size, and therefore higher is the bit depth necessary 117 Chapter 8. MSIC: Magnitude Sensitive Image Compression 118 (a) Common CL image compression algorithm. (b) MSIC algorithm. Figure 8.1: Basic idea of Competitive Learning algorithms in the task of image compression for grayscale images. Top: Common CL algorithm. Bottom: MSIC algorithm. Differences with other CL algortihms are the use of a MSCL to get block centers (centers are trained weights of MSCL units), the use of irregular blocks and the masked quantization/deprocessing. Chapter 8. MSIC: Magnitude Sensitive Image Compression 125 Figure 8.3: Neural networks used in the MSIC algorithm: Top: BMUMC and BMUIC . It is important to mention that this last MSCL is used also in receiver (BMUIC2). Bottom: Block extraction phase. Each block delivers the block limits, the image and a binary mask. MSCLP ICT (l) neural network, where a input sample (vectorized block from the extraction phase) has several masked components. of the corresponding block. After summing the mean, it is masked by the binary mask and added to the regenerated saliency map. Repeating the process for all the blocks we obtain the regenerated saliency map, that will represent the saliency values of pixels for the reconstructed image. 8.2.4 Image quantization The same process of the previous saliency-map image quantization is followed in this image quantization step. Blocks are extracted training the MSCLIC (with the coordinates at each pixel) to get the image block centers according to the Regenerated Saliency Map at the transmitter. Then the Voronoi regions of each of these centers are calculated. Blocks are extracted and vectorized. After removing the mean, each image block is processed using the masked version of MSCL with the MSCLP IC(l) that corresponds its size, in order to assign it the most similar pictorial content of the library that will be included in the reconstructed image. It is only necessary to send the corresponding block mean and index from the MSCLP IC(l) for each block. Chapter 8. MSIC: Magnitude Sensitive Image Compression 126 (a) Pictorical codebook of size 4x4 (b) Pictorical codebook of size 10x10 Figure 8.4: Examples of MSCLP ICT codebooks. (a) Codebook size l= 4. (b) Codebook size l= 10. These codebooks and others for different sizes are known, in form of library, by the transmitter and the receiver. Chapter 8. MSIC: Magnitude Sensitive Image Compression 127 In the codification of the whole image of the saliency map they are used: 830 (approximate number of blocks) * 15 (bits per block, one byte for block index and 7 bits for block mean) = 13690 bits. The number of blocks vary slightly in the tests to get a final number of bytes equivalent to JPEG (including map quantization) for a desired compression quality, as indicated in second column of table 8.1. 8.2.5 Map restoration at receiver Map restoration at receiver is accomplished following exactly the same process than map restoration at transmitter. To do it, the receiver uses block Map index, mean block-saliency, block-center and the same offline MSCLP IC(l) picture library. As operations are the same and they are applied to the same data, the Regenerated Saliency Map at receiver is exactly the same than the one at the transmitter. 8.2.6 Image restoration Last step in the whole process is image restoration, using the received means of blocksaliency, the pixel indexes and the regenerated saliency map. This step is similar to the previous described Map restoration with small changes. The main difference is that the image block centers are not available (they have not been transmitted). They are calculated training a new MSCL (MSCLIC2), with the coordinates of each pixel, and the magnitude values in the Regenerated Saliency Map (magnitude that was calculated with eq.8.1 at the emitter). This neural network becomes identical to MSCLIC. The weights of MSCLIC2are the centers of the image blocks, and their Voronoi regions define the masks and limits. Once again, image indexes are presented to the look-up table created with MSCLP IC(l) (according to the block size) that returns the block shape. Final image is regenerated by adding means of block-saliency, masking each block and positioning it in the image (adding it to the regenerated image as we had done before with the saliency-map image). 8.3 Extension to color images Figure 8.5 defines the flowchart to use MSIC in the case of color images. The process is similar to the used in the case of grayscale images, but applied to each of the color components of the image. First, we calculate the saliency map from the color image. With this saliency map we extract and quantify blocks (as described in Subsect. 8.2.2), blocks which are restored at Chapter 8. MSIC: Magnitude Sensitive Image Compression 128 Figure 8.5: Global algorithm for color images. Each color component is processed separately as in the grayscale method. However this process is exemplified in the text with a different magnitude definition for the saliency map, oriented to preserve the detail of the image for certain colors selected by the user. transmitter as mentioned in 8.2.3. As a result of this step we get the map block-centers, block-means and indexes. Encoding is made with the previously trained MSCLP IC(l) picture library. Then, original RGB image is transformed to the L-a-b color space. The reason of selecting this color codification is that it has been demonstrated its suitability for interpreting the real world [18]. Now with these L-a-b color components of the image, we follow the process indi- Chapter 8. MSIC: Magnitude Sensitive Image Compression 129 cated in Subsect. 8.2.4. Each of them will be trained with a MSCL neural network (MSCLIC−L, MSCLIC−a, MSCLIC−b,) and it will return the block sizes and indexes for each component. The indexes of the blocks are also encoded with MSCLP ICT (l). Once at receiver saliency map is restored (see Subsect. 8.2.5). Then, we follow the image restoration step, applied to each L-a-b component. Its centers are calculated training three MSCL networks (MSCLIC2−L, MSCLIC2−a, MSCLIC2−b,), with the coordinates of each pixel, and the regenerated saliency map. These neural networks becomes identical to those at the transmitter. To get the final image, we transform the restored L-a-b images to RGB. 8.4 Experimental results 8.4.1 Grayscale images Simulations were conducted on four 256x256 gray scaled images (65536 bytes), all of them typical in image compression benchmarking tasks. We applied the MSIC algorithm, with the following MSCL training parameters: 15 cycles and βcalculated so the learning factor vary along the training process from 0.9 to 0.05. We used Graph-Based Visual Saliency GBV S(x) ([27]) as the pixel saliency of the corresponding sample. However, it is possible to use other kind of magnitudes to define which areas of the image are compressed more or less deeply. JPEG was applied with the standard Matlab implementation and a compression Quality of Q = 3 or Q=5 (i.e., with a high compression ratio). Image Q/Bytes JPEG(Tot/50%) SOM(Tot/50%) MSIC(Tot/50%) Lena Q5/2010 212.3/340.4 205.4/374.0 501.1(18.2)/211.0(6.1) Street Q5/2127 302.3/369.0 322.1/465.3 466.2(7.8)/210.6(4.2) Boat Q5/1988 263.9/383.7 280.4/486.6 436.4(12.3)/282.0(5.6) Fish Q3/2090 485.7/597.7 466.3/904.3 895.8(15.8)/254.2(9.6) Table 8.1: Mean MSE for the whole image as well as for areas with saliency over 50% (grayscale example). Standard deviation is also shown (in brackets). We also compared with the algorithm described in [45], whose main steps are followed for all the mentioned SOM based algorithms: The original image is divided into small blocks (we select a size of 8x8 to achieve a similar compression ratio to JPEG or MSCL). Then, 2-D DCT is first performed on each block. The DC term is directly send for reconstruction, and the AC terms after low-pass filtering (we only consider 8 AC coefficients) is fed to a Chapter 8. MSIC: Magnitude Sensitive Image Compression 130 SOM network for training or testing. All experiments were carried out with the following parameters: 256 units, 5 training cycles and the learning factor decreases from 0.9 to 0.05. The number of bytes used to compress each image was the same for MSCL and JPEG (see Table 8.1) and fixed to 2048 for SOM. For evaluation purpose, we use the mean squared error (MSE) as an objective measurement for the performance. Table 8.1 shows the resulting mean of the MSE in 10 tests using our algorithm compared to JPEG and SOM applied to 4 test images. We present a second column showing the value of MSE but only calculated in those pixels which saliency is over 50%. Standard deviation is also shown (in brackets). To obtain the generic pictorial library MSCLP IC(l) we used three additional images different to the images used in testing from [30] with the same training parameters. This number is quite low, but enough to show the good performance of our proposal. However, in a real scenario it would be necessary to use a higher number of images to get a suitable pictorial library. Moreover, we have not used any entropic coding applied to MSCLP IC indexes which would have result in a further compression. As expected, the MSE value calculated for the whole image area given by JPEG is lower than the one provided by MSIC, because in this algorithm prototypes tend to focus on zones with high saliency while other areas in the image are under-represented. However, when MSE was calculated taking into account only those pixels with high saliency, MSIC obtained better results than JPEG or SOM. This effect can be clearly appreciated by visual inspection of the images represented in Fig. 8.6. They show how MSIC achieves a higher detail level at image areas of high saliency. In the case of JPEG, it tends to fill up big portions of the image with plain blocks, being unable to obtain a good detail at any part of the image. On the other hand, SOM produces slightly blurred images due to the low frequency filtering. The new algorithm could also be used in image compression applications with other magnitude functions instead of saliency. Fig. 8.7 shows the compressed results of applying MSIC using different Magnitude Functions to the street image. From left to right, first image is the original one, second image is MSIC using the same Magnitude Functions that the one used in eq.8.1. The Magnitude function in third image corresponds to 8.1, but using 1 −GBV S(x) instead of the pixel saliency. The fourth image uses the value of the vertical coordinate (normalized to one) and finally the fifth one uses the value of the vertical coordinate (normalized to one) minus one. It can be clearly seen that depending on the defined Magnitude Function, certain areas are compressed in higher quality than the rest of the image (foreground, background, top or bottom of the image). Chapter 8. MSIC: Magnitude Sensitive Image Compression 131 Figure 8.6: Top in columns: Original image, saliency map, MSIC, JPEG and SOM compression for the test images. Bottom: Lena detail in the three methods. It can be clearly seen that the Lena face, compressed with MSIC shows a more natural view (altmost like painted with Pointillism technique) than the other methods that have square block borders. Chapter 8. MSIC: Magnitude Sensitive Image Compression 132 Figure 8.7: Original ’Street’ image and the compressed images using MSIC with four different Magnitude Functions. This toy example was only presented to show the possibilities of achieving selective compression in different areas of the image just by varying the Magnitude Function. MSIC algorithm is much more slower than JPEG. In a serial execution on single core computer, JPEG processing takes only 0.11% of the total processing time used by MSIC (that in our tests it take 6,8 seconds for compressing each of the grayscale test images). Most of the time (91.6%) is spent on block extraction (34% of which is used in extracting blocks from the saliency map and 66% in extracting blocks from the image). Block encoding and decoding takes 6.7% of the time, and 1.7% the rest of the algorithm. However processing time may be reduced using parallel processing and compiled libraries (now simulated in Matlab). The slowest task is finding the best matching unit to define the Voronoi region to extract a block, and in the encoding-decoding task. BMU finding represents the 68% of the block extraction time, and the 51% of the encodingdecoding time. It is a slow process because in our sequential implementation we must, for each sample, calculate the distances from it to each of the units. In a parallel implementation, this processing could be applied simultaneously for all units. Then, using for instance 1000 units, block extraction time could be only 29.3% of initial total time. Using similar approach for encoding-decoding the final processing time can be reduced to be 2.3 seconds (34,3% of the original processing time). 8.4.2 Color images In the color experiments, it is applied the method explained in section 8.3, with the same parameters used in the grayscale case. Now we use a different saliency definition focused in those image zones with colors selected by the user. This type of compression, preserving with more detail image zones with certain color selection, may have several applications. For instance, in medical images, the specialist may define the colors of those areas that has to be well preserved. Other Chapter 8. MSIC: Magnitude Sensitive Image Compression 133 application is for video transmission limited by narrow bandwidths, as in underwater image transmission. In that case, it is possible to work with a highly compressed global image, and if the user wants a higher definition in areas of a specific color, MSIC could get to a better definition of those areas, obviously degrading others to keep the limited bandwidth. We propose the next process to calculate the saliency map from the color values of each pixel, we first calculate the saliency map of each color in the set of colors. The saliency map of a selected color is obtained by binarizing the image, based on thresholding the distance of the pixel color and the selected color. Then we apply a border detection algorithm to get the edges of the image zones painted in that color. This edge detection step ensures that the saliency will represent more clearly those zones of the image with borders with the selected colors. The saliency map of the image is obtained as the maximum of the filtered edge images for all the set of colors. Using this value of magnitude, we get more units in the interesting regions on which colors are similar to the defined set. JPEG was implemented using Matlab and different compression qualities. Experiments use the test images depicted in the first column of Fig. 8.8. The second column shows the resulting saliency maps for these images. To keep the fish details in the first image, orange and white colors are used as color set. The flower image uses dark and clear pink, the boat image uses only brown and the parachute image uses pink and black from the parachutist. Image Q/Bytes JPEG(Tot/50%) MSIC(Tot/50%) Fish Q3/1702 1328/2695 2193(20.7)/1789(40.3) Flower Q5/1722 862/1299 3540(227.1) /1167(49.4) Boat Q6/1720 1303/1570 2366(87.4)/1190(25.3) Sky Q5/1706 967/2312 240(58.2) /468(19.7) Table 8.2: Mean MSE for the whole image as well as for areas with saliency over 50% (color example). Standard deviation is also shown (in brackets). Table 8.2 shows the resulting mean of the MSE in 10 tests using MSCL compared to JPEG. It is also shown for each algorithm, the MSE value calculated in those pixels with saliency over 50%. Standard deviation is shown in brackets, and number of bytes and image quality are also displayed. As expected, the MSE value calculated for the whole image area is lower using JPEG than the one provided by MSIC. However, when MSE was calculated taking into account only those pixels exhibiting a high saliency, MSIC obtained the best results. Chapter 8. MSIC: Magnitude Sensitive Image Compression 134 Figure 8.8: Top in columns: Original color image, saliency map generated for a one or two-color selection (fish with orange and white; flower with dark and clear pink; boat with brown; parachute with pink and black), MSIC and JPEG compression for the test images. Bottom: Fish image detail in both compression methods. Chapter 9. Surface modelling 141 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values MSCL Curvature 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values MSCL Q−error 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values FSCL 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values FCM 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values NG 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 Counts Range of curvature values SOM Figure 9.5: Histograms of the curvatures assigned to prototypes in several methods (from left to right and top to bottom: MSCL curvature, MSCL Q-error, FSCL, FCM, NG and SOM) for the Fandisk example. The red vertical line indicates the mean value and the green lines represent the standard deviation range. MSCL with curvature shows the larger number of units in high curvature zones. a larger number of units that increase their resolution. As a comparative measure, we represent histograms of curvature values along the different codebooks generated by the models. To assign a curvature value to each unit, we interpolate the curvature map as if its prototype vector was a data sample. Figure 9.5 shows histograms for the different models in Fandisk example. The red vertical line indicates mean value of the curvature distribution for each model. It is worth noting that curvature-based MSCL approach shows the distribution of curvature in its codebook with more concentration in high curvature values taking 0.3451 as mean value, while the rest of models have means between 0.22 and 0.23. The number of units dedicated to planar zones (null curvature bin in the horizontal axe) is clearly the lowest for the curvature-based MSCL approach, while the rest of the models have high number of units in these planar zones. 9.3 3D Depth images example In 3D computer graphics, a depth map or a 3D depth image is an image that contains information relating to the surface distances of scene objects from a viewpoint, usually represented by a grey level. This property facilitates the computation of the curvature at each region of the image, which is closely related to the problem of discovering the edges Chapter 9. Surface modelling 142 Figure 9.6: Surface modelling example.(a) Original image. (b) 3D depth image. (c) Curvature map applying Canny. Zones with higher curvature are also brighter. (d) Final surface models after training dataset with a SOM and (e) a MS-SOM following curvature. in the grayscale image. An edge mostly corresponds to a change in depth, and therefore it is a region with high curvature. In this example we compare the performance of SOM and MS-SOM in the task of modelling a 3D surface, given a depth image downloaded from [76]. Processing a 3D image in this way is useful when it is necessary to have a good representation of the 3D space (i.e. in robot indoor navigation to define the 3D occupancy grid mapping). Data samples are the three dimensional vector formed by the pixel coordinates and the pixel depth: x(t) = (x, y, z), where zis the normalized distance to the camera. Curvature is calculated applying the Canny filter to the image I. Top of figure 9.6 shows the original image, the depth map I(closer points are brighter) and its associated curvature values obtained with Canny filter. This curvature is used as magnitude vector associated to dataset X. We trained both SOM and MS-SOM with the same number of units, and similar training parameters, including the same linear codebook initialization. Figure 9.6 (dand e) shows the surface modelled with SOM and MS-SOM respectively. MS-SOM allocates more units than SOM in the zones corresponding to the edges in the 3D depth map, therefore three-dimensional borders are clearly represented, and it is possible to distinguish the Chapter 9. Surface modelling 143 human figure and other details, while in the SOM figure they are mostly confused with the background. Part IV CONCLUSIONS 144 Chapter 10 Conclusions and future work The subject of this thesis is to advance in dataset modeling via competitive learning where data samples are weighted by a magnitude that does not necessarily correspond with data density. I proposed a set of Magnitude Sensitive Competitive Neural Networks (MSCNN ) that work like usual competitive learning neural networks in vector quantization tasks, but include a target magnitude function. The effect of this factor is to force units to concentrate in zones of high value of the desired target function, calculated locally from the data or unit parameters. MSCNNs differ from other standard Competitive Learning algorithms that usually generate a discrete approximation to data probability density-function. As a result, MSCNNs are more versatile to distribute prototypes following any property or characteristic of the data. The application examples showed MSCNN capabilities in different applications: Gaussian distribution quantization, data series interpolation, surface modelling from 3D point clouds, color quantization and selective image compression. The comparative results with other competitive methods have validated advantages of MSCNNs in those tasks where the desired codebook distribution does not correspond to the data density distribution. 10.1 Contributions The major contributions of this Thesis are: 1. I proposed a hard competitive learning algorithm, MSCL, which has the property of distributing centroids in data-distribution zones according to an arbitrary magnitude calculated or obtained locally for each unit (Algorithm is described in [63] and 145 Chapter 10. Conclusions and future work 146 exhaustively explained in [61]). The algorithm uses two heuristic methods to get this goal: •First, competition step takes a global and a local phase, where units compete to get minimal product of magnitude by distance. •Second, learning factor is different for each unit, and depends on the previously accumulated magnitude that this unit have received. The MSCL Algorithm was proposed in sequential and in batch implementations. Several examples showed the advantages of it over other competitive learning algorithms. 2. I proposed a soft competitive learning algorithm, MS-SOM (inspired in Self-organizing maps), which also has the property of distributing centroids in data-distribution zones according to the magnitude, but keeping track of neigboring relations between units so it produces a low-dimensional (typically two-dimensional), discretized representation of the input space of the training samples, called a map (Algorithm described in [65] ). Apart from the local competition and the use of specific learning factor for every unit, it uses a neighboring function to modulate learning, and updates all units each time a sample is presented. The algorithm is also introduced in online and batch versions. Experimental comparisons were made with SOM in a simple VQ example and classification tasks. The topological representation of stimulus naturally emerges in the biological model of lateral connectivity with excitation/inhibition in the form of Mexican hat. SOM algorithm was developed as an smart simplification of this biological model. MS-SOM introduces a second level of organization of neurons following any magnitude function. This magnitude mechanism could be simplifying other types of biological processes as, for example, a magnitude derived from a chemical diffusion map. This proposition is not supported by experimental biological proofs, but I considered interesting to develop a new method that, preserving the topological behaviour, added other levels of organization with certain biological plausibility. 3. I presented a masked version of MSCL and MS-SOM that enabled the possibility of learning from data samples of different length (idea outlined in [64]). The algorithm is useful when data samples have some invalid components. This situation occurs Chapter 10. Conclusions and future work 147 some times when data is retrieved from different sources, for instance in statistical data from different countries. A conventional algorithm fails in learning from this dataset, as it needs some kind of data normalization. I demonstrated in Chapter 5 that a codebook trained with this algorithm results in similar unit allocation than using MSCL or MS-SOM with the unmasked dataset. 4. I presented a generalization of two common algorithms, frequently used in initializing K-means methods: KKZ and K-Means++. The new algorithm, called MS-INIT is the extrapolation of both algorithms to the situation where each sample have an associated magnitude. The idea is that MS-INIT also use a ’magnitude’ factor during competition to select each of the units from the data samples. This algorithm was compared with other initialization algorithms and I demonstrated that it performs better in initializing a MSCL neural network. 5. I also developed the Magnitude Sensitive Image Compression algorithm, MSIC ([64]). This algorithm, which uses several MSCL networks, was intended to achieve image compression with different compression ratios in different areas of the image, depending on their saliency. The algorithm was developed in two versions, for grayscale images, and for colour images. The basic idea of this algorithm was to divide the image in irregular blocks of different size, smaller in zones of high interest (i.e., high magnitude), and bigger otherwise. Then, blocks were encoded by a set of MSCLs, where each MSCL neural network was trained with blocks of different size. As there were more number of blocks in the most interesting areas of the image (areas with higher saliency), these zones receive higher resolution in the compression process. The definition of blocks were made by an additional MSCL trained to allocate its units in areas corresponding to the more salient pixels. For training some of the MSCL, I used the ’masked’ version of the algorithm. Comparison with JPEG and SOM demonstrate the advantages of MSIC in selective image compression. Additionally I made some minor contributions: 1. I defined two functions to measure the goodness of the quantization achieved by MSCNNs developed along the thesis: WMSE, the weighted version of MSE (Mean Chapter 10. Conclusions and future work 148 Squared Error), and weighted Entropy. Here, instead of the density of probability, it is used probability of accumulated magnitude at each unit. 2. I also demonstrate the advantage of both MSCL and MS-SOM in a surface modeling task. In this case two real application examples were shown, surface reconstruction from 3D point clouds generated form real laser, and the same task using Depth images captured with TOF cameras. Both algorithms surpassed other typical competitive learning algorithms, because MSCL or MS-SOM were trained to focus on the zones of great curvature, while plain portions of the surface were underrepresented. 3. I presented the use of the new algorithms in a real Color Reduction task. Here, dataset consists on triplets formed by the three coordinates of each sample in the image color space. Training a neural network with a reduced number of codewords, it is possible to get a reduced color palette for the image. The novelty was the use of a MSCL for this training process, with some kind of magnitude associated to each sample. I tested different functions to define this magnitude: pixel saliency, distance to the center of the image, a magnitude that avoids mean color in the image, text image binarization . In these cases, MSCL and MS-SOM performed better than other algorithms. 4. Finally I compared SOM and MS-SOM in classification tasks. In this case, magnitude was selected to force units to focus in zones with higher miss-classification error so the final classification error was lower in MS-SOM than in the SOM algorithm. 10.2 List of publications 1. E. Pelayo, J. D. Buldain, C. Orrite, SO-VAT: Self-Organizing Visual Assessment of cluster Tendency for large data sets, in proceeding of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN (2011) 141-146. 2. E. Pelayo, J. D. Buldain, C. Orrite, Magnitude Sensitive Competitive Learning, in proceeding of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN (2012) 305-310. 3. E. Pelayo, J. D. Buldain, C. Orrite, Focused Image Color Quantization using Magnitude Sensitive Competitive Learning Algorithm, in Proceedings of the 4 th International Joint Conference on Computational Intelligence, IJCCI, (2012) 516-521. Chapter 10. Conclusions and future work 149 4. E. Pelayo, J. D. Buldain, C. Orrite, Magnitude Sensitive Competitive Learning, Neurocomputing 112 (2013) 4-18, ISSN 0925-2312. 5. E. Pelayo, J. D. Buldain, C. Orrite, Magnitude Sensitive Image Compression, in Proceedings of the 5 th International Joint Conference on Computational Intelligence, IJCCI, (2013) 370-380. ( This paper received the NCTA 2013 - BEST STUDENT PAPER AWARD ). 6. E. Pelayo, J. D. Buldain, C. Orrite, Color Quantization with Magnitude Sensitive Competitive Learning Algorithm, LNCS, Transactions on Computational Collective Intelligence, Special Issue IJCCI 2012. ( Review pending ). 7. E. Pelayo, J. D. Buldain, C. Orrite, Selective image compression using MSIC algorithm, LNCS, Studies in Computational Intelligence (SCI) published by SpringerVerlag, Special Issue IJCCI 2013. ( Review pending ). 8. E. Pelayo, J. D. Buldain, MS-SOM: Magnitude Sensitive Self-Organizing Maps, in Proceedings of the 10th WORKSHOP ON SELF-ORGANIZING MAPS, WSOM (2014) ( Review pending ). 10.3 Future work Algorithms proposed in this thesis can be improved, and research and future developments can be expected. Regarding the methodological aspects there are some possible competitive learning variants that can be developed, maintaining the idea of magnitude modulation: 1. Regarding MSCL itself, a wider experimentation could be done on some of the algorithm parameters. For instance, using a variable number of winners to compete in the local competition step. In the chapter devoted to the MSCL algorithm, we demonstrated that low values for the number of competing units were the most suitable when a constant value was used. However, it was not investigated the effect of using a variable number of winners, number that could decrease during training. 2. The neural gas (NG) is a simple algorithm for finding optimal data representations based on feature vectors. It is a soft competitive algorithm, as SOM neural network, but NG does not preserve the topological properties of the input space. It has the advantage over SOM of being simpler, and getting better results in some occasions, Chapter 10. Conclusions and future work 150 specially with high dimensional datasets. Extending the idea of magnitude to Neural Gas as we did with SOM is one of the possible future research lines (this algorithm could be called MS-NG). 3. Another option is using once again soft competition, but with no fixed neighboring relation between units, just winner unit could pull from neigboring ones. These relations could be established between winner an rival units during training (as mentioned in the section related to connections, in the chapter dedicated to MSCL). The resulting algorithm could be an alternative to MS-NG or MS-SOM. The advantages of this algorithm over MSCL would be a faster convergence and the fact that it would avoid ’dead-units’. 4. A growing version of MSCL could be implemented (it could be somehow as an initial step with MS-INIT, and then normal training). The advantage over MSCL or MSSOM is that it would not be required to know in advance the number of units necessary for quantification. 5. It could be implemented a Recursive/Recurrent MSCL to be applied in temporal series. Then, MSCL would be focused on responding to certain temporal variations. 6. Another methodological improvement is the use of Hierarchical MSCLs. Different MSCLs could be trained simultaneously from the dataset, but achieving better results than if being alone. 7. Finally, it is also possible to use any of the MSNN neural networks to train the center vectors in a Radial Basis Function Neural Network. Therefore, depending on the used magnitude function, it is possible to approximate a function with great detail in certain areas of the space, or achieve better time-series prediction giving higher importance to some of the temporal sequences. Concerning the application of these algorithms, there are several open research lines. 1. A possible future work in color quantization would be the processing of multi-channel images from satellite. In this application, the number of colors is replaced by the number of channels, so the dimension of the data can increase considerably. Using MSCL, with magnitude maps obtained from labelled zones of the images, it is possible to focus the vector quantification towards zones of interest, for example detailing built areas or areas that contains a specific crop.