FM Ville Hyvönen puollustaa väitöskirjaansa "A Machine Learning Approach to Approximate Nearest Neighbor Search" maanantaina 23.10.2023 klo 14 Helsingin yliopiston Chemicum-rakennuksen auditoriossa A129 (A.I. Virtasen aukio 1, 1. krs). Vastaväittäjänä toimii professori Sanjoy Dasgupta (University of California, San Diego, Yhdysvallat) ja kustoksena professori Teemu Roos (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Ville Hyvösen väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Complex Systems Computation -ryhmässä tehtävää tutkimusta. Väitöskirjan ohjaajana on toiminut professori Teemu Roos (Helsingin yliopisto).
Koneoppiminen approksimatiivisessa lähimmän naapurin haussa
Approksimatiivinen lähimmän naapurin (ALN) haku on fundamentaalinen algoritminen ongelma. Tehtävänä on suunnitella tietorakenne, joka mahdollistaa nopeat, mutta approksimatiiviset, lähimmän naapurin kyselyt. ALN-hakua hyödynnetään usein sovelluksissa, joissa aineistot ovat suuria ja korkeaulotteisia ja joissa tarvitaan nopeita vasteaikoja. Tärkeät nykyaikaiset sovellusalueet sisältävät suosittelujärjestelmät, suurten kielimallien opettamisen, päättelyn suurissa malleissa sekä informaation haun.
ALN-algoritmit voidaan luokitella hajautustauluihin, puihin, ja graafeihin perustuviin menetelmiin. Tämä väitöskirja käsittelee avaruuden osituksiin, eli hajautustauluihin ja puihin, perustuvia menetelmiä. Väitöskirjan kontribuutiot voidaan jakaa kahteen osaan. Ensimmäiseksi, tehostamme puupohjaisia ALN-menetelmiä ja parannamme niiden käytettävyyttä. Toiseksi, muotoilemme kandidaattijoukon valinnan ALN-haussa moniluokkaisena luokitteluongelmana (multilabel classification problem). Siten pystymme hyödyntämään nykyaikaisia koneoppimisen menetelmiä ALN-haussa.
Väitöskirja esittelee kaksi uutta puutyyppiä ALN-hakuun: harvan pääkomponenttipuun ja harvan satunnaisprojektiopuun. Verrattuna alkuperäisiin pääkomponenttipuihin ja satunnaisprojektiopuihin, nämä harvat puut ovat nopeampia rakentaa, vaativat vähemmän muistia ja ovat nopeampia ALN-kyselyihin vastattaessa. Lisäksi väitöskirjassa kehitetään äänestyshaku (voting search) menetelmänä kandidaattijoukon valitsemiseksi ALN-haussa. Kokeemme osoittavat, että äänestyshaku on tehokkaampi aiemmin kandidaattijoukon valintaan käytettyyn taulukkohakuun (lookup search) verrattuna. Lisäksi väitöskirjaa lisää puihin perustuvien ALN-algoritmien käytettävyyttä kehittämällä menetelmän automaattiseen hyperparametrien säätämiseen. Julkaisimme kehittämämme ALN-algoritmin (kokoelma harvoja satunnaisprojektiopuita yhdistettynä äänestyshakuun varustettuna automaattisella hyperparametrien säätämisellä) avoimen lähdekoodin C++-kirjastona (käytettävissä Pythonin kautta).
Väitöskirjan toinen osio perustuu havaintoon, että kandidaattijoukon valinta ALN-haussa voidaan muotoilla moniluokkaisena luokitteluongelmana. Tässä koneoppimisviitekehyksessä avaruuden osiointiin pohjautuvat tietorakenteet (puut ja hajautustaulut) tulkitaan osiointiluokittelijoina. Kokeidemme mukaan tähän tulkintaan perustuva luonnollinen luokittelija on tehokkaampi kandidaattijoukonvalintamenetelmä kuin aiemmin käytetty taulukkohaku ja tässä väitöskirjassa aiemmin esitelty äänestyshaku. Luonnollista luokittelijaa voidaan käyttää minkä tahansa avaruuden osiointiin perustuvan tietorakenteen kanssa tehostamaan kyseisen tietorakenteen toimintaa ALN-kyselyihin vastaamisessa.
Sen lisäksi, että se lisää aiempien avaruuden osiointiin perustuvien tietorakenteiden suorituskykyä, väitöskirjassa esitelty koneoppimisviitekehys mahdollistaa minkä tahansa olemassa olevan (moniluokkaisen) luokittelijan käyttämisen tietorakenteena lähimmän naapurin hakuun. Siten väitöskirja avaa kokonaan uuden tutkimussuunnan ALN-hakuun, joka on vakiintunut algoritminen ongelma. Havainnollistamme tätä mahdollisuutta käyttämällä (moniluokkaista) satunnaismetsäluokittelijaa tietorakenteena ALN-hakuun.
Kandidaattijoukon valinnan muotoileminen luokitteluongelmana myös mahdollistaa ALN-haun tarkastelemisen tilastotieteellisen oppimisteorian viitekehyksessä. Tarkemmin sanottuna osoitamme riittävän ehdon avaruuden osiointiin perustuvien luokittelijoiden tarkentuvuudelle ALN-hakuun. Todistamme kronologisten kd-puiden ja satunnaisprojektiopuiden tarkentuvuuden osoittamalla, että ne täyttävät tämän riittävän ehdon.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio tulee olemaan saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-9955-3.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: ville.o.hyvonen@helsinki.fi.