Some Competitive Learning Methods Bernd Kritzke Systems Biophysics Institute for Neural Computation Ruhr-Universitiit Bochum Draft from April 5, 1997 (Some additions and refinements are planned for this document so it will stay in the draft status still for a while.) Comments are weleame.Abstract ‘This report has the purpose of describing several algorithms from the literature all related to competitive learning. A uniform terminology is used for all methods ‘Moreover, identical examples are provided to allow a qualitative comparisons of the methods. ‘The on-line version! of this document contains hyperlinks to Java implementations of several of the discussed methods. Taps] vere nentoinformatik [Link]/ini/ DM /research/ gn /JavaPaper/Contents 1 Introdnetion 2 Common Properties & Notational Conventions 3 Goals of Competitive Learning 3.1 Frror Minimization 3.2. Entropy Maximization 3.3 Feature Mapping 34 Other Goals 4 Hard Competitive Learning 4.1 Batch Update: LBG 42 Online Update: Basic Algorithm 4.3 Constant Learning Rate tially Decaying Learning Rate . . . 5. SCL w/o Fixed Network Dimensionality 51 Nenal Gas 5.2 Competitive Hebbian Learning 5.3 Neural Gas plus Competitive Hebbian Learning 54 Growing Neural Gas 55 Other Methods 6 SCL with Fixed Network Dimensionality 6.1 SelF-organizing Feature Map 6.2 Growing Cell Struetures 63 Growing Grid 64 Other Methods 7 Quantitative Results (t. 8 Discussion (t.b.d.) RefersChapter 1 Introduction In the area of competitive learning a rather large number of models exist which have similar goals but difer considerably in the way they work. A common goal ‘of those algorithms is to distribute a certain number of vectors in a possibly high- dimensional 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 In this report we review several methods related to competitive learning, A common terminology is used to make a comparison of the methods easy. Moreover. software implementations of the methods are provided allowing experiments with ditferent data distributions and observation of the learning process. ‘Thanks to the Java programming language the implementations run on a large number of platforms without the need of compilation or local adaptation, The report is structured as follows: Tn chapter 2 the baste terminology troduced and properties shared by all models are outlined. Chapter 3 discusses possible goals for competitive learning systems. Chapter 4 is concerned with hard competitive learning, i.e. models where only the winner for the given input signal is adapted. Chapters 5 and 6 describe soft competitive learning. ‘These models ate characterized by adapting in addition to the winner also some other units of the network. Chapter 5 is concerned with models where the network has no fixed di- mensionality. Chapter 6 describes models which do have a fixed dimensionality and may be used for data visualization, sinee they define a mapping from the usually high-cimensional input space to the low-dimensional network structure. ‘The last two chapters still have to be written and will contain quantitative results and a discussion.Chapter 2 Common Properties and Notational Conventions ‘The models described in this report share several architectural properties which are described in this chapter. Ror simplicity, we will refer to any of these models as network even if the model does not. belong to what is usually understood as “neural network” Rach network ennsists af a set of Nv units A= fer, C25 ++ ow he (24) Kach unit ¢ has an associated reference vector " (22) Wee indicating its position or receptive field center in input space. Between the units of the network there exists a (possibly empty) set, CCAKA (23) of neighborhood connections which are unwei :hted and symmetric: EC HS (ZN EC (2.4) These connections have nothing to do with the weighted connections found, e.., in multilayer pereeptrons (Rumelhart et al. 1986). They are used in some methods to ‘extend the adaptation of the winner (see below) to some of its topological neighbors, For a unit ¢ we denote with iV. the set of its direct topological neighbors: {ie Al(o,i) €Ch. (25) N ‘Lhe n-dimensional input signals are assumed to be generated either according to a continious probability density funetion ple), € eR" (2.6) or from a finite training data set D=4 For a given input signal € the winner the unit with the nearest. reference vector Ewhe eR (2.7) (€) among the units in A is defined as(6) = arg mince 4|| — Wel (2.8) whereby | - || denotes the Euclidean vector norm. In case of a tie among several units one of them is chosen to be the winner by throwing a fair dice. In some cases we will denote the current winner simply by s (omitting the dependency on €). If not only the winner but also the second-nearest unit or even more distant units are of interest, we denote with s; the inearest unit (s1 is the winner, s2 is the second-neatest tmnt, etc.). “Two fundamental and elosely related concepts from computational geometry are important to understand in this context. ‘These are the Voronoi ‘Tessellation ancl the Delaunay Triangulation: Given a set of vectors Wi, ..., Wy in R” (see figure 2.1 a), the Voronoi Region V; of a particular vector w; is defined as the set of all points in R for which ws is the nearest, weetor: Vi = {€€ Ri = arg minjess,...wyllé — Wall}. (2.9) In order for each data point to be associated to exactly one Voronoi region we define (as previously done for the winner) that in case of a tie the corresponding point is mapped at random to one of the nearest reference vectors. Alternatively. ‘one could postulate general positions for all data points and reference vectors in which case a tie would have zero probability. It is known, that each Voronoi region Vis a convex area, ie. (EV AGEV) + (tal —-&)EVI(Va0Sasi), — (210) ‘The partition of R" formed by all Voronoi polygons is called Voronoi Tessellation ‘or Dirichlet Tessellation (see figure 2.1 b). Efficient algorithms to compute it are only known for two-dimensional data sets (Preparata and Shamos, 1990). ‘The concept itself, however, is applicable to spaces of arbitrarily high dimensions, fone connects all pairs of points for which the respective Voronoi regions share an edge (an (1 ~ 1}-dimensional hyperface for spaces of dimension n) one gets the Delaunay Triangulation (see figure 2.1 c). This triangulation is special among all possible triangulation in varions respeets. Tt is, et, the only triangulation in wh the citcumeircle of each triangle contains no other point from the original sot than the vertices of this triangle. Moreover, the Delaunay triangulation Hrs been shown tobe optimal for funetion interpolation (Omohundo, 1990). The competitive Hebbian learning method (see section 5.2) generates a subgraph of the Delaunay triangulation which is limited to those areas of the input space where data is found, For convenience we deline the Voronoi Region of a unit e.c € A, a8 the Voronoi region ofits reference vector: Ve={€E R"Is(€) = ch. (2.41) In the case of a finite input data set D we denote for a unit. ¢ with the term Voronoi Set the subset R. of D for which c is the winner (see figure 2.2): Re= {EE Disl€) =o}. (243)6 CHAPTER 2, COMMON PROPERTIES & NOTATIONAL CONVENTIONS a) °) Figure 2.1: a) Point set in R*, b) corresponding Voronoi tessellation, c) correspond- ing Delaunay triangulation a) data set D 1n input data set D is shown (a) and the partition of D into Voronot sets for a particular set of reference vectors (b). Each Voronoi set contains the data points within the corresponding Voronoi field.Chapter 3 Goals of Competitive Learning A number of different and often mutually exclusive goals can be set for competitive learning systems. In the following some of these goals are discussed. 3.1 Error Minimization A frequent goal is the minimization of the expected quantization (or distortion) error. In the case of a continuous input signal distribution p(€) this amounts to finding values for the reference vectors We,c € A such that the error (H(A) = Yo fle wel?of@)te (a1) is minimized (Ve is the Voronoi region of unit c). Correspondingly, in the case of a finite data set D the error B(D, A) = 1/|D| > YD i — wel? (3.2) CCAR, has to be minimized with R. being the Voronoi set of the unit c A typical application where error minimization is important is vector quantiza- tion (Linde et al., 1980; Gray, 1984). In vector quantization data is transmitted ‘over limited bandwidth communication channels by transmitting, for each data vee- tor only the inder of the nearest reference vector. ‘The set of reference vectors (which is called codebook in this context) is assumed to be known both to sender and receiver. ‘Therefore, the receiver can use the transmitted indexes to rettieve the corresponding reference vector. ‘There is an information loss in this case which is equal to the distance of current data vector and nearest reference vector. ‘The ‘expectation value of this error is described by equations (3.1) and (3.2). In par- ticular if the data distribution is clustered (contains subregions of high probability density), dramatic compression rates can be achieved with vector quantization with relatively little distortion8 CHAPTER 3, GOALS OF COMPETITIVE LEARNING 3.2. Entropy Maximization Sometimes the reference vectors should he distribnted such that. each reference vector has the same chance to be winner for a randomly generated input signal & ig (eed) (33) I we interpret the generation of an input signal and the subseent mapping ‘onto the nearest unit in A as random experiment which assigns a value x € A to the random variable X, then (3.3) is equivalent to maximizing the entropy Pls) = H(X) =~ Pla) oa( PCa) = Blow 5) (4) ma 2 with E(-) being the expectation operator If the data is generated from a continuous probability (3.3) is equivalent to ribution p(é), then 1 5) [w@u= Gy Weed) (35) In the case of a finite data set D (3.3) corresponds to the situation where each Voronoi set Re contains (up to discretization effects) the same number of data vectors: 1 ml An advantage of choosing reference veetors such as to maximize entropy is the inherent robustness of the resulting system. The removal (or “failure”) of any reference vector affects only a limited fraction of the data. Entropy maximization and error minimization can in general not be achieved simultaneously. In particular if the data distribution is highly non-uniform both foals differ considerably. Consider, e.g, a signal distribution p(€) where 50 percent of the input signals come from a very small (point-like) region of the input. space whereas the other fifty percent are uniformly distributed within a huge hypercube ‘To maximize entropy half of the reference vectors have to be positioned in each region. ‘Lo minimize quantization error however, only one single vector should be positioned in the point-like region (reducing the quantization error for the signals there basically to zero) and all others should be uniformly distributed within the hypercube. (vee A), (36) 3.3. Feature Mapping With some network architecturesit is possible to map high-dimensional input signals onto a lower-dimensional structure in such a way, that some similarity relations present in the original data are still present after the mapping. ‘This has been denoted feature mapping and can be useful for data visualization. A prerequisite for this is that the network used has a lixed dimensionality. ‘This is the case, e.g for the selForganizing feature map and the other methods discussed in section 6 of this report. ‘A related question is, how topology-preserving is the mapping from the input data space onto the discrete network structure, Le. how well ate similarities pre served? Several quantitative measures have been proposed to evaluate this Itke the topographic product (Bauer and Pawelzik, 1992) or the topographic function (Villmann et al., 1994)34, OTHER GOALS 0 3.4 Other Goals Competitive learning methods can also be used for density estimation, Le. for the generation of an estimate for the unknown probability density p(€) of the input signals. Another possible goal is clustering, where a partition of the data into subgroups ‘or clusters is sought, stich that the distance of data items within the same cluster (ntra-custer variance) is small and the distance of data items stemming from differ- cent clusters (inter-cluster variance) is large. Many different flavors of the clustering problem exist depending, e.g., on whether the mumber of clusters is pre-defined or should be a result of the clustering process. A comprehensive overview of clustering methods is given by Jain and Dubes (1988) Combinations of competitive learning methods with supervised learning ap- proaches are feasible, too. One possibility are radial basis function networks (RBEN} where competitive learning is used to position the radial centers (Moody and Darken, 1989; Fritzke, 1994b). Moreover, local linear maps have been combined with com- petitive learning methods (Walter et al., 1990; Martinets et al., 1989, 1998; Fritzke, 1995b). In the simplest case for each Voronoi region one linear model is used to describe the input/output relationship of the data within the Voronoi region,Chapter 4 Hard Competitive Learning 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. Different specific methods can be obtained by performing either batch or on-line update. In batch methods (e.g. LBG) all possible input signals (which must come from a finite set in this case) are evaluated first before any adaptations are done. This is iterated a number of times. On-line methods, on the other hand (e.g. k-means), perform ‘an update directly after each input signal, Among the on-line metiiods variants with constant adaptation rate can be distinguished from variants with decreasing adaptation rates of different kinds, A general problem occurring with hard competitive learning is the possible ex- istence of “dead units”. ‘These are units which ~ perhaps due to inappropriate initialization ~ ate never winner for an input signal and, therelore, keep their posi- tion indefinitely. Those units do not contribute to whatever the networks purpose is (e.g, error minimization) and must be considered harmful since they ate unused notwork resourees. A common way to avoid dead units is to use distinct sample vectors acoording to p(€) to initialize the reference vectors. “The following problem, however, remains: if the reference vectors are initialized randomly according to p(€), then their expected initial local density is proportional to p(€). This may be rather suboptimal for certain goals. For example, if the goal is ‘error minimization and p(€) is highly non-uniform, then itis better to undersample the regions with high probability density (ie., use less reference vectors there than dictated by p(€)) and oversample the other Tegions. One possibility to adapt the distribution of the reference vectors to a specific goal is the use of local statistical measures for directing insertions and possibly also deletion of units (see sections 5.4, 6.2 and 6.3) Anotier problem of hard competitive learning is that different random initial izations may lead to very different results. ‘The purely local adaptations may not be able to get the system out of the poor local miniunm where it, was statted One way to cope with this problem is to change the “winner-take-all” approach of hard competitive learning to the “winner-take-most” approach of soft competitive learning. In this ease not only the winner but also some ottier units are adapted (see chapters 5 and 6). In general this decreases the dependency on initialization. 4.1 Batch Update: LBG The LBG (or generalized Lloyd) algorithm (Linde et al., 1980; Forgy, 1965; Lloyd, 1957) works by repeatedly moving all reference vectors to the arithmetic mean of their Voronoi sets. ‘The theoretical fomndation for this is that it ean he shawn 104.2, ON-LINE UPDATE: BASIC ALGORITHM, ul (Gray, 1992) that a necessary condition for a set of reference vectors {Welc € A} to minimize the distortion error E(D,A) = 1D) 2 Ig = well”. (41) ceAgeR, is that each reference vector w, fulills the centroid condition. In the case ofa finite set of input signals and the use of the Buclidean distance measure the centroid condition reduces to 1 w= Tay be (4.2) cl eee whereby Re is the Voronoi set of unit e ‘The complete LBG algorithm is the following: 1. Initialize the set A to contain N (NV € M) units ¢ A= fer, en «+5 en} (43) with reference vectors we, € R" chosen randomly (but mutually different) from the finite data set D. 2. Compute for each unit ¢ € A its Voronoi set Re. 3. Move the reference vector of each unit to the mean of its Voronoi set: wee rea ye (44) ER. 4. If in step 3 any of the we did change, continue with step 2 5. Return the current set of reference vectors. The stops 2 and 3 together form a so-called Lloyd iteration, which is guarantecd to decrease the distortion error or leave it at least unchanged. LBG is guaranteed to converge in a finite number of Lloyd iterations to a local minimum of the distortion ‘error fimetion (see figure 4.1 for an example). ‘An extension of LBG, called LBG-U (Fritzke, 1997), is often able to improve on the local minima found by LBG. LBG-U performs non-local moves of single reference vectors which do not contribute much to error reduction (and are, therefore, not useful, ths the “U” in LBG-U) to locations where large quantization error does ‘occur. ‘Thereafter, normal LBG is used to find the nearest local minimum of the distortion error function. 'This is iterated as long as the L13G-generated local minima improve. LBG-U requires a finite data set, too, and is guaranteed to converge in a finite mumber of steps. 4.2 On-line Update: Basic Algorithm In some situations the data set D is so huge that batch methods become impractical, In other cases the input data comes as a continuous stream of unlimited length which makes it completely impossible to apply batch methods. A resort is on-line update, which ean be described as follows: 1. Initialize the set A to contain AV units: A= {0100-005 en} (49) with reference vectors we, € R” chosen randomly according to p(€).2 CHAPTER 4, HARD COMPETITIVE LEARNING a) data set D g) 5 Lloyd iterations 1) 6 Loyd iterations i) 7 Lloyd iterations Figure 4.1: LBG simulation. a) The data set D consisting of 100 data items. b) 20 reference vectors have been initialized randomly from points in D. ‘The correspond- ing Voronoi tessellation is shown. c-i) The positions of the reference vectors after the indicated number of Lloyd iterations. Reference vectors which did not move uring the previous Lloyd iteration are shown in black. In this simulation LBG has converged after 7 Lloyd iterations.4.3, CONSTANT LEARNING RATE WW 2. Generate at random an input signal € according to p(é). 3. Determine the mer s = s(€): 9(€) = arg mitoe 4||§ — Well. (4.6) 4. Adapt the reference vector of the winner towards € Aw, =¢(€—w,). (47) 5. Unless the maxinmm number of steps is reached continue with step 2 ‘Thereby, the learning mate e determines the extent to which the winner is adapted towards the input signal. Depending on whether ¢ stays constant or decays over time, several different, methods are possible some of which are described in the following. 4.3 Constant Learning Rate If the learning rate is constant, ie. fo, (0 < € <1), (48) then the value of each reference vector We tepresents an exponentially decaying average of those input signals for which the unit ¢ has been winner. To see this, let €),€5,..-€) be the sequence of input signals for which c is the winner. The sequence of successive values taken by we can then be written as w.(0) = (random signal according to p(€)) we(1) we(0) + €a(i — we(0)) (1 = eo) wel) + e085 (4.9) wel(2) (1 = eo)we(1) + €0€ (1 €0)?we(0) + (1 — en)en€S + €0€5, (4.10) welt) = (1—€o)we(t — 1) + en€ (1 c'wel0) +0) J =e)! (4.11) From (4.8) and (4.11) itis obvious that the influence of past input signals decays ‘exponentially fast with the number of further input signals for which c is winner (see also figure 4.2). ‘The most recent input signal, however, always determines a fraction ¢ of the current value of We. ‘This has two conseaences. First, sch a system stays adaptive and is therefore in principle able to follow also non-stationary signal distribution p(€). Second (and for the same reason), there is no convergence. Even after a large mimber of input signals the current input signal can cause a considerable change of the reference vector of the winner. A typical behavior of such a system in case of a stationary signal distribution is the following: the reference vectors drift from their initial positions to quasi-stationary positions where theyu CHAPTER 4, HARD COMPETITIVE LEARNING oor 0.001 0.0001 160-05 16-06 1 w 100 1000) 000K Figure 4.2: Intluence of an input signal € on the vector of its winner s as a function ‘of the nnmber of following input signals for which s is winner (including ). Results, for ditferent constant adaptation rates are shown. ‘The respective section with the :eaxis indicates how many signals are needed until the influence of € is below 10-8 For example if the learning rate 9 is set to 0.5, about 10 additional signals (the section with the z-axis is near 11) are needed to let this happen. start to wander around a dynamie equilibrium. Better quast-stationary positions in terms of mean square error are achieved with smaller learning rates. In this case. however, the system also needs more adaptation steps to reach the quasi-stationary positions. the distribution is non-stationary then the information about the non-station- arity (how rapidly does the distribution change) can be used to set an appropriate learning rate. Hor rapidly changing distributions relatively large learning rates should be used! and vice versa. Figure 4.3 shows some stages of a sinmiation for a simple ring-shaped data distribution. Figure 4.4 displays the tinal results after 40000 adaptation steps for three other distribution, In both cases a constant learning rate en = 0.05 was used. 4.4 k-means Instead of having a constant learning rate, we can also decrease it over time. A particularly interesting way of doing so is to have a separate learning rate for each unit ¢ € A and to set it according to the harmonic series =t (4.12) ‘Thereby, the time parameter ¢ stands for the number of input signals for which this particular unit has been winner so far. ‘This algorithm is known as &-means (MacQueen, 1967), which is a rather appropriate name, because each reference vector w,(t) is always the exact arithmetic mean of the input signals €5,€5,...,¢ it has been winner for so far. The sequence of successive values of W. is the following:44, K-MEANS 1b ) 2500 signals f) 10000 signals) 40000 signals _h) Voronoi regions Figure 4.3: Hard competitive learning simulation sequence for a ring-shaped uni- form probability distribution. A constant adaptation rate was used. a) Initial state, b-f) Intermediate states, g) Final state. h) Voronoi tessellation corresponding to the final state, Figure 44: Hard competitive learning simulation results after 40000 input signals for three different probability distributions. A constant learning rate was used. a) ‘This distribution is uniform within both shaded areas. ‘The probability density, however, in the upper shaded area is 10 times as high as in the lower one. b) The distribution is uniform in the shaded area. ) In this distribution each of the 11 circles indicates the standard deviation of a Gaussian kernel which was used to rate the data. All Ganssian kernels have the same a priori probability.16 CHAPTER 4, HARD COMPETITIVE LEARNING we(0) = (random signal according to p(€)) well) = we(0) + €(1)(€i — wel0)} =6 (4.13) wel2) = wel) + (2G — well) 7 eee (4.14) welt) = welt —1) + e(t)(€i — welt — 1)) 7 gto+ & (4.15) One should note that the set of signals €3,€5,...,€5 for which a particular unit has been winner may contain elements which le outside the current Voronoi region of e. The reason is that each adaptation of w, changes the borders of the Voronoi region V-. Therefore, although we(t) represents the arithmetic mean of the signals it has been winner for, at time ¢ some of these signal may well le in Voronoi regions belonging to other units Another important point about K-means is, that there is no strict: convergence (as is present e.g, in LBG), the reason being that the sum of the harmonic series diverges: tin, 5 Because of this divergence, even after a large number of input signals and cor respondingly low values of the learning rate e(t) arbitrarily large modifications of each input vector may occur in principal. Such large modification, however, are very improbable and in simulations where the signal distribution is stationary the reference vectors tstally rather quickly take on values which are not much changed in the following. In fact, it has been shown that k-means does converge asymptot- ically to a configuration where each reference vector We is positioned such that it coincides with the expectation value (4.16) preg e ve) = [ ertene (a7) of its Voronoi region V- (MacQueen, 1965). One can note that (4.17) is the con- tinuous variant of the centroid condition (4.2). Figure 4.5 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 4.6 displays the final results after 40000 adaptation steps for three other distribution. 4.5 Exponentially Decaying Learning Rate Another possibilty for a decaying adaptation rate has been proposed by Ritter etal (1991) in the context of self-organizing maps. They propose an exponential decay according te (0) = e(eg/e) fom (4.18)45, EXPOD INTIALLY DEUAYING LEARNING RATE Ww ¢) 2500 signals £) 10000 signals —_g) 40000 signals _h) Voronoi regions Figure 4.5: f-means simulation sequence for a ring-shaped uniform probability distribution. a) Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the final state. The final distribtion of the reference vectors still reflects the clusters present in the initial state (see in particular the rogion of higher vector density at the lower left) a) b) ° Figure 4.6: -means simulation results after 40000 input signals for three different probability distributions (described in the caption of figure 4.4).as CHAPTER 4, HARD COMPETITIVE LEARNING ‘0: exponential decay — ‘it): harmonic series on 0) ott) 0.01 0.001 0.0001 16-05 19-07 5000 10000 15000 20000 25000 30000 35000 4000¢ ei(er/e)"/"=* and the harmonic series g(t) = 1/t for a particular set of parameters (6 = 10, €y = 1E-5, tax = 40000). The displayed difference between the two learning rates can be interpreted as noise which in the case of an exponentially decaying learning rate is introduced to the system and then gradually removed. whereby ¢; and ¢y are initial and final values of the learning rate and tmax 18 the total number of adaptation steps which is taken. In figure 4.7 this kind of learning rate is compared to the harmonic series for a specific choice of parameters. In particular at the beginning of the simulation the exponentially decaying learning rate is considerably larger than that dictated by the harmonie series. This can be interpreted as introducing noise to the system which is then gradually removed and, therefore, suggests a relationship to simlated annealing techniques (Kirkpatrick et al., 1983). Simulated annealing gives a system the ability to escape from poor local minima to which it might have been initialized Preliminary experiments comparing k-means and hard competitive learning with a learning rate according to (4.18) indicate that the latter method is less susceptible to poor initialization and for many data distributions gives lower mean square error Also small constant learning rates usually give better results than k-means. Only in the special case that only one reference vector exists (|| = 1) it is completely Impossible to beat A-means on average, since in this case it realizes the optimal estimator (the mean of all samples occurred so far). ‘These observations are in complete agreement with Darken and Moody (1990) who investigated k-means anc a mimber of different learning rate schedules like constant learning rates and a learning rate which is the square root of the rate used by k-means (e(#) = 1/ y(t) ‘Their results indicate that iff fs larger than 1, then k-means is inferior to the other learning rate schedules. In the examples they give the difference in distortion error is up to two orders of magnitude. Figure 4.8 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 4.9 displays the final results after 40000 adaptation steps for three other distribution. The parameters used in both examples were: ¢; = 0.5, €y 0.0005 ad trax = 40000.45, EXPOD INTIALLY DECAYING LEARNING RATE 16 ) 2500 signals f) 10000 signals) 40000 signals _h) Voronoi regions Figure 4.8: Hard competitive learning. simnlation sequence for a ring-shaped tt form probability distribution. An exponentially decaying learning rate was used. a) Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the tinal state. a) Figure 4.9: Hard competitive learning simulation results after 40000 input signals for three different probability distributions (described in the caption of figure 4.4), An exponentially decaying learning rate was used.Chapter 5 Soft Competitive Learning without Fixed Network Dimensionality In this chapter some methods from the area of soft competitive learning are de- scribed. ‘They have in common, in contrast to the models in the following chapter that no topology of a fired dimensionality is imposed on the network. In one case there is no topology at all (neural gas). In other cases the dimensionality of the network depends on the (oen! dimensionality of the data and may vary within the input space. 5.1 Neural Gas ‘The neural gas algorithm (Martinetz and Schulten, 1991) sorts for each input signal € the units of the network according to the distance of their reference vectors to & Based on this “rank order” a certain munber of units is adapted. Both the mumber of adapted units and the adaptation strength are decreased according to a fixed schedtule. ‘The complete neural gas algorithm is the following 1. Initialize the set A to contain NV units c; A= {er, C25 +++, en} (5.1) with reference vectors we, € R chosen randomly according to p(é) Initialize the time parameter 0. 2. Generate at random an input signal € according to p(€)- 3. Order all elements of A according to their distance to & i. find the sequence of indices (io, fi, ---, iv-1) such that wi, is the reference vector closest to & Ws, is the relerence vector second-closest to € and Wis, f= 0,2, .V—1 is the reference vector such that & vectors wy exist with |€ — ws|| < [If ‘W.||. Following Martinetz et al. (1993) we denote with ky(€,A) the number k associated with ws 4. Adapt the reference vectors according ta Aw = et) hail AN) (E = wo) (5.3) 205.2. COMPETITIVE HEBBIAN LEARNING a with the following time-dependencies: et) = Ais), (5.4) elt) = ees/ei) lo, (5.5) hny(h) = exp(~h/A(t). (5.6) 5. Increase the time parameter ¢: t=t+l (5.7) 6. If < tage Continue with step 2 For the time-dependent parameters suitable initial values (A, ¢:) and final values (Ay, €7) have to be chosen. Figure 5.1 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 5.2 displays the final results after 40000 adaptation steps for three other distribution. Following Martinetz et al. (1993) we used the following parameters: A; = 10, Ay = 0.01, & = 0.5, €f = 0.005, tmax = 49000, 5.2 Competitive Hebbian Learning This method (Martinetz and Schnlten, 1991; Martinetz, 1993) is usually not used ‘on its own but in conjunction with other methods (see sections 5.3 and 5.4). It is, however, instructive to study competitive Hebbian learning on its own. ‘The method does not change reference vectors at all (which could be interpreted as having a zero learning rate). It only generates a number of neighborhood edges between the units fof the network. Tt was proved by Martinetz (1993) that the so generated graph is optimally topology-preserving in a very general sense. In particular each edge of this graph belongs to the Delannay triangulation corresponding, to the given set of reference vectors. The complete competitive Hebbian learning algorithm is the following: 1. Initialize the set A to contain N units c A= {ery 02) «0 ew} (5.8) with reference vectors we, € R” chosen randomly according to p(). Initialize the connection set € , € C Ax A, to the empty set c=0. (5.9) 2. Generate at random an input signal & according to pl€). 3. Determine units s; and s2 (s1,82 € A) such that 81 = arg mine al Well (6.10) and $2 =arg mince a\ {4,116 — Wel (5.11) 4. Ifa connection between s; and s2 does not exist already, create it: C=CUA ssa) te (5.2) 5. Continue with step 2 unless the maximum number of signals is reached. Figure 5.3 shows some stages of a simulation for a simple ring-shaped data distri- bution. Figure 5.4 displays the final results after 40000 adaptation steps for three ‘other distriintion2 CHAP WORK DIMENSIONALITY TER 5. SCL W/O FIXED NI a) O signals 6 iS ¢) 2500 signals £) 10000 signals —_g) 40000 signals _h) Voronoi regions Figure 5.1: Neural gas simulation sequence for a ring-shaped uniform probability distribution. a) Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the final state. Initially strong neighborhood interac tion leads to a clustering of the reference vectors which then relaxes until at the end a rather even distribnition of reference vectors is fond Figure 5.2: Neural gas sinmlation results after 40000 input signals for three different probability distributions (cescribed in the caption of figure 4.4)..5.2, COMPETITIVE HEBBIAN LEARNID 2 ) 2500 signals f) 10000 signals) 40000 signals _h) Voronoi regions Figure 5.3: Competitive Hebbian learning simulation seauence for a ring-shaped uniform probability distribution. a) In 8) Final state. h) Voronoi tessellation corresponding to the final state. Obviously, the method is sensitive to initialization since the initial positions are always equal to the final positions, a) b) °) Figure 5.4: Competitive Hebbian learning simulation results after 40000 input. sig nals for three different, probability distributions (described in the caption of figure 44)24 CHAPTER 5. SCL W/O FIXED NETWORK DIMENSIONALITY 5.3 Neural Gas plus Competitive Hebbian Learn- ing This method (Martinetz and Schulten, 1991, 1994) is a straight-forward superpo- sition of neural gas and competitive Hebbian learning. It is sometimes denoted as “topology-representing networks” (Martinetz and Schulten, 1994). This term, however, is rather general and would apply also to the growing neural gas model deseribed later. At each adaptation step a connection between the winner and the second-nearest unit is created (this is competitive Hebbian learning). Since the referenice vectors are adapted according to the nieural gas method a mechanism is needed to remove edges which are not valid anymore. This is done by a local edge aging mechanism. The complete neural gas with competitive Hebbian learning algorithm is the following: 1. Initialize the set A to contain N’ units: A= {0100-005 en} (613) with reference vectors we, € R chosen randomly according to p(€). Initialize the connection set € , CC Ax A, to the empty set: c=. (5.14) Initialize the time parameter t: (5.15) 2. Generate at random an input signal € according to p(é). 3. Order all elements of A according to their distance to &, i.c., find the sequence: of indices (ip, in, ..., iv—1) such that wy, is the reference vector closest to &, Wi, is the reerence vector second:-closest to € ad Wig, k= Oy --y N~ 1 is the reference vector such that vectors w; exist with | — wsll < lf ‘wy ||. Following Martinetz et al. (1993) we denote with k,(€,A) the number k associated with ws 4, Adapt the reference vectors according to Awy = ¢(t) -ha(hi(& A) -(E— wi) (5.16) with the following time-dependencies: A(t) = AAg/ A)", (5.17) et) = aler/aytl (5.18) hny(h) = exp(~h/A(t). (6.19) 5. If it does not exist already, create a connection between ig and i: C=CU (lio, i1)}. (5.20) Set the age of the connection between ip and ii to zero (“reftesh” the edge): ABC(igis) = O- (5.21)54, GROWING NEURAL GAS 2 6. Increment the age of all edges emanating from io: AGEs) = ABCig,y +1 (HEN) (5.22) ‘Thereby, Ne is the set of direct topological neighbors of ¢ (see equation 2.5). 7. Remove edges with an age larger than the maximal age T(t) whereby Tt) = TAT / Te)!" (5.23) 8. Increase the time parameter f: (5.24) B. It < tage Continue with step 2. For the time-dependent parameters suitable initial values (A;, €;, T;) and final values (4, €f, Tr) have to be chosen. Figure 5.5 shows some stages of a simulation for a simple ring-shaped data. distribution. Figure 6.6 displays the final results after 40000 adaptation steps for three other distribution. Following Martinetz et al. (1993) we used the following. parameters: A; = 10, Ay = 0.01, & = 0.5, €y = 0.005, faax = 40000, 20,2) = 200, ‘The network size NV was set to 100, 5.4 Growing Neural Gas This method (Fritzke, 1994b, 1995a) is different from the previously described models since the number of units is changed (mostly increased) during the self: organization process. The growth mechanism from the earlier proposed growing cell structures (Fritzke, 1994a) and the topology generation of competitive Hebbian learning (Martinetz and Schulten, 1991) are combined to a new model. Starting with very few units new units are inserted successively. To determine where to insert new units, local error measures are gathered during the adaptation process Kach new rit is inserter near the rit which has acenrmnlated most error. ‘The complete growing neural gas algorithm is the following: 1. Initialize the set A to contain two units cy and ¢: A={er cab (5.25) ‘with reference vectors chosen randomly according to pl€). Initialize the connection set € , CCA x A, to the empty set c=0. (5.26) 2. Generate at random an input signal € according to p(€)- 3. Determine the winner s; and the second-nearest unit s2 (81,82 € A) by 81 = arg mine «|| — Well (5.27) and $2 = arg mince 4\{4,)l|6 — Well: (5.28)WORK DIMENSIONALITY 26 CHAP ER 5. SCL W/O FIXED NET OOO a} 0 signals ) 100 signals ©) 300 signals) 1000 signals ) 2500 signals f) 10000 signals) 40000 signals _h) Voronoi regions Figure 5.5: Neural gas with competitive Hebbian learning simulation sequence for a ring-shaped uniform probability distribution. a) Initial state. b-f) Intermediate states. 2) Final state, h) Voronoi tessellation corresponding to the final state. The centers move according to the neural gas algorithm. Additionally, however, edges are created by competitive Hebbian learning and removed if they are not “refreshed for a while a) b) °) igure 5.6: Neural gas with competitive Hebbian learning simulation results after 40000 input signals for three different probability distributions (described in the caption of figure 4.4)5.4, GROWING NEURAL GAS 2 4. Ia connection between sy and s2 does not exist already, create it: C=CUL(s1,82) (5.29) Set the age of the connection between s; and s2 to zero ( “refresh” the edge): ABC; 42) = 0. (5.30) 5. Add the squared distance between the input signal and the winner to a local error variable: AE,, = [If — wei ll? (5.31) 6. Adapt the reference vectors ofthe winner and its direct topological neighbors by fractions ¢ and e, respectively, of the total distance to the input signal Ws, el E — Woy) (5.32) Aw; = enl€-wi) (Vie Ns, (5.33) ‘Thereby NV, (see equation 2.5) is the set of direct topological neighbors of si 7. Increment the age of all edges emanating from s1 ABE ay 2) = ABE) +1 (WEE Na) (5.34) 8. Remove edges with an age larger than dypqe- Lf this results in units having no more emanating edges, remove those units as well. 9. If the number of input signals generated so far is an integer multiple of a parameter A, insert a new unit as follows: «# Determine the unit q with the maximum accumulated error: a= arg mare 4Fe 635) 4 Determine among the neighbors of q the unit f with the maximum ac- cumulated error f= arg maxgey,Ee (5.36) Add a new unit r to the network and interpolate its reference vector from qand f. A=AU{r}, wr = (Wo + wy)/2. (5.37) Insert edges connecting the new unit r with units q and f, and remove the original edge between q and f: CHaCULirg) (AH C= C\L(a AIT (5.38) ‘* Decrease the error variables of q and f by a fraction a: AE, =-aE,, — ABy = —o8y. (5.39) Interpolate the error variable of r from q and J: E, = (By +E y)/2, (5.40) 10. Decrease the error variables of all its: AEe=-GE. (Yee A). (5.41) 11, Ifa stopping criterion (¢.g., net size or some performance measure) is not yet fulfilled continue with step 2. Figure 5.7 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 5.8 displays the final results after 40000 adaptation steps for three other distribution. ‘Ihe parameters used in both simulations were: A = 300, € = 0.05, € = 0.0006, a = 0.5, 8 = 0.0005, dma = 88.28 CHAPTER 5. SCL W/O FIXED NETWORK DIMENSIONALITY a) 0 signals b) 100 signals ¢) 2500 signals f) 10000 signals) 40000 signals) Voronoi regions Figure 5.7: Growing neural gas simulation sequence for a ring-shaped uniform probability distribution. a) Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the final state. ‘The maximal network size was set to 100. a) ed Figure 5.8: Growing neural gas simulation results after 40000 input signals for three different probability distributions (described in the caption of figure 4.4)..5.5. OTHER METHODS 5.4 Other Methods Several other models without a fixed network dimensionality are known. DeSieno (1988) proposed a method where frequent winners get a “bad conscience” for win- ning so often and, therefore, add a penalty term to the distance from the input signal. ‘This leads eventually to a situation where each unit wins approximately ‘equally often (entropy maximization). Kangas et al. (1990) proposed to use the minimum spanning tree among the units as neighborhood topology to eliminate the a priori choice for a topology in some models Some other methods have been proposed,Chapter 6 Soft Competitive Learning with Fixed Network Dimensionality In this chapter methods trom the area of soft competitive learning are described which have a network of a fixed dimensionality & which has to be chosen in advance. One advantage of a fixed network dimensionality is that such a network defines a mapping from the n-dimensional input space (with n being arbitrarily large) to the A-timensional structure. ‘This makes it possible to get low-dimensional representation of the data which may be used for visualization purposes, 6.1 Self-organizing Feature Map ‘This model stems from Kohonen (1982) and builds upon earlier work of Willshaw and von der Malsburg (1976). The model is similar to the (nmeh later developed) neural gas model (see 5.1) since a decaying neighborhood range and adaptation strength are used. An important ditierence, however, is the topology which is constrained to be a two-dimensional grid (a) and does not change during self organization “The distance on this grid is used to determine how strongly a unit r = apm is adapted when the unit s = aj; is the winner. ‘he distance measure is the Ly-norm (ak = a5; (6.1) Ritter et al. (1991) propose to use the following function to define the relative strength of adaptation for an arbitrary unit r in the network (given that s is the winner} = R+Li—m| fore = aim and =Aulrys)? hea = ex (6.2) ‘Thereby, the standard deviation o of the Gaussian is varied according to a(t) = 0140/05)" (6.3) for a suitable initial value oj and a final value oy. ‘The complete self-organizing feature map algorithm is the following 1. Initialize the set A to contain N= A={e1, C25 ent (6.4) Np units c, 306.2. GROWING CELL STRUCTURES 31 with reference vectors we, € R” chosen randomly according to p(€). Initialize the connection set C to form a rectangular Ny x No grid. Initialize the time parameter t: =0, (6.5) 2. Generate at random an input signal € according to p(é). 3. Determine the winner s(€) s(€) = arg ming ll ~ wel (6.6) 4. Adapt each unit r according to Aw, = eft) ltrs — wr) (6.7) whereby a(t) = oa 4/0)" (6.8) and et) = eles /e)i to, (6.9) Increase the time parameter ttl. (6.10) 6. It < taae continue with step 2. Figure 6.1 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 6.2 displays the final results after 40000 adaptation steps for three other distribution. The parameters were o; = 3.0, 05 = 0.1, ¢: = 0.5, € 0.005, trax 6.2 Growing Cell Structures ‘This model (Fritzke, 1994a) is rather similar to the growing neural gas model! ‘The main difference is that the network topology is constrained to consist of dimensional simplices whereby & is some positive integer chosen in advance. ‘The basie building block and also the initial configuration of each network is a k- dimensional simplex. ‘This is, e.g., a line for k=l, a triangle for k=2, and a tetra- Iedron for k=! For a given network configuration a number of adaptation steps are used to update the reference vectors of the nodes and to gather local error information at each node, ‘This error information is used to decide where to insert new nodes. A new node is always inserted by splitting the longest edge emanating from the node q with ‘maximum accumulated error. In doing this, additional edges are inserted such that the resulting structure consists exclusively of -dimensional simplices again. ‘The srowing cell structures learning procedure is described in the following: TGomparedl tothe orginal growing cell structures algorithm described by Fritake (1994a) sight ‘changes and simpliications have been done regarding the re-distribution of accumulated error, Moreover, the discussion of removal of units has been left out completely for sake of brevity32 CHAPTER 6. SCL WITH FIXED NETWORK DIMENSIONALITY ) 2500 signals f) 10000 signals) 40000 signals _h) Voronoi regions igure 6.1: Selforganizing feature map_sitmulation sequence for a ring-shaped ni- form probability distribution. a) Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the final state. Large adaptation rates in the beginning as well as a large neighborliood range cause strong, initial adaptations which decrease towards the end. Figure 6.2: SelEorganizing feature map simitlation results after 40000 input signals for three different probability distributions (described in the caption of figure 4.4)6.2. GROWING CELL STRUCTURES Fe 1. Choose a network dimensionality k. Initialize the set. A to contain k +1 units ¢ A=fey C25 +05 Coit (6.11) with reference vectors We, € R” chosen randomly according to p(é). Initialize the connection set C, € C Ax A such that each unit is connected to each other unit, Le, sch that the network has the topology of a h-dimenstonal simplex. 2. Generate at random an input signal € according to p(é). 3. Determine the winner «: s(€) arg mings lf ~ Well (6.12} 4. Add the squared distance? between the input a local ertor variable I ial and the winner unit s to AB, le - wall? (6.13) 5. Adapt the reference vectors of s and its direct topological neighbors towards € by fractions ¢ and én, respectively, of the total distance: Aw, Aw; ea(E— ws) (6.14) enl€ = wi) (vie Ng). (6.15) ‘Thereby, we denote with N, the set of direct topological neighbors of s. 6. If the number of input signals generated so far is an integer multiple of a parameter A, insert a new unit as follows: © Determine the unit q with the maximum accumulated error: arg maxec.¢Ec (6.16) ‘¢ Insert. a new unit r by splitting the longest edge emanating from q, say an edge leading to a unit f. Insert the connections (q,r) and (r, f) and remove the original connection (g, f). ‘To re-build the structure such that it again consists only of k-dimensional simplices, the new unit r is alse connected with all common neighbors of q and f, Le., with all units in the set Ny Ny ‘* Interpolate the reference vector of r from the reference vectors of q and fi wy = (wy + w)/2. (6.17) ‘© Decrease the error variables of all neighbors of r by a fraction which depends on the number of neighbors of r: AB, ie (WEN. (6.18) “Depending on the problem at hand also other local measures are possible, eg. the number ‘of inp signals for which & particular unit ss the winner or even the positioning err of robot frm controled by the network. “The local measure should generally be something which one i interested to reduce and which is lkaly to be reduced by the insertion of new units.M CHAPTER 6. SCL WITH FIXED NETWORK DIMENSIONALITY ‘ Set the error variable of the new unit r to the mean value of its neighbors: 1 B= iq = By (6.19) 7. Tieerense the error variables af all units AE.=-fE. (Wee A). (6.20) 8. If a stopping criterion (e.g., net size or some performance measure) is not yet fulfilled continue with step 2. Figure 6.3 shows some stages of a simulation for a simple ring-shaped data distribution. Figure 6.4 displays the final results after 40000 adaptation steps for three other distribution. The parameters used in both simulations were: a 1.0, € = 0.06, ¢ = 0.002, = 0.0005, 4 = 200. 6.3 Growing Grid Growing grid is another incremental network. ‘The basi¢ principles used also in _xvowing cell structures and growing neural gas are applied with some modifications to a rectangular prid. Alternatively, growing grid can be seen as an incremental variant of the selForganizing feature map. ‘The model has two distinct phases, a growth phase and a fine-tuning phase Daring the growth phase a rectangular network is built up starting from a minimal size by inserting complete rows and columns tntil the desired size is reached or until ‘performance criterion is met. Only constant parameters are used in this phase. In the fine-tuning phase the sizeof the network is not changed anymore and a decaying Jearning rate is used to find good final values for the reference vectors. As for the self-organizing map, the network structure isa two-dimensional grid (cis). This grid is initially set to 2x 2 structure. Again, the distance on the grid is used to determine how strongly a unit r = dim is adapted when the unit. ¢ = aiy is the winner. The distance measure used is the La-norm di(rys) =[F—k/+ Lim] for r= aim and $= ais (6.21) ion used to determine the adaptation strength for a unit r given ner is the same as for the selorganizing feature map: ~aalrss)? on ea = exp (6.22) ‘The width parameter 0, however, remains constant throughout the whole sim ulation. Tt is chosen relatively small compared to the values usually used at the beginning for the selForganizing feature map. One can note that as the growing ‘grid network grows, the fraction of all units which is adapted together with the winner decteases. This is also the case in the self-organizing feature map but is achieved there with a constant network size and a decreasing neighborhood width, The complete growing grid algorithm is the following: Groth Phase 1. Set the initial network width and height: M 2 (6.23)