Created by Petteri Nevavuori.
Kirjana Goodfellow et al.: Deep Learning (2016)
Otsikot seuraavat pääotsikoiden tasolla kirjaa, mutta alaotsikot eivät aina.
Satunnaisalgoritmit jaetaan kahteen kategoriaan: Tarkan vastauksen palauttaviin Las Vegas -algoritmiin ja satunnaisen määrän virhettä sisältäviin Monte Carlo -algoritmiin. Koneoppimisessa käytetyt deterministiset likiarvoalgoritmit ovat luonteeltaan jälkimmäisiä, sillä tarkkoja vastauksia ei useinkaan voida saada - molemmat algoritmit ovat kuitenkin vahvasti edustettuja koneoppimisen kentässä.
Koneoppimisen tehtävät liittyvät usein Monte Carlo -ennusteen muodostamiseen opitusta todennäköisyysjakaumasta nostetuilla näytteillä.
Näytteistys eli näytteiden tuottaminen tarjoaa joustavan ja halvan tavan summien ja integraalien muodostamiseen. Mallinnustavasta riippuen summien muodostus voi olla mahdollista mutta ajallisesti haastavaa, tai vaihtoehtoisesti ylipäätään hankalaa. Näytteistyksellä voidaan joko nopeuttaa tai mahdollistaa näiden mallinnustilanteiden laskentoja. Näytteistys voi olla myös yksi mallinnuksen tavoitteista, etenkin generatiivisten mallien kanssa.
Monte Carlo -näytteistyksellä on mahdollista muodostaa likiarvoinen summa tai integraali tilanteessa, jossa sen laskenta on mahdotonta. Tällöin summaa tai integraalia käsitellään todennäköisyysjakauman odotusarvona vastaavan keskiarvon suhteen.
Summalle tämä tarkoittaa, että
$$ s = \sum_x p(x)f(x) = E_p[f(x)]$$ja integraalille
$$ s = \int p(x)f(x)dx = E_p[f(x)].$$Odotusarvoa $s$ voidaan arvioida likimääräisesti nostamalla $n$ näytettä todennäköisyysjakaumasta $p$ ja laskemalla niiden keskiarvon. Näin saadaan muodostettua ennuste
$$ \hat{s}_p = \frac{1}{n}\sum^n_{i=1, x \tilde{} p}f(x^{(i)}). $$Mikäli näytteiden oletetaan olevan toisistaan riippumattomia, suurten lukujen lain mukaan keskiarvo lähenee todellista odotusarvoa näytteiden lukumäärän kasvaessa rajatta. Keskiarvon lisäksi näytteistä lasketaan niiden hajonta. Näin saadaan muodostettua tiettyyn luottamusväliin sopiva ennuste summan odotusarvosta siten, että luottamusväli ilmaisee Monte Carlo -metodille ominaisen satunnaisen virheen keskimääräisesti.
Kaikki tämä on kuitenkin riippuvaista todennäköisyysjakaumasta $p$. Mikäli siitä ei voida helposti nostaa näytteitä, on todennäköisyysjakauman mallintamista lähestyttävä muilla keinoin. Yksi näistä keinoista on myöhemmin esiteltävä Monte Carlo Markovin ketju (Markov chain). Toinen on merkityksellisyyden mukaan näytteistys (importance sampling).
Integroitavan tai summattavan funktion erittelyssä merkittävä askel on todennäköisyysjakaumaa $p(x)$ ja odotusarvon määrityksen kohteena olevaa arvofunktiota $f(x)$ ilmaisevien osien määrittäminen. Yksiselitteistä ratkaisua ei tälle ole, sillä osiin eritelty alkuperäinen funktio $p(x)f(x)$ voidaan kirjoittaa aina muodossa
$$ p(x)f(x) = q(x)\frac{p(x)f(x)}{q(x)}. $$Mikä tahansa Monte Carlo -malli voidaan muuntaa merkityksellisyyden mukaan näytteistäväksi malliksi. Mikäli eriteltyjen osien $p$ ja $f$ määrittäminen riittävän tarkasti ei onnistu, voidaan silti pyrkiä määrittämään optimaalisin $q$ eli $q^*$, mitä kutsutaan merkityksellisyyden mukaan näytteistykseksi. Tällöin ennustettu Monte Carlo -näytteistyksen odotusarvo jakauman $q$ mukaan on
$$ \hat{s}_q = \frac{1}{n}\sum^n_{i = 1, x \tilde{} q}\frac{p(x^{(i)})f(x^{(i)})}{q(x^{(i)})}. $$Summan tai integraalin odotusarvo ei ole riippuvainen jakaumasta $q$, mutta kyseisen jakauman valinnalla on suurta merkitystä odotusarvon hajontaan. Pienin varianssi eli optimaalisin $q$ eli $q^*$ saavutetaan, kun
$$ q^*(x) = \frac{p(x) \mid f(x) \mid }{Z}, $$jossa $Z$ on näytteiden summan lukuun 1 normalisoiva vakio. Käytännössä paras valinta $q$:lle on varianssia riittävästi minimoiva mutta silti riittävän helposti näytteistettävissä oleva jakauma.
Toinen tapa lähestyä odotusarvon likimäärää $\hat{s}$ on käyttää vääristynyttä merkityksellisyyden mukaan näytteistystä (biased importance sampling, BIS). Tällöin normalisointia ei käytetä. Likiarvoinen odotusarvo on tällöin
$$\hat{s}_{BIS} = \frac{\sum^n_i \frac{\hat{p}(x_i)}{\hat{q}(x_i)}f(x_i)}{\sum^n_i \frac{\hat{p}(x_i)}{\hat{q}(x_i)}} .$$Näytteiden määrän kasvaessa rajatta muuntuu tämäkin odotusarvo vääristymättömäksi, mistä johtuen sitä kutsutaankin asymptoottisesti vääristymättömäksi.
Jakauman $q$ valinta on kaksiteräinen miekka. Hyvin valittuna se tehostaa Monte Carlo -menetelmän toimintaa huomattavasti, mutta huonosti valittuna huonontaa sitä merkittävästi. Datan $x$ ollessa moniulotteista on $q(x)$ ja $p(x)\mid f(x) \mid$ välisellä suhteella merkitystä. Mikäli termien välillä on epäsuhtaa suuntaan tai toiseen, ei merkityksellisyyden mukaan näytteistys toimi kunnolla. Tästä huolimatta menetelmää on käytetty monissa koneoppimisalgoritmeissa, syväoppivat menetelmät mukaan lukien. Etenkin hankalien näytteiden nostaminen useammin koulutuksen aikana voi vähentää gradienttien varianssia.
Usein tarkkojen näytteiden nostaminen on kuitenkin haastavaa. Syvien mallien kanssa näin on suuntaamattomien mallien kanssa. Tällöin Markovin ketjuna tunnnettu matemaattinen työkalu on avuksi, ja sitä hyödyntäviä Monte Carlo -ennusteita tuottavia malleja kutsutaan kootusti Markovin ketju Monte Carlo -malleiksi (MCMC). Nämä mallit toimivat parhaiten, kun niiden tuottamat todennäköisyydet ovat jotain muuta kuin täydellisen epätodennäköisiä ($p = 0$). Siksi energiapohjaiset mallit ovat suosittu valinta MCMC-menetelmän kanssa.
Energiapohjaisista malleista näytteistäminen on hankalaa, missä Markovin ketjun hyödyntäminen onneksi auttaa. Markovin ketju on iteratiivinen prosessi, joka alustetaan satunnaiseen tilaan $x$. Tämän jälkeen tilaa päivitetään, kunnes tila vastaa datantuottoprosessin $p(x)$ tuottamaa näytettä. Päivitys laskemalla tilalle uusi arvo $x'$ siirtymäjakaumasta $T(x' \mid x)$ ja asettamalla $x=x'$. Tila voi olla sekä diskreetti että jatkuva.
Menetelmän tavoitteena on toisin sanoen ottaa alkuperäisen tilan $x$ tuottanut jakauma $q(x)$ ja päivittää sitä iteratiivisesti aika-askelten määrällä $t$ niin kauan, että $q^{(t)}(x) \approx p(x)$. Koska päivittäminen eksponentiaalista, tietyin reunaehdoin menetelmä takaa $q$:n asettumisen tasapainoiseen jakaumaan (equilibrium distribution). Siirtymäjakaumalla $T$ on tällöin eniten vaikututusta siihen, muuttuuko $q$ ajan myötä vastaamaan $p$:tä.
Markovin ketjun koulutusta kutsutuaan sisäänajoksi (burn-in). Sisäänajetusta ja tasapainotilan saavuttaneesta Markovin ketjusta voidaan nostaa äärettömästi näytteitä, jotka ovat kaikki samasta jakaumasta. Ne ovat myös keskenään korreloivia, minkä vuoksi perättäisten näytteiden käyttö ei ole mielekästä i.i.d.-oletuksen näkökulmasta. Tätä voidaan kuitenkin kiertää ottamalla vain joka n:s näyte tai käyttämällä monta ketjua rinnan. Syväoppivien menetelmien kanssa käytetään tavanomaisesti koulutuksen osajoukon näytemäärää vastaavaa määrää Markovin ketjuja.
Tasapainotilan saavuttamiseen menevän ajan määrittely ennalta ja saavutetun tilan todentaminen ei ole yksiselitteistä. Selkeää teoriaa tälle ei vielä ole. Siksi perinteisesti Markovin ketjuja koulutetaan jonkin raaka-arvion mukaisen ajan verran, minkä jälkeen todetaan ketjun tila heuristisesti, eli näyte näytteeltä vertailemalla.
Markovin ketjun todennäköisyysjakauman $q$ käyttökelpoisuuden varmiastamista ei ole vielä käsitelty. Tärkeimmässä roolissa on jo auemmin mainittu siirtymäjakauman $T$ valinta. Myöhemmin esiteltävien keinojen lisäksi yksinkertainen tapa on käyttää Gibbsin näytteistystä (Gibbs sampling). Tällöin siirtymäjakaumasta näytteistämiseksi valitaan yksi näytteiden muuttujista, joka näytteistetään ehdollisesti riippummattomana suuntaamattomasta energiapohjaisesta graafimallista. Esimerkiksi RBM-mallin piilomuuttujat voidaan kaikki näytteistää samalla kertaa, sillä ne ovat ehdollisesti riippumattomia.
Markovin ketjujen taipumus näytteistää peräkkäisesti toisiinsa vahvasti kytköksissä olevia eli korreloivia näytteitä on ongelmallista. Esimerkin vuoksi tilanne on hieman samankaltainen, kuin syväoppivan mallin optimoinnissa. Mikäli Markovin ketju löytää jonkun alueen eli moodin (mode), jossa energiafuntio saadaan pienenemään, se jää helposti siihen jumiin. Tilanne vastaa käytännössä lokaalien minimien ongelmaa syväoppivien menetelmien optimoinnissa. Opittava jakauma $q$ voi kyllä saavuttaa tasapainon, muttei parasta vastaavuutta tavoiteltavaan jakaumaan $p$ nähden.
On myös tavallista, että mallinnettavassa kohteessa on itsessään monta eri moodia. Tällöin MCMC-mallin kyvyttömyys nousta korkeamman energian muurien yli moodista toiseen asettaa koko näytteistysprosessin luotettavuuden vaakalaudalle. Tällöin jopa tasapainon saavuttaminen on haaste ja hyvin hidasta. Kirjan kuva 17.2. kuvaa tilannetta hyvin. Siinä on rinnan sekä Gibbsin näytteistyksellä (suuntaamaaton graafi, vasen kuva) että edeltävien todennäköisyyksien menetelmällä (suunnattu graafi, oikea kuva) tuotettuja näytteitä.
Lukusuunta on kuvakohtaisesti rivi kerrallaan vasemmalta oikealle. Moodista, eli tässä tapauksessa numerosta, toiseen hyppääminen onnistuu heikosti Gibbsin näytteistyksellä, kun taas GAN-verkon eli suunnatun graafin näytteet eroavat selkeästi toisistaan.
Moodeja, jotka eroavat selkeästi toisistaan, on hankala sekoittaa. Eräs tapa helpottaa tätä on pienentää eri moodien välisten matalamman todennäköisyyden eli korkeamman energian muurien huippuja. Tämä helpottaa näytteistyksen hyppäystä moodista toiseen. Energiapohjaisilla malleilla tämä on melko yksinkertaista. Todennäköisyysjakaumaa skaalataan lisäparametrilla, jolla huippuja saadaan leikattua. Tätä paramteria nimitetään käänteiseksi lämpötilaksi (reciprocal temperature) ja merkitään kirjassa $\beta$.
Todennäköisyyden pienetessä eli energian eli lämpötilan kasvaessa $\beta$ pienenee, kun taas lämpötilan pienetessä $\beta$ kasvaa. Näin huiput ja laaksot tasoittuvat. Temperoinniksi kutsutaan yleistä strategiaa käyttää yhtä pienempää $\beta$:n arvoa nopean moodista toiseen hyppimisen sallimiseksi. Käyttämällä eri lämpötiloja saadaan vaihtelevuutta sekä korkean tarkkuuden ($q \approx p, \beta > 1$) ja moodien vaihtelevuuden ($\beta < 1$) välillä.
Piilomuuttujia sisältävien mallien kanssa on tavanomaista lisätä syvyyttä paremman suorituskyvyn toivossa. Monte Carlo -näytteistyksessä piilomuuttujien lisääminen vaikuttaa kuitenkin siten, että näytteiden tuottaminen ehdollisessta jakaumasta $p(x \mid h)$ on helpompaa. Se juontanee juurensa saumattomampaan piilokuvaukseen, joka saavutetaan syvemmillä malleilla.