Mashinalarni o'qitishdagi eng yaxshi xakerlardan biri bilan tanishtirish: Hashing Trick

2018 yilni turli xil ommaviy axborot vositalari kutib olishdi, chunki spam o'chib keta boshlaydi, chunki mashinalarni o'rganish algoritmlari haqiqiy pochta nima ekanligini va nima yo'qligini aniqlashda deyarli mukammal bo'ladi. Men hech qachon bunday bo'lmasligiga amin emasman (mashinani o'rganishdagi yutuqlar ikkala tomonni ham kamaytiradi), lekin ML-ga asoslangan oddiy spam tasniflagichlari qanday qurilgani va muhim muammoni qanday hal qilish, filtrni chetlab o'tish, mashinani o'rganishda eng yaxshi qoziqlardan birini qo'llash: xesh-nayrang. Bu spamni aniqlashdan tashqarida ham foydalidir.

Oddiy spam-tasniflagichni yaratish

Hujjatlarni tasniflash vazifalari, shu jumladan spamni tasniflash uchun, odatda "so'zlar to'plami" (BOW) vakili deb nomlanadigan narsani yaratishdan boshlanadi. Ma'lum bir spam va spam bo'lmagan elektron pochta xabarlari to'plamini hisobga olgan holda, har bir noyob so'z lug'atga qo'shiladi va odatda 0 dan boshlanadigan noyob indeks belgilanadi. Aytaylik, qisqartirish uchun bizda ikkita qisqa matnli misollar to'plami mavjud, bu spam va boshqa qonuniy:

Men haftasiga o'n ming dollarni Internet orqali ko'rib chiqaman! (Spam)
kelgusi haftaning boshida uchrashuvga tayyormisiz? (spam emas)

Agar biz ma'lumotlar to'plamini skanerlash va so'z boyligimizni shakllantirishni boshlasak, quyidagilar bilan yakunlashimiz mumkin:

i: 0
qilmoq: 1
o‘n: 2
ming: 3
dollar: 4
boshiga: 5
hafta: 6
shunchaki: 7
bemaqsad: 8
: 9
veb: 10
quyidagilar: 11
siz: 12
bepul: 13
uchun: 14
a: 15
uchrashuv: 16
erta: 17
keyingi: 18

Hammasi bo'lib 19 ta noyob so'z mavjud va ularning har biriga alohida indeks beriladi (har ikkala misolda ham hafta haftasi so'zi ko'rinadi). Keyingi qadam, bizning mashinani o'rganish modelimiz uchun xususiyatli vektorlarni yaratish. Biz har bir misol uchun nolinchi ustun vektorini yaratamiz, shunda bir xil elementlar bilan so'z birikmalarimizda (19):

Men haftasiga o'n ming dollarni Internet orqali ko'rib chiqaman! (Spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]
kelgusi haftaning boshida uchrashuvga tayyormisiz? (spam emas)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

Keyinchalik, har bir misolda har bir so'z uchun indeksni olish va shu indeksdagi qiymatni bittaga ko'paytirish uchun so'z birikmalarini qidiramiz.

Men haftasiga o'n ming dollarni Internet orqali ko'rib chiqaman! (Spam)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
kelgusi haftaning boshida uchrashuvga tayyormisiz? (spam emas)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Olingan xususiyat vektorlari so'zlar to'plami vakili. BOW vakolatxonalari odatda tinish belgilariga va so'zlarning tartibiga oid ma'lumotlarni chiqarib tashlashadi, ammo ko'plab muammolar uchun bu muammo emas. Keyinchalik murakkab BOW vakilliklari so'zlarni hisoblash o'rniga TF-IDF og'irliklari va / yoki n-grammlaridan foydalanadi, ammo asosiy fikr bir xil.

BOW xususiyat vektorlarimizga ega bo'lgach, biz spam filtrini yaratish uchun ikkilik tasniflagichni tayyorlashimiz mumkin. O'rganish algoritmlariga tegishli ko'plab tanlovlar mavjud, ammo eng keng tarqalgan shubhalar: Naip Bayes, tasodifiy o'rmonlar, logistik regressiya va tobora ko'proq nerv tarmoqlari. O'qitilgan modelni hisobga olgan holda, biz BOW vektori sifatida yangi elektron pochtada qidirish va misol spam bo'ladimi yoki yo'qligini aniqlash uchun so'z birikmalaridan foydalanishimiz mumkin. Shuni esda tutingki, real vaqtda taqqoslash uchun biz tezkor xotiradagi lug'atni iloji boricha tezroq saqlashimiz kerak.

Muammo: filtrni aylanib o'tish

Spamerlar ayyor. Spam filtrlanmaganligiga ishonch hosil qilishning mashhur usullaridan biri bu tasniflagichni o'rganish uchun ishlatiladigan so'z birikmalarida bo'lmagan so'zlarni aralashtirishdir. Masalan, quyidagi ozgina shartli jumlalarni ko'rib chiqing:

ii mayke, siz keyingi haftaning boshida $$$ sörf1ing teh veb uchrashuvida bepul qatnashasizmi

Shubhasiz, bu hech kim qonuniy elektron pochtani qabul qiladigan narsa emas. Ammo agar ushbu misol uchun BOW vektorini yaratish uchun bizning so'z boyligimizdan foydalansak nima bo'ladi? Birinchi sakkizta so'z bizning lug'atimizda umuman yo'q va uni o'z ichiga olmaydi. Qolganlari quyidagi vektorga olib keladi:

ii mayke, siz keyingi haftaning boshida $$$ sörf1ing teh veb uchrashuvida bepul qatnashasizmi
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Ushbu vektor qonuniy misol uchun bir xil, siz kelgusi haftaning boshida uchrashuv uchun bo'shmisiz? . Bizning misollarimizda o'qitilgan har qanday tasniflovchi, ehtimol bu spam qonuniy deb o'ylashi mumkin. Bu juda muhim muammo va uni o'ylagandek hal qilish oson emas. Biz yangi so'zlarni lug'atimiz tarkibiga qo'sha olamiz, ammo bu xususiyat vektorlarning hajmi, shuningdek lug'atning o'zi ham o'zgarishini anglatadi. Mashinani o'qitish modellari odatda qat'iy o'lchamdagi o'quv misollarini o'rganishadi, shuning uchun biz o'z modelimizni noldan qayta tiklashimiz kerak. Bu vaqt talab etadi va biz buni qilayotib, eski klassifikator spamni qabul qilishda davom etadi. Bizga a) lug'atdan tashqari so'zlar bilan shug'ullanish mumkin bo'lgan echim kerak; b) biz har safar yangi so'z yoki noto'g'ri yozishda duch kelganimizda o'zimizning modellarimizni noldan qayta tayyorlashni talab qilmaydi va v) iloji boricha aniq. Agar biz tezkor xotirada juda katta so'z birikmalarini saqlamasdan qochib qutulsak.

Xesh hiyla bilan tanishtirish

Hash funktsiyalari kompyuter fanida juda muhimdir. Turli xil xesh funktsiyalari juda ko'p, ammo ularning barchasi bir xil narsani amalga oshiradilar: o'zboshimchalik bilan o'lchamdagi ma'lumotlarni belgilangan o'lchamdagi ma'lumotlar bilan xaritalash. Odatda, ular bir qatorni (xash deb nomlanuvchi) tupurishadi:

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

Xeshni hisoblash mantig'i hash funktsiyasining o'ziga bog'liq, ammo barcha hash funktsiyalari bir xil umumiy xususiyatlarga ega:

  • Agar biz bir xil kirishni xesh funktsiyasiga bersak, u har doim bir xil natijani beradi.
  • Xesh funktsiyasini tanlash mumkin bo'lgan chiqish oralig'ini aniqlaydi, ya'ni diapazoni har doim sobit bo'ladi (masalan, 0 dan 1024 gacha raqamlar).
  • Hash funktsiyalari bir tomonlama: hash berilgan bo'lsa, kirish nima bo'lganini aniqlash uchun teskari qidiruvni amalga oshira olmaymiz.
  • Hash funktsiyalari turli xil kirishlar (to'qnashuvlar) uchun bir xil qiymatga ega bo'lishi mumkin.

Hash funktsiyalari deyarli har qanday informatika sohasida juda foydali, ammo bizning spam-tasnifimizning so'zdan tashqari muammosini qanday hal qilish uchun ulardan foydalanish mumkin? Javob darhol aniq emas, lekin birinchi qadam - so'z boyligimizdan butunlay qutilish. Buning o'rniga, bizning BOW vakilliklarimizni qurishda biz har bir mashq misolimiz uchun juda ko'p sonli elementlarni (aytaylik, 2²⁸) nol ustunli vektorni yaratishni boshlaymiz:

Men haftasiga o'n ming dollarni Internet orqali ko'rib chiqaman! (Spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 element)
kelgusi haftaning boshida uchrashuvga tayyormisiz? (spam emas)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 element)

Keyinchalik, [0, 2²⁸] diapazondagi satrlarni va chiqadigan qiymatlarni iste'mol qiladigan f funksiyasini tanlaymiz. Boshqacha qilib aytganda, biz xesh funktsiyamiz hech qachon bizning xususiyat vektorlarimizning o'lchamlari doirasidan tashqaridagi indeksga murojaat qilmasligiga aminmiz.

Ushbu ishga tushirishdan so'ng, har bir mashg'ulot misoli uchun, biz hash funktsiyasi orqali har bir so'zni birma-bir beramiz va indeksdagi qiymatni bittaga ko'paytiramiz. Nuqtalar kabi siyrak vektorlar bilan tugashimiz mumkin:

Men haftasiga o'n ming dollarni Internet orqali ko'rib chiqaman! (Spam)
-> [0 ... 0 1 1 1 0 1 1 0 ... 0 1 1 1 1 0 1 1 0] (2 ^ 28 elementlar)
kelgusi haftaning boshida uchrashuvga tayyormisiz? (spam emas)
-> [0 1 0 1 0 ... 0 1 0 ... 0 1 0 ... 0 1 1 0 1 1 0 1] (2 ^ 28 element)

Ushbu jarayon xesh-nayrang deb nomlanadi.

Endi bizning BOW vakolatimiz bor va avvalgidek ma'lumotlar bo'yicha klassifikatorni tayyorlashimiz mumkin. Oddiy, yo'qmi? Biz alohida so'z birikmalaridan foydalanishni kechiktirdik, ya'ni RAMda katta miqdordagi so'zlarni saqlashimiz shart emas. Ammo bu shunchaki yoqimli yon ta'sir - biz hal qilmoqchi bo'lgan asosiy masala - bu so'zdan tashqari so'zlardan foydalangan holda filtrni aylanib o'tish. Xesh-hiyla qanday yordam beradi?

Aytaylik, bizda 2²⁸ BOW xususiyatli vektorlar zichligi bo'yicha o'qitiladigan spam-klassifikator bor. Yangi xatni olgan holda, biz avvalgidek ishlaymiz, 2²⁸ vektorni boshlaymiz va har bir so'zni xesh funktsiyamizdan o'tkazamiz. Avvalgidan farqli o'laroq, har bir so'z ba'zi xususiyatlarni oshirish bilan yakunlanadi. Bizning BOW vektorimizni hisobga olgan holda, har bir so'z, hatto yangi so'zlar ham bashorat qilish vaqtida hisobga olinadi. Yangi so'zlar hali ham bizning tasniflagichimizning aniqligini yomonlashtiradi, ammo endi yangi so'zlarni yaratish orqali bizning spam filtrimizni butunlay chetlab o'tishning iloji yo'q. BOW vektorlarining barchasi bir xil darajada bo'lganligi sababli, biz modemni yangi spam / spam bo'lmagan namunalar bilan asta-sekin butun narsalarni noldan qayta o'qimasdan moslashtira olamiz. Bu onlayn o'rganish shakli: foydalanuvchi elektron pochtani spam deb belgilasa, model butun jarayonni qayta boshlamasdan, asta-sekin o'rganishga qodir. Spamni filtrlash kabi amaliy dastur uchun bu xususiyatlarni o'chirib tashlashning aniq afzalligi: yangi spam / spam bo'lmagan namunalar paydo bo'lishi bilanoq o'rganishni o'rganish orqali hujumlarga tezkorlik bilan javob qaytarishimiz mumkin.

Ammo to'qnashuvlar haqida nima deb o'ylaysiz? Nahotki ba'zi bir qasddan xato xato qilish hash funktsiyasidan o'tib ketsa, qandaydir qonuniy so'z bilan bir xil ko'rsatkichni ko'paytirishi mumkin emasmi? Ha, bunday bo'lishi mumkin, lekin agar siz vektor o'lchamini tanlasangiz (iloji boricha kattaroq qilsangiz) va hash funktsiyasini diqqat bilan tanlasangiz, bu sodir bo'lish ehtimoli ahamiyatsiz, va agar shunday bo'lsa ham, bu odatda o'rganishga ta'sir qilmaydi (yoki aniqlik) ) bu juda ko'p. Odatda standart hash funktsiyalari uchun hujjatlar odatda to'qnashuv ehtimolligini o'z ichiga oladi, shuning uchun o'zingizning hashing hiyla-nayrangingiz echimini yaratishda ularni ko'rib chiqing.

E'tibor bering, ba'zi holatlarda siz to'qnashuvlarni (masalan, o'xshash qonuniy so'zlarni guruhlash uchun) xohlashingiz mumkin, bunda siz xeshni yutishdan oldin ularni chelakka tashlashingiz mumkin.

Ba'zi yakuniy fikrlar

Xesh-hiyla - bu mashina o'rganishdagi eng yaxshi nayranglardan biri bo'lib, u deyarli kerakli darajada muhabbatga ega emas. Yagona salbiy tomoni shundaki, teskari qidirish (kirish uchun chiqish) mumkin emas, ammo ko'p muammolar uchun bu shart emas. Umuman olganda, hashing hiyla-nayrangi sizga standart o'rganish algoritmlari (regressiya, tasodifiy o'rmonlar, uzatiladigan neyron tarmoqlari, SVMlar, matritsali faktorizatsiya va boshqalar) bilan o'zgaruvchan o'lchovli xususiyat vektorlarini ishlatishga imkon beradi. Bu ko'p mashina o'rganuvchilarni kamida bir oz hayajonlantirishi uchun etarli bo'lishi kerak.