LearnedSketch AI-system til frekvensestimering forbedrer estimater af populære søgeforespørgsler

Hvis du kigger under motorhjelmen på internettet, du vil finde masser af gear, der kører rundt, som gør det hele muligt.

For eksempel, tag en virksomhed som AT&T. De skal nøje forstå, hvilke internetdata der skal hen, så de bedre kan rumme forskellige niveauer af brug. Men det er ikke praktisk at overvåge hver pakke data præcist, fordi virksomheder simpelthen ikke har ubegrænsede mængder lagerplads. (Forskere kalder dette faktisk "Britney Spears-problemet, " opkaldt efter søgemaskiners langvarige bestræbelser på at måle trendende emner.)

På grund af dette, teknologivirksomheder bruger specielle algoritmer til groft at estimere mængden af ​​trafik på vej til forskellige IP-adresser. Traditionelle frekvensestimeringsalgoritmer involverer "hashing, " eller tilfældigt opdele varer i forskellige buckets. Men denne tilgang udelukker det faktum, at der er mønstre, der kan afsløres i store mængder data, som hvorfor én IP-adresse har en tendens til at generere mere internettrafik end en anden.

Forskere fra MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) har udtænkt en ny måde at finde sådanne mønstre ved hjælp af maskinlæring.

Deres system bruger et neuralt netværk til automatisk at forudsige, om et specifikt element vil optræde ofte i en datastrøm. Hvis det gør, den er placeret i en separat bøtte med såkaldte "heavy hitters" til at fokusere på; hvis det ikke gør, det håndteres via hashing.

"Det er som en triage situation på en skadestue, hvor vi prioriterer de største problemer, før vi kommer til de mindre, " siger MIT professor Piotr Indyk, medforfatter til et nyt papir om systemet, der vil blive præsenteret i maj på den internationale konference om læringsrepræsentationer i New Orleans, Louisiana. "Ved at lære egenskaberne af heavy hitters, når de kommer ind, vi kan lave frekvensestimering meget mere effektivt og med meget mindre fejl."

I test, Indyks team viste, at deres læringsbaserede tilgang havde op mod 57 procent færre fejl til at estimere mængden af ​​internettrafik i et netværk, og op mod 71 procent færre fejl for at estimere antallet af forespørgsler for en given søgeterm.

Teamet kalder deres system "LearnedSketch, fordi de ser det som en metode til at "skitsere" dataene i en datastrøm mere effektivt. Så vidt de ved, det er verdens første maskinlæringsbaserede tilgang til ikke kun selve frekvensestimering, men for en bredere klasse af såkaldte "streaming"-algoritmer, der bruges i alt fra sikkerhedssystemer til naturlig sprogbehandling.

LearnedSketch kunne hjælpe teknologivirksomheder med mere effektivt at knuse alle slags meningsfulde data, fra trendemner på Twitter til stigninger i webtrafik, der kan tyde på fremtidige distribuerede denial-of-service-angreb. E-handelsvirksomheder kunne bruge det til at forbedre produktanbefalinger:Hvis LearnedSketch fandt ud af, at kunder har en tendens til at handle mere sammenlignende for husholdningselektronik end for legetøj, den kunne automatisk afsætte flere ressourcer til at sikre nøjagtigheden af ​​sine frekvenstællinger for elektronik.

"Vi er alle bekendt med forbrugervendte applikationer af maskinlæring som naturlig sprogbehandling og taleoversættelse, " siger Sergei Vassilvitskii, en datalog, der studerer algoritmisk maskinlæring og ikke var involveret i projektet. "Denne arbejdslinje, på den anden side, er et spændende eksempel på, hvordan man bruger maskinlæring til at forbedre selve kernecomputersystemet."

Hvad der også er overraskende ved LearnedSketch er, at som den lærer at tælle genstande, strukturen, den lærer, kan generaliseres selv til usete genstande. For eksempel, at forudsige, hvilke internetforbindelser der har mest trafik, modellen lærer at gruppere forskellige forbindelser efter præfikset for deres destinations-IP. Dette skyldes, at steder, der genererer stor trafik, som store virksomheder og universiteter, har tendens til at dele et bestemt præfiks.

"Vi kombinerer modellen med klassiske algoritmer, så vores algoritme naturligt arver værst tænkelige garantier fra de klassiske algoritmer, " siger ph.d.-studerende Chen-Yu Hsu, medforfatter til det nye blad. "Denne slags resultater viser, at maskinlæring i høj grad er en tilgang, der kunne bruges sammen med de klassiske algoritmiske paradigmer som 'del og hersk' og dynamisk programmering."

Denne historie er genudgivet med tilladelse fra MIT News (web.mit.edu/newsoffice/), et populært websted, der dækker nyheder om MIT-forskning, innovation og undervisning.