Eksponenttiperheen upotusmenetelmä

Eksponenttiperheen upotusmenetelm¨ a

Jonna Ikonen

Pro Gradu- tutkielma It¨a-Suomen yliopisto Fysiikan ja

matematiikan laitos Syksy 2017

Sis¨ alt¨ o

1 Johdanto 1

2 Tarvittavia m¨a¨aritelmi¨a 3

3 Dimension pienent¨amismenetelmist¨a 6

3.1 P¨a¨akomponenttianalyysi . . . 7

3.2 Moniulotteinen skaalaus . . . 11

3.3 Locally linear embedding . . . 12

3.4 Menetelmien hyvyydest¨a . . . 17

4 Eksponenttiperheen upotusmenetelm¨a 18 4.1 Eksponenttiperhe . . . 18

4.2 Sanaupotukset . . . 23

4.3 Eksponenttiperheen upotusmenetelm¨a . . . 28

4.3.1 Teoriaa . . . 29

4.3.2 Parametrien estimointi . . . 34

5 Esimerkkej¨a eksponenttiperheen upotusmenetelm¨an k¨ayt¨ost¨a 41 5.1 Bernoullin jakauma . . . 41

5.2 Normaalijakauma . . . 43

6 Loppup¨a¨atelm¨at 47

IT ¨A-SUOMEN YLIOPISTO,

Luonnontieteiden ja mets¨atieteiden tiedekunta, Joensuu Fysiikan ja matematiikan laitos

Matematiikka

Opiskelija, Jonna Ikonen:

Pro gradu-tutkielma 51 s.

Pro gradu- tutkielman ohjaajat: Jukka Tuomela, Ville Hautam¨aki 12.10.2017

Tiivistelm¨ a

Erilaisten data-aineistojen dimension, eli ulottuvuuden, kasvaessa tarvitaan uusia menetelmi¨a, joiden avulla aineistojen informaation tiivist¨aminen on- nistuu ilman sen oleellista h¨avi¨amist¨a. Tutkielmassa k¨ayd¨a¨an l¨api vertailun vuoksi nykyisist¨a dimensionpienent¨amismenetelmist¨a p¨a¨akomponenttianalyysi, moniulotteinen skaalaus ja LLE eli locally linear embedding-menetelm¨a. Tut- kielmassa keskityt¨a¨an kuitenkin uudempaan eksponenttiperheen upotusme- netelm¨a¨an ja sen teoriaan. Eksponenttiperheen upotusmenetelm¨an tarkoitus on upotetun eksponenttiperheen jakauman ja parametrit yhdist¨av¨an raken- teen avulla saada tarkasteltavasta aineistosta esiin hy¨odyllisi¨a ominaisuuk- sia. Apuna k¨aytet¨a¨an my¨os havaintopisteiden konteksteja. Tutkielman lopus- sa k¨ayd¨a¨an l¨api esimerkkej¨a eksponenttiperheen upotusmenetelm¨ast¨a sek¨a bernoull-jakautuneen, ett¨a normaalijakautuneen aineiston tapauksessa.

Avainsanat: Eksponenttiperheen upotusmenetelm¨a, Upotettu rakenne, Di- mension pienent¨aminen, Eksponenttiperhe, Sanaupotukset

UNIVERSITY OF EASTERN FINLAND, Faculty of Science and Forestry, Joensuu Department of Physics and Mathematics Mathematics

Student, Jonna Ikonen:

Master’s Thesis, 51 p.

Supervisors of the Master’s Thesis: Jukka Tuomela, Ville Hautam¨aki 12.10.2017

Abstract

When the dimension of datasets grow, new methods are needed to compress the information without losing anything essential. This thesis compares cur- rent dimension reduction methods: principal component analysis, multidi- mensional scaling (MDS) and locally linear embedding (LLE), although it is focused on newer exponential family embeddings -method and the theory of it. The function of exponential family embedding method is to get useful features out of data by using embedded exponential family distribution, and parameters sharing structure. Contexts of observations are also used. Finally examples of exponential family embedding method with bernoull-distributed data and normally distributed data are used.

Keywords: Exponential family embeddings, Embedded structure, Dimension reduction, Exponential family, Word embeddings

Lyhenneluettelo

SGD Stochastic gradient descent-menetelm¨a CBOW Continuous bag of words-malli

LLE Locally linear embedding-menetelm¨a MDS Multidimensional scaling-menetelm¨a PCA Principal component analysis

Symbolit

log Luonnollinen logaritmi

x Reaalilukuisista muuttujista k¨aytet¨a¨an pieni¨a kirjaimia x Vektoreista k¨aytet¨a¨an pieni¨a paksunnettuja kirjaimia X Matriiseista k¨aytet¨a¨an paksunnettuja isoja kirjaimia

1 Johdanto

T¨am¨an tutkielman tarkoituksena on tutustua eksponenttiperheen upotusme- netelm¨a¨an (exponential family embeddings, EF-EMB) [8]. Tutkielmassa k¨ayd¨a¨an l¨api mallin teoriaa ja esimerkkej¨a mallin k¨ayt¨ost¨a, sek¨a verrataan mallia teo- reettiselta n¨ak¨okannalta muihin k¨ayt¨oss¨a oleviin menetelmiin. Eksponentti- perheen upotusmenetelm¨a on melko uusi ja siit¨a kertovan l¨ahdekirjallisuuden m¨a¨ar¨a on hyvin rajallinen. Eksponenttiperheen upotusmenetelm¨an tarkoi- tuksena on selvitt¨a¨a hyvin laajojen data-aineistojen ominaisuuksia ja ha- vaintojen jakautumista aineistossa. Eksponenttiperheen upotusmenetelm¨an tarkoitus on yleist¨a¨a sanaupotusten (word embeddings) idea my¨os muunlai- siin moniulotteisiin aineistoihin. Sanaupotusten avulla esitet¨a¨an esimerkiksi sanoja matriisien avulla muuttamalla ne numeroarvoisiksi vektoreiksi.

Luvussa kaksi k¨ayd¨a¨an l¨api muutamia tutkielmassa tarvittavia m¨a¨aritelmi¨a.

Luvussa kolme esitell¨a¨an muutamia yleisimpi¨a menetelmi¨a, joita k¨aytet¨a¨an laajojen data-aineistojen visualisointiin aineiston dimensiota pienent¨am¨all¨a.

Yleisimpiin menetelmiin on otettu k¨asitelt¨aviksi p¨a¨akomponenttianalyysi, moniulotteinen skaalaus ja locally linear embedding-menetelm¨a. Tarkoituk- sena on tutustua muihin nykyisin enemm¨an k¨ayt¨oss¨a oleviin menetelmiin ennen eksponenttiperheen upotusmenetelm¨an k¨asittely¨a vertailun vuoksi.

Luvussa nelj¨a k¨asitell¨a¨an eksponenttiperheen upotusmenetelm¨a¨a ja sen ymm¨ar- t¨amisen kannalta olennaista taustateoriaa. Aluksi l¨ahdet¨a¨an liikkeelle yleisen eksponenttiperheen m¨a¨arittelyst¨a sek¨a teoriasta ja todistetaan tutkielmassa tarvittavia lauseita. Sen j¨alkeen kerrotaan taustateoriaa ja muutamia esi- merkkej¨a sanaupotus-malleista. T¨am¨an j¨alkeen siirryt¨a¨an Eksponenttiper- heen upotusmenetelm¨an teoriaan ja ominaisuuksiin. Ensin m¨a¨aritell¨a¨an me- netelm¨an k¨asitteit¨a ja jakauma sek¨a parametrit. Sen j¨alkeen k¨ayd¨a¨an l¨api parametrien estimointi, jossa apuna k¨aytet¨a¨an regularisaatiota sek¨a stochas- tic gradient descent-menetelm¨a¨a.

Luvussa viisi k¨asitell¨a¨an esimerkkej¨a mallin k¨ayt¨ost¨a. Ensimm¨ainen esimerk- ki on tilanteesta, jossa tutkittava aineisto on Bernoulli-jakautunut ja toisen esimerkin tapauksessa aineisto on normaalijakautunut.

Luvussa kuusi on loppup¨a¨atelmi¨a eksponenttiperheen upotusmenetelm¨ast¨a ja pohdintaa sen eroista muihin tutkielmassa esiteltyihin menetelmiin verrat- tuna. Lukijan oletetaan osaavan matematiikkaa v¨ahint¨a¨an aineopintojen laa- juisesti. Erityisesti ty¨oss¨a k¨aytet¨a¨an matriisilaskentaa ja todenn¨ak¨oisyyslaskentaa.

2 Tarvittavia m¨ a¨ aritelmi¨ a

Luvussa k¨ayd¨a¨an l¨api tutkielmassa tarvittavia m¨a¨aritelmi¨a.

Huomautus 2.1. Tutkielmassa kertolaskut matriisien ja vektoreiden v¨alill¨a tai niill¨a kesken¨a¨an ovat normaaleja matriisien v¨alisi¨a kertolaskuja, ellei toisin mainita. Vektorien v¨alinen pistetulo eli skalaaritulo eli sis¨atulo m¨a¨aritell¨a¨an tutkielmassa transpoosin avulla normaalina matriisien v¨alisen¨a kertolaskuna seuraavasti: jos x ja y ovat vektoreita, niin pistetulo:

x·y=xy^T.

Olkoon X = (X₁, X₂, . . . , X_d) satunnaismuuttujavektori, jossa jokainen X_i on satunnaismuuttuja. Satunnaismuuttujia on yhteens¨a d kappaletta. Arvot xji ∈R, j = 1, . . . , n ovat havaintoja t¨ast¨a satunnaismuuttujasta. T¨ass¨a ha- vaitun arvonx_ji ensimm¨ainen indeksij viittaa tiettyyn havaittuun arvoon ja toinen indeksiiviittaa tiettyyn satunnaismuuttujaan, jonka arvo on kyseess¨a.

Havaintoja on yhteens¨an kappaletta jokaisesta satunnaismuuttujasta.

M¨a¨aritelm¨a 2.2. Edell¨a m¨a¨aritellyn satunnaismuuttujavektorin yksitt¨aisen satunnaismuuttujan X_i odotusarvo E(X_i)∈R m¨a¨aritell¨a¨an seuraavasti:

E(Xi) =

n

X

j=1

xjipji.

Arvon x_ji ensimm¨ainen alaindeksi j viittaa tiettyyn havaintoon satunnais- muuttujasta ja toinen alaindeksi i tietyyn satunnaismuuttujaan aineistossa.

Arvoa xji vastaava todenn¨ak¨oisyys on pji ja havaintoja on yhteens¨a n kap- paletta.

Huomautus 2.3. Jos aineiston jakaumaa ei t¨asm¨allisesti tiedet¨a, niin satun- naismuuttujan odotusarvon estimaattina k¨aytet¨a¨an satunnaismuuttujan ha- vaintojen keskiarvoa, jolloin:

E(Xi) = 1 n

n

X

j=1

xji.

M¨a¨aritelm¨a 2.4. SatunnaismuuttujavektorinX tietyn satunnaismuuttujan X_i varianssi Var(X_i)∈R on:

Var(X_i) = E((X_i−E(X_i))²) = E((X_i−

n

X

i=1

x_jip_ji)²) =

n

X

i=1

(p_ji(x_ji−

n

X

i=1

x_jip_ji)²).

M¨a¨aritelm¨a 2.5. Kahden satunnaismuuttujanX_i jaX_j v¨alinenkovarianssi Cov(X_i, X_j)∈R m¨a¨aritell¨a¨an seuraavasti:

Cov(X_i, X_j) = E[(X_i−E(X_i))(X_j−E(X_j))]

=E[X_iX_j−E(X_i)E(X_j)]

=E[X_iX_j−

n

X

k=1

x_kip_ki

! _n X

k=1

x_kjp_kj

! ]

Satunnaismuuttujavektorin X kovarianssimatriisi on muotoa:

Cov(X) = Σ=











Cov(X₁, X₁) Cov(X₁, X₂) . . . Cov(X₁, X_d) Cov(X₁, X₂) Cov(X₂, X₂) . . . Cov(X₂, X_d)

... ... . .. ...

Cov(X1, Xd) Cov(X2, Xd) . . . Cov(Xd, Xd)











Huomautus 2.6. SatunnaismuuttujanX_ikovarianssi itsens¨a kanssa on satun- naismuuttujan varianssi:

Cov(X_i, X_i) =E[(X_i−E(X_i))(X_i−E(X_i))] =E[(X_i−E(X_i))²] = Var(X_i) Lause 2.7. Kovarianssimatriisi voidaan esitt¨a¨a my¨os seuraavalla tavalla:

Σ=E((X−E(X))(X−E(X))^T)

Todistus.

Σ=











Cov(X1, X1) Cov(X1, X2) . . . Cov(X1, Xd) Cov(X₁, X₂) Cov(X₂, X₂) . . . Cov(X₂, X_d)

... ... . .. ...

Cov(X₁, X_d) Cov(X₂, X_d) . . . Cov(X_d, X_d)











=











E[(X₁−E(X₁))(X₁−E(X₁))] . . . E[(X₁−E(X₁))(X_d−E(X_d))]

E[(X₁−E(X₁))(X₂−E(X₂))] . . . E[(X₂−E(X₂))(X_d−E(X_d))]

... . .. ...

E[(X1−E(X1))(Xd−E(Xd))] . . . E[(Xd−E(Xd))(Xd−E(Xd))]











=E





















X1−E(X1) X₂−E(X₂)

... X_d−E(X_d)











X₁−E(X₁) X₂−E(X₂) . . . X_d−E(X_d)











=E((X−E(X))(X−E(X))^T)

M¨a¨aritelm¨a 2.8. Kahden satunnaismuuttujanX_i ja X_j v¨alinen korrelaatio m¨a¨aritell¨a¨an lausekkeella:

Corr(X_i, X_j) = Cov(X_i, X_j) pVar(X_i)Var(X_j),

miss¨a kovarianssi ja varianssit lasketaan vastaavasti kuin edellisiss¨a m¨a¨aritelmiss¨a.

3 Dimension pienent¨ amismenetelmist¨ a

Dimension pienenent¨amismenetelm¨at (dimensionality reduction methods)pyr- kiv¨at siihen, ett¨a dimensioltaan laajojen data-aineistojen visualisointia hel- potetaan pienent¨am¨all¨a aineiston dimensiota ilman, ett¨a aineistossa tapahtuu oleellista informaation h¨avi¨amist¨a. Dimensio tarkoittaa aineiston eri muut- tujien lukum¨a¨ar¨a¨a. Aineistoa yritet¨a¨an k¨asitell¨a ja muokata siten, ett¨a siit¨a on helpompi havaita eroja eri havaintojen tai niiden ryhmittymien v¨alill¨a esimerkiksi muokkaamalla aineisto siten, ett¨a se voidaan esitt¨a¨a kaksiulottei- sessa kuvassa. Luvun tarkoitus on tutustuttaa lukija suosituimpiin yleisess¨a k¨ayt¨oss¨a oleviin dimensionpienent¨amismenetelmiin ennen kuin seuraavassa kappaleessa siirryt¨a¨an tutkielmassa k¨asitelt¨av¨a¨an uudempaan menetelm¨a¨an.

Oletetaan, ett¨a aineisto X ⊂R^d ja X ={x₁,x₂, . . . ,x_i, . . . ,x_n}. Aineistoa voidaan ajatella pisteparvena, jossa on n havaintopistett¨a ja jokainen ha- vainnoista kuuluu R^d avaruuteen. Havaintomatriisina sama aineisto voidaan esitt¨a¨a muodossa:

X = (x₁,x₂, . . . ,x_i, . . . ,x_n)∈R^d×n, jossa jokainen

x_i =

















 x_i1 xi2

... x_ij

... x_id

















 ,

eli jokainen x_i ∈R^d on vektori. Havaintoja on nyt n kappaletta ja eri muut- tujien lukum¨a¨ar¨a on d eli aineiston dimensio on d.

Dimension pienenent¨amismenetelmien tarkoitus on muodostaam-dimensioinen projektio d-dimensioiselle havaintoaineistolle siten, ett¨am << d,eli uusi di- mensio m on huomattavasti vanhaa dimensiota d pienempi. Dimension pie- nennyksen j¨alkeen saadaan aineistoY ⊂R^mmiss¨aY ={y₁,y₂, . . . ,y_i, . . . ,y_n}.

Havaintomatriisina Y ∈R^m×n. Luonnollisesti graafinen visualisointi on hel- pointa, jos pystyt¨a¨an valitsemaanm= 2 taim= 3. T¨am¨a ei kuitenkaan aina onnistu ilman oleellista informaation h¨avi¨amist¨a. Luvussa esitell¨a¨an muuta-

mia eniten k¨aytettyj¨a dimensionpienent¨amismenetelmi¨a yksi kerrallaan ja n¨aiden menetelmien matemaattisia perusominaisuuksia.

3.1 P¨ a¨ akomponenttianalyysi

P¨a¨akomponenttianalyysi (principal component analysis, PCA)[7] on ominais- vektoreihin perustuva menetelm¨a, joka on suunniteltu mallintamaan lineaa- rista vaihtelevuutta suurissa havaintoaineistoissa [7]. P¨a¨akomponenttianalyysi on vastaava menetelm¨a kuin singulaariarvohajotelma (Singular value decom- position, SVD), eri aloilla on totuttu k¨aytt¨am¨a¨an eri nime¨a menetelm¨alle.

P¨a¨akomponenttianalyysi voidaan m¨a¨aritell¨a kahdella eri tavalla, jotka mo- lemmat johtavat samaan algoritmiin [5]. Ensimm¨aiseksi se voidaan m¨a¨aritell¨a ortogonaalisena projektiona havaintoainestosta pienempidimensioiseen line- aariavaruuteen siten, ett¨a projisoidun aineiston varianssi on maksimoitu [5].

M¨a¨aritelm¨ass¨a lasketaan lineaariset projektiot suurimmalle varianssille ai- neiston kovarianssimatriisin ominaisvektoreista [7]. T¨am¨a k¨ayd¨a¨an tarkem- min l¨api alempana. Toiseksi p¨a¨akomponenttianalyysi voidaan m¨a¨aritell¨a line- aarisena projektiona, joka minimoi keskim¨a¨ar¨aisen virhefunktion projektios- sa. T¨am¨a m¨a¨aritell¨a¨an keskim¨a¨ar¨aisen¨a havaintopisteiden ja niiden projek- tioiden v¨alisin¨a et¨aisyyksin¨a. P¨a¨akomponentianalyysin tulokset ovat samoja molemmilla eri m¨a¨arittelytavoilla[5].

Seuravaksi k¨ayd¨a¨an tarkemmin l¨api ensimm¨aist¨a eli varianssin maksimointiin perustuvaa p¨a¨akomponenttianalyysin m¨a¨aritelm¨a¨a. Oletetaan, ett¨a havain- toaineistossa X onderi satunnaismuuttujaa ja n eri havaintoa. Kiinnostuk- sen kohteena on varianssi ja kovarianssi tai korrelaatio satunnaismuuttujien v¨alill¨a. Tarkoituksena on etsi¨a kuvausZ =A^TX. T¨ass¨aA⊂R^d×n on jouk- ko vektoreita: A = {α₁,α₂, . . . ,α_m}. Tarkoituksena on etsi¨a ensin vektori α1 ∈R^d siten, ett¨a kuvauksen varianssi Var(α^T₁X) on mahdollisimman suu- ri, jolloin vakiovektorin α₁ avulla selitet¨a¨an mahdollisimman suuri osa alku- per¨aisen aineiston vaihtelusta. Nyt α^T₁X ∈R^1×n[3].

Seuraavaksi etsit¨a¨an edellisen kuvauksenα^T₁X kanssa korreloimaton kuvaus α^T₂X, siten ett¨a etsit¨a¨an vastaavasti vektori α₂, jolla kuvauksen varianssi saadaan mahdollisimman suureksi [3]. Korreloimattomuus kuvausten v¨alill¨a tarkoittaa sit¨a, ett¨a

Corr(α^T₁X,α^T₂X) = 0

⇔Cov(α^T₁X,α^T₂X) =0

Vektoreiden etsimist¨a jatketaan eteenp¨ain niin pitk¨alle kun l¨oydet¨a¨an vek- toreita α_i, joiden muodostama funktio α_iX ei korreloi mink¨a¨an aikaisem- man kuvauksenα^T_kX kanssa. Funktionα^T_kX sanotaan olevan k:s PC, eli k:s p¨a¨akomponentti. P¨a¨akomponenttien tarkoitus on yhdist¨a¨a samaan kompo- nenttiin useamman alkuper¨aisen muuttujan vaihtelu. Ensimm¨ainen p¨a¨akompo- nentti selitt¨a¨a mahdollisimman paljon alkuper¨aisten muuttujien vaihtelusta, jonka lis¨aksi seuraava p¨a¨akomponentti selitt¨a¨a mahdollisimman paljon vaih- telusta, jota ensimm¨ainen p¨a¨akomponentti ei viel¨a selit¨a. Edelleen seuraava uusi p¨a¨akomponentti selitt¨a¨a aina mahdollisimman suuren osan vaihtelusta, joka on viel¨a selitt¨am¨att¨a[3][6].

Edell¨a kuvattu kuvaus saadaan selvitetty¨a ominaisarvojen avulla. P¨a¨akompo- nenttien etsinn¨ass¨a k¨aytet¨a¨an apuna havaintoaineiston kovarianssimatriisia Σ, ja lausetta 2.7. Kovarianssimatriisissa on laskettuna kaikkien muuttu- jien v¨aliset keskin¨aiset kovarianssit. Kovarianssimatriisi on symmetrinen ne- li¨omatriisi[3].

Huomautus 3.1. Jos kovarianssimatriisia ei tiedet¨a, niin sen estimaattina k¨aytet¨a¨an otoksesta laskettua kovarianssimatriisia. Kovarianssimatriisin si- jasta voidaan k¨aytt¨a¨a my¨os korrelaatiomatriisia, jossa kovarianssien tilalla on muuttujien v¨alinen korrelaatio. T¨am¨a on suositeltavaa varsinkin jos muuttu- jat ovat yhteismitattomia. Korrelaatiomatriisin tilanteessa kaikki muuttujat normitetaan siten, ett¨a niill¨a on sama keskiarvo ja hajonta, jolloin muuttu- jien vaihtelu on samanarvoista [6][3].

Kovarianssimatriisin ominaisarvot λ_k saadaan seuraavasta yht¨al¨ost¨a:

det(Σ−λ_kI) = 0

Koska kovarianssimatriisi on symmetrinen neli¨omatriisi kaikki ominaisarvot ovat reaalisia.

Ominaisarvojen avulla saadaan ominaisvektoritv_k ∈R^dseuraavasta yht¨al¨ost¨a:

(Σ−λ_kI)v_k = 0.

Lause 3.2. Voidaan osoittaa, ett¨a kuvauksen varianssi:

Var(α^T_kX) =α^T_kΣα_k=λ_k,

miss¨a λ_k on kovarianssimatriisin Σ k:nneksi suurin ominaisarvo. N¨ain ol- len kovarianssimatriisin Σ suurin ominaisarvo on samalla kuvauksen suurin mahdollinen varianssi.

Todistus. Kuvauksen odotusarvo:

E(α^T_kX) = α^T_kE(X) Joten varianssi:

Var(α^T_kX) = Cov(α^T_kX,α^T_kX)

=E((α^T_kX −E(α^T_kX))(α^T_kX −E(α^T_kX))^T)

=E((α^T_kX −α^T_kE(X))(α^T_kX −α^T_kE(X))^T)

=E((α^T_k(X−E(X))(α^T_k(X−E(X))^T)

=E((α^T_k(X−E(X))((X−E(X))^Tαk)

=α^T_kE((X −E(X))((X −E(X))^T)αk

=α^T_kΣαk

Varianssin maksimi vektorinα_ksuhteen saadaan derivoimalla. Samalla rajoi- tetaanα^T_kα_k= 1 jolloin ehk¨aist¨a¨ankα_kk → ∞. Apuna k¨aytet¨a¨an Lagrangen kerrointa jota kuvaa muuttuja βk.

F(α_k, β_k) =α^T_kΣα_k+β_k(1−α^T_kα_k).

T¨am¨an derivaataksi saadaan:

∇_αkF = (Σ+Σ^T)α_k−2β_kα_k Koska Σon symmetrinen matriisi saadaan:

= 2Σα_k−2β_kα_k.

Kun derivaatta asetetaan nollaksi saadaan kriittiset pisteet yht¨al¨ost¨a Σα_k =β_kα_k,

joten vektorin α_k t¨aytyy olla matriisin Σ ominaisvektori v_k ja kertoimen β_k t¨aytyy olla matriisin Σk:nneksi suurin ominaisarvo λ_k. Jos yht¨al¨o¨a viel¨a kerrotaan vasemmalta puolelta vektorilla α^T_k ja k¨aytet¨a¨an aikaisempaa ra- joitetta α^T_kα_k = 1 saadaan kuvauksen varianssi muotoon:

α^T_kΣα_k=λ_k,

joten varianssi maksimoituu kun α_k on ominaisvektoreista se jolla on suurin ominaisarvo.

Edellisest¨a saadaan, ett¨a k:nnen p¨a¨akomponentin α^T_kX vektori α_k saadaan, kun kovarianssimatriisista Σotetaan sen k:nneksi suurimman ominaisarvon λ_k ominaisvektori v_k [3]:

α^T_kX =v^T_kX.

Ominaisarvojen summa on sama kuin kovarianssimatriisin diagonaaliarvo- jen summa. P¨a¨akomponenttien varianssien summa on siis sama kuin alku- per¨aisten muuttujien varianssien summa ja n¨ain ollen p¨a¨akomponentit se- litt¨av¨at kaiken alkuper¨aisen havaintomatriisin vaihtelusta. Yksitt¨aisen p¨a¨akom- ponentinα_kselitt¨am¨a osuus voidaan laskea ominaisarvojen avulla seuraavasti [6]:

λ_k Pd

i=1λ_i.

Menetelm¨an avulla lasketuista p¨a¨akomponenteista t¨aytyy erikseen viel¨a p¨a¨att¨a¨a, kuinka monta suurinta otetaan jatkotarkasteluihin mukaan. Yleisen¨a s¨a¨ant¨on¨a voidaan pit¨a¨a komponenttien ottamista mukaan, kunnes niiden selitt¨am¨a ko- konaisvaihtelu ylitt¨a¨a 80−90% kaikesta vaihtelusta. Valittujen komponent- tien lukum¨a¨ar¨amon aineiston uusi dimensio. Valittujen komponenttien omi- naisvektorit v_k ∈ R^d asetetaan matriisiin V ∈ R^d×m. Nyt uudet havainto- vektorit z_i ∈Rⁿ saadaan kuvauksella

Z =V^TX,

miss¨a Z ∈ R^m×n on matriisi, josta saadaan m kappaletta uusia havainto- vektoreita z_i. Toisin sanoen alkuper¨aisen aineiston X vektoreiden x_i koor- dinaatit korvataan vektoreiden z_i koordinaateilla, jolloin projektio saadaan muodostettua[6].

3.2 Moniulotteinen skaalaus

Moniulotteinen skaalaus (multidimensional scaling, MDS)[5] on p¨a¨akomponentti- analyysin tapaan ominaisvektoreihin perustuva menetelm¨a, joka pyrkii mal- lintamaan havaintojen v¨alist¨a vaihtelevuutta suurissa havaintoaineistoissa [7]. Sill¨a pyrit¨a¨an konstruoimaan otosyksikk¨ojen v¨aliset suhteet k¨aytt¨am¨all¨a pelk¨ast¨a¨an et¨aisyysmatriisia. Klassisessa MDS-menetelm¨ass¨a tarkoituksena on laskea aineistolle pienidimensioinen projektio s¨ailytt¨aen samalla niin hy- vin kuin mahdollista parittaiset et¨aisyydet havaintopisteiden v¨alill¨a. Jos esi- merkiksi tied¨amme et¨aisyydet tiettyjen kaupunkien v¨alill¨a MDS menetelm¨a yritt¨a¨a uudelleen muodostaa kartan, jonka perusteella n¨am¨a alkuper¨aiset et¨aisyydet on laskettu. Visualisoinnin kannalta uudeksi dimensioksi kannat- taa valita enint¨a¨an 2 tai 3, jolloin tulkinta on helpointa. MDS-menetelm¨ast¨a on erilaisia sovelluksia, esimerkiksi klassinen MDS [6], metrinen MDS [6] ja ei-metrinen MDS [6]. Erilaisia laskentamenetelmi¨a on n¨ain ollen my¨os monia [7] [6][5].

Klassisessa menetelm¨ass¨a et¨aisyys lasketaan Euklidisena et¨aisyyten¨a. L¨aht¨okoh- tana menetelm¨ass¨a on havaintojen i ja j v¨aliset parittaiset et¨aisyydet q_ij. MDS on iteratiivinen menetelm¨a, jossa ensiksi arvioidaan uudet koordinaa- tit ja sitten tiettyj¨a kriteereit¨a k¨aytt¨aen niit¨a pyrit¨an t¨asment¨am¨a¨an. Ensiksi p¨a¨atet¨a¨an haluttu uusi dimensio m. Menetelm¨ass¨a arvioidaan ensin kaikkien havaintojen koordinaatit halutussa uudessa dimensiossa ja saatujen koordi- naattien avulla lasketaan havaintojen v¨aliset uudet et¨aisyydet dij. Esimer- kiksi kun uusi dimensio m = 2 et¨aisyydet arvioitujen uusien koordinaattien (x_i, y_i) ja (x_j, y_j) v¨alill¨a lasketaan seuraavasti:

d_ij = q

(x_i−x_j)²+ (y_i−y_j)².

Et¨aisyyksien q_ij ja d_ij v¨alille lasketaan regressiosuora. Regressio voi olla esi- merkiksi lineaarinen, polynominen tai monotoninen. Lineaarisessa tapauk- sessa se on muotoa:

d_ij =a+bq_ij +e_ij,

miss¨a a ja b ovat vakiokertoimia ja e virhetermi. Estimoidun mallin avulla havaitut et¨aisyydet q_ij skaalataan mahdollisimmann hyvin vastaamaan ar- vioituja et¨aisyyksi¨ad_ij testisuureen ST avulla:

ST =

P(d_ij −dˆ_ij)² Pdˆ²_ij

!¹₂

Testisuurretta ST kutsutaan stressiksi (stress formula), koska se arvioi sit¨a, ett¨a kuinka paljon koordinaattien estimaatteja ˆd_ij on muutettava, ett¨a uu- det et¨aisyydet dij mahdollisimman hyvin vastaavat alkuper¨aisi¨a et¨aisyyksi¨a q_ij. Regressiota ja testisuureen laskemista toistetaan, kunnes ei saada en¨a¨a parempia tuloksia eli kunnes testisuure ei en¨a¨a pienene. Lopputuloksena saa- daan uudet koordinaatit m-ulotteisessa avaruudessa [6].

IM (Isomap)-menetelm¨a on MDS-menetelm¨an muunnelma ep¨alineaarisille aineistoille. IM-menetelm¨a k¨aytt¨a¨a pisteiden v¨alisen¨a et¨aisyyten¨a euklidi- sen et¨aisyyden sijasta ep¨alineaarisia polkuja. Menetelm¨ass¨a muodostetaan ymp¨arist¨ograafi G, joka on painotettu alkuper¨aisill¨a havaintojen v¨alisill¨a ly- himmill¨a et¨aisyyksill¨a DG ∈ R^n×n k:n l¨ahimm¨an naapurin kanssa. Graafis- sa solmuina ovat siis alkuper¨aiset havainnot x_i, i = 1, . . . , n ja jokaisesta havainnosta on piirretty havaintojen v¨alisell¨a et¨aisyydell¨a painotettu kaari k:n l¨ahimm¨an havainnon kanssa. T¨all¨a tavalla upotus pienempidimensioiseen avaruuteen saadaan valikoimalla vektorit y₁, . . . ,y_m ∈ Rⁿ siten, ett¨a alku- per¨aisten et¨aisyyksien ja uusien havaintopisteiden parittaisten et¨aisyyksien erotus on mahdollisimman pieni.

3.3 Locally linear embedding

LLE-menelm¨a (locally linear embedding)[7] on my¨os yksi suosituimmista di- mensionpienent¨amismenetelmist¨a. Menetelm¨a laskee dimensioltaan pienen, saman ymp¨arist¨on s¨ailytt¨av¨an aineiston suuri-dimensioisesta l¨aht¨oaineistosta.

Menetelm¨an algoritmi perustuu yksinkertaisiin geometrisiin havaintoihin. Ole- tetaan edelleen, ett¨a aineisto on muotoa X ∈ R^n×d ja havainnot ovat otos jostakin sile¨ast¨a monistosta. Mik¨ali aineisto on sopiva, eli havainnot ovat hyvin poimittu ymp¨ari monistoa (the manifold is well-sampled), oletetaan ett¨a jokainen havaintopiste ja sit¨a l¨ahimp¨an¨a olevat muut havainnot sijait- sevat samassa alueessa monistoa tai alueen l¨ahettyviss¨a. N¨ain ollen esimer- kiksi kaksidimensioisesta kuvasta voidaan erottaa ryhmi¨a eli havainnot ovat jakautuneet kuvassa useampaan eri paikkaan siten ett¨a paikkojen v¨alill¨a voi- daan n¨ahd¨a eroja. N¨aiden alueiden geometria karakterisoidaan kertoimilla

w_ij, joiden avulla asetetaan uusi paikka jokaiselle alkuper¨aiselle havainnolle sen naapurihavaintojen perusteella.

Yksinkertaisessa LLE-menetelm¨ass¨a lasketaan ensiksi jokaiselle havainnolle x_i ∈ R^d K kappaletta l¨ahint¨a toista havaintoa k¨aytt¨aen mittana Euklidis- ta et¨aisyytt¨a. N¨aiden naapurihavaintojen avulla muodostetaan seuraavaksi virhefunktio t¨ass¨a tapauksessa seuraavasti:

ε(W) =

n

X

i=1

|x_i−

n

X

j=1

w_ijx_j|²

Yksitt¨ainen painokerroin wij kertoo havaintopisteen j vaikutuksen havain- topisteeseen i. Virhefunktiossa k¨ayt¨oss¨a on kaksi rajoitetta. Ensimm¨aiseksi kerroinw_ij = 0,jos havainto x_j ei kuulu havainnonx_i naapurustoon, eli K:n l¨ahimm¨an naapurin joukkoon. Virhefunktiosta selvitet¨a¨an kertoimiawij ∈R, jotka muodostavat kerroinmatriisin W ∈ R^n×n. Toinen rajoite on, ett¨a ker- roinmatriisin rivit summautuvat ykk¨oseen, eli:

n

X

j=1

w_ij = 1.

Virhefunktio minimoimalla selvitet¨a¨an kertoimetw_ij. Tarkastellaan merkint¨ojen yksinkertaistamisen vuoksi yksitt¨aist¨a havaintopistett¨ax_i ∈R^d ja k¨aytet¨a¨an siit¨a merkint¨a¨ax. T¨at¨a havaintopistett¨a l¨ahimp¨an¨a sijaitsevistaK:sta toises- ta havainnoista k¨aytet¨a¨an merkint¨a¨a n_j. Nyt virhefunktio t¨alle yksitt¨aiselle havaintopisteelle voidaan kirjoittaa muotoon:

ε(w) = |x−

K

X

j=1

w_jn_j|².

Koska painot w_j summautuvat ykk¨oseen saadaan:

=|

K

X

j=1

w_j(x−n_j)|²

=

K

X

j=1 K

X

k=1

wjwk(x−nj)^T(x−nk)

K¨aytet¨a¨an viel¨a loppuosan kovarianssimatriisin alkiosta merkint¨a¨a C_kj ∈R, jolloin muodoksi tulee:

=

K

X

j=1 K

X

k=1

w_jw_kC_jk

=w₁w₁C₁₁+w₁w₂C₁₂+w₂w₂C₂₂+. . .+w_Kw_KC_KK

=w^TCw

T¨ass¨aw = (w1, w2, . . . , wK) ja C ∈R^K×K on kovarianssimatriisi. Virhfunk- tio ε(w) voidaan minimoida k¨aytt¨am¨all¨a Lagrangen kerrointa λ∈R, jolloin funktio on muotoa:

f(w) = 1

2w^TCw

ja k¨aytt¨aen edelleen ehtoa, ett¨a painojen summa on yksi, eli:

K

X

j=1

w_j = 1 ↔1^Tw= 1,

kun 1= (1,1, . . . ,1)∈R^K. Nyt rajoitusehto minimoinnissa on:

g(w) = 1^Tw−1 = 0.

N¨ain ollen optimaalisuusehto on:

∇f(w) +λ∇g(w) = 0

⇔Cw+λ1= 0

⇔w=−λC⁻¹1

⇔1^Tw=−λ1^TC⁻¹1 Rajoitusehtoa k¨ayt¨am¨all¨a t¨ast¨a tulee:

⇔ −λ1^TC⁻¹1= 1

⇔ −λ= 1 1^TC⁻¹1

Sijoittamalla t¨am¨a aikaisempaan yht¨al¨o¨on saadaan tarkastelun kohteena ol- leelle havaintopisteelle xoptimaaliseksi painoiksi saadaan:

w= C⁻¹1 1^TC⁻¹1

K¨ayt¨ann¨oss¨a kuitenkin k¨a¨anteismatriisin laskeminen on yleens¨a laskennal- liseti ty¨ol¨ast¨a ja hidasta. Tehokkaampi keino virhefunktion minimoimiseen saadaan lineaaristen yht¨al¨oryhmien avulla. Olkoon ˆw = (w, λ) ∈ R^K+1 ja b = (0,0, . . . ,0,1)∈R^K+1. Lis¨aksi olkoon

Cˆ =

C 1^T 1 0

.

Nyt w ja λ saadaan ratkaisemalla yht¨al¨o:

Cˆwˆ =b

⇔











C11 . . . C1K 1 ... . .. ... ... C_K1 . . . C_KK 1 1 . . . 1 0



















 w1

... w_K

λ











=









 0

... 0 1











⇔

K

X

j=1

C_kjw_j =−λ∀k = 1, . . . , K

ja lis¨aksi

K

X

i=1

w_i = 1.

N¨ain saadaan samat arvot painokertoimille kuin edell¨a saatiin.

Painokertoimet, jotka selvitet¨a¨an t¨all¨a tavalla, noudattavat mallin kannal- ta olennaista symmetriaa. Jokaisen yksitt¨aisen havaintopisteen kanssa ker- toimet ovat muuttumattomia siirrolle, kierroille ja uudelleen skaalaukselle havaintopisteiden v¨alill¨a. Muuttumattomuus kierron ja uudelleen skaalauk- sen tapauksessa seuraa suoraan virhefunktiosta. Muuttumattomuus siirron

tapauksessa seuraa siit¨a, ett¨a painokertoimien summa on 1. Seuraus t¨ast¨a symmetriasta on se, ett¨a painokertoimet karakterisoivat olennaiset geomet- riset ominaisuudet ryhmien muodosta, jotka monistoon lopulta muodostuvat.

Tarkastellaan seuraavaksi taas koko aineistoa yksitt¨aisen havaintopisteen si- jasta. Menetelm¨an tarkoitus on supistaa aineiston dimensioduuteen reilusti pienemp¨a¨an dimensioon m. Jokainen vektori x_i ∈ R^d projisoidaan vektoriin y_i ∈ R^m koordinaattien perusteella. Uudet koordinaatit saadaan minimoi- malla seuraavaksi toinen virhefunktio uusien koordinaatien y_i suhten edelli- sest¨a virhefunktiosta saatujen kertoimien w_ij avulla:

Φ(Y) =X

i

|y_i−X

j

w_ijy_j|².

Nyt samat kertoimet jotka m¨a¨aritell¨a¨an alkuper¨aiselle havaintopisteelle d- dimensioisessa monistossa m¨a¨aritt¨av¨at sen paikan my¨os m-dimensioisessa monistossa. Virhefunktio saadaan m¨a¨aritelty¨a muodossa:

Φ(Y) =X

ij

m_ijy_iy^T_j.

T¨am¨a muoto sis¨alt¨a¨a sis¨atulon uusista koordinaateista ja matriisin M ∈ R^n×n alkion m_ij ∈R:

m_ij =δ_ij −w_ij −w_ji+X

k

w_kiw_kj.

T¨ass¨aδ_ij = 1 jos i=j ja muuten 0. Koko matriisi M on muotoa:

M =I −W −W^T −W^TW = (I−W)^T(I −W) (3.1) Optimoinnissa k¨aytet¨a¨an ehtoja, jotka tekev¨at siit¨a hyvin asetetun. Koordi- naatteja y_i voidaan siirt¨a¨a vakioiden avulla ilman, ett¨a virhefunktion arvo muuttuu. N¨ain ollen koordinaatit voidaan keskitt¨a¨a origoon:

X

i

y_i =0.

Huonojen (degenerated) ratkaisujen v¨altt¨amiseksi asetetaan my¨os uusien koor- dinaattivektoreiden varianssi ykk¨oseksi, jolloin:

1 n

X

i

y_iy^T_i =I,

miss¨aI ∈R^d×d on yksikk¨omatriisi.

Optimaaliset uudet koordinaattivektorit saadaan laskemalla matriisin M ominaisarvoista m+ 1 pienint¨a ja asettamalla uusiksi koordinaateiksi n¨ait¨a ominaisarvoja vastaavat ominaisvektoritv_i ∈Rⁿ. Alimmainen matriisin omi- naisvektori on ominaisarvoa nollaa vastaava yksikk¨ovektori, jossa kaikki kom- ponentit ovat yht¨asuuria. T¨am¨a vektori j¨atet¨a¨an huomioimatta, joka johtaa siihen rajoitukseen, ett¨a uusien koordinaattivektoreiden keskiarvo on nolla.

N¨ain ollen muiden ominaisvektoreiden komponenttien t¨aytyy kohtisuoruu- den takia summautua nollaan. N¨ain saadaan n-kappaletta m-dimensioisia uusia koordinaattivektoreita y_i ∈ R^m. Koska matriisi M voidaan esitt¨a¨a lauseen 3.1 muodossa, niin sit¨a ei tarvitse t¨asm¨allisesti laskea miss¨a¨an vai- heessa. Ominaisvektoreiden selvitt¨amiseen riitt¨a¨a se, ett¨a matriisiW ∈R^n×n on muodostettu, koska kertomalla lauseketta 3.1 molemmin puolin ominais- vektorilla v saadaan [5][7] :

M v= (v−W v)−W^T(v−W v).

3.4 Menetelmien hyvyydest¨ a

Sek¨a p¨a¨akomponenttianalyysi, LLE-menetelm¨a ett¨a MDS-menetelm¨a ovat yksinkertaisia toteuttaa ja ne eiv¨at vaadi lokaalien minimien laskemista de- rivoimalla. T¨am¨a selitt¨a¨a sen, ett¨a p¨a¨akomponenttianalyysi ja MDS ovat laajasti k¨aytettyj¨a menetelmi¨a, vaikka niill¨a on olemassa tiettyj¨a rajoituk- sia. N¨am¨a rajoitukset johtuvat mallien lineaarisuuteen liittyvist¨a oletuksis- ta. Jos muuttujien v¨alill¨a on jokin ep¨alineaarinen suhde, niin esimerkiksi p¨a¨akomponenttianalyysiss¨a se j¨a¨a kokonaan huomaamatta. T¨am¨a johtuu ko- varianssimatriisin k¨ayt¨ost¨a mallissa. Jos muuttujien jakaumista ei tiedet¨a p¨a¨akomponenttianalyysiss¨a mit¨a¨an, niin p¨a¨akomponentit ovat vain toisiaan vasten kohtisuorassa olevia vektoreita, joista ensimm¨ainen kulkee mahdolli- simman l¨ahelt¨a kaikkia havaintopisteit¨a. J¨arkev¨ampi tulkinta kuitenkin saa- daan, jos havaintojen tiedet¨a¨an jakaantuvan normaalisti[7][6].

Aineiston informaation s¨ailytt¨aminen voi my¨os olla haastavaa. Esimerkiksi p¨a¨akomponenttianalyysin tilanteessa kaikille aineistoille ei pystyt¨a l¨oyt¨am¨a¨an tarpeeksi pient¨a uutta dimensiota ilman, ett¨a informaatiota oleellisesti h¨avi¨a¨a.

Jos alkuper¨aisten muuttujien v¨alill¨a korrelaatio on pient¨a, niin silloin ne kaik- ki yhdess¨a kuvaavat parhaiten aineiston ominaisuuksia ja p¨a¨akomponenttianalyysin k¨aytt¨aminen ei tuota hyvi¨a tuloksia[6].

4 Eksponenttiperheen upotusmenetelm¨ a

Edellisess¨a kappaleessa esiteltiin yleisimpi¨a k¨ayt¨oss¨a olevia dimensionpie- nent¨amismenetelmi¨a, jotka perustuvat mitattavissa oleviin R^d aineistoihin.

Tutkielman tarkoituksena on tutustua tarkemmin eksponenttiperheen upo- tusmenetelm¨a¨an, (exponential family embeddings, EF-EMB)[8], jossa voidaan k¨aytt¨a¨a my¨os muuntyyppisi¨a aineistoja. T¨ass¨a luvussa k¨ayd¨a¨an l¨api ekspo- nenttiperheen upotusmenetelm¨an ominaisuuksia ja malliin liittyv¨a¨a tausta- teoriaa. Aluksi l¨ahdet¨a¨an liikkeelle yleisen eksponenttiperheen m¨a¨arittelyst¨a, koska eksponenttiperheen upotusmenetelm¨a¨an tarvitaan eksponenttiperheen teoriaa. Eksponenttiperheen upotusmenetelm¨a perustuu osittain sanaupotus- malleihin, joten niit¨a k¨asitell¨a¨an my¨os omassa kappaleessaan. Eksponentti- perheen ominaisuuksien ja sanaupotusmallien j¨alkeen keskityt¨a¨an pelk¨ast¨a¨an eksponenttiperheen upotusmenetelm¨an m¨a¨arittelyyn ja ominaisuuksiin.

4.1 Eksponenttiperhe

M¨a¨aritelm¨a 4.1. Eksponenttiperhe(Exponential family)on vektorimuuttu- jan ja vektoriparametrin tapauksessa niiden todenn¨ak¨oisyysjakaumien jouk- ko, joiden tiheysfunktiot voidaan esitt¨a¨a sopivien funktioiden avulla seuraa- vassa muodossa [1][2]:

f(X|θ) = h(x_i)Exp(η(θ)^Tt(x_i)−a(η(θ))) (4.1)

Funktiossa 4.1:

• X on satunnaismuuttuja, jonka ominaisuuksia ja jakaumaa halutaan tutkia ja xi ∈ R^d on havainto satunnaismuuttujasta, my¨ohemmin i= 1, . . . , n.

• Eli jokainen havainto sis¨alt¨a¨a d dimensioisen mittauksen satunnais- muuttujasta ja havaintoja on yhteens¨an kappaletta.

• Vektori θ ∈R^t on tarkasteltavana olevan jakauman parametrivektori.

• Dimensiotm¨a¨ar¨aytyy tarkasteltavan jakauman parametrien lukum¨a¨ar¨an mukaan.

• Funktiot :R^d→R^sontyhjent¨av¨at tunnusluvut (sufficient statistics)eli parametrien selvitt¨amiseen tarvittava riitt¨av¨a vektoriarvoinen funktio.

• Funktiota η:R^t→R^s sanotaan luonnolliseksi parametrivektoriksi.

• Kahdessa edellisess¨a funktiossa dimensio s m¨a¨ar¨aytyy tarkasteltavan jakauman ja tilanteen mukaan ja on sama luku kummankin funktion tilanteessa.

• h:R^d→R varmistaa ett¨a X on oikeassa avaruudessa/mittayksik¨oss¨a

• a : R^d → R on logaritmin normalisoija (log normalizer), jonka avulla tiheysfunktio integroituu arvoon 1

Eksponenttiperheeseen kuuluvat esimerkiksi normaalijakauma, gammajakau- ma, Poissonjakauma ja Bernoullin jakauma. Eksponenttiperheeseen kuulu- maton jakauma on esimerkiksi Studentin t-jakauma. Eksponenttiperheen avul- la voidaan yleist¨a¨a samoja teoriaan liittyvi¨a ominaisuuksia usealle eri to- denn¨ak¨oisyysjakaumalle. Esimerkiksi todistaessa jotakin lausetta sit¨a ei tar- vitse erikseen todistaa jokaiselle eri todenn¨ak¨oisyysjakaumalle, vaan voidaan todistaa se p¨atev¨aksi yleisesti eksponenttiperheen jakaumien tilantessa. T¨all¨oin se p¨atee jokaiselle eksponenttiperheen jakaumalle. Eksponenttiperheen jakau- man sanotaan olevan yksiulotteinen, jos havaintoaineiston dimensio don yk- si ja muissa tapauksissa jakauman sanotaan olevan moniulotteinen. Seuraa- vassa esimerkiss¨a k¨ayd¨a¨an l¨api, mit¨a yl¨apuolella esitetyt eksponenttiperheen funktiot ovat yksiulotteisen normaalijakauman tapauksessa.

Esimerkki 4.2. Normaalijakauma

Parametrivektori on nyt θ = (µ, σ). Normaalijakauman tiheysfunktio on muotoa:

f(x) = 1 σ√

2π exp

−(x−µ)² 2σ²

= 1

√2πexp

log 1

σ

exp −x²

2σ² + xµ σ² − µ²

2σ²

= 1

√2πexp −x²

2σ² +xµ σ² − µ²

2σ² −log(σ)

= 1

√2πexp µ

σ², −1 2σ²

(x, x²)^T − µ²

2σ² −log(σ)

T¨ast¨a muodosta n¨ahd¨a¨an, ett¨a yksiulotteisen normaalijakauman tapaukses- sa:

• t(x) = x

x²

• η(θ) = _µ

σ²

−_2σ¹2

= η₁

η₂

• h(x) =^√_2π¹

• a(θ) = _2σ^µ22 + log(σ)

Eksponenttiperheen ominaisuuksista todistetaan seuraavaksi lause, jota tar- vitaan my¨ohemmin.

Lause 4.3.

∇_ηa(η) =E_η[t(x)]

Toisin sanoen funktion a(η) derivointi vektorin η suhteen antaa tulokseksi vektorin t(x) ensimm¨aisen momenttivektorin eli odotusarvovektorin [1].

Todistus. Eksponenttiperheen m¨a¨aritelm¨ass¨af(x|η) =h(x) exp((η)^Tt(x)− a(η)) on tiheysfunktio, joten sen integraali yli koko m¨a¨arittelyjoukon saa arvon yksi:

Z

f(x|η)dx= 1

⇔ Z

h(x) exp(η^Tt(x)−a(η))

dx= 1

⇔ Z

h(x) exp(η^Tt(x)) exp(−a(η))

dx= 1

⇔exp(−a(η)) Z

h(x) exp(η^Tt(x))

dx= 1

⇔exp(a(η)) = Z

h(x) exp(η^Tt(x)) dx

⇔a(η) = ln Z

h(x) exp(η^Tt(x)) dx

Derivoimalla t¨at¨a parametrivektorinη suhteen saadaan:

∇_ηa(η) = ∇_ηln Z

h(x) exp(η^Tt(x)) dx

Logaritmifunktion derivoimiss¨a¨ant¨o¨a k¨aytt¨am¨all¨a p¨a¨ast¨a¨an muotoon:

∇_ηa(η) = ∇_η R

h(x) exp(η^Tt(x)) dx R (h(x) exp(η^Tt(x)))dx

Ja edelleen yht¨al¨on oikeaa puolta muokkaamalla p¨a¨ast¨a¨an haluttuun lopul- liseen muotoon:

∇_ηa(η) =

R ∇_ηh(x) exp(η^Tt(x)) dx R (h(x) exp(η^Tt(x)))dx

=

R t(x)h(x) exp(η^Tt(x)) dx exp(a(η))

= Z

t(x)h(x) exp(η^Tt(x)) exp(−a(η)) dx

= Z

t(x)h(x) exp(η^Tt(x)−a(η)) dx

= Z

t(x)f(x|η)dx=E_η[t(x)]

Huomautus 4.4. Vastaavasti funktiona(η) derivoiminen kahdesti vektorin η muuttujien suhteen antaa vektorin t(x) kovarianssimtriisin:

∇²_ηa(η) = Cov_η[t(x)]∈R^s×s

Seuraavassa esimerkiss¨a n¨aytet¨a¨an, miten lause 4.3 toimii yksiulotteisen nor- maalijakauman tapauksessa. Apuna on k¨aytetty l¨ahdett¨a [1].

Esimerkki 4.5. Odotusarvo ja kovarianssimatriisi yksiulotteisen normaalija- kauman tapauksessa

Edellisess¨a esimerkiss¨a saatiin normaalijakaumalle:

η(θ) = _µ

σ²

−_2σ¹2

ja

a(θ) = µ²

2σ² + log(σ).

Ratkaistaan funktiosta η(θ) muuttujatµ ja σ:

η₁ = µ

σ² ↔µ= η₁ σ² η₂ = −1

2σ² ↔σ= r 1

−2η₂ Sijoittamalla η1 ja η2 funktioon a(θ) saadaan:

a(η) = µ²

2σ² + log(σ)

=−η₁²σ⁴

2σ² + log(σ)

=−η₁² 4η₂ +1

2log 1

2η₂

Joten odotusarvovektoriksi saadaan:

∇_ηa(η) =

∂a(η)

∂η₁ ,∂a(η)

∂η₂

= −η₁

2η2

, η²₁ 4η₂² − 1

2η2

= −_σ^µ2

2_2σ⁻¹2

, (_σ^µ2)²

4(_2σ⁻¹2)² − 1 2_2σ⁻¹2

= µ, µ²+σ²

= (E_η[x], E_η[x²]) =E_η[t(x)]

T¨ast¨a saa laskettua x:n varianssin:

Var_η(x) = E(x)²_η−E(x²)_η =µ²−(µ²+σ²) =σ²

Lasketaan seuraavaksi viel¨a koko kovarianssimatriisi:

∇²_ηa(η) =











∂²a(η)

∂η₁²

∂²a(η)

∂η2∂η1

∂²a(η)

∂η1∂η2

∂²a(η)

∂η²₂











=









−1 2η2

η1

2η²₂

η1

2η²₂ (^−η_2η3²¹ 2

− _2η¹2 2

)









=











−1 2⁻¹

2σ2

µ σ2

2(⁻¹

2σ2)²

µ σ2

2(⁻¹

2σ2)²

−(^µ

σ2)² 2(⁻¹

2σ2)³ − ₂₍−1¹ 2σ2)²











=





σ² 4µσ² 4µσ^{2 µ2}₂^σ4 + 2σ⁴





=





Var_η[x] Cov(x, x²) Cov(x, x²) Varη[x²]





= Cov_η[t(x)].

Nyt eksponenttiperheen m¨a¨aritelm¨a on tullut tutuksi esimerkkien avulla.

Seuraavaksi siirryt¨a¨an sanaupotusmallien teoriaan ja niiden j¨alkeen jatketaan eksponenttiperheen upotusmenetelm¨an m¨a¨arittelyyn, jossa seuraavan kerran tarvitaan t¨ass¨a kappaleessa k¨asiteltyj¨a eksponenttiperheen ominaisuuksia.

4.2 Sanaupotukset

Sanaupotusten (word embeddings) [14] m¨a¨aritelm¨a on yleisimm¨an k¨asityksen mukaan erilaisten sanojen esitt¨aminen numeerisessa muodossa. Useimmitten numeerinen esitys on Rⁿ vektori. T¨ass¨a tutkielmassa k¨asitelt¨av¨a eksponent- tiperheen upotusmenetelm¨a perustuu sanaupotus malleille, joten seuraavak- si tutustutaan hieman sanaupotus mallien teoriaan. Sanaupotus mallit ovat hyvin toimivia malleja, kun halutaan ottaa selv¨a¨a semanttisuuden, eli kielen merkityksen, samanlaisuudesta aakkoston eri termien v¨alill¨a [8].

Esimerkiksi jos tarkastellaan tekstimuotoista aineistoa ja lasketaan sanoista

”kuningas”, ”mies”ja ”nainen”tehdyill¨a vektoriesityksill¨a seuraava laskutoi- mitus:

v(”kuningas”)−v(”mies”) +v(”nainen”)

voidaan saada tulokseksi vektori, joka on l¨ahell¨a sanan ”kuningatar”vektoriesi- tyst¨av(”kuningatar”). Sovitetut sanaupotukset voivat siis auttaa ymm¨art¨a- m¨a¨an, ennustamaan ja hahmottamaan kielten rakenteita [14][16].

Ensimm¨aiset teoreettiset perusteet sanaupotuksille ovat 1950-luvun alusta.

Ensimm¨aiset yritykset k¨aytt¨a¨a sanojen ominaisuuksia esitt¨am¨a¨an niiden sa- mankaltaisuutta tehtiin k¨asin. 1990-luvun alussa otettiin ensimm¨aisi¨a ker- toja k¨aytt¨o¨on automaattisesti koodattuja sanojen yhteydest¨a riippuvia omi- naisuuksia. Sanaupotukset ovat yleistyneet 2010 luvulla ja nykyaikana sa- naupotukset ovat suosituin tutkimusalueluonnollisen kielen k¨asitelyss¨a (Na- tural Language Processing, NLP) [14]. Sanaupotuksia ja niiden sovelluksia k¨aytet¨a¨an my¨os esimerkiksi automaattisessa puheentunnistuksessa ja teks- tin k¨a¨ann¨oksiss¨a [15]. Viime vuosina koneoppimisen tekniikoiden kehittyess¨a on tullut mahdolliseksi k¨aytt¨a¨a yh¨a monimutkaisempia malleja laajempiin aineistoihin ja n¨am¨a monimutkaisemmat mallit tyypillisesti suoriutuvat pa- remmin kuin yksinkertaiset mallit.

Yksinkertainen ja helppo tapa muodostaa sanoista vektoreita on asettaa jo- kaiselle sanalle x_i vektori Rⁿ avaruuteen, miss¨a n on aakkoston koko. Jo- kaisen aakkoston kirjaimen kohdalla vektori saa arvon nolla kaikissa muissa paikoissa paitsi yhdess¨a tietyss¨a indeksiss¨a. Sanojen esitt¨aminen t¨all¨a taval- la johtaa usein harvaan aineistoon ja saatetaan tarvita paljon dataa, ett¨a esiin saadaan onnistuneesti mit¨a¨an tilastollisesti j¨arkev¨a¨a. T¨ast¨a tulee tarve muodostaa jatkuva vektoriavaruuden esitys sanoille, joka johtaa aineistoon, jota voidaan hy¨odynt¨a¨a erilaisilla malleilla. Tarkemmin sanottuna halutaan semanttisesti samankaltaiset sanat yhdistetty¨a l¨ahekk¨aisiin pisteisiin, jotta saadaan esiin hy¨odyllist¨a informaatiota sanojen tarkoituksista [14][16].

Sanaupotusmallit voidaan jakaa menetelmin¨a kahteen eri p¨a¨akategoriaan.

Ensimm¨ainen on laskentaan perustuvat menetelm¨at (count-based methods) ja toinen ennustavat menetelm¨at (predictive methods). Laskentaan perustu- vat menetelm¨at eiv¨at k¨ayt¨a ennustamista apuna, vaan kaikki tulokset nojaa- vat aineistoista laskettuihin lukuihin. Ennustavat menetelm¨at taas yritt¨av¨at ennustaa sanan sen naapurisanojen avulla suhteessa opittuihin upotettuihin vektoreihin. Molemmille p¨a¨amenetelmille yhteist¨a on oletus, ett¨a sanat jotka esiintyv¨at samassa kontekstissa jakavat samantapaisen semanttisuuden [14].

Eri menetelmi¨a on useita ja niist¨a on paljon muunnelmia [8], mutta jokainen niist¨a kuvastaa samaa p¨a¨aideaa. Menetelmiss¨a jokainen aakkoston termi on liitetty kahteen vektoriin, upotettuun vektoriin ja kontekstivektoriin. N¨am¨a kaksi vektoria hallitsevat ehdollisia todenn¨ak¨oisyyksi¨a, jotka yhdist¨av¨at jo- ka sanan sit¨a ymp¨ar¨oiv¨a¨an kontekstiin. Eri menetelm¨at yhdist¨av¨at n¨am¨a eri tavalla [8].

Oletuksena kaikilla sanaupotusmenetelmill¨a on se, ett¨a samankaltaisilla sa- noilla pit¨aisi olla samankaltaiset vektorit, eli samankaltaisten sanojen vek- toreiden pit¨aisi korreloida kesken¨a¨an. T¨am¨a tarkoittaa sit¨a, ett¨a kahden sa- nan vektorin v¨alinen korrelaatio on l¨ahell¨a luka yksi. Se, ett¨a sanaupotukset ovat yhdistetty niiden kontekstiin kuuluviin sanoihin, nojaa samankaltaisiin ominaisuuksiin, eli samankaltaisilla sanoilla on tapana esiinty¨a samassa kon- tekstissa. Esimerkiksi tietyn valtion nimi esiintyy usein samassa yhteydess¨a sen p¨a¨akaupungin nimen kanssa. T¨ast¨a voi tulla ongelmaksi, ett¨a my¨os vas- takkaista tarkoittavat sanat korreloivat kesken¨a¨an. T¨am¨a tarkoittaa siis sit¨a, ett¨a sanojen v¨alill¨a voidaan havaita negatiivista korrelaatiota eli sanojen vek- toreiden v¨alinen korrelaatio saa negatiivisia miinus yht¨a l¨ahell¨a olevia arvo- ja. Negatiivisen korrelaation ongelmaa on korjattu symmetristen rakenteiden avulla [14].

Toinen ominaisuus viimeaikaisissa sanaupotuksissa on se, ett¨a ne voidaan rat- kaista lineaarialgebran keinoilla, vaikka upotukset ovat muodostettu ep¨aline- aarisilla menetelmill¨a [14]. Neuroverkkojen avulla lasketut esitykset sanoille ovat t¨ass¨a mieless¨a mielenkiintoisia. Opitut vektorit koodaavat monta kieli- tietellist¨a riippuvuutta ja ryhm¨a¨a ja yll¨att¨aen monet n¨aist¨a voidaan esitt¨a¨a li- neaarisina k¨a¨ann¨oksin¨a. Esimerkiksi l¨ahteess¨a [15] aineistona k¨aytet¨a¨an suur- ta m¨a¨ar¨a¨a erilaisia uutisartikkeleita Googlen sis¨aisest¨a tietokannasta. T¨ass¨a aineistossa seuraava sanojen vektoriesitysten v¨alinen laskutoimitus

v(”M adrid”)−v(”Espanja”) +v(”Ranska”)

on l¨ahemp¨an¨a sanan Pariisi vektoriesityst¨av(”P ariisi”) kuin mink¨a¨an muun sanan vektoriesityst¨a samassa aineistossa [15].

Yksi esimerkki sanaupotus mallista on Skip-gram malli, joka on tehokas me- netelm¨a, kun tarkastellaan sanojen vektoriesityksi¨a suuresta m¨a¨ar¨ast¨a ep¨a- muodollista teksti¨a. Toisin kun useimmat neuroverkkoihin perustuvat mallit Skip-gram malli ei vaadi lukuisia matriisien kertolaskuja ja on siten lasken- nallisesti tehokkaampi [15]. Kuva 1 havainnollistaa Skip-gram mallin toimin-

taa.

Kuva 1:Esimerkkikuva Skip-gram mallin toiminnasta. P¨a¨am¨a¨ar¨an¨a on muo- dostaa sanoille vektorimuotoiset esitykset, joiden avulla voidaan ennustaa sanan l¨aheisi¨a sanoja [15].

Skip-gram mallin tarkoituksena on muodostaa sanoille esitykset vektorimuo- dossa ja niiden avulla ennustaa sanan l¨aheisi¨a sanoja tekstiss¨a. Esimerkiksi sanan ”Volga”vektoriesityst¨a l¨ahell¨a voi olla sanojen ”Ven¨aj¨a”ja ”joki”vektori- esitykset. Tarkemmin ottaen sanoille ennustetaan muita sanoja tietyll¨a s¨ateell¨a sanaa aikaisemmin ja sen j¨alkeen siten ett¨a tarkasteluissa voidaan my¨os hyp¨at¨a osan sanoista yli [16].

Virkkeellew1w2. . . wm, miss¨a jokainenwi on yksi sana, k-skip-n-gram joukko on:

{w_i1, w_i2, . . . , w_in|

n

X

j=1

i_j −ij−1 < k},

jossa n on s¨ade joka kertoo kuinka montaa per¨akk¨aist¨a sanaa tarkastellaan ja k kertoo monenko vierekk¨aisen sanan yli tarkastelussa voidaan hyp¨at¨a [17]. Tarkastelu aloitetaan tekstin ensimm¨aisest¨a sanasta ja edet¨a¨an siit¨a eteenp¨ain, joten taakse j¨a¨avi¨a sanoja nykyisen sanan kanssa ei tarvitse tar- kastella, koska skip-gram joukon alkiot n¨aiden sanojen kanssa on saatu jo kun on tarkasteltu n¨ait¨a edellisi¨a sanoja. Esimerkiksi virkkeen

”U lkona saattaa paistaa huomenna aurinko.”

0-skip-2-gram joukko on:

{(ulkona, saattaa),(saattaa, paistaa),(paistaa, huomenna), (huomenna, aurinko)}

ja 1-skip-2-gram joukko on:

{(ulkona, saattaa),(ulkona, paistaa),(saattaa, paistaa),(saattaa, huomenna), (paistaa, huomenna),(paistaa, aurinko),(huomenna, aurinko)}.

S¨ateenn kasvattaminen parantaa mallin tuloksia, mutta my¨os kasvattaa las- kemisen m¨a¨ar¨a¨a. Esimerkiksi jos virkkeess¨a on 10 sanaa niin 4-skip-2-gram joukossa 35 alkiota ja 4-skip-3-gram joukossa on jo 80 alkiota. Toisaalta l¨aheiset sanat vaikuttavat tiettyyn sanaan enemm¨an kuin kaukaisemmat.

N¨ain ollen kovin suurta et¨aisyytt¨a ei v¨altt¨am¨att¨a tarvitse mallissa k¨aytt¨a¨a parempien tulosten saavuttamiseksi. Samoin ylihyp¨att¨avien sanojen lukum¨a¨a- r¨ank kasvattaminen lis¨a¨a laskujen m¨a¨ar¨a¨a. Jos virkkeess¨a on edelleen 10 sa- naa, niin 0-skip-2-gram joukossa on 9 alkiota ja 4-skip-2-gram joukossa jo 35 alkiota [16][15].

Yksi skip-gram mallin vahvuuksista on se, ett¨a esimerkiksi kaksisanaisis- ta fraaseista voidaan muodostaa vain yksi vektori. N¨ain ollen malli pystyy k¨asittelem¨a¨an my¨os kaksisanaiset fraasit, kuten esimerkiksi kaksisanaisen ni- men ”Hartwall -areena”, vaikka sanat ”Hartwall”ja ”areena”eiv¨at yksitt¨ain muulloin esinny usein samassa kontekstissa. T¨all¨a tavalla mallista saadaan tarkempi [15].

Toinen esimerkki sanaupotus-mallista on CBOW malli (Continuous Bag of Words), joka toimii p¨ainvastaisesti, kuin Skip-gram-malli. CBOW-malli yritt¨a¨a ennustaa tietty¨a sanaa ymp¨ar¨oivien sanojen perusteella sen sijaan, ett¨a tie- tyn sanan vektoriesityksell¨a yritett¨aisiin ennustaa sen l¨aheisi¨a sanoja [16].

Kuva 2 havainnollistaa tarkemmin CBOW-mallin toimintaa. CBOW-malli on itse asiassa seuraavassa kappaleessa k¨asitelt¨av¨an EF-EMB mallin erikois- tapaus [8].

Kuva 2: Esimerkkikuva CBOW mallin toiminnasta. P¨a¨am¨a¨ar¨an¨a on muo- dostaa tietylle sanalle vektoriesitys sit¨a ymp¨ar¨oivien sanojen vektoriesitysten perusteella [15].

4.3 Eksponenttiperheen upotusmenetelm¨ a

Luvussa k¨asitell¨a¨an eksponenttiperheen upotusmenetelm¨a¨a (Exponential Fa- mily Embeddings) [8]. Menetelm¨an tarkoituksena on saada laajojen havain- toaineistojen jakaumista esiin hy¨odyllisi¨a ominaisuuksia. Menetelm¨an avulla yritet¨a¨an yleist¨a¨a esimerkiksi edellisess¨a kappaleessa k¨asitellyt sanaupotus- mallit sanojen lis¨aksi my¨os erityyppisille moniulotteisille aineistoille. Apuna k¨aytet¨a¨an eksponenttiperhett¨a ja sen ominaisuuksia. Yleist¨a eksponenttiper- hett¨a on k¨asitelty jo edell¨a kappaleessa 3.1.

Ensiksi m¨a¨aritell¨a¨an menetelm¨ass¨a tarvittavat k¨asitteet ja funktiot. T¨am¨an j¨alkeen k¨ayd¨a¨an t¨asm¨allisesti l¨api kuinka menetelm¨an parametrit saadaan estimoitua. L¨ahteen¨a kappaleessa k¨aytet¨a¨an p¨a¨aasiassa artikkelia [8].

Motivaationa eksponenttiperheen upotusmenetelm¨an k¨ayt¨olle pidet¨a¨an sit¨a, ett¨a on mahdollista hy¨odynt¨a¨a samaa menetelm¨a¨a monenlaisiin aineistoihin silloin, kun n¨aihin aineistoihin liittyv¨at oletukset pysyv¨at samoina. Eli siis samaa mallia voidaan k¨aytt¨a¨a useille eri aineistolle, kunhan ne noudatta- vat tiettyj¨a oletuksia. Esimerkiksi tarkasteltavana alana voi olla kielitiede, jolloin aineisto voi olla teksti¨a ja indeksin¨a tietty sana sek¨a sanan paikka tekstiss¨a. Toinen esimerkki on neurotiede, jolloin indeksin¨a voidaan esimer- kiksi k¨aytt¨a¨a tietty¨a neuronia sek¨a aikaa ja kiinnostava muuttuja voi olla esimerkiksi neuroneiden aktiivisuustaso eri neuroneissa. Kolmas esimerkki

on ostotottumusten tutkiminen, jossa indeksin¨a on tietyn asiakkaan ostos- kori ja siit¨a l¨oytyv¨at tuotteet. T¨ass¨a tilanteessa kiinnostuksen kohteena voi olla mit¨a tuotteita ostetaan yleens¨a samalla ostokerralla. Nelj¨anten¨a esimerk- kin¨a ovat elokuva-arvostelut, miss¨a indeksin¨a on sek¨a elokuva, ett¨a arvoste- lun antanut henkil¨o ja kiinnostuksen kohteena on elokuvien kesken¨ainen pa- remmuusj¨arjestys. Huomionarvoista t¨ass¨a esimerkiss¨a on se, ett¨a elokuvien paremmuusj¨arjestykseen vaikuttaa annetun arvosanan lis¨aksi my¨os arvosa- nan antaja. Jos tietty henkil¨o siis antaa keskim¨a¨arin parempia arvosanoja, niin EF-EMB malli ottaa sen huomioon, kun lasketaan lopullista arvosanaa tietylle elokuvalle.

4.3.1 Teoriaa

Eksponenttiperheen upotusmenetelm¨an mukaan tietyn havaintopisteen ja- kaumaan vaikuttaa ratkaisevasti muu aineisto havaintopisteen kontekstissa, kuten vaikka l¨ahiymp¨arist¨oss¨a. Eksponenttiperheen upotusmenetelm¨ass¨a on sanaupotusmallien tavoin my¨os ajatuksena, ett¨a havainnot, joilla on jokin sa- maa tarkoittava ominaisuus omaavat tyypillisesti my¨os samantyyppisen kon- tekstin [8][9].

Oletetaan, ett¨a eksponenttiperheen upotusmenetelm¨ass¨a k¨asitelt¨av¨a aineis- to X ⊂ R^d on vastaavaa muotoa kuin luvun 2 alussa esiteltiin. Upotettuun eksponenttiperheeseen tarvitaankontekstifunktiota (context function), ehdol- lista eksponenttijakaumaa sek¨aupottava rakenne (embedding structure).

Ensiksi m¨a¨aritell¨a¨an jokaiselle havaintopisteelle konteksti. Olkoon S_n kaik- kien havaintojen x_i indeksien joukko eli S_n={1, . . . , n}.

M¨a¨aritelm¨a 4.6. Konteksti m¨a¨arittelee niiden muiden havaintojen joukon, joiden informaatiota k¨aytet¨a¨an hyv¨aksi, kun m¨a¨aritell¨a¨an jakaumaa tietyss¨a havaintopisteess¨a. Tietyn havainnonx_i kontekstijoukko c_i m¨a¨aritell¨a¨an jouk- kona muiden havaintojen indeksej¨a:

c_i ⊂S_n.

Tietyn havainnon xi kontekstiin kuuluvien muiden havaintojen joukkoa eli havainnon kontekstia merkit¨a¨an muuttujalla x_ci:

x_ci ={x_i|i∈c_i}.