Aproximace matice nízkého řádu - Low-rank matrix approximations

Aproximace matice nízkého řádu jsou základními nástroji při aplikaci metody jádra k učení ve velkém měřítku problémy.^[1]

Metody jádra (například podporovat vektorové stroje nebo Gaussovské procesy^[2]) promítají datové body do trojrozměrného nebo nekonečného prostor funkcí a najděte optimální dělící hyperplán. V metoda jádra data jsou reprezentována v a matice jádra (nebo, Gramová matice ). Mnoho algoritmů může vyřešit strojové učení problémy s používáním matice jádra. Hlavní problém metoda jádra je jeho vysoká výpočetní náklady spojený s jádrové matice. Cena je minimálně kvadratická v počtu tréninkových datových bodů, ale většina metody jádra zahrnout výpočet inverze matice nebo rozklad vlastních čísel a cena se stane kubickým v počtu tréninkových dat. Velké tréninkové soupravy způsobují velké náklady na skladování a výpočet. Přes metody nízkého stupně rozkladu (Choleský rozklad ) snížit tyto náklady, nadále vyžadují výpočet matice jádra. Jedním z přístupů k řešení tohoto problému jsou aproximace matice nízkého řádu. Nejoblíbenější příklady z nich jsou Nyströmova metoda a náhodné funkce. Oba byly úspěšně použity na efektivní učení jádra.

Nyströmova aproximace

Metody jádra se stanou neproveditelnými, když počet bodů ${ displaystyle n}$ je tak velká, že jádrová matice ${ displaystyle { hat {K}}}$ nelze uložit do paměti.

Li ${ displaystyle n}$ je počet příkladů školení, náklady na skladování a výpočet požadováno k nalezení řešení problému pomocí obecného metoda jádra je ${ displaystyle O (n ^ {2})}$ a ${ displaystyle O (n ^ {3})}$ resp. Nyströmova aproximace může umožnit významné zrychlení výpočtů.^[2]^[3] Tohoto zrychlení je dosaženo použitím namísto matice jádra jeho aproximace ${ displaystyle { tilde {K}}}$ z hodnost ${ displaystyle q}$ . Výhodou metody je, že není nutné počítat nebo ukládat celek matice jádra, ale pouze jeho blok velikosti ${ displaystyle q krát n}$ .

Snižuje požadavky na úložiště a složitost na ${ displaystyle O (nq)}$ a ${ displaystyle O (nq ^ {2})}$ resp.

Věta o aproximaci jádra

${ displaystyle { hat {K}}}$ je matice jádra pro některé metoda jádra. Zvažte první ${ displaystyle q$ body v tréninkové sadě. Pak existuje matice ${ displaystyle { tilde {K}}}$ z hodnost ${ displaystyle q}$ :

${ displaystyle { tilde {K}} = { hat {K}} _ {n, q} { hat {K}} _ {q} ^ {- 1} { hat {K}} _ {n , q} ^ { text {T}}}$ , kde

${ displaystyle ({ hat {K}} _ {q}) _ {i, j} = K (x_ {i}, x_ {j}), i, j = 1, tečky, q}$ ,

${ displaystyle { hat {K}} _ {q}}$ je invertibilní matice

a

${ displaystyle ({ hat {K}} _ {n, q}) _ {i, j} = K (x_ {i}, x_ {j}), i = 1, tečky, n { text { a}} j = 1, dots, q.}$

Důkaz

Aplikace rozkladu singulární hodnoty

Přihlašování rozklad singulární hodnoty (SVD) do matice ${ displaystyle A}$ s rozměry ${ Displaystyle p krát m}$ vyrábí a singulární systém skládající se z singulární hodnoty ${ displaystyle { sigma _ {j} } _ {j = 1} ^ {k}, { text {}} ( sigma _ {j}> 0 { text {}} forall j = 1 , tečky, k),}$ vektory ${ displaystyle {v_ {j} } _ {j = 1} ^ {m} in mathbb {C} ^ {m}}$ a ${ displaystyle {u_ {j} } _ {j = 1} ^ {p} in mathbb {C} ^ {p}}$ tak, že tvoří ortonormální základy ${ displaystyle mathbb {C} ^ {m}}$ a ${ displaystyle mathbb {C} ^ {p}}$ respektive:

${ displaystyle { begin {cases} A ^ { text {T}} Av_ {j} = sigma _ {j} v_ {j}, { text {}} j = 1, tečky, k, A ^ { text {T}} Av_ {j} = 0, { text {}} j = k + 1, dots, m, AA ^ { text {T}} u_ {j} = sigma _ {j} u_ {j}, { text {}} j = 1, dots, k, AA ^ { text {T}} u_ {j} = 0, { text {}} j = k + 1, dots, p. end {cases}}}$

Li ${ displaystyle U}$ a ${ displaystyle V}$ jsou matice s ${ displaystyle u}$ A ${ displaystyle v}$ Je ve sloupcích a ${ displaystyle Sigma}$ je úhlopříčka ${ Displaystyle p krát m}$ matice s singulární hodnoty ${ displaystyle sigma _ {i}}$ na prvním ${ displaystyle k}$ -záznamy na diagonále (všechny ostatní prvky matice jsou nuly):

${ displaystyle { begin {cases} Av_ {j} = { sqrt { sigma _ {j}}} u_ {j}, { text {}} j = 1, tečky, k, Av_ { j} = 0, { text {}} j = k + 1, tečky, m, A ^ { text {T}} u_ {j} = { sqrt { sigma _ {j}}} v_ {j}, { text {}} j = 1, tečky, k, A ^ { text {T}} u_ {j} = 0, { text {}} j = k + 1, dots, p, end {případy}}}$

pak matice ${ displaystyle A}$ lze přepsat jako:^[4]

${ displaystyle A = U Sigma ^ {1/2} V ^ { text {T}}}$ .

Další důkaz

${ displaystyle { hat {X}}}$ je ${ displaystyle n krát D}$ datová matice
${ displaystyle { hat {K}} = { hat {X}} { hat {X}} ^ { text {T}}}$
${ displaystyle { hat {C}} = { hat {X}} ^ { text {T}} { hat {X}}}$

Použití rozkladu singulární hodnoty na tyto matice:

${ displaystyle { hat {X}} = { hat {U}} { hat { Sigma}} ^ {1/2} { hat {V}} ^ { text {T}}, { text {}} { hat {K}} = { hat {U}} { hat { Sigma}} { hat {U}} ^ {T}, { text {}} { hat {C }} = { hat {V}} { hat { Sigma}} { hat {V}} ^ { text {T}}.}$

${ displaystyle { hat {X}} _ {q}}$ je ${ displaystyle q krát D}$ -dimenzionální matice skládající se z první ${ displaystyle q}$ řádky matice ${ displaystyle { hat {X}}}$
${ displaystyle { hat {K}} _ {q} = { hat {X}} _ {q} { hat {X}} _ {q} ^ { text {T}}}$
${ displaystyle { hat {C}} = { hat {X}} ^ { text {T}} { hat {X}}}$

Použití rozkladu singulární hodnoty na tyto matice:

${ displaystyle { hat {X}} _ {q} = { hat {U}} _ {q} { hat { Sigma}} _ {q} ^ {1/2} { hat {V} } _ {q} ^ { text {T}}, { text {}} { hat {K}} _ {q} = { hat {U}} _ {q} { hat { Sigma} } _ {q} { hat {U}} _ {q} ^ {T}, { text {}} { hat {C}} _ {q} = { hat {V}} _ {q} { hat { Sigma}} _ {q} { hat {V}} _ {q} ^ { text {T}}.}$

Od té doby ${ displaystyle { hat {U}}, { text {}} { hat {V}}, { hat {U}} _ {q} { text {and}} { hat {V}} _ {q}}$ jsou ortogonální matice,

${ displaystyle { hat {U}} = { hat {X}} { hat {V}} { hat { Sigma}} ^ {- 1/2}, { text {}} { hat {V}} _ {q} = { hat {X}} _ {q} ^ { text {T}} { hat {U}} _ {q} { hat { Sigma}} _ {q } ^ {- 1/2}.}$

Výměna ${ displaystyle { hat {V}}, { text {}} { hat { Sigma}} { text {by}} { hat {V}} _ {q} { text {and}} { hat { Sigma}} _ {q}}$ , aproximace pro ${ displaystyle { hat {U}}}$ lze získat:

${ displaystyle { tilde {U}} = { hat {X}} { hat {X}} _ {q} ^ { text {T}} { hat {U}} _ {q} { klobouk { Sigma}} _ {q} ^ {- 1}}$ ( ${ displaystyle { tilde {U}}}$ není nutně ortogonální matice ).

Definování však ${ displaystyle { tilde {K}} = { tilde {U}} { hat { Sigma}} _ {q} { tilde {U}} ^ { text {T}}}$ , lze jej vypočítat dalším způsobem:

${ displaystyle { begin {aligned} { tilde {K}} = { tilde {U}} { hat { Sigma}} _ {q} { tilde {U}} ^ { text {T} } = { hat {X}} { hat {X}} _ {q} ^ { text {T}} { hat {U}} _ {q} { hat { Sigma}} _ {q } ^ {- 1} { hat { Sigma}} _ {q} ({ hat {X}} { hat {X}} _ {q} ^ { text {T}} { hat {U }} _ {q} { hat { Sigma}} _ {q} ^ {- 1}) ^ { text {T}} = { hat {X}} { hat {X}} _ {q} ^ { text {T}} { big {} { hat {U}} _ {q} ({ hat { Sigma}} _ {q} ^ {- 1}) ^ { text {T}} { hat {U}} _ {q} ^ { text {T}} { big }} ({ hat {X}} { hat {X}} _ {q} ^ { text {T}}) ^ { text {T}} konec {zarovnáno}}}$

Podle charakterizace pro ortogonální matice ${ displaystyle { hat {U}} _ {q}}$ : rovnost ${ displaystyle ({ hat {U}} _ {q}) ^ { text {T}} = ({ hat {U}} _ {q}) ^ {- 1}}$ drží. Poté pomocí vzorce pro inverzní funkci k násobení matic ${ displaystyle (AB) ^ {- 1} = B ^ {- 1} A ^ {- 1}}$ pro invertibilní matice ${ displaystyle A}$ a ${ displaystyle B}$ , výraz ve složených závorkách lze přepsat jako:

${ displaystyle { begin {aligned} { hat {U}} _ {q} ({ hat { Sigma}} _ {q} ^ {- 1}) ^ { text {T}} { hat {U}} _ {q} ^ { text {T}} = ({ hat {U}} _ {q} { hat { Sigma}} _ {q} ^ { text {T}} { hat {U}} _ {q} ^ { text {T}}) ^ {- 1} = ({ hat {K}} _ {q}) ^ {- 1} end {zarovnáno}}}$ .

Pak výraz pro ${ displaystyle { tilde {K}}}$ :

${ displaystyle { begin {aligned} { tilde {K}} = ({ hat {X}} { hat {X}} _ {q} ^ { text {T}}) { hat {K }} _ {q} ^ {- 1} ({ hat {X}} { hat {X}} _ {q} ^ { text {T}}) ^ { text {T}} konec {zarovnáno}}}$ .

Definování ${ displaystyle { hat {K}} _ {n, q} = { hat {X}} { hat {X}} _ {q} ^ { text {T}}}$ , důkaz je hotový.

Obecná věta o aproximaci jádra pro mapu funkcí

Pro mapu funkcí ${ displaystyle Phi: { mathcal {X}} rightarrow { mathcal {F}}}$ s přidruženými jádro ${ displaystyle K (x, x ') = langle Phi (x), Phi (x') rangle _ { mathcal {F}}}$ : rovnost ${ displaystyle { hat {K}} = { hat {K}} _ {n, q} { hat {K}} _ {q} ^ {- 1} { hat {K}} _ {n , q} ^ { text {T}}}$ také následuje nahrazením ${ displaystyle { hat {X}}}$ provozovatelem ${ displaystyle { hat { Phi}}: { mathcal {F}} rightarrow mathbb {R} ^ {n}}$ takhle ${ displaystyle langle { hat { Phi}} w rangle _ {i} = langle Phi (x_ {i}), w rangle _ { mathcal {F}}}$ , ${ displaystyle { text {}} i = 1, tečky, n}$ , ${ displaystyle w in { mathcal {F}}}$ , a ${ displaystyle { hat {X}} _ {q}}$ provozovatelem ${ displaystyle { hat { Phi}} _ {q}: { mathcal {F}} rightarrow mathbb {R} ^ {q}}$ takhle ${ displaystyle langle { hat { Phi}} w rangle _ {i} = langle Phi (x_ {i}), w rangle _ { mathcal {F}}}$ , ${ displaystyle { text {}} i = 1, tečky, q}$ , ${ displaystyle w in { mathcal {F}}}$ . Jednoduchá kontrola opět ukazuje, že mapa funkcí je nutná pouze v důkazu, zatímco konečný výsledek závisí pouze na výpočtu funkce jádra.

Aplikace pro regularizované nejmenší čtverce

Ve vektorové a jádrové notaci je problém Regularizované nejmenší čtverce lze přepsat jako:

{ displaystyle min _ {c in mathbb {R} ^ {n}} { frac {1} {n}} | { hat {Y}} - { hat {K}} c | _ { mathbb {R} ^ {n}} ^ {2} + lambda langle c, { hat {K}} c rangle _ { mathbb {R} ^ {n}}}

.

Při výpočtu gradientu a nastavení na 0 lze získat minimum:

{ displaystyle { begin {aligned} - { frac {1} {n}} { hat {K}} ({ hat {Y}} - { hat {K}} c) + lambda { čepice {K}} c = 0 Rightarrow { hat {K}} ({ hat {K}} + lambda nI) c = { hat {K}} { hat {Y}} Rightarrow c = ({ hat {K}} + lambda nI) ^ {- 1} { hat {Y}}, { text {where}} c in mathbb {R} ^ {n} konec {zarovnáno}}}

Inverzní matice ${ displaystyle ({ hat {K}} + lambda nI) ^ {- 1}}$ lze vypočítat pomocí Identita matice Woodburyho:

${ displaystyle { begin {aligned} ({ hat {K}} + lambda nI) ^ {- 1} = { cfrac {1} { lambda n}} { bigg (} { cfrac {1 } { lambda n}} { hat {K}} + I { bigg)} ^ {- 1} = { cfrac {1} { lambda n}} { bigg (} I + { hat {K}} _ {n, q} ({ lambda n} { hat {K}} _ {q}) ^ {- 1} { hat {K}} _ {n, q} ^ { text {T}} { bigg)} ^ {- 1} = { cfrac {1} { lambda n}} { Big (} I - { hat {K}} _ {n, q} ( lambda n { hat {K}} _ {q} + { hat {K}} _ {n, q} ^ { text {T}} { hat {K}} _ {n, q}) ^ {- 1} { hat {K}} _ {n, q} ^ { text {T}} { Big)} konec {zarovnáno}}}$

Má požadované požadavky na úložiště a složitost.

Randomizovaná mapa funkcí aproximace

Nechat ${ displaystyle mathbf {x}, mathbf {x '} v mathbb {R} ^ {d}}$ - vzorky údajů, ${ displaystyle z: mathbb {R} ^ {d} rightarrow mathbb {R} ^ {D}}$ - náhodně mapa funkcí (mapuje jeden vektor na vektor s vyšší dimenzí), takže vnitřní součin mezi dvojicí transformovaných bodů se blíží jejich jádro hodnocení:

${ displaystyle K ( mathbf {x}, mathbf {x '}) = langle Phi ( mathbf {x}), Phi ( mathbf {x'}) rangle cca z ( mathbf { x}) ^ { text {T}} z ( mathbf {x '})}$ ,

kde ${ displaystyle Phi}$ je mapování vložené do RBF jádro.

Od té doby ${ displaystyle z}$ je nízkodimenzionální, lze vstup snadno transformovat pomocí ${ displaystyle z}$ , poté lze použít různé metody lineárního učení k aproximaci odpovědi odpovídajícího nelineárního jádra. K výpočtu aproximací jader RBF existují různé randomizované mapy funkcí. Například, Náhodné Fourierovy funkce a funkce náhodného binování.

Náhodné Fourierovy funkce

Náhodné Fourierovy funkce mapa vytváří a Monte Carlo přiblížení k mapě prvků. Metoda Monte Carlo je považována za randomizovanou. Tyto náhodné funkce sestává ze sinusoidů ${ displaystyle cos (w ^ { text {T}} mathbf {x} + b)}$ náhodně vylosováno z Fourierova transformace z jádro být aproximován, kde ${ displaystyle w in mathbb {R} ^ {d}}$ a ${ displaystyle b in mathbb {R}}$ jsou náhodné proměnné. Čára je vybrána náhodně, pak se na ní datové body promítnou pomocí mapování. Výsledný skalár prochází sinusoidem. Produkt transformovaných bodů bude aproximovat jádro invariantní k posunu. Protože mapa je hladká, náhodné Fourierovy rysy dobře fungují na interpolačních úkolech.

Funkce náhodného binování

Funkce náhodného binování mapují oddíly vstupního prostoru pomocí náhodně posunutých mřížek v náhodně vybraných rozlišeních a přiřadí vstupnímu bodu binární bitový řetězec, který odpovídá košům, do kterých spadá. Mřížky jsou konstruovány tak, aby pravděpodobnost, že dva body ${ displaystyle mathbf {x}, mathbf {x '} v mathbb {R} ^ {d}}$ jsou přiřazeny ke stejnému zásobníku, je úměrný ${ displaystyle K ( mathbf {x}, mathbf {x '})}$ . Vnitřní součin mezi dvojicí transformovaných bodů je úměrný počtu spojování dvou bodů dohromady, a je tedy objektivním odhadem ${ displaystyle K ( mathbf {x}, mathbf {x '})}$ . Protože toto mapování není plynulé a využívá blízkost mezi vstupními body, funkce náhodného binování fungují dobře pro přibližování jader, které závisí pouze na ${ displaystyle L_ {1}}$ - vzdálenost mezi datovými body.

Porovnání aproximačních metod

Přístupy k rozsáhlému učení jádra (Nyströmova metoda a náhodné funkce) se liší ve skutečnosti, že metoda Nyström používá základové funkce závislé na datech, zatímco v přístupu náhodných funkcí jsou základní funkce vzorkovány z distribuce nezávislé na tréninkových datech. Tento rozdíl vede k vylepšené analýze přístupů k učení jádra založených na metodě Nyström. Když je ve vlastním spektru velké mezery jádro matice, přístupy založené na metodě Nyström mohou dosáhnout lepších výsledků než Náhodné funkce založený přístup.^[5]

Viz také

externí odkazy

Andreas Müller (2012). Aproximace jádra pro efektivní SVM (a další metody extrakce funkcí).

Reference

^ Francis R. Bach a Michael I. Jordan (2005). „Prediktivní nízký stupeň rozkladu pro metody jádra“. ICML.
^ ^A ^b Williams, C.K.I. a Seeger, M. (2001). „Použití metody Nyström k urychlení jaderných strojů“. Pokroky v systémech zpracování neurálních informací.CS1 maint: používá parametr autoři (odkaz)
^ Petros Drineas a Michael W. Mahoney (2005). „K Nyströmově metodě pro přiblížení gramové matice pro vylepšené učení založené na jádře“. Journal of Machine Learning Research 6, str. 2153–2175.
^ C. Eckart, G. Young, Aproximace jedné matice druhou s nižší hodností. Psychometrika, svazek 1, 1936, strany 211–8. doi:10.1007 / BF02288367
^ Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin a Zhi-Hua Zhou (2012). „Nyströmova metoda vs. náhodné Fourierovy rysy: Teoretické a empirické srovnání“. Pokroky v systémech zpracování neurálních informací 25 (NIPS).

[1] Francis R. Bach a Michael I. Jordan (2005). „Prediktivní nízký stupeň rozkladu pro metody jádra“. ICML.

[:2-2] A ^b Williams, C.K.I. a Seeger, M. (2001). „Použití metody Nyström k urychlení jaderných strojů“. Pokroky v systémech zpracování neurálních informací.CS1 maint: používá parametr autoři (odkaz)

[:4-3] Petros Drineas a Michael W. Mahoney (2005). „K Nyströmově metodě pro přiblížení gramové matice pro vylepšené učení založené na jádře“. Journal of Machine Learning Research 6, str. 2153–2175.

[EYM-thm-4] C. Eckart, G. Young, Aproximace jedné matice druhou s nižší hodností. Psychometrika, svazek 1, 1936, strany 211–8. doi:10.1007 / BF02288367

[:3-5] Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin a Zhi-Hua Zhou (2012). „Nyströmova metoda vs. náhodné Fourierovy rysy: Teoretické a empirické srovnání“. Pokroky v systémech zpracování neurálních informací 25 (NIPS).

[1]

[2]

[3]

[4]

[5]