Podrobný sylabus prednášky

Neurónové siete

 

Fenomén neurónových sietí (NS)

 

- sú inšpirované biologickými neurónovými sieťami

- využívajú distribuované, paralelné spracovanie informácie pri vykonaní výpočtov

- znalosti sú ukladané predovšetkým prostredníctvom sily väzieb medzi jednotlivými neurónmi

- učenie je základná a podstatná vlastnosť neurónových sietí

 

 

História

 

- Warren Mc Culloch, Walter Pitts, 1943

            -najjednoduchšie typy NS ... ľubovoľná aritmetická alebo logická funkcia

- Donald Hebb: The Organization of Behavior, 1949

            -učiace pravidlo pre synapsie neurónov

- prvý neuropočítač Smark, 1951, Marwin Minsky

- Frank Rosenblatt, 1957... perceptrón, učiaci algoritmus  - Principles of Neurodynamics

- 1957, 1958 Mark I -  Perceptron

- ADALINE

- Nils Nilsson: Learning Machines, 1965

- 1967-1982  - ojedinelý výskum, NS zaznávané

- 80. roky

- 1982,84 John Hopfield – vyznačne sa zaslúžil o pokračovanie vo výskume NS

 

 

Umelé neurónové siete sú vlastne:

 

- paralelné výpočtové modely - husto poprepájané adaptívne jednotky (procesory)

- adaptívna povaha – "učenie z príkladov" - čo je veľmi žiadané v aplikáciách, kde :

·        tréningové údaje sú k dispozícii

·        je neúplné porozumenie riešeného problému - výpočtové modely pre triedy problémov:

(a)    klasifikácia

(b)   syntéza a rozpoznávanie reči

(c)    aproximácia funkcií

(d)   kompresia údajov

(e)    vyhľadávanie klastrov

(f)     predikcia

(g)    kombinatorické optimalizačné úlohy

(h)    modelovanie nelineárnych systémov

(i)      riadenie

 

 

 

 

Prahové jednotky (Threshold Gates)

 

Lineárne prahové jednotky - LTG

 

Základná funkcia  -  rozlišovať body (vektory) patriace do dvoch tried.

 

Prenosová funkcia LTG je daná analyticky
 
                    ak     ,

                    inak.

 

kde

x=(x1,x2,...,xn)T            sú vstupné hodnoty

w=(w1,w2,...,wn)          hodnoty váh

T je prahová hodnota.

 

Vektor x je n - rozmerný s binárnymi alebo reálnymi zložkami

- xÎ(0,1)n  alebo xÎRn

- váhy w Î Rn

 

LTG počíta jedno z nasledujúcich zobrazení:

- xÎ(0,1)n  Þ y :  {0,1}n  ® {0,1}

- xÎRn       Þ y :  Rn ® {0,1}

 

Príklad realizácie booleovskej funkcie pomocou LTG

y(x1, x2, x3)= x1 x2 + x2  x3.

pomocou LTG, pričom podčiarknuté sú negácie.

 

Problém : skonštruovať LTG pre booleovskú funkciu XOR - y(x1,x2)

                  y(0,0) = y(1,1) = 0, y(0,1) = y(1,0) = 1

 

Booleovská funkcia, ktorá je realizovateľná pomocou jednej LTG sa nazýva prahová funkcia.

 

Prahová funkcia je lineárne separovateľná funkcia, tj. funkcia so vstupmi patriacimi do dvoch rôznych tried takými, že vstupy jednej triedy môžu byť geometricky separované od vstupov druhej triedy nadrovinou.

 

Porovnanie počtov prahových funkcií vs. počtov všetkých možných booleovských funkcií pre vybrané hodnoty n.

 

n

Bn

Total number of BF

1

4

4

2

14

16

3

104

256

4

1882

65536

5

94572

4,3 . 109

6

15028134

1,8 . 1019

 
 
 

 

 

 

 


Polynomiálne prahové jednotky

 

KVADRATICKÉ prahové jednotky

 
 
                    ak         

                    inak

 

 

kde x=[x1,x2,...,xn]T sú vstupy a w=(w1,...,wn,w12,...,wnn] sú hodnoty váh, T je prahová hodnota.

 

 

Kvadratická prahová jednotka pre XOR:   w1=0.3, w2=0.3, w12=-0.5, T=0.2

 

 

 

POLYNOMIÁLNE prahové jednotky – zovšeobecnenie;
 
 

 

 

 

 


Výpočtové schopnosti polynomiálnych prahových jednotiek

 

 

Veta: [Nilsson, 1965; Krishnan,1966]

Ľubovoľná booleovská funkcia n premenných môže byť realizovaná pomocou polynomiálnej prahovej jednotky rádu r, r £ n.

 

Veta: [Weierstrass]

Nech g je spojitá reálna funkcia, definovaná na uzavretom intervale [a, b]. Potom pre ľubovoľné e > 0, existuje polynóm y (ktorý môže závisieť od e) s reálnymi koeficientami taký, že pre každé x z intervalu [a, b] platí |g(x)-y(x)| < e

 

 

Veta hovorí, že:

Každá spojitá funkcia môže byť aproximovaná pomocou polynómu.

Rád polynómu závisí od funkcie, ktorá je aproximovaná, a od presnosti aproximácie.

 

Dôkaz ... Apostol, T. M.(1957) Mathematical Analysis: A modern approach to advanced calculus. Addison-Wesley, Reading, Mass.

 

 

 

 

 

 

 

 

Perceptróny, učiace pravidlá

 

Perceptrónová výpočtová jednotka.

 

Učiace pravidlá pre perceptróny

Predpokladajme, že trénujeme perceptrón pomocou tréningovej množiny – dvojice

{ (x1, d1),  (x2, d2), ..., (xm, dm) },

kde xk Î Rn+1 je k-tý vstupný vektor a dk Î{-1,+1}, k=1, 2,..., m je predpokladaná trieda (cieľ) pre k-tý vstupný vektor (poradie dvojíc - náhodné)

 

Správna klasifikácia

Cieľ - navrhnúť perceptrón, ktorý pre každý vstupný vektor xk  tréningovej množiny dá výstup yk, ktorý sa zhoduje s cieľom dk. Teda yk = sgn(wTxk)= dk, k=1, 2,..., m.

 

Riešenie w* - učiace pravidlo (Rosenblatt, 1962):

 
 
   W1 =  arbitrary

 

   Wk+1 = wk + ro (dk - yk)xk    k=1,2,...

 

kde ro je kladná konštanta - učiaci pomer.

 

Poznámky:

- ak riešenie existuje, potom je dosiahnuté po konečnom počte iterácií;

- vo všeobecnosti táto metóda poskytuje nekonečný počet riešení;

- perceptrónové učiace pravidlo konverguje k jednému z nich;

- riešenie je citlivé na hodnotu učiaceho pomeru ro, ktorá koriguje prezentáciu dvojice;

- počet korekcií k0 závisí od výberu počiatočných hodnôt vektora váh W1;

- ak riešenie neexistuje, perceptrón  to neodhalí

- vektor riešenia existuje, vtedy a len vtedy daná tréningová množina je lineárne separovateľná

 

Veta: [Novikoff, 1962; Ridgway, 1962; Nilsson,1965]}

Ak tréningová množina je lineárne separovateľná, potom učiace pravidlo pre perceptróny konverguje k riešeniu v konečnom počte iterácií.