Соревнование mlbootcamp от mail.ru. Кратко о рецепте второго места
В статье будет коротко про историю построения решения, немного советов про то, на чем набил шишек и благодарности.
Итак, поехали.
Всего используется 12 признаков, вычисленных за 2 предыдущие недели:
— maxPlayerLevel — максимальный уровень игры, который прошел игрок
— numberOfAttemptedLevels — количество уровней, которые попытался пройти игрок
— attemptsOnTheHighestLevel — число попыток, сделанных на самом высоком уровне
— totalNumOfAttempts — общее число попыток
— averageNumOfTurnsPerCompletedLevel — среднее количество ходов, выполненных на успешно пройденных уровнях
— doReturnOnLowerLevels — делал ли игрок возвраты к игре на уже пройденных уровнях
— numberOfBoostersUsed — количество использованных бустеров
— fractionOfUsefullBoosters — количество бустеров, использованных во время успешных попыток (игрок прошел уровнь)
— totalScore — общее количество набранных очков
— totalBonusScore — общее количество набранных бонусных очков
— totalStarsCount — общее количество набранных звезд
— numberOfDaysActuallyPlayed — количество дней, когда пользователь играл в игру
Все предоставленные для задачи данные разбиты на две части: обучающую (x_train.csv и y_train.csv) и тестовую (x_test.csv). Каждая строка файлов x_train.csv и x_test.csv соответствует одному пользователю. Данные в строке разделены точкой с запятой. Первая строка содержит имена признаков. Файл y_train.csv содержит значения 1 или 0 в зависимости от того, остался пользователь в игре или вышел из нее соответственно.
Как обучающая (x_train.csv и y_train.csv), так и тестовая (x_test.csv) выборки содержат информацию о 25289 пользователях.
В качестве ответа для данной задачи принимается текстовый файл, каждая строка которого соответствует строке в файле x_test.csv и содержит значение от 0 до 1 (вероятность того, что пользователь останется в игре). В качестве критерия качества решения задачи используется логарифмическая функция потерь.
Количество посылок ограничено пятью в сутки
Тестовая выборка случайным образом разбита на две части в соотношении 40/60. Результат на первых 40% будет определять положение участников в рейтинговой таблице на всем протяжении конкурса. Результат на оставшихся 60% станет известен после окончания конкурса и именно он определит финальную расстановку участников.
В качестве метрики использовался logloss, поэтому стоило помнить о том что:
— Многие классификаторы уже умеют минимизировать logloss «из коробки»;
— Logloss «не прощает», когда округляешь ответы до 1.0 или 0.0, вместо, к примеру, 0.97 и 0.03 и ошибаешься (см. график ниже).
Поэтому не следует трогать результаты предикта руками, и тем более округлять.
О решении задачи
Первый сабмит был сделан практически сразу после открытия соревнования — это случайный лес на топ-10 лучших, по его же мнению, фичах. После этого был сделан шаг, на который была потрачена примерно неделя, но он не был результативен — были сгенерированы квадратичные фичи и запущен простейший жадный алгоритм отбора фич по результату на кросс-валидации.
Алгоритм такой: обучаем лес, берем из него важность фич, и, начиная с первых двух, добавляем по одной фиче в наш текущий набор. Если добавление фичи приводит к улучшению результата — оставляем фичу в наборе. Если нет — откидываем её и больше никогда к ней не возвращаемся.
По завершении работы этого нехитрого алгоритма используем еще одну эвристику — выкидываем по очереди по одной фиче и смотрим на результат при работе на всех остальных. Если результат улучшается — значит фичу в топку.
Пока поиск фич генерировал лесные массивы и разогревал квартиру, захотелось обучить логистическую регрессию и поиграться с xgboost’ом, т.к. ранее его не использовал (да-да).
Сначала попробовал логистическую регрессию на имеющихся признаках (не забыв их нормализовать, конечно), затем решил преобразовать все фичи следующим образом:
— бьем все значения фичи на N интервалов равных размеров 1/N по перцентилям
— кодируем значение фичи как ohe, т.е. если значение фичи в примере попадает в интервал — ставим 1, иначе 0, итого из одного значения получается вектор [0 0… 0 1 0… 0] длины N.
Идея была следующая — разный уровень игрока (кол-во дней которое он играл, кол-во звезд и т.д.) нелинейно влияют на целевую переменную, тогда можно попробовать эту нелинейность занести в линейную модель в этом преобразованном виде (хотя и в таком, урезанном, «групповом» варианте).
Такое преобразование дало на кросс-валидации около 0.3836 — неплохо для логистической регрессии (как оказалось потом, можно и лучше).
Затем приступил к xgboost’у и достаточно быстро получил неплохое решение на кросс-валидации, примерно такое же как и у случайного леса на тот момент (что-то около 0.3812).
После этого сложил результаты трех неплохих на кросс-валидации классификаторов в один, поделил на три, отправил, и… меня ждало разочарование, так как паблик лидерборд оказался набором примеров, на которых мой ансамбль работал из рук вон плохо. Кстати такая ситуация наблюдалась не только у меня, а у всех моих друзей и знакомых, которые решали задачу. Доходило до смешного — чем лучше классификатор вел себя на кросс-валидации, тем ниже он утаскивал меня в публичном лидерборде. Эта ситуация неслабо демотивировала, поэтому интерес к задаче был утерян примерно на неделю.
<Прошла неделя>
В один из дней я открыл лидерборд, и увидел как мой друг ушел по таблице вверх, и за один (или два) дня оказался уже в двадцатке. «Ничего себе» — подумал я, засучил рукава, и снова взялся за задачу.
Методом пристального разглядывания графиков обнаружилось, что были люди с одним днем участия в онлайн игре, имеющие 100+ уровень, очень много бонусов и очков. Это навело на мысль, что люди на самом деле играли уже давно, просто двухнедельное окно, в котором у нас считаются фичи, зацепило их всего одним днем. Поломав пару вечеров голову над тем как бы это использовать, на основе каждой из фич maxPlayerLevel, totalStarsCount и totalNumOfAttempts решил изготовить по одной новой фиче «спрогнозированное количество дней», которое играет игрок. Идея следующая — берем нижние значения (взял все что ниже 4-го перцентиля) в каждом из дней по выбранной фиче (например, maxPlayerLevel), получаем достаточно красивый график, который неплохо приближается полиномом (взял четвертую степень, хотя и третьей бы, пожалуй, хватило). Имея построенный полином, можем теперь находить его корни для значения фичи у игрока и стоить предсказания количества дней, которые играл игрок. Выглядит это так:
По оси х отложено количество дней, по оси y — значение выбранных фич. Изломанная кривая — это те самые значения фичи, лежащие ниже 4-го перцентиля, красивая гладкая кривая — график аппроксимирующего полинома.
from numpy.polynomial import Polynomial as P
class nlSolver():
def __init__(self):
self.p=None
def fit(self,f_x,f_y):
self.p = P.fit(f_x, f_y, 4)
return self
def get_y_by_x(self,f_x):
return self.p(f_x)
def get_x_by_y(self,f_y,initial_x):
res = max([r.real for r in (self.p - f_y).roots()])
return resПолучив таким образом еще три признака, нормировал исходные фичи (кроме количества дней, которое провел игрок в игре) на каждую из новых, таким образом общее количество фич возросло вчетверо. Придумал и добавил еще два десятка фич, среди которых, например, такие:
...
X['positiviness'] = X.totalStarsCount*X.totalBonusScore*X.usefulBoosters
X['winDesire'] = X.attemptsPerDay*X.numberOfBoostersUsed*X.attemptsOnTheHighestLevel
X['positivinessPerWinDesire'] = X.positiviness/(X.winDesire+1)
...
Далее, ввиду разросшегося количества признаков, не стал генерировать квадратичные и отобрал лучшие фичи из имеющихся, обучил ансамбль и оказался на 60 месте, поднявшись с ~120 го.
Логистическая регрессия sklearn’а была заменена на стохастическую реализацию таковой в vowpal wabbit (задействовал питоновскую обертку собственного написания, про неё в другой раз), попутно отказался от своей идеи использовать кодирование фич на интервалы и еще слегка улучшил результат логрега на кросс-валидации (тут было также немного самописных костылей для получения результата кросс-предикта). Т.к. vw уже был задействован, то почему бы не задействовать перцептрон из него (флаг --nn) — так к ансамблю добавился еще один классификатор.
Ну раз перцептрон из vw был задействован, то почему бы не задействовать и MLPClassifier.
После этого к ансамблю добавилось еще два классификатора на основе случайного леса. Один из них обучался на выборке с убранными отклонениями на каждом из дней по значению фич (все примеры, значения фич в которых ниже 1-го перцентиля и выше 99-го не участвовали в обучении классификатора), второй — просто на новых отобранных фичах.
Итого, к концу соревнования ансамбль насчитывал 7 классификаторов. Как для всего этого сделать нормальную схему кросс-валидации и не сильно мучиться? Схема построения следующая:
- Каждый из классификаторов кладем в отдельную папку в проекте.
- Каждый из классификаторов вместо кросс-валидации делает кросс-предикт на трейне, результат складывает в файл в своей папке, с определенным окончанием (чтобы эти файлы было проще искать).
- В каждой папке обучаем по одному классификатору на всем трейне, делаем предикт на тестовой выборке, который также кладем в файл в своей папке с определенным окончанием.
- В директории над папками классификаторов делаем общий скрипт ансамбля, который для кросс-валидации подгружает из всех нужных папок классификаторов все кросс-предикты, преобразует их по нужным нам правилам в результат ансамбля и подсчитывает нужную нам метрику (логлосс).
- Получив результаты валидации ансамбля остается подгрузить из каждой папки предикты, и преобразовать их по тем же правилам для получения прогноза ансамбля на тестовой выборке.
- Добавляем несколько завершающих штрихов.
— Вместо «сложить все и поделить на количество классификаторов» складываем результат каждого из классификаторов с собственным, подобранным, весом и делим на сумму весов. Коэффициент одного из классификаторов не нужно модифицировать — таким образом фиксируем масштаб, с остальными коэффициентами «играемся» до тех пор, пока уменьшается результат кросс-валидации. Улучшение на 0.0005–0.0007 достаточно быстро находится руками (можно не делать это руками, а подобрать веса регрессией).
Последний день
В последний день, когда решение уже было собрано и отправлено, мой лучший результат находился в паблике на 37 месте, а на кросс-валидации выдавал логлосс 0.37906093. О том, что занял второе место, я узнал из сообщения друга в скайпе. Подумал, что это шутка, однако зайдя на сайт, убедился что действительно правда.
«Полезные» советы
Слово «полезные» сознательно помещено в кавычки, т.к. большинство из них не единожды встречаются в каждой истории про победу в соревнованиях по машинному обучению:
- На старте не стоит целый день рисовать красивые графики, считать статистики и заниматься прочими премудростями, а лучше сделать первый сабмит. Потратьте на это час-другой и не переживайте пока о месте в таблице. Это позволит победить лень с самого старта, проверить, правильно ли вы поняли задачу, работает ли система сабмита на стороне организаторов соревнования, корректно ли сформирован файл с ответом и т.п.
- После первого сабмита стоит посмотреть на данные, статистики, графики и попытаться понять, о чем же все-таки задача. Например в этой задаче я почему-то сначала считал, что все люди, на основе которых сформированы примеры в выборках, начали играть именно от первого дня, а затем кто-то по дороге прекратил, и лишь после применения метода внимательного разглядывания понял, что это не так.
- Каждое изменение, каждый опыт и каждую идею стоит проверять отдельно, при этом делая копии всего чего можно. При возможности стоит, конечно, использовать систему контроля версий, но порой можно обойтись и без неё. Например, если вы работаете в ipython notebook — то перед проведением очередного эксперимента сделайте копию ноутбука. Место на жестком диске стоит гораздо дешевле потраченных нервов на поиск «именно того» правильного варианта, который давал желаемое решение.
- Заведите себе доску, блокнотик или программу в которые будете записывать приходящие в голову идеи. Я, например, пользуюсь trello, там у меня есть три группы карточек: «Новые идеи», «Работающие идеи» и «Неработающие идеи». Новые идеи записываю в первую группу, а затем после проведения опыта она перемещается либо во вторую, либо в третью.
- Кросс-валидируйтесь, и не забывайте делать файл с предсказанием для теста текущего опыта. Также хороший подход (если даже не лучше) — это записывать файлы с кросс-предиктом на обучающей выборке. Плюсы становятся очевидны при объединении моделей в ансамбль.
- Верьте в результат своей кросс-валидации
Благодарности
Огромное спасибо компании Mail.ru, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.
Комментарии (10)
ServPonomarev
25 марта 2017 в 07:56
+1↑
↓
По поводу алгоритма отбора квадратичных фич, который неделю грел комнату. Вполне можно ожидать, что некоторые фичи сами по себе не играют, но заиграют в связке с другими. Отбрасывание не улучшающих результат фич навечно рубит возможность найти подобные играющие пары и ансамбли фич. Этот процесс, в принципе, похож на градиентный спуск, только осуществляемый в пространстве фич (подключена/отключена). Надо возвращаться и снова пробовать отброшенные фичи после некоторого числа шагов спуска.
romanegunkov
25 марта 2017 в 08:40
–1↑
↓
Сами обучающие данные можно у себя поделить на обучающие и тестовые, тогда можно оценить работу метрик и отловить момент переобучения без выполнения сабмита на сервер с ограничением 5 в день. Вы это использовали?
devpony
25 марта 2017 в 11:21
+2↑
↓
кросс-валидируйтесь
-
romanegunkov
25 марта 2017 в 12:44
0↑
↓
Кросс-валидация даже лучше, если по ресурсам подходит.
QtRoS
25 марта 2017 в 11:22
+1↑
↓
Спасибо моей девушке за терпение и еще раз терпение)
Жизненно…
markhor
25 марта 2017 в 11:57
+3↑
↓
Вот я не понимаю, честно. Какой смысл упарываться ради 0.1–1%? В продакшне на котором миллионы сэмплов франкенштейн-ансамбль не применишь, в нем может и VW будет по швам трещать. Какая разница в логлоссе между линрегом на one hot encoding-е и супер навроченным ансамблем? Кому это нужно?-
ServPonomarev
25 марта 2017 в 12:08
+7↑
↓
реклама себя любимого, призовой фонд, строчка в резюме. 25 марта 2017 в 12:29
+7↑
↓
В продакшене все по другому, статья не про продакшен. Соревнование — оно для того и соревнование, чтобы упарываться.
25 марта 2017 в 13:28
+2↑
↓
кратко о рецепте второго места
О рецепте стабильного второго места.
Поздравляю с дублем!25 марта 2017 в 14:55
0↑
↓
А сколько получилась точность предсказания модели, что человек «выйдет из игры»? В каком-нибудь более понятном показателе, а то я не очень понимаю этот Log loss. Простите за болванство.
