Breaking the Dimensionality Curse of Voronoi Tessellations
Tid: Må 2022-11-07 kl 15.00
Plats: F3 Lindstedtsvagen 26
Videolänk: https://kth-se.zoom.us/j/69595665882
Språk: Engelska
Ämnesområde: Datalogi
Respondent: Vladislav Polianskii , Robotik, perception och lärande, RPL
Opponent: Professor Michael Bronstein, University of Oxford, Oxford, United Kingdom
Handledare: Florian T. Pokorny, Robotik, perception och lärande, RPL
QC 20221017
Abstract
Med hänsyn till omfattningen av området artificiell intelligens kan indelningen av de underliggande metoderna ofta begränsas till antingen en probabilistisk eller en geometrisk synvinkel. En sådan uppdelning är särskilt utbredd inom mer klassisk maskininlärning, "före-neurala-nätverk", om man jämför Bayesiansk modellering med mer deterministiska modeller som k-närmste grannar.
Den forskning som bedrivs i avhandlingen bygger på studier och utveckling av geometriskt grundade metoder, hämtade från områdena beräkningstopologi och geometri, som tillämpas på maskininlärningsuppgifter. Arbetet knyts samman med analysen av naturliga grannskapspartitioner i datarummet som kallas Voronoi-tessellationer, liksom deras dubbla Delaunay-tessellationer. Ett grundläggande problem som uppstår när man arbetar med dessa konstruktioner är deras överväldigande höga geometriska komplexitet i höga dimensioner som är väldigt vanliga i moderna maskininlärningsuppgifter. Vi presenterar en grupp liknande tekniker som är utformade för att lindra dessa begränsningar och göra det möjligt att arbeta med Voronoi-tessellationer implicit i godtyckliga dimensioner utan att de konstrueras explicit. Teknikerna är baserade på ett strålkastningsförfarande, en utbredd metodik som har fått fäste inom områden som stokastisk geometri och datorgrafik. Vi presenterar tillämpningar av sådana dekompositioner på vanliga maskininlärningsproblem, t.ex. klassificering, täthetsuppskattning och aktiv interpolering. Vi går även igenom metoderna för approximation av Delaunay-grafer och för en mer allmän diskussion om ämnet högdimensionell geometrisk analys.