Online strojové učení je technika strojového učení , kde jsou data zpřístupňována v sekvenčním pořadí a používána k aktualizaci nejlepší predikce pro následná data, prováděná v každém tréninkovém kroku. Metoda je opačná k technice dávkového tréninku, ve které je nejlepší předpověď generována najednou z úplného souboru dat tréninku. Online učení je běžná technika používaná v oblastech strojového učení, když není možné trénovat na celé datové sadě, například když jsou potřeba algoritmy, které pracují s externí pamětí. Metoda se také používá v situacích, kdy algoritmus musí dynamicky přizpůsobovat nové vzory v datech nebo když se samotná data tvoří jako funkce času, např.předpověď ceny akciového trhu . Algoritmy online učení mohou být náchylné ke katastrofické interferenci , což je problém, který lze vyřešit postupným učením [1] .
Za podmínek supervizovaného učení se trénuje funkce , kde je považován za prostor vstupních dat a je prostorem výstupních dat, který dobře predikuje na prvcích společného rozdělení pravděpodobnosti na . Ve skutečnosti při tréninku není skutečné rozdělení nikdy známo. Obvykle je naopak přístup k tréninkové sadě příkladů . Za těchto podmínek je ztrátová funkce dána jako , takže měří rozdíl mezi předpokládanou hodnotou a skutečnou hodnotou . Ideálním cílem je vybrat funkci , kde je prostor funkcí, nazývaný prostor hypotéz, tak, aby celková ztráta byla v určitém smyslu minimální. V závislosti na typu modelu (statistický nebo kontradiktorní) lze vyvinout různé koncepty ztráty, které vedou k různým algoritmům učení.
Ve statistických modelech učení se předpokládá, že testovací vzorek pochází ze skutečného rozdělení a cílem učení je minimalizovat očekávané „riziko“
Obecným paradigmatem v této situaci je vyhodnotit funkci minimalizací empirického rizika nebo minimalizací regularizovaného empirického rizika (typicky pomocí Tichonovovy regularizace ). Volba ztrátové funkce zde poskytuje několik dobře známých algoritmů učení, jako jsou regularizované nejmenší čtverce a podpůrné vektorové stroje . Čistě online model v této kategorii by trénoval pouze na nových vstupech , aktuálním nejlepším prediktoru a některých dalších uložených informacích (které obvykle mají paměťové nároky nezávislé na velikosti dat). Pro mnoho nastavení problémů, jako jsou nelineární metody jádra , není skutečné online učení možné, ačkoli lze použít hybridní formy online učení s rekurzivními algoritmy, kde hodnota může záviset na všech předchozích datových bodech a na všech předchozích datových bodech . V tomto případě již nelze omezovat požadavky na paměť, protože je třeba zachovat všechny předchozí body, ale výpočet řešení s novými přidanými datovými body může trvat méně času než techniky dávkového učení.
Běžnou strategií pro řešení tohoto problému je minidávkové učení, kde jsou malé dávky datových bodů zpracovány v určitém časovém okamžiku, což lze považovat za pseudo-online učení pro mnohem menší celkový počet školicích bodů. Technika minibatch se používá s iterací přes trénovací data k získání optimalizované verze algoritmů strojového učení externí paměti, jako je stochastický gradient sestup . V kombinaci se zpětnou propagací jde v současnosti o de facto trénovací metodu pro umělé neuronové sítě .
Lineární metoda nejmenších čtverců se zde používá k vysvětlení různých nápadů na online učení. Myšlenky jsou dostatečně obecné na to, aby byly použitelné pro jiná nastavení, jako jsou jiné konvexní ztrátové funkce .
V kontrolovaném prostředí s funkcí kvadratické ztráty je cílem minimalizovat empirickou ztrátu
, kde .Nechť je matice dat a je maticí cílových hodnot po příchodu prvních datových bodů. Za předpokladu, že kovarianční matice je invertibilní (jinak by měl být proveden postup podobný Tichonovově regularizaci), nejlepší řešení metody nejmenších čtverců je dáno rovností
.Nyní bude výpočet kovarianční matice nějakou dobu trvat , inverze matice bude nějakou dobu trvat a násobení matice bude nějakou dobu trvat , což dává celkový čas . Pokud je v datové sadě celkem bodů a potřebujete přepočítat řešení poté, co každý datový bod dorazí , přirozený přístup bude zcela složitý . Všimněte si, že pokud je matice uložena, aktualizace v každém kroku vyžaduje pouze přidání , což vyžaduje čas, což snižuje celkový čas na , ale vyžaduje další úložný prostor [ 2] .
Rekurzivní nejmenší čtverce zvažují online přístup k nejmenším čtvercům. Lze ukázat, že s inicializací a řešením lineární metody nejmenších čtverců lze vypočítat následovně:
Výše uvedený iterační algoritmus lze dokázat indukcí na [3] . Důkaz to také ukazuje . Lze uvažovat o rekurzivních nejmenších čtvercích v kontextu adaptivních filtrů (viz Rekurzivní nejmenší čtverce ).
Složitost kroků tohoto algoritmu je , což je rychlejší než odpovídající složitost dávkového učení. Paměť potřebná pro každý krok pro uložení matice je zde konstanta . Pro případ, kdy to není reverzibilní, se uvažuje o regulované verzi ztrátové funkce . Pak je snadné ukázat, že stejný algoritmus pracuje s , a pokračující iterace dává [2] .
Pokud rovnost
Nahrazen
nebo na , stane se z toho algoritmus sestupu stochastickým gradientem. V tomto případě je složitost kroků tohoto algoritmu snížena na . Požadavky na paměť v každém kroku jsou konstantní .
Velikost kroku pro řešení očekávaného problému minimalizace rizika by však měla být zvolena pečlivě, jak je vysvětleno výše. Volbou velikosti kroku tlumení lze dokázat konvergenci průměrné iterace . Tato nastavení jsou speciálním případem stochastické optimalizace , což je dobře známý optimalizační problém [2] .
V praxi je možné provést několik stochastických přechodů gradientu přes data. Výsledný algoritmus se nazývá metoda inkrementálního gradientu a odpovídá iteraci
Hlavní rozdíl oproti metodě stochastického gradientu spočívá v tom, že se zde rozhoduje o tom, který tréninkový bod se v kroku navštíví . Taková sekvence může být náhodná nebo deterministická. Počet iterací je tak oddělen od počtu bodů (každý bod lze zobrazit vícekrát). Lze prokázat, že metoda inkrementálního gradientu poskytuje empirickou minimalizaci rizika [4] . Inkrementální techniky mohou mít výhody při zvažování účelové funkce jako součtu mnoha prvků, například jako empirické chyby velmi rozsáhlého souboru dat [2] .
Jádra lze použít k rozšíření výše uvedených algoritmů na neparametrické modely (nebo modely, ve kterých parametry tvoří nekonečně-dimenzionální prostor). Odpovídající procedura již nebude skutečně online a místo toho bude ukládat všechny datové body, ale metoda zůstává rychlejší než hrubá síla. Tato diskuse je omezena na případ kvadratické ztráty, i když ji lze rozšířit na jakoukoli konvexní ztrátovou funkci. Přímou indukcí [2] lze ukázat, že když a je datová matice, a je výstupem po krocích algoritmu náhodného sestupu gradientu, pak
kde a posloupnost splňuje opakující se vztahy
aVšimněte si, že zde je standardní jádro v , a prediktivní funkce má tvar
.Nyní, když zavedeme společné jádro a reprezentujeme predikční funkci jako
,pak stejný důkaz ukazuje, že minimalizace ztrátové funkce pomocí nejmenších čtverců se získá nahrazením výše uvedené rekurze za
Výše uvedený výraz vyžaduje zapamatování všech dat k aktualizaci . Celková časová složitost pro rekurzi, je-li vypočtena pro -tý datový bod, je , kde jsou náklady na výpočet jádra na jednom páru bodů [2] . Pak použití jádra umožňuje pohyb z konečně-dimenzionálního prostoru parametrů do potenciálně nekonečně-dimenzionálního prostoru reprezentovaného jádrem , namísto opakování přes parametr space , jehož rozměr je stejný jako velikost trénovací datové sady. Obecně je tento přístup důsledkem věty o reprezentaci [2] .
Progresivní učení je efektivní model učení, který se projevuje procesem učení lidí. Tento proces učení je nepřetržitý, vychází z přímé zkušenosti. Technika progresivního učení ve strojovém učení se může učit nové třídy nebo štítky dynamicky za běhu [5] . Ačkoli online školení může trénovat nové vzorky dat , které přicházejí postupně, nemohou trénovat nové třídy dat . Paradigma progresivního učení je nezávislé na počtu třídních omezení a může vyučovat nové třídy při zachování znalostí z předchozích tříd. Pokud však narazíte na novou třídu (nepřirozeně se vyskytující), klasifikátor se automaticky přestaví a parametry se vypočítají tak, aby byly zachovány předchozí znalosti. Tato technika je vhodná pro aplikace v reálném světě, kde je počet tříd často neznámý a je vyžadováno online učení z dat v reálném čase.
Online konvexní optimalizace [6] je obecné rozhodovací schéma, které využívá konvexní optimalizaci k získání účinných algoritmů. Schéma je vícenásobné opakování následujících akcí:
Pro
Cílem je minimalizovat „litování“ neboli rozdíl mezi celkovou ztrátou a ztrátou v nejlepším pevném bodě zpětně. Jako příklad zvažte případ online lineární regrese nejmenších čtverců. Zde váha vektorů pochází z konvexní množiny a příroda vrací funkci konvexní ztráty . Všimněte si, že implicitně odesláno s .
Některé problémy s online predikcí se však nevejdou do schématu online konvexní optimalizace. Například v online klasifikaci nejsou funkce oblasti predikce a ztráty konvexní. V takových scénářích se používají dvě jednoduché techniky redukce konvexních případů – randomizace a funkce náhradní ztráty.
Některé jednoduché online konvexní optimalizační algoritmy:
Následuj vůdceNejjednodušším pravidlem učení pro pokus je vybrat (v aktuálním kroku) hypotézu, která má nejmenší ztrátu ze všech předchozích kol. Tento algoritmus se nazývá „ Následuj vůdce “ a jednoduše dává kolo :
Tuto metodu pak lze považovat za chamtivý algoritmus . Pro případ online kvadratické optimalizace (kde ztrátová funkce je ) lze ukázat, že hranice „litování“ roste jako . Podobné meze však nelze získat pro algoritmus follow-the-leader pro jiné důležité rodiny modelů jako pro online lineární optimalizaci. K jejich získání je do algoritmu přidána regularizace.
Sledování regulovaného vůdceJedná se o přirozenou modifikaci algoritmu sledování vůdce, který se používá ke stabilizaci rozhodnutí následování vůdce a získání lepších hranic lítosti. Je vybrána funkce regularizace a školení se provádí v kole t takto:
Jako speciální případ zvažte případ online lineární optimalizace, tedy když příroda vrací ztrátové funkce formuláře . Také nechte . Předpokládejme, že regularizační funkce je vybrána pro nějaké kladné číslo . Pak lze ukázat, že se iterace minimalizace „lítosti“ mění v
Všimněte si, že to lze přepsat jako , což vypadá přesně jako online metoda sestupu gradientu.
Pokud je S konvexní podprostor , S musí být promítnut, což má za následek upravené pravidlo aktualizace
Algoritmus je známý jako líná projekce, protože vektor akumuluje gradienty. Toto je také známé jako Nesterovův algoritmus dvojitého průměrování (nebo subgradientní metoda dvojitého průměrování [7] ). V tomto scénáři jsou lineární ztrátové funkce a kvadratická regularizace „litování“ omezeny na , a pak má průměrná „litování“ tendenci k 0 .
"Litová" hranice pro lineární ztrátové funkce byla prokázána výše . Pro zobecnění algoritmu na jakoukoli konvexní ztrátovou funkci se používá funkce subgradient jako lineární aproximace kolem , což vede k online algoritmu sestupu subgradientu:
Spuštění parametru
Pro
Můžete použít online algoritmus subgradientního sestupu k získání hranic „litování“ pro online verzi podpůrného vektorového stroje pro klasifikaci, který používá po částech lineární ztrátovou funkci
Čtvercově regulované algoritmy sledující vedoucí vedou k líně projektovaným gradientovým algoritmům, jak je popsáno výše. Chcete-li použít výše uvedený přístup pro jakékoli konvexní funkce a regularizéry, lze použít online zrcadlový sestup. Optimální regularizaci v po částech lineární funkce lze získat pro lineární ztrátové funkce, což vede k algoritmu AdaGrad . Pro euklidovskou regularizaci lze ukázat, že hranice „litování“ je stejná a lze ji zlepšit na přísně konvexní a exp-konkávní ztrátové funkce.
Paradigma online učení má různé interpretace v závislosti na volbě modelu učení, přičemž každý má jinou kvalitu předpovědí sekvence funkcí . Pro diskusi používáme stochastický gradientní algoritmus sestupu. Jak bylo uvedeno výše, rekurze algoritmu je dána rovností
První interpretace považuje metodu stochastického sestupu gradientu za aplikaci na výše definovaný problém minimalizace očekávaného rizika [8] . Navíc v případě nekonečného datového toku, protože se předpokládá, že instance jsou vzorkovány z nezávislé a rovnoměrně distribuované distribuce , jsou gradientové sekvence ve výše uvedené iteraci nezávislé a rovnoměrně rozložené vzorky očekávaného odhadu stochastického gradientu rizika , a proto lze použít výsledky složitosti pro metodu sestupu stochastického gradientu k omezení odchylky , kde je minimalizátor [9] . Tento výklad platí také pro konečné trénovací množiny. Přestože přechody již nebudou při iteraci dat nezávislé, lze ve speciálních případech získat výsledky složitosti.
Druhá interpretace je aplikována na případ konečné trénovací množiny a považuje algoritmus stochastického sestupu gradientu za zástupce inkrementálního sestupu gradientu [4] . V tomto případě se lze podívat na empirické riziko:
Protože gradienty v iteracích přírůstkového klesání gradientu jsou stochastickými odhady gradientu , tato interpretace souvisí s metodou stochastického klesání gradientu, ale je aplikována na empirickou minimalizaci rizika na rozdíl od očekávaného rizika. Protože se tato interpretace týká spíše empirického rizika než očekávaného rizika, vícenásobné průchody dat jsou dokonale platné a ve skutečnosti vedou k úzkým hranicím rozptylu , kde .
Strojové učení a dolování dat | |
---|---|
Úkoly | |
Učení s učitelem | |
shluková analýza | |
Redukce rozměrů | |
Strukturální prognózy | |
Detekce anomálií | |
Grafové pravděpodobnostní modely | |
Neuronové sítě | |
Posílení učení |
|
Teorie | |
Časopisy a konference |
|