skissemetoder

Skissemetoder, eller sketching-metoder, er en gruppe tilfeldige tilnærmings- og komprimeringsmetoder som lager små, forenklede representasjoner av store datasett eller matriser. Målet er å gjøre beregninger raskere og mer minnevennlige, samtidig som man bevarer viktige egenskaper som normer, innbyrtningsprodukter og rang. Skisser brukes ofte som mellomlagrede representasjoner i store linære algebra-oppgaver, regressing og maskinlæring.

Vanlige teknikker inkluderer random projeksjon, randomisert prøvetaking og hashing-baserte metoder. Random projeksjon reduserer dimensjonalitet ved å projisere data til lavere dimensjoner slik at avstander og innbyrtningsprodukter blant punkter beholdes med høy sannsynlighet (Johnson-Lindenstrauss-sammenheng). Projektene kan være dense eller sparsifiserte for å gjøre beregningene mer effektive. Random sampling og hashing-baserte sketches, som CountSketch og feature hashing, estimerer frekvenser eller lar modellen håndtere høyere dimensjoner ved å bruke hashfunksjoner til å fordele komponenter på en kontrollert måte. Leverage-score sampling velger rader eller kolonner basert på deres lineære påvirkning i dataene, noe som gir effektive lav-rang-tilnærminger. Det finnes også streaming-skisser og andre spesialiserte metoder.

Anvendelser omfatter tilnærmet matriseproduksjon og lav-rang-tilnærminger (for eksempel til SVD), effektive minstekvadrater-løsninger i store datamengder, regresjon, og store data-strømmer i online eller distribuert beregning. Skissemetoder brukes også i privatlivsbeskyttelse ved å konfidensielt aggregere data før analyse.

Teoretisk sett gir skissering sannsynlighetsbaserte garanti­er om at visse mål holdes innenfor et lite feilintervall etter skissen, ofte med den skisse-dekningen av størrelse avhengig av ønsket feilmargin og datas størrelse. Historisk har prinsippene røtter i sannsynlighetsteori og numerisk lineær algebra, og de ble særlig populært i store data- og maskinlæringssammenhenger i 2000- og 2010-årene.

---