9.1. Moduláris háló kialakítása feladat dekompozíció alapján

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 C1, C2,…,CK-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 Ci és a Cj 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= { z l } l=1 L = { ( x l , d l ) } l=1 L MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOwaiabg2da9maacmaabaGaaCOEamaaDaaaleaacaWGSbaabaaaaaGccaGL7bGaayzFaaWaa0baaSqaaiaadYgacqGH9aqpcaaIXaaabaGaamitaaaakiabg2da9maacmaabaWaaeWaaeaacaWH4bWaaSbaaSqaaiaadYgaaeqaaOGaaiilaiaadsgadaWgaaWcbaGaamiBaaqabaaakiaawIcacaGLPaaaaiaawUhacaGL9baadaqhaaWcbaGaamiBaiabg2da9iaaigdaaeaacaWGmbaaaaaa@4CBC@ (9.1)

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

Z i = { z l ( i ) } l=1 L i = { x l ( i ) , d l ( i ) } l=1 L i i=1,,K MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOwamaaBaaaleaacaWGPbaabeaakiabg2da9maacmaabaGaaCOEamaaDaaaleaacaWGSbaabaWaaeWaaeaacaWGPbaacaGLOaGaayzkaaaaaaGccaGL7bGaayzFaaWaa0baaSqaaiaadYgacqGH9aqpcaaIXaaabaGaamitamaaBaaameaacaWGPbaabeaaaaGccaaMi8Uaeyypa0JaaGjcVpaacmaabaGaaCiEamaaDaaaleaacaWGSbaabaWaaeWaaeaacaWGPbaacaGLOaGaayzkaaaaaOGaaiilaiaadsgadaqhaaWcbaGaamiBaaqaamaabmaabaGaamyAaaGaayjkaiaawMcaaaaaaOGaay5Eaiaaw2haamaaDaaaleaacaWGSbGaeyypa0JaaGymaaqaaiaadYeadaWgaaadbaGaamyAaaqabaaaaOGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caWGPbGaeyypa0JaaGymaiaacYcacqWIMaYscaGGSaGaam4saaaa@750F@ (9.2)

Az eddigi jelöléseknek megfelelően xl egy bemeneti vektor, dl 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 Ci megkülönböztetése Cj-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 { 0,1 } MathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamizamaaBaaaleaacaWGSbaabeaakiabgIGiopaacmaabaGaaGimaiaacYcacaaIXaaacaGL7bGaayzFaaaaaa@3DBF@ . A gyakorlatban azonban általában megengedjük, hogy a kívánt válasz: d l { ε,1ε } MathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamizamaaBaaaleaacaWGSbaabeaakiabgIGiopaacmaabaGaeqyTduMaaiilaiaaigdacqGHsislcqaH1oqzaiaawUhacaGL9baaaaa@4140@ legyen ahol ε egy kis pozitív szám. Ekkor a Ci, Cj osztálypárhoz tartozó mintakészlet az alábbi módon definiálható:

Z ij = { ( x l (i) ,1ε ) } l=1 L i { ( x l (j) ,ε ) } l=1 L j i,j=1...Késij MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOwamaaBaaaleaacaWGPbGaamOAaaqabaGccqGH9aqpdaGadaqaamaabmaabaGaaCiEamaaDaaaleaadaWgaaadbaGaamiBaaqabaaaleaacaqGOaGaamyAaiaabMcaaaGccaGGSaGaaGymaiabgkHiTiabew7aLbGaayjkaiaawMcaaaGaay5Eaiaaw2haamaaDaaaleaacaWGSbGaeyypa0JaaGymaaqaaiaadYeadaWgaaadbaGaamyAaaqabaaaaOGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaeyOkIGSaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7daGadaqaamaabmaabaGaaCiEamaaDaaaleaadaWgaaadbaGaamiBaaqabaaaleaacaqGOaGaamOAaiaabMcaaaGccaGGSaGaeqyTdugacaGLOaGaayzkaaaacaGL7bGaayzFaaWaa0baaSqaaiaadYgacqGH9aqpcaaIXaaabaGaamitamaaBaaameaacaWGQbaabeaaaaGccaaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaamyAaiaacYcacaaMi8UaaGjcVlaadQgacqGH9aqpcaaIXaGaaGjcVlaayIW7caaMi8UaaiOlaiaayIW7caaMi8UaaGjcVlaac6cacaaMi8UaaGjcVlaayIW7caGGUaGaaGjcVlaayIW7caaMi8Uaam4saiaayIW7caaMi8UaaGjcVlaabMoacaWGZbGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caWGPbGaeyiyIKRaamOAaaaa@B10D@ (9.3)

vagyis a Ci osztályba tartozó mintákra a kívánt válasz közel 1, a Cj-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 Zij csak a Ci és a Cj 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ó.

9.1. ábra - Egy háromosztályos feladat felbontása 3 egyszerű kétosztályos feladatra
Egy háromosztályos feladat felbontása 3 egyszerű kétosztályos feladatra

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

Z i ( j ) = { z l ( ij ) } l=1 L i ( j ) = { x l ( ij ) , d l ( ij ) } l=1 L i ( j ) j=1,, M i MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOwamaaDaaaleaacaWGPbaabaWaaeWaaeaacaWGQbaacaGLOaGaayzkaaaaaOGaeyypa0ZaaiWaaeaacaWH6bWaa0baaSqaaiaadYgaaeaadaqadaqaaiaadMgacaWGQbaacaGLOaGaayzkaaaaaaGccaGL7bGaayzFaaWaa0baaSqaaiaadYgacqGH9aqpcaaIXaaabaGaamitamaaDaaameaacaWGPbaabaWaaeWaaeaacaWGQbaacaGLOaGaayzkaaaaaaaakiaayIW7cqGH9aqpcaaMi8+aaiWaaeaacaWH4bWaa0baaSqaaiaadYgaaeaadaqadaqaaiaadMgacaWGQbaacaGLOaGaayzkaaaaaOGaaiilaiaadsgadaqhaaWcbaGaamiBaaqaamaabmaabaGaamyAaiaadQgaaiaawIcacaGLPaaaaaaakiaawUhacaGL9baadaqhaaWcbaGaamiBaiabg2da9iaaigdaaeaacaWGmbWaa0baaWqaaiaadMgaaeaadaqadaqaaiaadQgaaiaawIcacaGLPaaaaaaaaOGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caWGQbGaeyypa0JaaGymaiaacYcacqWIMaYscaGGSaGaamytamaaBaaaleaacaWGPbaabeaaaaa@8064@ , (9.4)

ahol L i ( j ) MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamitamaaDaaaleaacaWGPbaabaWaaeWaaeaacaWGQbaacaGLOaGaayzkaaaaaaaa@39CD@ jelöli ennek a részhalmaznak az elemszámát. A részhalmazokra igaz kell legyen, hogy j=1 M i Z i ( j ) = Z i MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkIG8aa0baaSqaaiaadQgacqGH9aqpcaaIXaaabaGaamytamaaBaaameaacaWGPbaabeaaaaGccaWGAbWaa0baaSqaaiaadMgaaeaadaqadaqaaiaadQgaaiaawIcacaGLPaaaaaGccqGH9aqpcaWGAbWaaSbaaSqaaiaadMgaaeqaaaaa@4358@ és j=1 M i Z i ( j ) = MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykIC8aa0baaSqaaiaadQgacqGH9aqpcaaIXaaabaGaamytamaaBaaameaacaWGPbaabeaaaaGccaWGAbWaa0baaSqaaiaadMgaaeaadaqadaqaaiaadQgaaiaawIcacaGLPaaaaaGccqGH9aqpcqGHfiIXaaa@42D6@ . Az így definiált tanító részhalmazok segítségével definiálhatjuk a kétosztályos osztályozási feladatokat. A Ci osztály u-adik részhalmaza és a Cj osztály v-edik részhalmaza által képezett kétosztályos feladat tanító készlete ennek megfelelően:

Z ij ( u,v ) = { ( x l (iu) ,1ε ) } l=1 L i ( u ) { ( x l (jv) ,ε ) } l=1 L j ( v ) i,j=1,,Késij,u=1,, M i ,v=1,, M j MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGAbWaa0baaSqaamaaBaaameaacaWGPbGaamOAaaqabaaaleaadaqadaqaaiaadwhacaGGSaGaamODaaGaayjkaiaawMcaaaaakiabg2da9maacmaabaWaaeWaaeaacaWH4bWaa0baaSqaamaaBaaameaacaWGSbaabeaaaSqaaiaabIcacaWGPbGaamyDaiaabMcaaaGccaGGSaGaaGymaiabgkHiTiabew7aLbGaayjkaiaawMcaaaGaay5Eaiaaw2haamaaDaaaleaacaWGSbGaeyypa0JaaGymaaqaaiaadYeadaqhaaadbaWaaSbaaeaacaWGPbaabeaaaeaadaqadaqaaiaadwhaaiaawIcacaGLPaaaaaaaaOGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaeyOkIGSaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7daGadaqaamaabmaabaGaaCiEamaaDaaaleaadaWgaaadbaGaamiBaaqabaaaleaacaqGOaGaamOAaiaadAhacaqGPaaaaOGaaiilaiabew7aLbGaayjkaiaawMcaaaGaay5Eaiaaw2haamaaDaaaleaacaWGSbGaeyypa0JaaGymaaqaaiaadYeadaqhaaadbaWaaSbaaeaacaWGQbaabeaaaeaadaqadaqaaiaadAhaaiaawIcacaGLPaaaaaaaaOGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVdqaaaqaaiaadMgacaGGSaGaaGjcVlaayIW7caWGQbGaeyypa0JaaGymaiaacYcacqWIVlctcaGGSaGaaGjcVlaadUeacaaMi8UaaGjcVlaayIW7caqGPdGaam4CaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaamyAaiabgcMi5kaadQgacaGGSaGaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caWG1bGaeyypa0JaaGymaiaacYcacqWIMaYscaGGSaGaamytamaaBaaaleaacaWGPbaabeaakiaacYcacaaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaadAhacqGH9aqpcaaIXaGaaiilaiablAciljaacYcacaWGnbWaaSbaaSqaaiaadQgaaeqaaaaaaa@DA3A@ (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 Ci osztályba tartozó mintákat mindig más-más Cj, j=1,2,…,K, ji 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 (Ci, Cj) 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 Ci osztályba tartozik és akkor lesz ε, ha a Cj-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 MIN =min( x 1 , x 2 ,, x N ) MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyEamaaBaaaleaacaqGnbGaaeysaiaab6eaaeqaaOGaeyypa0JaaeyBaiaabMgacaqGUbGaaeikaiaadIhadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamiEamaaBaaaleaacaaIYaaabeaakiaacYcacqWIMaYscaGGSaGaamiEamaaBaaaleaacaWGobaabeaakiaabMcaaaa@4749@ , (9.6)

ahol x1, x2, …, xN jelölik a MIN modul bemeneteit, yMIN 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 Ci osztályba besorolni, ha a MIN modullal összefogott összes osztályozó a Ci osztályba sorolja az adott mintát.

A második esetben olyan moduljaink vannak, melyek feladata, hogy egy adott Cj 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 Cj osztály v-edik és a Ci 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 Cj 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 MAX =max( x 1 , x 2 ,, x N ) MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyEamaaBaaaleaacaqGnbGaaeyqaiaabIfaaeqaaOGaeyypa0JaaeyBaiaabggacaqG4bGaaeikaiaadIhadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamiEamaaBaaaleaacaaIYaaabeaakiaacYcacqWIMaYscaGGSaGaamiEamaaBaaaleaacaWGobaabeaakiaabMcaaaa@474D@ , (9.7)

ahol a modul bemenetei most is az x1, x2, …, xN értékek, kimenete pedig yMAX. 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 Cj 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

i=1 K j=1 ji K M i M j MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaadaaeWbqaaiaad2eadaWgaaWcbaGaamyAaaqabaGccaWGnbWaaSbaaSqaaiaadQgaaeqaaaabaeqabaGaamOAaiabg2da9iaaigdaaeaacaWGQbGaeyiyIKRaamyAaaaabaGaam4saaqdcqGHris5aaWcbaGaamyAaiabg2da9iaaigdaaeaacaWGlbaaniabggHiLdaaaa@486F@ (9.8)

-ről

i=1 K j=i+1 K M i M j MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaadaaeWbqaaiaad2eadaWgaaWcbaGaamyAaaqabaGccaWGnbWaaSbaaSqaaiaadQgaaeqaaaqaaiaadQgacqGH9aqpcaWGPbGaey4kaSIaaGymaaqaaiaadUeaa0GaeyyeIuoaaSqaaiaadMgacqGH9aqpcaaIXaaabaGaam4saaqdcqGHris5aaaa@4694@ (9.9)

-re redukálható, ahol Mk a Ck (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.2. ábra - Az 9.1 ábrán látható háromosztályos feladat moduláris megoldása
Az 9.1 ábrán látható háromosztályos feladat moduláris megoldása

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.

9.3. ábra - Egy egyszerű, lineárisan nem szeparálható kétosztályos feladat (a zöld tanító mintapontok az egyik, a feketék a másik osztályba tartoznak)
Egy egyszerű, lineárisan nem szeparálható kétosztályos feladat (a zöld tanító mintapontok az egyik, a feketék a másik osztályba tartoznak)

9.4. ábra - A moduláris kialakítás lépései (az egyes részmegoldások a sötéttel jelzett területeken adnak közel 1 értéket, a világossal jelölt területeken közel 0 értéket)
A moduláris kialakítás lépései (az egyes részmegoldások a sötéttel jelzett területeken adnak közel 1 értéket, a világossal jelölt területeken közel 0 értéket)

9.5. ábra - A 9.3 ábrán látható feladat dekompozíciónak megfelelő moduláris háló felépítése
A 9.3 ábrán látható feladat dekompozíciónak megfelelő moduláris háló felépítése

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.



[6] Ebben a fejezetben az eddigiektől eltérően a mintapontok számát nem P-vel, hanem L-lel jelöljük. Ennek oka, hogy a fejezetben tárgyalt egyes moduláris rendszereknél valószínűségi értelmezés, vagy valószínűségek meghatározása is szükséges, és P-t a megfelelő sűrűségfüggvények vagy valószínűségek jelölésére használjuk.