Задача от Kaggle - Quora Question Pairs

Задача от Kaggle - Quora Question Pairs

-       Что, опять про Кагл?

-       Эээ...Да. опять.

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

Теория конечно нужна, но полностью погрузиться в тему можно только на практике, решая вполне конкретные задачи. А в случае каких-то вопросов, коллективный разум сообщества всегда придет на помощь, подскажет и даже покажет. Решая здесь задачи, и новичок, и профессионал уровня «grandmaster» могут, как говорится, “оторваться по полной программе”.

Заглянув как-то на сайт Кагла, я увидел, что начался конкурс по теме NLP (Natural Language Processing).  Имея уже некоторый опыт в таких задачах и располагая свободным временем, я тоже решил  оторваться поучаствовать. Итак, про саму задачу.

Какой у вас вопрос?

Есть такая компания Quora. Это онлайн-сервис вопросов-ответов, который посещает более 100 миллионов человек каждый месяц, поэтому неудивительно, что многие люди задают одинаковые вопросы. Несколько вопросов с похожим смыслом неприятны по двум причинам. Во-первых, вы будете искать свой ответ дольше, во-вторых, эксперты будут тратить лишнее время, отвечая на дубли.

В задаче нужно решить проблему обработки естественного языка, чтобы определить, являются ли пары вопросов дублирующими или нет. Это упростит поиск ответов на вопросы, и в целом, поможет улучшить работу сервисов Quora. Цель этого конкурса – предсказать, какая из представленных пар вопросов содержит два вопроса с одинаковым значением. Разметкой целевой переменной (дубль - не дубль) занималась группа из нескольких экспертов. Однако мнения экспертов  по своей природе субъективны, и истинный смысл предложений иногда может трактоваться по-разному. Другими словами, разметка, выполненная человеком, является “шумным” процессом. В результате, значения целевой переменной в этом наборе данных должны восприниматься как “информационные”, но они не на 100% точны и могут содержать ошибку.

В этом конкурсе не обошлось без сюрпризов от организаторов. В качестве меры по борьбе с неспортивным поведением (читай - подгонкой данных), Кагл дополнил тестовый датасет синтетическими парами вопросов. Этих вопросов не было в данных, предоставленных Quora, и они впоследствии не учитывались при подсчете конечного результата. В них рандомным образом были заменены одно или несколько слов. Все вопросы в тренировочном датасете являлись настоящими примерами из Quora. Ну что же, посмотрим на сами данные.

Исходные данные

В тренировочном датасете содержалось 404290 пар вопросов.

В тестовом  датасете пар вопросов было 2345796 (позже было установлено, что реальных пар вопросов в нем было около 500 тысяч)

Итак, структура данных до неприличия проста:

●      id - идентификатор пар вопросов.

●      qid1, qid2 - идентификаторы вопросов (доступен только в train.csv)

●      question1, question2 - собственно сами вопросы

●      is_duplicate - целевая переменная, 1 дубликат, 0 не дубликат.

В качестве метрики предлагалось использовать log_loss

Кусок данных из трейна выглядит так:

Из таблицы видно, что смысл может быть одинаковым у совершенно разных по структуре вопросов, и наоборот, незначительные изменения одного вопроса вдруг полностью меняют его смысл. И это типичная проблема при решении таких “языковых” задач. Т.е. методы из разряда “щас быстро посчитаем одинаковые слова в вопросах”, здесь, как правило, не работают. Хотя, конечно, бывают исключения. Но их немного.

Еще одна очень важная особенность данных, это то, что один и тот же вопрос может быть в паре у нескольких других. Что это означает? Да наверное ничего, так мне подумалось в самом начале. Однако через некоторое время, появились смутные подозрения, что это все же можно и нужно как-то использовать. Мозг рисовал в воображении странные ажурные конструкции, где вопросы это некие шарики разного размера, а между шарами натянуты нити.

И рисовал он как-то так:

Да-да, вы правы, это похоже на граф.

Позже эти абстракции полностью подтвердились и оформились в виде конкретных идей, и не только у меня одного. Эта особенность данных некоторыми была отнесена в разряд data leak, но я предпочитаю более мягкое определение -  анализ с использованием структуры данных. В дальнейшем, как это нередко бывает на Кагле, данный конкурс превратился из задачи NLP в задачу поиска других закономерностей (уязвимостей) в структуре данных. Стандартные методы анализа текстов (TF-IDF, Word2vec и т.д.), конечно, использовались и работали, но фичи, использующие структуру данных, настолько сильно улучшали результат, что возникал вопрос - а где тут задача по NLP. Как бы то ни было, задача есть задача, и надо ее решать.

Решение

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

1. Мягкий - удалялись некоторые знаки препинания и некоторые одиночные символы. Регистр сохранялся.
2. Жесткий - удалялись все знаки препинания и одиночные символы. Все слова преобразовывались в нижний регистр.
3. Стемминг - удалялись все знаки препинания и одиночные символы. Все слова преобразовывались в нижний регистр. К словам применялся алгоритм стемминга.
4. Лемматизация - удалялись все знаки препинания и одиночные символы. Все слова преобразовывались в нижний регистр. Слова лемматизировались.

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

Фичи

Генерация признаков для обучения моделей осуществлялась следующими модулями:

Классические методы

1. length - количественные характеристики вопросов. Сколько слов, сколько символов, сколько чисел и т.д.
2. counts - количество совпадений слов из первого вопроса со словами из второго вопроса.
3. distance - расстояние между вопросами. Использовались  алгоритмы Levenshtein, Jellyfish, SequenceMatcher.
4. fuzzy - метрики нечеткого сравнения из пакета fuzzywuzzy
5. LSA - Считаем матрицу TF-IDF [вопрос:слово]. Используем косинус расстояния между вопросами и первые 100 главных компонент SVD разложения матрицы.
6. word2vec - строим модель на всем корпусе вопросов. Используем вектора вопросов и расстояние между ними.
7. glove - метрики полученные из проекции вопросов в пространство модели glove.42B.300d. Использовались различные метрики расстояния и статистические характеристики векторов модели (моменты 2, 3, 4 порядка)

Рекуррентные сети

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

Краткие пояснения:

●      Слои Embedding отвечают за преобразование слов в вектора некоторого пространства. Используется та же модель glove.42B.300d.

●      Слои Representation состоят из 1D сверточного слоя и следующего за ним слоя Bidirectional LSTM.

●      Выходной слой Dense формирует из двух потоков признаков вероятность схожести вопросов.

По сравнению с другими моделями, рекуррентная модель показывает довольно средние результаты, но используя ее выход на втором уровне обучения, она прилично помогает. Некоторые команды использовали более продвинутую архитектуру - Siamese Networks with Attention. Если очень просто, то ее отличие в том, что применяется механизм взвешивания слов. Таким образом, важные с точки зрения смысла слова получают больший вес в дальнейших вычислениях вероятности схожести, и сеть работает значительно лучше.

Методы, использующие структуру данных

Далее пойдет описание методов, не относящихся напрямую к NLP. Конечно, эти методы характерны не только для этой конкретной задачи, но их применение в реальных задачах затруднено или вообще невозможно.

Матрица смежности

Этот метод я подсмотрел у Станислава Семенова, когда он рассказывал о решении конкурса Kaggle Avito Duplicate Ads Detection. Он и Дмитрий Цыбулевский тогда заняли первое место.

Давайте построим список уникальных вопросов. Возьмем все вопросы, из трейна и теста, объединим их и удалим дубликаты. Мы получим список уникальных вопросов длиной N. В нашем случае из 5500172 вопросов, 4789032 являются уникальными. Следующий шаг - строим матрицу [N:N] и заполняем ее нулями.

Далее, берем все пары вопросов и, используя список уникальных вопросов как индекс, заполняем значения матрицы, соответствующих двум вопросам из пары единицами.

Что же мы получили? Мы получили матричное представление графа, который изображен на первой картинке. Все связи между вопросами в этой очень разреженной матрице помечены единицей. Дальше можно использовать различные метрики расстояний в этой матрице как признаки. Я поступил по-другому, сделал SVD преобразование матрицы и взял 50 главных компонент.

Частотный анализ

Считаем частоту вопросов, т.е. сколько раз вопрос встречается и в трейне, и в тесте. Этот признак давал огромный прирост в результате, поскольку выборка вопросов от Quora, видимо, как-то зависела от этой частоты.

Общие ребра графа

Звучит как-то двусмысленно. На самом деле, имеется в виду следующее.

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

Примерно вот так:

Таким образом, мы получаем некую меру связанности вопросов. 

Свойство транзитивности

Идея проста и достаточно очевидна. Допустим, у нас есть три вопроса A, B, C. Тогда если A == B и B == C, то А == С. Разумеется, А будет похож на С с какой-то вероятностью. В той или иной форме, эта идея присутствовала у всех команд, которые были в топе лидерборда.

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

Законы физики

Иногда воображение и знание элементарных законов физики может помочь в решении таких совсем не физических задач. Давайте представим себе, что вопросы это некие частицы, случайно расположенные в пространстве. И эти частицы взаимодействуют таким образом, что если частицы-вопросы похожи, то они притягиваются, а если не похожи, то — отталкиваются. Это может быть похоже на гравитационное или электростатическое взаимодействие. Спустя некоторое время, под влиянием этого взаимодействия рой частиц принимает какой-то вполне упорядоченный вид, и в качестве признаков можно использовать расстояние между частицами и их пространственные координаты.

Итак, фичи вроде есть. Давайте что-нибудь предскажем.

Модели

Как уже было сказано выше, несколько моделей было построено на рекуррентных сетях, но они использовались, в основном, на втором уровне обучения. Для построения моделей на деревьях решений использовались, в основном, бустеры LightGBM и совсем немного XGBoost. Качество прогноза у них было очень похоже, но LightGBM мог использовать GPU и работал раза в три быстрее. Для валидации данные разбивались на 5 фолдов. Ближе к финалу конкурса количество признаков было около 800, и модель обучалась примерно 6-7 часов. К слову сказать, это количество признаков было предельным для моего компьютера с 64Gb.

Постобработка

Где-то в середине конкурса, на его форуме появилось несколько постов, где указывалось на то, что распределение таргета в трейне и в тесте разное.

Причем, сильно разное. Скорее всего, оно изменилось из-за того, что пары вопросов теста были разбавлены синтетическими парами вопросов. Путем нехитрых экспериментов было установлено, что в трейне отношение дубль/недубль было примерно 0.37, а в тесте 0.165. Там же, на форуме, скоро появилась реализация необходимой функции калибровки. Лучшая одиночная модель без калибровки на лидерборде показывала 0.20456, а после калибровки — уже 0.15959.

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

Команда

Когда у меня появилось ощущение, что запас идей подходит к концу, мне в личку написали Александр Рыжков и Антон Вахрушев, с предложением присоединиться к их команде. Я уже работал с Александром перед этим, над задачей Grupo Bimbo Inventory Demand (наша команда тогда заняла 2 место). Поэтому решение было однозначным. По позициям они были далеко впереди меня, имели выделенный сервер на Амазоне и успели применить следующие подходы:

1. Несколько вариантов Factorization Machines
2. Больше графовых фич: PageRank, субграфы, общие соседи соседей и т.д.
3. Стекинг  

После объединения получили результат на лидерборде 0.13796. Свежие мозги и идеи всегда идут на пользу команде. Дальнейшее улучшение достигалось полировкой параметров моделей, перетряхиванием датасета на предмет мешающих фич. Также нужно было исключить из наших датасетов идентичные фичи, поскольку их повторение, как правило, ухудшает результат моделирования.

Кроме того, выяснилось, что некоторые графовые фичи существенно оверфитят модель. В связи с этим, Антон предложил следующую схему по фильтрации таких фич. Мы вводим новую целевую переменную, значение которой равно нулю в трейне и единице в тесте. Далее строим простую XGBoost модель и, используя весь наш датасет, пытаемся  предсказать наш новый таргет. После этого внимательно смотрим на список feature importance модели. Те признаки, которые оказались вверху списка, потенциально могут приводить к переобучению модели, поскольку они хорошо разделяют трейн и тест.

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

В процессе поиска идей, я предпринял попытку реализовать архитектуру сети BiMPM. На тот момент это было state of art решение в NLP. Эта модель искала связи не только между словарным представлением  двух вопросов, но и между символьным представлением. Идея была замечательная, но в процессе реализации, я, видимо, где-то допустил ошибку и при обучении не получил вменяемого результата. Искать ошибку и переучивать сеть просто не было времени. К тому же она неприлично долго обучалась. На обучение 5 фолдов, уходило больше 18 часов на пяти арендованных амазоновских инстансах с GPU.

Идеи, которые не дали результата:

1. Брали базу SNLI. Делали из нее все наши фичи и обучали модель. Далее, подавали на вход SNLI модели фичи из датасета Quora. Выход SNLI модели использовали как новые фичи .
2. Брали матрицу от преобразования TF-IDF и считали корреляционную матрицу по вопросам. Поскольку всего уникальных вопросов было почти 5 миллионов, то учитывали только коэффициенты больше 0.8.
3. LSA по общей части вопросов, по разнице вопросов.
4. Пытались найти причины для использования значений индексов вопросов qid1 и qid2.
5. Была проверка гипотезы, что индексы пар вопросов, были как-то связаны с датой их появления на сайте Quora.

Вполне мог что-то забыть.

Когда до окончания конкурса осталось дней 8-9, мы решили для усиления пригласить в команду кого-нибудь еще.

Первым на предложение  откликнулся Mario Filho.

Он предложил несколько важных вещей и изменений.

1. Другая разбивка на фолды. Чтобы уменьшить переобучение, вопросы в фолдах должны быть как можно слабее связаны.
2. Агрегация уже существующих фич по id вопроса.
3. Добавил несколько других моделей в стек. 

Вторым откликнулся активный товарищ из китая lystdo. Он был Ph.D и имел доступ к университетскому компьютеру с шестью GTX 1080. Накрутил кучу рекуррентных моделей и рвался в бой. Также он предложил свою схему багинг-стекинга для генерации сабмитов. И весь остаток конкурса мы все занимались только генерацией данных для него, а он агрегировал их в свою модель. В таком режиме мы и подошли к финалу конкурса.

Наша команда заняла 6 место и имела следующие результаты:

public  LB: 0.11532                       private LB: 0.11887

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

Вот, пожалуй, и все.

Спасибо, что дочитали до конца.