March 24, 2010 KohonenAlgorithm, MasterDiploma

March 24, 2010 KohonenAlgorithm, MasterDiploma

Lets quickly remind how does Self-Organizing Map works and which are building blocks of it.

In my implementation I have processor named SomLearningProcessor which does all main algorithm steps. After you created instance of that class you are able to call **void Learn()** method, which goes through all iterations finds best matching neuron with method **int FindBestMatchingNeuron(double[] dataVector) **and then it accommodates network with using dataVector and found BMN – this is done with method **void AccommodateNetworkWeights(****int bestNeuronNum, double[] dataVector, int
iteration)**. I will return back to this processor with more details, I just wanted to give quick vision what is it.

So lets move to building blocks of our learning algorithm:

**Network **

First of all it has Network, which I inject into our SomLearningProcessor through the INetwork interface:

public interface INetwork

{

IList<INeuron> Neurons { get; set; }

ITopology Topology { get; set; }

}

As you see it has list of **Neurons **which should fill the leaning grid, which is provided through the **Topology** interface. The default implementation of the network interface supplies possibility to **randomize **neurons with specifying **minWeights **and **maxWeights **boundaries for randomizing.

public class NetworkBase : INetwork

{

public NetworkBase(bool randomize, IList<double> maxWeights, IActivationFunction activationFunction, ITopology topology)

{…

Also we are injecting IActivationFunction for our neurons, so they will calculate reaction basing on this interface. Interface provides method **double GetResult(double inputValue);**

There are following concrete implementations of the interface IActivationFunction:

- HardLimitActivationFunction
- LinearActivationFunction
- SymmetricHardLimitActivationFunction
- TransparentActivationFunction

For Self-Organizing Maps I’m using TransparentActivationFunction, which just returns summarized value.

**Topology**

Another interesting thing that we are using during learning process is Topology. Interface looks like this:

public interface ITopology

{

int

NeuronsCount { get; }

NeuronsCount { get; }

int RowCount { get;

}

}

int ColCount { get;

}

}

double WholeTopologyRadius { get; }

int

GetNeuronNumber(Location

location);

GetNeuronNumber(Location

location);

Location

GetNeuronLocation(int neuronNumber);

IList<int> GetDirectlyConnectedNeurons(int neuronNumber);

Dictionary<int, double>

GetNeuronsInRadius(int neuronNumber, double radius);

GetNeuronsInRadius(int neuronNumber, double radius);

}

As you see Topology consists with Rows and Columns as usual matrix, but the main point of interest is the method: **Dictionary<int, double>**

** GetNeuronsInRadius(int neuronNumber, double radius);** What does it do?

For the found best matching neuron **neuronNumber **– it should find all neurons which are located in boundaries of provided **radius**. Please also note that I’m returning pairs <NeuronNumber, DistanceFromItToBMN> in result dictionary. This allow increase performance a bit, because no need to double calculate distances.

Currently I have two finished implementations of ITopology they are **SimpleMatrixTopology** and **BoundMatrixTopology**.

Difference between them is that **BoundMatrixTopology **is closed cover like on the picture below, for matrix 6×5 and winning neuron number 22 with radius 2.1 it returns following neighbor neurons.

As you see it also returned 4 as connected neuron.

Same situation for **SimpleMatrixToplogy **returns next:

So far we have visual explanation how it searches for the neighbor neurons. On the picture below we could see which distances are returned by the **
GetNeuronsInRadius **method.

For my research I’m using **SimpleMatrixTopology **because it is much faster than **BoundMatrixTopology**.

**A bit about Learning Process**

Learning process is build upon changing weights of the neurons in order to be more close to input data vector. But also with increasing iteration number we should shrink the radius where we search for neighbor neurons and we should decrease learning rate. Also those neurons which are close to winner should be modified more than those which are far from it. This purposes are supplied by three interfaces. They are IRadiusProvider, INeighbourhoodFunction and ILearningFactorFunction.

**RadiusProvider**

Answers for the question which radius we should take on the n-th iteration. Currently I have one implementation of the interface, which looks like below:

public class DefaultRadiusProvider : IRadiusProvider

{

public int MaxIterations { get; private set; }

public double

TopologyRadius { get; private set;

}

TopologyRadius { get; private set;

}

public

double TimeConstant { get; private

set; }

double TimeConstant { get; private

set; }

public

DefaultRadiusProvider(int

maxIterations, double startRadius)

DefaultRadiusProvider(int

maxIterations, double startRadius)

{

MaxIterations = maxIterations;

TopologyRadius = startRadius;

TimeConstant = maxIterations / Math.Log(startRadius);

}

public double GetRadius(int

iteration)

iteration)

{

return

TopologyRadius*Math.Exp(-iteration/TimeConstant);

TopologyRadius*Math.Exp(-iteration/TimeConstant);

}

}

As you see when we create instance of it we define **TimeConstant **and that stands for:

when we calculate radius we are using next formula:

In those two formulas **δ0** is half of the initial Grid radius and I setup it in constructor of Topology like: **Math.Max(ColCount, RowCount) / 2.0**, but of course we could choose wider initial value.

**NeighbourhoodFunction**

The most commonly used is Gauss Neighbourhood function, because it is quite smooth.

public class GaussNeighbourhoodFunction : INeighbourhoodFunction

{

public

double GetDistanceFalloff(double distance, double

radius)

double GetDistanceFalloff(double distance, double

radius)

{

double denominator = 2 *

radius * radius;

return Math.Exp(- distance / denominator);

}

}

We provide two parameters one of them is distance between neuron * i *and neuron

**LearningFactorFunction**

And as we said before, learning rate should decrease with time. For this purpose I have few implementations of the interface ILearningFactorFunction. I’m using ExponentionalFactorFunction

which has method:

public

override double

GetLearningRate(double iteration)

override double

GetLearningRate(double iteration)

{

return StartLearningRate * Math.Exp(- iteration /

MaxIterationsCount);

MaxIterationsCount);

}

The formula looks like:

where τ2 is equal to maximum iterations count and η0 is starting learning rate. I set it to the 0.07.

**Other Interfaces **

During learning process I’m using few other interfaces. They are:

**ShuffleProvider **– provides method using which I shuffle input space vectors on each epoch.

**LearningDataProvider **– gives us possibility to get i-th input vector and answers for questions how many there are vectors and what is the dimension of input space. Using this interface I can mask providing of completely random input vectors as I did in this application. Or I can provide **DataPersister **into it, so it will be able read data from file or whatever.

**MetricFunction **– is just distance measurement for our grid. I have **CityBlocks **and **Euclidean** implementations.

**SomLearningProcessor**

With mix of all described above we can build our Learning Processor. Below is full code snippet of **SomLearningProcessor**:

public class SomLearningProcessor

{

public INetwork Network { get; private

set; }

set; }

public ITopology Topology { get; private set; }

protected

IShuffleProvider

ShuffleProvider { get; set; }

IShuffleProvider

ShuffleProvider { get; set; }

protected ILearningDataProvider LearningDataProvider { get; set; }

protected

IRadiusProvider

RadiusProvider { get; private set;

}

IRadiusProvider

RadiusProvider { get; private set;

}

protected

INeighbourhoodFunction

NeighbourhoodFunction { get; set; }

INeighbourhoodFunction

NeighbourhoodFunction { get; set; }

protected IMetricFunction MetricFunction { get; set; }

protected

ILearningFactorFunction

LearningFactorFunction { get; set; }

ILearningFactorFunction

LearningFactorFunction { get; set; }

protected

int MaxIterationsCount { get; set; }

int MaxIterationsCount { get; set; }

public SomLearningProcessor(

ILearningDataProvider

learningDataProvider,

learningDataProvider,

INetwork network,

IMetricFunction

metricFunction,

metricFunction,

ILearningFactorFunction

learningFactorFunction,

learningFactorFunction,

INeighbourhoodFunction

neighbourhoodFunction,

neighbourhoodFunction,

int maxIterationsCount,

IShuffleProvider

shuffleProvider)

shuffleProvider)

{

LearningDataProvider =

learningDataProvider;

learningDataProvider;

Network =

network;

network;

Topology =

network.Topology;

network.Topology;

MetricFunction =

metricFunction;

metricFunction;

LearningFactorFunction = learningFactorFunction;

NeighbourhoodFunction = neighbourhoodFunction;

MaxIterationsCount =

maxIterationsCount;

maxIterationsCount;

ShuffleProvider = shuffleProvider;

RadiusProvider = new DefaultRadiusProvider(maxIterationsCount,

Topology.WholeTopologyRadius);

Topology.WholeTopologyRadius);

}

public virtual

void Learn()

void Learn()

{

int vectorsCount =

LearningDataProvider.LearningVectorsCount;

LearningDataProvider.LearningVectorsCount;

IList<int> suffleList = new ShuffleList(vectorsCount);

for (int

iteration = 0; iteration < MaxIterationsCount; iteration++)

iteration = 0; iteration < MaxIterationsCount; iteration++)

{

suffleList = ShuffleProvider.Suffle(suffleList);

for (int

dataInd = 0; dataInd < vectorsCount; dataInd++)

dataInd = 0; dataInd < vectorsCount; dataInd++)

{

double[] dataVector =

LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);

LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);

int bestNeuronNum =

FindBestMatchingNeuron(dataVector);

FindBestMatchingNeuron(dataVector);

AccommodateNetworkWeights(bestNeuronNum, dataVector, iteration);

}

}

}

protected

virtual int

FindBestMatchingNeuron(double[]

dataVector)

virtual int

FindBestMatchingNeuron(double[]

dataVector)

{

int result = -1;

Double minDistance = Double.MaxValue;

for (int i

= 0; i < Network.Neurons.Count; i++)

= 0; i < Network.Neurons.Count; i++)

{

double distance =

MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);

MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);

if

(distance < minDistance)

(distance < minDistance)

{

minDistance = distance;

result = i;

}

}

return

result;

result;

}

protected

virtual void

AccommodateNetworkWeights(int

bestNeuronNum, double[] dataVector, int iteration)

virtual void

AccommodateNetworkWeights(int

bestNeuronNum, double[] dataVector, int iteration)

{

var radius = RadiusProvider.GetRadius(iteration);

var

effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);

effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);

foreach (var

effectedNeuron in

effectedNeurons.Keys)

effectedNeuron in

effectedNeurons.Keys)

{

var

distance = effectedNeurons[effectedNeuron];

distance = effectedNeurons[effectedNeuron];

AccommodateNeuronWeights(effectedNeuron, dataVector, iteration,

distance, radius);

}

}

protected

virtual void

AccommodateNeuronWeights(int

neuronNumber, double[] dataVector, int iteration, double

distance, double radius)

virtual void

AccommodateNeuronWeights(int

neuronNumber, double[] dataVector, int iteration, double

distance, double radius)

{

var neuronWghts =

Network.Neurons[neuronNumber].Weights;

Network.Neurons[neuronNumber].Weights;

var

learningRate = LearningFactorFunction.GetLearningRate(iteration);

learningRate = LearningFactorFunction.GetLearningRate(iteration);

var

falloffRate = NeighbourhoodFunction.GetDistanceFalloff(distance,

radius);

falloffRate = NeighbourhoodFunction.GetDistanceFalloff(distance,

radius);

for (int

i = 0; i < neuronWghts.Length; i++)

{

double weight = neuronWghts[i];

neuronWghts[i] += learningRate * falloffRate *

(dataVector[i] – weight);

}

}

}

Lets talk a bit about each of the methods.

**public virtual
void Learn()**

It is the main public method which could be used in outside world, so ti will learn **Network **using all stuff that we injected in constructor. After Lean has executed usage code could use learned **Network **through the public property. What this method does is: it goes through all iterations up to MaxIterationsCount, then shuffles input space (or not shuffles, it depends on shuffling provider), finds Best Matching Neuron and Accommodates Network weights.

**protected
virtual int
FindBestMatchingNeuron(double[]
dataVector)**

Is the most expensive operation. As you see it goes through all the neurons in Network and calculated distance from current neuron to dataVector. Then it returns neuron with minimal distance.

**protected
virtual void
AccommodateNetworkWeights(int
bestNeuronNum, double[] dataVector, int iteration)**

Takes BMN number, asks RadiusProvider for the radius on current iteration and then asks Topology to find all neurons connected to BMN in current radius. For each found neuron it accommodates weights in next method.

**protected
virtual void
AccommodateNeuronWeights(int
neuronNumber, double[] dataVector, int iteration, double
distance, double radius)**

The most interesting line of code in this method is actual accommodation:

neuronWghts[i] = neuronWghts[i] + learningRate * falloffRate *

(dataVector[i] – neuronWghts[i]);

(dataVector[i] – neuronWghts[i]);

Which stands for formula:

Why did I make all methods virtual and so much protected properties? That is intent of my next post on implementation of SOM, where I’m going to talk about Parallelization of calculations in our algorithm.

texttexttext`code`

more code

~~~~