От пясъчника Как да стигнете до върха на Kaggle или Matrixnet у дома

Историята е разделена на следните части: 1. Условия на конкурса; 2. Създаване на нови характеристики; 3. Логистична регресия – насладата на адаптивния градиент; 4. Matrixnet - пресъздаване на пълния алгоритъм; 5. Ускоряване на машинното обучение в Python.

1. Условия на конкурса

Самите данни можете да изтеглите тук.

Отрицателната вероятност за грешка (Negative Likelihood Loss - NLL) беше декларирана като критерий за оценка:

КъдетоNе броят на записите,yе стойността на променливата за кликване,pе вероятността събитието да е кликване („1“).

Важно свойство на тази функция за грешка е, че акоpсе основава на сигмоидна функция, тогава частната производна (наричана по-долу градиент) ще бъде(p-y).

2. Създаване на нови характеристики

Първо, нека да разгледаме изходните данни, с какво можем да работим:

Какво ново създаваме:

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

• час - изберете час, изхвърлете деня;
• C1 - Предполагам, че часовата зона е скрита зад това, така че след 2-рия ден сливам часа с колоната;
• C15 и C16 - комбинираме, тъй като ширината и височината на банера лесно се отгатват зад тях, няма смисъл да оставяме допълнителни характеристики;
• Сайт* и приложение* - трансформират се в разположение*, тъй като е ясно, че банерът се показва или на сайта, или в приложението, а останалите стойности са просто криптирани NULL, което е допълнително. не носи информация;
• Ние премахваме всички стойности, които не са намерени в тестовите данни. Това помага за намаляване на пренатоварването.

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

3. Логистична регресия - прелестите на адаптивния градиент

Логистичната регресия е популярен алгоритъм за класификация. Има 2 основни причини за такава популярност: 1. Лесен за разбиране и създаване на алгоритъм;

2. Скорост и адаптивност на прогнозирането на големи данни поради стохастичен градиентен спад (SGD).

Използвайки данните на Avazu като пример, нека да видим как поради стохастичния градиент не винаги „стигаме“ точно до минимума:

3.1. адаптивен градиент

Ако обаче с течение на времето намалим скоростта на обучение на алгоритъма (скорост на обучение), тогава ще стигнем до по-точно решение, тъй като градиентът няма да реагира толкова много на нетипични данни. Авторите на Adaptive Gradient (AdaGrad) предлагат да се използва сумата от всички предишни градиенти, за да се намалят последователно нивата на учене:

Така получаваме полезните свойства на алгоритъма:

• По-плавно спускане до минимум (степента на учене намалява с течение на времето);
• Алфа за всяка характеристика се изчислява индивидуално (което е много важно за редки данни, където повечето от характеристиките са много редки);
• Изчисляването на алфа взема предвид колко се е променил параметърът (w) на характеристиката: колкото повече се е променил преди, толкова по-малко ще се промени в бъдеще.

Адаптивният градиент започва да се обучава по същия начин като нормалната логистична регресия, но след това достига до по-нисък минимум:

Всъщност, ако обичайното спускане на стохастичен градиент се повтаря много пъти върху едни и същи данни, тогава можеподход AdaGrad. Това обаче ще отнеме повече повторения. В моя модел използвах комбинация от тези техники: 5 итерации с обичайния алгоритъм и след това една с AdaGrad. Ето резултатите:

3.2. Трансформация на данни за логистична регресия

За да може алгоритъмът за логистична регресия да работи с данни (и те са във формат на текстови стойности), те трябва да бъдат преобразувани в скаларни стойности. Използвах еднократно кодиране: преобразуване на текстови характеристики в NxM матрица със стойности "0" и "1", където N е броят на записите, а M е броят на уникалните стойности за тази функция. Основните причини са, че се съхранява максимална информация, а хеширането на функции ви позволява бързо да работите с пространства с милиони функции в рамките на логистична регресия.

4. Matrixnet - сглобяване в домашни условия

Да вървим по ред, от какво се състои Mactrixnet:

1. Базов елемент - Дърво на класификация и регресия (CART);
2. Основен алгоритъм - Машина за усилване на градиента (GBM)
3. Актуализация на основния алгоритъм - Stochastic Gradient Boosting Machine (SGBM).

4.1. Класификация и регресионно дърво (CART)

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

Така дървото на решенията има следните параметри, които определят алгоритъма:

• Условия за разделяне на листове (x_1≥0,5)
• "Височина" на дървото (брой нива с условия, в горния пример те са 2)
• Правило за прогнозиранеp®(примерът по-горе използва очакване)

4.1.1. Как да дефинираме характеристиказа условието за разделяне

На всяко ниво трябва да дефинираме характеристика за условието на разделяне, което ще раздели равнината по такъв начин, че да правим по-точни прогнози.

По този начин преминаваме през всички характеристики и възможни разделяния и избираме тези точки, където ще имаме по-ниска стойност на NLL след разделянето (в примера по-горе това е, разбира се,x2). За да се определи разделянето, обикновено се използват други функции - придобиване на информация и примес на Gini, но в нашия случай ние избираме NLL, тъй като това е, което ни беше помолено да минимизираме в задачата (вижте описанието на задачата в раздел 1).

4.1.2. Регулиране в CART

В случая на CART обикновено е необходима регуляризация, за да не се правят твърде сигурни прогнози, когато не сме наистина сигурни. Yandex предлага да се коригира формулата за прогнозиране, както следва:

КъдетоNе броят на стойностите в листа, а ламбда е параметърът за регулиране (експертите на Matrixnet препоръчват 100, но трябва да тествате за всяка задача поотделно). По този начин, колкото по-малко стойности имаме в листа, толкова по-малко уверен ще бъде нашият алгоритъм относно прогнозираната стойност.

4.1.3. Забравящи дървета

В MatrixNet, вместо класическия подход, когато след разделяне сx1следващото ниво на дървото не може да раздели данните по тази характеристика, т.нар. забравящи дървета, които могат да разделят стойности за една и съща характеристика в рамките на няколко нива (като че ли „забравят“, че вече е направено разделяне върху него).

Използването на този тип дървета според мен е оправдано предимно в случаите, когато данните съдържат 1-2 характеристики, по-тесните разделяния за които дават по-добри резултати от разделянията за повеченеизползвани функции.

4.2. Машина за усилване на градиента

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

По същество всяко дърво помага да се оптимизира функцията на квадратичната грешка:

Основното предимство на GBM пред CART е по-малкият шанс за пренастройване, тъй като правим прогнози въз основа на листове с повече стойности. В MatrixNet в GBM „височината“ на дървото зависи от текущата итерация: започва от 1, увеличава се с още 1 на всеки 10 итерации, но никога не надвишава 6. Този подход ви позволява значително да овърклокнете алгоритъма, без да влошавате значително резултата в първите итерации. Тествах тази опция, но се спрях на опцията, когато преходът към следващото ниво се извършва след изчерпване на възможностите на предишното.

4.2.1. GBM за класификация

Когато работите с класификация, всяко следващо дърво трябва да подобрява предсказанието на предходното, но това трябва да стане по такъв начин, че дърветата да работят за една задача - класификация с помощта на сигмоидната функция. В този случай е удобно проблемът за оптимизация да се представи по същия начин, както при логистичната регресия, а именно:

Интересно решение на Yandex е, че логистичните регресионни прогнози се използват като първоначална прогнозаp0, а произведението от тегла и характеристики (wTx) се използва като една от характеристиките.

4.3. Стохастичен GBM

Стохастичният GBM се различава от обикновения GBM по това, че се отчита всяко дървоизвадка от данните (10-50%). Това помага да убием 2 заека едновременно - да ускорим алгоритъма (в противен случай ще трябва да изчислим резултата за всичките 40,4 милиона записа на тренировка), а също и да се отървем до голяма степен от проблема с претренирането. Краен резултат:

Както можете да видите, в крайна сметка най-голямата оптимизация се дава от работата с данни, а не от самите алгоритми. Въпреки че с конвенционалната логистична регресия би било трудно да се стигне над 30-то място, където всяка десет хилядна е от значение.

5. Опит за ускоряване на машинното обучение в Python

Това беше първият ми проект за самостоятелно внедряване на алгоритми за машинно обучение, тоест в кода, който прави прогнози, не се използват готови решения на трети страни, всички алгоритми и манипулации на данни се извършват на открито, което ми позволи да разбера по-добре същността на задачата и принципите на работа на тези инструменти. Използвах обаче най-добрите практики: логистичната регресия до голяма степен е кодът на Abnishek в Kaggle, Matrixnet заимства малка част от CART от кода на Stephen Marshall за Machine Learning: Algorithmic Perspective.

По отношение на изпълнението, започнах да експериментирам със задачата в R, но след това бързо я изоставих, тъй като е почти невъзможно да се работи с големи данни. Python беше избран поради простотата на синтаксиса и наличието на голям брой библиотеки за машинно обучение.

Основният проблем с CPython е, че е МНОГО бавен (макар и много по-бърз от R). Въпреки това има много опции за ускоряване, в резултат на което използвах следното:

• PyPy е JIT компилатор, който ви позволява да ускорите стандартния CPython x20 пъти, основният проблем е, че практически няма библиотеки за работа с изчисления (NumPyPy все още е в процес на разработка), всичко трябва да бъде написанобез тях. Чудесно за прилагане на логистична регресия със стохастичен градиентен низход, както в нашия случай;
• Numba - jit декораторите ви позволяват предварително да компилирате някои функции (принцип като в PyPy), но останалата част от кода може да се възползва напълно от библиотеките на CPython. Голям плюс е, че за предварително компилирани функции можете да премахнете GIL (Global Interpreter Lock) и да използвате няколко процесора. Какво използвах за ускоряване на Matrixnet. Проблемът с Numba е същият като с PyPy - няма поддръжка за никакви библиотеки, основната разлика е, че Numba има имплементация на някои функции на NumPy.

Не стигнах до Cython, защото се опитах да ускоря с минимално кръвопролитие, но мисля, че следващия път е по-лесно да превключите директно към GPGPU с помощта на Theano / Numba.

Пълният код на всички трансформации с данни и самите алгоритми за обучение е тук. Отказ от отговорност: кодът не е оптимизиран, той е предназначен само за изучаване на самите алгоритми.

Ако откриете неточности или грешки в статията или кода, пишете на ЛС.

Връзки към източници, използвани за статията и при работа по алгоритмите:

---