Introductie van een van de beste hacks in machine learning: de hashtruc

2018 is geprezen door verschillende verkooppunten als het jaar waarin spam begint te sterven omdat algoritmen voor machine learning bijna perfect zullen zijn om uit te zoeken wat echte e-mail is en wat niet. Ik ben er niet van overtuigd dat dit ooit zal gebeuren (vooruitgang in machine learning sneed beide kanten op), maar ik wil graag wat algemene gedachten delen over hoe ML-gebaseerde eenvoudige spamclassificaties worden gebouwd en hoe een belangrijk probleem, filteromzeiling, met een van de beste hacks in machine learning: de hashtruc. Het is ook nuttig buiten spamdetectie.

Een eenvoudige spamclassificator bouwen

Voor documentclassificatietaken, waaronder spamclassificatie, begint men meestal met het bouwen van een zogenaamde BOW-weergave (bag-of-words). Gegeven een reeks bekende spam- en niet-spam-e-mails, wordt elk uniek woord toegevoegd aan een vocabulaire en wordt een unieke index toegewezen, meestal beginnend bij 0. Laten we omwille van de duidelijkheid zeggen dat we een set van twee korte tekstvoorbeelden hebben, één dat is spam en een andere die legitiem is:

ik verdien tienduizend dollar per week gewoon op internet! (spam)
bent u vrij voor een vergadering begin volgende week? (geen spam)

Als we de dataset scannen en beginnen met het opbouwen van onze vocabulaire, kunnen we zoiets als dit eindigen:

i: 0
maken: 1
tien: 2
duizend: 3
dollars: 4
per: 5
week: 6
gewoon: 7
surfen: 8
de: 9
web: 10
zijn: 11
jij: 12
gratis: 13
voor: 14
a: 15
vergadering: 16
vroeg: 17
volgende: 18

Er zijn in totaal 19 unieke woorden en elk krijgt een unieke index (merk op dat het woord week in beide voorbeelden voorkomt). De volgende stap is het maken van kenmerkvectoren voor ons machine-leermodel. We beginnen met het maken van een nulkolomvector voor elk voorbeeld, met hetzelfde aantal elementen als er woorden in onze vocabulaire zijn (19):

ik verdien tienduizend dollar per week gewoon op internet! (spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
bent u vrij voor een vergadering begin volgende week? (geen spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Vervolgens voeren we voor elk woord in elk voorbeeld een vocabulaire op om de index te krijgen en de waarde bij die index met één te verhogen:

ik verdien tienduizend dollar per week gewoon op internet! (spam)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
bent u vrij voor een vergadering begin volgende week? (geen spam)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

De resulterende kenmerkvectoren zijn representaties van zakjes woorden. BOW-representaties gooien meestal informatie over interpunctie en woordvolgorde weg, maar voor veel problemen is dit geen probleem. Meer geavanceerde BOW-representaties gebruiken TF-IDF-gewichten en / of n-grammen in plaats van ruwe woordtellingen, maar het basisidee is hetzelfde.

Zodra we onze BOW-functievectoren hebben, kunnen we een binaire classifier trainen om een ​​spamfilter te bouwen. Er zijn veel keuzes met betrekking tot leeralgoritmen, maar de meest voorkomende verdachten zijn Naïeve Bayes, willekeurige bossen, logistieke regressie en, in toenemende mate, neurale netwerken. Gegeven een getraind model, kunnen we de woordenschat gebruiken om een ​​nieuwe e-mail als een BOW-vector in te voeren en te voorspellen of het voorbeeld al dan niet spam is. Merk op dat we voor realtime inferentie de woordenschat in RAM zo snel mogelijk moeten houden.

Het probleem: filteromzeiling

Spammers zijn sluw. Een populaire manier om ervoor te zorgen dat spam niet wordt uitgefilterd, is door woorden te mixen die niet voorkomen in de woordenschat die wordt gebruikt om de classificator te leren. Overweeg bijvoorbeeld de volgende, licht gekunstelde zin:

ii mayke bent u duizenden gratis voor een $$$ s surf1ing de webz-vergadering begin volgende week

Het is duidelijk dat dit niet iets is dat iemand een legitieme e-mail zou overwegen. Maar wat gebeurt er als we onze vocabulaire gebruiken om een ​​BOW-vector voor dit voorbeeld te bouwen? De eerste acht woorden staan ​​helemaal niet in ons vocabulaire en halen het niet. De rest wel, resulterend in de volgende vector:

ii mayke bent u duizenden gratis voor een $$$ s surf1ing de webz-vergadering begin volgende week
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Deze vector is dezelfde als die voor het legitieme voorbeeld. Bent u begin volgende week vrij voor een vergadering? . Elke classificator die getraind is in onze voorbeelden, denkt waarschijnlijk dat deze spam legitiem is. Dit is een aanzienlijk probleem en niet zo eenvoudig op te lossen als men zou denken. We zouden de nieuwe woorden aan onze woordenschat kunnen toevoegen, maar dat zou betekenen dat de grootte van de resulterende functievectoren zal veranderen, net als de woordenschat zelf. Machine learning-modellen leren meestal op trainingsvoorbeelden met een vaste grootte, dus we moeten ons model helemaal opnieuw trainen. Dat kost tijd en terwijl we dat doen, blijft de oude classifier spam accepteren. We hebben een oplossing nodig die a) omgaat met woorden die buiten de woordenschat vallen, b) niet vereist dat we onze modellen helemaal opnieuw trainen elke keer dat we een nieuw woord of spelfout tegenkomen, en c) zo nauwkeurig mogelijk is. Als we konden wegkomen zonder een enorme woordenschat in RAM te houden, nog beter.

Introductie van de hashtruc

Hash-functies zijn fundamenteel voor de informatica. Er zijn veel verschillende soorten hashfuncties, maar ze doen allemaal hetzelfde: gegevens van willekeurige grootte toewijzen aan gegevens van een vaste grootte. Meestal spugen ze een nummer uit (bekend als een hash):

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

De logica waarmee een hash wordt berekend, is afhankelijk van de hash-functie zelf, maar alle hash-functies hebben dezelfde gemeenschappelijke kenmerken:

  • Als we dezelfde invoer naar een hash-functie voeren, geeft deze altijd dezelfde uitvoer.
  • De keuze van de hash-functie bepaalt het bereik van mogelijke uitgangen, d.w.z. het bereik is altijd vast (bijv. Getallen van 0 tot 1024).
  • Hash-functies zijn in één richting: met een hash kunnen we geen reverse lookup uitvoeren om te bepalen wat de invoer was.
  • Hash-functies kunnen dezelfde waarde uitvoeren voor verschillende ingangen (botsing).

Hash-functies zijn ongelooflijk nuttig in zowat elk gebied van de informatica, maar hoe kunnen ze worden gebruikt om het probleemloze vocabulaire van onze spamclassificatie op te lossen? Het antwoord is niet meteen duidelijk, maar de eerste stap is om ons vocabulaire helemaal kwijt te raken. In plaats daarvan beginnen we bij het construeren van onze BOW-representaties een nulkolomvector met een enorm aantal (zeg, 2²⁸) elementen voor elk van onze trainingsvoorbeelden:

ik verdien tienduizend dollar per week gewoon op internet! (spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementen)
bent u vrij voor een vergadering begin volgende week? (geen spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 elementen)

Vervolgens kiezen we een hashfunctie f die tekenreeksen opeet en waarden uitvoert in het bereik [0, 2²⁸). Met andere woorden, we zorgen ervoor dat onze hashfunctie nooit een index buiten de dimensies van onze functievectoren aanpakt.

Na deze initialisatie voeren we voor elk trainingsvoorbeeld elk woord een voor een door onze hashfunctie en verhogen we de waarde bij de gegeven index met één - net als voorheen. We kunnen eindigen met spaarzame vectoren zoals deze:

ik verdien tienduizend dollar per week gewoon op internet! (spam)
-> [0 ... 0 1 1 1 0 1 1 0 ... 0 1 1 1 1 0 1 1 0] (2 ^ 28 elementen)
bent u vrij voor een vergadering begin volgende week? (geen spam)
-> [0 1 0 1 0 ... 0 1 0 ... 0 1 0 ... 0 1 1 0 1 1 0 1] (2 ^ 28 elementen)

Dit proces staat bekend als de hashing-truc.

We hebben nu onze BOW-weergave en kunnen een classifier op de gegevens trainen zoals voorheen. Simpel toch? We hebben het gebruik van een afzonderlijke woordenschat vergeten, wat betekent dat we geen potentieel grote woordenlijst in RAM hoeven te bewaren. Maar dat is slechts een mooi neveneffect - het echte probleem dat we willen aanpakken, is filteromzeiling met behulp van woordenschat. Dus hoe helpt de hashtruc?

Stel dat we een spamclassificator hebben die is getraind in een aantal dunne 2²⁸ BOW-functievectoren. Als we een nieuw stuk e-mail ontvangen, doen we hetzelfde als voorheen, initialiseren we een 2²⁸-vector en voeren we elk woord door onze hashfunctie. In tegenstelling tot voorheen, verhoogt elk woord met een bepaalde eigenschapswaarde. Gezien onze BOW-vector, wordt elk woord - zelfs nieuwe - in aanmerking genomen bij het voorspellen. Nieuwe woorden verslechteren nog steeds de nauwkeurigheid van onze classificator, maar het is niet langer mogelijk om ons spamfilter volledig te omzeilen door nieuwe woorden te verzinnen. Omdat de BOW-vectoren allemaal even groot blijven, kunnen we ons model stapsgewijs uitrusten met nieuwe voorbeelden van spam / niet-spam zonder het geheel opnieuw te trainen. Het is een vorm van online leren: wanneer een gebruiker een e-mail markeert als spam, kan het model daar stapsgewijs van leren, zonder het hele proces opnieuw te starten. Voor een praktische toepassing zoals spamfiltering, is dit een duidelijk voordeel van hashen van functies: we kunnen snel reageren op aanvallen door te leren zodra er nieuwe voorbeelden van spam / niet-spam binnenkomen.

Maar hoe zit het met botsingen, hoor ik u vragen? Is het niet mogelijk dat sommige opzettelijke spelfouten dezelfde index verhogen als een legitiem woord terwijl het de hash-functie passeert? Ja, het kan gebeuren, maar als u uw vectorgrootte kiest (deze zo groot mogelijk maakt) en de hashfunctie zorgvuldig gebruikt, is de kans dat dit gebeurt te verwaarlozen, en zelfs als dit het geval is, heeft dit meestal geen invloed op het leren (of de nauwkeurigheid) ) zoveel. De documentatie voor standaard hash-functies bevat meestal botsingskansen, dus zorg ervoor dat u deze opzoekt wanneer u uw eigen hashtruc-oplossing maakt.

Houd er rekening mee dat u in sommige gevallen zelfs botsingen wilt (bijvoorbeeld voor het groeperen van vergelijkbare legitieme woorden), in welk geval u deze wilt emmer voordat u gaat hashen.

Enkele laatste gedachten

De hashtruc is een van die handige trucs in machine learning die bijna niet zoveel liefde krijgt als het verdient. Het enige echte nadeel is het feit dat reverse lookups (uitvoer naar invoer) niet mogelijk zijn, maar voor veel problemen is dat geen vereiste. In meer algemene termen denkend, stelt de hashing-truc je in staat om kenmerkende vectoren met variabele grootte te gebruiken met standaard leeralgoritmen (regressie, willekeurige forests, feed-forward neurale netwerken, SVM's, matrixfactorisatie, enz.). Dat zou genoeg moeten zijn om de meeste beoefenaars van machine learning op zijn minst een beetje enthousiast te maken.