Добрый день, читатель! Данная статья расскажет о пути получения второго места на соревновании 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% станет известен после окончания конкурса и именно он определит финальную расстановку участников.

В качестве метрики использовался 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), получаем достаточно красивый график, который неплохо приближается полиномом (взял четвертую степень, хотя и третьей бы, пожалуй, хватило). Имея построенный полином, можем теперь находить его корни для значения фичи у игрока и стоить предсказания количества дней, которые играл игрок. Выглядит это так:

image

По оси х отложено количество дней, по оси 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. О том, что занял второе место, я узнал из сообщения друга в скайпе. Подумал, что это шутка, однако зайдя на сайт, убедился что действительно правда.

image

«Полезные» советы


Слово «полезные» сознательно помещено в кавычки, т.к. большинство из них не единожды встречаются в каждой истории про победу в соревнованиях по машинному обучению:

  • На старте не стоит целый день рисовать красивые графики, считать статистики и заниматься прочими премудростями, а лучше сделать первый сабмит. Потратьте на это час-другой и не переживайте пока о месте в таблице. Это позволит победить лень с самого старта, проверить, правильно ли вы поняли задачу, работает ли система сабмита на стороне организаторов соревнования, корректно ли сформирован файл с ответом и т.п.
  • После первого сабмита стоит посмотреть на данные, статистики, графики и попытаться понять, о чем же все-таки задача. Например в этой задаче я почему-то сначала считал, что все люди, на основе которых сформированы примеры в выборках, начали играть именно от первого дня, а затем кто-то по дороге прекратил, и лишь после применения метода внимательного разглядывания понял, что это не так.
  • Каждое изменение, каждый опыт и каждую идею стоит проверять отдельно, при этом делая копии всего чего можно. При возможности стоит, конечно, использовать систему контроля версий, но порой можно обойтись и без неё. Например, если вы работаете в ipython notebook — то перед проведением очередного эксперимента сделайте копию ноутбука. Место на жестком диске стоит гораздо дешевле потраченных нервов на поиск «именно того» правильного варианта, который давал желаемое решение.
  • Заведите себе доску, блокнотик или программу в которые будете записывать приходящие в голову идеи. Я, например, пользуюсь trello, там у меня есть три группы карточек: «Новые идеи», «Работающие идеи» и «Неработающие идеи». Новые идеи записываю в первую группу, а затем после проведения опыта она перемещается либо во вторую, либо в третью.
  • Кросс-валидируйтесь, и не забывайте делать файл с предсказанием для теста текущего опыта. Также хороший подход (если даже не лучше) — это записывать файлы с кросс-предиктом на обучающей выборке. Плюсы становятся очевидны при объединении моделей в ансамбль.

  • Верьте в результат своей кросс-валидации
    image

Благодарности


Огромное спасибо компании Mail.ru, а также Илье Стыценко и его команде за замечательный конкурс и подарки. Огромную благодарность выражаю моим друзьям и соперникам по конкурсу (и не только) за поддержку/возможность поговорить/посоветоваться и поделиться мнением, думаю это было полезно для всех нас. Спасибо моей девушке за терпение и еще раз терпение.
Поделиться с друзьями
-->

Комментарии (10)


  1. ServPonomarev
    25.03.2017 07:56
    +1

    По поводу алгоритма отбора квадратичных фич, который неделю грел комнату. Вполне можно ожидать, что некоторые фичи сами по себе не играют, но заиграют в связке с другими. Отбрасывание не улучшающих результат фич навечно рубит возможность найти подобные играющие пары и ансамбли фич. Этот процесс, в принципе, похож на градиентный спуск, только осуществляемый в пространстве фич (подключена/отключена). Надо возвращаться и снова пробовать отброшенные фичи после некоторого числа шагов спуска.


  1. romanegunkov
    25.03.2017 08:40
    -1

    Сами обучающие данные можно у себя поделить на обучающие и тестовые, тогда можно оценить работу метрик и отловить момент переобучения без выполнения сабмита на сервер с ограничением 5 в день. Вы это использовали?


    1. devpony
      25.03.2017 11:21
      +2

      кросс-валидируйтесь


      1. romanegunkov
        25.03.2017 12:44

        Кросс-валидация даже лучше, если по ресурсам подходит.


  1. QtRoS
    25.03.2017 11:22
    +2

    Спасибо моей девушке за терпение и еще раз терпение)
    Жизненно…


  1. markhor
    25.03.2017 11:57
    +3

    Вот я не понимаю, честно. Какой смысл упарываться ради 0.1-1%? В продакшне на котором миллионы сэмплов франкенштейн-ансамбль не применишь, в нем может и VW будет по швам трещать. Какая разница в логлоссе между линрегом на one hot encoding-е и супер навроченным ансамблем? Кому это нужно?


    1. ServPonomarev
      25.03.2017 12:08
      +8

      реклама себя любимого, призовой фонд, строчка в резюме.


    1. Eugene713
      25.03.2017 12:29
      +8

      В продакшене все по другому, статья не про продакшен. Соревнование — оно для того и соревнование, чтобы упарываться.


  1. tyamgin
    25.03.2017 13:28
    +2

    кратко о рецепте второго места

    О рецепте стабильного второго места.
    Поздравляю с дублем!


  1. gaploid
    25.03.2017 14:55

    А сколько получилась точность предсказания модели, что человек «выйдет из игры»? В каком-нибудь более понятном показателе, а то я не очень понимаю этот Log loss. Простите за болванство.