Соревнование mlbootcamp от mail.ru. Кратко о рецепте второго места
- воскресенье, 26 марта 2017 г. в 03:14:54
python
https://habrahabr.ru/post/324732/
Добрый день, читатель! Данная статья расскажет о пути получения второго места на соревновании MLBootCamp III. Для тех, кто не в курсе — это соревнование по машинному обучению и анализу данных от Mail.Ru Group, проходило с 15 февраля по 15 марта.
В статье будет коротко про историю построения решения, немного советов про то, на чем набил шишек и благодарности.
Итак, поехали.
В качестве метрики использовался 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-го перцентиля, красивая гладкая кривая — график аппроксимирующего полинома.
Получив таким образом еще три признака, нормировал исходные фичи (кроме количества дней, которое провел игрок в игре) на каждую из новых, таким образом общее количество фич возросло вчетверо. Придумал и добавил еще два десятка фич, среди которых, например, такие:
Далее, ввиду разросшегося количества признаков, не стал генерировать квадратичные и отобрал лучшие фичи из имеющихся, обучил ансамбль и оказался на 60 месте, поднявшись с ~120го.
Логистическая регрессия sklearn'а была заменена на стохастическую реализацию таковой в vowpal wabbit (задействовал питоновскую обертку собственного написания, про неё в другой раз), попутно отказался от своей идеи использовать кодирование фич на интервалы и еще слегка улучшил результат логрега на кросс-валидации (тут было также немного самописных костылей для получения результата кросс-предикта). Т.к. vw уже был задействован, то почему бы не задействовать перцептрон из него (флаг --nn) — так к ансамблю добавился еще один классификатор.
Ну раз перцептрон из vw был задействован, то почему бы не задействовать и MLPClassifier.
После этого к ансамблю добавилось еще два классификатора на основе случайного леса. Один из них обучался на выборке с убранными отклонениями на каждом из дней по значению фич (все примеры, значения фич в которых ниже 1-го перцентиля и выше 99-го не участвовали в обучении классификатора), второй — просто на новых отобранных фичах.
Итого, к концу соревнования ансамбль насчитывал 7 классификаторов. Как для всего этого сделать нормальную схему кросс-валидации и не сильно мучиться? Схема построения следующая:
В последний день, когда решение уже было собрано и отправлено, мой лучший результат находился в паблике на 37 месте, а на кросс-валидации выдавал логлосс 0.37906093. О том, что занял второе место, я узнал из сообщения друга в скайпе. Подумал, что это шутка, однако зайдя на сайт, убедился что действительно правда.
Слово «полезные» сознательно помещено в кавычки, т.к. большинство из них не единожды встречаются в каждой истории про победу в соревнованиях по машинному обучению:
Огромное спасибо компании Mail.ru, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.
- Машинное обучение
- Python
Добрый день, читатель! Данная статья расскажет о пути получения второго места на соревновании MLBootCamp III. Для тех, кто не в курсе — это соревнование по машинному обучению и анализу данных от Mail.Ru Group, проходило с 15 февраля по 15 марта.
В статье будет коротко про историю построения решения, немного советов про то, на чем набил шишек и благодарности.
Итак, поехали.
Спойлер
Данное повествование написано живым русским языком, является достаточно малонаучным и прозаичным, хотя и содержит несколько неплохих, с точки зрения автора, советов.
Задача "Выход из он-лайн игры"
Необходимо было научиться предсказывать, остается ли участник в онлайн игре или уходит из нее. Данные для обучения/теста посчитаны на последних двух неделях, а уходом считается отсутствие его в игре в течение недели.
Всего используется 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% станет известен после окончания конкурса и именно он определит финальную расстановку участников.
Всего используется 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 и ошибаешься (см. график ниже)
График логлосса, первая попавшаяся картинка из google
Поэтому не следует трогать результаты предикта руками, и тем более округлять.
О решении задачи
Первый сабмит был сделан практически сразу после открытия соревнования — это случайный лес на топ-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 достаточно быстро находится руками (можно не делать это руками, а подобрать веса регрессией)
— вместо «сложить все и поделить на количество классификаторов» складываем результат каждого из классификаторов с собственным, подобранным, весом и делим на сумму весов. Коэффициент одного из классификаторов не нужно модифицировать — таким образом фиксируем масштаб, с остальными коэффициентами «играемся» до тех пор, пока уменьшается результат кросс-валидации. Улучшение на 0.0005-0.0007 достаточно быстро находится руками (можно не делать это руками, а подобрать веса регрессией)
Последний день
В последний день, когда решение уже было собрано и отправлено, мой лучший результат находился в паблике на 37 месте, а на кросс-валидации выдавал логлосс 0.37906093. О том, что занял второе место, я узнал из сообщения друга в скайпе. Подумал, что это шутка, однако зайдя на сайт, убедился что действительно правда.
«Полезные» советы
Слово «полезные» сознательно помещено в кавычки, т.к. большинство из них не единожды встречаются в каждой истории про победу в соревнованиях по машинному обучению:
- на старте не стоит целый день рисовать красивые графики, считать статистики и заниматься прочими премудростями, а лучше сделать первый сабмит. Потратьте на это час-другой и не переживайте пока о месте в таблице. Это позволит победить лень с самого старта, проверить, правильно ли вы поняли задачу, работает ли система сабмита на стороне организаторов соревнования, корректно ли сформирован файл с ответом и т.п.
- после первого сабмита стоит посмотреть на данные, статистики, графики и попытаться понять, о чем же все-таки задача. Например в этой задаче я почему-то сначала считал, что все люди, на основе которых сформированы примеры в выборках, начали играть именно от первого дня, а затем кто-то по дороге прекратил, и лишь после применения метода внимательного разглядывания понял, что это не так
- каждое изменение, каждый опыт и каждую идею стоит проверять отдельно, при этом делая копии всего чего можно. При возможности стоит, конечно, использовать систему контроля версий, но порой можно обойтись и без неё. Например, если вы работаете в ipython notebook — то перед проведением очередного эксперимента сделайте копию ноутбука. Место на жестком диске стоит гораздо дешевле потраченных нервов на поиск «именно того» правильного варианта, который давал желаемое решение
- заведите себе доску, блокнотик или программу в которые будете записывать приходящие в голову идеи. Я, например, пользуюсь trello, там у меня есть три группы карточек: «Новые идеи», «Работающие идеи» и «Неработающие идеи». Новые идеи записываю в первую группу, а затем после проведения опыта она перемещается либо во вторую, либо в третью
- кросс-валидируйтесь, и не забывайте делать файл с предсказанием для теста текущего опыта. Также хороший подход (если даже не лучше) — это записывать файлы с кросс-предиктом на обучающей выборке. Плюсы становятся очевидны при объединении моделей в ансамбль
- верьте в результат своей кросс-валидации
Благодарности
Огромное спасибо компании Mail.ru, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.