Articles

Problém XOR v neuronových sítích.

Úvod
Toto je první ze série příspěvků věnovaných implementacím umělých neuronových sítí (ANN). Cílem článku je pomoci čtenáři získat představu o základních pojmech předtím, než přejde k algoritmickým implementacím, které budou následovat.

Nepředpokládají se žádné předchozí znalosti, i když v zájmu stručnosti není v článku vysvětlena veškerá terminologie. Místo toho jsou uvedeny hypertextové odkazy na Wikipedii a další zdroje, kde může být vyžadováno další čtení.

Jedná se o rozsáhlé téma. ANN mají širokou škálu aplikací a lze je použít pro učení pod dohledem, bez dohledu, částečně pod dohledem a pro učení s posilováním. A to ještě předtím, než se dostanete k architekturám specifickým pro daný problém v rámci těchto kategorií. Někde ale začít musíme, takže abychom zúžili záběr, začneme aplikací ANN na jednoduchý problém.

Problém XOr
Problém XOr neboli „výlučné nebo“ je klasickým problémem ve výzkumu ANN. Jedná se o problém použití neuronové sítě k předpovědi výstupů logických hradel XOr vzhledem ke dvěma binárním vstupům. Funkce XOr by měla vrátit pravdivou hodnotu, pokud se oba vstupy nerovnají, a nepravdivou hodnotu, pokud se rovnají. Všechny možné vstupy a předpovězené výstupy jsou zobrazeny na obrázku 1.

XOr je klasifikační problém a problém, u kterého jsou očekávané výstupy předem známy. Je proto vhodné použít přístup učení pod dohledem.

Na první pohled se zdá, že XOr je velmi jednoduchý problém, nicméně Minksy a Papert (1969) ukázali, že to byl velký problém pro architektury neuronových sítí z 60. let, známé jako perceptrony.

Perceptrony
Stejně jako všechny ANN se perceptron skládá ze sítě jednotek, které jsou analogické biologickým neuronům. Jednotka může přijímat vstup od jiných jednotek. Při tom vezme součet všech přijatých hodnot a rozhodne, zda bude signál předávat dál ostatním jednotkám, ke kterým je připojena. Tomuto postupu se říká aktivace. Aktivační funkce používá nějaké prostředky k redukci součtu vstupních hodnot na 1 nebo 0 (nebo na hodnotu velmi blízkou 1 nebo 0), aby vyjádřila aktivaci nebo její nedostatek. Jiná forma jednotky, známá jako zkreslovací jednotka, se vždy aktivuje a obvykle posílá všem jednotkám, ke kterým je připojena, pevně zakódovanou hodnotu 1.

Perceptrony obsahují jednu vrstvu vstupních jednotek – včetně jedné zkreslovací jednotky – a jednu výstupní jednotku (viz obrázek 2). Zde je zkreslující jednotka znázorněna čárkovaným kroužkem, zatímco ostatní jednotky jsou znázorněny modrými kroužky. Existují dvě nepředpojaté vstupní jednotky, které představují dvě binární vstupní hodnoty pro XOr. Může být zahrnut libovolný počet vstupních jednotek.

Perceptron je typ sítě s dopředným šířením, což znamená, že proces generování výstupu – známý jako dopředné šíření – probíhá jedním směrem ze vstupní vrstvy do výstupní vrstvy. Mezi jednotkami ve vstupní vrstvě nejsou žádná spojení. Místo toho jsou všechny jednotky ve vstupní vrstvě připojeny přímo k výstupní jednotce.

Zjednodušené vysvětlení procesu dopředného šíření je takové, že vstupní hodnoty X1 a X2 jsou spolu s hodnotou zkreslení 1 vynásobeny příslušnými váhami W0..W2 a rozebrány do výstupní jednotky. Výstupní jednotka vezme součet těchto hodnot a použije aktivační funkci – obvykle Heavsideovu krokovou funkci – k převodu výsledné hodnoty na 0 nebo 1, čímž klasifikuje vstupní hodnoty jako 0 nebo 1.

Je to nastavení váhových veličin, které dává autorovi sítě kontrolu nad procesem převodu vstupních hodnot na výstupní hodnotu. Právě váhy určují, kde je nakreslena klasifikační čára, čára, která rozděluje datové body do klasifikačních skupin. Pokud je všem datovým bodům na jedné straně klasifikační čáry přiřazena třída 0, všechny ostatní jsou klasifikovány jako 1.

Omezení této architektury spočívá v tom, že je schopna oddělit datové body pouze jednou čarou. To je nešťastné, protože vstupy XOr nejsou lineárně oddělitelné. To je patrné zejména při vykreslení vstupních hodnot XOr do grafu. Jak ukazuje obrázek 3, není možné oddělit předpovědi 1 a 0 jedinou klasifikační přímkou.

Vícevrstvé perceptrony
Řešením tohoto problému je rozšíření nad rámec jednovrstvé architektury přidáním další vrstvy jednotek bez přímého přístupu k vnějšímu světu, známé jako skrytá vrstva. Tento druh architektury – znázorněný na obrázku 4 – je další feed-forward síť známá jako vícevrstvý perceptron (MLP).

Je třeba poznamenat, že MLP může mít libovolný počet jednotek ve vstupní, skryté a výstupní vrstvě. Může mít také libovolný počet skrytých vrstev. Zde použitá architektura je navržena speciálně pro problém XOr.

Podobně jako u klasického perceptronu začíná dopředné šíření vynásobením vstupních hodnot a jednotky zkreslení ze vstupní vrstvy jejich příslušnými váhami, avšak v tomto případě existuje váha pro každou kombinaci vstupu (včetně jednotky zkreslení vstupní vrstvy) a skryté jednotky (bez jednotky zkreslení skryté vrstvy). Součin hodnot vstupní vrstvy a jejich příslušných vah se analyzuje jako vstup pro jednotky bez zkreslení ve skryté vrstvě. Každá nepředpojatá skrytá jednotka vyvolá aktivační funkci – v případě problému XOr obvykle klasickou sigmoidní funkci – aby součet svých vstupních hodnot zmačkala na hodnotu mezi 0 a 1 (obvykle na hodnotu velmi blízkou 0 nebo 1). Výstupy každé jednotky skryté vrstvy, včetně jednotky zkreslení, jsou pak vynásobeny další sadou příslušných vah a rozebrány na výstupní jednotku. Výstupní jednotka také analyzuje součet svých vstupních hodnot prostřednictvím aktivační funkce – opět je zde vhodná sigmoidní funkce – a vrací výstupní hodnotu spadající mezi 0 a 1. To je předpovídaný výstup.

Tato architektura je sice složitější než architektura klasické perceptronové sítě, ale je schopna dosáhnout nelineárního oddělení. Se správnou sadou váhových hodnot tak může zajistit potřebnou separaci pro přesnou klasifikaci vstupů XOr.

Zpětné šíření
Slonem v porcelánu je samozřejmě otázka, jak lze přijít na sadu váhových hodnot, která zajistí, že síť bude produkovat očekávaný výstup. V praxi by pokus o ruční nalezení přijatelné sady vah pro síť MLP byl neuvěřitelně pracný úkol. Ve skutečnosti je NP-úplný (Blum a Rivest, 1992). Naštěstí je však možné naučit se vhodnou sadu hodnot vah automaticky pomocí procesu známého jako zpětné šíření. Poprvé bylo prokázáno, že tento postup dobře funguje pro problém XOr, a to Rumelhartem a dalšími (1985).

Algoritmus zpětného šíření začíná porovnáním skutečné hodnoty výstupu procesu dopředného šíření s očekávanou hodnotou a poté postupuje zpět sítí a mírně upravuje každou z vah ve směru, který snižuje velikost chyby o malý stupeň. Jak dopředné, tak zpětné šíření se tisíckrát opakuje na každé kombinaci vstupů, dokud síť nedokáže přesně předpovědět očekávaný výstup možných vstupů pomocí dopředného šíření.

Pro problém xOr je k dispozici 100 % možných datových příkladů, které lze použít v procesu učení. Můžeme tedy očekávat, že natrénovaná síť bude ve svých předpovědích 100% přesná a není třeba se zabývat problémy, jako je zkreslení a rozptyl ve výsledném modelu.

Závěr
V tomto příspěvku byl prozkoumán klasický problém ANN XOr. Samotný problém byl podrobně popsán spolu se skutečností, že vstupy pro XOr nejsou lineárně rozdělitelné do svých správných klasifikačních kategorií. Na vysoké úrovni bylo prozkoumáno nelineární řešení – zahrnující architekturu MLP – spolu s algoritmem dopředného šíření, který se používá ke generování výstupní hodnoty ze sítě, a algoritmem zpětného šíření, který se používá k trénování sítě.

Příští příspěvek v této sérii bude obsahovat implementaci zde popsané architektury MLP v jazyce Java, včetně všech komponent potřebných k trénování sítě, aby fungovala jako logické hradlo XOr.

Blum, A. Rivest, R. L. (1992). Trénování tříuzlové neuronové sítě je NP-úplné. Neural Networks, 5(1), 117-127.

.