Koneoppimisen soveltaminen graafihakualgoritmien ohjaamisessa
Luukka, Joel (2017)
2017
Tietojenkäsittelytieteiden tutkinto-ohjelma - Degree Programme in Computer Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2017-12-11
Julkaisun pysyvä osoite on
http://urn.fi/URN:NBN:fi:uta-201712182945
http://urn.fi/URN:NBN:fi:uta-201712182945
Tiivistelmä
Graafirakenteita käytetään monissa eri sovelluksissa kuvaamaan niiden toimintaympäristöjen lainalaisuuksia. Graafien laajan sovelluskentän vuoksi graafihakualgoritmit ovat keskeisessä roolissa sovellusten toteutuksessa. Graafihakuongelmaan on kehitetty erittäin hyvin toimivia algoritmeja, mutta tietoaineistojen kasvaminen ja sovelluskohteiden monimutkaistuminen asettavat yhä korkeampia tehokkuusvaatimuksia graafihakualgoritmeille.
Graafihakumenetelmät ovat karkeasti jaettavissa kahteen joukkoon: heikkoihin hakumenetelmiin, jotka ovat suoritettavissa missä tahansa graafissa, ja heuristisiin hakumenetelmiin, jotka käyttävät sovellus-, hakutehtävä- ja graafikohtaista tietoa tehostaakseen hakua. Heikot hakumenetelmät ovat toimintavarmoja, mutta suorittavat paljon ylimääräisiä toimenpiteitä haun aikana, mikä tuottaa tehottomuutta. Heuristiset hakumenetelmät pystyvät välttämään osan ylimääräisistä vaiheista, mutta heuristisia hakuja on mahdollista räätälöidä vain rajattuun määrään sovelluskohteita.
Tässä tutkielmassa esittelen uuden koneoppimista käyttävän graafihakumenetelmän, jonka oppimistehtävänä on tuottaa malli, joka ohjaa hakua heurististen hakumenetelmien tapaan. Menetelmän oppiva osa perustuu vahvistusoppimiseen, jonka avulla voidaan purkaa tehokkaiden hakumenetelmien asettamia vaatimuksia graafien kuvaukseen ja laajentaa siten näiden hakumenetelmien sovelluskenttää.
Oppivan haun toimintaa mitattiin kahdessa kokeessa. Ensimmäisessä kokeessa oppivaa hakua verrattiin tehokkaaseen heuristiseen hakumenetelmään sille soveltuvissa hakutehtävissä. Toisessa kokeessa oppivan haun toimintaa tutkittiin heuristisille hauille sopimattomassa hakutehtävässä, jossa oppivan haun vertailukohtana käytettiin yksinkertaista leveyshakua.
Kokeiden tulosten perusteella oppivaa hakua voidaan pitää hyvänä keinona toteuttaa tehokkaampia hakumenetelmiä sovelluskohteissa, joissa heuristista hakua ei ole mahdollista käyttää. Tutkielmassa esitetty oppiva haku vaatii kuitenkin suuren muistimäärän sisäisen mallinsa ylläpitämiseen, mikä on otettava huomioon oppivan haun soveltamisessa ja jatkokehityksessä.
Graafihakumenetelmät ovat karkeasti jaettavissa kahteen joukkoon: heikkoihin hakumenetelmiin, jotka ovat suoritettavissa missä tahansa graafissa, ja heuristisiin hakumenetelmiin, jotka käyttävät sovellus-, hakutehtävä- ja graafikohtaista tietoa tehostaakseen hakua. Heikot hakumenetelmät ovat toimintavarmoja, mutta suorittavat paljon ylimääräisiä toimenpiteitä haun aikana, mikä tuottaa tehottomuutta. Heuristiset hakumenetelmät pystyvät välttämään osan ylimääräisistä vaiheista, mutta heuristisia hakuja on mahdollista räätälöidä vain rajattuun määrään sovelluskohteita.
Tässä tutkielmassa esittelen uuden koneoppimista käyttävän graafihakumenetelmän, jonka oppimistehtävänä on tuottaa malli, joka ohjaa hakua heurististen hakumenetelmien tapaan. Menetelmän oppiva osa perustuu vahvistusoppimiseen, jonka avulla voidaan purkaa tehokkaiden hakumenetelmien asettamia vaatimuksia graafien kuvaukseen ja laajentaa siten näiden hakumenetelmien sovelluskenttää.
Oppivan haun toimintaa mitattiin kahdessa kokeessa. Ensimmäisessä kokeessa oppivaa hakua verrattiin tehokkaaseen heuristiseen hakumenetelmään sille soveltuvissa hakutehtävissä. Toisessa kokeessa oppivan haun toimintaa tutkittiin heuristisille hauille sopimattomassa hakutehtävässä, jossa oppivan haun vertailukohtana käytettiin yksinkertaista leveyshakua.
Kokeiden tulosten perusteella oppivaa hakua voidaan pitää hyvänä keinona toteuttaa tehokkaampia hakumenetelmiä sovelluskohteissa, joissa heuristista hakua ei ole mahdollista käyttää. Tutkielmassa esitetty oppiva haku vaatii kuitenkin suuren muistimäärän sisäisen mallinsa ylläpitämiseen, mikä on otettava huomioon oppivan haun soveltamisessa ja jatkokehityksessä.