Kryptering forventes normalt at bremse beregningen, men anvendelse af kryptografiske værktøjer til at “narre” en algoritme kan faktisk få det til at fungere hurtigere
Koncepter fra kryptografi kan anvendes til at fremskynde algoritmer
Tilføjelse af et strejf af kryptering til nøglealgoritmer, der bruges i kunstige intelligensmodeller, kunne – overraskende – gøre dem mere effektive takket være et trick af matematik.
Kryptografi involverer normalt krypterende meddelelser for at få dem til at se tilfældige til ondsindede tilskuere, mens de bevarer deres information ved at skjule et mønster i tilfældigheden. Denne tilfældighed kan derefter låses op med den korrekte nøgle.
Nu eller Zamir ved Tel Aviv University i Israel og Vinod Vaikuntanathan ved Massachusetts Institute of Technology har fundet, at en lignende brug af kryptografi også kan forbedre visse algoritmernes effektivitet ved at udnytte denne “pseudorandomness”. ”I stedet for at forsøge at få denne ondsindede spiller til at tro, at det, han ser, er tilfældighed, vil vi prøve (at) narre en algoritme,” siger Zamir.
Mange algoritmer bruger allerede tilfældighed i form af tilfældige matrixer, gitter med tilfældigt valgte tal, der kan gøre problemer lettere at løse ved at reducere deres størrelse. Zamir og Vaikuntanathan har fundet ud af, at udskiftning af disse tilfældige matrixer med interlopere, der kun syntes tilfældige, kaldet fældedikorerede matrixer, gjorde det muligt at multipliceres hurtigere sammen, hvilket fremskynder algoritmer, der involverer denne proces uden at ændre resultaterne.
Nøglen til dette trick er, at ligesom krypterede meddelelser, kan de fældedurerede matrixer låses op med en adgangskode, der afslører et mønster for de tilsyneladende tilfældige tal. Dette mønster fungerer som en genvej: Matrixerne kan multipliceres på én gang i stedet for at skulle multiplicere hvert nummer med hvert andet nummer, som normalt ville være påkrævet. ”Dette er forskellen mellem en linje og en firkant af samme størrelse,” siger Zamir.
Disse fældedorede matrixer kunne have adskillige applikationer. Maskinindlæringsalgoritmer bruger ofte tilfældige matrixer, når de trænes som en del af et værktøj kaldet en klassificering, der bruges til at skelne mellem forskellige datapunkter, såsom katte eller hunde i billeder. Dette involverer at se på meget store datasæt, men de tilfældige matrixer kan hjælpe dem med at gøre dem mindre.
Parret fandt også, at dette trick kunne hjælpe på andre områder, såsom datakomprimering, der bruger tilfældige matrixer til at bevare vigtige funktioner i et datasæt, mens de kasserer irrelevante data, eller søger efter lignende genstande, som dem, der bruges af musikanbefalingstjenester.
Martin Albrecht ved King’s College London siger, at brug af kryptografi på denne måde er et smart trick, men det vil sandsynligvis kun fungere godt i tilfælde, hvor algoritmer er afhængige af meget store tilfældige matrixer på grund af den måde, disse matrixer er designet på. ”De er solide speed-ups, men du har sandsynligvis brug for ganske store systemer for virkelig at se det,” siger Albrecht. ”Der vil være nogle seje applikationer, men det er ikke som om det vil blive spaltet ind overalt, og alt er magisk hurtigere.”