Hogyan alkalmazható a többszörös dimenzióskálázás (MDS) nem-euklideszi hasonlóságokkal?

A többszörös dimenzióskálázás (MDS) és a kernel PCA alapvetően azonos működési elvet követnek – mindkettő az eigenvektorok legnagyobb komponenseire vetítve dolgozik. Azonban, ha a D mátrix nem negatív féldefinált, akkor nincs közvetlen kapcsolat a kernel PCA-val. Az egyik legfontosabb alkalmazási terület az izometrikus beágyazásoknál abban rejlik, amikor a D mátrix nem euklideszi távolságmátrix, hanem valamilyen más normán alapuló távolságot mértek, vagy akár nem metrikus távolságot, mint például a koszinusz távolság. Ebben az esetben a D mátrix nem biztos, hogy megfelel az euklideszi távolságmátrix kritériumainak, azaz JDJ nem feltétlenül negatív féldefinált. Mégis, egy olyan beágyazást keresünk, amely megőrzi a D távolságait annyira, amennyire csak lehetséges a euklideszi térben.

A módszer alapja a középpontba helyezett mátrix, melyet H = − 1 2 JDJ-ként jelölünk. Ha D = DX egy euklideszi távolságmátrix, akkor a H = XXT formátumban jelenik meg, ahol a hij elemek a középpontosított adatpontok közötti belső szorzatok, és ezzel egy hasonlósági mátrixot alkotunk. A hasonlóságokat a koszinusz hasonlósághoz hasonlóan értelmezhetjük, ahol hij nagyobb értéket vesz fel, amikor az adatpontok i és j hasonlóbbak egymáshoz. Így, amikor D nem egy euklideszi távolságmátrix, H-t hasonlósági mátrixként kezeljük, amely a távolságok helyett a hasonlóságokat tükrözi.

Ezután a célunk, hogy megtaláljuk azt a X adatmátrixot, amely a következő minimizálási problémát oldja meg: min ‖H − XXT ‖2F, ahol X ∈ Mm×k. Ez a probléma hasonlít a klasszikus PCA problémájához, de mivel a XXT pozitív féldefinált, míg H nem feltétlenül az, nem alkalmazhatjuk közvetlenül az SVD-t vagy az eigenérték-dekompozíciót. A probléma lényegében egy korlátozott verziója a klasszikus PCA-nak, ahol a minimizálás csak a pozitív féldefinált mátrixok k-szintű rangjára vonatkozik.

A fenti matematikai formulák és a beágyazás matematikai kerete segít abban, hogy egy optimális megoldást találjunk, még akkor is, ha a bemeneti mátrixok nem euklideszi alapú távolságokkal rendelkeznek. A Theorem 8.27 kimondja, hogy ha a H mátrix szimmetrikus, és λi az egyes eigenértékek, akkor a legjobb pozitív féldefinált mátrix, amely a Frobenius-normát minimalizálja, a következő formában állítható elő: k Hk = λ+ i pipT i, ahol λ+ i = max{λi, 0}, és a legjobb approximációval rendelkező k-szintű mátrixok segítenek a hasonlóságok megőrzésében.

A klasszikus multidimenziós skálázás (klasszikus MDS) tehát egy olyan eszköz, amely lehetővé teszi a távolságok megőrzését a beágyazás során, miközben a távolságok közvetlen euklideszi normája helyett más hasonlósági mérőszámokat alkalmazunk. Az így kapott vizualizációk, mint az MNIST adathalmaz esetében, amelyek koszinusz-hasonlóságot alkalmaznak, vagy a Gauss-magos távolságot használó MDS, bemutatják, hogyan lehet az adatok közötti komplex kapcsolatokat és hasonlóságokat ábrázolni, még akkor is, ha az eredeti távolságmátrix nem metrikus.

Fontos megérteni, hogy a többszörös dimenzióskálázás alkalmazásakor nemcsak az adatok közötti távolságok, hanem azok hasonlóságai is rendkívül fontos szerepet játszanak a helyes beágyazás megtalálásában. A különböző típusú hasonlósági mátrixok alkalmazása, mint a koszinusz-hasonlóság vagy a Gauss-kernel alapú hasonlóság, különböző típusú vizualizációkat eredményezhet, amelyek más és más jellemzőket emelnek ki az adatok közötti kapcsolatokban.

A MDS tehát nemcsak a lineáris vagy euklideszi távolságok modellezésére korlátozódik, hanem lehetőséget ad arra is, hogy más típusú hasonlóságok és távolságok alkalmazásával találjunk érdemi beágyazásokat, különösen akkor, ha a normák nem a klasszikus euklideszi távolságokra építenek. A gyakorlatban mindenképp fontos, hogy megfelelően válasszuk meg a hasonlósági mértéket és figyeljünk az adatjellemzőkhez leginkább illeszkedő beágyazási technikák alkalmazására, hogy a vizualizációk és az analízisek valósághű és értelmes eredményeket adjanak.

Hogyan számítható ki egy mátrix rangja és nullitása?

Tegyük fel, hogy egy $b$ vektor egy mátrix egyenleteként van megadva, azaz $b = A x$, ahol $A$ egy $m \times n$ méretű mátrix, $x$ pedig egy $n$-dimenziós vektor. Ekkor azt mondjuk, hogy a vektor $b$ benne van a mátrix képében, ha létezik egy olyan vektor $x$, amely megoldja az egyenletet. Ez a képi tér dimenziójára, azaz a rangra vonatkozó alapvető információt nyújt.

A mátrix rangja az ábrázolt képi tér dimenziójával egyenlő, tehát egy mátrix rangja a képi térének dimenziója. A rang meghatározza, hogy hány lineárisan független oszlop létezik a mátrixban, és hogy hány különböző irányt ölel fel a képtér.

A rang meghatározása

A kernel és nullitás

Egy másik fontos fogalom a mátrixokkal kapcsolatban a kernel, vagy null tér, amely azokat a vektorokat tartalmazza, amelyeket a mátrix nullára transzformál. Formálisan, ha egy mátrix $A$ van, akkor a kernelje a következő módon van definiálva:

A rang és a nullitás közötti kapcsolatot a következő fontos tétel fogalmazza meg:

Ez azt jelenti, hogy a mátrix rangjának és nullitásának összege mindig megegyezik a mátrix oszlopainak számával.

Nonszinguláris mátrixok

Az olyan mátrixok, mint az egységmátrix, mindig nonszingulárisak, mivel a képtér minden irányt átfog, és ezért az invertálhatóságuk is biztosított. Ezzel szemben a nulla mátrix rangja nulla, és nullitása $n$-nek megfelelően teljesen szabad.

Összefüggés a mátrixok rangja és transzponáltja között

Egy érdekes tulajdonság, hogy egy mátrix és annak transzponáltja ugyanannyi ranggal rendelkeznek. Ez a tény meglepő lehet, mivel a rang a mátrix oszlopaiból származó vektorok lineáris függetlenségét méri, míg a transzponált mátrix sorait. Azonban a két tér dimenziója egyenlő, és ez azt jelenti, hogy a mátrix és a transzponált rangja mindig megegyezik.

A mátrix szorzatok rangja

\

Hogyan segít a lineáris algebra a gépi tanulás optimalizálásában?

A modern gépi tanulás alapját a lineáris algebra képezi, de az alapvető feladat mégis az optimalizálás. Az optimalizálás célja egy adott valós értékű nemlineáris függvény minimumának (vagy maximumának) megtalálása, amelyet ebben az összefüggésben veszteségfüggvénynek, célfüggvénynek, költségfüggvénynek, entrópiának vagy energiának nevezhetünk. Ez a függvény mérni hivatott az algoritmus teljesítményét, és minden esetben a legjobb eredményt szeretnénk elérni, különösen akkor, ha az új adatokra is alkalmazzuk, amelyek címkéinek előrejelzése a cél.

A veszteségfüggvények sokszor rengeteg paramétert tartalmaznak, melyek értékeit optimálisan kell beállítani az algoritmus betanítása során. Mégis, ezek a függvények alapvetően egyszerű összetevőkből építkeznek, mint például lineáris (vagy affinis) függvények, meglepően egyszerű nemlinearitásokkal kombinálva. Az optimalizálás során alapvető szerepe van a differenciálkalculus egyszerűbb eredményeinek, amelyeket itt anélkül ismertetünk, hogy bizonyítanánk őket; a részletekhez az érdeklődő olvasó bármely bevezető szintű szakkönyvet felhasználhat, mint például a [4,158] számú referencia. A differenciálkalculus kulcselemei közé tartoznak az egyváltozós és többváltozós függvények, folytonosság, határértékek, differenciálhatóság, az egyszerű és parciális deriváltak számítása, valamint különösen a láncszabály. A gépi tanulásban alapvető szerepet játszó automatikus differenciálás egy egyszerűsített módszert kínál a bonyolult veszteségfüggvények deriváltjainak kiszámítására a láncszabály segítségével.

A későbbi fejezetekben szükség lesz némi alapvető ismeretre a differenciálegyenletekről, különösen az egyszerű lineáris egyenletekről, és azok numerikus megoldási módszereiről; egy jó referencia erre a [30] számú mű. Az egyszerű integrálás, különösen a szkaláris függvények esetén, időnként előfordul. Feltételezzük továbbá, hogy az olvasó rendelkezik némi alapvető ismerettel a topológia terén is, különösen az euklideszi tér vonatkozásában. Ide tartozik az olyan fogalmak ismerete, mint a nyílt, zárt és kompakt (zárt és korlátos) halmazok, azok belső és határa, valamint a (útvonalas) összefüggőség. A legfontosabb eredmények között szerepel a folyamatos valós értékű függvények maximumának és minimumának létezése kompakt halmazon, amelynek célja a megtalálásuk módszerei.

Az első fejezet bevezeti a vektorokat, kezdve azok alapvető aritmetikai műveleteivel – összegzés és skaláris szorzás. Az itt alkalmazott vektorok túlnyomórészt valós vektorok, véges dimenziójú euklideszi térben. A fejezet további része az alapvető fogalmakat fedi le, mint a szubtér, a spán, a lineáris függetlenség, az alap és a dimenzió, ezen fogalmak megfelelő alkalmazásával és megértésével sikeresebbé válhatunk a téma elsajátításában.

A második fejezet a szokásos skaláris szorzatot és euklideszi normát ismerteti, hogy motiválja az általános belső szorzatok és azok normáinak bevezetését. A különböző normák és belső szorzatok kezelése alapvető fontosságú a gépi tanulási algoritmusok fejlesztésében. A Cauchy–Schwarz egyenlőség egyszerűen levezethető ebben a keretben, és az ismertebb háromszög-egyenlőség is következik a belső szorzattal rendelkező normákra.

A harmadik fejezet a mátrixokat és azok alapvető aritmetikai műveleteit ismerteti – mátrixösszeadás, skaláris és mátrixszorzás, valamint azok vektorokra gyakorolt hatása. A szimmetrikus mátrixok alapvető fontosságú osztályát is bemutatjuk. A mátrixok és a lineáris algebrai egyenletrendszerek közötti kapcsolat lehetővé teszi a mátrixokhoz kapcsolódó alapvető szubtérfogalmak bevezetését: a képe és a kernelje, amelyek dimenziója a rang és a nullitás. A fejezet röviden bemutatja a mátrix inverzét, de mivel a célunk a valós alkalmazásokban használt algoritmusok elsajátítása, a számítások során gyakran nem szükséges a mátrix inverzét vagy determinánsát kiszámítani, így ezen részletek tárgyalása rövid.

A fejezetek további részeiben az ortogonális bázisok, a Gram–Schmidt algoritmusok, az ortogonális projekciók, a legkisebb négyzetek módszere és az egyéb alkalmazások kerülnek bemutatásra, mind a gépi tanulás, mind pedig a lineáris algebrai rendszerek megoldása szempontjából. Az olvasó számára rendkívül fontos, hogy az alapvető lineáris algebrai ismereteket és azok alkalmazását képes legyen tudatosan használni a különféle algoritmusok optimalizálásában és implementálásában.

Hogyan működik az ortogonális iteráció az eigenértékek számításában?

Ha a hatvány-módszerrel próbálunk több, mondjuk p eigenvektort és eigenértéket kiszámítani, akkor az első reakció az lehet, hogy több, lineárisan független kezdő vektort választunk az inicializáláskor, és egyszerre végezzük el az iterációt azokon. Azonban a probléma az, hogy szinte minden vektor esetén az iterációk során végül az összes vektor a legnagyobb sajátvektor egy szorzatává válik. Az ilyen esetekben egyszerű normalizálás sem segít, hiszen a vektorok végül az egyik domináns sajátvektor irányába konvergálnak. Az ortogonális iteráció célja, hogy megakadályozza ezt a jelenséget, és biztosítsa, hogy a vektorok ne egyetlen domináns sajátvektor felé konvergáljanak, hanem az összes szükséges eigenvektor irányába.

Az ortogonális iteráció lényege, hogy a kezdő vektorokat ortonormalizáljuk minden egyes lépés után. Ezt a Gramm-Schmidt-féle ortonormalizáló eljárás segítségével végezzük el, így a vektorok nemcsak az eigenvektorok irányába konvergálnak, hanem azokat az ortonormált vektorokat eredményeznek, amelyek az eigenvektorokat reprezentálják. Ezt az eljárást egy szorzás és faktorizálás sorozataként végezzük el, amely során a mátrixokat fokozatosan átalakítjuk, miközben megőrizzük a vektorok ortonormalitását.

Fontos, hogy az ortogonális iterációban alkalmazott konvergenciát alapvetően a kezdő vektorok helyes megválasztása biztosítja. A kezdeti vektoroknak nem lehetnek olyan ortogonális komponenseik, amelyek kizárnák őket a sajátvektorok irányából. Az ilyen problémák elkerülése érdekében a legnagyobb eigenértékek sajátvektorainak irányába történő irányultságot garantálni kell. Ezt általában egy szabályos feltétellel biztosítjuk, amely az inicializáló vektorok egymással való kapcsolatát határozza meg. Az eljárás akkor garantáltan konvergál, ha az inicializáló vektorok nem ortogonálisak az első p sajátvektor irányába.

Ha a sajátértékek különböznek, akkor az ortogonális iteráció gyorsan konvergál, és az eredmények az eigenértékeket egyre pontosabban tartalmazzák a megfelelő sorrendben. A módszer képes akár az összes eigenérték kiszámítására is, ha azt szükségesnek találjuk, de természetesen a legnagyobb p eigenértékekre fókuszálva alkalmazható a leghatékonyabban.

Az ortogonális iteráció egyik fontos előnye, hogy az algoritmus több eigenvektor és eigenérték meghatározását végzi el egyszerre, ami jelentősen csökkenti a számítási időt és javítja az eredmények pontosságát. A hatvány-módszerhez képest tehát gyorsabb és hatékonyabb, különösen olyan esetekben, ahol több eigenvektorra van szükség. Az ortogonális iteráció tehát egy olyan eljárás, amely gyorsan alkalmazható nagyobb méretű mátrixok esetén is, és segít a sajátvektorok és eigenértékek pontosabb és gyorsabb meghatározásában.