Introduktion af en af ​​de bedste hacks i maskinlæring: Hashing-tricket

2018 er blevet hyldet af forskellige afsætningsmuligheder som året hvor spam vil begynde at dø, fordi maskinlæringsalgoritmer bliver næsten perfekte til at finde ud af, hvad der er reel mail, og hvad der ikke er. Jeg er ikke overbevist om, at det nogensinde vil ske (fremskridt inden for maskinlæring skærer begge veje), men jeg vil gerne dele nogle generelle tanker om, hvordan ML-baserede enkle spam-klassifikatorer er bygget, og hvordan man kan overvinde et væsentligt spørgsmål, filteromgåelse, ved hjælp af en af ​​de bedste hacks i maskinlæring: hashing-tricket. Det er også nyttigt uden spam-detektion.

Opbygning af en simpel spam-klassificering

For dokumentklassificeringsopgaver, herunder spam-klassificering, starter man normalt med at opbygge det, der er kendt som en BOW-ords-repræsentation. Givet et sæt kendte spam- og ikke-spam-e-mails, føjes hvert unikt ord til et ordforråd og tildeles et unikt indeks, typisk fra 0. Lad os sige, for kortfattethedens skyld, at vi har et sæt af to korte teksteksempler, et som er spam og en anden, der er legitim:

Jeg tjener ti tusind dollars om ugen bare ved at surfe på nettet! (Spam)
er du fri til et møde tidligt i næste uge? (ikke spam)

Hvis vi scanner datasættet og begynder at opbygge vores ordforråd, kan vi ende med noget lignende:

i: 0
fabrikat: 1
ti: 2
tusind: 3
dollars: 4
pr.: 5
uge: 6
bare: 7
surfing: 8
9:
web: 10
er: 11
dig: 12
gratis: 13
for: 14
a: 15
møde: 16
tidligt: ​​17
næste: 18

Der er i alt 19 unikke ord, og hver er tildelt et unikt indeks (bemærk, at ordet uge vises i begge eksempler). Det næste trin er at oprette funktionsvektorer til vores maskinlæringsmodel. Vi starter med at oprette en nulpolonnevektor for hvert eksempel med det samme antal elementer, som der er ord i vores ordforråd (19):

Jeg tjener ti tusind dollars om ugen bare ved at surfe på nettet! (Spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
er du fri til et møde tidligt i næste uge? (ikke spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Derefter udfører vi et ordforrådsopslag for hvert ord i hvert eksempel for at få indekset og øge værdien ved det indeks med et:

Jeg tjener ti tusind dollars om ugen bare ved at surfe på nettet! (Spam)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
er du fri til et møde tidligt i næste uge? (ikke spam)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

De resulterende trækvektorer er repræsentationer af tasker. BOW-repræsentationer smider typisk information om tegnsætning og ordrækkefølge, men for mange problemer er dette ikke et problem. Mere sofistikerede BOW-repræsentationer bruger TF-IDF-vægte og / eller n-gram i stedet for rå ordtællinger, men den grundlæggende idé er den samme.

Når vi først har vores BOW-funktionsvektorer, kan vi træne en binær klassificering til at opbygge et spamfilter. Der er mange valg med hensyn til indlæringsalgoritmer, men de mest almindelige mistænkte er Naïve Bayes, tilfældige skove, logistisk regression og i stigende grad neurale netværk. På baggrund af en trænet model kan vi bruge ordforrådet til at tilføje en ny e-mail som en BOW-vektor og forudsige, om eksemplet er spam. Bemærk, at for realtidsinferencer, er vi nødt til at holde ordforrådet i RAM for at være så hurtigt som muligt.

Problemet: filteromgåelse

Spammere er kunstige. En populær måde at sikre, at spam ikke filtreres ud, er at blande ord, der ikke er i ordforrådet, der blev brugt til at lære klassificeren. Overvej for eksempel følgende, lidt forfulgt dom:

Jeg er måske tusinder af gratis til et $ $ surf1ing-møde tidligt i næste uge

Det er klart, at dette ikke er noget, som nogen ville betragte som en legitim e-mail. Men hvad sker der, hvis vi bruger vores ordforråd til at bygge en BOW-vektor til dette eksempel? De første otte ord findes overhovedet ikke i vores ordforråd og kommer ikke ind. Resten er, hvilket resulterer i følgende vektor:

Jeg er måske tusinder af gratis til et $ $ surf1ing-møde tidligt i næste uge
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Denne vektor er den samme som for det legitime eksempel. Er du fri til et møde tidligt i næste uge? . Enhver klassificer, der trænes i vores eksempler, vil sandsynligvis synes, at denne spam er legitim. Dette er et markant problem og ikke så let at løse, som man måske tror. Vi kunne tilføje de nye ord til vores ordforråd, men det ville betyde, at den resulterende egenskabsvektorers størrelse ændres, ligesom ordforrådet selv. Maskinlæringsmodeller lærer typisk på eksempler på træning i fast størrelse, så vi bliver nødt til at omskolere vores model fra bunden. Det tager tid, og mens vi gør det, fortsætter den gamle klassificering med at acceptere spam. Vi har brug for en løsning, der a) kan håndtere ord uden ordforråd, b) kræver ikke, at vi omskolerer vores modeller fra bunden, hver gang vi støder på et nyt ord eller stavefejl, og c) er så nøjagtige som muligt. Hvis vi kunne slippe af sted uden at have et enormt ordforråd i RAM, er det endnu bedre.

Præsentation af hash-tricket

Hash-funktioner er grundlæggende for datalogi. Der er masser af forskellige typer hashfunktioner, men de gør alle de samme ting: kortlægge data i vilkårlige størrelser til data af en fast størrelse. Typisk spytter de et tal ud (kendt som en hash):

"John Doe" -> hash-funktion -> 34
"Jane Doe" -> hash-funktion -> 48

Den logik, hvormed en hash beregnes, afhænger af selve hashfunktionen, men alle hashfunktioner har de samme fælles egenskaber:

  • Hvis vi tilføjer den samme input til en hash-funktion, giver den altid den samme output.
  • Valget af hash-funktion bestemmer området for mulige output, dvs. området er altid fast (f.eks. Tal fra 0 til 1024).
  • Hash-funktioner er envej: med en hash kan vi ikke udføre en omvendt opslag for at bestemme, hvad input var.
  • Hashfunktioner udsender muligvis den samme værdi for forskellige indgange (kollision).

Hash-funktioner er utroligt nyttige i stort set ethvert område inden for datalogi, men hvordan kan de bruges til at løse problemet med ordforråd i vores spamklassificering? Svaret er ikke umiddelbart indlysende, men det første skridt er at slippe af med vores ordforråd helt. I stedet for, når vi konstruerer vores BOW-repræsentationer, vil vi starte med at lave en nul-søjlevektor med et enormt antal (sig, 2²⁸) elementer til hvert af vores træningseksempler:

Jeg tjener ti tusind dollars om ugen bare ved at surfe på nettet! (Spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementer)
er du fri til et møde tidligt i næste uge? (ikke spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementer)

Dernæst vælger vi en hash-funktion f, der spiser strenge og udsender værdier i området [0, 2²⁸). Med andre ord sørger vi for, at vores hash-funktion aldrig adresserer et indeks uden for vores funktionsvektors dimensioner.

Efter denne initialisering, for hvert træningsexempel, fodrer vi hvert ord, en efter en, gennem vores hash-funktion og øger værdien ved det givne indeks med en - ligesom før. Vi ender muligvis med sparse vektorer som denne:

Jeg tjener ti tusind dollars om ugen bare ved at surfe på nettet! (Spam)
-> [0 ... 0 1 1 1 0 1 1 0 ... 0 1 1 1 1 0 0 1 1 0] (2 ^ 28 elementer)
er du fri til et møde tidligt i næste uge? (ikke spam)
-> [0 1 0 1 0 ... 0 1 0 ... 0 1 0 ... 0 1 1 0 1 1 0 1] (2 ^ 28 elementer)

Denne proces er kendt som hashing-tricket.

Vi har nu vores BOW-repræsentation og kan træne en klassifikator på dataene som før. Enkelt, nej? Vi har forladt brugen af ​​et separat ordforråd, hvilket betyder, at vi ikke behøver at holde en potentielt stor liste over ord i RAM. Men det er kun en dejlig bivirkning - det egentlige problem, vi ønsker at tackle, er filteromgåelse ved hjælp af ordforråd. Så hvordan hjælper hash-tricket?

Lad os sige, at vi har en spam-klassifikator, der er trænet på en masse sparsomme 2²⁸ BOW-funktionsvektorer. Når vi får et nyt stykke mail, gør vi som før, initialiserer vi en 2²⁸ vektor og sender hvert ord gennem vores hashfunktion. I modsætning til før, ender hvert enkelt ord med at øge en vis egenskabsværdi. I betragtning af vores BOW-vektor er der taget hensyn til ethvert ord - også nyt - på forudsigelsestidspunktet. Nye ord forværrer stadig nøjagtigheden af ​​vores klassifikator, men det er ikke længere muligt at omgå vores spamfilter helt ved at sammensætte nye ord. Da BOW-vektorerne alle forbliver i samme størrelse, kan vi trinvis tilpasses vores model med nye spam / ikke-spam-eksempler uden at gendanne hele tingene fra bunden. Det er en form for online-læring: når en bruger markerer en e-mail som spam, er modellen i stand til at lære af denne gradvist, uden at genstarte hele processen. For en praktisk applikation som spamfiltrering er dette en klar fordel ved hashing af funktioner: vi kan reagere hurtigt på angreb ved at gøre læring, så snart nye spam / ikke-spam-eksempler kommer ind.

Men hvad med kollisioner, hører jeg, du spørger? Er det ikke muligt, at en vis forsætlig stavefejl ender med at øge det samme indeks som et legitimt ord, når det passerer gennem hash-funktionen? Ja, det kan ske, men hvis du vælger din vektorstørrelse (gør den så stor som muligt) og hashfunktion omhyggeligt, er oddsen for, at dette sker ubetydelig, og selvom det gør det, påvirker det normalt ikke læring (eller nøjagtighed) ) så meget. Dokumentationen for standard hash-funktioner inkluderer typisk kollisionssandsynligheder, så sørg for at slå dem op, når du laver din egen hash-trick-løsning.

Bemærk, at du i nogle tilfælde måske endda vil have sammenstød (f.eks. Til at gruppere lignende legitime ord), i hvilket tilfælde du måske ønsker at spandere dem inden hasling.

Nogle sidste tanker

Det hashende trick er et af de pæne tricks i maskinlæring, der ikke får næsten så meget kærlighed, som det fortjener. Den eneste virkelige ulempe er, at omvendte opslag (output til input) ikke er mulige, men for mange problemer er det ikke et krav. Når man tænker mere generelt, giver hashing-tricket dig mulighed for at bruge funktionsvektorer med variabel størrelse med standardindlæringsalgoritmer (regression, tilfældige skove, feed-forward neurale netværk, SVM'er, matrixfaktorisering osv.). Det burde være nok til at gøre de fleste maskinlærere i det mindste lidt spændte.