0
Hopp til hovedinnhold

Thompson-sampling for komplekse problemer

Sondre Glimsdal disputerer for ph.d.-graden med avhandlingen “Towards Thompson Sampling for Complex Bayesian Reasoning” mandag 25. mai 2020. (Foto: Privat)

Det overordnede formålet med avhandlingen “Towards Thompson Sampling for Complex Bayesian Reasoning” er å vise hvordan Thompson-sampling kombinert med Bayesiansk modellering kan utvide algoritmens bruksområde, slik at den kan anvendes til å løse vanskeligere og mer komplekse problemer.

Sondre Glimsdal

Ph.d.-kandidat og Machine Learning Specialist

Disputasen foregår digitalt på internett fordi UiA er stengt på grunn av Corona covid-19-situasjonen. Se under for hvordan publikum kan overvære disputasen.

Sondre Glimsdal disputerer for ph.d.-graden med avhandlingen “Towards Thompson Sampling for Complex Bayesian Reasoning” mandag 25. mai 2020.

Han har fulgt doktorgradsprogrammet ved Fakultet for teknologi og realfag, med spesialisering i IKT.

Slik oppsummerer Sondre Glimsdal selv avhandlingen:

Thompson-sampling for komplekse problemer

Problemløsningsalgoritmen Thompson-sampling har de siste årene tatt verden med storm med sin imponerende effektivitet og eleganse. Hittil har imidlertid algoritmen kun blitt brukt til å løse såkalte “flerarmede banditt”-problemer, som har definerte kjennetegn og egenskaper.

Det overordnede formålet med avhandlingen “Towards Thompson Sampling for Complex Bayesian Reasoning” er å vise hvordan Thompson-sampling kombinert med Bayesiansk modellering kan utvide algoritmens bruksområde, slik at den kan anvendes til å løse vanskeligere og mer komplekse problemer.

Flerarmede banditter

Det flerarmede bandittproblemet kan illustreres slik: en gambler går inn i et kasino, og kan velge mellom flere spilleautomater (enarmede banditter). Han vet at én spilleautomat har høyere vinnersjanse enn de andre, men ikke hvilken. Utfordringen er dermed å finne den mest lønnsomme automaten, samtidig som man unngår å kaste bort penger på automater med dårligere vinnersjanse.

Algoritmer for å løse et slikt problem blir eksempelvis brukt for å avgjøre hvilke annonser som vises når man besøker en nettside. Annonsøren ønsker å vise frem annonsene som har størst sjanse for å bli klikket på. Man kan tenke at alle annonsene er hver sin spilleautomat. Det å spille betyr at man velger å vise en bestemt annonse. Kun hvis annonsen trykkes på får annonsøren en gevinst. Ved å raskt finne den mest lønnsomme spilleautomaten maksimeres samtidig avkastning på annonseinntektene.

Nye Bayesianske sannsynlighetsmodeller

Egenskapene til Thompson-sampling egner seg veldig godt i miljøer med balanse mellom innsamling av usikker informasjon og utnyttelse av informasjon, slik som i flerarmede bandittproblemer. Denne avhandlingen viser imidlertid at ved å erstatte logikken til spillemaskinene med en Bayesiansk sannsynlighetsmodell, kan man benytte Thompson-sampling for å håndtere mer komplekse problemer som krever resonnering.

Denne nye kombinasjonen av Thompson-sampling og Bayesiansk modellering er mer robust, effektiv og generell enn eksisterende metoder, og åpner også døren for å løse problemer algoritmen tidligere ikke har håndtert. 

For å vise styrken i denne metoden anvendes den over en rekke bruksområder i artiklene som ligger til grunn for avhandlingen, blant annet optimal organisering av varehus basert på kundeadferd, estimering av reisetid og optimering av levetid for trådløse sensorenheter.

Disputasfakta:

Kandidaten: Sondre Glimsdal (1986, Oslo) Fagbrev som Serviceelektroniker. Bachelor- og mastergrad (2013 Thesis: "Efficient gaussian process based optimistic knapsack sampling with applications to stochastic resource allocation") i IKT ved Universitet i Agder. Arbeider nå som Machine Learning Specialist i Confirmit AS.

Prøveforelesning og disputas finner sted digitalt på internett i konferanseprogrammet Zoom (lenke under).

Disputasen blir ledet av professor Andreas Prinz, Institutt for informasjons- og kommunikasjonsteknologi, UiA

Prøveforelesning kl 10:15

Disputas kl 12:15

Oppgitt emne for prøveforelesning: “Explainable AI: why and how?"

Tittel på avhandling: “Towards Thompson Sampling for Complex Bayesian Reasoning”

Søk etter avhandlingen i AURA - Agder University Research Archive, som er et digitalt arkiv for vitenskapelige artikler, avhandlinger og masteroppgaver fra ansatte og studenter ved Universitetet i Agder. AURA blir jevnlig oppdatert.

Opponenter:

Førsteopponent: Prof. Marek Druzdzel, Bialystok University of Technology, Bialystok, Poland

Annenopponent: Professor Jim Tørresen, Universitetet i Oslo

Bedømmelseskomitéen er ledet av professor Vladimir Oleshchuk, Institutt for informasjons- og kommunikasjonsteknologi, UiA

Veiledere i doktorgradsarbeidet var professor Ole-Christoffer Granmo, UiA (hovedveileder) og førsteamanuensis Svein Olav Glesaaen Nyberg, UiA (medveileder)

Slik gjør du som publikum:

Disputasen er åpen for alle, men for å følge prøveforelesning og disputas må du melde deg som publikummer på denne lenken: https://uia.pameldingssystem.no/disputas-sondre-glimsdal Du vil da få en Zoom-lenke i retur.

Vi ber publikum om å ankomme digitalt tidligst ti minutter før oppgitt tid - det vil si til prøveforelesningen 10:05 og disputasen tidligst kl 12:05. Etter disse klokkeslettene kan du når som helst forlate og komme inn igjen i møtet. Videre ber vi om at publikum slår av mikrofon og kamera, og har dette avslått under hele arrangementet. Det gjør du nederst til venstre i bildet når du er i Zoom. Vi anbefaler å velge «Speaker view». Dette velger du oppe til høyre i bildet når du er i Zoom.

Opponent ex auditorio:

Disputasleder inviterer til spørsmål ex auditorio i innledningen i disputasen, med tidsfrister. Disputasleders e-post er tilgjengelig i chat-funksjonen under disputasen. Spørsmål om ex auditorio kan sendes til disputasleder Andreas Prinz på e-post andreas.prinz@uia.no

Avhandlingen er tilgjengelig her: https://uia.brage.unit.no/uia-xmlui/handle/11250/2655240

Lenke til disputasen, som formidles i konferanseprogrammet Zoom: 

Disputasen er åpen for alle, men for å følge prøveforelesning og disputas må du melde deg som publikummer på denne lenken:

https://uia.pameldingssystem.no/disputas-sondre-glimsdal Du vil da få en Zoom-lenke i retur.

Her er framgangsmåten for å bruke Zoom: support.zoom.us om du ikke kommer inn ved å klikke på lenken.