Vuoden 2020 pro gradu -palkinnon voittaja Timo Lintonen. Kuva TEK/ Teija Soini.
MALin pro gradu -palkinnon sai tänä vuonna filosofian maisteri Timo Lintonen pro gradu -tutkielmastaan ”Optimization in Semi-Supervised Classification Of Multivariate Time Series”. Oulun VTT:llä tehty opinnäytetyö käsittelee osittain ohjattua, monimuuttujaista aikasarjojen luokittelua. Valmistuttuaan Lintonen aloitti VTT:llä vakinaisena tutkijana, ja harjoittaa työn ohessa tohtoriopintoja Oulun yliopistossa. Seuraavassa lisää palkitusta työstä Lintosen itse kertomana.
Aloitin Pro gradu -tutkielmani kirjoittamisen saatuani opinnäytetyöpaikan VTT:llä. Työssäni VTT:llä pääsin alusta alkaen tutustumaan uusimpaan koneoppimisen tutkimukseen yhdessä kokeneiden tutkijoiden kanssa. Tutkielmani aihe, aikasarjojen osittain ohjattu oppiminen, nousi käytännön tarpeesta. Koneoppimisen tutkimuksessa sekä ohjattu että ohjaamaton oppiminen ja kuvantunnistus ovat saaneet paljon huomiota, mutta aikasarjojen vertailu ja osittain ohjattu (semi-supervised) oppiminen ovat vähemmän tutkittuja aiheita. Aikasarjat ovat erittäin yleinen datan muoto. Aikasarja x=(x1,…,xn) on joukko peräkkäin tehtyjä havaintoja, joten jokainen havainto xi riippuu jollain tavalla edellisistä havainnoista. Tästä syystä useiden perinteisten mallien, joiden toiminta perustuu olettamukseen havaintojen riippumattomuudesta, tarkkuus heikkenee. Aikasarjoja tuottavat esimerkiksi sensorit, jotka mittaavat seuraamaansa arvoa useita kertoja sekunnissa. Osittain ohjattua oppimista voidaan hyödyntää tilanteissa, joissa merkittyä dataa on käytettävissä vain vähän, mutta merkitsemätöntä dataa on saatavilla paljon ja vaivattomasti. Osittain ohjattua oppimista on käytetty muun muassa Wikipedia-artikkelien luokitteluun. Internetissä on runsaasti Wikipedia-artikkeleita jokaisen saatavilla, mutta näiden artikkelien konseptien ja kategorioiden tulkitsemista ja merkitsemistä varten asiantuntijan on luettava artikkelit yksitellen, mikä vie paljon aikaa. Tällöin on tehokkaampaa, jos asiantuntija lukee ja merkitsee pienen osan analysoitavista artikkeleista, jonka jälkeen algoritmi hyödyntää näitä asiantuntijan merkintöjä yhdessä valtavan merkitsemättömän tietokannan kanssa. Nämä ominaisuudet tekevät aikasarjojen osittain ohjatusta oppimisesta äärimmäisen hyödyllisen tutkimusaiheen.
Aikasarjojen luokittelussa Dynamic time warping -etäisyysmitta (DTW) ja lähinaapuriluokitin (nearest neighbor classifier) ovat kaksi historiallisesti merkittävää algoritmia. Nämä kaksi algoritmia ovat olleet jo vuosikymmeniä aikasarjojen luokittelun menestykkäintä kärkeä. DTW on aikasarjojen vertailuun käytetty etäisyysmitta, jonka Sakoe ja Chiba kehittivät 1970-luvulla. DTW-mitta kykenee, toisin kuin Euklidinen etäisyys (ED), korjaamaan ajoitusvirheet aikasarjojen välillä. Tämän ominaisuuden ansiosta DTW-mitalla on pitkä historia puheen tunnistuksessa. Kuvissa 1. ja 2. on kaksi samankaltaista aikasarjaa, jotka ovat hieman epätahdissa: oranssi sarja saavuttaa huippunsa indeksin 30 kohdalla, kun taas sinisen sarjan huippu on indeksin 40 kohdalla. Ajoitusvirheen korjaamisen myötä näiden sarjojen DTW-etäisyys on selvästi pienempi kuin Euklidinen etäisyys.
Ajoitusvirheiden korjaaminen on kiehtova matemaattisen optimoinnin ongelma. Olkoot x ja y aikasarjoja, joissa kummassakin on n havaintoa. Ajoitusvirheet näiden aikasarjojen välillä voidaan korjata minimoimalla funktio
Kuva 1. Euklidinen etäisyys kahden aikasarjan välillä.
Kuva 2. DTW-etäisyys kahden aikasarjan välillä.
Kuva 3. Esimerkki etenevän lähinaapuriluokittimen toiminnasta.
Kuvissa 1. ja 2. indeksiparit on yhdistetty harmailla katkoviivoilla. Tämän määritelmän perusteella sallittuja reittejä on äärettömän monta ja lyhimmässäkin sallitussa reitissä on n kappaletta indeksipareja. Tutkielmassani osoitan dynaamista optimointi käyttäen, että tämä haastava optimointitehtävä voidaan rekursiivisesti jakaa alitehtäviin, joiden ratkaiseminen on helppoa.
Toinen tärkeä algoritmi, lähinaapuriluokitin, on yksinkertainen ja paljon käytetty ohjatun oppimisen algoritmi, jota voidaan soveltaa hyvin useissa eri tilanteissa. Sen toiminta perustuu havaintojen (tässä tapauksessa aikasarjojen) välisiin etäisyyksiin. Lähinaapuriluokitin luokittelee jokaisen uuden aikasarjan samaan luokkaan, kuin mihin sitä lähin opetusdatan aikasarja kuuluu. Tutkielmassani sovelsin lähinaapuriluokittimen osittain ohjattua sukulaista, etenevää lähinaapuriluokitinta (nearest neighbor propagation). Tämä algoritmi oppii löytämään merkitsemättömästä datasta sille annettujen esimerkkien kaltaisia aikasarjoja. Esimerkkiaikasarjat voivat olla esimerkiksi sydänkäyrässä esiintyviä normaaleja sydämenlyöntejä, jolloin esimerkeistä poikkeavat aikasarjat ovat merkki sydämen toiminnan häiriöstä. Mistä tiedämme, että kaikki merkitsemättömässä datassa piilevät esimerkkien kaltaiset aikasarjat on löydetty? Tutkielmani pyrkii vastaamaan tähän kysymykseen kehittämälläni peak evaluation -algoritmilla. Tämä algoritmi arvioi aikasarjojen välisten etäisyyksien sarjaa, missä huomattavan suuret etäisyydet esimerkkiaikasarjoihin ovat merkki epäilyttävästä poikkeamasta. Kuvassa 3. on esimerkki etenevän lähinaapuriluokittimen toiminnasta. Algoritmi hyväksyy uusia aikasarjoja yksitellen aiemmin opittujen aikasarjojen joukkoon sen perusteella, kuinka lähellä nämä uudet aikasarjat ovat aiemmin opittuja aikasarjoja. Indeksin 25 kohdalla etäisyyssarjassa on selkeä piikki, joka kertoo siitä, että algoritmi siirtyy normaalien (eli esimerkkien kaltaisten) aikasarjojen luokasta epänormaalien aikasarjojen luokkaan.
Tutkielmassani käytin DTW-mittaa Australian viittomakielen viittomien ja allekirjoitusten vertailuun. Esimerkiksi viittomakielen tulkitsemisessa kunkin henkilön yksilöllinen tyyli viittoa aiheuttaa ajoitusvirheitä; jotkut saattavat viittoa muita hitaammin tai nopeammin. DTW-mitta ja peak evaluation -algoritmi yhdessä tuottivat tarkempia tuloksia kuin aiemmat aikasarjojen osittain ohjatussa tutkimuksessa käytetyt menetelmät. Tutkielmani tuloksilla on useita mahdollisia sovelluskohteita muun muassa energian kulutuksen seurannassa, tuotantolinjan laadunvalvonnassa ja liikenteen ohjauksessa.•
Timo Lintonen