Превью
Здравствуй! 25-го апреля 2016 года закончилось 3-х месячное напряженное соревнование Home Depot Product Search Relevance в котором нашей команде Turing Test (Igor Buinyi, Kostiantyn Omelianchuk, Chenglong Chen) удалось не только неплохо разобраться с Natural Language Processing и ML, но и занять 3-е место из 2125 команд. Полное описание нашего решения и код доступны тут, краткое интервью тут, а цель этой публикации не только рассказать о решении, которое принесло нам такой результат, но и о тех трудностях и переживаниях, через которые нам довелось пройти во время соревнования.
Пару слов о Kaggle
Вероятно, большинство читателей знакомы с Kaggle. Для остальных отмечу, что на данный момент это крупнейшая в мире площадка, где постоянно проходит существенное количество соревнований по Data Science тематике, в которых коллективный разум тысяч участников генерирует большое количество решений реальных прикладных задач. В результате участники соревнований получают знания и опыт (победители — еще и призы), а организаторы получают идеи, которые можно успешно внедрить на практике.
Постановка задачи
— есть сайт по продаже инструментов для ремонта и стройматериалов, на котором можно найти больше количество специфичных товаров
— есть юзеры, которые пытаются найти интересующий их товар, используя функцию поиска
— есть несколько сотен тысяч соответствий «поисковый запрос» /«показанный товар»; информация о товаре состоит из нескольких текстовых полей, таких как название, описание и множество атрибутов (например, бренд или цвет)
— есть усредненные оценки релевантности от асессоров по некоторой части таких соответствий
— стоит задача построить алгоритм, который будет хорошо прогнозировать оценки релевантности, которые поставили бы асессоры, для остальных пар «запрос» /«товар»
Зачем это нужно?
Оценки релевантности необходимы при оптимизации поискового алгоритма, который подбирает соответствие «запрос»/ «товар».
Такие оценки могут проставить асессоры, но они работают медленно, а их время стоит дорого или получить автоматически, тогда можно сэкономить на асессорах и существенно повысить скорость обратной связи. Однако качество оценок должно остаться на том же уровне.
Асессоры — это люди, которые могут ошибаться
Мы пытались научить модель имитировать поведение людей, выставляющих оценки (и ничего сверх этого). Ответ на вопрос насколько их оценки отвечают «реальной релевантности» неизменно уводит нас от конкретной задачи к истокам философии.
Как оценивалось качество модели?
В качестве метрики использовалась RMSE, которая как и любая другая квадратичная метрика сильнее всего штрафует большие ошибки.
Какими были исходные данные?
Данные состояли из пар «запрос»(search term)/«товар» (который состоял из трех частей: product title, product description, attributes) и усредненной оценки релевантности (которая принимала значения от 1 до 3, включая некоторые дробные).
Разбивка на train/test была сделана в пропорции 74 067/166 693 и не была случайной (было много запросов, которые присутствовали только в test или только в train и их распределение нельзя было назвать нормальным).
Данные были достаточно грязные (большое количество грамматических ошибок в запросах)
Немного о нас
Наша команда на протяжении 5/6 конкурса состояла из двух человек (Игорь Буйный и Константин Омелянчук). Мы оба коллеги-аналитики, работающие в украинской компании, разрабатывающей браузерные игры. До начала этого соревнования у нас за спиной было много прослушанных курсов и всего одно соревнование на kaggle.com, в котором мы попали только в топ 15%. Игорь как раз закончил один проект, где использовалось NLP, и позвал меня принять участие в этом конкурсе.
Наши цели
Изначальными целями были:
— получить практические навыки работы с реальными данными
— разобраться глубже с NLP
— подтянуть навыки программирования
— попасть в топ 10%
Но аппетит, как известно, приходит во время еды, и по мере приближения конца соревнования наши цели пересматривались в сторону более амбициозных.
Первые шаги
Как уже говорилось ранее, полное описание нашего решения опубликовано в другом месте, а в этой статье мы хотели бы рассказать о хронологии наших действий, поэтому подаем основные результаты и открытия в том порядке, в котором они достигались.
Этап 1
Мы начали с самого простого, с чего можно было начать — разобрались с готовыми скриптами, которые всегда можно найти на форуме. Поскольку никаких «посчитанных переменных» не было, их нужно было генерировать. Первыми переменными у нас (как и у многих других участников) были числовые переменные типа количества совпадений слов между запросом и документом. Первой обработкой текста было использование stemmer, который оставлял от каждого слова его корень. Модель xgboost на этих фичах после обработки текста с помощью stemmer давала RMSE в районе 0,49.
Этап 2
Далее мы начали двигаться в трех направлениях:
— генерация новых простых переменных
— подгонка параметров модели
— исправление наиболее часто встречающихся ошибок в тексте и приведение одинаковых по смыслу слов к единому формату.
Постепенно двигаясь в этих трех направлениях, мы приблизили RMSE к 0,48 и пришли к выводу, что третье направление давало наибольшее улучшение по сравнению с остальными. На этом этапе было сделано два важных открытия:
1. Возникла идея как-то автоматизировать процесс исправления ошибок, и было найдено решение использовать расстояние Дамерау-Левенштейна, чтобы учесть не только совпадающие, но и похожие слова. Это расстояние показывало, сколько нужно сделать операций вставки/замены/удаления/транспозиции символов, что бы преобразовать одну строку в другую. Мы считали два слова (word1,word2) одинаковыми, если это расстояние было меньше min(3,max(len(word1)-3,1)). Новые переменные, подсчитанные с использованием этого критерия, позволили улучшить RMSE до 0,478 и послужили еще одним подтверждением мысли о том, что обработка текста является очень важной в этом конкурсе.
2. К списку наших простых переменных мы добавили переменные, которые учитывали количество букв в совпадающих словах. Как ни странно, это оказались очень сильные переменные, с помощью которых мы улучшили RMSE до 0,474.
Этап 3
Стало понятно, что одними простыми (keyword match) переменными мы не обойдемся и нужно использовать более сложные. Классическими переменными в данной задаче являются tf/idf переменные, которые учитывают вес каждого совпадающего слова в зависимости от его частоты в конкретном документе и во всей коллекции документов. Первые же попытка добавить эти переменные принесла нам 0,468 на RMSE.
Параллельно с этим мы стали искать полезную информацию среди атрибутов(attributes) документа. Включение переменных связанных с брэндами и материалами повысило RMSE до 0,464.
Этап 4
Следующим этапом было генерация переменных, которые как-то бы учитывали смысловую связь между словами. В этой задаче нам помог пакет WordNet из библиотеки NLTK. Используя встроенные функции, которые по-разному считали синонимическую близость (similarity) между словами, мы получили еще одну категорию переменных с принципиально новой информацией, которая не использовалась ранее.
Также были посчитаны переменные, которые учитывали, к какой части речи относятся слова (использовался NLTK POS tagger). Вместе с этим мы существенно продвинулись в обработке текста и исправлении ошибок. Все это вместе позволило улучшить RMSE до 0,454 и попасть в топ10 команд. (примечание 1 на графике прогресса)
Этап 5
По мере нашего продвижения становилось все сложнее и сложнее улучшать RMSE и соотношение удачных действий к попыткам, которые не приносили желаемый результат, стало склоняться не в нашу сторону. Это навело на мысль, что пора приниматься за построения ансамбля. Первые попытки построить ансамбль не принесли успеха, но мы продолжили работать в этом направлении
Ключевыми действиями, которые позволили сделать нам следующий скачок, стали:
— обработка текста и исправление ошибок;
— локальные tf/idf переменные, которые считались на уровне документов, имеющих отношение к каждому конкретному поисковому запросу;
— word2vec переменные, которые дали очень существенный прирост к качеству прогноза.
Таким образом, мы довели RMSE до 0,445 на отдельной модели (single model) и вышли на первое место в текущем рейтинге спустя первые полтора месяца с начала соревнования. (примечание 2 на графике прогресса)
Рисунок. График прогресса результатов
Дополнительные проблемы потенциальных призеров
До выхода на первое место, мы рассматривали это соревнование как площадку для обучения, но в этот момент мы поняли, что есть шансы, как минимум, пробиться в топ10 (вместо изначальной цели в топ10%), а как максимум — попасть в призы (первые три места). Но для того, что бы бороться за призы, нам нужно было дополнительно решить две проблемы.
Воспроизводимое решение
Победители соревнования должны предоставить хорошо оформленную документацию и код, способный воспроизвести финальное решение. Наше решение, мягко говоря, не удовлетворяло этому требованию, так как в код постоянно вносились какие-то правки, старые версии кода часто не сохранялись, а промежуточные результаты расчетов записывались в целую кучу файлов. Кроме того, что нельзя было установить точное соответствие между версией кода и конкретным файлом с переменными, так и еще полный пересчет в ручном режиме требовал больше недели вычислительного времени на наших машинах.
Шаринг всех сторонних внешних данных
Вторым важным моментом стала поднявшаяся дискуссия на форуме о том, какая обработка текста является допустимой, а какая нет. Этот спор породил скрипт юзера steubk, который хитрым образом прогонял все поисковые запросы через гугл и подтягивал исправленный гуглом текст. Админы конкурса сперва выступили против использования этого алгоритма и против «ручных исправлений» (hand labeling) ошибок в тексте. Но поскольку не было четкой грани между тем, что является «ручным исправлением», а что — обобщенным правилом основанным на нашем суждении (feature engineering), то в результате таки разрешили использовать свои словари исправлений. Единственным условием было запостить этот словарь на форум за неделю до конца соревнования (merger deadline). Понимая важность обработки текста и считая, что мы создали весьма хороший словарь, мы не хотели публиковать его на форуме и искали пути, как автоматизировать большую часть обработки текста. Такая автоматизация приводила к ухудшению результатов, а поскольку без обработки текста мы не могли приступить к пересчету всех переменных, то это стопорило дальнейшую работу.
Разве это так сложно?
В общей сложности на переписывание всего кода по единому формату и пересчет переменных мы потратили порядка месяца (это еще совпало с дефицитом свободного времени на соревнование; смотри примечание 3 на графике прогресса). Некоторое продвижение мы получили от построения ансамбля. Общая идея ансамбля — научить на части данных много моделей 1-го уровня с разными параметрами и на разных наборах переменных и на основании предсказаний этих моделей построить модель 2-го уровня. Это подход хорошо работает, если грамотно разделить данные для обучения и валидации моделей. В нашем случае это усложнялось еще и тем, что данные в train и test отличались по своей структуре. Использование StratifiedKFold (K раз обучить модель на K-1 частях данных и собрать прогнозы на оставшихся частях) приводило к увеличению разрыва между результатами на кросс-валидации (cross-validation) и на текущем рейтинге (public leaderboard). Тем не менее, мы смирились с такой схемой построения ансамбля, так как по мере добавления новых моделей 1-го уровня она продолжала улучшать результат на текущем рейтинге.
Таким образом за три недели до конца соревнования мы довели наш RMSE до 0,44 и все еще были на первом месте с верой в то, что большинство наших трудностей позади и осталось лишь немножко поднажать для финального рывка. И тут началось объединение команд (team merging).
To merge or not to merge?
Зачем нужны объединения?
Объединение команд в первую очередь дает эффект аналогичный добавлению нового уровня к ансамблю. Некая линейная комбинация решений команд до объединения будет лучше любого отдельно взятого решения в силу того, что эти решения сильно отличаются между собой (имеют низкий коэффициент корреляции, например 0.9). В нашем соревновании эту разность во многом обеспечивало отличие в подходах к обработке текста и генерации переменных.
Второй плюс от объединения — это возможность учиться друг у друга, заимствовать какие-то идеи и обмениваться опытом (для чего в принципе и существует Kaggle).
Что произошло?
Мы понимали, что ближе к merger deadline процесс слияний пойдет более интенсивно, но явно недооценили масштаб произошедшего. Если за три недели до конца соревнования в топ10 было всего несколько команд, где было больше 2-х человек, то после того, как все закончилось, в топ10 вовсе не было команд менее трех человек (среднее количество участников в топ10 командах составило 4.6 человек).
Изначально мы не планировали с кем-либо объединяться, несмотря на хорошие шансы попасть в призы: не столько из жадности, сколько из желания понять конкретно свой уровень. Но примерно за неделю до дедлайна объединений нас откинули на 4-5 место, и мы остались чуть ли не единственной командой из 2-х участников в топ10 (не считая единственного на тот момент парня, который был один). Мы еще раз обсудили сложившуюся ситуацию и решили таки попробовать предложить ему объединиться. На его согласие мы особо не рассчитывали: этот парень Chenglong Chen единолично выиграл предыдущее похожее соревнование CrowdFlower Search Relevance, входит в топ-50 рейтинга Kaggle и предпочитает соревноваться один (до нашего соревнования он принял участие примерно в трех десятках соревнований, и только один раз был с кем-то в команде). Мы полагали, что раз он до этих пор продолжает соревноваться один, значит не хочет объединяться с кем-либо. Мы сильно удивились и обрадовались, когда спустя 2 часа в ответ на наше предложение увидели приветливый и лаконичный ответ:
“Sure! Just send me a team merge request :) We will discuss in details later.”
Определенная ирония состоит в следующем: единственным доступным каналом связи для нас была система внутренних сообщений на Kaggle доступная для участников с рейтингом выше 500. Так как до этого мы участвовали всерьез только в одном конкурсе, то оказалось, что рейтинг у одного из нас немного ниже 500, что не позволяет отправлять сообщения. Счастливым совпадением послужило то, что другой из нас потратил несколько часов пару месяцев назад на другой конкурс, где попал в топ90% и этого фантастического результата хватило для того, что бы получить возможность отсылать сообщения. Вполне вероятно, что если бы не этот факт, нашего объединения с Ченглонгом не было бы, как и не было бы этой статьи.
Что это нам дало?
Во-первых, после слияния мы оценили корреляцию наших лучших решений, и она по меркам Kaggle оказалась весьма низкой 0.87. Простое среднее наших двух решений дало нам RMSE 0,435 и вернуло нас на второе место на LB.(примечание 4 на графике прогресса)
Во-вторых, мы познакомились с невероятно талантливым, приятным и скромным парнем, у которого успели многому научиться за столь небольшой промежуток времени.
Открытия на финише.
Времени оставалось всего две недели, а мы находились на расстоянии пяти часовых поясов друг от друга. Поэтому решили, что оптимальная стратегия для нас — это обменяться идеями, переменными и кодом, но сосредоточиться на доделывании собственных решений, которые потом объединим простым взвешиванием (blending). В итоге Ченглонг использовал часть наших переменным и получил решение получше, но зато корреляция между нашими решениями увеличилась до 0.94. Поэтому улучшение нашего общего результата оказалась не таким большим, как нам хотелось бы.
Важность правильной кросс-валидации
Как уже говорилось выше, для кросс-валидации при построении ансамбля мы сначала учили модели на 2/3 данных и проверяли на оставшихся 1/3 данных. Этот подход для данного соревнования нельзя назвать удачным, так как он приводил к все увеличивающемуся разрыву между CV и LB.
Примерно за месяц до завершения соревнования мы написали код, который использовал использовал 1/3 данных для обучения и 2/3 данных для валидации (т.е. использовал разбивку, приближенную к разбивке между train и test). Разрыв между CV и LB значительно уменьшился, однако результаты ухудшились. Поэтому мы продолжили придерживаться первоначальной разбивки.
Забегая наперед, скажем, что в тот момент мы совершили ошибку. Мы получили хорошие результаты при старой стратегии кросс-валидации не потому, что эта стратегия была лучшей (она была хуже), а потому, что ансамбль строился на сотнях моделей, которые были построены в разные периоды при разных подходах к обработке текста и подсчету переменных. Использование таких разных подходов в этом соревновании улучшало решение. Примерно за неделю до конца мы пересчитали все переменные по единому алгоритму (нам нужно было сделать воспроизводимое решение, чтобы претендовать на призовое место) и ужаснулись, что получили хуже результат. Тут нам пригодился код, который мы отбросили ранее. Сотни моделей мы уже не успели бы пересчитать, но даже из восьми моделей получили лучше результат, чем при старом подходе.
Ченглонг же изначально использовал более эффективную разбивку. Дело в том, что часть поисковых запросов была только в train, часть — только в test, а часть — и там, и там. То же самое с продуктами. Ченглонг обратил на это внимание, и сделал похожее распределение в частях для обучения и валидации (рисунок ниже). В итоге, он получил на кросс-валидации результаты, гораздо более приближенные к реальности, чем у нас.
У нас не было времени внедрять эту же кросс-валидацию в наше решение, хотя мы и понимали, что она лучше нашего подхода. Поэтому мы не стали использовать переменные от Ченглонга, чтобы:
а) сохранить, как можно меньшую корреляцию между нашими решениями
б) получить ситуацию в которой наиболее сильное решение посчитано с использованием правильного алгоритма кросс-валидации (для избежания сюрпризов в конце)
Рисунок. Разбивка для кросс-валидации от Ченглонга
Такой ли уж случайный private?
Буквально в последние дни соревнования мы обратили внимание, что в исходных данных есть зависимость между ID записи и оценкой ее релевантности. На протяжении почти всего соревнования мы как и многие другие считали, что это последовательность записей в данных случайна. Мы испытали огромное удивление, увидев, что в зависимости от ID можно четко выделить три разных области, на которых сильно отличается среднее значение релевантности. Еще более удивительным было то, что 2 наших лучших решения абсолютно по-разному вели себя в одной из областей (part 3 на рисунке). До этого результат, который мы видели на LB соответствовал public данным (30% от test), но финальный результат должен был быть подсчитан на остальных 70% test (private). С учетом того, что данные были упорядочены явно неслучайным образом, вопрос состоял в том, является ли разбивка на public и private тоже неслучайной? И какое из наших решений лучше работает на спорной области (part3)?
Для решения последнего вопроса мы склеили наших два лучших решения (взяли первые две части от одного решения, а последнюю часть от другого). Результат на LB оказался таким же! Это значило, что целый огромный кусок данных полностью находится в private, и мы понятия не имеем какое из двух наших решений лучше работает на этой части данных. Так как Kaggle позволяет выбрать в качестве финального два решения, то мы решили попросту выбрать диаметрально разные веса для спорной части на наших решениях, что бы крупно не промахнуться.
Честно говоря, мы ожидали большого потрясения в рейтинге из-за неслучайной разбивки на public/private, но этого не произошло, так как оказалось, что треть всех данных в test была специально “заражена” для того, что бы отбить желание у участников заниматься “ручной обработкой” текста. Эта часть данных никак не оценивалась. Весьма жестокий ход со стороны организаторов.
Честность в ущерб результату
На протяжении конкурса мы считали преступлением оставлять компьютеры без расчетов на ночь и чаще всего ночью считались новые модели для ансамбля. После того, как нам пришлось переписать весь код для получения воспроизводимого решения, у нас осталось порядка 300 разных моделей 1-го уровня, которые мы не могли в точности воспроизвести, не имели на это достаточно времени, и не опубликовали старые словари на форуме за неделю до конца соревнования, как это требовалось в правилах. Тем не менее, добавление этих моделей к ансамблю давало небольшое улучшение на LB (скорее всего и за того, что эти модели относились к разным версиям обработки текста). Мы решили не использовать решение с этими моделями в качестве финального, так как это в нашем понимании противоречило условиям конкурса. Еще мы не исключали неприятных сюрпризов из-за неслучайного распределения данных и считали старую старую стратегию кросс-валидации менее надежной.
Если бы мы все-таки решились на это, то итоговое решение с этими моделями (это было наше лучшее решение в public) принесло бы нам 0,43188 на RMSE и первое место.
Момент истины, выводы и жизнь после победы
Вот и настал момент, когда оба наших финальных решения были готовы, и нам осталось только ждать публикации окончательных итогов на private. К этому моменту ситуация была такой, что мы занимали третье место, с неплохим отрывом от нас шла команда на первом месте, команды с 9-го места и ниже значительно отстали, а результаты команд с 2 по 8 места были достаточно близки, поэтому они вполне могли поменяться местами в итоговом зачете. С учетом ожидаемого потрясения мы понимали, что результат мог быть любым для нас внутри топ восьмерки. В заветные 3 часа ночи, после многократных обновлений страницы мы наконец-то увидели свой результат. 4-ое место...
Что такое победа?
Потрясение было огромным. Второй удар последовал, когда мы увидели, что наше решение со старыми не воспроизводимыми моделями принесло бы нам второе место. Уснуть в ту ночь было нелегко, но ближе к утру пришли мысли, что по факту итоговый разрыв между топ командами ничтожный и факт достижения высот подобного уровня значим сам по себе, не говоря уже о том колоссальном опыте и навыках, которые были получены в процессе. Денежное вознаграждения за 3-е место не было столь крупным, что бы это могло еще больше печалить, поэтому спустя некоторое время на смену грусти пришли приятные ощущения от хорошо проделанной работы. А на следующий день мы узнали, что команду, которая была на первом месте, дисквалифицировали, так как один из ее участников был уличен в использовании нескольких аккаунтов. Это строгое решение организаторов принесло нам итоговое третье место, которого мы в тот момент уже не ждали.
Жизнь после
После конкурса нас настигло моральное и физическое истощение, все-таки мы потратили много времени и сил. Но наивному желанию отдохнуть после его завершения не суждено было сбыться. За два месяца после конкурса мы дополнительно:
— сделали полную документацию по нашему решению
— подготовили интервью
— подготовили презентацию и провели звонок-конференцию с HomeDepot
— подготовили презентацию и выступили для Kaggle комьюнити в Киеве
— написали эту статью
В целом это уже были приятные моменты, но все равно на все это ушло куда больше времени, чем мы ожидали.
Выводы и советы
Итоги этого соревнования можно разбить на две группы. Первая — это то, что мы для себя извлекли из этого соревнования:
1. Результат соревнования в первую очередь зависит от того, сколько сил и времени вы готовы в него инвестировать. Знания и скиллы тоже решают, но их недостаток в большинстве случаев можно и нужно компенсировать избытком настойчивости.
2. Даже само по себе участие в соревнование является полезным и интересным опытом, не говоря уже о том, что это сильно расширяет кругозор и позволяет объективно оценить свой персональный уровень на фоне достойнейших конкурентов со всего мира.
3. Не стоит бояться пробовать! Когда начинаешь заниматься любимым делом, то находится сразу и время на него, и вдохновение. Если data science вам интересен — дерзайте и не пожалеете!
Вторая — это те причины, по которым нам удалось достичь подобного результата:
1. Большое количество инвестированного времени.
2. Тщательная обработка текста.
3. Использование опыта предыдущих победителей и большинства классических подходов, которые применяются в natural language processing.
4. Правильное распределение усилий.
5. Объединение с Ченглонгом.
Убежден, что это не последний наш конкурс на Kaggle, и надеюсь, что мы сможем поделиться будущими достижениями.
Автор: komelianchuk
