Как да стигнем до върха на kaggle или matriksnet у дома, savepearlharbor

Аз разделят историята на следните секции:
1. Условия на конкуренцията;
2. Създаване на нови възможности;
3. логистична регресия - чар адаптивна градиент;
4. Matriksnet - пълна реконструкция на алгоритъма;
5. Ускоряване на машинно обучение в Python.

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

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

- отрицателен вероятността за грешка (NLL Negative Вероятност Загуба) е обявен като критерий за оценка

Когато N - е броят на регистрите, Y - е стойността на кликване, р - вероятността, че събитието е кликване ( "1").

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

2. Създаване на нови функции

За да започнете, да погледнем в суровите данни, с които можем да работим:

Това създаде ново:

Пример потребителското ID образуване

Също така прави една малка трансформация преобразуване / на данните, насочена основно към да се отървем от повтарящи информация:

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

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

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

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

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

На примера на данни Avazu изглежда, защото на стохастичен градиента, ние не винаги "отиде" точно до минимум:

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

По този начин, ние се полезните свойства на алгоритъма:

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

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

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

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

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

Пример една гореща кодиране

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

Да вървим, за това какво представлява Maktriksnet:

1. База елемент - класификация и регресия Tree (КАРТ);
2. Основният алгоритъм - Gradient Увеличаване на машина (GBM)
3. Актуализиране на основния алгоритъм - стохастична Gradient Увеличаване на машина (SGBM).

4.1. Класификация и регресия Tree (КАРТ)

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

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

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

4.1.1. Как да се определи отговора на условията за сплит

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

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

4.1.2. Узаконяване КОШНИЦАТА

В случай на КОШНИЦАТА обикновено изисква узаконяване, така че да не се правят твърде уверени прогнози за където ние наистина не сме сигурни. Yandex предлага да се коригира формулата предсказание, както следва:

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

4.1.3. Разсеян дървета (Забравил дървета)

В Matriksnete вместо класическия подход, когато, след разделянето на x1 следващото ниво на дървото не могат да споделят данни за тази характеристика, които се използват така наречените разсеян дървета, които са в рамките на няколко нива разделени ценности на една и съща характеристика (като "забравяйки", че това разделяне вече е направена).

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

4.2. Gradient Увеличаване на машина

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

В действителност, всяко дърво помага за оптимизиране на функцията на квадрат грешка:

Основното предимство на GBM сравнение с количка - е по-малко вероятно да се преквалифицират като ние даваме прогнози въз основа на листа с голям брой стойности CMV. В Matriksnete в GBM височина «" на дървото зависи от текущата итерация започва с 1 на всеки 10 повторения увеличава с още 1, но никога повече от 6. Този подход може значително да ускори алгоритъм, а не много по-лоши резултати в първата итерация. Тествах тази версия, но се спря на вариант, при прехода към следващото ниво се извършва след изчерпването на възможностите за предходната година.

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

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

Yandex интересно решение е, че първоначалната прогноза предсказване P0 използва логистична регресия, и характеристиките на продукта и тегла (WTX) - като една от характеристиките.

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

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

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

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

Това беше първият ми реализация на проекта за машинно обучение алгоритми сами по себе си, че е в код, който прави прогнози, не използвайте готови решения на трети страни, всички алгоритми и манипулациите на данни да се появят на открито, което ми позволи да се разбере по-добре на целите и принципите на работа на тези инструменти. Въпреки това, аз се радваше на работното време: логистична регресия до голяма степен - Abnisheka код Kaggle, Matriksnet заема малка част от КОШНИЦАТА Стивън Маршал код, за да се научим на книга машина на: Алгоритмичната перспектива.

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

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

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

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

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

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

JHF / FTP / trebst.pdf

Стохастична Gradient Увеличаване - statweb.stanford.edu/