Breaking the Dimensionality Curse of Voronoi Tessellations

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.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-319984