Скоро открытие ML Boot Camp III

15 февраля стартует Machine Learning Boot Camp III — третье состязание по машинному обучению и анализу данных от Mail.Ru Group. Сегодня рассказываем о прошедшем контесте и открываем тайны нового! Итак, в ходе предстоящего конкурса нужно будет угадать, останется ли участник в онлайн-игре или уйдет из нее. Выборки для задачи построены на двенадцати игровых признаках для 25000 пользователей. Естественно, все данные анонимизированы.

Сами признаки:

• maxPlayerLevel — максимальный уровень игры, который прошел игрок;
• numberOfAttemptedLevels — количество уровней, которые попытался пройти игрок;
• attemptsOnTheHighestLevel — число попыток, сделанных на самом высоком уровне;
• totalNumOfAttempts — общее число попыток;
• averageNumOfTurnsPerCompletedLevel — среднее количество ходов, выполненных на успешно пройденных уровнях;
• doReturnOnLowerLevels — делал ли игрок возвраты к игре на уже пройденных уровнях;
• numberOfBoostersUsed — количество использованных бустеров;
• fractionOfUsefullBoosters — количество бустеров, использованных во время успешных попыток (игрок прошел уровнь);
• totalScore — общее количество набранных очков;
• totalBonusScore — общее количество набранных бонусных очков;
• totalStarsCount — общее количество набранных звезд;
• numberOfDaysActuallyPlayed — количество дней, когда пользователь играл в игру.

Тестовую выборку мы разобьем случайным образом в соотношении 40/60. Результат на первых 40 % будет определять положение участников в рейтинговой таблице на всем протяжении конкурса. Результат на оставшихся 60 % станет известен после окончания конкурса, и именно он определит финальную расстановку участников.

Обладателю лучшего решения мы подарим MacBook Air. Второму и третьему месту достанется Apple iPad. Четвертому, пятому и шестому — Apple iPod Nano. По традиции, 50 лучших участников получат памятные футболки с символикой чемпионата. Кроме того, лучших из лучших мы пригласим в Mail.Ru Group для собеседования на позиции, связанные с анализом данных. Зарегистрироваться на чемпионат можно здесь.

Machine Learning Boot Camp II

Чтобы участники лучше понимали, что им предстоит, представляем задачу прошлого чемпионата и лучшее решение от победителя.

Задача. Участники второго контеста столкнулись с задачей «Оценка производительности». Мы предложили им научить компьютер предсказывать время умножения двух матриц размера m?k и k?n на тестовой вычислительной системе. Участники знали, сколько времени эта задача решалась на других системах, размеры матриц и параметры систем.

В качестве критерия качества решения задачи мы использовали наименьшую среднюю относительную ошибку (MAPE, в некоторых источниках упоминается как MRE) для реализаций, работающих дольше одной секунды:

$$ где N — количество объектов в выборке, y_i — истинное время работы в i-­м эксперименте, g_i — предсказанное время. Первое место в конкурсе занял Михаил Карачун, о его методике решения — далее с его слов.

История победителя

Общая методика решения подобных задач описана в приложенном к соревнованию документе. Основная идея заключается в том, чтобы прогнозировать не время вычисления time, а величину time/(m*n*k). Причем эта величина в рамках одной системы колеблется незначительно, и при обучении модели на нескольких системах сразу лучше использовать нелинейные методы, например, случайный лес.

Шаг нулевой — common

Для решения использовался python, проверка результата локально происходила при помощи метода kfold с 5 разбиениями. При подготовке данных все категориальные признаки прошли преобразования «одно значение признак — одна колонка» (one hot)

Шаг первый — model selection

Для выбора параметров модели использовался модуль hyperopt. Он работает лучше простого поиска по сетке, так как не просто перебирает параметры, а пытается их оптимизировать.


После первого прогона с небольшим количеством деревьев лучше всего себя показал GradientBoostingRegressor(loss='lad').

Шаг второй — feature engineering

На втором этапе была поставлена задача отсеять лишние признаки, так как всего их оказалось ~ 1100. Для этого был использован метод рекурсивного отбора. Он заключается в последовательном исключении N признаков по оценке на основе кросс-валидации. На выходе алгоритм в параметре ranking_ хранится этап, на котором был отсеян признак: 1 — значит он остался до конца, чем больше — тем хуже. Параметр support_ хранит маску выбранных признаков — то есть тех, что в ranking_ с единицей. Нужно отметить, что не всегда окончательный вариант лучший, иногда для решений можно использовать признаки, которые были отсеяны ближе к концу отбора. Эта процедура выполнялась достаточно долго, например, на моем ноутбуке со средней производительностью она заняла более 12 часов.


В итоге количество признаков удалось уменьшить примерно до 10. Далее методом проб и ошибок были найдены еще несколько удачных.


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

Шаг третий — ensembling

Ансамбли. Если объединить деревья решений, обученные на разных подмножествах признаков, то результат превосходит по эффективности отдельно взятое дерево — так работает random forest. Но если взять несколько разных ансамблей и объединить их решения, то это тоже может помочь. Как показывает общая практика и мой личный опыт, если вы имеете несколько моделей с примерно одинаковым результатом, то их среднее почти всегда лучше. И чем больше отличаются эти модели по логике построения — тем лучше. Например, если вы решите взять два random forest с одинаковыми параметрами, но разным количеством деревьев — это вряд ли поможет. А если взять random forest и gradient boosting regressor — то почти всегда получается лучше, иногда это именно то что нужно, если речь идет о двух или трех знаках после запятой.

При решении данной задачи я взял топ моделей, полученных при гипероптимизации параметров и перебрал их сочетания. Особенно хорошо считались модели, которые давали одинаково хороший средний результат на кросс-валидации, при этом лучшие и худшие фолды у них различались. В итоге осталось три модели, в качестве прогнозных значений использовалось среднее.

Обучение разных моделей на подмножествах строк и/или столбцов быстрого результата не дали.


Шаг четвертый — we need to go deeper

После я решил проверить, как сильно отличается ошибка прогноза в зависимости от разных параметров вычислительной системы. Простой перебор показал, что если среднее значение ошибки при кросс-валидации ~0.05, то на одной из операционных систем эта ошибка ~0.30.

Первой идеей было скорректировать веса объектов при обучении, увеличив их для данной ос, но результат только ухудшился. Так как данных для этой ос достаточно мало (<100), то отдельную модель тоже не настроить — переобучится. Помогло промежуточное решение. Я взял отдельную модель, обучил ее на всей выборке, но с весами, отдававшими приоритет данной ос. При вычислении итогового результат эта модель использовалась только для одной ос. Т.е. основные модели обучались на всей выборке без весов и предсказывали результат для всех ос кроме одной. Одна модель обучалась на всей выборке с весами, и прогнозировала только для одной ос. Здесь впервые возникли трудности с кросс-валидацией — локальное улучшение не всегда подтверждалось публичной оценкой. Это связано с тем, что количество примеров для одной ос достаточно мало, и если они еще разбиваются на несколько частей для проверки, то стабильного результата ждать не придется.


Шаг пятый — last step

Имея достаточно неплохой набор моделей было сделано еще одно предположение, которое принесло достаточно хороший результат. Если нужно минимизировать относительное отклонение, почему бы именно его и не предсказывать? Здесь постараюсь подробнее. Есть несколько вариантов, что подавать модели в качестве эталонного примера:

1. Обучаем модель, подавая ей в качестве выхода непосредственно time — время вычисления. Это то, от чего мы отказались сразу, послушав совет авторов статьи приведенной в начале.
2. Обучаем модель, подавая на выход time/(m*n*k) — т. е. угловой коэффициент рассчитанный для каждой вычислительной системы. Это то, что мы делали до данного момента.
3. Обучаем модель, подавая на вход значение time/reg_k*(m*n*k). Т.е. мы предполагаем, что для каждой вычислительной системы зависимость времени от m*n*k линейная с угловым коэффициентом reg_k, и обучаем модель прогнозировать относительное отклонение от этой модели.

В качестве reg_k была взята медиана time/(m*n*k), в качестве идентификатора вычислительной системы — признаки os+cpuFull, так как именно на этом сочетании линейная модель с медианой давала лучший результат.


Шаг шестой — rules rule

Также расскажу про небольшой hack, который, между прочим, ощутимо сказался на итоговом результате. Если внимательно посмотреть на формулу оценки, то видно, что из нее исключаются измерения длительностью менее секунды. Это значит, что все прогнозные значения менее единицы можно смело округлять в большую сторону, так как если они действительно меньше, то в результат не включается, а если нет — то вы уменьшите ошибку.

Общие впечатления

Хочется отметить что по ходу всех улучшений, описанных в статье, локальная оценка решения, оценка в public score, а как потом выяснилось и в private score, всегда изменялись в сторону улучшения. Вот тут можно посмотреть итоговый рабочий скрипт.

Попробуйте себя!

Как всегда, мы предлагаем на портале обучающую статью для новичков и серьезную задачу для экспертов. Кстати, на портале можно потренироваться в решении предыдущих конкурсов — все они открыт в режиме песочницы. Присоединяйтесь к нам на регистрации!