История 3-го места на ML Boot Camp III

Недавно завершился контест по машинному обучению ML Boot Camp III от Mail.Ru.

Будучи новичком в machine learning мне удалось занять 3-е место. И в этой статье я постараюсь поделиться своим опытом участия.
Я давно участвую в различных контестах по спортивному программированию, в том числе и в других чемпионатах от Mail.Ru, откуда собственно и узнал об этом.

С машинным обучениям я был знаком только на уровне лабораторных работ. Слышал о таком ресурсе, как kaggle, но ни в чём подобном ранее не участвовал. Поэтому это стало для меня неким вызовом — вспомнить чему учили в универе, и попытаться что-то из этих знаний собрать.
На высокие места особо не надеялся, но призы неплохо добавляли мотивации.

Незадолго перед стартом уже была известна задача. Это задача бинарной классификации. Выбор языка программирования был не особо велик, я знал, что было принято использовать Python или R. С обоими я на минимальном уровне знаком, но выбрал R. В нём всё что нужно есть «из коробки», не нужно заморачиваться со сборкой или установкой пакетов. Хоть он и странный, в нём кривой GC, он периодически падает, о выборе я не пожалел.

Задача

Есть данные об участии игроков в онлайн-игре за последние 2 недели в виде 12 числовых признаков. Нужно определить, покинет-ли её игрок хотя-бы на неделю, или останется. А именно, сказать вероятность этого события. ? Ссылка на полное условие задачи.

На первый взгляд задача абсолютно классическая. Таких, наверное, море на kaggle, бери готовый код и используй. Даже в тренировке предлагают схожую задачу кредитного скоринга. Как оказалось, не на столько всё просто.

Мне пригодилось:

• 2 компьютера i5-3210M 2.5GHz ? 4, 12GB RAM и i3-4170 3.7GHz ? 4, 16GB RAM (было 8, но пришлось докупить ещё)
• Установленный RStudio на каждом
• Немного везения

Обзор данных

Обучающая и тестовая выборки без пропусков. Размером по 25000 каждая – на так уж и много. На этом исследование данных практически заканчивается. Я почти не делал никаких графиков и прочих визуализаций.

Первые попытки

Уже заранее определился, что начну с логических алгоритмов классификации – решающие деревья, решающий лес, а также random forest, bagging, boosting над ними. Решающие деревья и random forest не трудно запрограммировать самому. Это делается по лекциям Воронцова, где описан алгоритм ID3.

Стало понятно, что с самописными алгоритмами далеко не пойдёшь, хотя эта процедура здорово помогла в их понимании. Нужно использовать что-то готовое.

Xgboost

Xgboost — библиотека, реализующая градиентный бустинг. Используется многими победителями соревнований kaggle – значит нужно пробовать.

Одним из параметров обучения было количество деревьев (nrounds), но сразу не понятно сколько нужно указывать. Есть и альтернатива – разбить выборку на 2 части – обучение и контроль. Если при добавлении очередных деревьев ошибка на контроле начинает ухудшаться, то останавливать обучение. Я воспользовался техникой Bootstrap aggregating.

Делим выборку 200 раз случайным образом на обучающую и контрольную (по моим экспериментам, оптимальным оказалось соотношение 0.95/0.05), и запускаем xgboost. Итоговый классификатор – голосование (среднее) всех 200 базовых классификаторов.

Это дало мне гораздо лучший результат, нежели самописный Random Forest или AdaBoost.

Feature engineering

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

Новыми признаками стали просто попарное умножение и попарное деление каждого с каждым. Вместе с исходными всего получилось 144 признака.

В тех же лекциях Воронцов предлагает использовать жадный алгоритм Add-Del, поочередно удаляя и добавляя новый признак. Но по причине неустойчивости модели (на разных random seed с одинаковыми данными оценка качества сильно колеблется), этот подход не дал результата.

Я использовал генетический алгоритм. Сгенерируем начальную популяцию – бинарные вектора, означающие какие признаки брать, а какие нет. Новые индивиды появляются путем скрещивания и мутации предыдущих. Тут нужно было позаниматься подбором различных вероятностей, штрафов за количество признаков, и др. За 4-6 поколений и за 12 часов работы обычно всё сходилось к локальному минимуму. Однако этот локальный минимум уже давал неплохие оценки. Xgboost не очень чувствительный к неинформативным признакам (в отличии от нейросети, о которой будет дальше) – одна из причин того, что скрещивание двух хороших наборов признаков даёт тоже хороший набор.

В итоге из 144 признаков у меня отобрались 63.

LightGBM

Позже я перешел на использования библиотеки LightGBM от Microsoft. Она давала почти такие же результаты как Xgboost, но работала в разы быстрее. А также имела дополнительные параметры обучения. Например, полезной оказалась возможность ограничивать не только максимальную глубину дерева (max_depth), но и число листьев (num_leaves). Для меня оптимальными оказались num_leaves = 9 и max_depth = 4.

Нейронная сеть

После неудачных попыток использовать SVM, KNN, Random Forest, я остановился на нейронной сети. А точнее, на персептроне с одним скрытым слоем, используя пакет nnet.

Одним из первых что я сделал – запустил примерно такой код:

set.seed(2707) trControl = trainControl(method='cv', number=5, classProbs=T, summaryFunction=mnLogLoss) model = train(X, Y, method='nnet', metric='logLoss', maxit=1000, maximize=F, trControl=trControl) 

Это практически пример из мануала. Далее, взял среднее арифметическое с тем что получил от LightGBM, и сделал посылку на сервер. Очень удивился, как это закинуло меня на первое место, где продержался около недели.

Обработка частных случаев

Как и в обучающей, так и тестовой выборках присутствовали одинаковые вектора, но с разными ответами. Например, присутствовали такие, которые встречались по 1423, 278, 357, 110 раз. Наверное, нет ничего лучше, чем посчитать для них вероятности отдельно, что я и сделал. Обработал только те, которые встречались более 15 раз. Вопрос был только в том, исключать эти повторы из обучения, или нет. Я попробовал оба варианта, и сделал вывод, что исключение делает хоть немного, но хуже.

На самом деле сейчас можно было остановиться. Это дало бы финальное первое место с небольшим запасом. Но задним числом все умны.

Ансамбль из двух моделей

Стоило придумать более удачную агрегирующую функцию, нежели просто среднее арифметическое или среднее геометрическое. Идея следующая:

• Создадим новую выборку на основе старой. Отличие будут лишь в столбце ответов. Столбец ответов — 0 или 1 в зависимости от того, какая из двух моделей дала лучший результат по сравнению с правильным ответом.
• Запустим на этой выборке логистическую регрессию, SVM, бустинг, или что угодно другое. Как оказалось, стоило брать SVM.
• По этим результатам этой агрегирующей модели получаем вероятности, с которыми нужно доверять каждой из двух исходных (бустинг или нейросеть). По сути, если использовать линейную модель, то мы получаем оптимальные коэффициенты, вместо обычного среднего.

Нейронная сеть + bootstrap

Оставлять то, что получилось с удачным выбором seed было нельзя. Просто повезло, и, казалось, это явный overfit. Далее всё время я потратил на то, чтобы хотя-бы приблизиться к полученному результату. Итак, повезло с удачным выбором seed, т.е. удачно подобрались веса для нейронов. Тогда нужно было много раз запустить обучение, и выбрать лучшее. Но как определить получилось-ли лучше? И я придумал следующее:

• 200 раз разбиваем выборку в соотношении 0.9/0.1 (обучение/контроль).
• Для каждого разбиения по 20 раз запускаем обучение на обучающей подвыборке. Выбираем ту модель, которая дала лучший результат на контрольной.
• Итоговая модель – голосование (среднее) 200 моделей (важно, что не всех 200?20).

Таким образом, я почти приблизился к желаемому результату. Но к сожалению, для победы чуть-чуть не хватило.

Нереализованные задумки

• Использовать видеокарту для ускорения обучения. Официальная версия LightGBM не поддерживает, однако существуют форки.
• Использовать вычислительный кластер из двух компьютеров. Пакет doParallel это поддерживает. Ранее я просто переходил по RDP на второй компьютер и запускал вручную.
• Теоретически, потратив несколько посылок, можно было вычислить более точные вероятности для повторяющихся векторов с разными ответами (другими словами – вытянуть ещё немного данных со скрытой тестовой подвыборки).

Спасибо за внимание.

Список литературы:

• Лекции по логическим алгоритмам классификации, К. В. Воронцов
• Логические алгоритмы классификации, К. В. Воронцов
• Обобщающая способность Методы отбора признаков, К. В. Воронцов

  Код на github