Stabilita (teorie učení) - Stability (learning theory) - Wikipedia

Stabilita, také známý jako algoritmická stabilita, je pojem v teorie výpočetního učení jak a algoritmus strojového učení je narušen malými změnami jeho vstupů. Stabilní algoritmus učení je algoritmus, u kterého se predikce příliš nezmění, když se tréninková data mírně upraví. Zvažte například algoritmus strojového učení, na který je trénován rozpoznat ručně psané dopisy abecedy s použitím 1 000 příkladů ručně psaných písmen a jejich štítků („A“ až „Z“) jako cvičné sady. Jedním ze způsobů, jak upravit tuto tréninkovou sadu, je vynechat příklad, takže je k dispozici pouze 999 příkladů ručně psaných písmen a jejich štítků. Stabilní algoritmus učení by vytvořil podobné klasifikátor s tréninkovými sadami s 1000 a 999 prvky.

Stabilitu lze studovat u mnoha typů problémů s učením, od výuka jazyků na inverzní problémy ve fyzice a inženýrství, protože je to spíše vlastnost procesu učení než typ informace, která se učí. Studie stability získala na důležitosti v roce 2006 teorie výpočetního učení v roce 2000, kdy se ukázalo, že má souvislost s zobecnění^{[Citace je zapotřebí ]}. Ukázalo se, že zejména u velkých tříd učebních algoritmů empirická minimalizace rizik algoritmy, určité typy stability zajišťují dobré zobecnění.

Dějiny

Ústředním cílem při navrhování a systém strojového učení je zaručit, že učící algoritmus bude zevšeobecnit, nebo proveďte přesně nové příklady poté, co jste byli vyškoleni na konečný počet z nich. V 90. letech bylo dosaženo milníků v získávání mezí zobecnění algoritmy učení pod dohledem. Technika, která se historicky používala k prokázání zobecnění, měla ukázat, že algoritmus byl konzistentní, za použití jednotná konvergence vlastnosti empirických veličin k jejich prostředkům. Tato technika byla použita k získání mezí zobecnění pro velkou třídu empirická minimalizace rizik (ERM) algoritmy. Algoritmus ERM je takový, který vybírá řešení z prostoru hypotéz ${ displaystyle H}$ takovým způsobem, aby se minimalizovala empirická chyba na tréninkové sestavě ${ displaystyle S}$.

Obecný výsledek, prokázaný Vladimír Vapnik pro binární klasifikační algoritmy ERM je to, že pro jakoukoli cílovou funkci a distribuci vstupu, jakýkoli prostor hypotézy ${ displaystyle H}$ s VC-rozměr ${ displaystyle d}$, a ${ displaystyle n}$ příklady tréninku, algoritmus je konzistentní a vyprodukuje chybu tréninku, která je nanejvýš ${ displaystyle O left ({ sqrt { frac {d} {n}}} right)}$ (plus logaritmické faktory) ze skutečné chyby. Výsledek byl později rozšířen na téměř ERM algoritmy s funkčními třídami, které nemají jedinečné minimalizátory.

Vapnikova práce s využitím toho, co se stalo známé jako Teorie VC, vytvořil vztah mezi zobecněním algoritmu učení a vlastnostmi prostoru hypotéz ${ displaystyle H}$ naučených funkcí. Tyto výsledky však nebylo možné aplikovat na algoritmy s hypotézovými prostory neomezené dimenze VC. Jinými slovy, tyto výsledky nelze použít, když se naučená informace vyznačuje příliš velkou složitostí, než aby ji bylo možné měřit. Některé z nejjednodušších algoritmů strojového učení - například pro regresi - mají prostory hypotéz s neomezenou dimenzí VC. Dalším příkladem jsou algoritmy pro výuku jazyků, které mohou vytvářet věty libovolné délky.

Analýza stability byla vyvinuta v roce 2000 pro teorie výpočetního učení a je alternativní metodou pro získání mezí zobecnění. Stabilita algoritmu je spíše vlastností procesu učení než přímou vlastností prostoru hypotézy ${ displaystyle H}$, a lze jej posoudit pomocí algoritmů, které mají hypotézové prostory s neomezenou nebo nedefinovanou dimenzí VC, jako je nejbližší soused. Stabilní algoritmus učení je algoritmus, u kterého se naučená funkce příliš nemění, když je tréninková sada mírně upravena, například vynecháním příkladu. Míra Vynechejte jednu chybu se používá v algoritmu Cross Validation Leave One Out (CVloo) k vyhodnocení stability algoritmu učení s ohledem na funkci ztráty. Analýza stability jako taková je aplikací Analýza citlivosti na strojové učení.

Souhrn klasických výsledků

• Počátkem 20. století - Stabilita v teorii učení byla nejdříve popsána z hlediska kontinuity mapy učení ${ displaystyle L}$, vysledovat Andrej Nikolajevič Tichonov.
• 1979 - Devroye a Wagner zjistili, že chování algoritmu „necháme jeden na řadě“ souvisí s jeho citlivostí na malé změny ve vzorku.^[1]
• 1999 - Kearns a Ron objevili souvislost mezi konečnou dimenzí VC a stabilitou.^[2]
• 2002 - V mezníkovém článku Bousquet a Elisseeff navrhli pojem stejnoměrná stabilita hypotézy algoritmu učení a ukázal, že implikuje nízkou chybu generalizace. Jednotná stabilita hypotézy je však silná podmínka, která se nevztahuje na velké třídy algoritmů, včetně algoritmů ERM s prostorem hypotézy pouze dvou funkcí.^[3]
• 2002 - Kutin a Niyogi rozšířili výsledky Bousqueta a Elisseeffa tím, že poskytli hranice zobecnění pro několik slabších forem stability, které nazývali téměř všude stabilita. Dále podnikli první krok k vytvoření vztahu mezi stabilitou a konzistencí v algoritmech ERM v nastavení Pravděpodobně přibližně korektní (PAC).^[4]
• 2004 - Poggio a kol. prokázal obecný vztah mezi stabilitou a konzistencí ERM. Navrhli statistickou formu stability dovolené-jednoho-ven, kterou nazývali Stabilita CVEEEloo, a ukázal, že je a) dostatečný pro zobecnění v omezených třídách ztrát ab) nezbytný a dostatečný pro konzistenci (a tedy zobecnění) ERM algoritmů pro určité ztrátové funkce, jako je kvadratická ztráta, absolutní hodnota a ztráta binární klasifikace .^[5]
• 2010 - Shalev Shwartz si všiml problémů s původními výsledky Vapniku kvůli složitým vztahům mezi prostorem hypotéz a třídou ztrát. Diskutují o pojmech stability, které zachycují různé třídy ztrát a různé typy učení, pod dohledem a bez dozoru.^[6]

Předběžné definice

Definujeme několik pojmů souvisejících s tréninkovými sadami algoritmů učení, abychom pak mohli definovat stabilitu několika způsoby a prezentovat věty z pole.

Algoritmus strojového učení, známý také jako mapa učení ${ displaystyle L}$, mapuje tréninkovou datovou sadu, což je sada označených příkladů ${ displaystyle (x, y)}$, na funkci ${ displaystyle f}$ z ${ displaystyle X}$ na ${ displaystyle Y}$, kde ${ displaystyle X}$ a ${ displaystyle Y}$ jsou ve stejném prostoru příkladů školení. Funkce ${ displaystyle f}$ jsou vybrány z prostoru hypotézy funkcí zvaných ${ displaystyle H}$.

Výcviková sada, ze které se algoritmus učí, je definována jako

${ displaystyle S = {z_ {1} = (x_ {1}, y_ {1}) , .., z_ {m} = (x_ {m}, y_ {m}) }}$

a má velikost ${ displaystyle m}$ v ${ displaystyle Z = X krát Y}$

tažené i.i.d. z neznámé distribuce D.

Tedy mapa učení ${ displaystyle L}$ je definován jako mapování z ${ displaystyle Z_ {m}}$ do ${ displaystyle H}$, mapování tréninkové sady ${ displaystyle S}$ na funkci ${ displaystyle f_ {S}}$ z ${ displaystyle X}$ na ${ displaystyle Y}$. Zde uvažujeme pouze deterministické algoritmy, kde ${ displaystyle L}$ je symetrický vzhledem k ${ displaystyle S}$, tj. to nezávisí na pořadí prvků ve výcvikové sadě. Dále předpokládáme, že všechny funkce jsou měřitelné a všechny množiny počítatelné.

Ztráta ${ displaystyle V}$ hypotézy ${ displaystyle f}$ s ohledem na příklad ${ displaystyle z = (x, y)}$ je pak definována jako ${ displaystyle V (f, z) = V (f (x), y)}$.

Empirická chyba ${ displaystyle f}$ je ${ displaystyle I_ {S} [f] = { frac {1} {n}} součet V (f, z_ {i})}$.

Skutečná chyba ${ displaystyle f}$ je ${ displaystyle I [f] = mathbb {E} _ {z} V (f, z)}$

Vzhledem k tréninkové sadě S o velikosti m sestavíme pro všechny i ​​= 1 ...., m upravené tréninkové sady takto:

• Odebráním i-tého prvku

${ displaystyle S ^ {| i} = {z_ {1}, ..., z_ {i-1}, z_ {i + 1}, ..., z_ {m} }}$

• Nahrazením i-tého prvku

${ displaystyle S ^ {i} = {z_ {1}, ..., z_ {i-1}, z_ {i} ^ {'}, z_ {i + 1}, ..., z_ {m} }}$

Definice stability

Stabilita hypotézy

Algoritmus ${ displaystyle L}$ má stabilitu hypotézy β vzhledem ke ztrátové funkci V, pokud platí:

${ displaystyle forall i in {1, ..., m }, mathbb {E} _ {S, z} [| V (f_ {S}, z) -V (f_ {S ^ { | i}}, z) |] leq beta.}$

Stabilita hypotézy z hlediska bodu

Algoritmus ${ displaystyle L}$ má bodově stabilitu hypotézy β vzhledem ke ztrátové funkci V, pokud platí:

${ displaystyle forall i in {1, ..., m }, mathbb {E} _ {S} [| V (f_ {S}, z_ {i}) - V (f_ {S ^ {| i}}, z_ {i}) |] leq beta.}$

Stabilita chyb

Algoritmus ${ displaystyle L}$ má stabilitu chyby β vzhledem ke ztrátové funkci V, pokud platí:

${ displaystyle forall S in Z ^ {m}, forall i in {1, ..., m }, | mathbb {E} _ {z} [V (f_ {S}, z )] - mathbb {E} _ {z} [V (f_ {S ^ {| i}}, z)] | leq beta}$

Jednotná stabilita

Algoritmus ${ displaystyle L}$ má jednotnou stabilitu β vzhledem ke ztrátové funkci V, pokud platí:

${ displaystyle forall S in Z ^ {m}, forall i in {1, ..., m }, sup _ {z in Z} | V (f_ {S}, z) -V (f_ {S ^ {| i}}, z) | leq beta}$

Pravděpodobnostní verze rovnoměrné stability β je:

${ displaystyle forall S in Z ^ {m}, forall i in {1, ..., m }, mathbb {P} _ {S} { sup _ {z v Z } | V (f_ {S}, z) -V (f_ {S ^ {| i}}, z) | leq beta } geq 1- delta}$

Algoritmus se říká, že je stabilní, když hodnota ${ displaystyle beta}$ klesá jako ${ displaystyle O ({ frac {1} {m}})}$.

Stabilita křížové validace (CVloo) na jedné straně

Algoritmus ${ displaystyle L}$ má stabilitu CVloo β vzhledem ke ztrátové funkci V, pokud platí:

${ displaystyle forall i in {1, ..., m }, mathbb {P} _ {S} {| V (f_ {S}, z_ {i}) - V (f_ {S ^ {| i}}, z_ {i}) | leq beta _ {CV} } geq 1- delta _ {CV}}$

Definice (CVloo) stability je ekvivalent ke stabilitě hypotézy Pointwise viděné dříve.

Chyba očekávané dovolené${ displaystyle Eloo_ {chyba}}$) Stabilita

Algoritmus ${ displaystyle L}$ má ${ displaystyle Eloo_ {chyba}}$ stabilita, pokud pro každé n existuje a ${ displaystyle beta _ {EL} ^ {m}}$ a a ${ displaystyle delta _ {EL} ^ {m}}$ takové, že:

${ displaystyle forall i in {1, ..., m }, mathbb {P} _ {S} {| I [f_ {S}] - { frac {1} {m}} sum _ {i = 1} ^ {m} V (f_ {S ^ {| i}}, z_ {i}) | leq beta _ {EL} ^ {m} } geq 1- delta _ {EL} ^ {m}}$, s ${ displaystyle beta _ {EL} ^ {m}}$ a ${ displaystyle delta _ {EL} ^ {m}}$ jít na nulu pro ${ displaystyle m, rightarrow infty}$

Klasické věty

Od Bousqueta a Elisseeffa (02):

U algoritmů symetrického učení s omezenou ztrátou, pokud má algoritmus Uniform Stability s pravděpodobnostní definicí výše, pak se algoritmus zobecní.

Uniform Stability je silná podmínka, kterou nesplňují všechny algoritmy, ale překvapivě ji splňuje velká a důležitá třída regulačních algoritmů. Omezení zobecnění je uvedeno v článku.

Od Mukherjee et al. (06):

• Pro algoritmy symetrického učení s omezenou ztrátou, pokud má algoritmus oba Cross-validation (CVloo) Leave-one-out cross-validation (CVloo) Stability and Expected-leave-one-out error (${ displaystyle Eloo_ {chyba}}$) Stabilita, jak je definována výše, pak se algoritmus zobecní.
• Ani jedna podmínka sama o sobě pro zobecnění nestačí. Oba však společně zajišťují zobecnění (zatímco obrácení není pravdivé).
• Konkrétně pro algoritmy ERM (řekněme pro ztrátu čtverce) je pro konzistenci a zobecnění nezbytná a dostatečná stabilita s křížovou validací (CVloo) typu Leave-one-out.

To je důležitý výsledek pro základy teorie učení, protože ukazuje, že dvě dříve nesouvisející vlastnosti algoritmu, stabilita a konzistence, jsou ekvivalentní pro ERM (a určité ztrátové funkce). V článku je uvedena vazba generalizace.

Algoritmy, které jsou stabilní

Toto je seznam algoritmů, které se ukázaly jako stabilní, a článek, kde jsou uvedeny přidružené meze zobecnění.

• Lineární regrese^[7]
• Klasifikátor k-NN se ztrátovou funkcí {0-1}.^[8]
• Podporujte vektorový stroj (SVM) klasifikace s ohraničeným jádrem a kde je regularizátor normou v Hilbertově prostoru pro reprodukci jádra. Velká regularizační konstanta ${ displaystyle C}$ vede k dobré stabilitě.^[9]
• Klasifikace SVM s měkkou rezervou.^[10]
• Regularizováno Regrese nejmenších čtverců.^[11]
• Algoritmus minimální relativní entropie pro klasifikaci.^[12]
• Verze pytlování regulátory s číslem ${ displaystyle k}$ regresorů roste s ${ displaystyle n}$.^[13]
• Klasifikace SVM pro více tříd.^[14]
• Všechny výukové algoritmy s regularizací Tichonova splňují kritéria Uniform Stability a jsou tedy zobecnitelné.^[15]

Reference

Další čtení