Bekpropagacija

Bekpropagacija je metoda koja se koristi u veštačkim neuronskim mrežama za izračunavanje doprinosa greške svakog neurona nakon obrade serije podataka. To je poseban slučaj starije i opštije tehnike koja se naziva automatsko diferenciranje. U kontekstu učenja, bekpropagacija se obično koristi od strane algoritma za optimizaciju gradijenta kako bi se prilagodila težina neurona izračunavanjem gradijenta funkcije gubitka. Ova tehnika se ponekad naziva i povratno širenje grešaka, jer se greška izračunava na izlazu i prenosi natrag kroz mrežne slojeve.

Algoritam za proširenje unazad je ponovo otkriven i ekvivalent je automatskom diferenciranju u obrnutom režimu akumulacije. Bekpropagacija zahteva poznati izlaz za svaku ulaznu vrednost pa se stoga smatra da je to metod učenja nadgledanjem (mada se takođe koristi u nekim nenadgledanim mrežama kao što su autoenkoderi). Bekpropagacija je takođe generalizacija delta pravila za višeslojne mreže, omogućene korišćenjem pravila lanca za iterativno izračunavanje nagiba za svaki sloj. Ona je usko povezana sa Gaus-Njutn algoritmom, i deo je kontinuiranog istraživanja u nervnoj bekpropagaciji. Bekpropagacija se može koristiti u bilo kom optimizatoru zasnovanom na gradijentu, kao što je L-BFGS ili skraćeni Njutn. Takođe se često koristi za obučavanje dubokih neuronskih mreža, pojma koji se koristi za opis neuronskih mreža sa više od jednog skrivenog sloja.

Motivacija

Cilj svakog algoritma učenja nadgledanja je pronalaženje funkcije koja najbolje mapira skup ulaza na njihov tačan izlaz. Primer bi bio klasifikacioni zadatak, gde je ulaz slika životinje, a tačan rezultat je ime životinje.

Motivacija za bekpropagaciju je obučavanje višeslojne neuronske mreže tako da može naučiti odgovarajuća predstavljanja kako bi omogućila da sazna neko proizvoljno mapiranje unosa za izlaz.

Gubitak funkcije

Ponekad se naziva funkcija troška ili funkcija greške (ne sme se mešati sa Gausovom funkcijom greške), funkcija gubitka je funkcija koja mapira vrednosti jedne ili više promenljivih kao realan broj koji intuitivno predstavlja neki "trošak" povezan sa tim vrednostima. Funkcija gubitka računa razliku između izlaza mreže i očekivanog izlaza, nakon što se slučaj raširi kroz mrežu.

Pretpostavke

Dve pretpostavke se moraju napraviti o obliku funkcije greške. Prva je da se može napisati kao prosek ${\textstyle E={\frac {1}{n}}\sum _{x}E_{x}}$ preko funkcija greške ${\textstyle E_{x}}$ za ${\textstyle n}$ individualnih primera obuke, ${\textstyle x}$. Razlog za ovu pretpostavku je da algoritam bekpropagacije izračunava gradijent funkcije greške za jedan primer treninga, koji treba generalizovati sa ukupnom funkcijom greške. Druga pretpostavka je da se može napisati kao funkcija izlaza iz neuronske mreže.

Neka su $y,y'$ vektori u $\mathbb {R} ^{n}$.

Posmatrajmo funkciju greške $E(y,y')$ koja računa metriku između izlaza.

Standardan izbor je:

kvadrat Euklidske metrike između vektora $y$ i vektora $y'$ :

$$E(y,y')={\tfrac {1}{2}}\lVert y-y'\rVert ^{2}$$

Koeficijent ${\tfrac {1}{2}}$ se koristi kako bi se skratio sa 2 nakon diferenciranja Funkcija greške na osnovu ${\textstyle n}$ primera se može zapisati kao prosečna vrednost:

$$E={\frac {1}{2n}}\sum _{x}\lVert (y(x)-y'(x))\rVert ^{2}$$

i kao parcijalni izvod u odnosu na izlaz funkcije

$${\frac {\partial E}{\partial y'}}=y'-y$$

Algoritam optimizacije ponavlja ciklus od dve faze, širenje i ažuriranje težine. Kada se ulazni vektor pojavi na mreži, on se prosleđuje napred kroz mrežu, sloj po sloj, sve dok ne dostigne izlazni sloj. Izlaz mreže se zatim upoređuje sa željenim izlazom, koristeći funkciju gubitka. Dobijena vrednost greške se izračunava za svaki od neurona u izlaznom sloju. Vrednosti greške se zatim prosleđuju iz izlaza nazad kroz mrežu, sve dok svaki neuron ne dobije pridruženu vrednost greške koja odražava njen doprinos izvornom izlazu. Bekpropagacija koristi ove vrednosti greške za izračunavanje gradijenta funkcije gubitka. U drugoj fazi, ovaj gradijent se napaja metodom optimizacije, koja zauzvrat to koristi za ažuriranje težine, u pokušaju da minimizira funkciju gubitka.

Neka je $N$ neuronska mreža sa $e$ konekcija, $m$ ulaza i $n$ izlaza.

$x_{1},x_{2},\dots$ označavaju vektore u $\mathbb {R} ^{m}$, $y_{1},y_{2},\dots$ vektore u $\mathbb {R} ^{n}$ i $w_{0},w_{1},w_{2},\ldots$ vektore u $\mathbb {R} ^{e}$.

Oni se redom nazivaju ulazi, izlazi i težine.

Neuronska mreža odgovara funkciji $y=f_{N}(w,x)$ koja za dati vektor težina mapira ulaz i izlaz.

Optimizacija kao ulaze uzima sekvencu primera $(x_{1},y_{1}),\dots ,(x_{p},y_{p})$ i kao rezultat daje sekvencu težina $w_{0},w_{1},\dots ,w_{p}$ počevši od neke težine $w_{0}$ koja se obično bira kao proizvoljna.

Ove težine se računaju na sledeći način: Prvo se računa $w_{i}$ koristeći samo $(x_{i},y_{i},w_{i-1})$ za $i=1,\dots ,p$. Izlaz algoritma je $w_{p}$ koji nam daje novu funkciju $x\mapsto f_{N}(w_{p},x)$. Računica je ista u svakom koraku, ovde je opisan slučaj za $i=1$.

Računanje $w_{1}$ iz $(x_{1},y_{1},w_{0})$ se završava primenjujući gradijent nagiba na funkciju $w\mapsto E(f_{N}(w,x_{1}),y_{1})$ kako bi se našao lokalni minimum, počevši od $w=w_{0}$.

Intuicija

Da bi se shvatilo matematičko izvođenje algoritma bekpropagacije, poželjno je da se prvo razviju neke intuicije o odnosu između stvarnog izlaza neurona i tačnog izlaza za određeni primer. Razmotrimo jednostavnu neuronsku mrežu sa dve ulazne jedinice, jednom izlaznom jedinicom i bez skrivenih jedinica. Svaki neuron koristi linearni izlaz, što je ponderisana suma njegovog unosa.

U početku, pre treninga, težine će biti podešene nasumično. Zatim neuron uči na primerima, koji se u ovom slučaju sastoje od skupa trojki $(x_{1},x_{2},t)$ gde su $x_{1}$ i $x_{2}$ ulazi u mrežu i t je ispravan izlaz (izlaz koji mreža treba na kraju da proizvede za date ulaze). Inicijalna mreža, za date $x_{1}$ i $x_{2}$ će izračunati izlaz u koji se verovatno razlikuje od t (date slučajne težine) . Uobičajena metoda za merenje neslaganja između očekivanog izlaza t i stvarnog izlaza y je kvadratna mera greške:

$E=(t-y)^{2},$

gde je E neslaganje ili greška.

Kao primer, razmotrite mrežu u jednom slučaju: $(1,1,0)$, tako da ulaz $x_{1}$ i ulaz $x_{2}$ budu 1 i 1 i tačan izlaz, t bude 0. Sada, ako je stvarni izlaz y iscrtan na horizontalnoj osi zajedno sa greškom E na vertikalnoj osi, rezultat je parabola. Minimum parabole odgovara izlazu y koji minimizuje grešku E. Na jednom primeru, minimum takođe dotiče horizontalnu osu, što znači da će greška biti nula i da mreža može proizvesti izlaz y koji tačno odgovara očekivanom izlazu t. Samim tim, problem mapiranja ulaza na izlaze može se svesti na problem optimizacije pronalaska funkcije koja će dati minimalnu grešku.

Međutim, izlaz neurona zavisi od ponderisane sume svih inputa: $y=x_{1}w_{1}+x_{2}w_{2},$ gde su težine na vezu od ulaznih jedinica do izlazne jedinice. Stoga, greška takođe zavisi od dolaznih težina neuronu, što je na kraju ono što treba promeniti u mreži kako bi se omogućilo učenje. Ako je svaka težina iscrtana na zasebnoj horizontalnoj osi i greška na vertikalnoj osi, rezultat je parabolička posuda. Za neuron sa k težina, isti grafik bi zahtevao eliptički paraboloid sa $k+1$ dimenzijom.

Inercija

Koristeći promenljivi inercijski izraz (Momentum) ${\textstyle \alpha }$ , gradijent i poslednja promena se mogu ponderisati tako da podešavanje težine dodatno zavisi od prethodne promene. Ako je Momentum ${\textstyle \alpha }$ jednak 0, promena zavisi isključivo od gradijenta, dok vrednost 1 zavisi samo od poslednje promene.

Slično kao lopta koja se spušta niz planinu, čija trenutna brzina se određuje ne samo trenutnim nagibom planine, već i sopstvenom inercijom, može se dodati inercija:

$$\Delta w_{ij}(t+1)=(1-\alpha )\eta \delta _{j}o_{i}+\alpha \,\Delta w_{ij}(t)$$

gde je

${\textstyle \Delta w_{ij}(t+1)}$ promena u težini ${\textstyle w_{ij}(t+1)}$ u vezi između neurona ${\textstyle i}$ i neurona ${\textstyle j}$ u vremenu ${\textstyle (t+1),}$

${\textstyle \eta }$ stopa učenja

${\textstyle \delta _{j}}$ greška signala neurona j

${\textstyle o_{i}}$ izlaz neurona ${\textstyle i}$ što je i ulaz za trenutni neuron (neuron ${\textstyle j,}$)

${\textstyle \alpha }$ uticaj inercije ${\textstyle \Delta w_{ij}(t)}$ Ovo odgovara promeni težine u prethodnoj tački vremena

Inercija zavisi od trenutne promene težine ${\textstyle (t+1)}$ iz trenutnog gradijenta funkcije greške (nagib planine, prva suma), kao i od promene težine u prethodnoj tački vremena (inercija, druga suma).

Uz inerciju, izbegavaju se takođe i problemi zaglavljivanja (u strmim ravnicama i ravnim platoima). Budući da, na primer, gradijent funkcije greške postaje vrlo mali u ravnim platoima, inercija bi odmah dovela do "usporavanja" gradijenta. Ovo usporavanje je odloženo dodavanjem inercije tako da se ravni plato može preći što brže.

Načini učenja

Dostupna su dva načina učenja: stohastični i serijski. U stohastičkom učenju, svaki ulaz stvara prilagođavanje težine. U serijskom učenju težine se prilagođavaju na osnovu serije ulaza, akumulirajući greške nad tom serijom. Stohastično učenje uvodi "buku" u proces gradacije, koristeći lokalni gradijent izračunat iz jedne tačke podatka; ovo smanjuje šanse da se mreža zaglavi u lokalnim minimumima. Međutim, serijsko učenje obično daje brže i stabilnije rezultate, pošto se svaka promena vrši u pravcu prosečne greške serije. Opšti izbor kompromisa je korišćenje "mini-serija", što znači male serije i sa uzorcima u svakoj seriji izabranim stohastički iz celog skupa podataka.

Ograničenja

Ne postoji garancija da će bekpropagacija naći globalni minimum funkcije greške, već samo lokalni minimum. Za ovaj problem koji nastaje zbog nekonveksnosti funkcije greške u neuronskim mrežama, se dugo smatralo da predstavlja veliki nedostatak, ali je Jan LeCun pokazao da u mnogim praktičnim problemima ovo nije ozbiljan nedostatak.

Istorija

Prema različitim izvorima , osnove neprekidne bekpropagacije su izveli u kontekstu teorije kontrole Henri Dž. Keli 1960. godine i Artur E. Brajson 1961. Koristili su principe dinamičkog programiranja. Godine 1962. Stjuart Drejfus je objavio jednostavniji alat zasnovan samo na pravilu lanca. Brajson i Ho su to opisali kao višestepenu dinamičku sistemsku optimizaciju 1969.

Linainma je 1970. objavio opštu metodu za automatsko diferenciranje (AD) diskretnih povezanih mreža ugnježdenih diferencijabilnih funkcija. Ovo odgovara bekpropagaciji, koja je efikasna i za retke mreže.

Godine 1973. Drejfus je koristio bekpropagaciju kako bi prilagodio parametre kontrolora proporcionalno greški gradijenata. Godine 1974. Verbos je pomenuo mogućnost primene ovog principa na veštačke neuronske mreže, a 1982. godine je Linainma primenio AD metod na neuralne mreže na način koji se danas koristi.

Godine 1986. Rumelhart, Hinton i Vilijams su eksperimentalno pokazali da ova metoda može generisati korisna interna predstavljanja dolaznih podataka u skrivenim slojevima neuronskih mreža. Godine 1993, Van je bio prvi koji je pobedio na takmičenju za priznavanje međunarodnih uzoraka kroz bekpropagaciju.

Tokom 2000-ih godina za nju je opalo interesovanje, ali se vratilo u 2010-im, jer je korišćena od strane jeftinih, moćnih računarskih sistema zasnovanih na GPU-u.

Literatura

• Alpaydin, Ethem (2010). Introduction to Machine Learning. MIT Press. ISBN 978-0-262-01243-0. 
• Werbos, Paul John (1975). Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences. Harvard University. 
• Bryson, A. E.; Yu-Chi, Ho (01. 1. 1975). Applied Optimal Control: Optimization, Estimation and Control. CRC Press. ISBN 978-0-89116-228-5. 
• Werbos, Paul (1982). „Applications of advances in nonlinear sensitivity analysis”. System modeling and optimization (PDF). Springer. str. 762—770. 
• Russell, Stuart; Norvig, Peter. Artificial Intelligence A Modern Approach. str. 578. „The most popular method for learning in multilayer networks is called Back-propagation”