Szkoła cz. 2 – Winner Takes All

Prowadzący zajęcia ze Sztucznej Inteligencji nie pozwala odpocząć moim szarym komórkom serwując kolejne zadanie z sieci neuronowych. Tym razem jednak nie musiałem rozwiązywać konkretnego problemu, a jedynie przedstawić działanie algorytmu.

Zadanie:

Napisać program prezentujący w sposób graficzny naukę neuronów stosując proces nauki bez nauczyciela. Uczenie przeprowadzić z wykorzystaniem jednego z algorytmów WTA (Winner Takes All) lub WTM (Winner Takes Most).

Krótkie postawy teoretyczne:

Nauka bez nauczyciela (sieć samoorganizująca się) – W tym procesie nauki pożądana odpowiedź sieci nie jest znana. Sieć nie posiadając informacji o poprawności danych powstałych na wyjściu, uczy się poprzez analizę pobudzenia, w trakcie tej analizy parametry sieci podlegają zmianom.

Nauka z algorytmem WTA:

  1. inicjalizacja wag sieci
    • neuron1 (w1, w2) = (1, 3)
    • neuron2 (w1, w2) = (2, 4)
  2. wzór na obliczenie odległości wektora wejściowego do wag każdego z neuronów:
    • d = sqrt((w1 – x1)^2 + (w2 – x2)^2)
  3. wybranie neuronu zwycięzcy (wygrywającego) dla którego odległość wag od wektora wejściowego jest najmniejsza (na podstawie Euklidesowej miary odległości).
    • Zwyciężył neuron2 ponieważ ma odległość mniejszą od neuron1.
  4. zmiana wartości poszczególnych wag tego neuronu przyjmując, że szybkość nauki wynosi n = 0,6
  5. powtórzenie kroków 2-5 dla wszystkich przykładów uczących.
  • Obliczenia (d):

    dn1 = sqrt((1 – 5)^2 + (3 – 8)^2) = sqrt(41) = 6,40

    dn2 = sqrt((2 – 5)^2 + (4 – 8)^ 2) = sqrt(25) = 5

  • Obliczenia (w):

    w1’ = w1 + n * (x1 – w1) = 2 + 0,6 * (5 – 2) = 3,8

    w2’ = w2 + n * (x2 – w2) = 4 + 0,6 * (8 – 4) = 6,4

Implementacja:

Cała samoorganizująca się sieć miała składać się jakby z dwóch części:

  1. Rodzin losowo wybranych punktów
  2. Losowo lub „ręcznie” dodanych neuronów

Postanowiłem więc utworzyć takie oto klasy reprezentujące powyższą sytuację:
Klasa „Characteristics”:

Klasa abstrakcyjna zawierająca właściwość zwracającą rodziny punktów, bądź utworzone neurony.
Zawiera także metodę Prepare() przygotowująca rodziny punktów, bądź neurony.

public abstract class Characteristics
{
        protected List<DataTable> _listOfAttribute;
        public abstract void Prepare();
}

Klasa „FamiliesOfPoints”:

Klasa dziedzicząca po „Characteristics”. Losuje rodziny punktów z wyznaczonego przedziału, oraz udostępnia je w postaci listy typu DataTable.

class FamiliesOfPoints : Characteristics
{
/// <summary>
/// Ilosc rodzin
/// </summary>
private int _amount;
/// <summary>
/// Obiekt pozwalajacy na losowanie liczb
/// </summary>
private Random _random;

/// <summary>
/// Wlasciwosc udostepniajaca obiekty
/// DataTable zawierajace rodziny punktow
/// </summary>
public List<DataTable> FamiliesPoints
{
  get
  {
    return base._listOfAttribute;
  }
}
/// <summary>
/// Konstruktor klasy
/// </summary>
/// <param name="amount">Ilosc rodzin punktow</param>
public FamiliesOfPoints(int amount)
{
base._listOfAttribute = new List<DataTable>();
_amount = amount;
_random = new Random(DateTime.Now.Millisecond);
}

/// <summary>
/// Metoda przygotowujaca rodziny punktow
/// Uruchamia losowanie
/// </summary>
public override void Prepare()
{
//Wylosowane liczby sa typu double
string switchOperand = "x1";
for (int i = 0; i < _amount; i++)
{
  //Wylosowanie czesci ulamkowej
  double doubleValue = RandomDoubleNumber();

  //Wylosowanie punktu i dodanie
  //czesci ulamkowej do niego
  double x2 = RandomIntNumber() + doubleValue;
  double x1 = RandomIntNumber() + doubleValue;

  //Utworzenie DataTable przechowujacego dana rodzine punktow
  DataTable dataTable = new DataTable("Family "
                       + i.ToString());
  dataTable.Columns.Add(new DataColumn("X1"));
  dataTable.Columns.Add(new DataColumn("X2"));

//Utworzenie punktow z danej rodziny na
//podstawie pierwszego wylosowanego punktu
//Przesuwam o wyznaczona wartosc punkt x1
//dodajac nowo wylosowana czesc ulamkowa lub x2
  switch (switchOperand)
  {
    case "x1":
     dataTable.Rows.Add(new object[] {
            Math.Round(i + RandomDoubleNumber(), Math.Round(x2, 2) });
     dataTable.Rows.Add(new object[] {
          Math.Round(i + RandomDoubleNumber() + 2, 2), Math.Round(x2 - 2, 2) });
     dataTable.Rows.Add(new object[] {
         Math.Round(i + RandomDoubleNumber() + 2, 1), Math.Round(x2 + 2, 1) });
     dataTable.Rows.Add(new object[] {
         Math.Round(i + RandomDoubleNumber() + 2, 2), Math.Round(x2, 2) });
     dataTable.Rows.Add(new object[] {
         Math.Round(i + RandomDoubleNumber() + 2, 1), Math.Round(x2, 1) });
     switchOperand = "x2";
    break;
	case "x2":
     dataTable.Rows.Add(new object[] { Math.Round(x1, 2),
				   Math.Round(x2, 2) });
	 dataTable.Rows.Add(new object[] { x1, Math.Round(x2 - 2, 2) });
     dataTable.Rows.Add(new object[] { x1, Math.Round(x2 + 2, 1) });
     dataTable.Rows.Add(new object[] { Math.Round(x1 + 2, 2),
	               Math.Round(x2 + 2, 2) });
     dataTable.Rows.Add(new object[] { Math.Round(x1 - 2, 1),
	               Math.Round(x2 - 2, 1) });
     switchOperand = "x1";
    break;
}
  _listOfAttribute.Add(dataTable);
}
}

/// <summary>
/// Metoda losujaca liczbe calkowita
/// </summary>
/// <returns>Zwraca wylosowana liczbe
/// w postaci typu double</returns>
private double RandomIntNumber()
{
  return _random.Next(3, 98);
}

/// <summary>
/// Losuje liczbe z przedzialu (0, 1)
/// </summary>
/// <returns>Zwraca wartosc liczby</returns>
private double RandomDoubleNumber()
{
  return Math.Round(_random.NextDouble(), 1);
}
}
}

Klasa „Neurons”:

Klasa dziedzicząca po „Characteristics”. Wagi neuronów pobierane są z pliku .xml lub losowane.

class Neurons : Characteristics
{
/// <summary>
/// Zmienna identyfikujaca sposob
/// tworzenia neuronow
/// odczyt z pliku/losowanie
/// </summary>
private object _neuronMode;

/// <summary>
/// Wlasciwosc zwracajaca obiekt
/// DataTable zawierajacy neurony
/// </summary>
public DataTable FamilyNeurons
{
  get
  {
    return base._listOfAttribute[0];
  }
}
/// <summary>
/// Szybkosc uczenia
/// </summary>
public double N
{
  get;
  private set;
}

/// <summary>
/// Konstruktor klasy
/// </summary>
/// <param name="neuronMode">Sposob tworzenia neuronow</param>
/// <param name="n">Szybkosc nauki</param>
public Neurons(object neuronMode, double n)
{
  base._listOfAttribute = new List<DataTable>();
  _neuronMode = neuronMode;
  N = n;
}
/// <summary>
/// Metoda przygotowujaca neurony
/// Kontroluje jakiego typu
//jest zmienna _neuronMode
/// Jesli jest to zmienna typu
///string przyjmuje to za sciezke do
/// pliku i uruchamia metode ReadFromFile()
/// Jesli jest to liczba typu int uruchamia metode
/// RandomNeurons()
/// </summary>
public override void Prepare()
{
  if (_neuronMode.GetType().Equals(typeof(string)))
  {
    ReadFromFile((string)_neuronMode);
  }

  if (_neuronMode.GetType().Equals(typeof(int)))
  {
    RandomNeurons();
  }
}
/// <summary>
/// Metoda odczytujaca z pliku,
// wagi poszczegolnych neuronow
/// </summary>
/// <param name="path">Sciezka do pliku</param>
private void ReadFromFile(string path)
{
  //Utworzenie obiektu DataTable
  //przechowujacego wagi
  //oraz identyfikator danego neuronu
  DataTable neuronsTable =
	new DataTable("Neurons");
  neuronsTable.Columns.Add(new DataColumn("Id"));
  neuronsTable.Columns.Add(new DataColumn("W1"));
  neuronsTable.Columns.Add(new DataColumn("W2"));

  //Utworzenie dokumentu XPathDocument pozwalajacego odczytac
  //plik xml z neuronami
  XPathDocument xPathDocument = new XPathDocument(path);
  int idNeuron = 0;
  XPathNavigator nav = xPathDocument.CreateNavigator();
  XPathNodeIterator iter = nav.Select("/Neurons/Neuron/*");

  object[] weights = new object[3];

  while (iter.MoveNext())
  {
    idNeuron++;
    weights[0] = idNeuron;
   //Sprawdzam czy aktualny node ma nazwe W1
    if (iter.Current.Name.Equals("W1"))
    {
      weights[1] = iter.Current.ValueAsDouble;
    }
    iter.MoveNext();
   //Sprawdzam czy aktualny node ma nazwe W2
    if (iter.Current.Name.Equals("W2"))
    {
      weights[2] = iter.Current.ValueAsDouble;
    }

   neuronsTable.Rows.Add(weights);
  }

  _listOfAttribute.Add(neuronsTable);
}

/// <summary>
/// Metoda losujaca wagi neuronow
/// </summary>
private void RandomNeurons()
{
  DataTable neuronsTable =
	new DataTable("Neurons");
  neuronsTable.Columns.Add(new DataColumn("Id"));
  neuronsTable.Columns.Add(new DataColumn("W1"));
  neuronsTable.Columns.Add(new DataColumn("W2"));

  //Utworzenie obiektu umozliwiajacego losowanie
  Random random =
	new Random(DateTime.Now.Millisecond);
 for (int i = 0; i < (int)_neuronMode; i++)
 {
  int w1 = random.Next(4, 97);
  int w2 = random.Next(4, 97);

  neuronsTable.Rows.Add(new object[] {
        i + 1,
         w1,
         w2 });
 }

  _listOfAttribute.Add(neuronsTable);
}
}

Plik xml zawierający wagi neuronów:

<?xml version="1.0" encoding="utf-8" ?>
<Neurons>
  <Neuron>
    <W1>1</W1>
    <W2>2</W2>
  </Neuron>
  <Neuron>
    <W1>2</W1>
    <W2>5</W2>
  </Neuron>
  <Neuron>
    <W1>4</W1>
    <W2>1</W2>
  </Neuron>
  <Neuron>
    <W1>7</W1>
    <W2>1</W2>
  </Neuron>
  <Neuron>
    <W1>4</W1>
    <W2>6</W2>
  </Neuron>
</Neurons>

Implementując dalej algorytm WTA postanowiłem poskładać sieć w całość wykorzystując wzorzec projektowy o nazwie „Builder” Wzorzec ten pozwolił mi oddzielić sposób tworzenia składników sieci i udostępnić obiekt reprezentujący algorytm WTA – złożony z tychże składników.

Interfejs „INetworkBuilder”:

W pierwszym kroku utworzyłem interfejs zlecający budowę konkretnych części danego algorytmu i zwracający utworzony obiekt z tych części.

interface INetworkBuilder
    {
        void BuildPointsClass(int amount);
        void BuildNeurons(object neuronMode, double n);
        Algorithm GetAlgorithm();
    }

Klasa „AlgorithmBuilderWTA”:

Następnie stworzyłem klasę implementująca ten interfejs – budującą zgodnie z wytycznymi interfejsu wybrany algorytm. (W tym przypadku algorytm WTA)

class AlgorithmBuilderWTA : INetworkBuilder
{
   private Algorithm _algorithmWTA = new AlgorithmWTA();

#region IBuilder Members
/// <summary>
/// Metoda uruchamiajac proces losowania punktow
/// </summary>
/// <param name="amount">Ilosc rodzin punktow</param>
public void BuildPointsClass(int amount)
{
  Characteristics familiesOfPoints =
  	new FamiliesOfPoints(amount);
  familiesOfPoints.Prepare();
  (_algorithmWTA as AlgorithmWTA).AddPartAlgorithm(familiesOfPoints);
}

/// <summary>
/// Metoda uruchamiajaca tworzenie neuronow
/// </summary>
/// <param name="neuronMode">Sposob tworzenie: odczyt z pliku/losowanie</param>
/// <param name="n">Szybkosc nauki</param>
public void BuildNeurons(object neuronMode, double n)
{
  Characteristics neurons =
		new Neurons(neuronMode, n);
  neurons.Prepare();
  (_algorithmWTA as AlgorithmWTA).AddPartAlgorithm(neurons);
}

/// <summary>
/// Metoda zwracajaca obiekt utworzonego algorytmu WTA
/// </summary>
/// <returns>Algorithm obiekt</returns>
public Algorithm GetAlgorithm()
{
	return _algorithmWTA;
}

#endregion
}
}

Kolejnym krokiem było stworzenie dwóch klas. Algorithm – niejako „spina” w jedną rodzinę klasy reprezentujące algorytmy nauki sieci (w moim przypadku mam tylko jeden algorytm, klasa nie zawiera żadnych składowych), oraz klasę AlgorithmWTA – oto ich kody.

Klasa „Algorithm”:

public abstract class Algorithm
{
}

Klasa „AlgorithmWTA”:

class AlgorithmWTA : Algorithm
{
#region Fields &amp;amp; Properties
/// <summary>
/// Obiekt rodziny punktow
/// </summary>
private FamiliesOfPoints _familiesPoints;
/// <summary>
/// Obiekt neuronow
/// </summary>
private Neurons _neurons;
/// <summary>
/// Wlasciwosc zwracajaca Neurony
/// </summary>
public DataTable FamilyNeurons
{
  get
  {
    return _neurons.FamilyNeurons;
  }
}
/// <summary>
/// Wlasciwosc zwracajaca rodziny punktow
/// </summary>
public List<DataTable> FamilyPoints
{
  get
  {
    return _familiesPoints.FamiliesPoints;
  }
}
/// <summary>
/// Wlasciwosc zwracajaca neurony nauczone
/// </summary>
public DataTable ChangedNeurons
{
  get;
  private set;
}
#endregion

#region Public Methods
/// <summary>
/// Metoda dodajaca obiekty: Kolejne skladowe
/// niezbedne do uruchomienia
/// procesu nauki algorytmem WTA
/// </summary>
/// <param name="part">Skladowe</param>
public void AddPartAlgorithm(Characteristics part)
{
  if (part.GetType().Equals(
           typeof(FamiliesOfPoints)))
  {
    _familiesPoints = (FamiliesOfPoints)part;
  }

  if (part.GetType().Equals(
           typeof(Neurons)))
  {
    _neurons = (Neurons)part;
  }
}
/// <summary>
/// Metoda uruchamiajaca proces nauki
/// </summary>
public void TeachNeurons()
{
if (_familiesPoints != null
		&amp;amp;&amp;amp; _neurons != null)
{
  int max = _familiesPoints.FamiliesPoints[0].Rows.Count;

  ChangedNeurons = GetNewNeuronsDataTable();

 foreach (DataRow row in _neurons.FamilyNeurons.Rows)
 {
   ChangedNeurons.Rows.Add(new object[] {
		row["Id"],
		row["W1"],
		row["W2"]});
 }

   DataRow winner = null;
 //Rozpoczecie procesu obliczania kolejnych
 //zwyciezcow dla danych wektorow uczacych
 //Petla zewnetrzna jest wykonywana tyle razy
 //ile wynosi ilosc najwiekszej rodziny punktow
 //W tym wypadku rodziny maja stala wielkosc 5 punktow
 for (int i = 0; i < max; i++)
 {
  //Petla wewnetrzna wybiera po jednym
  // punkcie z kazdej rodziny
  //Kolejno wyliczani sa zwyciezkie
  //neurony dla danego punktu
   for (int j = 0; j < _familiesPoints.FamiliesPoints.Count; j++)
   {
     DataTable dataTable = _familiesPoints.FamiliesPoints[j];

     if (max >= dataTable.Rows.Count)
     {
       max = dataTable.Rows.Count;
     }
   //Metoda ElementAtOrDefault(i) wyciaga po
   //jednym punkcie z kazdej rodziny
     DataRow point =
	    dataTable.Rows.OfType<DataRow>().ElementAtOrDefault(i);

     if (point != null)
     {
      //Obliczany jest zwyciezca
       winner = CalculateWinner(point);
     }

     if (winner != null)
     {
       CalculateWeights(point,
	         winner["Id"].ToString());
     }
   }
 }
}
}
#endregion

#region Help Methods
/// <summary>
/// Metoda obliczajaca zwyciezce dla
/// danego punku v i neuronow
/// </summary>
/// <param name="v">Punkt</param>
/// <param name="neurons">Neurony z aktualnymi wagami</param>
/// <returns>Zwyciezki neuron</returns>
private DataRow CalculateWinner(DataRow v)
{
  DataRow winner = null;
 if (v != null)
 {
    List<double> neuronsList =
		new List<double>();

    double valueOne;
    double valueTwo;

  for (int i = 0; i < ChangedNeurons.Rows.Count; i++)
  {
    valueOne = double.Parse(ChangedNeurons.Rows[i]["W1"].ToString())
	- double.Parse(v["X1"].ToString());
    valueTwo = double.Parse(ChangedNeurons.Rows[i]["W2"].ToString())
	- double.Parse(v["X2"].ToString());
    neuronsList.Add(Math.Round(Math.Sqrt(Math.Pow(valueOne, 2)
	+ Math.Pow(valueTwo, 2)), 2));
  }
  winner = ChangedNeurons.Rows.OfType<DataRow>()
     .ElementAtOrDefault(
		neuronsList.IndexOf(neuronsList.Min())
	);
 }

  return winner;
}
/// <summary>
/// Oblieczenie nowych wag dla danego neuronu
/// </summary>
/// <param name="neurons">Aktualne neurony</param>
/// <param name="v">Punkt</param>
/// <param name="idNeuron">Identyfikator neuronu
/// zapisany w DataTable</param>
private void CalculateWeights(DataRow v, string idNeuron)
{
  //Wyszukanie pierwszego neuronu zgodnego
  // z podanym Id w DataTable neurons
  DataRow neuron = ChangedNeurons.Rows.OfType<DataRow>()
	.FirstOrDefault(dr =>
  {
    return dr["Id"].Equals(idNeuron);
  });

 //Obliczenie nowych wag dla neuronow
 if (neuron != null)
 {
   neuron["W1"] = double.Parse(neuron["W1"].ToString())
   + _neurons.N * (double.Parse(v["X1"].ToString())
   - double.Parse(neuron["W1"].ToString()));

   neuron["W2"] = double.Parse(neuron["W2"].ToString())
   + _neurons.N *(double.Parse(v["X2"].ToString())
   - double.Parse(neuron["W2"].ToString()));
 }
}
/// <summary>
/// Utworzenie nowej tabeli dla neuronow
/// </summary>
/// <returns>Tabela</returns>
private DataTable GetNewNeuronsDataTable()
{
  var columnCollection = from colName
    in _neurons.FamilyNeurons.Columns.OfType<DataColumn>().AsEnumerable()
    select new DataColumn(colName.ColumnName);

  DataTable neurons = new DataTable();
  foreach (DataColumn column in columnCollection)
  {
    neurons.Columns.Add(column);
  }
    return neurons;
}
#endregion
}

Ostatnim etapem było utworzenie klasy uruchamiającej cały proces tworzenia.

Klasa „AlgorithmManager”:

class AlgorithmManager
{
/// <summary>
/// Metoda tworzaca algorytm WTA,
///przyjmujaca klase budujaca algorytm
/// oraz poszczegolne skladowe niezbedne
/// do utworznie algorytmu
/// </summary>
/// <param name="algorithmBuilder">Klasa budujaca algorytm</param>
/// <param name="amountOfPoints">Ilosc rodzin punktow</param>
/// <param name="neuronMode">Sposob tworzenia neuronow</param>
/// <param name="n">Szybkosc nauki</param>
public void BuildAlgorithm(INetworkBuilder algorithmBuilder, int amountOfPoints,
		object neuronMode, double n)
{
  algorithmBuilder.BuildPointsClass(amountOfPoints);
  algorithmBuilder.BuildNeurons(neuronMode, n);
}
}

Dodanie kolejnego algorytmu nauki sieci jest dość proste dzięki zastosowanemu wzorcowi – sprowadza się tylko do implementacji jednej klasy reprezentującej dany algorytm.

Przykładowe uruchomienie procesu nauki:
Ilość rodzin punktów: 5;
Neurony (Losowane) – ilość: 6;
Szybkość nauki n: 0,6.

INetworkBuilder algorithmBuilder = new AlgorithmBuilderWTA();

AlgorithmManager manager = new AlgorithmManager();
manager.BuildAlgorithm(algorithmBuilder, 5, 6, 0,6);
Algorithm algorithm = algorithmBuilder.GetAlgorithm();

AlgorithmWTA wta = (AlgorithmWTA)algorithm;
wta.TeachNeurons();

Na koniec zamieszczam screeny obrazujące wyniki działania algorytmu WTA.

Neurony pobrane z wpisanych wag w pliku xml:

xmlneurons.jpg

Neurony wylosowane:

losneurons.jpg
  1. Coz mam powiedziec, good work, dobrze opisane. Dzieki!

  2. Dzięks. ;) Przedmiot do najłatwiejszych nie należy – może to komuś pomoże zrozumieć.

    • MaRCHeW
    • 9 kwietnia 2009

    Witam.

    Świetny tekst. Interesuję się Forex’em oraz programowaniem automatycznych strategii do handlu na giełdzie w MQL4 oraz C#. Od pewnego czasu starałem się zrozumieć sieci neuronowe by wspomóc swoje programy w procesie podejmowania decyzji. Twój tekst wprowadził mnie w temat. Dzięki wielkie :D

    • podziękował :)
    • 30 marca 2014

    Wielkie dzięki :) Akurat przerabiamy ten materiał z Panem dr Klimkiem i nie wiedziałem jak się za to zabrać. Dobra robota!

  1. Na razie brak trackbacków