Машинско учење на мрежи

У рачунарству, онлајн машинско учење (енг. Оnline machine learning) јесте метод машинског учења у коме подаци секвенцијално постају доступни, па се затим користе за ажурирање предиктора будућих података на сваком кораку, насупрот техника офлајн машинског учења које генеришу предикторе учењем на целом скупу података за обуку. Онлајн учење је уобичајена техника која се користи у областима машинског учења где је немогуће претраживање целог скупа података, што стога захтева потребу за изузетно напредним алгоритмима. Такође се користи и у ситуацијама када је неопходно да се алгоритам динамички прилагођава новим обрасцима у подацима или када се сами подаци генеришу као функција времена, нпр. предвиђање цена акција. Онлајн алгоритми учења могу често бити склони грешкама.

Уводна прича

У надгледаном машинском учењу, задатак је учење (обрада) функције $f:X\to Y$ где је $X$ простор улаза, а $Y$ простор излаза тј. скуп вредности функције, која добро предвиђа конкретне инстанци чије је појављивање дато функцијом расподеле $p(x,y)$ на $X\times Y$. У пракси, ученику никада није позната расподела вредности $p(x,y)$. Уместо тога ученик обично има приступ конкретном скупу инстанци $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$. У овом случају, такозвана функција грешке дата са $V:Y\times Y\to \mathbb {R}$ јесте функција таква да $V(f(x),y)$ мери разлике између предвићених вредности $f(x)$ и правих вредности $y$. Кључна ствар јесте избор функције $f\in {\mathcal {H}}$, где је ${\mathcal {H}}$ простор функција који се назива простор хипотеза, тако да је функција грешке минимализована. У зависности од статистичког модела могу се дефинисати разни облици функције грешке, које ће касније водити разним алгоритмима машинског учења.

Статистичко виђење онлајн машинског учења

У статистичким моделима учења, за узорак $(x_{i},y_{i})$ се претпоставља да је изабран из одговарајуће расподеле $p(x,y)$, па је даље циљ минимизовати очекивани "ризик":

$I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .$

Надаље је циљ оценити функцију ${\hat {f}}$ методом емпиријске минимизације ризика или регуларизоване емпиријске минимизације ризика (обично метод Tikhonov-e регуларизације). Одабир функције грешке у овим случајевима доводи до неколико добро познатих алгоритама као што су метода најмањих квадрата и SVM метод машинског учења. Чисто онлајн метод машинског учења у овом случају би своја предвиђања засновао само на основу новог улаза $(x_{t+1},y_{t+1})$, тренутно најпрецизнијег предиктора $f_{t}$ и специфичних, до тог корака сачуваних, додатних информација (за чување оваквих информација обично је резервисан фиксни меморијски простор, независан од количине доступних података). За разне формулације проблема, на пример за нелинеарни метод језгара право онлајн машинско учење није могуће спровести. Ипак неку врсту модификованог односно хибридног онлајн машинског учења ипак је могуће спровести, рецимо рекурзивним алгоритмом када $f_{t+1}$ зависи од $f_{t}$ и свих претходних тачака $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$. У овом случају просторни захтеви алгоритма више нису гарантовано константни с обзиром да је алгоритму сада неопходно да чува вредности свих претходних тачака, али ће таквом решењу врло вероватно требати мање времена за извршавање додавањем нових тачака односно података у поређењу са горепоменутим офлајн машинским учењем примењеним на исти проблем. Честа стратегија за превазилажење претходно наведених проблема јесте машинско учење комбиновањем претходних онлајн и офлајн метода коришћењем мини серија, које процесирају мале групе од $b\geq 1$ података у једном кораку. Претходно се може сматрати као псеудо-онлајн учење када је $b$ много мање од укупног броја тачака тј. података за обраду у општем случају. Технике мини серија машинског учења се користе када имамо вишеструки пролаз кроз податке у процесу обраде, у циљу добијања оптимитзованих верзија алгоритама аутоматског учења.

Пример: линеарна апроксимација (метод најмањих квадрата)

Линеарни метод најмањих квадрата (илустрација)

Једноставан уводни пример линеарна метода најмањих квадрата користи се да објасни ширину идеја које се провлаче кроз корене онлајн машинског учења. Ова математичка идеја јесте довољно општа да се примени у разним другим проблемима, нпр. са осталим конвексинм функцијама грешке.

Учење у серијама

Ако у надгледаном машинском учењу за функцију грешке узмемо квадратну функцију, минимизација грешке своди се на минимизацију квадратне функције.

$I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}$ где је

$x_{j}\in \mathbb {R} ^{d},w\in \mathbb {R} ^{d},y_{j}\in \mathbb {R}$.

Нека $X$ буде $i\times d$ матрица и нека је $Y$ матрица $i\times 1$ циљаних вредности након првих $i$ тачака.

Претпоставимо да је матрица коваријансе $\Sigma _{i}=X^{T}X$ инверзибилна (иначе се на њу примењују одређени методи регуларизације), најбоље решење $f^{*}(x)=\langle w^{*},x\rangle$ линеарним методом најмањих квадрата дато је са

$w^{*}=(X^{T}X)^{-1}X^{T}Y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}$.

Даље, рачунање матрице коваријансе $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}$ повлачи сложеност $O(id^{2})$, инвертовање матрице $d\times d$ повлачи сложеност $O(d^{3})$, док је остало множење сложености $O(d^{2})$, дајући тако укупну сложеност целог процеса $O(id^{2}+d^{3})$. Када је $n$ укупан број доступних тачака и када треба поново рачунати решење након додавања сваке нове тачке $i=1,\ldots ,n$, изложено решење ће имати укупну сложеност $O(n^{2}d^{2}+nd^{3})$. Приметимо да ако у меморији чувамо матрицу коваријансе $\Sigma _{i}$, тада њено ажурирање на сваком кораку захтева само додавање $x_{i+1}x_{i+1}^{T}$, које је сложености $O(d^{2})$, што умањује укупну сложеност на $O(nd^{2}+nd^{3})=O(nd^{3})$, али користи додатни простор реда величине $O(d^{2})$ да чувамо $\Sigma _{i}$.

Онлајн машинско учење: рекурзивна метода најмањих квадрата

Рекурзивни алгоритам методе најмањих квадрата разматра проблем методе најмањих квадрата из угла онлајн машинског учења. Исти се може приказати на следећи начин. Нека је $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ и $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$. Решење линеарним методом најмањих квадрата дато у претходном одељку може бити израчунато следећим итеративним процесом:

$\Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}$

$w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

Претходни итеративни алгоритам може бити доказан методом математичке индукције по $i$.. Претходни доказ показује да је $\Gamma _{i}=\Sigma _{i}^{-1}$. Сложеност у $n$ корака овог алгоритма јесте $O(nd^{2})$, што је за ред величине ефикасинје од одговарајућег претходно изложеног алгоритма за учење у серијама. Просторни захтеви сваког $i$-тог корака овде се своде на чување матрице $\Gamma _{i}$, што је константа $O(d^{2})$. У случају када $\Sigma _{i}$ није регуларна тј. инверзибилна, разматра се функција грешке $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}$. Даље је релативно једноставо показати да наш алгоритам ради са почетним условом $\Gamma _{0}=(I+\lambda I)^{-1}$, и итерацијама $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$.

Стохастички метод градијентног спуста

Ако у претходном алгоритму формулу

$\textstyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

заменимо формулом

$\textstyle w_{i}=w_{i-1}-\gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})$

где $\Gamma _{i}\in \mathbb {R} ^{d\times d}$ и $\gamma _{i}\in \mathbb {R}$, долазимо до нечега што се назива стохастички метод градијентног спуста. Овај алгоритам има сложеност за $n$ корака редуковану на $O(nd)$. Просторни захтеви овог алгоритма у сваком $i$-том кораку су константни $O(d)$.

Било како било, величину корака $\gamma _{i}$ треба пажљиво изабрати тако да се минимизује очекивана грешка. Избором корака $\gamma _{i}\approx {\frac {1}{\sqrt {i}}},$ може се показати конвергенција претходног итеративног низа u просечном броју корака ${\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}$. Овај проблем представља специјални случај области стохастичке оптимизације, добро познате подобласти оптимизације.

Постепени стохастички метод градијентног спуста

У пракси могуће је изводити вишеструке стохастичке пролазе (који се у том случају називају циклуси или епохе) кроз податке. Овако модификовани алгоритам се назива постепени стохастички метод градијентног спуста и одговара следећој итеративној формули:

$\textstyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})$.

Основна разлика у односу на претходно изложени метод јесте та што у овом случају низ $t_{i}$ се користи да се одлучи која тачка ће бити посећена у $i$-том кораку. Тај низ може бити стохастичki или детерминистички. Број итерација више није једнак броју тачака (свака тачка може бити коришћена више него једном). Ова метода се може искористити да минимизује функцију ризика Технике сличне овој могу бити корисне када се узимају у обзир функције грешке састављене од веома великог скупа података.

Кернел методе

Кернели се могу користити за проширивање горенаведених алгоритама на непараметрарске моделе (или моделе где параметри формирају простор бесконачне димензије). Одговарајући поступак више неће бити у пуном смислу метод онлајн машинског учења, и уместо тога укључиче чување свих података, али ће и даље бити доста бржи од метода грубе силе. Наредна дискусија је ограничена на случај квадратне функције грешке, али се једноставно може проширити на било који случај конвексне функције грешке. Једноставном математичком индукцијом могуће је показати да ако је $X_{i}$ матрица података а $w_{i}$ резултат алгоритма након $i$-тог корака стохастичког метода градијентног спуста, тада:

$w_{i}=X_{i}^{T}c_{i}$

где је $\textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}$ и додатно низ $c_{i}$ је дат рекурзивном дефиницијом:

$c_{0}=0$

$(c_{i})_{j}=(c_{i-1})_{j},j=1,2...,i-1$ и

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}$

Приметимо да је $\langle x_{j},x_{i}\rangle$ стандардни кернел на $\mathbb {R} ^{d}$, и предиктор јесте облика

$f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle$.

Даље, ако општи кернел означимо са $K$ и ако је предиктор сада облика:

$f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)$

тада ће доказ аналоган претходном показати да се предиктор који минимизује грешку добија променом горње рекурзије на

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}$.

Горенаведени израз захтева чување свих података за ажурирање $c_{i}$. Укупна временска сложеност претходне рекурзије када се израчнавања врше за сваку $n$-ту тачку је $O(n^{2}dk)$, где хе $k$ сложеност израчунавања вредности кернела на пару тачака домена.. Дакле, употреба форми омогућила је да се пође од простора параметара коначне димензије $\textstyle w_{i}\in \mathbb {R} ^{d}$ и да се дође до евентуално бесконачнодимензионог простора презентованог кернелом $K$ и уместо извођења рекурзије на простору параметара $\textstyle c_{i}\in \mathbb {R} ^{i}$, чија је димензија једнака димензији посматраних података. Теоријски, претходно је последица теореме о репрезентацији (теорема математичке статистике).

Прогресивно учење

Прогресивно учење је ефективан модел учења који симулира процес учења код људи. То је процес континуираног учења директно на основу искуства. Техника прогресивног учења (енг. PLN) у машинском учењу може учити нове класе/лабеле динамично, у покрету. Иако онлајн машинско учење може обрађивати нове узорке података који стижу секвенцијално, оно не може обрађивати нове класе података које се динамички уводе у сам модел. Парадигма прогресивног учења је независна од броја ограничења у класама и може учити тј. обрађивати нове класе док истовремено задржава сва знања из претходно обрађених класа. Када год се наиђе на нову класу података (класу непознату алгортму, ону коју до сада још није сусрео) класификатор се аутоматски преобликује и параметри се обрађују на начин којим се задржава досадашње знање. Овакве технике су погодне за апликације у пракси, где је број различитих класа често непознат и потребно је учење у реалном времену.

Онлајн конвексна оптимизација

У техникама онлајн конвексне оптимизације (енг. ОСО) скуп хипотеза и функција грешке су присиљено конвексни да би алгоритам добио више простора за учење. Модификован алгоритам сада има следећи облик: За $t=1,2...,T$

• Алгоритам добија улаз $x_{t}$
• Алгоритам рачуна $w_{t}$ из фиксног конвексог скупа $S$
• Околина враћа конвексну функцију грешке $v_{t}:S\rightarrow \mathbb {R}$.
• Алгоритам процењује направњене погрешке $v_{t}(w_{t})$ и ажурира модел.

На пример, размотримо онлајн машинско учење кроз линеарну апроксимацију методом најмањих квадрата. Овде тежински вектори долазе из конвексног скупа $S=\mathbb {R} ^{d}$, док је конвексна функција грешке дата са $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$. Приметимо узгред да је у овом случају $y_{t}$ имплицитно послато кроз $v_{t}$.

Мећутим, неки проблеми онлајн машинског учења не могу се природно уклопити у ову методу. За пример посматрајмо онлајн класификацију код које домен и функција грешке нису конвексни. У оваквим ситуацијама користе се две основне технике конвесксификације: рандомизација и замена функције грешке.

Неки од једноставних онлајн метода конвексне оптимизације алгоритама су:

Алгоритам прати лидера (енг. FТL)

Најједноставнији метод учења јесте избор (у тренутном кораку) хипотезе која има најмање гутитака у свим претходним корацима. Овај алгоритам носи назив Алгоритам прати лидера (енг. Follow the leader) и дат је једноставном формулом за корак $t$ са:

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)$.

На овај метод може се гледати као на похлепни алгоритам. У случају онлајн квадратне оптимизације (где је функција губитка дата са $v_{t}(w)=||w-x_{t}||_{2}^{2}$), може се показати да границе регресије расту са $\log(T)$. Какогод, овај метод се не може применити на друге важне фамилије модела машинског учења као сто је онлајн линеарна оптимизација. Да би се то урадило, овај алгоритам се модификује тако што се изврши такозвана регуларизација.

Модификовани алгоритам прати лидера (енг. FТRL)

Модификовани алгоритам прати лидера представља природну модификацију претходног алгоритма која се додаје да стабилизује понашање истог, и да обезбеди боље границе регресије. Функција регуларизације дата је са $R:S\rightarrow \mathbb {R}$ и учење је дато у кораку t као:

$w_{t}={\underset {w\in S}{\operatorname {arg\,min} }}\sum _{i=1}^{t-1}v_{i}(w)+R(w)$

Као посебан пример претходног размотримо случај онлајн линеарне оптимизације где је функција губитка дата у облику $v_{t}(w)=\langle w,z_{t}\rangle$. Такође, имамо $S=\mathbb {R} ^{d}$. Претпоставимо да је функција регуларизације $R(w)={\frac {1}{2\eta }}||w||_{2}^{2}$ одабрана за неки позитиван број $\eta$. Под оваквим претпоставкама, може се доказати да итеративни процес минимизације има слецећи облик:

$w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}$

Приметимо да претходно може бити записано и као $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$, што изгледа баш као онлајн метода градијентног спуста.

Ако је уместо тога S неки конвексан подскуп од $\mathbb {R} ^{d}$, S би требало пројектовати, што доводи до промене правила ажурирања

$w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})$

Овај алгоритам познат је и под именом лења пројекција, због тога што вектор $\theta _{t+1}$ акумулира градијент. Такође, познат је и под именом двоструки Нестеров средњи алгоритам. У овом случају, случају линеарне функције губитка и квадратне регуларизације, граница регерије је у оквирима сложености $O({\sqrt {T}})$, и стога просечна регресија иде ка 0 што и желимо.

Остали алгоритми

Квадратно регуларисани алгоритам пратње лидера води до лење пројекције градијентног метода као што је описано у претходним пасусима. Да би се горе описано користило за произвољне конвексне функције и регуларизаторе може се користити слична модификација. Други алгоритам се назива предвиђање стручним саветима. У овом случају скуп хипотеза састоји се од $d$ функција. Дистрибуција $w_{t}\in \Delta _{d}$ над $d$ експертских функција се одржава, и предвиђање се врши узимањем узорака из ове дистрибуције. У слушају Еуклидске регуларизације, може се показати да је граница регресије дата са $O({\sqrt {T}})$, сто може бити побољшано до ганице $O({\sqrt {\log T}})$ ако се користи боља функција регуларизације.

Интерпретације онлајн машинског учења

Парадигма онлајн машинског учења интересантно има различите интерпретације у зависности од избора метода учења, од којих свака има различите импликације у погледу предиктивног квалитета секвенце функција $f_{1},f_{2},\ldots ,f_{n}$. За ову дискусију користи се стохастички алгоритам градијентног спуста. Као сто је горе наведено, његова рекурзија дата је са

$\textstyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})$.

Прва интерпретација разматра метод стохастичког алгоритма градијентног спуста примењеног на проблем минимизације очекиваног ризика $I[w]$ дефинисаног раније. Заиста, у случају бесконачног стримовања односно дотока података, као у примеру $(x_{1},y_{1}),(x_{2},y_{2}),\ldots$ претпостављено је да исти долазе из расподеле $p(x,y)$, за низ градијената $V(\cdot ,\cdot )$ у претходним итерацијама претпоставља се да је узорак стохастичких процена градијената очекиваног ризика $I[w]$ и стога је могуће применити резултате метода стохастичког градијентног спуста за ограничење девијације $I[w_{t}]-I[w^{\ast }]$, где је $w^{\ast }$ минимизатор за $I[w]$.. Ова интерпретација је такође валидна и у случају коначног скупа доступних података. Иако са вишеструким пролазом кроз податке градијенти више нису независни, и даље се претходни резултати могу користити у неким ситуацијама.

Друга интерпретација се примењује на случај коначног скупа података и разматра се Стохастички градијентни спуст као пример методе postepenog градијентног спуста. У овом случају посматра се емпиријски ризик дат са:

$I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .$

Како су градијенти $V(\cdot ,\cdot )$ у овој методи такође стохастичке процене градијента од $I_{n}[w]$, тумачење овог метода је такође повезано са методом стохастичког градијентног спуста, али се примењује у циљу минимизовања емпиријског ризика уместо минимизације очекиваног ризика. Како се оваква интерпретација концентрише на емпиријски ризик а не на очекивани ризик, вишеструки проласци кроз податке су дозвољени и заправо воде до строжих граница девијације $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]$, где је $w_{n}^{\ast }$ минимизатор од $I_{n}[w]$.

Имплементације онлајн машинског учења

• Vowpal Wabbit: Отворени софтвер, брз онлајн систем машинског учења што је значајно за подршку бројним редукцијама машинског учења, подржавајући избор различитих функција губитака и алгоритама оптимизције. Користи такозвани трик са хеширањем за ограничавање величине скупа функција, независно од количине података који се обрађују.
• scikit-learn: Обезбеђује изванредне имплементације алгоритама за
  • Класификацију.
  • Регресију
  • Кластеринг, итд.

Види још

• Машинско учење
• Квантно машинско учење
• Алгоритам
• Вјештачка интелигенција

Литература

• Yin, G. George; Kushner, Harold J. (2003). Stochastic approximation and recursive algorithms and applications (Second изд.). New York: Springer. стр. 8–12. ISBN 978-0-387-21769-7.