Backpropagation neural network

Jednovrstvové neurónové siete nachádzajú svoje uplatnenie v rôznych problémoch, najmä však v problematike rozpoznávania vzorov. Perceptrón slúži ako jednoduchá neurónová sieť, ktorá dokáže separovať dve a (po modifikácii) viac množín. Nemusí sa pritom jednať priamo o množiny uvedeného typu a principiálne ani o separovateľné problémy. Je možné to aplikovať na podobné úlohy rozpoznávania aké boli popísané v predchádzajúcich článkoch ohľadne neurónových sietí. V každom prípade, jednovrstvové neurónové siete vykazujú pomerne nízku efektivitu a v spojitosti s tým sa okruh realizovateľných úloh rapídne zmenšuje. Viacvrstvové neurónové siete (vrátane neurónovej siete typu Perceptrón so skrytou vrstvou) je možné aplikovať oveľa efektívnejšie na rôzne druhy úloh, avšak najčastejšie sa používajú na riešenie rozpoznávania vzorov (Pattern Recognition). Existuje množstvo rôznych typov viacvrstvových neurónových sietí, avšak v našom prípade sa budeme zaoberať viacvrstvovou neurónovou sieťou s adaptačným algoritmom Backpropagation, tzn. spätné šírenie chyby. Keďže sa jedná o viacvrstvovú neurónovú sieť, tak pochopiteľne takáto sieť musí obsahovať minimálne dve vrstvy. Konkrétne pre túto sieť budeme potrebovať dokonca až tri vrstvy. Čo sa týka vrstiev ako takých, tak všeobecne sa používajú väčšinou tri až štyri vrstvy, tzn. jedna je vstupná vrstva, jedna je výstupná vrstva a jedna alebo dve vrstvy sú tzv. skryté vrstvy (hidden layers) (na obrázku označenie (z_1, z_2,...,z_n)).

 

V zásade sa jedná o takú istú vrstvu ako ostatné vrstvy len s tým rozdielom, že skrytá vrstva musí byť s ktoroukoľvek ďalšou vrstvou spojená spôsobom každý s každým. Skrytá vrstva slúži na efektívnejší adaptačný proces, tzn. neurónová sieť sa bude efektívnejšie učiť a poskytovať tak lepšie výsledky. Navyše komplikovanejšie úlohy si priamo vyžadujú tieto skyrté vrstvy, pretože veľakrát bez takýchto vrstiev nie je možné daný problém vyriešiť. Neurónové siete ako také sú do veľkej miery rýdzo matematický problém, konkrétne sa jedná o oblasť numerickej a štatistickej matematiky, takže všetky výpočty poukazujú na pravdepodobnostné problémy. Z toho vyplýva, že matematický popis neurónových sietí je možné klasifikovať ako problém minimalizácie nejakej funkcie. Ak si predstavíme učenie vo všeobecnosti, tak človek sa učí do určitej miery formou pokusu a omylu a z toho vyplýva, že pri takomto type učenia vznikajú chyby učenia a následne tieto chyby sú častejším opakovaním minimalizované. Podobný princíp je založený na celých neurónových sieťach a konkrétne v našom prípade sa bude jednať o sofistikované riešenie minimalizácie chýb. Keďže sme spomínali, že neurónové siete sú vhodné na rozpoznávanie obrazov (vzorov), tak v tomto prípade si popíšeme metódu Backpropagation pri riešení rozpoznávania celých čísel. Výsledný program bol napísaný v jazyku .NET C#, WinForms a vyzerá nasledovne:

Na obrázku, na ľavej strane zadávame vzor číslice, ktorú chceme rozpoznať a na pravej strane máme uvedenú rozpoznanú číslicu. Vstupná vrstva neurónov bude pozostávať zo 100 neurónov, pretože vstupná matica pre rozpoznávanie číslic obsahuje pole 10x10 bodov, teda 1 neurón odpovedá 1 políčku. Výstupná vrstva neurónov pozostáva z 10 neurónov, pretože sieť je naučená rozpoznávať 10 číslic, od 0 až 9. Skrytá vrstva obsahuje 50 neurónov. Počet týchto neurónov nie je striktne daný. Ako už bolo spomínané, závisí od daného prípadu a väčšinou sa určuje odhadom alebo testovaním. Existujú empirické vzorce podľa ktorých je možné vypočítať počet vrstiev topológie siete ako aj počet neurónov skrytej vrstvy, avšak jedná sa iba o predbežné odhady a doposiaľ prakticky neexistuje nejaký platný osvedčený predpis, vzorec, podľa ktorého by bolo možné presne spočítať počet požadovaných neurónov. V nasledujúcej časti budú popísané niektoré dôležité časti. Výstupná vrstva je jednoznačne daná a teda predstavuje už spomenuté číslice. To je možné napísať ako dvojrozmerné pole vektorov od 0 až 9

//0
output[0, 0] = 1;
output[0, 1] = 0;
output[0, 2] = 0;
output[0, 3] = 0;
output[0, 4] = 0;
output[0, 5] = 0;
output[0, 6] = 0;
output[0, 7] = 0;
output[0, 8] = 0;
output[0, 9] = 0;

//1
output[1, 0] = 0;
output[1, 1] = 1;
output[1, 2] = 0;
output[1, 3] = 0;
output[1, 4] = 0;
output[1, 5] = 0;
output[1, 6] = 0;
output[1, 7] = 0;
output[1, 8] = 0;
output[1, 9] = 0;

.
.
.

//9
output[9, 0] = 0;
output[9, 1] = 0;
output[9, 2] = 0;
output[9, 3] = 0;
output[9, 4] = 0;
output[9, 5] = 0;
output[9, 6] = 0;
output[9, 7] = 0;
output[9, 8] = 0;
output[9, 9] = 1;

Vstupná vrstva a skrytá vrstva sa na začiatok naplní náhodnými číslami:

void initNetwork()
{
    int i, j;

    Random rand = new Random();

    inputs[inputNeurons] = 1.0;
    hidden[hiddenNeurons] = 1.0;

    for (j = 0; j < hiddenNeurons; j++)
    {
        for (i = 0; i < inputNeurons + 1; i++)
        {
            w_h_i[j, i] = (rand.NextDouble() - 0.5);
        }
    }

    for (j = 0; j < outputNeurons; j++)
    {
        for (i = 0; i < hiddenNeurons + 1; i++)
        {
            w_o_h[j, i] = (rand.NextDouble() - 0.5);
        }
    }
}

Pole w_h_i[j, i] reprezentuje váhové hodnoty medzi skrytou a vstupnou vrstvou a pole w_o_h[j, i] reprezentuje váhové hodnoty medzi výstupnou a skrytou vrstvou. Principiálny algoritmus Backpropagation je možné nájsť na internete, napr. na tejto stránke. Výpočet jednotlivých váhových prepojení trénovacej množiny je nasledovný:

void feedForward()
{
    int i, j;

    for (i = 0; i < hiddenNeurons; i++)
    {
        hidden[i] = 0.0;

        for (j = 0; j < inputNeurons + 1; j++)
        {
            hidden[i] += (w_h_i[i, j] * inputs[j]);
        }
        hidden[i] = sigmoid(hidden[i]);
    }


    for (i = 0; i < outputNeurons; i++)
    {
        outputs[i] = 0.0;

        for (j = 0; j < hiddenNeurons + 1; j++)
        {
            outputs[i] += (w_o_h[i, j] * hidden[j]);
        }
        outputs[i] = sigmoid(outputs[i]);
    }
}

Pričom sigmoidálna funkcia má tvar:

double sigmoid(double x)
{
    return (1.0 / (1.0 + Math.Exp(-x)));
}

Samotný prepočet váhových prepojení sa uskutočňuje počas celého procesu viac-krát v závislosti od veľkosti chybovej odchýlky. Práve túto časť má na starosti programový kód po stlačení tlačidla Recognize:

Random randTrain = new Random();

double mse;
int test;
int zero = 0;

generateMap();
initNetwork();

do
{
    test = randTrain.Next(0, 10);

    setNetworkInputs(test, 0.0);
    feedForward();
    backpropagateError(test);
    mse = calculateMSE(test);

} while (mse > 0.001);

setNetworkInputsPattern();
feedForward();

for (int z = 0; z < inputNeurons; z++)
{
    zero += map[z];
}

if (zero > 0)
{
    lblOutNum.Text = classifier().ToString();
}
else
{
    lblOutNum.Text = "X";
}

V uvedenom kóde tvorí podstatnú časť cyklus, ktorým kontrolujeme danú chybovú odchýlku. Odchýlka sa prepočitáva nasledujúcim programovým kódom:

void backpropagateError(int test)
{
    int outE;
    int hidE;
    int inpE;
    double[] errOut = new double[outputNeurons];
    double[] errHid = new double[hiddenNeurons];

    for (outE = 0; outE < outputNeurons; outE++)
    {
        errOut[outE] = ((double)output[test, outE] - outputs[outE]) * sigmoid_d(outputs[outE]);
    }

    for (hidE = 0; hidE < hiddenNeurons; hidE++)
    {
        errHid[hidE] = 0.0;

        for (outE = 0; outE < outputNeurons; outE++)
        {
            errHid[hidE] += errOut[outE] * w_o_h[outE, hidE];
        }
        errHid[hidE] *= sigmoid_d(hidden[hidE]);
    }

    for (outE = 0; outE < outputNeurons; outE++)
    {
        for (hidE = 0; hidE < hiddenNeurons; hidE++)
        {
            w_o_h[outE, hidE] += RO * errOut[outE] * hidden[hidE];
        }
    }

    for (hidE = 0; hidE < hiddenNeurons; hidE++)
    {
        for (inpE = 0; inpE < inputNeurons + 1; inpE++)
        {
            w_h_i[hidE, inpE] += RO * errHid[hidE] * inputs[inpE];
        }
    }
}

Výpočet MSE, tzv. stredná štvorcová chyba je daná vzťahom:

 

pričom \hat{Y_i} je vektor predpokladaných hodnôt (v našom prípade jednotlivé výstupy číslic) a Y_i je vektor aktuálne pozorovaných výstupných hodnôt a tomu zodpovedná programový kód:

double calculateMSE(int test)
{
    double mse = 0.0;
    int i;

    for (i = 0; i < outputNeurons; i++)
    {
        mse += sqr(output[test, i] - outputs[i]);
    }

    return (mse / (double)i);
}

A pre koncový klasifikátor nasledovný kód:

int classifier()
{
    int best = 0;
    double max;

    max = outputs[0];

    for (int i = 1; i < outputNeurons; i++)
    {
        if (outputs[i] > max)
        {
            max = outputs[i];
            best = i;
        }
    }
    return best;
}

Niektoré ukážky výstupov pre jednotlivé číslice:

 

Chybovú funkciu je možné si predstaviť ako 3D povrch váhovými hodnotami na osi x a y a hodnotou chybovej funkcie na osi z. Týmto vznikne (ideálne) teleso zobrazené na obrázku nižšie. Postupne ako klesá hodnota chybovej funkcie prostredníctvom vektora, približujeme sa skutočnému, ideálnemu váhovému vektoru. Cieľom je, aby v každom kroku výpočtu vektor klesal smerom k tzv. sedlu (sedlový bod), čo predstavuje lokálne minimum.

 

Práve z toho dôvodu je nutné počítať so skrytou vrstvou neurónov a mala by byť navrhnutá tak, aby sa algoritmus nezacyklil, alebo aby váhový vektor nesmeroval mimo požadovaný sedlový bod. Existujú rôzne modifikácie tohto výpočtu, optimalizované na strmosť a rýchlosť vypočítaných hodnôt. Podrobne sa tým zaoberá už spomínaná numerická matematika, optimalizačné metódy, alebo teória diferenciálnych rovníc.