Česky
Kamil Dudka

Study

File detail

Name:Downloadsfc.txt [Download]
Location: study > min
Size:15.8 KB
Last modification:2009-06-26 20:53

File content

Copyright (c)  2008  Kamil Dudka.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
Texts.  A copy of the license is included in the section entitled "GNU
Free Documentation License".

Soft Computing
==============
- nepřekládá se do češtiny
- tradiční programování ... hard-computing
- funkčním modelem pro soft-computing je lidský mozek

- není samostatná teorie, ale jakýsi deštník nad několika přístupy
    - fuzzy logika (výpočet nad slovy)
    - neuro-výpočty (identifikace systémů, učení, adaptace)
    - pravděpodobnostní usuzování (šíření míry pravděpodobnosti)
    - GA (víme...)

- predikátová logika má jednoznačný inferenční (odvozovací) mechanismus
- problém je, že často nejsme schopni sehnat kompletní soubor následků a příčin
- v praxi je nereálné popsat všechny výjimky, navíc práce s velkým množstvím
  dat je výpočetně náročná
- často je potřeba rozhodovat se na základě nekompletních informací (medicína,
  ...)


Neuronové sítě
--------------
- umělé neuronové sítě jsou založené na principech biologických neuronů
- několik modelů umělého neuronu
    - McCulloch&Pitts (původní model) - excitační/inhibiční vstupy
    - současný model umělého neuronu
        A. bázová funkce
            1) lineární (vážený součet)
            2) radiální (RBF) - vzdálenost vektoru vstupů od vektoru vah

        B. aktivační funkce
            a) nespojitá (skoková)
                - častá úprava: vstup navíc s trvale "připojenou" hodnotou 1,
                  která určuje práh
            b) po částech lineární (rampová) aktivační funkce
                - používá se velmi zřídka
            c) spojitá aktivační funkce (sigmoida)
                - podívat se na obecný vzorec sigmoidy a jeho zjednodušení
                - zjednodušený vztah je potřeba znát nazpaměť, jeho derivaci
                - derivace má zásadní vliv na učení neuronové sítě
                - odvození derivace není potřeba se učit

- klasifikace neuronových sítí
    I. podle architektury (propojení)
        a) plně propojená síť (v praxi se nepoužívá - nelze učit)
        b) plně propojená symetrická síť (Hopfield) - lze učit
        c) vrstvová síť - signál teče v jednom směru, případně po straně
        d) dopředná síť - specializace předchozího typu (nejsou příčné vazby)
                        - nejpoužívanější typ neuronové sítě
                        - typické učení tohoto typu je back propagation

    II. podle učení
        - obecně není problém naučit neuronovou síť správně rozpoznávat
          trénovací množinu
        - problém bývá spíše se zobecňováním - tj. naučit síť správně
          rozpoznat něco, co ještě neviděla
          (problém přeučení - učíme se na zkoušku tak dlouho, až nakonec vůbec
           nic neumíme)

        a) korelační učení
        b) soutěživé učení - neurony soutěží mezi sebou, vítězný neuron
                             potom fireuje
        c) adaptační učení - nejpoužívanější způsob

    III. podle aplikace
        a) klasifikace - zařazení vstupního vektoru do jedné z (pevně daných)
                         tříd
        b) shlukování (K-means, víme)
        c) vektorová kvantifikace - přiřazení vektoru nejbližšímu vzorovému
                                    vektoru)
        d) asociace - např. rozpoznání podobného obrázku
        e) aproximace funkce - jasné
        f) predikce
        g) identifikace systémů - black-boxy
        h) optimalizace

    IV. podle způsobu výpočtu
        a) synchronní - např. výpočet po jednotlivých vrstvách
        b) asynchronní

- hodnocení neuronových sítí
    - jak dobře se učí
    - jak dobře síť zobecňuje
    - požadavky na výpočetní zdroje

- hodnocení KVALITY odezvy NS
    - euklidovská/Hammingova vzdálenost (Hammingova se používá hlavně pro
      binární kódování)
    - odlišně se stanovuje kvalita u klasifikačních/shlukovacích sítí
        - % chybně klasifikovaných vzorů
        - počet shluků, vnitřní vzdálenost, vnější vzdálenost (mezi shluky)

- modely umělého neuronu
    Perceptron
    - nejjednodušší model neuronu
    - kreslí se zvlášť bázová a aktivační funkce
    - $x_0 = 1$ (reprezentuje práh)
    - aktivační funkce: (upravená) funkce signum (při 0 zůstává původní stav)
    - ve dvojrozměrném prostoru (dva vstupy) přímka, ve 3D rovina, ....
    - učení
        - máme nějakou trénovací množinu, hledáme vektor vah (w)
        - aby se NS naučila trénovací množinu, tato množina musí být
          bezesporná (na jeden vstupní vektor nemohou být dvě různé odezvy)
        - vzory z trénovací množiny se vybírají náhodně (problém
          s opakovatelností procesu učení)
        - naučit se vzorec učení perceptronu (bude se pořád opakovat) -
          není skalární součin, ale násobení vektoru skalárem
        - řešení existuje pouze pro lineárně separovatelné vektory

        - sl. 33 dole: (a+b)^2 = a^2 +2ab +b^2
        - neznáme \alpha ani \beta, ale jsou to čísla a tedy $k$ musí být
          konečné --> po konečném počtu kroků síť zkonverguje (pokud jsou
          obrazy lineárně separovatelné)
        - sl. 36: pokud rozdělíme oblast čtyřmi přímkami "jakkoliv", dostaneme
          11 oblastí (podívat se na obecný vzorec)

        - dávkové pravidlo - suma (vezmu všechno naráz)
        - Butzovo pravidlo - nevede k výraznému zlepšení
        - koeficient učení (p) se volí menší než 1 (víme)
        - sl. 40: bude na půlsemestrálce (počítat na papír pěkně krok, po
          kroku...)
        - vztah váha -> dělící přímka:
            w=(1 -1 -1)  -->  0 = 1*x_2 -1*x_1 -1*1  --> x_2 = x_1 + 1

        - pocket algoritmus ("v kapsi" si pamatuje váhový vektor, který dobře
          klasifikoval největší počet vzorků - což nutně nemusí být ten
          poslední pro neseparabilní vzorky)

    ADALINE (ADAptive LInear NEuron)
    - k učení se používá hodnota $u$, ne $y$ - viz. obrázek (obejití aktivační
      funkce)
    - učení
        \alpha-LMS (Least Mean Square)
            - \alpha se volí v rozsahu <0,2>, ale neví proč to není do 1

        \mi-LMS (Least Mean Square)

        inkrementální \mi-LMS

    MADALINE (Many ADALINE)
    - algoritmus učení je stanoven Ad-Hoc (bez důkazu)
    - nevede vždy ke konvergenci
    - v logické vrstvě jsou libovolně nakombinované funkce OR/AND
    - zavádí se abstrakce (-1 --> log. 0, 1 --> log. 1)
    - učení je postavené na vodě, u II., III. ještě více
    - tohle snad zkoušet nebude...

    BP = Back Propagation
    - nejdůležitější
    - máme prostor, ve kterém nejsou vzorky lineárně separovatelné
    - vstupní vrstva sítě transformuje vzorky ze vstupního prostoru do jiného
      prostoru, kde lineárně separovatelné jsou
    - u_k --> y_k ... převod na binární (+/-1) hodnoty

    - počítá se parciální derivace podle váhy
    - gradient ukazuje, jak se mění chyba na základě změny váhy

    - počáteční hodnoty vah - náhodné hodnoty z intervalu <-0.5, 0.5> nebo ...
    - hodnoty vstupního vektoru je dobré normalizovat, aby jedna z nich nebyla
      dominantní
    - koeficient učení obvykle 0.7
    - někdy se používá momentum (\alpha - hybnost) - změna váhy se neřídí
      pouze gradientem, ale také podle předchozí změny váhy
    - četnost úpravy vah:
        a) po každém vzorku
        b) dávkově - po průchodu celou trénovací množinou

    - back propagation má problémy s lokálními extrémy
    - na začátku množinu vzorků (náhodně) rozdělíme na trénovací a testovací
      množinu --> znát graf průběhu trénovací/testovací chyby (přeučení)
    - existuje spousta vylepšení:
        QuickPropagation


Neuronové sítě s proměnnou topologií
====================================
- dva přístupy k tvorbě optimální sítě:
    A) zmenšování velké naučené sítě
    B) zvětšování malé nenaučitelné sítě

Pruning algorithm
-----------------
- vyhození neuronu s nízkou váhou
- lepší přístup: jestliže od nějakého neuronu mají neurony ve vyšší vrstvě
  nízké váhy, tak jej mohu vyhodit (!!)

Upstart algorithm
-----------------
- algoritmus se volá rekurzivně
- pokud dostane jednu z množin prázdnou, tak "není co řešit"
- testováno na problému "izolovaných rohů"

Marchand's algorithm
--------------------
- na zkoušce snad nebude

Tiling algorithm
----------------
- postupné tvoření vícevrstvé dopředné sítě
- každá další vrstva má méně neuronů než vrstva předcházející
- alg. končí, když je v poslední vrstvě jediný neuron
- postupné rozdělování..., není triviální


Sítě RBF
========
- název podle bázové funkce (Radiální Bázová Funkce)
- první vrstva používá neurony, jejichž bázové funkce jsou radiální
- jinak síť vypadá stejně

- skrytá vrstva má radiální bázovou funkci a Gaussovu aktivační funkci
- výstupní vrstva jsou neurony s lineární bázovou funkcí a lineární aktivační
  funkcí

- učení je zdlouhavé --> odhady parametrů pomocí shlukové analýzy
- určení středů: K-means clustering
    - určím K, středy shluků zvolím náhodně
    - následně dopočítám skutečné středy shluků jako těžiště
    - "středy" se postupně přesouvají do středů shluků
    - pokud jsou shluky zřejmé, algoritmus je najde
    - lze snadno kontrolovat a vybrat nejlepší řešení (vzdálenost bodů
      od těžiště co nejmenší, vzdálenost těžišť od sebe co největší)

Sítě RCE
========
- RCE = Restricted Coulomb Energy
- skrytá vrstva: neurony s RBF, skokovou aktivační funkcí
- výstupní vrstva: neurony s funkcí logického OR
- tvoří se hyperkoule (které se buď překrývají nebo ne - dvě varianty)
- rychle se učí

Topologicky organizované neuronové sítě
=======================================

Hammingova síť
--------------
- prakticky se nepoužívá

Maxnet
------
- plně propojená síť
- výstupní hodnota se počítá jako max(0, vnitřní hodnota)
- po několik krocích zvítězí jediný neuron s nenulovou hodnotou

Jednoduchá soutěživá síť
------------------------
- založená na Maxnet, ale má vstupy
- Kohonenova vrstva - Maxnet doplněný o vstupy s vahami
- vítězný neuron představuje shluk, do kterého síť zařadila vstupní vektor

https://www.fit.vutbr.cz/study/courses/SFC/private/06sfc_4.pdf - sl. 24
- bude na půlsemce - mrknout na alg., zkontrolovat výsledky podle programu:
    https://www.fit.vutbr.cz/study/courses/SFC/private/scl.exe

Kohonenovy mapy
---------------
- neupravuje váhu pouze vítězného neuronu, ale také jeho topologického okolí
- sousedství může být rozmanité (řetěz, čtvercová mřížka, ...)
- pokud je vzorek zařazen do nějaké třídy, může být během učení přeřazen do
  jiné třídy

CPN = Counter Propagation Network
---------------------------------
- vzniklo v době, kdy stroje neměly takový výkon
- dvě vrstvy
    vstupní - klasický Maxnet (Kohonenova vrstva)
    výstupní vrstva - vstupní neurony stejné třídy by měly vybudit jeden
                      výstup
- alg. je SCL (neupravuje okolí)
- v praxi nepoužitelné
    - vstupní vrstva by musela mít příliš mnoho neuronů
    - vždy vítězí pouze jeden vstupní neuron (ostatní jsou neaktivní)

Full counterpropagation
-----------------------
- funguje obousměrně (učení)
    - hledám na vstupy odpovídající výstupy
    - hledám podle výstupu odpovídající vstupy

LVQ = Learning Vector Quantizers
--------------------------------
- stejné jako SCL s tím rozdílem, že víme, do které třídy vzorky zařadit
- pokud je třída správně, posílím váhy neuronu, jinak oslabím
- nepoužívá se okolí

ART = Adaptive Resonance Theory
-------------------------------
- obousměrné váhy
- speciální vstupní vrstva (nejsou neurony)
    - v první fázi propustí vstup směrem nahoru
    - v druhé fází provede porovnání mezi vstupem a tím, co přišlo z hora
      (na vstupech se generuje binární vektor)

- postupné vyřazování neuronů (adaptivní rezonance)
- důležitý je "parametr ostražitosti"
    --> kontrola ostražitosti
- v průběhu učení se váhy ubírají (proces zapomínání)
- pokud se vzorek zcela zapomene, přidá se pro něj nový neuron


Neuronové sítě jako asociativní paměti
======================================
- paměť adresovaná obsahem
- např. na obrázek (fotografii) odpoví jménem

- podívat se na definici auto-/hetero-asociativní sítě
- pokud rozpoznávaný prvek nebyl součástí trénovací množiny, přiřadí se tomu
  nejbližšímu vektoru, který tam byl

- Back Propagation lze také použít jako asociativní paměť

Hopfieldova neuronová síť
-------------------------
- symetrická plně propojená neuronová síť
- počítá se vnitřní potenciál neuronu (jako suma vážených vstupů)
- binární výstupy (ale existuje i spojitá varianta)
- záleží na konkrétním zvoleném alg. jestli konverguje nebo ne

- nevýhodou je malá kapacita (se 100 neurony uložíme 6 nebo 7 vzorů)
- falešné atraktory (způsobené lokálními minimy)

BAM = Bidirectional Associative Memory
--------------------------------------
- podobné jako Hopfield
- důkaz není potřeba, podobný předchozímu

SDM = Sparse Distributed Memory
-------------------------------
- podívat se na tabulku
- na rozdíl od klasické paměti RAM, nejsou adresy souvislé
- paměťové buňky nejsou bity, ale obousměrné čítače
- počítají se Hammingovi vzdálenosti

Optimalizační problémy
======================
Modifikované Hopfieldovy sítě
-----------------------------
- spojitá varianta
- dokáže velice jednoduše vyřešit problém osmi dam (mřížka + diagonály)
- také problém obchodního cestujícího (spojení matice do válce)

Testování logických obvodů
--------------------------
- diskrétní varianta
- na vstupy i výstupy se dívám jako na signály
- potom jsem schopný vzít třeba výstup a vstup ANDu a dopočítat druhý vstup
  (musí pracovat s nedeterminismem)

Simulované žíhání
-----------------
- podívat se do EVO

Boltzmanův stroj
----------------
- podívat se na schéma
- vstupní(viditelné)/skryté neurony
- problém s učením skrytých neuronů
- dvě fáze učení:
    1. vstupní(viditelné) neurony jsou fixovány, mění se pouze výstupní
       hodnoty skrytých neuronů

    2. mění se výstupní hodnoty všech neuronů


Fuzzy množiny
=============
- podívat se do SIN, SNT

Pravděpodobnostní usuzování
===========================
- tabulka s osmi prvky na straně 7 lze převést na tabulku s pěti prvky
    - složitost se sníží z 2^n na n (??)
    - jeden z nejvýznamnějších objevů umělé inteligence

- Bayessovské sítě
    CPT = Condition Propability Table

Hrubé (rough) množiny
=====================
    aproximace ... odhad

Knowledge representation systems
--------------------------------
- systémy pro dolování dat

Chaos
=====
- chaotické chování na základě deterministických pravidel
- vysoká citlivost na počáteční podmínky
- dynamický systém se vyvíjí v čase
- fázový prostor - např. nakreslím sinus ve fázovém prostoru (ne závislost
  hodnoty na čase, ale jeho derivaci na jeho hodnotě - potom jsem schopen
  z grafu rozhodnout, jestli je systém tlumený, stabilní, ...)