Algoritmer for klyngeanalyse og lav-rang tilnærmings problem

I den moderne verden er det mye som styres av maskinlæring. Eksemplene strekker seg fra hvilke poster vi ser i nyhetsfeeden vår til vurderinger om hvorvidt en person sannsynligvis vil være en gjentagende lovbryter. Samtidig som at kunstig intelligens tar over flere oppgaver så øker bekymringene rundt forklarbarheten og gjennomsiktigheten til slike systemer. En rekke maskinlæringsprimitiver brukes som byggeklosser i konstruksjonen av kompliserte løsninger på ulike problemer. Flere av disse primitivene er relativt enkle og veldefinerte, så det er viktig at vi studerer disse grundig. Vi ønsker oss algoritmer som kan komme med beviselige garantier for. Det betyr at algoritmene alltid må finne riktig svar og at tiden de bruker på beregningene må kunne avgrenses.

Et av disse primitivene er klyngeanalyse. I dette problemet har vi en rekke enheter, og vi må dele dem inn i noen få grupper slik at lignende enheter er med i samme gruppe. Klyngeanalyse er en av de mest kjente verktøyene i maskinlæring og brukes for eksempel til å klassifisere vev i tomografisk skanning eller til å klassifisere brukere i et sosialt nettverk. Men å finne en optimal inndeling er et notorisk vanskelig problem og vi forventer faktisk ikke at det er mulig å finne en rask generell algoritme for det. Derfor er det interessant å identifisere tilfeller når dette problemet kan løses optimalt.

Simonov sin avhandling utvider både teorien bak standard klyngeanalyse og også mer generelle varianter av problemet med et fokus på algoritmisk ansvarlighet. Hva kan vi si om klyngeproblemet hvis vi vil finne en optimal rettferdig inndeling? Dette er viktig i situasjoner hvor klyngene brukes som grunnlag for beslutningstaking siden kostnadsoptimal inndeling kan være diskriminerende for visse grupper. Et annet spørsmål er om man kan utføre klyngeanalyse effektivt når data har gått tapt eller om data endres av en fiende? Dette er noen av temaene som er studert i avhandlingen.

Personalia

Kirill Simonov har vært doktorgradsstudent i algoritmegruppen ved Institutt for Informatikk siden april 2018 hvor han har vært veiledet av Prof. Fedor V. Fomin. Han har en bachelorgrad og mastergrad i matematikk fra Saint Petersburg State University.