Nelineární redukce rozměrů - Nonlinear dimensionality reduction

Vysoce dimenzionální data, tj. data, která k reprezentaci vyžadují více než dvě nebo tři dimenze, mohou být obtížně interpretovatelný. Jedním z přístupů ke zjednodušení je předpokládat, že zájmová data leží na vložený nelineární potrubí v rámci prostor vyšší dimenze. Pokud je potrubí dostatečně nízké dimenze, lze data vizualizovat v nízkodimenzionálním prostoru.

Vlevo nahoře: 3D datová sada 1 000 bodů ve spirálovitém pásmu (aka roláda ) s obdélníkovým otvorem uprostřed. Vpravo nahoře: původní 2D potrubí použité ke generování 3D datové sady. Vlevo dole a vpravo: 2D zotavení potrubí, respektive pomocí LLE a Hessian LLE algoritmy implementované sadou nástrojů Modulární zpracování dat.

Níže je uveden přehled některých důležitých algoritmů z historie rozmanité učení a nelineární redukce rozměrů (NLDR).[1][2] Mnoho z těchto nelineárních snížení rozměrů metody se vztahují k lineární metody uvedené níže. Nelineární metody lze široce rozdělit do dvou skupin: ty, které poskytují mapování (buď z vysoko-dimenzionálního prostoru do nízkodimenzionálního vkládání nebo naopak), a ty, které pouze poskytují vizualizaci. V kontextu strojové učení, lze mapovací metody považovat za předběžné extrakce funkcí krok, po kterém algoritmy rozpoznávání vzorů jsou použity. Ty, které pouze poskytují vizualizaci, jsou obvykle založeny na datech blízkosti - to znamená, vzdálenost Měření.

Související metody lineárního rozkladu

Aplikace NLDR

Zvažte datovou sadu představovanou jako matici (nebo databázovou tabulku), takže každý řádek představuje sadu atributů (nebo funkcí nebo dimenzí), které popisují konkrétní instanci něčeho. Pokud je počet atributů velký, pak je prostor jedinečných možných řádků exponenciálně velký. Čím větší je rozměrnost, tím obtížnější je vzorkování prostoru. To způsobuje mnoho problémů. Algoritmy, které pracují s vysokodimenzionálními daty, mají obvykle velmi vysokou časovou složitost. Mnoho algoritmů strojového učení například bojuje s vysokodimenzionálními daty. Toto se stalo známé jako kletba dimenzionality. Redukce dat na méně dimenzí často zefektivňuje analytické algoritmy a může pomoci algoritmům strojového učení vytvářet přesnější předpovědi.

Lidé mají často potíže s porozuměním dat v mnoha dimenzích. Redukce dat na malý počet dimenzí je tedy užitečná pro účely vizualizace.

Graf dvourozměrných bodů, který je výsledkem použití algoritmu NLDR. V tomto případě se sochařství rozdělovače používá k redukci dat pouze na dvě dimenze (rotace a měřítko).

Redukční dimenze reprezentace dat jsou často označovány jako „vnitřní proměnné“. Tento popis naznačuje, že se jedná o hodnoty, ze kterých byla data vytvořena. Zvažte například datovou sadu, která obsahuje obrázky písmene „A“, které bylo zmenšeno a otočeno o různé množství. Každý obrázek má 32x32 pixelů. Každý obrázek lze reprezentovat jako vektor s hodnotami 1024 pixelů. Každý řádek je vzorek na dvourozměrném potrubí v 1024-dimenzionálním prostoru (a Hammingův prostor ). Vnitřní dimenze jsou dvě, protože dvě proměnné (rotace a měřítko) se měnily, aby se vytvořila data. Informace o tvaru nebo vzhledu písmene „A“ nejsou součástí vnitřních proměnných, protože jsou v každém případě stejné. Nelineární redukce rozměrů zahodí korelované informace (písmeno „A“) a obnoví pouze různé informace (rotace a měřítko). Obrázek vpravo ukazuje ukázkové obrázky z této datové sady (pro úsporu místa nejsou zobrazeny všechny vstupní obrázky) a graf dvourozměrných bodů, který je výsledkem použití algoritmu NLDR (v tomto případě bylo použito sochařské tvarování) zredukovat data pouze na dvě dimenze.

PCA (algoritmus redukce lineární dimenze) se používá ke zmenšení stejné datové sady na dvě dimenze, výsledné hodnoty nejsou tak dobře organizované.

Pro srovnání, pokud Analýza hlavních komponent, což je algoritmus redukce lineární dimenze, se používá ke zmenšení stejné datové sady na dvě dimenze, výsledné hodnoty nejsou tak dobře organizované. To ukazuje, že vysokodimenzionální vektory (každý představující písmeno „A“), které vzorkují toto potrubí, se liší nelineárním způsobem.

Mělo by tedy být zřejmé, že NLDR má několik aplikací v oblasti počítačového vidění. Zvažte například robota, který používá kameru k navigaci v uzavřeném statickém prostředí. Snímky získané touto kamerou lze považovat za vzorky na potrubí ve vysokodimenzionálním prostoru a vnitřní proměnné tohoto potrubí budou představovat polohu a orientaci robota. Tento nástroj se neomezuje pouze na roboty. Dynamické systémy, obecnější třída systémů, která zahrnuje roboty, jsou definovány z hlediska potrubí. Aktivní výzkum v NLDR se snaží rozvinout pozorovací potrubí spojená s dynamickými systémy, aby vyvinuly techniky pro modelování těchto systémů a umožnily jim autonomní provoz.[3]

Níže jsou uvedeny některé z nejvýznamnějších algoritmů pro učení se různým způsobem. Algoritmus se může naučit interní model dat, která lze použít k mapování bodů nedostupných v době tréninku do vkládání do procesu, který se často nazývá přípona mimo vzorek.

Důležité koncepty

Sammonovo mapování

Sammonovo mapování je jednou z prvních a nejpopulárnějších technik NLDR.

Aproximace hlavní křivky jednorozměrným SOM (A přerušovaná čára s červenými čtverečky, 20 uzlů). První hlavní složka je znázorněna modrou přímkou. Datové body jsou malé šedé kruhy. Pro PCA je Frakce rozptylu nevysvětlitelná v tomto příkladu je 23,23%, pro SOM je to 6,86%.[4]

Samoorganizující se mapa

The samoorganizující se mapa (SOM, také volal Mapa Kohonen) a jeho pravděpodobnostní varianta generativní topografické mapování (GTM) pomocí bodové reprezentace ve vloženém prostoru vytvoří a latentní variabilní model na základě nelineárního mapování z vloženého prostoru do prostoru s vysokou dimenzí.[5] Tyto techniky souvisí s prací na hustotní sítě, které také vycházejí ze stejného pravděpodobnostního modelu.

Analýza hlavních komponent jádra

Snad nejpoužívanějším algoritmem pro mnohočetné učení je jádro PCA.[6] Je to kombinace Analýza hlavních komponent a trik s jádrem. PCA začíná výpočtem kovarianční matice matice

Poté promítne data na první k vlastní vektory této matice. Pro srovnání, KPCA začíná výpočtem kovarianční matice dat poté, co byla transformována do prostoru vyšší dimenze,

Potom promítá transformovaná data na první k vlastní vektory této matice, stejně jako PCA. Využívá trik jádra k odečtení velké části výpočtu, takže celý proces lze provést bez skutečného výpočtu . Samozřejmě musí být vybráno tak, aby mělo známé odpovídající jádro. Naneštěstí není jednoduché najít dobré jádro pro daný problém, takže KPCA nepřináší dobré výsledky s některými problémy při použití standardních jader. Je například známo, že si s těmito jádry na serveru špatně vedou roláda potrubí. Lze však zobrazit některé další metody, které v takových nastaveních fungují dobře (např. Laplacian Eigenmaps, LLE), jako speciální případy jádra PCA vytvořením matice jádra závislé na datech.[7]

KPCA má interní model, takže jej lze použít k mapování bodů do jeho vložení, které nebyly k dispozici v době školení.

Hlavní křivky a potrubí

Aplikace hlavních křivek: Nelineární index kvality života.[8] Body představují data OSN 171 zemí ve 4-dimenzionálním prostoru tvořených hodnotami 4 indikátorů: hrubý produkt na obyvatele, délka života, dětská úmrtnost, tuberkulóza výskyt. Různé formy a barvy odpovídají různým geografickým umístěním. Červená tučná čára představuje hlavní křivka, přibližný datový soubor. Tato hlavní křivka byla vytvořena metodou elastická mapa. Software je k dispozici pro nekomerční nekomerční použití.[9][10]

Hlavní křivky a potrubí dát přirozený geometrický rámec pro nelineární redukci rozměrů a rozšířit geometrickou interpretaci PCA explicitním vytvořením vloženého potrubí a kódováním pomocí standardní geometrické projekce na potrubí. Tento přístup navrhl Trevor Hastie ve své práci (1984)[11] a dále rozvíjeno mnoha autory.[12]Jak definovat „jednoduchost“ potrubí je závislé na problému, nicméně je běžně měřeno vnitřní rozměrností a / nebo plynulostí potrubí. Obvykle je hlavní potrubí definováno jako řešení optimalizačního problému. Objektivní funkce zahrnuje kvalitu aproximace dat a některé trestní podmínky pro ohýbání potrubí. Populární počáteční aproximace jsou generovány lineárním PCA, Kohonenovým SOM nebo automatickými kodéry. The elastická mapa metoda poskytuje algoritmus maximalizace očekávání pro jistinu rozmanité učení s minimalizací kvadratické energie funkční v kroku „maximalizace“.

Laplaciánské vlastní mapy

Viz také: Regularizace potrubí

Laplaciánské vlastní mapy používají spektrální techniky k provedení redukce rozměrů.[13] Tato technika se spoléhá na základní předpoklad, že data leží v nízkodimenzionálním potrubí ve vysokodimenzionálním prostoru.[14] Tento algoritmus nemůže vložit body mimo vzorek, ale techniky založené na Reprodukce jádra Hilbertova prostoru pro přidání této schopnosti existuje regularizace.[15] Takové techniky lze aplikovat i na jiné nelineární algoritmy snižování rozměrů.

Tradiční techniky, jako je analýza hlavních komponent, nezohledňují vnitřní geometrii dat. Laplaciánské vlastní mapy vytvářejí graf z informací o sousedství datové sady. Každý datový bod slouží jako uzel v grafu a konektivita mezi uzly se řídí blízkostí sousedních bodů (např. Pomocí Algoritmus k-nejbližšího souseda ). Takto generovaný graf lze považovat za diskrétní aproximaci nízkodimenzionálního potrubí ve vysokodimenzionálním prostoru. Minimalizace nákladové funkce na základě grafu zajišťuje, že body blízko sebe na potrubí jsou mapovány blízko sebe v nízkodimenzionálním prostoru, přičemž se zachovávají místní vzdálenosti. Vlastní funkce Operátor Laplace – Beltrami na potrubí slouží jako vkládací rozměry, protože za mírných podmínek má tento operátor spočetné spektrum, které je základem pro čtvercové integrovatelné funkce na potrubí (ve srovnání s Fourierova řada na jednotkovém kruhovém potrubí). Pokusy umístit laplaciánské vlastní mapy na pevnou teoretickou základnu se setkaly s určitým úspěchem, protože za určitých neomezujících předpokladů bylo prokázáno, že graf laplaciánské matice konverguje k operátoru Laplace-Beltrami, protože počet bodů jde do nekonečna.[14]

V klasifikačních aplikacích lze k modelování tříd dat, které lze definovat ze sad pozorovaných instancí, použít potrubí s nízkou dimenzí. Každou pozorovanou instanci lze popsat dvěma nezávislými faktory, které se nazývají „obsah“ a „styl“, kde „obsah“ je invariantní faktor související s podstatou třídy a „styl“ vyjadřuje variace v této třídě mezi instancemi.[16] Laplaciánské vlastní mapy bohužel nemusí být schopny vytvořit koherentní zastoupení třídy zájmu, když tréninková data sestávají z instancí, které se výrazně liší z hlediska stylu.[17] V případě tříd, které jsou reprezentovány vícerozměrnými sekvencemi, bylo navrženo strukturní laplaciánské vlastní mapy, aby se tento problém překonal přidáním dalších omezení do informačního grafu sousedství Laplacianských vlastních map, aby lépe odrážely vnitřní strukturu třídy.[18] Přesněji řečeno, graf se používá ke kódování jak sekvenční struktury vícerozměrných sekvencí, tak, aby se minimalizovaly stylistické variace, blízkost mezi datovými body různých sekvencí nebo dokonce uvnitř sekvence, pokud obsahuje opakování. Použitím dynamické časové deformace, blízkost je detekována nalezením korespondence mezi sekcemi vícerozměrných sekvencí a v jejich rámci, které vykazují vysokou podobnost. Experimenty prováděné dne rozpoznávání činnosti na základě vidění, klasifikace objektové orientace a aplikace pro obnovu 3D lidské pozice prokázaly přidanou hodnotu strukturálních laplaciánských vlastních map při práci s vícerozměrnými sekvenčními daty.[18] Rozšíření strukturních laplaciánských vlastních map, generalizovaných laplaciánských vlastních map, vedlo ke generování potrubí, kde jedna z dimenzí konkrétně představuje variace ve stylu. To se ukázalo zvláště cenné v aplikacích, jako je sledování lidského kloubového těla a extrakce siluety.[19]

Isomap

Isomap[20] je kombinací Floyd-Warshallův algoritmus s klasikou Vícerozměrné škálování. Classic Multidimensional Scaling (MDS) trvá matici párových vzdáleností mezi všemi body a vypočítává polohu pro každý bod. Isomap předpokládá, že párové vzdálenosti jsou známé pouze mezi sousedními body, a k výpočtu párových vzdáleností mezi všemi ostatními body používá algoritmus Floyd – Warshall. To efektivně odhaduje úplnou matici párově geodetické vzdálenosti mezi všemi body. Isomap pak používá klasický MDS k výpočtu zmenšených pozic všech bodů. Landmark-Isomap je varianta tohoto algoritmu, který používá orientační body ke zvýšení rychlosti za cenu určité přesnosti.

V učení potrubí se předpokládá, že vstupní data jsou vzorkována z nízkodimenzionálního potrubí který je vložen do výškového vektorového prostoru. Hlavní intuicí za MVU je využití lokální linearity potrubí a vytvoření mapování, které zachovává místní sousedství v každém bodě podkladového potrubí.

Lokálně lineární vkládání

Lokálně lineární vkládání (LLE)[21] byl představen přibližně ve stejnou dobu jako Isomap. To má několik výhod oproti Isomap, včetně rychlejší optimalizace při implementaci využít řídká matice algoritmy a lepší výsledky s mnoha problémy. LLE také začíná hledáním sady nejbližších sousedů každého bodu. Potom vypočítá sadu vah pro každý bod, který nejlépe popisuje bod jako lineární kombinaci jeho sousedů. Nakonec používá optimalizační techniku ​​založenou na vlastních vektorech k nalezení nízkodimenzionálního vkládání bodů, takže každý bod je stále popsán se stejnou lineární kombinací jeho sousedů. LLE má tendenci špatně zacházet s nerovnoměrnými hustotami vzorků, protože neexistuje pevná jednotka, která by bránila driftování vah, protože různé oblasti se liší v hustotách vzorků. LLE nemá žádný interní model.

LLE vypočítá barycentrické souřadnice bodu Xi na základě svých sousedů Xj. Původní bod je rekonstruován lineární kombinací danou maticí hmotnosti Žij, jejích sousedů. Chyba rekonstrukce je dána funkcí nákladů E(Ž).

Váhy Žij odkazují na výši příspěvku bod Xj při rekonstrukci bodu Xi. Funkce nákladů je minimalizována za dvou omezení: (a) Každý datový bod Xi je rekonstruován pouze od svých sousedů, čímž se prosazuje Žij být nula, pokud bod Xj není sousedem bodu Xi a (b) Součet každého řádku váhové matice se rovná 1.

Původní datové body se shromažďují v a D dimenzionální prostor a cílem algoritmu je snížit dimenzionálnost na d takhle D >> d. Stejné váhy Žij který rekonstruuje ith datový bod v D dimenzionální prostor bude použit k rekonstrukci stejného bodu ve spodní části d dimenzionální prostor. Na základě této myšlenky je vytvořena mapa pro zachování sousedství. Každý bod Xi v D dimenzionální prostor je mapován na bod Yi v d dimenzionální prostor minimalizací nákladové funkce

V této nákladové funkci, na rozdíl od předchozí, váhy Wij jsou udržovány pevné a minimalizace se provádí v bodech Yi optimalizovat souřadnice. Tento problém s minimalizací lze vyřešit řešením řídkého N X N problém vlastní hodnoty (N počet datových bodů), jejichž spodní část d nenulové vlastní vektory poskytují ortogonální sadu souřadnic. Obecně jsou datové body rekonstruovány z K. nejbližší sousedé, měřeno Euklidovská vzdálenost. Pro takovou implementaci má algoritmus pouze jeden volný parametr K, které lze zvolit křížovou validací.

Hessianské lokálně lineární vkládání (Hessian LLE)

Jako LLE, Hessian LLE je také založen na technikách řídké matice.[22] Má tendenci poskytovat výsledky mnohem vyšší kvality než LLE. Bohužel má velmi nákladnou výpočetní složitost, takže není vhodný pro silně vzorkované potrubí. Nemá žádný interní model.

Modifikované lokálně lineární vkládání (MLLE)

Modifikovaná LLE (MLLE)[23] je další varianta LLE, která používá více závaží v každém sousedství k řešení problému úpravy místní matice hmotnosti, což vede ke zkreslení v mapách LLE. Volně řečeno, několik závaží je místní ortogonální projekce původních závaží vyrobených společností LLE. Tvůrci této legalizované varianty jsou také autory Local Tangent Space Alignment (LTSA), což je implicitní ve formulaci MLLE, když si uvědomíme, že globální optimalizace ortogonálních projekcí každého váhového vektoru v podstatě srovnává lokální tangentní prostory každého datového bodu. Teoretické a empirické důsledky správné aplikace tohoto algoritmu jsou dalekosáhlé.[24]

Zarovnání místního tečného prostoru

Hlavní článek: Zarovnání místního tečného prostoru

LTSA[25] je založen na intuici, že když je potrubí správně rozloženo, všechny tečné hyperplany k potrubí budou zarovnány. Začíná to výpočtem k- nejbližší sousedé každého bodu. Vypočítává tečný prostor v každém bodě výpočtem d-prvé hlavní komponenty v každém místním sousedství. Poté se optimalizuje, aby se našlo vložení, které zarovná tečné prostory.

Maximální rozptyl se odvíjí

Maximální rozptyl rozložení „Isomap a Locally Linear Embedding sdílejí společnou intuici spoléhající se na představu, že pokud je rozdělovač správně rozložen, pak je maximalizována odchylka mezi body. Jeho počátečním krokem, jako je Isomap a Locally Linear Embedding, je nalezení k- nejbližší sousedé každého bodu. Poté se snaží vyřešit problém maximalizace vzdálenosti mezi všemi nesousedícími body, omezený tak, aby byly zachovány vzdálenosti mezi sousedními body. Primárním přínosem tohoto algoritmu je technika obsazení tohoto problému jako semidefinitního programovacího problému. Řešitelé semidefinitního programování mají bohužel vysoké výpočetní náklady. Stejně jako lokálně lineární vkládání nemá žádný interní model.

Autoencoders

An autoencoder je zpětná vazba nervová síť který je vyškolen k aproximaci funkce identity. To znamená, že je trénováno pro mapování z vektoru hodnot na stejný vektor. Při použití pro účely redukce rozměrů je jedna ze skrytých vrstev v síti omezena tak, aby obsahovala pouze malý počet síťových jednotek. Síť se tedy musí naučit kódovat vektor do malého počtu rozměrů a poté jej dekódovat zpět do původního prostoru. První polovina sítě je tedy modelem, který mapuje z vysokého do nízkodimenzionálního prostoru, a druhá polovina mapuje z nízko-dimenzionálního prostoru. I když je myšlenka autoencoderů docela stará, trénink hlubokých autoencoderů je možný teprve nedávno omezené Boltzmannovy stroje a naskládané odšumovací automatické kodéry. Souvisí s autoencoders je NeuroScale algoritmus, který využívá stresové funkce inspirované vícerozměrné škálování a Sammon mapování (viz výše), abyste se naučili nelineární mapování z trojrozměrného do vloženého prostoru. Mapování v NeuroScale jsou založena na radiální základní funkční sítě. Další využití neuronové sítě pro redukci rozměrů spočívá v tom, aby se naučila tečné roviny v datech.[26]

Latentní variabilní modely Gaussova procesu

Latentní variabilní modely Gaussova procesu (GPLVM)[27] jsou pravděpodobnostní metody redukce rozměrů, které používají Gaussovy procesy (GP) k nalezení nízkodimenzionálního nelineárního vkládání vysoce dimenzionálních dat. Jsou rozšířením pravděpodobnostní formulace PCA. Model je definován pravděpodobnostně a latentní proměnné jsou poté marginalizovány a parametry jsou získány maximalizací pravděpodobnosti. Stejně jako jádro PCA používají funkci jádra k vytvoření nelineárního mapování (ve formě a Gaussův proces ). V GPLVM je však mapování z vloženého (latentního) prostoru do datového prostoru (jako hustotní sítě a GTM), zatímco u jádra PCA je to v opačném směru. Původně byl navržen pro vizualizaci vysoce dimenzionálních dat, ale byl rozšířen o konstrukci sdíleného modelu potrubí mezi dvěma pozorovacími prostory. GPLVM a jeho mnoho variant byly navrženy speciálně pro modelování lidského pohybu, např. Zpětně omezený GPLVM, dynamický model GP (GPDM ), vyvážený GPDM (B-GPDM) a topologicky omezený GPDM. Aby se v analýze chůze zachytil vazebný účinek rozdělovačů pózu a chůze, bylo navrženo vícevrstvé společné rozdělovače chůze a pózy.[28]

t-distribuované stochastické vkládání sousedů

t-distribuované stochastické vkládání sousedů (t-SNE)[29] je široce používán. Je to jedna z rodiny stochastických metod vkládání sousedů. Algoritmus vypočítá pravděpodobnost, že páry datových bodů ve vysokodimenzionálním prostoru souvisejí, a poté zvolí nízkodimenzionální vložení, která vytvoří podobnou distribuci.

Další algoritmy

Relační perspektivní mapa

Relační perspektivní mapa je a vícerozměrné škálování algoritmus. Algoritmus najde konfiguraci datových bodů na potrubí simulací vícečásticového dynamického systému na uzavřeném potrubí, kde jsou datové body mapovány na částice a vzdálenosti (nebo odlišnost) mezi datovými body představují odpudivou sílu. Jak se rozdělovač postupně zvětšuje, multi-částicový systém se postupně ochlazuje a konverguje do konfigurace, která odráží informace o vzdálenosti datových bodů.

Mapa relační perspektivy byla inspirována fyzickým modelem, ve kterém se kladně nabité částice volně pohybují po povrchu koule. Vedeni Coulomb platnost mezi částicemi bude minimální energetická konfigurace částic odrážet sílu odpudivých sil mezi částicemi.

Mapa relační perspektivy byla představena v roce.[30]Algoritmus nejprve použil byt torus jako rozdělovač obrazu, byl rozšířen (v softwaru VisuMap používat jiné typy uzavřených potrubí, například koule, projektivní prostor, a Kleinova láhev, jako obrazové potrubí.

Nákazové mapy

Mapy nákazy používají více nákaz v síti k mapování uzlů jako mračno bodů.[31] V případě Model globálních kaskád rychlost rozmetání lze upravit parametrem prahu . Pro nákazová mapa je ekvivalentní s Isomap algoritmus.

Křivočará analýza složek

Křivočará analýza složek (CCA) hledá konfiguraci bodů ve výstupním prostoru, která co nejvíce zachovává původní vzdálenosti, přičemž se zaměřuje na malé vzdálenosti ve výstupním prostoru (naopak Sammonovo mapování které se zaměřují na malé vzdálenosti v původním prostoru).[32]

Je třeba si všimnout, že CCA jako iterativní algoritmus učení ve skutečnosti začíná zaměřením na velké vzdálenosti (jako je Sammonův algoritmus), poté postupně mění zaměření na malé vzdálenosti. Informace o malé vzdálenosti přepíší informace o velké vzdálenosti, pokud je třeba provést kompromisy mezi nimi.

Stresová funkce CCA souvisí se součtem správných Bregmanových divergencí.[33]

Křivočará analýza vzdálenosti

CDA[32] trénuje samoorganizující se neuronovou síť, aby se vešla do potrubí a snaží se ji zachovat geodetické vzdálenosti v jeho vložení. Je založen na Curvilinear Component Analysis (která rozšířila Sammonovo mapování), ale místo toho používá geodetické vzdálenosti.

Snížení difomorfní dimenze

Difeomorfní Snížení rozměrů nebo Diffeomap[34] se učí plynulé diffeomorfní mapování, které přenáší data na lineární podprostor nižší dimenze. Metody řeší plynulé časově indexované vektorové pole tak, aby toky podél pole, které začínají v datových bodech, skončily v lineárním podprostoru nižší dimenze, čímž se pokusí zachovat párové rozdíly jak v dopředném, tak i v inverzním mapování.

Zarovnání potrubí

Zarovnání potrubí využívá předpoklad, že různorodé datové sady vytvořené podobnými generujícími procesy budou sdílet podobnou podkladovou rozmanitou reprezentaci. Naučením projekcí z každého původního prostoru do sdíleného potrubí se získávají korespondence a znalosti z jedné domény lze přenést do jiné. Většina technik uspořádání potrubí zohledňuje pouze dvě datové sady, ale koncept se rozšiřuje na libovolně mnoho počátečních datových sad.[35]

Difúzní mapy

Difúzní mapy využívá vztah mezi teplem difúze a a náhodná procházka (Markovův řetězec ); analogie je nakreslena mezi operátorem difúze na potrubí a Markovovou přechodovou maticí fungující na funkcích definovaných v grafu, jehož uzly byly vzorkovány z potrubí.[36] Zejména nechte datovou sadu reprezentovat . Základním předpokladem difuzní mapy je, že vysoce dimenzionální data leží na nízkodimenzionálním potrubí dimenze . Nechat X představují soubor dat a představují distribuci datových bodů na X. Dále definujte a jádro což představuje určitou představu o afinitě bodů v X. Jádro má následující vlastnosti[37]

k je symetrický

k je zachování pozitivity

Lze si tedy představit jednotlivé datové body jako uzly grafu a jádra k jako definování jakési afinity v tomto grafu. Graf je konstrukčně symetrický, protože jádro je symetrické. Je snadné vidět, že z n-tice (X,k) lze vytvořit reverzibilní Markovův řetězec. Tato technika je společná pro řadu oborů a je známá jako graf Laplacian.

Například graf K. = (X,E) lze zkonstruovat pomocí Gaussova jádra.

Ve výše uvedené rovnici to označuje je nejbližší soused . Správně, Geodetické vzdálenost by měla být použita ke skutečnému měření vzdáleností na potrubí. Protože přesná struktura potrubí není k dispozici, je pro nejbližší sousedy geodetická vzdálenost aproximována euklidovskou vzdáleností. Volba moduluje naši představu o blízkosti v tom smyslu, že pokud pak a pokud pak . První znamená, že došlo k velmi malé difúzi, zatímco druhá znamená, že proces difúze je téměř dokončen. Různé strategie na výběr najdete v.[38]

Aby věrně reprezentoval Markovovu matici, musí být normalizována odpovídajícím stupeň matice :

nyní představuje markovský řetězec. je pravděpodobnost přechodu z na v jednom časovém kroku. Podobně pravděpodobnost přechodu z na v t časové kroky jsou dány . Tady je matice vynásobí sám t krát.

Markovova matice představuje určitou představu o místní geometrii datové sady X. Hlavní rozdíl mezi difuzními mapami a analýza hlavních komponent je to, že v difúzních mapách jsou uvažovány pouze místní rysy dat, na rozdíl od přijímání korelací celého souboru dat.

definuje náhodnou procházku datovou sadou, což znamená, že jádro zachycuje určitou lokální geometrii datové sady. Markovův řetězec definuje rychlý a pomalý směr šíření hodnotami jádra. Jak se procházka šíří vpřed v čase, informace o místní geometrii se agregují stejným způsobem jako místní přechody (definované diferenciálními rovnicemi) dynamického systému.[37] Metafora difúze vychází z definice rodinné difuzní vzdálenosti {}

Pro pevné t, definuje vzdálenost mezi libovolnými dvěma body datové sady na základě připojení cesty: hodnota bude menší, čím více cest se připojí X na y a naopak. Protože množství zahrnuje součet všech cest délky t, je mnohem odolnější vůči šumu v datech než geodetická vzdálenost. bere v úvahu veškerý vztah mezi body xay při výpočtu vzdálenosti a slouží jako lepší představa blízkosti než jen Euklidovská vzdálenost nebo dokonce geodetická vzdálenost.

Místní multidimenzionální škálování

Provádí se místní multidimenzionální škálování vícerozměrné škálování v místních regionech a poté použije konvexní optimalizaci, aby všechny kusy zapadly dohromady.[39]

Nelineární PCA

Používá nelineární PCA (NLPCA) zpětná propagace trénovat vícevrstvý perceptron (MLP), aby se vešel do potrubí.[40] Na rozdíl od typického školení MLP, které aktualizuje pouze váhy, NLPCA aktualizuje jak váhy, tak vstupy. To znamená, že s váhami i vstupy se zachází jako s latentními hodnotami. Po tréninku jsou latentními vstupy nízkodimenzionální reprezentace pozorovaných vektorů a mapy MLP z této nízkodimenzionální reprezentace do vysokodimenzionálního pozorovacího prostoru.

Vysokorozměrné škálování založené na datech

Data-Driven High Dimensional Scaling (DD-HDS)[41] úzce souvisí s Sammonovo mapování a křivočará analýza komponent kromě toho, že (1) současně penalizuje falešná sousedství a slzy zaměřením na malé vzdálenosti v původním i výstupním prostoru a že (2) odpovídá koncentrace opatření přizpůsobením funkce vážení rozložení vzdálenosti.

Tvarování potrubí

Sochařství potrubí[42] používá odstupňovaná optimalizace najít vložení. Stejně jako ostatní algoritmy počítá k- nejbližší sousedé a snaží se hledat vložení, které zachovává vztahy v místních čtvrtích. Pomalu rozšiřuje rozptyl z vyšších dimenzí a současně upravuje body v nižších dimenzích, aby tyto vztahy zachoval. Pokud je rychlost změny měřítka malá, může najít velmi přesné vkládání. Může se pochlubit vyšší empirickou přesností než jiné algoritmy s několika problémy. Lze jej také použít k upřesnění výsledků z jiných algoritmů pro různá učení. Snaží se rozvinout několik variet, pokud však není použita velmi pomalá rychlost škálování. Nemá žádný model.

RankVisu

RankVisu[43] je navržen tak, aby zachoval spíše hodnost sousedství než vzdálenost. RankVisu je obzvláště užitečné při obtížných úkolech (kdy nelze uspokojivě dosáhnout zachování vzdálenosti). Hodnost sousedství je ve skutečnosti méně informativní než vzdálenost (řady lze odvodit ze vzdáleností, ale vzdálenosti nelze odvodit z řad) a její zachování je tedy snazší.

Topologicky omezené izometrické vkládání

Topologicky omezené izometrické vkládání (TCIE)[44] is an algorithm based on approximating geodesic distances after filtering geodesics inconsistent with the Euclidean metric. Aimed at correcting the distortions caused when Isomap is used to map intrinsically non-convex data, TCIE uses weight least-squares MDS in order to obtain a more accurate mapping. The TCIE algorithm first detects possible boundary points in the data, and during computation of the geodesic length marks inconsistent geodesics, to be given a small weight in the weighted Majorizace stresu that follows.

Uniform manifold approximation and projection

Uniform manifold approximation and projection (UMAP) is a nonlinear dimensionality reduction technique.[45] Visually, it is similar to t-SNE, but it assumes that the data is uniformly distributed on a místně připojen Riemannovo potrubí a to Riemannova metrika is locally constant or approximately locally constant.[46]

Methods based on proximity matrices

A method based on proximity matrices is one where the data is presented to the algorithm in the form of a similarity matrix nebo a matice vzdálenosti. These methods all fall under the broader class of metric multidimensional scaling. The variations tend to be differences in how the proximity data is computed; například, Isomap, locally linear embeddings, maximum variance unfolding, a Sammon mapping (which is not in fact a mapping) are examples of metric multidimensional scaling methods.

Viz také

Reference

  1. ^ Lawrence, Neil D (2012). "A unifying probabilistic perspective for spectral dimensionality reduction: insights and new models". Journal of Machine Learning Research. 13 (May): 1609–1638. arXiv:1010.4830. Bibcode:2010arXiv1010.4830L.
  2. ^ John A. Lee, Michel Verleysen, Nonlinear Dimensionality Reduction, Springer, 2007.
  3. ^ Gashler, M. and Martinez, T., Temporal Nonlinear Dimensionality Reduction, V Proceedings of the International Joint Conference on Neural Networks IJCNN'11, pp. 1959–1966, 2011
  4. ^ The illustration is prepared using free software: E.M. Mirkes, Principal Component Analysis and Self-Organizing Maps: applet. University of Leicester, 2011
  5. ^ Yin, Hujun; Learning Nonlinear Principal Manifolds by Self-Organising Maps, in A.N. Gorban, B. Kégl, D.C. Wunsch, and A. Zinovyev (Eds.), Hlavní rozdělovače pro vizualizaci dat a zmenšení dimenze, Lecture Notes in Computer Science and Engineering (LNCSE), vol. 58, Berlin, Germany: Springer, 2007, Ch. 3, pp. 68-95. ISBN  978-3-540-73749-0
  6. ^ B. Schölkopf, A. Smola, K.-R. Müller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neurální výpočet 10(5):1299-1319, 1998, MIT Stiskněte Cambridge, MA, USA, doi:10.1162/089976698300017467
  7. ^ Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004. doi:10.1145/1015330.1015417
  8. ^ Gorban, A. N.; Zinovyev, A. (2010). "Principal manifolds and graphs in practice: from molecular biology to dynamical systems". International Journal of Neural Systems. 20 (3): 219–232. arXiv:1001.1122. doi:10.1142/S0129065710002383. PMID  20556849. S2CID  2170982.
  9. ^ A. Zinovyev, ViDaExpert - Multidimensional Data Visualization Tool (free for non-commercial use). Institut Curie, Paříž.
  10. ^ A. Zinovyev, ViDaExpert overview, IHES (Institut des Hautes Études Scientifiques ), Bures-Sur-Yvette, Île-de-France.
  11. ^ Hastie, T. (November 1984). Principal Curves and Surfaces (PDF) (Disertační práce). Stanford Linear Accelerator Center, Stanford University.
  12. ^ Gorban, A. N.; Kégl, B.; Wunsch, D. C.; Zinovyev, A., eds. (2007). Principal Manifolds for Data Visualisation and Dimension Reduction. Lecture Notes in Computer Science and Engineering (LNCSE). Sv. 58. Berlin – Heidelberg – New York: Springer. ISBN  978-3-540-73749-0.
  13. ^ Belkin, Mikhail; Niyogi, Partha (2001). "Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering". Advances in Neural Information Processing Systems. MIT Stiskněte. 14: 586–691.
  14. ^ A b Belkin, Mikhail (August 2003). Problems of Learning on Manifolds (Disertační práce). Department of Mathematics, The University of Chicago. Matlab code for Laplacian Eigenmaps can be found in algorithms at Ohio-state.edu
  15. ^ Bengio, Yoshua; et al. (2004). "Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering" (PDF). Advances in Neural Information Processing Systems.
  16. ^ Tenenbaum, J.; Freeman, W. (2000). "Separating style and content with bilinear models". Neurální výpočet. 12 (6): 1247–1283. doi:10.1162/089976600300015349. PMID  10935711. S2CID  9492646.
  17. ^ Lewandowski, M.; Martinez-del Rincon, J.; Makris, D.; Nebel, J.-C. (2010). "Temporal extension of laplacian eigenmaps for unsupervised dimensionality reduction of time series". Proceedings of the International Conference on Pattern Recognition (ICPR).
  18. ^ A b Lewandowski, M.; Makris, D.; Velastin, S. A.; Nebel, J.-C. (2014). "Structural Laplacian Eigenmaps for Modeling Sets of Multivariate Sequences". IEEE Transactions on Cybernetics. 44 (6): 936–949. doi:10.1109/TCYB.2013.2277664. PMID  24144690. S2CID  110014.
  19. ^ Martinez-del-Rincon, J.; Lewandowski, M.; Nebel, J.-C.; Makris, D. (2014). "Generalized Laplacian Eigenmaps for Modeling and Tracking Human Motions". IEEE Transactions on Cybernetics. 44 (9): 1646–1660. doi:10.1109/TCYB.2013.2291497. PMID  25137692. S2CID  22681962.
  20. ^ J. B. Tenenbaum, V. de Silva, J. C. Langford, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290, (2000), 2319–2323.
  21. ^ S. T. Roweis and L. K. Saul, Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science Vol 290, 22 December 2000, 2323–2326.
  22. ^ Donoho, D.; Grimes, C. (2003). "Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data". Proc Natl Acad Sci U S A. 100 (10): 5591–5596. doi:10.1073/pnas.1031596100. PMC  156245. PMID  16576753.
  23. ^ Z. Zhang and J. Wang, "MLLE: Modified Locally Linear Embedding Using Multiple Weights" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.382
  24. ^ Sidhu, Gagan (2019). "Locally Linear Embedding and fMRI feature selection in psychiatric classification". IEEE Journal of Translational Engineering in Health and Medicine. 7: 1–11. arXiv:1908.06319. doi:10.1109/JTEHM.2019.2936348. PMC  6726465. PMID  31497410. S2CID  201832756.
  25. ^ Zhang, Zhenyue; Hongyuan Zha (2005). "Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment". SIAM Journal on Scientific Computing. 26 (1): 313–338. CiteSeerX  10.1.1.211.9957. doi:10.1137/s1064827502419154.
  26. ^ Bengio, Yoshua; Monperrus, Martin; Larochelle, Hugo (October 2006). "Nonlocal Estimation of Manifold Structure" (PDF). Neurální výpočet. 18 (10): 2509–2528. doi:10.1162/neco.2006.18.10.2509. ISSN  0899-7667. PMID  16907635. S2CID  1416595.
  27. ^ N. Lawrence, Probabilistic Non-linear Principal Component Analysis with Gaussian Process Latent Variable Models, Journal of Machine Learning Research 6(Nov):1783–1816, 2005.
  28. ^ M. Ding, G. Fan, Multilayer Joint Gait-Pose Manifolds for Human Gait Motion Modeling, IEEE Transactions on Cybernetics, Volume: 45, Issue: 11, Nov 2015.
  29. ^ van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). "Visualizing High-Dimensional Data Using t-SNE" (PDF). Journal of Machine Learning Research. 9: 2579–2605.
  30. ^ James X. Li, Visualizing high-dimensional data with relational perspective map, Information Visualization (2004) 3, 49–59
  31. ^ Taylor, D.; Klimm, F.; Harrington, H. A.; Kramár, M.; Mischaikow, K.; Porter, M. A.; Mucha, P. J. (2015). "Topological data analysis of contagion maps for examining spreading processes on networks". Příroda komunikace. 6: 7723. doi:10.1038/ncomms8723. PMC  4566922. PMID  26194875.
  32. ^ A b Demartines, P.; Hérault, J. (1997). "Curvilinear Component Analysis: A Self-Organizing Neural Network for Nonlinear Mapping of Data Sets" (PDF). Transakce IEEE na neuronových sítích. 8 (1): 148–154. doi:10.1109/72.554199. PMID  18255618.
  33. ^ Sun, Jigang; Crowe, Malcolm; Fyfe, Colin (2010). "Curvilinear component analysis and Bregman divergences" (PDF). European Symposium on Artificial Neural Networks (Esann). d-side publications. pp. 81–86.
  34. ^ Christian Walder and Bernhard Schölkopf, Diffeomorphic Dimensionality Reduction, Advances in Neural Information Processing Systems 22, 2009, pp. 1713–1720, MIT Press
  35. ^ Wang, Chang; Mahadevan, Sridhar (July 2008). Manifold Alignment using Procrustes Analysis (PDF). The 25th International Conference on Machine Learning. pp. 1120–1127.
  36. ^ Lafon, Stephane (May 2004). Diffusion Maps and Geometric Harmonics (Disertační práce). univerzita Yale.
  37. ^ A b Coifman, Ronald R.; Lafon, Stephane (19 June 2006). "Diffusion Maps". Věda.
  38. ^ Bah, B. (2008). Diffusion Maps: Applications and Analysis (Diplomová práce). University of Oxford.
  39. ^ Venna, J.; Kaski, S. (2006). "Local multidimensional scaling". Neuronové sítě. 19 (6–7): 889–899. doi:10.1016/j.neunet.2006.05.014. PMID  16787737.
  40. ^ Scholz, M.; Kaplan, F.; Guy, C. L.; Kopka, J.; Selbig, J. (2005). "Non-linear PCA: a missing data approach". Bioinformatika. Oxford University Press. 21 (20): 3887–3895. doi:10.1093/bioinformatics/bti634. PMID  16109748.
  41. ^ S. Lespinats, M. Verleysen, A. Giron, B. Fertil, DD-HDS: a tool for visualization and exploration of high-dimensional data, IEEE Transactions on Neural Networks 18 (5) (2007) 1265–1279.
  42. ^ Gashler, M. and Ventura, D. and Martinez, T., Iterative Non-linear Dimensionality Reduction with Manifold Sculpting, In Platt, J.C. and Koller, D. and Singer, Y. and Roweis, S., editor, Advances in Neural Information Processing Systems 20, pp. 513–520, MIT Press, Cambridge, MA, 2008
  43. ^ Lespinats S., Fertil B., Villemain P. and Herault J., Rankvisu: Mapping from the neighbourhood network, Neurocomputing, vol. 72 (13–15), pp. 2964–2978, 2009.
  44. ^ Rosman G., Bronstein M. M., Bronstein A. M. and Kimmel R., Nonlinear Dimensionality Reduction by Topologically Constrained Isometric Embedding, International Journal of Computer Vision, Volume 89, Number 1, 56–68, 2010
  45. ^ McInnes, Leland; Healy, John; Melville, James (2018-12-07). "Uniform manifold approximation and projection for dimension reduction". arXiv:1802.03426.
  46. ^ "UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction — umap 0.3 documentation". umap-learn.readthedocs.io. Citováno 2019-05-04.

externí odkazy