Egy komplex feladat dekompozíció útján történő megoldására számos lehetőségünk van. Az egyik legkézenfekvőbb eljárás, hogy mielőtt a feladatot valamilyen eszközzel megpróbálnánk megoldani, előbb funkciók szerint részekre bontjuk, és csak a részfeladatok külön-külön történő megoldásával foglalkozunk. Az előzetes részekre bontás a feladat részletes ismerete alapján lehetséges. Ilyenkor a dekompozíció mindig feladatfüggő, ennélfogva csak akkor alkalmazható, ha a problémáról elegendő előzetes ismeret áll a rendelkezésünkre. Jó példa erre az előző fejezetben bemutatott pótkocsis teherautó tolatási feladat egy lehetséges megoldása [Jen93]. E szerint célszerű különválasztani a pótkocsi irányának meghatározását a pótkocsi pozíciójának meghatározásától. A dekompozíció előnye, hogy a részfeladatok az eredeti megoldásnál (ld. 8.1 példa) jóval egyszerűbben megoldhatók − az iránymeghatározáshoz például egyetlen perceptron is elegendő −, továbbá az egyes részfeladatokat egymástól függetlenül, párhuzamosan is meg lehet valósítani.

A dekompozíció egy másik lehetősége, ha a feladat felbontását előre nem végezzük el, az a tanulás során automatikusan alakul ki. Erre a fejezet későbbi részében találunk majd példát.

A következőkben egy olyan eljárást mutatunk be, mely a priori ismeret nélkül is hatékonyan dekomponálja a feladatot, mégpedig úgy, hogy a kapott részfeladatok kisebbek és jóval egyszerűbbek, mint az eredeti feladat. Ráadásul az egész eljárás nagyon egyszerű is. Az egyetlen korlátozás, hogy a dekomponálásnak ez a megoldása csak osztályozási problémáknál alkalmazható.

Osztályozási feladatoknál egy többosztályos feladat természetes dekompozíciója lehet, ha a feladatot kétosztályos feladatok együttesére bontjuk fel. Így pl. egy K-osztályos feladat felbontható K darab olyan kétosztályos feladatra, ahol a K osztály egyikét szeretnénk megkülönböztetni a maradék K−1 osztálytól. Itt tehát annyi kétosztályos részfeladatot tudunk definiálni, ahány osztály az eredeti feladatban megkülönböztethető. Az ilyen dekompozíció hátránya, hogy a származtatott kétosztályos feladatok az adatok (tanítóminták) számát tekintve nagyon kiegyensúlyozatlanok lehetnek. Ha ugyanis feltételezzük, hogy az eredeti feladat K osztályának mindegyikébe közel azonos számú tanítópont tartozik, akkor a származtatott kétosztályos feladatoknál a két osztály egyikébe (K−1)-szer annyi minta esik, mint a másikba. A kiegyensúlyozatlanság a tanítást nehezítheti, az egész tanítási folyamatot jelentősen lelassíthatja.

A kiegyensúlyozatlanság elkerülhető, ráadásul a dekompozíció eredményeképp kapott osztályozási feladatok még egyszerűbbekké is válnak, ha a K-osztályos feladatot olyan kétosztályos részfeladatokra bontjuk, ahol egy részfeladat az eredeti K osztályból kizárólag két osztály szétválasztására irányul, miközben a maradék K−2 osztállyal nem is foglalkozunk [Lu99]. Ha C₁, C₂,…,C_K-val jelöljük a megkülönböztetendő K osztályt, akkor az egyszerűbb kétosztályos feladatokra bontás azt jelenti, hogy egy kétosztályos feladat során a C_i és a C_j osztályt szeretnénk megkülönböztetni egymástól, ahol i,j=1,…,K, i≠j, és természetesen minden i,j párt csak egyszer veszünk számba. Egy adott kétosztályos részfeladat megoldásánál a maradék K−2 osztály tanítópontjait figyelmen kívül hagyjuk. Ha továbbra is feltételezzük, hogy az egyes osztályokba közel azonos számú tanítópont tartozik, akkor a dekompozíció eredményeképp kapott egyszerű kétosztályos feladatoknál mindkét osztályt hasonló számú tanítópont reprezentál, a tanítókészlet a dekompozíció után is kiegyensúlyozott és az eredeti feladatban szereplő osztályok számától (K-tól) független marad.

Az eljárás részletesebb bemutatásához induljunk ki abból, hogy rendelkezésünkre áll egy

$Z={\left\{z_l^{}\right\}}_{l=1}^L={\left\{\left(x_l,d_l\right)\right\}}_{l=1}^L$ (9.1)

tanítókészlet^[6], melyet a K osztálynak megfelelően K diszjunkt részhalmazra bontunk.

$Z_i={\left\{z_l^{\left(i\right)}\right\}}_{l=1}^{L_i}={\left\{x_l^{\left(i\right)},d_l^{\left(i\right)}\right\}}_{l=1}^{L_i}i=\mathrm{1,}\dots ,K$ (9.2)

Az eddigi jelöléseknek megfelelően x_l egy bemeneti vektor, d_l pedig a hozzá tartozó kívánt válasz, a felső index pedig az osztálybesorolást jelző címke.

A javasolt dekompozíció szerint a feladat K(K−1) egyszerűbb kétosztályos részfeladatra bontható. Ebben még van redundancia, hiszen C_i megkülönböztetése C_j-től megoldja a két osztály fordított irányú megkülönböztetését is. A felesleges ismétlések elkerülésével K(K−1)/2 egyszerűbb kétosztályos feladatunk lesz. Kétosztályos feladatnál a kívánt válasz két lehetséges érték valamelyike lesz, tehát pl. $d_l\in \left\{\mathrm{0,1}\right\}$ . A gyakorlatban azonban általában megengedjük, hogy a kívánt válasz: $d_l\in \left\{\epsilon \mathrm{,1}-\epsilon \right\}$ legyen ahol ε egy kis pozitív szám. Ekkor a C_i, C_j osztálypárhoz tartozó mintakészlet az alábbi módon definiálható:

$Z_{ij}={\left\{\left(x_{{}_l}^{\text{(}i\text{)}}\mathrm{,1}-\epsilon \right)\right\}}_{l=1}^{L_i}\cup {\left\{\left(x_{{}_l}^{\text{(}j\text{)}},\epsilon \right)\right\}}_{l=1}^{L_j}i,j=1...K\text{é}si\ne j$ (9.3)

vagyis a C_i osztályba tartozó mintákra a kívánt válasz közel 1, a C_j-be tartozókra pedig közel 0 lesz. (Ez azért előnyös a {0,1} kívánt válasz értékhalmazzal szemben, mert a hálók és tanító eljárások egy részénél a 0, illetve az 1 környzetében nagyon lelassul a tanulási sebesség.) Vegyük észre, hogy Z_ij csak a C_i és a C_j osztályba tartozó mintapontokat tartalmazza, a maradék K−2 osztály pontjai az elemi kétosztályos feladat megoldásánál nem kerülnek felhasználásra.

Ezt a dekompozíciót K=3 mellett illusztrálja a 9.1 ábra. Az eredeti háromosztályos feladatot az ábra szerint három elemi kétosztályos feladatra bontottuk, miközben mindegyik esetben a harmadik osztály pontjait figyelmen kívül hagytuk.

A fenti dekompozíció nem minden esetben elegendő ahhoz, hogy az elemi kétosztályos feladatok kellően egyszerűek legyenek. Bizonyos problémáknál a megkülönböztetendő két osztály elválasztó felülete lehet nagyon bonyolult is. Ilyen esetekben az előzőekben kapott egyszerű kétosztályos feladatokat érdemes még tovább bontani. Hasonló esettel állunk szemben, ha már az eredeti probléma is kétosztályos, de nehéz volt. A tovább-bontás azt jelenti, hogy az egyes osztályokba tartozó tanító halmazokat további részhalmazokra bontjuk, és ezekre a részhalmazokra fogalmazunk meg kétosztályos feladatokat. Ez a felbontás – szemben az előzővel – már nem egyértelmű, hiszen bármely, adott osztályhoz tartozó pontkészlet tetszőleges módon dekomponálható.

Tételezzük fel, hogy az i-edik osztályhoz tartozó, (9.2) által definiált mintahalmazt tovább bontjuk M_i részhalmazra (1≤ M_i). A C_i osztályhoz tartozó j-edik ilyen részhalmaz az alábbi módon definiálható:

$Z_i^{\left(j\right)}={\left\{z_l^{\left(ij\right)}\right\}}_{l=1}^{L_i^{\left(j\right)}}={\left\{x_l^{\left(ij\right)},d_l^{\left(ij\right)}\right\}}_{l=1}^{L_i^{\left(j\right)}}j=\mathrm{1,}\dots ,M_i$ , (9.4)

ahol $L_i^{\left(j\right)}$ jelöli ennek a részhalmaznak az elemszámát. A részhalmazokra igaz kell legyen, hogy ${\cup }_{j=1}^{M_i}{Z}_i^{\left(j\right)}=Z_i$ és ${\cap }_{j=1}^{M_i}{Z}_i^{\left(j\right)}=\varnothing$ . Az így definiált tanító részhalmazok segítségével definiálhatjuk a kétosztályos osztályozási feladatokat. A C_i osztály u-adik részhalmaza és a C_j osztály v-edik részhalmaza által képezett kétosztályos feladat tanító készlete ennek megfelelően:

$\begin{array}{l}{Z}_{{}_{ij}}^{\left(u,v\right)}={\left\{\left(x_{{}_l}^{\text{(}iu\text{)}}\mathrm{,1}-\epsilon \right)\right\}}_{l=1}^{L_{{}_i}^{\left(u\right)}}\cup {\left\{\left(x_{{}_l}^{\text{(}jv\text{)}},\epsilon \right)\right\}}_{l=1}^{L_{{}_j}^{\left(v\right)}}\\ \\ i,j=\mathrm{1,}\cdots ,K\text{é}si\ne j,u=\mathrm{1,}\dots ,M_i,v=\mathrm{1,}\dots ,M_j\end{array}$ (9.5)

A dekompozíció akár addig is folytatható, amíg a részhalmazokban csak egy-egy mintapont marad. Ez azt jelenti, hogy az így definiált elemi osztályozási feladatok már biztosan megoldhatók lineáris szeparálásra alkalmas eszközökkel is. Természetesen ilyen mértékű felbontásra nincs minden esetben szükség.

Az elemi osztályozási feladatok megoldása után a következő lépés az eredmények integrálása. Az aggregálásnál két esetet kell megkülönböztetni.

Az első esetben legyenek olyan osztályozó moduljaink, ahol mindegyik feladata az, hogy adott C_i osztályba tartozó mintákat mindig más-más C_j, j=1,2,…,K, j≠i osztályba tartozó mintáktól különböztessen meg. Egy ilyen osztályozó modulra az érvényes, hogy a tanításhoz a (C_i, C_j) osztálypárhoz tartozó, a (9.3) összefüggés által definiált mintakészletet használjuk, vagyis az osztályozó tanításánál a kívánt válasz akkor lesz 1−ε, ha a tanítóminta a C_i osztályba tartozik és akkor lesz ε, ha a C_j-be.

Az ilyen típusú modulok eredményeinek integrálására a MIN művelet szolgál. A MIN műveletet megvalósító modul feladata, hogy a bemenetére kerülő értékek minimumát adja válaszul:

$y_{\text{MIN}}=\text{min(}{x}_1,x_2,\dots ,x_N\text{)}$ , (9.6)

ahol x₁, x₂, …, x_N jelölik a MIN modul bemeneteit, y_MIN pedig a modul kimenetét. A MIN modullal egyesített osztályozók eredő válasza csak akkor lesz 1−ε, ha a MIN modul minden bemenetére 1−ε kerül, vagyis, ha a MIN modult meghajtó minden osztályozó válasza 1−ε. Az integrált osztályozó tehát akkor fog egy mintát a C_i osztályba besorolni, ha a MIN modullal összefogott összes osztályozó a C_i osztályba sorolja az adott mintát.

A második esetben olyan moduljaink vannak, melyek feladata, hogy egy adott C_j osztály mintakészletének különböző részhalmazaiba tartozó mintákat különböztesse meg valamely más osztályba tartozó mintáktól. Ezekre az osztályozó modulokra az érvényes, hogy a tanításukhoz a C_j osztály v-edik és a C_i osztály u-adik részhalmazaihoz tartozó, a (9.5) összefüggés által definiált mintakészleteket használjuk, vagyis mindegyik osztályozó tanításánál a kívánt válasz akkor lesz ε, ha a tanítóminta a C_j osztály valamelyik v részhalmazába tartozik.

Az ilyen típusú modulok eredményének integrálására a MAX művelet szolgál. A MAX műveletet megvalósító modul feladata, hogy a bemenetére kerülő értékek maximumát adja válaszul:

$y_{\text{MAX}}=\text{max(}{x}_1,x_2,\dots ,x_N\text{)}$ , (9.7)

ahol a modul bemenetei most is az x₁, x₂, …, x_N értékek, kimenete pedig y_MAX. A MAX modullal egyesített osztályozók eredő válasza akkor lesz ε, ha a MAX modul egyik bemenetére sem kerül 1−ε. Ehhez a MAX modult meghajtó minden osztályozó válasza ε kell legyen, ami egyben azt is jelenti, hogy a MAX modult meghajtó minden osztályozó modulra a C_j osztály valamelyik v részhalmazába tartozó minta kerül.

Ha a MIN és a MAX műveletek elvégzésére alkalmas modulokat kiegészítjük egy INV modullal, akkor az előzőekben bemutatott bármilyen dekompozíció eredményeként kapott elemi kétosztályos osztályozó modulok integrálása felesleges redundancia nélkül lehetséges. Az INV modul egybemenetű, egykimenetű modul, melynek feladata a bemenetére kerülő érték invertálása, vagyis, ha az INV bemenete ε, a kimenete 1−ε kell legyen, és fordítva, 1−ε bemenetre ε választ kell adjon. Ez teszi lehetővé, hogy ha csak az osztályok szerint végezzük a dekompozíciót, egy K osztályos osztályozó helyett elegendő K(K−1)/2 kétosztályos osztályozót alkalmazni.

Ha az egyes osztályokat még tovább bontjuk és a (9.5) összefüggés szerinti mintahalmazokkal dolgozunk, akkor az INV modulok használata következtében az elemi kétosztályos osztályozók száma

${\displaystyle \sum _{i=1}^K{\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne i\end{array}}^K{M}_i{M}_j}}$ (9.8)

-ről

${\displaystyle \sum _{i=1}^K{\displaystyle \sum _{j=i+1}^K{M}_i{M}_j}}$ (9.9)

-re redukálható, ahol M_k a C_k (k=1,2,…,K) osztály részhalmazainak a száma.

Könnyen észrevehető, hogy az integráló modulok feladata hasonló a logikai ÉS, VAGY és NEM műveletekhez. Ha az egyes osztályozó modulok bináris kimenetet szolgáltatnak, akkor az integráló modulok kimeneteit valóban az osztályozók kimeneteinek logikai ÉS, VAGY, illetve NEM kapcsolatait felhasználva kaphatjuk meg.

Az is könnyen belátható, hogy az INV művelet mellett valójában elegendő kizárólag a MIN vagy kizárólag a MAX művelet, bár sok esetben egyszerűbb a modulok összekapcsolása, ha mindkettő rendelkezésre áll. A 9.2 ábrán a 9.1 ábra háromosztályos feladatának moduláris megoldása látható.

9.1 Példa

Az alábbiakban egy kétosztályos feladat kapcsán mutatjuk be a feladatdekompozíció egy speciális alkalmazási lehetőségét. A feladat a 9.3 ábrán látható. Az ábrából az is nyilvánvló, hogy a kétosztályos feladat lineárisan nem szeparálható. A feladatdekompozíciós eljárással azonban olyan elemi kétosztályos feladatokra bontható, ahol ezek az elemi feladatok már lineáris szeparálással (pl. egy egyszerű perceptronnal) megoldhatók. Az ábra azt is mutatja, hogy – ideális esetben – milyen tartományok megkülönböztetése szükséges a feladat megoldásához. Az ideális eset itt azt jelenti, hogy az elválasztó egyenesek a mintapontoktól egyforma és a lehető legnagyobb távolságban helyezkednek el. Ilyen megoldást garantáltan egy lineáris SVM-mel érhetünk el, egy egyszerű percetrontól azonban csak az várható, hogy a két különböző osztályba tartozó pontok között a pontokat hibátlanul elválasztó, de nem feltétlenül ideális elhelyezkedésű egyeneseket határozzon meg.

A következő, 9.4 ábrán azokat a lépéseket követhetjük, melyek a moduláris kialakítás eléréséhez vezetnek. Ugyancsak látható, hogy az elemi kétosztályos osztályozók integrálásához milyen modulokra van szükség.

A teljes moduláris osztályozó rendszer felépítését a 9.5 ábra mutatja. A moduláris felépítésnél azt tételeztük föl, hogy az egyes osztályozó modulok és a teljes hálózat is akkor vesz fel magas értéket, ha a fekete pontokkal jelölt bemenetek kerülnek a hálóra.

A feladatdekompozíció sikerrel alkalmazható összetett gyakorlati feladatok megoldására. Egy sikeres példaként említhetjük a kézzel írott számjegyek felismerésére kidolgozott és a 7.1.2 alfejezetben már bemutatott megoldást is, amely ezt a megközelítést alkalmazta, hiszen a 10 számjegy felismerését nem egy 10-osztályos osztályozó hálózattal, hanem 10×9/2=45 egyszerű kétosztályos osztályozóval oldotta meg. Az egyes elemi kétosztályos osztályozók mindig két osztályt (számjegyet) próbáltak egymástól megkülönböztetni, miközben a maradék nyolc további osztály mintapontjaival egyáltalán nem foglalkoztak. Ez a megoldás – mint láttuk – egy nagyon egyszerű háló architektúrát eredményezett, hiszen az elemi kétosztályos osztályozók egyszerű perceptronok voltak. A megfelelő osztályozó modulok eredményeinek integrálása ott ÉS kapukkal volt megoldva, ami megfelel a MIN műveleteknek.