Как-то в самом начале нового года мы решили совместить приятное с полезным: дружно отдохнуть и поработать. И пригласили сотрудников, наших студентов и экспертов из компаний EMC, Rosalind, Yota, Game|Changers провести три дня зимних каникул в домике под Петербургом.
Встреча с друзьями-единомышленниками за городом хороша, чтобы поделиться идеями, написать статью или закончить работу, до которой никак не доходили руки. Для этого мы и организовали выезд на Data Mining Camp. Решили, что будет сауна, настольные игры, контактный зоопарк и – гвоздь программы – хакатон.
На хакатоне ребята при помощи экспертов работали над тремя исследованиями: модель иерархической кластеризации признаков, модель ухода слушателей онлайн-курсов, попробовали улучшить алгоритм Gradient Boosting Machines, а также поучаствовали в международном конкурсе на платформе Kaggle. О том как это было и как ребята продолжают работать над этими идеями под катом…
Потехе час...
Первым делом мы отправились в частный зоопарк. Порезвились там, вспомнили детство: каждый нашел развлечение на свой вкус. Кому-то по душе пришелся попрошайка-енот, кому-то верблюд или лама…
… но самые смелые отважились поиграть с большими, но добрыми собаками.
Вечер первого дня мы провели за задушевными разговорами в сауне и подготовкой к завтрашнему хакатону, встречая прибывающих гостей. Следующее утро прошло за разговорами и настольными играми.
Вдохновленные развлекательной программой мы приступили к обсуждению насущных дел. Прямо за игрой в “Манчкин” разговор перешел к образованию в сфере Data Mining и идеям для новых исследований.
… а делу время!
Среди нас были специалисты в области биоинформатики, финансов, телекома и больших данных, которые за чашечкой чая поделились своим исследовательским опытом. Например, после рассказа Владимира Суворова, эксперта из EMC, о расшифровке генома стрекозы, появился десяток идей, что бы еще такого можно расшифровать и как начать сотрудничество в области биоинформатики.
Эксперты из Rosalind поделились своим образовательным опытом. Мы пришли к выводу, что лекции по машинному обучению и анализу данных менее эффективны, чем практика. Хакатоны, конкурсы, реальные задачи от экспертов — вот что нужно, чтобы стать хорошим специалистом. Открытым остался вопрос: “Как совместить онлайн и оффлайн образование? Рекомендовать перед началом обучения прослушать определенные курсы на Coursera? Совсем исключить лекции? Или есть другой путь?”
Тем временем близился хакатон, который мы решили разделить на два независимых потока: участники хакатона #1 проводили свое мини-исследование и писали статью по его результатам, а участники хакатона #2 общими усилиями решали задачу для международного конкурса.
Хакатон #1
В исследовательском хакатоне участвовало три команды. Первая команда работала над методами отбора признаков, одной из главных задач анализа данных. Зачем это нужно? Слишком большое количество признаков, то есть столбцов в наборе данных может усложнить вычисления или вообще сделать их невозможными. Например, если размер выборки меньше, чем количество признаков.
Предположим, что мы хотим предсказать, какое место наша страна займет на олимпиаде, и решили набрать побольше информации. Об экономике: ВВП на душу населения, объем внешнего долга, минимальный размер оплаты труда, объем импорта и экспорта, количество иммигрантов. О географии: широта столицы, процент площади, занятой горами, площадь всей страны. О прошедших олимпиадах: количество медалей каждого достоинства, количество спортсменов, количество видов спорта, в котором представлена страна, место проведения… В общем, мы так увлеклись сбором данных, что не заметили, как количество признаков превысило количество участвующих стран. А это, прямо скажем, нехорошо, потому что количество уравнений стало меньше количества неизвестных, что ведет либо к несовместности системы, либо к бесконечному количеству решений.
Придется отсеять лишнюю информацию. Обычно для выбора модели с оптимальным набором признаков используют информационные критерии (AIC, BIC). Лучшей считается модель, в достаточной мере полно описывающая данные с наименьшим количеством признаков. Или используют встроенные в модели методы регуляризации, другими словами, надеются, что модель сама справится с некорректными данными. Или понижают размерность данных с помощью метода главных компонент (PCA). Суть метода главных компонент легче всего передать на примере с двумя признаками:
Каждой строке таблицы соответствует точка на плоскости. Проведем через них прямую так, чтобы вдоль нее происходило максимальное изменение данных, она называется первой главной компонентой — PC1. Затем спроецируем все исходные точки на эту ось. Все отклонения от новой оси будем считать шумом. Проверить, действительно ли это шум, можно, поступив с этими остатками так же, как мы поступили с исходными данными — найти в них ось максимальных изменений. Она называется второй главной компонентой (PC2). И так надо действовать до тех пор, пока шум уже не станет действительно шумом, то есть случайным хаотическим набором величин. Пример взят отсюда, здесь же можно поподробнее почитать про метод главных компонент.
Если же не хочется менять признаки, как при методе главных компонент, или модели не имеют встроенных регуляризаций, например, нейронные сети, и легко подвержены переобучению, нужны другие подходы. Наши ребята решили разработать модель иерархической кластеризации признаков с последующим поиском подмножества самых удачных из них.
Рассмотрим поподробнее получившийся алгоритм. Иерархия будет формироваться с помощью алгоритма кластеризации, наиболее популярный из них — метод k-средних. Количество кластеров k известно заранее, предположим, что мы задали k=2. Выберем случайным образом два признака из нашей модели и начнем формировать вокруг них кластеры. Будем переносить центр кластера, пока суммарное квадратичное отклонение не станет минимальным. Признак в нашем случае превращается в точку в n-мерном пространстве, где n-количество записей в таблице, то есть количество стран, принимающих участие в олимпиаде. О механизме работы алгоритма k-средних можно почитать здесь.
Теперь наши признаки разделены на две группы. В каждой из них мы выбрали один характерный признак по принципу близости к медиане кластера (1). Снова кластеризуем каждую из получившихся групп, исключив характерный признак (2). Будем повторять до тех пор, пока количество признаков в подгруппе >2.
В итоге получим дерево, в узлах которого к нижним уровням находятся все менее значимые признаки (3). После этого производится отбор. Предположим, что нам нужно оставить 8 признаков. Сначала наша модель обучается только на признаках из верхнего уровня иерархии. Для каждого из них принимается решение на основе вклада признака в модель: оставить в модели, убрать или углубиться в подгруппу. Если вклад достаточно велик — оставляем, если средний — оставляем и углубляемся в подгруппу, если совсем мал — выбрасываем всю подгруппу вместе с ним. Продолжаем спускаться вниз по дереву до тех пор, пока ошибка предсказания нашей модели уменьшается и количество отобранных признаков <8 (4).
Вторая команда работала над созданием модели ухода пользователей MOOC (Massive Open Online Course) на примере трех платформ: Coursera, Rosalind и Stepic. Эта задача сейчас очень актуальна для онлайн образования — в одном из интервью Дафна Коллер рассказывала, что только 7% пользователей заканчивают курс на Coursera. Цель — создать модель, которая будет описывать поведение пользователя на разных этапах обучения, чтобы отслеживать активность и найти «узкие места».
На хакатоне ребята исследовали данные платформы Rosalind, которая в первую очередь направлена на подготовку биоинформатиков с помощью решения практических задач. В течение хакатона ребята определились со списком признаков для модели и вариантами целевой переменной. Для построения модели выделили три типа признаков, характеризующих:
На хакатоне посчитали не все признаки (не хватило мощностей и рабочих рук), но зато стало понятно, куда ребятам двигаться в дальнейших исследованиях.
Третья команда попробовала усовершенствовать алгоритм Gradient Boosting. Этот алгоритм строит модель предсказания из ансамбля «слабых» предсказывающих моделей, которые называют «base-learner» или «базовые кирпичики». «Слабые» модели обучаются на тренировочной выборке, после чего объединяются таким образом, чтобы итоговая модель предсказания становилась точнее на каждой итерации. Обычно используется алгоритм Gradient Tree Boosting, где в качестве «базовых кирпичиков» выступают деревья принятия решений CART фиксированного размера. В узлах деревьев принятия решений лежат условия перехода, а в листьях — значения целевой функции. На картинке классический пример дерева принятия решений про пассажиров Титаника (sibsp — количество родственников на корабле):
Ребята задумались, можно ли увеличить точность модели, различным образом смешивая компоненты ансамбля. Были рассмотрены варианты GBM(Gradient Boosting Machines), где ансамбль состоит из SVM-регрессий, линейных моделей и всевозможных вариантов деревьев. Пока что стандартный GBM победить не удалось, но работа продолжает кипеть и после окончания хакатона.
Целью всех трех команд было написать статью для участия в международной конференции по машинному обучению ICML, которая пройдет летом в Пекине.
Хакатон #2
Второй хакатон был посвящен конкурсу от компании Яндекс на краудсорсинговой платформе Kaggle. Задача — ранжировать веб-страницы в выдаче на основе предпочтений пользователя. Яндекс предоставил историю почти 6 миллионов пользователей за 27 дней, это около 21 миллиона запросов. Для каждого запроса имелись: id пользователя, список слов в запросе, 10 позиций из выдачи, номер позиции, которую выбрал пользователь, и время каждого действия пользователя. В дополнение к этому были предоставлены данные тестовых сессий за следующие 3 дня.
Нужно было расположить выдачу в тестовых сессиях так, чтобы получить максимальный показатель NDCG (Normalized discounted cumulative gain). Рассмотрим подробнее, что это такое. DCG — discounted cumulative gain или приведенная суммарная эффективность релевантности рассчитывается по следующей формуле:
где i-порядковый номер выдачи, а rel — степень соответствия запросу. По шкале соответствия 0 до 3 первые шесть страниц в выдаче могут быть оценены, например, так: 3,2,3,0,1,2. Рассчитаем приведенную суммарную эффективность релевантности:
и приведенную суммарную эффективность релевантности при идеальном ранжировании:
Нормируем результат, разделив реальный DCG на идеальный:
Эта метрика часто используется в информационном поиске и при оценке ранжирования.
Разобравшись с показателями эффективности, ребята приступили к работе. Подготовленные логи пользовательских запросов заняли более 60 гигабайт, что затруднило применение алгоритмов машинного обучения. Времени до дедлайна оставалось всего-ничего, поэтому было решено оставить данные только о персональных навигационных запросах. Они составили 10% от выборки, то есть 6 гигабайт.
Для того чтобы улучшить текущую выдачу команда решила проверить, есть ли такие пользователи, которые в прошлом вводили тот же самый запрос (query_id). Во многих случаях так и оказалось. Ребята проализировали время посещения этим пользователем определенных документов, частоту кликов и другие параметры в обучающей выборке, а затем использовали эти данные для ранжирования текущей выдачи. Было использовано простейшее правило: веб-документ продвигался наверх, если раньше пользователь с таким же запросом посещал его несколько раз, и среднее время посещения было более 400 t.s.(time stamp — эквивалент времени. По условию время, равное 400 t.s и более, означало релевантность документа пользователю).
По итогам конкурса наша команда преодолела baseline — результат удалось улучшить на 0.6% по сравнению с тем, что предложил Яндекс в качестве образца. Для сравнения, лучший результат в таблице лидеров обошел baseline всего на 1,6%. Вот за такие копейки идет борьба по улучшению качества сервиса.
Впечатления
Наутро все разъехались по домам. Время прошло незаметно за работой и развлечениями, за интересными разговорами и обменом идеями.
Идея проведения подобных встреч показалась удачной, поэтому мы решили регулярно проводить мини-конференции в неформальной обстановке. Следующую назначаем на весну и обязательно напишем анонс с точной датой на Хабре. Мы всегда рады новым единомышленникам, и если у вас есть интересные идеи по этому поводу, пожалуйста, поделитесь ими в комментариях!
Автор: DMwarden
