Efektivnost adaptace a učení

• T / T → 0
  Efektivnost AS je porovantelná s efektivností učícího se systému po naučení
• T / T → 1 (T / T < 1)
  AS je zhruba stejně efektivní jako neadaptivní systém
• T / T ≥ 1
  K adaptaci nedochází

Výběr a uspořádání příznaků

• Technická realizovatelnost
• Rychlost a zpracování
• Nebezpečí přeučení
• Korelace příznaků

Volba informativních příznaků

• Výběr minimálního počtu příznaků z předem zvolené množiny příznaků
  (nelze zaručit, že tato množina obsahuje informativní příznaky - volba závisí na konkrétní úloze)
• Uspořádání příznaků v předem zvolené množině příznaků
  - podle množství nesené informace - sekvenční a.

Vlastnosti Karhunen-Loeveova rozvoje

1. Při daném počtu členů rozvoje poskytuje ze všech rozvojů nejmenší střední kvadratickou odchylku od původních vzorů
2. Vzory jsou po použití disperzní matice po aproximaci nekolerované
   →dekolerace příznaků
3. Lleny rozvoje nepřispívají rovnoměrně k aproximaci - vliv každého z členů na přesnost aproximace se zmenšuje s jeho pořadovým indexem
   → vliv členů s vysokými indexy bude malý a můžeme je zanedbat (resp. vynechat)
4. Velikost chyby aproximace neovlivňuje strukturu rozvoje
   → Změna požadavků na chybu aproximace nevyžaduje přepočítávat celý rozvoj
   → stačí jen přidat či odstranit něklik posledních členů
   výhodné u sekvenčních metdo klasifikace

    ( v11 .. v1p )
    (  . .     . )
V = (  .   .   . )
    (  .     . . )
    ( vm1 .. vmp )

Výpočet matice V

• "vycentrovat data"
  u_j = (1 / n) * Suma[i = 1 .. n]x_ij
• Disperzní maitce pro trénovací množinu
  w_ij = w_ji = (1 / n) * Suma[k = 1 .. n](x_ki - u_i)(x_kj - u_j)
  
  • Vektory, které definují nejdůležitější příznaky jsou charakteristickým vektory disperzní matice
  • Charakteristická čísla odpovídají rozptylu nejdůležitějších příznaků
    → prvním sloupcem matice V bude charakteristický vektor odpovídající největšímu charakteristickému číslu, ..
  • Další sloupce V se přestanou přidávat poté, co lze další charakteristická čísla vzhledem k jejich velikosti zanedbat.

1. Centrované nejdůležitější příznaky
   y = V'(x - u), kde
   u = (u₁, ..) je vektor středních hodnot
2. Normalizace nejdůležitějších příznaků
   y = L^(-1/2) V'(x - p), kde L je matice p*p, prvky diagonály jsou charakteristická čísla odpovídající sloupcům V, ostatní prvky jsou 0
3. Normalizace nejdůležitějších příznaků vzhledem k rozptylům
   w'_ij = w_ij / sqrt( w_ii w_jj )
   sqrt(X) je druhá odmocnina z X

Formální neuron

Přenosová funkce

• Skoková:
  f(ξ) =
  • 1, jestliže ξ > 0
  • 0, v ostatních případech
  
• Sigmoidální:
  S(ξ) = 1 / (1 + e^-ξ)
  

Učení

• S učitelem:
  Trénovací množina - [vstup / požadovaný výstup]
• Bez učitele (samoorganizace):
  Chybí požadovaný výstup

Definice formálního neuronu

Definice stavů neuronu

• Jestliže f[w,v](z) = 1, říkáme, že je neuron aktivní
• Jestliže f[w,v](z) = 1/2, říkáme, že je neuron tichý;
  Tato skutečnost znamená, že příslušný vstup leží v dělící nadrovině určené tímto neuronem
• Jestliže f[w,v](z) = 0, říkáme, že je neuron pasivní.

Definice trénovacích vzorů

• vstupní vzor označuje vstupní vektor x z množiny Rⁿ zpracovávaný sítí
• požadovaný výstup d = (d₁, .., d_m) tvoří požadované výstupy neuronů výstupní vrstvy
• pro daný vstupní vzor představuje skutečný výstup B vektor y = (y₁, .., y_m) tvořený skutečnými výstupy neuronů výstupní vrstvy

Perceptron a lineární separabilita

Lineární separabilita

Absolutní lineární separabilita

• pro všechny body z A platí, že:
  Suma[i = 1 .. n]w_ia_i - (v' - Ε / 2) ≥ 0
  to znamená, že Suma[i = 1 .. n]w_ia_i - v' ≥ - Ε / 2 > 0
  → Suma[i = 1 .. n]w_ia_i > v' (+ (a₁, ..., a_n) z množiny A) (*)
• Podobně pro všechny body z B:
  Suma[i = 1 .. n]w_ib_i-v = Suma[i = 1 .. n]w_ib_i-(v'-Ε / 2) < 0
  a tedy: Suma[i = 1 .. n]w_i - v' < Ε / 2 < 0 (**)
  

Dělící nadrovina

Otevřený (uzavřený) negativní poloprostor
určený n-rozměrným váhovým vektorem w je množina všech bodů x z monžiny Rⁿ, pro které pw.x < 0 (w.x ≤ 0)

Dělicí nadrovina určená n-rozměrným váhovým vektorem w je množina všech bodů x z množiny Rⁿ, pro které w.x =

Problém : Nalézt takové váhy (resp. práh), které by umožnily separaci (oddělení) dvou množin vzorů.
→ např. perceptronový algoritmus učení
.Předp:
A ... množina vstupních vektorů v n-rozměrném prostoru
B ... množina vstupních vektorů v n-rozměrném prostoru
→ separace A a B:
Perceptron by měl realizovat binární funkci f_w tak, aby
f_w(x) = 1 pro všechna x z množiny A
f_w(x) = 0 pro všechna x z množiny B
(f_w závisí na vahách, resp. prahu)

Chybová funkce odpovídá počtu chybně "zařazených" vzorů:
E(w) = Suma[x je z množiny A](1 - f_w(x)) + Suma[x je z množiny B]f_w(x)

Cíl učení: Minimalizace E(w) ve váhovém prostoru
(→ nejlépe E(w) = 0)

Perceptronový algoritmus učení - idea

Hledáme váhový vektor w s pozitivním(P a P je třeba "odseparovat") skalárním součinem pro všechny vektory reprezentované body v P a se záporným skalárním součinem pro všechny vektory reprezentované body v N

→ Obecně: Za předpokladu, že P a N jsou množiny n-rozměrných vektorů, chceme nalézt takový váhový vektor w, že:
w.x > 0 pro všechny x z množiny P
w.x < 0 pro všechny x z množiny N

• perceptronový algoritmus učení začíná s náhodně zvoleným váhovým vektorem w₀
• pokud existuje vektor x z množiny P takový, že w.x < 0, znamená to, že úhel mezi těmito dvěma vetkroy je větší než 90^o
  
  • váhový vektor je nutné zadaptovat (~ototčit) ve směru x (tak, aby se tento vektor dostal do "pozitivního" poloprostoru definovaného w
  • otočení ve směru x lze provést přičtením x k vektoru w
• pokud existuje x z množiny N a w.x >, pak je úhel mezi x a w menší než 90^o
  
  • váhový vektor je nutné zadaptovat (~otočit) směrem od x
  • to lze provést odečtením x od w
  (vektory z P otáčejí váhový vektor opačným směrem, než vektory z N)
  → pokud existuje řešení, lze ho nalézt v konečném počtu kroků
• heuristika pro počáteční nastavení vah:
  začít s průměrem "pozitivních" vstupních vektorů minus průměr "negativních" vektorů
• parametr učení
• stupeň adaptivity vah ~ plasticita sítě

Perceptron - algoritmus učení

1. krok: Inicializace vah malými náhodnými hodnotami w_i(0); (1 ≤ i ≤ n + 1)
   w_i(0) ... váha vstupu v čase 0
   
2. krok: Předložení trénovacího vzoru ve tvaru:
   (x₁, ..., x_n+1) ... vstupní vzor
   d(t) ... požadovaný výstup (pro předložený vstup)
   
3. krok: Výpočet skutečného výstupu (odezvy sítě)
   y(t) = sgm(Suma[i = 1 .. n+1]w_i(t)x_i(t))
   
4. krok: Adaptace vah podle:
   w_i(t+1) = w_i(t) - výstup je správný
   w_i(t+1) = w_i(t) + x_i(t) - výstup je 0 a měl být 1
   w_i(t+1) = w_i(t) - x_i(t) - výstup je 1 a měl být 0
   
   
5. krok: Poku t nedosáhl požadované hodnoty, přejdi k 2. kroku
   

Modifikace: Parametr učení m (0 ≤ m ≤ 1)
~ ovlivňuje rychlost adaptace. Adaptace vah podle:
w_i(t+1) = w_i(t) - výstup je správný
w_i(t+1) = w_i(t) + m*x_i(t) - výstup je 0 a měl být 1
w_i(t+1) = w_i(t) - m*x_i(t) - výstup je 1 a měl být 0

Konvergence perceptronového algoritmu učení (Rosenblatt - 1959)

V: Nechť P a N jsou konečné a lineárně separabilní množiny. Potom provede perceptronový algoritmus učení konečný počet aktualizací váhového vektoru w_t
(Pokud se budou cyklicky testovat jeden po druhém vzory z P a N, najde perceptronový algoritmus učení po provedení konečného počtu aktualizací váhový vektor, pomocí něhož lze navzájem separovat P a N)

Důkaz: ukážeme, že perceptronový algoritmus učení přiblíží počáteční váhový vektor w₀ dostatečně blízko "hledaného řešení"w^*

• 3 zjednodušení - bez újmy na obecnosti
  1. Namísto P a N vytvoříme jedinou množinu P' = P U N^-
     (N^- tvoří "negované" prvky z N)
  2. VEktory z P' budou normalizované
     (jestliže byl nalezen váhový vektor w, pro který platí w.x > 0, potom totéž platí i pro každý další vektor .x, m > 0)
  3. Váhový vektor bude také normalizovaný
     (předpokládané normalizované řešení problému lineární separace budeme označovat jako w*)
• předpokládejme, že po t+1 aktualizacích byl vypočten váhový vektor w_t+1
  → to znamená, že po t aktualizacích byl vektor p_i (z nožiny P') chybně klasifikován (pomocí váhového vektoru w_t)
  a tedy: w_t+1 = w_t + p_i
• kosinus úhlu u mezi w_t+1 a w^* je:
  cos u = (w^*.w_t+1) / ||w_t+1|| (*)
• pro výraz v čitateli (*) víme, že:
  w^*.w_t+1 = w^*.(w_t + p_i) =
  w^*.w_t + w^*.p_i)
  ≥ w^*.w_t + d,
  kde d = min {w^*.p, p z množiny P'}
  Protože váhový vektor w^* definuje absolutní lineární separaci P a N, víme, že d > 0
  
  → indukcí dostáváme:
  w^*.w_t+1 ≥ w^*.w₀ + (t+1)*d (**)
  
• Na druhé straně víme, že pro výraz ve jmenovateli (*) platí:
  ||w_t+1||² = (w_t + p_i) * (w_t + p_i) = ||w_t||² + 2w_tp_i + ||p_i||²
  protože w_t.p_i ≤ 0
  (jinak by nebylo potřeba aktualizovat w_t podle p_i)
  platí, že:
  ||w_t+1||² ≤ ||w_t||² + ||p_i||² ≤ ||w_t||² + 1
  (protože všehcny vektory z P' byly normalizovány)
  → indukcí dostáváme:
  ||w_t+1||² ≤ ||w₀||² + (t + 1) (***)
  
• z (**) a (***) dostáváme porovnáním s (*) nerovnici:
  cos u ≥ (w.w₀ + (t+1)*d ) / sqrt(||w₀||² + (t+1))
  → pravá strana nerovnice roste proporcionálně s sqrt(t) a protože d > 0, mohla by být libovolně velká.
  Protože ale cos u ≤ 1, musí existovat horní mez a počet aktualizací váhového vektor musí být konečný
  QED
  

Přihrádkový algoritmus učení

Idea:

• nejlepší váhový vektor nalezený pomocí perceptronového algoritmu učení je "uložen v přihrádce"
• současně se pokračuje v aktualizaci váhového vektoru
• pokud se najde "lepší" váhový vektor, nahradí se ním vektor uložený v přihrádce

Start:
Náhodná inicializace váhového vektoru w a uložení váhového vektoru do přihrádky: w_s = w
Nastavení historie uloženého váhového vektoru: h_s = 0

Iterace:
aktualizace pomocí jedné iterace perceptronového algoritmu učení
aktualizace h podle po sobě jdoucích úspěšně testovaných vektorech
jestliže nastance h > h_s, nahraď w_s vektorem w a h_s číslem h.
Pokračuj v iteraci.


Protože se bere v úvahu jen informace o posledně zvolených vzorech, může dojít i k záměně "správného" váhového vektoru za horší. Pravděpodobnost tohoto jevu by však měla klesat s rostoucím počtem iterací. Pokud je trénovací množina konečná a složky váhového a příznakových vektorů jsou racionální, lze ukázat, že přihrádkový algoritmus konverguje k optimálnímu řešení s pravděpodobností 1.