A fejezetben leírt osztályozási módszerek némelyikét, például a tartóvektor-gépeket és az AdaBoost módszert eredetileg bináris osztályozási problémákhoz tervezték. Sok olyan valós probléma van azonban, mint például a karakterfelismerés, az arcazonosítás és a szövegosztályozás, ahol a bemenő adatok kettőnél több kategóriába vannak osztva. Ez a szakasz néhány olyan módszert mutat be, amelyek a bináris osztályozókat terjesztik ki többosztályos problémák kezeléséhez. A módszerek szemléltetéséhez legyen Y={ y 1 , y 2 ,…, y K } a bemenő adatok osztályainak halmaza.

Az első módszer a többosztályos problémát K bináris problémára bontja. Minden y i ∈Y osztályhoz egy bináris problémát hozunk létre, ahol minden az y i osztályhoz tartozó példányt pozitív esetként, míg a kimaradó példányokat negatív esetekként tekintjük. Ezután egy bináris osztályozót alkotunk az y i osztály példányainak az összes többi osztálytól való elválasztásához. Ezt ``egy a többi ellen'' (one-against-rest, 1-r) módszernek nevezik.

A második, ``egy az egy ellen'' (one-against-one, 1-1) nevű módszer K(K−1)/2 bináris osztályozót hoz létre, ahol minden egyes osztályozót egy ( y i , y j ) osztálypár megkülönböztetésére használunk. Az ( y i , y j ) párhoz tartozó osztályozó létrehozásánál figyelmen kívül hagyjuk azokat a példányokat, amelyek nem tartoznak sem az y i , sem az y j osztályhoz. Az 1-r és az 1-1 módszernél is a bináris osztályozók által létrehozott predikciók kombinálásával osztályozunk egy tesztpéldányt. A predikciók kombinálásához tipikusan egy szavazási sémát alkalmaznak, ahol a legtöbb szavazatot kapott osztályt rendelik hozzá a tesztpéldányhoz. Az 1-r módszernél ha egy példány negatívként osztályozott, akkor a pozitív osztályt kivéve minden osztály egy szavazatot kap. Ez a módszer azonban a külöböző osztályok közötti döntetlenhez vezethet. Egy másik lehetőség a bináris osztályozók kimeneteinek valószínűség-becslésekké transzformálása, majd a tesztpéldánynak a legnagyobb valószínűségű osztályhoz rendelése.

5.10. Példa.

Vegyünk egy többosztályos problémát, ahol Y={ y 1 , y 2 , y 3 , y 4 } . Tételezzük fel, hogy egy tesztpéldányt az 1-r módszer szerint (+,−,−,−) módon osztályozunk. Más szavakkal, pozitívként osztályozzuk, ha y 1 -et használjuk pozitív osztályként, és negatívként, ha y 2 , y 3 és y 4 a pozitív osztály. Egyszerű többségi szavazás használata esetén y 1 kapja a legtöbb számú szavazatot, négyet, míg az összes többi osztály csak három szavazatot kap. A tesztpéldányt ezért y 1 osztályúként osztályozzuk.

Tételezzük fel, hogy a tesztpéldányt a következőképpen osztályozzuk az 1-1 módszer segítségével:

A táblázat első két sora az osztályozó építéséhez választott ( y i , y j ) osztálypároknak felel meg, az utolsó sor pedig a tesztpéldány prediktált osztályát reprezentálja. A predikciók kombinálása után y 1 és y 4 két szavazatot kap, míg y 2 és y 3 csak egy szavazatot kap. A tesztpéldányt ezért y 1 vagy y 4 osztályúként osztályozzuk, a döntetlen helyzetek megoldásához használt eljárástól függően.

Hibajavító kimenet kódolás

Az előző két módszer egy lehetséges problémája, hogy túl érzékenyek a bináris osztályozási hibákra. Az 5.10. példában adott 1-r módszernél ha legalább az egyik bináris osztályozó egy hibát vét az előrejelzéseiben, akkor az együttes végül az osztályok közötti döntetlent jelenthet vagy hibás előrejelzést adhat. Tételezzük fel például, hogy a tesztpéldány (+,−,+,−) módon osztályozott a harmadik osztályozó általi hibás osztályozásnak köszönhetően. Ebben az esetben bonyolult lesz megmondani, hogy a példányt vajon y 1 vagy y 3 osztályúként kell-e osztályozni, hacsak nem vesszük figyelembe az egyes osztálypredikciókhoz tartozó valószínűségeket.

A hibajavító kimenet kódolás (ECOC -- error-correcting output coding) módszer egy robusztusabb módját biztosítja többosztályos problémák kezelésének. A módszert egy zajos csatornákon keresztüli üzenetküldés információelméleti megközelítése ihlette. A módszer mögötti ötlet az átvitt üzenetekhez redundancia hozzáadása egy kódszó segítségével úgy, hogy a vevő érzékelheti a kapott üzenet hibáit, és visszanyerheti az eredeti üzenetet, ha a hibák száma kicsi.

Többosztályos tanuláshoz minden y i osztályt egy kódszónak nevezett egyedi, n hosszú bitsorozat reprezentál. Ezután n bináris osztályozót tanítunk a kódszó bitsorozat minden egyes bitjének előrejelzéséhez. Egy tesztpéldány prediktált osztályát az a kódszó adja meg, amelynek Hamming-távolsága a legközelebbi a bináris osztályozók által előállított kódszóhoz. Emlékezzünk arra, hogy két bitsorozat közötti Hamming-távolságot az eltérő bitek száma adja meg.

5.11. Példa.

Tekintsünk egy többosztályos problémát, ahol Y={ y 1 , y 2 , y 3 , y 4 } . Tételezzük fel, hogy az osztályokat a következő 7-bites kódszavakkal kódoljuk:

A kódszó minden egyes bitjét egy bináris osztályozó tanításához használjuk fel. Ha egy tesztpéldányt (0,1,1,1,1,1,1) módon osztályoznak a bináris osztályozók, akkor a kódszó és y 1 közötti Hamming-távolság 1 , míg a többi osztálytól 3 a Hamming-távolság. A tesztpéldányt ezért y 1 osztályúként osztályozzuk.

A hibajavító kimenet kódolás egy érdekes tulajdonsága, hogy ha bármely kódszópár közötti minimális Hamming-távolság d , akkor a kimeneti kód bármely ⌊ (d−1)/2 ⌋ számú hibája javítható a legközelebbi kódszó segítségével. Mivel a minimális Hamming-távolság bármely kódszópár között 4 az 5.11. példában, az együttes elviselheti a hét bináris osztályozó egyike által vétett hibákat. Ha egynél több osztályozó vét hibát, akkor az együttes nem minden esetben képes a hiba kompenzálására.

Egy fontos kérdés a különböző osztályokhoz megfelelő kódszóhalmaz tervezésének módja. A kódelméletben hatalmas számú algoritmus került kifejlesztésre korlátos Hamming-távolságú n -bites kódszavak generálására. Ezeknek az algoritmusoknak a tárgyalása azonban kívül esik ennek a könyvnek a keretein. Érdemes megjegyezni, hogy szignifikáns különbség van a kommunikációs feladatokhoz használt hibajavító kódok és a többosztályos tanuláshoz használtak tervezése között. Kommunikációhoz a kódszavaknak a sorok közötti Hamming-távolságot kell maximalizálni, hogy a hibajavítás elvégezhető legyen. A többosztályos tanulás azonban megköveteli, hogy a kódszavak soronkénti és oszloponkénti távolságai jól elkülönültek legyenek. Egy nagyobb oszloponkénti távolság biztosítja azt, hogy a bináris osztályozók kölcsönösen függetlenek, amely egy fontos követelmény az együttes tanulási módszereknél.