Online competitive incremental-decremental clustering with the Winner-Kill-Loser rule

Jasmin Leveille (Center of Excellence for Learning in Education, Science, and Technology, Boston University), Isao Hayashi (Faculty of Informatics, Kansai University, Takatsuki, Osaka 569-1095, Japan), Kunihiko Fukushima (Faculty of Informatics, Kansai University, Takatsuki, Osaka 569-1095, Japan), Massimiliano Versace (Center of Excellence for Learning in Education, Science, and Technology, Boston University)

Incremental clustering techniques are general-purpose methods for clustering where the number of cluster nodes is determined online, and in particular increased, upon presentation of training data. Examples include the Leader algorithm (Hartigan, 1975), and adaptive resonance theory (Carpenter and Grossberg, 2003). Incremental learning rules for clustering are attractive for their simplicity and ease of application, and have generally led to good results on a number of tasks. Recently, a variant of incremental learning which considers online removal of tuned nodes was proposed to train simple cells in a hierarchical network (Fukushima, 2010). The learning rule presented therein, termed winner-kill-loser (WKL), is a kind of competitive rule in which only sufficiently active units enter the competition and where the losing units are effectively removed from the network.

In this work, we extend the WKL learning rule to study the structure and formation of simple cell receptive fields. We start with an analysis of the properties of the WKL rule and demonstrate that, unlike many clustering techniques, in its simplest form the learning rule does not seek to approximate maximum-likelihood estimates of the node parameters. Instead, the WKL learning rule converges asymptotically to a uniform covering of the input space, irrespective of the data probability distribution. Even in the case of a uniform data distribution, our analysis also highlights conditions for the presence of irreducible gaps in this covering. We can compute a lower bound on the size of these gaps, and show how this bound relates to clustering performance in sample simulations. In particular, we investigate through simulation whether this lower bound can account for improvements in performance reported when using the dual-threshold rule, in which the net input activation threshold for each simple cell is lowered after learning (Fukushima, 2010). Based on these results, we propose to complement the WKL learning rule by inserting activity-dependent thresholds that govern the selectivity of learned receptive fields. We show through simulation that the structure of the newly developed receptive fields approximates the input data distribution.


1. Hartigan, J.A. (1975). Clustering algorithms. Wiley.

2. Carpenter, G.A. and Grossberg, S. (2003). Adaptive resonance theory. In M.A. Arbib (Ed.) The Handbook of Brain Theory and Neural Networks, Second Edition (pp.87-90). Cambridge, MA: MIT Press.

3. Fukushima, K. (2010). Neocognitron trained with winner-kill-loser rule. Neural Networks, 23, 926-938.


Preferred presentation format: Poster
Topic: Computational neuroscience

Document Actions