Articles

Az XOR-probléma a neurális hálózatokban.

Bevezetés
Ez az első bejegyzés a mesterséges neurális hálózatok (ANN) megvalósításait vizsgáló sorozatban. A cikk célja, hogy segítsen az olvasónak megérteni az alapfogalmakat, mielőtt rátérne a következő algoritmikus megvalósításokra.

Nem feltételezünk előzetes ismereteket, bár a rövidség kedvéért a cikk nem minden terminológiát magyaráz meg. Ehelyett hiperhivatkozásokat adunk a Wikipédiára és más forrásokra, ahol további olvasásra lehet szükség.

Ez egy nagy téma. Az ANN-ek sokféleképpen alkalmazhatók, és használhatók felügyelt, felügyelet nélküli, félig felügyelt és megerősítéses tanulásra. Ez még azelőtt, hogy belemennénk a problémaspecifikus architektúrákba ezeken a kategóriákon belül. De valahol el kell kezdenünk, ezért a terjedelem leszűkítése érdekében az ANN-ek egy egyszerű problémára való alkalmazásával kezdjük.

Az XOr probléma
Az XOr, vagy “kizárólagos vagy” probléma az ANN-kutatás klasszikus problémája. Ez az a probléma, amikor egy neurális hálózat segítségével két bináris bemenet esetén meg kell jósolni az XOr logikai kapuk kimeneteit. Egy XOr függvénynek igaz értéket kell visszaadnia, ha a két bemenet nem egyenlő, és hamis értéket, ha egyenlőek. Az összes lehetséges bemenetet és a megjósolt kimeneteket az 1. ábra mutatja.

Az XOr egy osztályozási probléma, amelynél a várható kimenetek előre ismertek. Ezért célszerű felügyelt tanulási megközelítést alkalmazni.

A felszínen az XOr nagyon egyszerű problémának tűnik, azonban Minksy és Papert (1969) kimutatta, hogy ez nagy problémát jelentett az 1960-as évek neurális hálózati architektúrái, az úgynevezett perceptronok számára.

Perceptronok
Mint minden ANN, a perceptron is egységek hálózatából áll, amelyek analógok a biológiai neuronokkal. Egy egység más egységektől kaphat bemenetet. Ennek során a kapott értékek összegét veszi, és eldönti, hogy továbbítja-e a jelet a többi egységnek, amelyekkel kapcsolatban áll. Ezt nevezzük aktiválásnak. Az aktiválási függvény valamilyen eszközzel a bemeneti értékek összegét 1-re vagy 0-ra (vagy az 1 vagy 0-hoz nagyon közeli értékre) csökkenti, hogy az aktiválást vagy annak hiányát reprezentálja. Az egység egy másik formája, az úgynevezett előfeszítő egység mindig aktiválódik, jellemzően egy keményen kódolt 1-et küld minden olyan egységnek, amelyhez csatlakozik.

A perceptronok egyetlen réteg bemeneti egységet – beleértve egy előfeszítő egységet – és egyetlen kimeneti egységet tartalmaznak (lásd a 2. ábrát). Itt a torzító egységet szaggatott körrel, míg a többi egységet kék körrel ábrázoljuk. Az XOr két bináris bemeneti értékét két nem előfeszített bemeneti egység képviseli. Bármennyi bemeneti egység szerepelhet.

A perceptron egyfajta feed-forward hálózat, ami azt jelenti, hogy a kimenet létrehozásának folyamata – az úgynevezett forward propagation – egy irányban folyik a bemeneti rétegből a kimeneti rétegbe. A bemeneti réteg egységei között nincsenek kapcsolatok. Ehelyett a bemeneti réteg minden egysége közvetlenül a kimeneti egységhez kapcsolódik.

Az előrehaladási folyamat egyszerűsített magyarázata az, hogy az X1 és X2 bemeneti értékeket, valamint az 1 előfeszítési értéket megszorozzuk a megfelelő W0..W2 súlyokkal, és a kimeneti egységbe elemezzük. A kimeneti egység ezeknek az értékeknek az összegét veszi, és egy aktiválási függvényt – jellemzően a Heavside-féle lépésfüggvényt – alkalmaz, hogy a kapott értéket 0 vagy 1 értékké alakítsa, és így a bemeneti értékeket 0 vagy 1 értéknek minősítse.

A súlyváltozók beállítása az, ami a hálózat szerzőjének irányítást ad a bemeneti értékek kimeneti értékké alakításának folyamata felett. A súlyok határozzák meg, hogy hol húzódik az osztályozási vonal, az a vonal, amely az adatpontokat osztályozási csoportokba sorolja. Ha az osztályozási vonal egyik oldalán lévő összes adatpont 0 osztályba kerül, akkor az összes többi 1 osztályba kerül.

Ez az architektúra korlátja, hogy csak egyetlen vonallal képes az adatpontok szétválasztására. Ez azért nem szerencsés, mert az XOr bemenetek nem szeparálhatók lineárisan. Ez különösen akkor látható, ha az XOr bemeneti értékeket grafikonra rajzolja. Ahogy a 3. ábrán látható, az 1-es és a 0-s előrejelzéseket nem lehet egyetlen osztályozási vonallal elválasztani.

Multilayer Perceptrons
A probléma megoldása az, hogy az egyrétegű architektúrán túl egy további, a külvilághoz közvetlen hozzáféréssel nem rendelkező, rejtett rétegnek nevezett egységréteggel bővítjük. Ez a fajta architektúra – a 4. ábrán látható – egy másik, többrétegű perceptron (MLP) néven ismert feed-forward hálózat.

Érdemes megjegyezni, hogy egy MLP tetszőleges számú egységgel rendelkezhet a bemeneti, rejtett és kimeneti rétegekben. A rejtett rétegek száma is tetszőleges lehet. Az itt használt architektúrát kifejezetten az XOr problémára terveztük.

A klasszikus perceptronhoz hasonlóan az előrehaladás úgy kezdődik, hogy a bemeneti réteg bemeneti értékeit és torzító egységét megszorozzuk a megfelelő súlyokkal, azonban ebben az esetben a bemenet (beleértve a bemeneti réteg torzító egységét) és a rejtett egység (kivéve a rejtett réteg torzító egységét) minden egyes kombinációjára van egy súly. A bemeneti réteg értékeinek és a hozzájuk tartozó súlyoknak a szorzatát a rejtett réteg nem előfeszített egységeinek bemeneteként elemezzük. Minden nem előfeszített rejtett egység aktiválási függvényt használ – az XOr probléma esetében általában a klasszikus szigmoid függvényt -, hogy a bemeneti értékek összegét egy 0 és 1 közötti értékre szorítsa le (általában egy 0-hoz vagy 1-hez nagyon közeli értékre). Az egyes rejtett rétegegységek kimeneteit, beleértve az előfeszítő egységet is, ezután megszorozzuk egy másik, megfelelő súlyokkal, és egy kimeneti egységbe elemezzük. A kimeneti egység a bemeneti értékeinek összegét szintén egy aktiváló függvényen keresztül elemzi – itt is a szigmoid függvény a megfelelő -, hogy egy 0 és 1 közé eső kimeneti értéket adjon vissza. Ez a megjósolt kimenet.

Ez az architektúra, bár összetettebb, mint a klasszikus perceptronhálózaté, képes nemlineáris szétválasztást elérni. Így a súlyértékek megfelelő beállításával képes biztosítani az XOr bemenetek pontos osztályozásához szükséges elválasztást.

Backpropagation
Az elefánt a szobában természetesen az, hogy hogyan találjuk ki azokat a súlyértékeket, amelyek biztosítják, hogy a hálózat a várt kimenetet produkálja. A gyakorlatban egy MLP-hálózat számára elfogadható súlykészletet találni kézzel hihetetlenül fáradságos feladat lenne. Valójában ez a feladat NP-teljes (Blum és Rivest, 1992). Szerencsére azonban lehetséges a megfelelő súlyértékek automatikus megtanulása a backpropagation nevű folyamat segítségével. Ezt először Rumelhart és társai (1985) mutatták be, hogy jól működik az XOr problémára.

A backpropagation algoritmus azzal kezdi, hogy összehasonlítja az előrehaladási folyamat által kimenő tényleges értéket a várható értékkel, majd visszafelé halad a hálózaton, kissé módosítva az egyes súlyokat olyan irányba, hogy a hiba nagysága egy kis mértékben csökkenjen. Mind az előre-, mind a hátrafelé terjedést több ezerszer futtatjuk újra az egyes bemeneti kombinációkon, amíg a hálózat az előre terjedés segítségével pontosan meg tudja jósolni a lehetséges bemenetek várható kimenetét.

Az xOr probléma esetében a lehetséges adatpéldák 100%-a áll rendelkezésre a képzési folyamathoz. Ezért elvárhatjuk, hogy a betanított hálózat 100%-os pontosságú előrejelzéseket adjon, és nem kell olyan kérdésekkel foglalkoznunk, mint a torzítás és a variancia a kapott modellben.

Következtetés
Ebben a bejegyzésben a klasszikus ANN XOr problémát vizsgáltuk. Részletesen ismertettük magát a problémát, valamint azt a tényt, hogy az XOr bemenetei nem választhatók szét lineárisan a helyes osztályozási kategóriáikra. Egy nem lineáris megoldást – amely egy MLP-architektúrát foglal magában – vizsgáltunk magas szinten, valamint a hálózat kimeneti értékének létrehozására használt forward propagation algoritmust és a hálózat betanítására használt backpropagation algoritmust.

A sorozat következő bejegyzésében az itt leírt MLP-architektúra Java implementációját mutatjuk be, beleértve a hálózat XOr logikai kapuként való működésének betanításához szükséges összes komponenst.

Blum, A. Rivest, R. L. (1992). Egy 3 csomópontos neurális hálózat képzése NP-teljes. Neural Networks, 5(1), 117-127.