Добрый день, читатель! Данная статья расскажет о пути получения второго места на соревновании 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, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.
В статье будет коротко про историю построения решения, немного советов про то, на чем набил шишек и благодарности.
Итак, поехали.
Спойлер
Данное повествование написано живым русским языком, является достаточно малонаучным и прозаичным, хотя и содержит несколько неплохих, с точки зрения автора, советов.
Задача "Выход из он-лайн игры"
Необходимо было научиться предсказывать, остается ли участник в онлайн игре или уходит из нее. Данные для обучения/теста посчитаны на последних двух неделях, а уходом считается отсутствие его в игре в течение недели.
Всего используется 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, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.
Поделиться с друзьями
Комментарии (10)
romanegunkov
25.03.2017 08:40-1Сами обучающие данные можно у себя поделить на обучающие и тестовые, тогда можно оценить работу метрик и отловить момент переобучения без выполнения сабмита на сервер с ограничением 5 в день. Вы это использовали?
markhor
25.03.2017 11:57+3Вот я не понимаю, честно. Какой смысл упарываться ради 0.1-1%? В продакшне на котором миллионы сэмплов франкенштейн-ансамбль не применишь, в нем может и VW будет по швам трещать. Какая разница в логлоссе между линрегом на one hot encoding-е и супер навроченным ансамблем? Кому это нужно?
Eugene713
25.03.2017 12:29+8В продакшене все по другому, статья не про продакшен. Соревнование — оно для того и соревнование, чтобы упарываться.
tyamgin
25.03.2017 13:28+2кратко о рецепте второго места
О рецепте стабильного второго места.
Поздравляю с дублем!
gaploid
25.03.2017 14:55А сколько получилась точность предсказания модели, что человек «выйдет из игры»? В каком-нибудь более понятном показателе, а то я не очень понимаю этот Log loss. Простите за болванство.
ServPonomarev
По поводу алгоритма отбора квадратичных фич, который неделю грел комнату. Вполне можно ожидать, что некоторые фичи сами по себе не играют, но заиграют в связке с другими. Отбрасывание не улучшающих результат фич навечно рубит возможность найти подобные играющие пары и ансамбли фич. Этот процесс, в принципе, похож на градиентный спуск, только осуществляемый в пространстве фич (подключена/отключена). Надо возвращаться и снова пробовать отброшенные фичи после некоторого числа шагов спуска.