Regularizace potrubí - Manifold regularization

Regularizace potrubí může klasifikovat data, když jsou označená data (černé a bílé kruhy) řídká, a to díky využití neoznačených dat (šedé kruhy). Bez mnoha označených datových bodů učení pod dohledem algoritmy se mohou naučit pouze velmi jednoduché hranice rozhodování (horní panel). Rozdílné učení může nakreslit rozhodovací hranici mezi přirozenými třídami neznačených dat za předpokladu, že blízké body pravděpodobně patří do stejné třídy, a tak by se rozhodovací hranice měla vyhýbat oblastem s mnoha neznačenými body. Toto je jedna verze učení pod dohledem.

v strojové učení, Regularizace potrubí je technika pro použití tvaru datové sady k omezení funkcí, které by se na této datové sadě měly naučit. U mnoha problémů se strojovým učením data, která se mají naučit, nepokrývají celý vstupní prostor. Například a systém rozpoznávání obličeje nemusí být nutné klasifikovat žádný možný obrázek, ale pouze podmnožinu obrázků, které obsahují tváře. Technika mnohočetného učení předpokládá, že příslušná podmnožina dat pochází z potrubí, matematická struktura s užitečnými vlastnostmi. Tato technika také předpokládá, že funkce, která se má naučit, je hladký: data s různými štítky pravděpodobně nebudou blízko u sebe, a proto by se funkce označování neměla rychle měnit v oblastech, kde je pravděpodobně mnoho datových bodů. Z tohoto předpokladu může algoritmus různého regularizace pomocí neznačených dat informovat, kde se naučená funkce může rychle měnit a kde není, pomocí rozšíření techniky Tichonovova regularizace. Algoritmy regularizace potrubí se mohou rozšířit učení pod dohledem algoritmy ve Windows učení pod dohledem a transdukční učení nastavení, kde jsou k dispozici neoznačené údaje. Tato technika byla použita pro aplikace zahrnující lékařské zobrazování, geografické zobrazování a rozpoznávání objektů.

Regulátor rozdělovače

Motivace

Regularizace potrubí je typ regulace, rodina technik, která redukuje nadměrné vybavení a zajišťuje, že problém je dobře pózoval penalizací komplexních řešení. Zejména regularizace potrubí rozšiřuje techniku Tichonovova regularizace jak je aplikováno na Reprodukce jádra Hilbertovy mezery (RKHS). Podle standardní Tikhonovovy regularizace na RKHS se učící algoritmus pokouší naučit se funkci ${ displaystyle f}$ z prostoru hypotéz funkcí ${ displaystyle { mathcal {H}}}$. Prostor hypotézy je RKHS, což znamená, že je spojen s a jádro ${ displaystyle K}$, a tak funguje každý kandidát ${ displaystyle f}$ má norma ${ displaystyle left | f right | _ {K}}$, což představuje složitost kandidátské funkce v prostoru hypotézy. Když algoritmus uvažuje o kandidátské funkci, vezme v úvahu svou normu, aby penalizoval složité funkce.

Formálně, vzhledem k souboru označených tréninkových dat ${ displaystyle (x_ {1}, y_ {1}), ldots, (x _ { ell}, y _ { ell})}$ s ${ displaystyle x_ {i} v X, y_ {i} v Y}$ a a funkce ztráty ${ displaystyle V}$, učící se algoritmus využívající Tikhonovovu regularizaci se pokusí výraz vyřešit

${ displaystyle { underset {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} sum _ {i = 1} ^ { ell } V (f (x_ {i}), y_ {i}) + gamma left | f right | _ {K} ^ {2}}$

kde ${ displaystyle gamma}$ je hyperparametr který určuje, nakolik bude algoritmus preferovat jednodušší funkce před funkcemi, které lépe vyhovují datům.

Dvojrozměrný potrubí vložené do trojrozměrného prostoru (vlevo nahoře). Regularizace potrubí se pokouší naučit funkci, která je hladká na rozvinutém potrubí (vpravo nahoře).

Regularizace potrubí přidává druhý regularizační termín, vnitřní regulátor, do regulátor okolní teploty používá se ve standardní regulaci Tikhonova. Pod mnohonásobný předpoklad ve strojovém učení příslušná data nepocházejí z celého vstupního prostoru ${ displaystyle X}$, ale místo toho z nelineárního potrubí ${ displaystyle M podmnožina X}$. Geometrie tohoto potrubí, vnitřní prostor, se používá ke stanovení normalizační normy.^[1]

Laplaciánská norma

Existuje mnoho možných možností ${ displaystyle left | f right | _ {I}}$. Mnoho přirozených možností zahrnuje gradient na potrubí ${ displaystyle nabla _ {M}}$, který může poskytnout měřítko, jak hladká je cílová funkce. Hladká funkce by se měla pomalu měnit tam, kde jsou vstupní data hustá; to je přechod ${ displaystyle nabla _ {M} f (x)}$ by měl být malý, kde mezní hustota pravděpodobnosti ${ displaystyle { mathcal {P}} _ {X} (x)}$, hustota pravděpodobnosti náhodně nakresleného datového bodu, který se objeví na ${ displaystyle x}$, je velký. To dává jednu vhodnou volbu pro vnitřní regulátor:

${ displaystyle left | f right | _ {I} ^ {2} = int _ {x in M} left | nabla _ {M} f (x) right | ^ { 2} , d { mathcal {P}} _ {X} (x)}$

V praxi nelze tuto normu vypočítat přímo z důvodu okrajového rozdělení ${ displaystyle { mathcal {P}} _ {X}}$ není známo, ale lze jej odhadnout z poskytnutých údajů. Zejména pokud jsou vzdálenosti mezi vstupními body interpretovány jako graf, pak Laplaciánská matice grafu může pomoci odhadnout mezní rozdělení. Předpokládejme, že vstupní data obsahují ${ displaystyle ell}$ označené příklady (páry vstupu ${ displaystyle x}$ a štítek ${ displaystyle y}$) a ${ displaystyle u}$ neoznačené příklady (vstupy bez přidružených štítků). Definovat ${ displaystyle W}$ být maticí hranových vah pro graf, kde ${ displaystyle W_ {ij}}$ je míra vzdálenosti mezi datovými body ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$. Definovat ${ displaystyle D}$ být diagonální matice s ${ displaystyle D_ {ii} = součet _ {j = 1} ^ { ell + u} W_ {ij}}$ a ${ displaystyle L}$ být Laplaciánská matice ${ displaystyle D-W}$. Pak jako počet datových bodů ${ displaystyle ell + u}$ zvyšuje, ${ displaystyle L}$ konverguje k Operátor Laplace – Beltrami ${ displaystyle Delta _ {M}}$, který je divergence přechodu ${ displaystyle nabla _ {M}}$.^[2][3] Pak, pokud ${ displaystyle mathbf {f}}$ je vektor hodnot hodnoty ${ displaystyle f}$ na data, ${ displaystyle mathbf {f} = [f (x_ {1}), ldots, f (x_ {l + u})] ^ { mathrm {T}}}$, vnitřní normu lze odhadnout:

${ displaystyle left | f right | _ {I} ^ {2} = { frac {1} {( ell + u) ^ {2}}} mathbf {f} ^ { mathrm { T}} L mathbf {f}}$

Jako počet datových bodů ${ displaystyle ell + u}$ zvyšuje, tato empirická definice ${ displaystyle left | f right | _ {I} ^ {2}}$ konverguje k definici, když ${ displaystyle { mathcal {P}} _ {X}}$ je známo.^[1]

Řešení problému regularizace

Pomocí závaží ${ displaystyle gamma _ {A}}$ a ${ displaystyle gamma _ {I}}$ pro okolní a vnitřní regulátory se konečný výraz, který má být vyřešen, stává:

${ displaystyle { podmnožina {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} sum _ {i = 1} ^ { ell } V (f (x_ {i}), y_ {i}) + gamma _ {A} left | f right | _ {K} ^ {2} + { frac { gamma _ {I }} {( ell + u) ^ {2}}} mathbf {f} ^ { mathrm {T}} L mathbf {f}}$

Stejně jako u ostatních metody jádra, ${ displaystyle { mathcal {H}}}$ může to být nekonečně-dimenzionální prostor, takže pokud nelze výraz regularizace explicitně vyřešit, je nemožné hledat řešení v celém prostoru. Místo toho reprezentativní věta ukazuje, že za určitých podmínek o volbě normy ${ displaystyle left | f right | _ {I}}$, optimální řešení ${ displaystyle f ^ {*}}$ musí být lineární kombinací jádra se středem v každém ze vstupních bodů: u některých vah ${ displaystyle alpha _ {i}}$,

${ displaystyle f ^ {*} (x) = součet _ {i = 1} ^ { ell + u} alpha _ {i} K (x_ {i}, x)}$

Pomocí tohoto výsledku je možné hledat optimální řešení ${ displaystyle f ^ {*}}$ prohledáním konečně-dimenzionálního prostoru definovaného možnými možnostmi ${ displaystyle alpha _ {i}}$.^[1]

Aplikace

Regularizace potrubí může rozšířit řadu algoritmů, které lze vyjádřit pomocí Tikhonovovy regularizace, výběrem vhodné funkce ztráty ${ displaystyle V}$ a prostor hypotéz ${ displaystyle { mathcal {H}}}$. Dva běžně používané příklady jsou rodiny podporovat vektorové stroje a regularizované nejmenší čtverce algoritmy. (Regularizované nejmenší čtverce zahrnují algoritmus hřebenové regrese; související algoritmy LASSO a elastická regularizace sítě lze vyjádřit jako podpůrné vektorové stroje.^[4][5]) Rozšířené verze těchto algoritmů se nazývají Laplacian Regularized Least Squares (zkráceně LapRLS) a Laplacian Support Vector Machines (LapSVM).^[1]

Laplaciánské regulované nejméně čtverce (LapRLS)

Regularizovaná metoda nejmenších čtverců (RLS) je rodina regresní algoritmy: algoritmy, které předpovídají hodnotu ${ displaystyle y = f (x)}$ pro jeho vstupy ${ displaystyle x}$, s cílem, aby se předpokládané hodnoty blížily skutečným štítkům dat. RLS je zejména navržen tak, aby minimalizoval střední čtvercová chyba mezi předpokládanými hodnotami a skutečnými štítky, s výhradou regularizace. Ridgeova regrese je jednou z forem RLS; obecně je RLS stejný jako hřebenová regrese v kombinaci s metoda jádra.^{[Citace je zapotřebí ]} Prohlášení o problému pro RLS je výsledkem volby funkce ztráty ${ displaystyle V}$ v Tikhonově regularizaci jako střední kvadratická chyba:

${ displaystyle f ^ {*} = { podmnožina {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} sum _ {i = 1} ^ { ell} (f (x_ {i}) - y_ {i}) ^ {2} + gamma left | f right | _ {K} ^ {2}}$

Díky reprezentativní věta, řešení lze zapsat jako vážený součet jádra vyhodnoceného v datových bodech:

${ displaystyle f ^ {*} (x) = součet _ {i = 1} ^ { ell} alpha _ {i} ^ {*} K (x_ {i}, x)}$

a řešení pro ${ displaystyle alpha ^ {*}}$ dává:

${ displaystyle alpha ^ {*} = (K + gamma ell I) ^ {- 1} Y}$

kde ${ displaystyle K}$ je definována jako matice jádra s ${ displaystyle K_ {ij} = K (x_ {i}, x_ {j})}$, a ${ displaystyle Y}$ je vektor datových štítků.

Přidání laplaciánského výrazu pro regularizaci potrubí dává prohlášení Laplacian RLS:

${ displaystyle f ^ {*} = { podmnožina {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} součet _ {i = 1} ^ { ell} (f (x_ {i}) - y_ {i}) ^ {2} + gamma _ {A} left | f right | _ {K} ^ {2} + { frac { gamma _ {I}} {( ell + u) ^ {2}}} mathbf {f} ^ { mathrm {T}} L mathbf {f}}$

Reprezentativní věta pro regularizaci potrubí opět dává

${ displaystyle f ^ {*} (x) = součet _ {i = 1} ^ { ell + u} alpha _ {i} ^ {*} K (x_ {i}, x)}$

a tím se získá výraz pro vektor ${ displaystyle alpha ^ {*}}$. Pronájem ${ displaystyle K}$ být jádrovou maticí, jak je uvedeno výše, ${ displaystyle Y}$ být vektorem datových štítků a ${ displaystyle J}$ být ${ displaystyle ( ell + u) krát ( ell + u)}$ bloková matice ${ displaystyle { begin {bmatrix} I _ { ell} & 0 0 & 0_ {u} end {bmatrix}}}$:

${ displaystyle alpha ^ {*} = { podmnožina { alpha in mathbf {R} ^ { ell + u}} { arg ! min}} { frac {1} { ell} } (Y-JK alpha) ^ { mathrm {T}} (Y-JK alpha) + gamma _ {A} alpha ^ { mathrm {T}} K alpha + { frac { gamma _ {I}} {( ell + u) ^ {2}}} alpha ^ { mathrm {T}} KLK alpha}$

s řešením

${ displaystyle alpha ^ {*} = vlevo (JK + gamma _ {A} ell I + { frac { gamma _ {I} ell} {( ell + u) ^ {2}}} LK right) ^ {- 1} Y}$^[1]

LapRLS byl aplikován na problémy včetně senzorových sítí,^[6]lékařské zobrazování,^[7][8]detekce objektů,^[9]spektroskopie,^[10]klasifikace dokumentů,^[11]lékové interakce s proteiny,^[12]a komprimovat obrázky a videa.^[13]

Laplaciánské podpůrné vektorové stroje (LapSVM)

Podporujte vektorové stroje (SVM) jsou rodina algoritmů často používaných pro klasifikace dat do dvou nebo více skupin nebo třídy. Intuitivně SVM nakreslí hranici mezi třídami tak, aby nejbližší označené příklady k hranici byly co nejdále. To lze přímo vyjádřit jako a lineární program, ale je to také ekvivalentní Tikhonovově regularizaci s ztráta závěsu funkce, ${ displaystyle V (f (x), y) = max (0,1-yf (x))}$:

${ displaystyle f ^ {*} = { podmnožina {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} součet _ {i = 1} ^ { ell} max (0,1-y_ {i} f (x_ {i})) + gamma left | f right | _ {K} ^ {2}}$^[14][15]

Přidání termínu vnitřní regularizace k tomuto výrazu poskytne prohlášení o problému LapSVM:

${ displaystyle f ^ {*} = { podmnožina {f in { mathcal {H}}} { arg ! min}} { frac {1} { ell}} sum _ {i = 1} ^ { ell} max (0,1-y_ {i} f (x_ {i})) + gamma _ {A} left | f right | _ {K} ^ {2} + { frac { gamma _ {I}} {( ell + u) ^ {2}}} mathbf {f} ^ { mathrm {T}} L mathbf {f}}$

Znovu reprezentativní věta umožňuje vyjádření řešení z hlediska jádra vyhodnoceného v datových bodech:

${ displaystyle f ^ {*} (x) = součet _ {i = 1} ^ { ell + u} alpha _ {i} ^ {*} K (x_ {i}, x)}$

${ displaystyle alpha}$ lze najít napsáním úlohy jako lineárního programu a řešením dvojí problém. Opět nechám ${ displaystyle K}$ být jádrovou maticí a ${ displaystyle J}$ být bloková matice ${ displaystyle { begin {bmatrix} I _ { ell} & 0 0 & 0_ {u} end {bmatrix}}}$, lze prokázat řešení

${ displaystyle alpha = left (2 gamma _ {A} I + 2 { frac { gamma _ {I}} {( ell + u) ^ {2}}} LK right) ^ {- 1} J ^ { mathrm {T}} Y beta ^ {*}}$

kde ${ displaystyle beta ^ {*}}$ je řešení dvojího problému

${ displaystyle { begin {aligned} && beta ^ {*} = max _ { beta in mathbf {R} ^ { ell}} & sum _ {i = 1} ^ { ell} beta _ {i} - { frac {1} {2}} beta ^ { mathrm {T}} Q beta & { text {předmět}} && sum _ {i = 1} ^ { ell} beta _ {i} y_ {i} = 0 &&& 0 leq beta _ {i} leq { frac {1} { ell}} ; i = 1, ldots, ell end {zarovnáno}}}$

a ${ displaystyle Q}$ je definováno

${ displaystyle Q = YJK left (2 gamma _ {A} I + 2 { frac { gamma _ {I}} {( ell + u) ^ {2}}} LK right) ^ {- 1} J ^ { mathrm {T}} Y}$^[1]

LapSVM byl aplikován na problémy včetně geografického zobrazování,^[16][17][18]lékařské zobrazování,^[19][20][21]rozpoznávání obličejů,^[22]údržba strojů,^[23]a rozhraní mozku a počítače.^[24]

Omezení

• Regularizace potrubí předpokládá, že data s různými štítky pravděpodobně nebudou blízko sebe. Tento předpoklad umožňuje technice čerpat informace z neoznačených dat, ale vztahuje se pouze na některé problémové domény. V závislosti na struktuře dat může být nutné použít jiný algoritmus učení s částečným dohledem nebo transdukcí.^[25]
• V některých datových sadách je vnitřní normou funkce ${ displaystyle left | f right | _ {I}}$ může být velmi blízká okolní normě ${ displaystyle left | f right | _ {K}}$: například pokud se data skládají ze dvou tříd, které leží na kolmých řádcích, bude se vnitřní norma rovnat okolní normě. V tomto případě nemají neoznačená data žádný vliv na řešení naučené různou regularizací, i když data odpovídají předpokladu algoritmu, že oddělovač by měl být plynulý. Přístupy související s společné školení bylo navrženo řešit toto omezení.^[26]
• Pokud existuje velmi velké množství neoznačených příkladů, matice jádra ${ displaystyle K}$ se stává velmi velkým a algoritmus regularizace potrubí může být při výpočtu neúměrně pomalý. V tomto případě mohou pomoci online algoritmy a řídké aproximace potrubí.^[27]

Software

• The Knihovna ManifoldLearn a Knihovna Primal LapSVM implementovat LapRLS a LapSVM ve Windows MATLAB.
• The Knihovna Dlib pro C ++ zahrnuje funkci regularizace lineárního potrubí.

Viz také

• Rozdělování učení
• Učení s částečným dohledem
• Transdukce (strojové učení)
• Spektrální teorie grafů
• Reprodukce jádra Hilbertova prostoru
• Tichonovova regularizace
• Diferenciální geometrie

Reference