Vi introduserer en av de beste hakkene i maskinlæring: Hashing-trikset

2018 har blitt hyllet av forskjellige utsalgssteder som året da spam vil begynne å dø fordi maskinlæringsalgoritmer vil bli nesten perfekte til å finne ut hva som er ekte post og hva ikke. Jeg er ikke overbevist om at det noen gang vil skje (fremskritt i maskinlæring kutter begge veier), men jeg vil gjerne dele noen generelle tanker om hvordan ML-baserte enkle spam-klassifisere er bygget og hvordan du kan overvinne et betydelig problem, filtrere omgåelse, bruker en av de beste hacks i maskinlæring: hashing-trikset. Det er nyttig utenfor spamdeteksjon også.

Bygge en enkel spam klassifiserer

For dokumentklassifiseringsoppgaver, inkludert spam-klassifisering, starter man vanligvis med å bygge det som er kjent som en bag-of-word-representasjon. Gitt et sett med kjente spam- og ikke-spam-e-poster, blir hvert unike ord lagt til et ordforråd og tildelt en unik indeks, vanligvis fra 0. La oss si, for korthets skyld, at vi har et sett med to korte teksteksempler, ett som er spam og en annen som er legitim:

jeg tjener ti tusen dollar per uke bare for å surfe på nettet! (Spam)
har du fri til et møte tidlig neste uke? (ikke spam)

Hvis vi skanner datasettet og begynner å bygge ordforrådet vårt, kan vi ende opp med noe slikt:

i: 0
lage: 1
ti: 2
tusen: 3
dollar: 4
per: 5
uke: 6
bare: 7
surfing: 8
9:
nett: 10
er: 11
du: 12
gratis: 13
for: 14
a: 15
møte: 16
tidlig: 17
neste: 18

Det er totalt 19 unike ord, og hver er tildelt en unik indeks (merk at orduken vises i begge eksemplene). Neste trinn er å lage funksjonsvektorer for vår maskinlæringsmodell. Vi starter med å lage en nullkolonnevektor for hvert eksempel, med samme antall elementer som det er ord i ordforrådet vårt (19):

jeg tjener ti tusen dollar per uke bare for å surfe på nettet! (Spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
har du fri til et møte tidlig neste uke? (ikke spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Så, for hvert ord i hvert eksempel, utfører vi et vokabularoppslag for å få indeksen og øke verdien på den indeksen med én:

jeg tjener ti tusen dollar per uke bare for å surfe på nettet! (Spam)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
har du fri til et møte tidlig neste uke? (ikke spam)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

De resulterende trekkvektorene er fremstillinger av bag-of-word. BOW-representasjoner kaster vanligvis ut informasjon om tegnsetting og ordensrekkefølge, men for mange problemer er dette ikke et problem. Mer sofistikerte BOW-representasjoner bruker TF-IDF-vekter og / eller n-gram i stedet for rå ordtelling, men den grunnleggende ideen er den samme.

Når vi har BOW-funksjonsvektorer, kan vi trene en binær klassifisering for å bygge et spamfilter. Det er mange valg angående læringsalgoritmer, men de vanligste mistenkte er Naïve Bayes, tilfeldige skoger, logistisk regresjon og, i økende grad, nevrale nettverk. Gitt en trent modell, kan vi bruke ordforrådet til å mate inn en ny e-post som en BOW-vektor og forutsi om eksemplet er spam. Vær oppmerksom på at for sanntids inferanse, må vi holde ordforrådet i RAM for å være så raskt som mulig.

Problemstillingen: omgåelse av filter

Spammere er listige. En populær måte å sikre at spam ikke blir filtrert ut er å blande inn ord som ikke er ordforrådet som brukes til å lære klassifiseringen. Tenk for eksempel følgende, litt forfulgt setning:

I maike er du tusenvis av gratis for et $ $ s surfing-web-møte tidlig i neste uke

Det er klart at dette ikke er noe noen vil anse som en legitim e-post. Men hva skjer hvis vi bruker ordforrådet vårt til å lage en BOW-vektor for dette eksempelet? De første åtte ordene er ikke i ordforrådet vårt i det hele tatt, og kommer ikke inn i det. Resten er, noe som resulterer i følgende vektor:

I maike er du tusenvis av gratis for et $ $ s surfing-web-møte tidlig i neste uke
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Denne vektoren er den samme som for det legitime eksemplet. Har du fri til et møte tidlig neste uke? . Enhver klassifiserer som er trent på våre eksempler, vil sannsynligvis tro at denne søppelposten er legitim. Dette er et betydelig problem, og ikke så lett å løse som man kanskje tror. Vi kan legge til de nye ordene i ordforrådet vårt, men det vil bety at den resulterende funksjonenes vektors størrelse endres, og det samme vil ordforrådet. Maskinlæringsmodeller lærer vanligvis på eksempler på opplæring i fast størrelse, så vi må trene om modellen vår fra bunnen av. Det tar tid, og mens vi gjør det, vil den gamle klassifiseringen fortsette å godta spam. Vi trenger en løsning som a) kan takle ord utenfor ordforrådet, b) krever ikke at vi omskolerer modellene våre fra bunnen av hver gang vi støter på et nytt ord eller stavefeil, og c) er så nøyaktige som mulig. Hvis vi kunne slippe unna uten å holde et stort ordforråd i RAM, enda bedre.

Vi introduserer hasing-trikset

Hash-funksjoner er grunnleggende for informatikk. Det er mange forskjellige typer hasjfunksjoner, men de gjør alle de samme tingene: kartdata av vilkårlige størrelser til data av en fast størrelse. Vanligvis spytter de ut et tall (kjent som en hasj):

"John Doe" -> hasjfunksjon -> 34
"Jane Doe" -> hasjfunksjon -> 48

Logikken som en hasj beregnes avhenger av selve hasjfunksjonen, men alle hasjfunksjoner har de samme felles egenskapene:

  • Hvis vi mater den samme inngangen til en hasjfunksjon, vil den alltid gi samme utgang.
  • Valget av hasjfunksjon bestemmer rekkevidden for mulige utganger, dvs. området er alltid fast (f.eks. Tall fra 0 til 1024).
  • Hash-funksjoner er enveis: gitt en hasj kan vi ikke utføre et omvendt oppslag for å bestemme hva innspillet var.
  • Hash-funksjoner kan gi samme verdi for forskjellige innganger (kollisjon).

Hash-funksjoner er utrolig nyttige på omtrent hvilket som helst område innen informatikk, men hvordan kan de brukes til å løse problemet med ordforrådet til spam-klassifiseringen vår? Svaret er ikke umiddelbart åpenbart, men det første trinnet er å bli kvitt ordforrådet vårt helt. I stedet for når vi konstruerer våre BOW-representasjoner, vil vi begynne med å lage en null-kolonnevektor med et enormt antall (si, 2²⁸) elementer for hvert av våre treningseksempler:

jeg tjener ti tusen dollar per uke bare for å surfe på nettet! (Spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementer)
har du fri til et møte tidlig neste uke? (ikke spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementer)

Deretter velger vi en hasjfunksjon f som spiser strenger og gir ut verdier i området [0, 2²⁸). Med andre ord sørger vi for at hasjfunksjonen vår aldri adresserer en indeks utenfor dimensjonene til funksjonsvektorene våre.

Etter denne initialiseringen, for hvert treningseksempel, mater vi hvert ord, ett etter ett, gjennom vår hasjfunksjon, og øker verdien til den gitte indeksen med en - akkurat som før. Vi kan ende opp med sparsomme vektorer som dette:

jeg tjener ti tusen dollar per uke bare for å 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)
har du fri til et møte tidlig neste uke? (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 prosessen er kjent som hashing-trikset.

Vi har nå vår BOW-representasjon, og kan trene en klassifiserer på dataene som før. Enkelt, nei? Vi har gitt bort fra bruk av et eget ordforråd, noe som betyr at vi ikke trenger å føre en potensielt stor liste over ord i RAM. Men det er bare en fin bieffekt - det virkelige problemet vi ønsker å takle er filteromgåelse ved hjelp av ordforråd. Så hvordan hjelper hasing-trikset?

La oss si at vi har en spam-klassifiserer som er trent på en haug med sparsomme 2²⁸ BOW-funksjonsvektorer. Gitt en ny post, gjør vi som før, initialiserer en 2²⁸ vektor og sender hvert ord gjennom hasjfunksjonen vår. I motsetning til tidligere, ender hvert eneste ord opp med å øke funksjonen. Gitt vår BOW-vektor blir alle ord - også nye - tatt i betraktning på prediksjonstidspunktet. Nye ord forverrer fortsatt nøyaktigheten til klassifiseringen vår, men det er ikke lenger mulig å omgå spamfilteret vårt helt ved å lage nye ord. Siden BOW-vektorene alle har samme størrelse, kan vi trinnvis passe modellen vår med nye spam / ikke-spam-eksempler uten å omskolere hele saken fra bunnen av. Det er en form for online læring: når en bruker markerer en e-post som spam, er modellen i stand til å lære av det trinnvis, uten å starte hele prosessen på nytt. For en praktisk applikasjon som spamfiltrering er dette en tydelig fordel med hashing av funksjoner: vi kan reagere raskt på angrep ved å gjøre læring så snart nye spam / ikke-spam-eksempler kommer inn.

Men hva med kollisjoner, hører jeg at du spør? Er det ikke mulig at en eller annen forsettlig stavefeil ender med å øke den samme indeksen som et legitimt ord når det går gjennom hasjfunksjonen? Ja, det kan skje, men hvis du velger vektorstørrelse (gjør den så stor som mulig) og hasjfunksjon nøye, er oddsen for at dette skal skje ubetydelig, og selv om det gjør det, påvirker det vanligvis ikke læring (eller nøyaktighet) ) så mye. Dokumentasjonen for standard hasjfunksjoner inkluderer vanligvis kollisjonssannsynligheter, så sørg for å slå dem opp når du lager din egen hashing-løsning.

Legg merke til at i noen tilfeller kan det hende du vil ha kollisjoner (for eksempel for å gruppere lignende legitime ord), i hvilket tilfelle kan det være lurt å bøtte dem før hasling.

Noen siste tanker

Det hashing-trikset er et av de ryddige triksene i maskinlæring som ikke får nesten like mye kjærlighet som det fortjener. Den eneste virkelige ulempen er at omvendte oppslag (output til input) ikke er mulig, men for mange problemer er det ikke et krav. Med mer generelle tanker, har hasing-trikset deg å bruke funksjonsvektorer med variabel størrelse med standard innlæringsalgoritmer (regresjon, tilfeldige skoger, fremover-nevrale nettverk, SVM-er, matrisefaktorisering, etc.). Det burde være nok til at de fleste maskinlærende utøvere i det minste blir litt begeistret.