Analýza komponent sousedství - Neighbourhood components analysis

Analýza komponent sousedství je učení pod dohledem metoda pro klasifikace vícerozměrný data do různých tříd podle daného vzdálenost metrická přes data. Funkčně slouží stejným účelům jako Algoritmus K-nejbližších sousedů, a přímo využívá související pojem nazývaný stochastické nejbližší sousedy.

Definice

Analýza komponent sousedství si klade za cíl „naučit se“ metriku vzdálenosti vyhledáním lineární transformace vstupních dat tak, aby byl v transformovaném prostoru maximalizován průměrný výkon klasifikace ponechat-ven-ven (LOO). Klíčovým vhledem do algoritmu je matice ${displaystyle A}$ odpovídající transformaci lze nalézt definováním diferencovatelné objektivní funkce pro ${displaystyle A}$ , následované použitím iteračního řešiče, jako je konjugovaný gradient. Jednou z výhod tohoto algoritmu je, že počet tříd ${displaystyle k}$ lze určit jako funkci ${displaystyle A}$ , až do skalární konstanty. Toto použití algoritmu proto řeší problém výběr modelu.

Vysvětlení

Aby bylo možné definovat ${displaystyle A}$ , definujeme objektivní funkci popisující přesnost klasifikace v transformovaném prostoru a pokusíme se ji určit ${displaystyle A ^ {*}}$ tak, aby byla tato objektivní funkce maximalizována.

${displaystyle A ^ {*} = {mbox {argmax}} _ {A} f (A)}$

Klasifikace Leave-one-out (LOO)

Zvažte předpovídání označení třídy jednoho datového bodu na základě konsensu jeho ${displaystyle k}$ - nejbližší sousedé s danou metrikou vzdálenosti. Toto je známé jako nechte-ven-ven klasifikace. Sada nejbližších sousedů ${displaystyle C_ {i}}$ může být zcela odlišný po průchodu všech bodů lineární transformací. Konkrétně sada sousedů pro bod může projít diskrétními změnami v reakci na plynulé změny v prvcích ${displaystyle A}$ , což znamená, že jakákoli objektivní funkce ${displaystyle f (cdot)}$ na základě sousedů bodu bude po částech konstantní, a tedy nediferencovatelné.

Řešení

Tuto obtíž můžeme vyřešit pomocí přístupu inspirovaného stochastický gradient. Spíše než zvažovat ${displaystyle k}$ - nejbližší sousedé v každém transformovaném bodě klasifikace LOO, budeme považovat celou transformovanou datovou sadu za stochastické nejbližší sousedy. Definujeme je pomocí a funkce softmax na druhou Euklidovská vzdálenost mezi daným bodem klasifikace LOO a každým dalším bodem v transformovaném prostoru:

${displaystyle p_ {ij} = {egin {cases} {frac {e ^ {- || Ax_ {i} -Ax_ {j} || ^ {2}}} {sum _ {k} e ^ {- || Ax_ {i} -Ax_ {k} || ^ {2}}}}, & {mbox {if}} jeq i 0, & {mbox {if}} j = iend {cases}}}$

Pravděpodobnost správné klasifikace datového bodu ${displaystyle i}$ je pravděpodobnost klasifikace bodů každého ze sousedů se stejnou třídou ${displaystyle C_ {i}}$ :

${displaystyle p_ {i} = součet _ {jin C_ {i}} p_ {ij} čtyřkolka}$ kde ${displaystyle p_ {ij}}$ je pravděpodobnost klasifikace souseda ${displaystyle j}$ bodu ${displaystyle i}$ .

Definujte objektivní funkci pomocí klasifikace LOO, tentokrát s využitím celé sady dat jako stochastických nejbližších sousedů:

${displaystyle f (A) = součet _ {i} součet _ {jin C_ {i}} p_ {ij} = součet _ {i} p_ {i}}$

Všimněte si, že za stochastických nejbližších sousedů je třída konsensu pro jeden bod ${displaystyle i}$ je očekávaná hodnota třídy bodu v limitu nekonečného počtu vzorků odebraných z distribuce přes jeho sousedy ${displaystyle jin C_ {i}}$ tj.: ${displaystyle P (Třída (X_ {i}) = Třída (X_ {j})) = p_ {ij}}$ . Předpovídaná třída je tedy afinní kombinace tříd každého druhého bodu váženého funkcí softmax pro každý z nich ${displaystyle jin C_ {j}}$ kde ${displaystyle C_ {j}}$ je nyní celá transformovaná datová sada.

Tato volba objektivní funkce je výhodnější, protože je diferencovatelná s ohledem na ${displaystyle A}$ (označ ${displaystyle x_ {ij} = x_ {i} -x_ {j}}$ ):

${displaystyle {frac {částečné f} {částečné A}} = - 2Asum _ {i} součet _ {jin C_ {i}} p_ {ij} vlevo (x_ {ij} x_ {ij} ^ {T} -sum _ {k} p_ {ik} x_ {ik} x_ {ik} ^ {T} ight)}$

${displaystyle = 2Asum _ {i} vlevo (p_ {i} součet _ {k} p_ {ik} x_ {ik} x_ {ik} ^ {T} -sum _ {jin C_ {i}} p_ {ij} x_ {ij} x_ {ij} ^ {T} ight)}$

Získání a spád pro ${displaystyle A}$ znamená, že jej lze najít pomocí iteračního řešení, jako je konjugovaný gradient. Všimněte si, že v praxi se většina nejvnitřnějších podmínek gradientu hodnotí jako nevýznamné příspěvky kvůli rychle se snižujícímu příspěvku vzdálených bodů od bodu zájmu. To znamená, že lze vnitřní část přechodu zkrátit, což má za následek přiměřené výpočetní časy i pro velké datové sady.

Alternativní formulace

„Maximalizace ${displaystyle f (cdot)}$ je ekvivalentní minimalizaci ${displaystyle L_ {1}}$ -vzdálenost mezi předpokládanou distribucí třídy a skutečnou distribucí třídy (tj .: kde ${displaystyle p_ {i}}$ vyvolané ${displaystyle A}$ jsou všechny rovny 1). Přirozenou alternativou je KL-divergence, která indukuje následující objektivní funkci a gradient: “(Goldberger 2005)

${displaystyle g (A) = součet _ {i} log vlevo (součet _ {jin C_ {i}} p_ {ij} ight) = součet _ {i} log (p_ {i})}$

${displaystyle {frac {částečné g} {částečné A}} = 2Asum _ {i} vlevo (součet _ {k} p_ {ik} x_ {ik} x_ {ik} ^ {T} - {frac {součet _ {jin C_ {i}} p_ {ij} x_ {ij} x_ {ij} ^ {T}} {součet _ {jin C_ {i}} p_ {ij}}} hned)}$

V praxi optimalizace ${displaystyle A}$ použití této funkce má tendenci poskytovat podobné výsledky výkonu jako u originálu.

Historie a pozadí

Analýza komponent sousedství byla vyvinuta Jacobem Goldbergerem, Samem Roweisem, Ruslanem Salakhudinovem a Geoffem Hintonem z katedry počítačové vědy na University of Toronto v roce 2004.

Viz také

Reference

J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Analýza komponent sousedství. Pokroky v systémech zpracování neurálních informací. 17, 513-520, 2005.

externí odkazy

Software

The Knihovna MLPACK obsahuje a C ++ implementace
nca (C ++ )
sklearn implementace (Krajta )