Як потрапити в топ на Kaggle, або Матрікснет в домашніх умовах

Розповідь поділяю такі розділи: 1. Умови конкурсу; 2. створення нових характеристик; 3. Логістична регресія – принади адаптивного градієнта; 4. Матрікснет – відтворення повного алгоритму; 5. Прискорення машинного навчання у Python.

1. Умови конкурсу

Самі дані можна завантажити тут.

Як критерій оцінки було заявлено негативну ймовірність помилки (Negative Likelihood Loss – NLL):

ДеN- це кількість записів,y- це значення змінної click,p- ймовірність того, що подією був клік («1»).

Важливою властивістю цієї функції помилки є те, що якщоpзаснована на сигмоїд функції, то приватною похідною (далі, градієнтом) буде(p-y).

2. Створення нових характеристик

Для початку подивимося на вихідні дані, з чим ми можемо працювати:

Що створюємо нового:

Також робимо невеликі перетворення/трансформації даних, спрямовані, перш за все, на порятунок від інформації, що повторюється:

• hour – виділяємо годину, викидаємо день;
• C1 - припускаю, що за цим ховався часовий пояс, тому після 2 числа зливаю з колонкою годину;
• С15 і C16 – об'єднуємо, тому що за ними легко вгадується ширина та висота банера, немає сенсу залишати зайві характеристики;
• Site* і app* — трансформуємо в placement*, оскільки зрозуміло, що банер з'являється або на сайті, або в додатку, а інші значення – це просто зашифрований NULL, який дод. інформації не несе;
• Забираємо всі значення, які не зустрічалися у тестових даних. Це допомагає зменшити перенавчання.

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

3. Логістична регресія (Logistic Regression) – принади адаптивного градієнта

Логістична регресія – найпопулярніший алгоритм для класифікації. Є дві основні причини такої популярності: 1. Простота для розуміння та створення алгоритму;

2. Швидкість і адаптивність передбачення великих даних рахунок стохастичного градієнтного спуску (stochastoc gradient descent, SGD).

На прикладі даних Avazu подивимося, як через стохастичний градієнт ми не завжди «йдемо» точно до мінімуму:

3.1. Адаптивний градієнт

Однак якщо з часом скорочувати швидкість навчання алгоритму (learning rate), то ми будемо приходити все до більш точного рішення, оскільки градієнт не так сильно реагуватиме на нетипові дані. Автори адаптивного градієнта (Adaptive Gradient, AdaGrad) пропонують використовувати суму всіх попередніх градієнтів, щоб зменшувати послідовність швидкості навчання:

Таким чином, ми отримуємо корисні властивості алгоритму:

• Гладший спуск до мінімуму (швидкість навчання зменшується з часом);
• Альфа для кожної характеристики розраховується індивідуально (що дуже важливо для sparse даних, де більшість характеристик зустрічаються дуже рідко);
• У розрахунку альфи враховується, наскільки сильно змінювався параметр (w) характеристики: що сильніше змінювався раніше, то менше змінюватиметься у майбутньому.

Адаптивний градієнт починає навчатися так само, як звичайна логістична регресія, але потім приходить до нижчого мінімуму:

Якщо звичайний стохастичний градієнтний спуск повторювати багато разів на одних і тих же даних, то він моженаблизитися до AdaGrad. Однак це займе більше ітерацій. У своїй моделі я використав комбінацію цих технік: 5 ітерацій із звичайним алгоритмом, а потім один із AdaGrad. Ось результати:

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

Щоб алгоритм логістичної регресії міг працювати з даними (а вони представлені у форматі текстових значень), їх необхідно перетворити на скалярні значення. Я використовував one-hot encoding: перетворення текстових характеристик в матрицю NxM зі значеннями «0» і «1», де N – це кількість записів, а M – кількість унікальних значень у цієї характеристики. Основні причини – зберігається максимум інформації, а feature hashing дозволяє швидко працювати з просторами з мільйонами характеристик у рамках логістичної регресії.

4. Матрікснет - складання в домашніх умовах

Підемо по порядку, з чого складається Мактрікснет:

1. Базовий елемент – Classification and Regression Tree (CART);
2. Основний алгоритм – Gradient Boosting Machine (GBM)
3. Апдейт основного алгоритму – Stochastic Gradient Boosting Machine (SGBM).

4.1. Classification and Regression Tree (CART)

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

Таким чином, дерево рішень має такі параметри, що визначають алгоритм:

• Умови спліту на листи (x_1≥0.5)
• «Висота» дерева (у рівнів з умовами, у прикладі вище їх 2)
• Правило прогнозуванняp®(у прикладі вище використовується математичне очікування)

4.1.1. Як визначити характеристикудля умови спліту

На кожному рівні нам необхідно визначити характеристику для умови спліту, який розділить площину таким чином, що ми робитимемо більш точні прогнози.

Таким чином проходимо за всіма характеристиками і можливими сплітами і вибираємо ті точки, де у нас буде нижче значення NLL після спліту (у прикладі вище це, звичайно,x2). Для визначення спліту зазвичай використовуються інші функції – information gain та Gini impurity, однак у нашому випадку ми вибираємо NLL, оскільки саме це просили нас мінімізувати у завданні (див. опис завдання у розділі №1).

4.1.2. Регуляризація в CART

У випадку з CART зазвичай необхідна регуляризація, щоб не робити надто впевнені передбачення там, де ми насправді не впевнені. Яндекс пропонує скоригувати формулу передбачення таким чином:

ДеN– кількість значень у листі, а лямбда – регуляризационный параметр (фахівці Мактрикснета рекомендують 100, але потрібно тестувати під кожну задачу окремо). Таким чином, чим менше у нас значень у аркуші, тим менше наш алгоритм буде впевнений у значенні, що передбачається.

4.1.3. Забудькі дерева (Oblivious Trees)

У Матрікснеті замість класичного підходу, коли після сплиту поx1наступний рівень дерева не може ділити дані за цією характеристикою, використовуються т.зв. забудькуваті дерева, які можуть у межах кількох рівнів сплітити значення за однією і тією ж характеристикою (начебто «забуваючи», що по ній спліт уже був зроблений).

Використання цього типу дерев, на мій погляд, обґрунтовано насамперед у тих випадках, коли в даних є 1-2 характеристики, більш вузькі спліти за якими дають кращі результати, ніж спліти по щене використаним характеристикам.

4.2. Gradient Boosting Machine

Gradient Boosting Machine (GBM) – це використання лісу коротких дерев, де кожне наступне не намагається вгадати цільове значення, а намагається покращити прогноз попередніх дерев. Розглянемо простий приклад з регресією та деревами з висотою 1 (можемо робити лише 1 спліт у межах кожного дерева).

По суті, кожне дерево допомагає оптимізувати функцію квадратичної помилки:

Основна перевага GBM в порівнянні з CART - це менша ймовірність перенавчання, так як ми даємо прогнози на підставі аркушів з більшою кількістю значень. У Матрікснеті в GBM "висота" дерева залежить від поточної ітерації: починається з 1, кожні 10 ітерацій збільшується ще на 1, але ніколи не перевищує 6. Цей підхід дозволяє суттєво розігнати алгоритм, не сильно погіршуючи результат на перших ітераціях. Я тестував цей варіант, але зупинився на варіанті коли перехід на наступний рівень здійснюється після вичерпання можливостей на попередньому.

4.2.1. GBM для класифікації

Під час роботи з класифікацією кожне наступне дерево повинне покращувати прогноз попереднього, проте робити це потрібно таким чином, щоб дерева працювали на одне завдання – класифікацію за допомогою сигмоїд функції. У цьому випадку зручно уявити завдання оптимізації такої ж, як у логістичній регресії, а саме:

Цікавим рішенням Яндекса є те, що як початковий прогнозp0використовуються передбачення логістичної регресії, а добутки ваг і характеристик (wTx) — як одна з характеристик.

4.3. Stochastic GBM

Stochastic GBM відрізняється від звичайного GBM тим, що кожне дерево вважається навибірці даних (10-50%). Це допомагає одночасно вбити 2-х зайців – прискорити роботу алгоритму (інакше нам довелося б прораховувати результат для всіх 40,4 млн. тренувальних записів), а також значною мірою позбутися проблеми перетренованості. Фінальний результат:

Як видно, все ж таки найбільшу оптимізацію дає робота з даними, а не самі по собі алгоритми. Хоча зі звичайною логістичною регресією було б складно піднятися вище 30-го місця, де йде на кожну десятитисячну.

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

Це був мій перший проект реалізації алгоритмів машинного навчання власними силами, тобто в коді, яким робив передбачення, не використовуються готові сторонні рішення, всі алгоритми та маніпуляції з даними відбуваються відкрито, що дозволило мені краще зрозуміти суть завдання та принципи роботи цих інструментів. Однак я користувався напрацюваннями: логістична регресія в значній мірі – код Абнішека на Kaggle, Матрікснет запозичує невелику частину CART із коду Стівена Маршала до книги Machine Learning: Algorithmic Perspective.

З погляду реалізації, я починав експериментувати із завданням у R, але потім швидко відмовився від нього, оскільки практично неможливо працювати з великими даними. Python був вибраний через простоту синтаксису і наявності великої кількості бібліотек для машинного навчання.

Основна проблема CPython - він дуже повільний (хоча і набагато швидше R). Однак є багато опцій для його прискорення, в результаті використав такі:

• PyPy – JIT-компілятор, який дозволяє прискорити стандартний CPython x20 разів, основна проблема – немає ніяких бібліотек для роботи з обчисленнями (NumPyPy все ще в розробці), все потрібно писатибез них. Прекрасно підходило для реалізації логістичної регресії зі стохастичним спуском градієнта, як у нашому випадку;
• Numba – декоратори jit дозволяють пре-компілювати деякі функції (принцип, як у PyPy), проте решта коду може використовувати всі переваги бібліотек CPython. Великий плюс – для прекомпільованих функцій можна знімати GIL (Global Interpreter Lock) та використовувати декілька CPU. Що я й використав для прискорення Матрікснета. Проблема у Numba така сама, як і у PyPy, - немає підтримки ніяких бібліотек, головна відмінність - у Numba є реалізація деяких функцій NumPy.

До Cython не дійшов, тому що намагався прискоритися мінімальною кров'ю, але, думаю, наступного разу простіше переходити відразу на GPGPU за допомогою Theano/Numba.

Повний код всіх перетворень із даними та самими алгоритмами навчання лежить тут. Disclaimer: код не оптимізований, призначений лише для вивчення самих алгоритмів.

Якщо ви знайшли будь-які неточності чи помилки у статті чи коді, пишіть у особу.

Посилання на джерела, що використовуються для статті та під час роботи над алгоритмами:

---