Mi az a Lineáris Diszkriminancia Analízis és hogyan működik a felügyelt osztályozásban?

Feltételezzük, hogy rendelkezünk információval az adatok osztályairól, vagyis a teljesen felügyelt osztályozás keretein belül dolgozunk. Az adatkészletünkben adottak az adatpontok $x_1, \ldots, x_m \in \mathbb{R}^n$, melyek egy $m \times n$ méretű adatmátrixot alkotnak, valamint az ezekhez tartozó osztálycímkék $y_1, \ldots, y_m$, melyek egész számok az 1 és $c$ közötti tartományból, és jelzik, hogy az adott adatpont melyik osztályhoz tartozik. Az $i$-edik osztály adatpontjainak indexeit $C_i = \{ j \mid y_j = i \}$-vel jelöljük, és az osztály adatpontjainak számát $m_i = \# C_i$-vel. Az egyes osztályokhoz tartozó részmátrixokat $X_i$-vel jelöljük, ahol $X_i$ egy $m_i \times n$ méretű mátrix, amely az $i$-edik osztály adatait tartalmazza.

A diszkriminancia elemzéshez először bevezetjük az osztályalapú kovariancia mátrixokat. Az $i$-edik osztály átlaga

mely alapján az osztály kovariancia mátrixa a következő:

A cél egy olyan egységvektor $u \in \mathbb{R}^n$ megtalálása, amely maximalizálja az osztályok közötti szórás (variancia) és minimalizálja az osztályokon belüli szórást. Ez a kettősség az osztályelválasztás alapja: az osztályokat egymástól távol tartjuk, miközben az egyes osztályokon belül a pontokat közelebb hozzuk egymáshoz. Ezért optimalizáljuk az alábbi hányadost, az úgynevezett osztályelválasztási mutatót:

Ha feltesszük, hogy $S_w$ pozitív definit, akkor ez egy általánosított Rayleigh hányados, amelynek maximális értékét és a hozzá tartozó vektort az általánosított sajátérték-probléma

megoldásai adják. A legnagyobb sajátértékhez tartozó sajátvektor az optimális irány, amely mentén az osztályok a legjobban elkülöníthetők.

Gyakran előfordulhat, hogy $S_w$ szinguláris vagy közel szinguláris, azaz nem invertálható vagy rossz kondíciószámú. Ez problémát okozhat a probléma numerikus megoldásában, mivel a hányados értelmezése ilyenkor nehéz. Ezt a problémát többféleképpen kezelhetjük: egyik lehetőség, hogy a $S_w$ mátrixot regulárizáljuk úgy, hogy hozzáadunk egy kis identitásmátrixot, vagyis $S_{w,\lambda} = S_w + \lambda I$, ahol $\lambda > 0$ egy kis paraméter. Ez a kovariancia-összehúzás (covariance shrinkage) egyszerűen megvalósítható, és kis értékek általában elegendőek a pozitív definitás biztosításához.

Az LDA alapvetően egy vetítési eljárás, amely az adatokat a kiválasztott diszkrimináló irányokra vetíti, így erősítve az osztályok közötti különbségeket és csökkentve az osztályokon belüli varianciát. Ez a vetítés általában megelőzi a különböző felügyelt osztályozó algoritmusokat, de önmagában is használható az osztályok megkülönböztetésére.

Miért fontos a momentum a nehéz labda módszerében és hogyan befolyásolja a konvergenciát?

A nehéz labda módszerének alapja az, hogy az iterációk során figyelembe veszi a korábbi irányokat, amely lehetővé teszi a gyorsabb előrehaladást az optimális megoldás felé, különösen akkor, ha a hagyományos gradiens módszer nem elegendő. A Polyak által 1964-ben javasolt módszer úgy működik, hogy a korábbi lépés és a gradiens együttes figyelembevételével módosítja a következő iteráció irányát. A módszer formulája:

Ahol $\alpha$ a rögzített lépésköz, $\beta > 0$ pedig egy momentum paraméter. Az iteráció során figyelembe vesszük a korábbi lépés irányát, $x_k - x_{k-1}$, és ezt kombináljuk a gradiens negatív irányával, $-\nabla F(x_k)$. A módszer lényege, hogy az előző irányt használva csökkenti a "bouncing" hatást, amely a nagy lépésközökkel végzett gradiens módszer alkalmazásakor tapasztalható. Az így elért javulás nem csupán a gyorsabb előrehaladást jelenti, hanem a konvergencia ütemének növelését is.

A nehéz labda módszer egyik fontos jellemzője, hogy szükség van két kezdeti feltételre: $x_0$ és $x_1$. Általában a $x_1$-et egyenlővé teszik $x_0$-val, vagy $x_1$-et az egyszerű gradiens módszer első lépésével választják meg. A választott paraméterek és kezdeti feltételek nagyban befolyásolják a módszer konvergenciáját, és ha nem megfelelőek, az iterációk instabilitásához vezethetnek. Ennek elkerülése érdekében az $\beta$ paraméter értékét szigorúan a [0, 1] intervallumban kell tartani, mivel ennek túllépése instabilitást eredményezhet, amely a konvergencia megakadályozásához vezethet.

Amikor a nehéz labda módszert alkalmazzuk egy kvadratikus függvény minimizálására, ahol $\nabla F(x) = Hx - b$, és a cél a lineáris rendszer $Hx = b$ megoldása, akkor a nehéz labda iterációs képlet a következő formát ölti:

A konvergencia sebességét ebben az esetben a következő tétel határozza meg:

Tétel: Legyen $H$ szimmetrikus, pozitív definit. Legyen $x^*$ a lineáris rendszer egyedüli megoldása. Ha az $x_k$ iterációk a nehéz labda iterációs képletet követik, és $x_1 = x_0$, akkor minden $\epsilon > 0$ esetén létezik egy $N$ pozitív egész szám, amelynél minden $k \geq N$ esetén az alábbi egyenlőség teljesül:

Ez azt jelenti, hogy ha az $\alpha$ és $\beta$ paraméterek megfelelően vannak beállítva, a nehéz labda módszer konvergenciája gyorsabb lesz, mint a hagyományos gradiens módszeré, amely szintén lineáris konvergenciát biztosít. A megfelelő paraméterek, különösen a $\beta$ értéke, azonban nagyban befolyásolják a módszer teljesítményét, és érdemes ezeket finomhangolni a problémához.

Endtext