Представяме ви един от най-добрите хакове в машинното обучение: трикът на хеширане

2018 г. беше приветствана от различни търговски обекти като годината, когато спамът ще започне да умира, защото алгоритмите за машинно обучение ще станат почти перфектни при намирането на това какво е истинска поща и кое не. Не съм убеден, че това някога ще се случи (напредъкът в машинното обучение отрязва и двата начина), но бих искал да споделя някои общи мисли за това как са изградени прости ML-класификатори за спам и как да се преодолее значителен проблем, филтриране заобикаляне, използване на един от най-добрите хакове в машинното обучение: хеширащият трик. Полезно е и откриването на спам.

Изграждане на прост класификатор за спам

За задачи за класифициране на документи, включително класификация на нежелана поща, човек обикновено започва с изграждането на това, което е известно като представяне на пакет от думи (BOW). Като се има предвид набор от известни спам и не-спам имейли, всяка уникална дума се добавя към речник и им се присвоява уникален индекс, обикновено започващ от 0. Да речем, за краткост, че имаме набор от два кратки текстови примера, един което е спам и друго, което е законно:

правя десет хиляди долара на седмица, просто сърфирам в интернет! (спам)
свободен ли си за среща в началото на следващата седмица? (не е спам)

Ако сканираме набора от данни и започнем да изграждаме речника си, може да завършим с нещо подобно:

i: 0
направи: 1
десет: 2
хиляда: 3
долари: 4
на: 5
седмица: 6
само: 7
сърфиране: 8
: 9
уеб: 10
са: 11
ти: 12
безплатно: 13
за: 14
a: 15
среща: 16
рано: 17
следващ: 18

Има общо 19 уникални думи и на всяка е присвоен уникален индекс (обърнете внимание, че думата седмица се появява и в двата примера). Следващата стъпка е да създадем характеристики на вектори за нашия модел на машинно обучение. Започваме, като създаваме нулев вектор на колона за всеки пример, със същия брой елементи, както има думи в нашия речник (19):

правя десет хиляди долара на седмица, просто сърфирам в интернет! (спам)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
свободен ли си за среща в началото на следващата седмица? (не е спам)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

След това за всяка дума във всеки пример извършваме търсене на речник, за да получим индекса и увеличаваме стойността в този индекс с едно:

правя десет хиляди долара на седмица, просто сърфирам в интернет! (спам)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
свободен ли си за среща в началото на следващата седмица? (не е спам)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Резултатните вектори на функциите са представяне на думите. Представите на BOW обикновено изхвърлят информация за препинателните знаци и подредбата на думите, но за много проблеми това не е проблем. По-сложните BOW представителства използват TF-IDF тегла и / или n-грам вместо необработено число на думи, но основната идея е същата.

След като имаме нашите вектори за функции BOW, можем да обучим двоичен класификатор за изграждане на спам филтър. Има много възможности за алгоритми за учене, но най-честите заподозрени са наивни байеси, случайни гори, логистична регресия и все по-често невронни мрежи. Като имаме обучен модел, можем да използваме речника, за да се захранваме в нов имейл като BOW вектор и да прогнозираме дали примерът е или не. Обърнете внимание, че за извод в реално време трябва да запазим речника в RAM, за да бъде възможно най-бърз.

Проблемът: заобикаляне на филтъра

Спамерите са хитри. Един популярен начин да се уверите, че спамът не се филтрира е да се смесват с думи, които не са в речника, използван за изучаване на класификатора. Помислете например за следното, леко измислено изречение:

ii май ще сте безплатни хиляди безплатно за $$$ s сърфиране в webz среща в началото на следващата седмица

Ясно е, че това не е нещо, което някой би считал за легитимен имейл. Но какво се случва, ако използваме нашия речник, за да изградим BOW вектор за този пример? Първите осем думи изобщо не са в речника ни и няма да го направим. Останалите са, което води до следния вектор:

ii май ще сте безплатни хиляди безплатно за $$$ s сърфиране в webz среща в началото на следващата седмица
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Този вектор е същият като този за законния пример, свободен ли сте за среща в началото на следващата седмица? , Всеки класификатор, обучен по нашите примери, вероятно смята, че този спам е легитимен. Това е значителен проблем и не е толкова лесно да се реши, колкото може да се мисли. Бихме могли да добавим новите думи към речника си, но това ще означава, че размерът на векторите на произтичащите елементи ще се промени, както и самия речник. Моделите за машинно обучение обикновено се учат на примери за обучение с фиксиран размер, така че ще трябва да преквалифицираме модела си от нулата. Това отнема време и докато правим това, старият класификатор ще продължи да приема спам. Нуждаем се от решение, което а) може да се справи с думи извън речника; б) не изисква от нас да преквалифицираме моделите си от нулата всеки път, когато срещнем нова дума или правописна грешка, и в) е възможно най-точна. Ако можехме да се измъкнем, без да запазим огромен речник в RAM, още по-добре.

Представяме хеширащия трик

Функциите на хеш са основни за компютърните науки. Има много различни видове хеш функции, но всички те вършат едно и също нещо: картографират данни с произволни размери на данни с фиксиран размер. Обикновено изплюват номер (известен като хеш):

"John Doe" -> хеш функция -> 34
"Jane Doe" -> хеш функция -> 48

Логиката, чрез която се изчислява хеш, зависи от самата хеш функция, но всички хеш функции имат едни и същи общи характеристики:

  • Ако подадем един и същ вход към хеш функция, тя винаги ще даде същия изход.
  • Изборът на хеш функция определя обхвата на възможните изходи, т.е. диапазонът винаги е фиксиран (например числа от 0 до 1024).
  • Функциите на хеш са еднопосочни: като имаме хеш, не можем да извършим обратен търсене, за да определим какъв е бил входът.
  • Функциите хеш могат да извеждат една и съща стойност за различни входове (сблъсък).

Функциите на хеш са невероятно полезни почти във всяка област на компютърната наука, но как могат да бъдат използвани за отстраняване на проблема с извън речника на нашия спам класификатор? Отговорът не е веднага очевиден, но първата стъпка е да се освободим от речника си напълно. Вместо това, когато конструираме нашите BOW представления, ще започнем, като направим нулев вектор на колона с огромен брой (да речем, 2 ⁸) елементи за всеки от нашите примери за обучение:

правя десет хиляди долара на седмица, просто сърфирам в интернет! (спам)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 елемента)
свободен ли си за среща в началото на следващата седмица? (не е спам)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 елемента)

След това ще изберем хеш функция f, която изяжда низовете и извежда стойности в диапазона [0, 2²⁸). С други думи, ние се уверяваме, че нашата хеш функция никога няма да адресира индекс извън размерите на нашите вектори на функции.

След тази инициализация, за всеки пример за обучение, ние захранваме всяка дума, една по една, чрез нашата хеш функция и увеличаваме стойността в дадения индекс по една - точно както преди. Може да свършим с оскъдни вектори като този:

правя десет хиляди долара на седмица, просто сърфирам в интернет! (спам)
-> [0 ... 0 1 1 1 0 1 1 0 ... 0 1 1 1 1 0 1 1 0] (2 ^ 28 елемента)
свободен ли си за среща в началото на следващата седмица? (не е спам)
-> [0 1 0 1 0 ... 0 1 0 ... 0 1 0 ... 0 1 1 0 1 1 0 1] (2 ^ 28 елемента)

Този процес е известен като трика на хеширане.

Вече имаме нашето BOW представителство и можем да обучим класификатор на данните, както преди. Просто, нали? Забравихме използването на отделен речник, което означава, че не трябва да съхраняваме потенциално голям списък с думи в RAM. Но това е само хубав страничен ефект - истинският проблем, с който искаме да се справим, е заобикалянето на филтъра, използвайки думи извън речника. И така, как помага хеширащият трик?

Нека да кажем, че имаме класификатор на спам, обучен на куп оскъдни вектори с размер 2 ⁸⁸ BOW. Като имаме ново парче поща, ние правим както преди, инициализираме 2 ² вектор и предаваме всяка дума чрез нашата хеш функция. За разлика от преди, всяка една дума завършва с увеличаване на някаква стойност на функцията. Като се има предвид нашия BOW вектор, всяка дума - дори и нови - се взема предвид по време на прогнозиране. Новите думи все още влошават точността на нашия класификатор, но вече не е възможно да заобикаляме изцяло нашия филтър за спам чрез съставяне на нови думи. Тъй като всички вектори BOW остават в един и същ размер, можем постепенно да паснем на модела си с нови примери за спам / не-спам, без да преквалифицираме цялата работа от нулата. Това е форма на онлайн обучение: когато потребителят маркира имейл като спам, моделът е в състояние да се учи от това постепенно, без да рестартира целия процес. За практическо приложение като филтриране на спам, това е явно предимство на хеширането на функции: можем да реагираме бързо на атаки, като се учим веднага щом влязат нови примери за спам / не-спам.

Ами сблъсъците, чувам ли да питаш? Не е ли възможно някакво умишлено правопис да завърши с увеличаване на същия индекс като легитимна дума, когато преминава през хеш функцията? Да, това може да се случи, но ако изберете размера на вектора си (направете го колкото е възможно по-голям) и хеш функцията внимателно, шансовете за това да се случат са незначителни и дори ако това се случи, обикновено това не влияе на ученето (или точността) ) толкова много. Документацията за стандартните хеш-функции обикновено включва вероятности за сблъсък, така че не забравяйте да ги потърсите, когато правите свое собствено решение за трикове на хеширане.

Имайте предвид, че в някои случаи може дори да искате сблъсъци (например за групиране на подобни законни думи), в този случай може да искате да ги съберете преди хеширане.

Някои заключителни мисли

Трикът на хеширане е един от онези спретнати трикове в машинното обучение, които не получават почти толкова любов, колкото заслужава. Единственият реален недостатък е фактът, че обратното търсене (изход към въвеждане) не е възможно, но за много проблеми това не е изискване. Мислейки в по-общи термини, трикът на хеширане ви позволява да използвате вектори с променлив размер със стандартни алгоритми на обучение (регресия, случайни гори, невронни мрежи с пренасочване, SVMs, матрична факторизация и др.). Това трябва да е достатъчно, за да накара повечето практикуващи машинно обучение поне малко да се развълнуват.