The models described in this report share several architectural
properties which are described in this chapter. For 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''.

Each network consists of a set of *N* units:

Each unit *c* has an associated *reference vector*

indicating its position or *receptive field center* in input space.

Between the units of the network there exists a (possibly empty) set

of *neighborhood connections* which are unweighted
and symmetric:

These connections have nothing to do with the weighted connections
found, e.g., in multi-layer perceptrons (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 *c* we denote with the set of its direct topological
neighbors:

The *n*-dimensional input signals are assumed to be generated either according to a continuous probability density function

or from a finite training data set

For a given input signal the *winner* among the
units in is defined as the unit with the nearest reference
vector

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 the *i*-nearest
unit ( is the winner, is the second-nearest unit, etc.).

Two fundamental and closely related concepts from computational
geometry are important to understand in this context. These are the *
Voronoi Tessellation* and the *Delaunay Triangulation*:

Given a set of vectors in (see figure
2.1 a), the *Voronoi Region* of a particular
vector is defined as the set of all points in for which
is the nearest vector:

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 is a convex area, i.e.

The partition of 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.

If one connects all pairs of points for which the respective Voronoi
regions share an edge (an (*n*-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 various respects. It is, e.g., the only triangulation
in which the circumcircle of each triangle contains no other point
from the original point set than the vertices of this triangle.
Moreover, the Delaunay triangulation has been shown to be optimal for
function interpolation (Omohundro, 1990). The *competitive Hebbian learning*
method generates a
subgraph of the Delaunay triangulation which is limited to those areas
of the input space where data is found.

**Figure 2.1:** a) Point set in , b) corresponding Voronoi tessellation, c)
corresponding Delaunay triangulation.

For convenience we define the *Voronoi Region of a unit* , as the Voronoi region of its reference vector:

In the case of a finite input data set we denote for a unit *c* with the term *Voronoi Set* the subset of for which *c* is the winner (see figure 2.2):

**Figure 2.2:**
An input data set is shown (a) and the partition of into Voronoi sets for a particular set of reference vectors (b). Each Voronoi set contains the data points within the corresponding Voronoi field.

Sat Apr 5 18:17:58 MET DST 1997