18 ноября Telegram запустил соревнование по кластеризации данных: Data Clustering Contest. Нужно было за две недели сделать свой новостной агрегатор. Ограничения, которые были установлены в этом соревновании отпугнули кучу людей, но не меня и моих коллег. Я расскажу от том, каким путём мы прошли, какие выборы сделали и с какими сложностями столкнулись. Решение, которое мы заслали в соревнование обрабатывало 1000 документов за 3,5 секунды, занимало 150 Мб, заняло 6 место на публичном голосовании и 3 место в итоговых результатах. Мы допустили много ошибок, из-за которых не заняли место повыше, большинство из них сейчас исправлены. Весь код и все модели можно найти в репозитории. Все скрипты для обучения моделек перенесены на Colab.

Топ из публичного голосования

Задача

Официальное описание соревнования лежит здесь.

Там 5 подзадач:

• определение языка статьи
• определение, является ли статья новостью
• определение категории новости из списка из 7 категорий
• кластеризация новостей и выбор заголовочного документа для кластера
• ранжирование кластеров, то есть выбор, на какую позицию какой кластер поставить

Подзадачи конкурса в порядке выполнения

Это не слишком далеко от того, как работают реальные новостные агрегаторы. Из этого неясно, как именно будут работать итоговое решение в Телеграме: раз в минуту/час/день, будет ли оно каждый раз заново запускать все этапы. Также было неясно, в каком формате будут запускаться эти 5 подзадач: по отдельности, все вместе для одного языка, все вместе для разных языков. Про публичное голосование тоже не было ничего известно во время самого соревнования.

С первой задачей всё более или менее понятно. А вот дальше начинаются сложности, потому что ни готовой разметки, ни инструкции ни на одну из задач нет. То есть, определение “новости” неизвестно, границы категорий не заданы, гранулярность кластеризации не описана, критериев качества ранжирования нет. Часть из этого мы воссоздали сами, но на часть у нас не хватило времени.

Ограничения:

• максимальный вес архива с решением: 200 Мб (а позже 1.5 Гб)
• минимум 1000 документов в минуту
• 2 недели со старта до конца соревнования
• запускается через бинарник на Debian GNU/Linux 10.1, можно устанавливать любые пакеты для этой конфигурации

Ограничение на скорость довольно слабое, 1000 документов в минуту можно получить практически для любой системы, кроме совсем уж тяжёлых и неповоротливых моделей. Главным тут является ограничение на вес архива: изначальные 200 Мб отсекали многие свежие наработки в области обработки естественных языков, в том числе почти любые предобученные векторы (готовые word2vec, fasttext, GloVe, для русского тут) и предобученные ULMFiT/ELMo/BERT. Это не означает, что их вообще нельзя использовать. Их нужно было бы учить с нуля с урезанным числом параметров или дистиллировать текущие модели, что за 2 недели та ещё задачка.

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

Выбор стека

Начнём с языка. В теории, можно было бы всё написать на Python (и многие так в итоге и сделали). Нас остановили ограничение по скорости и ограничение на запуск из бинарника. Ни одно из них в итоге бы не помешало, но мы и не знали, какой объём данных будет скармливаться алгоритму. Я предполагаю, что решения на Питоне не смогли бы корректно обработать все новости за месяц разом.

Я знаю, что некоторые писали на Go, и это, вероятно, хороший выбор. Мы же люди привычные к C++, к тому же многие библиотеки для машинного обучения вроде как имеют версии под него, поэтому мы остановились на нём. При этом никто не мешает обучать модели на Питоне, что мы тоже сделали. Использовали C++11, выше не брали из-за зависимостей.

C точки зрения NLP, мы решили застрять в 2016 году и ограничиться FastText’ом. Могли бы застрять и ещё раньше, используя только TF-IDF, но это, как ни парадоксально, было бы даже сложнее и, скорее всего, не так эффективно. FastText — это такой word2vec с добавкой из буквенных n-грамм, которые позволяют ему получать осмысленные векторы для слов не из словаря. Предобученная ELMo для русского весит 197 Мб, предобученный BERT — 632 Мб, поэтому это неподходящие варианты для этого соревнования (по крайней мере так было в начале). Кроме того, FastText доступен под C++ и без проблем статически линкуется.

По-хорошему нам бы нужен был хороший токенизатор. Но лёгких решений на момент соревнования как будто бы не было, в итоге мы просто делили по пробелам (что неправильно, не делайте так!). Уже после контеста мы нашли токенизатор из OpenNMT, и сейчас его используем. Его главная особенность в том, что он поддерживает и C++, и Python, а значит не будет никакой разницы между обучением и применением. А ещё он достаточно быстрый.

Кроме того, нам нужны были алгоритмы кластеризации, в идеале агломеративная кластеризация или DBSCAN, потому что с ними мы уже работали. DBSCAN нашёлся в MLPack, MLPack нашёлся как пакет для Debian’а. Параллельно с этим мы написали свою агломеративную кластеризацию. В итоге для того, чтобы не затаскивать такую большую зависимость, от DBSCAN’а решили отказаться. Но в целом с MLPack был не самый плохой опыт.

У нас была мысль попробовать использовать какой-нибудь фреймворк для глубокого обучения: TensorFlow, Torch, MXNet. “TensorFlow написан на C++, это будет легко” — думали мы. Во-первых, это легко до тех пор, пока вы не попытаетесь его статически влинковать. Во-вторых, итоговый бинарник банально не влезет в 200 Мб. Есть ещё Tensorflow Lite, но до него уже руки не дошли. Примерно такие же разочарования ждали нас со всеми фреймворками.

Поэтому мы решили делать проще и перемножать матрицы самостоятельно. Естественно, мы не настолько сумасшедшие люди, чтобы перемножать их полностью самостоятельно. Тут мы большого сравнения библиотек не делали, взяли Eigen, который был на слуху и делал свою работу без нареканий. Для обучения использовали Keras, потому что у нас простая модель, без кастомных слоёв и лоссов, иначе бы использовали Torch (его и использовали в более поздних экспериментах). Плюс тут сыграли личные предпочтения одного из участников команды.

В итоге вышло так:

• Применение: C++, FastText, OpenNMTTokenzer, Eigen
• Обучение: Python, FastText, OpenNMTTokenzer, Keras

Для разметки использовали Яндекс.Толоку.

Решение

Для определения языка использовали готовую модель от команды FastText’а почти без изменений.

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

Для определения категорий собрали разметку в Толоке. Собирали обучающую и тестовую выборку. Для этого написали инструкцию, завели обучение, экзамен и ханипоты. Обучающая выборка собиралась с перекрытием 3 и согласованностью 2/3, тестовая с перекрытием 5 и согласованностью 4/5. Скрипты для агрегации умеют считать согласованность толокеров, она вполне приличная. К примерам на английском добавляли машинный перевод на русский. Потратили 60$ на всё. Данных получилось не очень много, для русского языка было 327 примеров в тестовой разметке и 1176 примеров в обучающей, категории были не сбалансированы. Для хорошей разметки стоило бы потратить в 3-4 раза больше денег.

Кроме нашей разметки, использовали категории из внешних датасетов. Для русского брали категории и теги Ленты, для английского BBC и News categories. При этом категории из этих внешних датасетов нужно было отобразить в категории соревнования.

Посчитав размеры на коленке, решили сделать свои предобученные FastText векторы. Предобучали на части данных из соревнования и на открытых новостных корпусах: Лента и РИА для русского; BBC, All the news, News categories для английского. Так сделано, чтобы словарь и сама модель не были завязаны на конкретный временной период.

На разметке обучили классификатор через supervised режим FastText’а с использованием предобученных векторов и заданного размера классификатора (опции семейства autotune). Supervised режим — это просто линейная модель над усреднением всех векторов слов, можно было бы сделать сложнее, и в этом месте получить качество чуть лучше.

Данные для обучения классификаторов категорий

Для хорошей кластеризации принципиально нужны 2 вещи: хорошие векторы и хороший алгоритм. В качестве векторов сначала пробовали просто усреднение векторов всех слов текста, получалось не очень. В итоге учили линейную сиамскую сеть над усреднением (а также покомпонентным минимумом и максимумом) векторов слов на задаче предсказания следующего кусочка текста. То есть брали доступные тексты, делили их пополам, над каждой половинкой делали линейный слой с связанными весами, делали скалярное произведение получившихся векторов, а потом домножали на циферку и прогоняли через сигмоиду. Использовали логлосс, в качестве единиц брали половинки одного текста. А в качестве ноликов левую половинку от одного текста, а правую — от хронологически предшествующего текста того же источника (такие вот hard-negative примеры). Вот таким способом получились уже более адекватные (на глаз) векторы. Ещё адекватнее было бы делать более сложную архитектуру половинок и использовать triplet loss. Модель строили и учили на Keras’е, но ничего не мешало это делать и на Torch’е. Веса линейного слоя экспортировали в применялку через обычный текстовый файлик.

Модель обучения векторов для кластеризации

Ежели вы спросите, а как бы мы это делали, если бы ограничений не было, так тут всё просто. Тут применимы все модели, которые обычно используют для определения парафраз, например дообученный BERT. Это бы работало, будь у нас разметка. А вот в наивном unsupervised варианте я бы ставил на ELMo. Более того, с ELMo у нас есть эксперимент.

В качестве алгоритма взяли SLINK: агломеративную кластеризацию за O(n^2) и вычислением расстояния как минимума между точками двух кластеров. У такого способа есть свои недостатки, самый главный из них — подклейка по транзитивности: первая точка склеивается со второй, вторая с третей, а в итоге первая и третья в одном кластере, хотя сами по себе далеко друг от друга.

Агломеративная кластеризация. Кого клеить первым выбираем по расстоянию между векторами.

При этом O(n^2) для всех документов за месяц — это слишком долго. Есть несколько вариантов решения этой проблемы, нам известны два: отбор кандидатов и склейка. Мы пошли вторым путём, отсортировали по времени весь массив входных документов и разбили на чанки из 10000 документов с перехлёстом в 2000 документов. Кластеризовали чанки по отдельности, по перехлёсту склеивали. Это работает только потому, что вряд ли далеко отстоящие по времени документы принадлежат одному кластеру.

Заголовочный документ кластера выбирали по 3 факторам: свежести, похожести на остальные документы кластера, весу источника. Свежесть — функция от возраста кластера, отмасштабированная сигмоида в нашем случае. Возраст кластера считаем от 99 процентиля дат всех документов. Похожесть считаем через те же векторы, что и в кластеризации. Вес источника считаем как PageRank по ссылкам, которые нашли в тексте.

Ранжировали кластера тоже по 3 факторам: свежести, весу источника, размеру кластера.

Ошибки

1. Опечатались в названии одной из категорий.
2. Неправильно выбрали процентиль для “текущего” момента времени, из-за чего на первом английском тестовом датасете вперёд выходили документы из “будущего”.
3. Плохо обучили категории для английского, из-за чего была низка полнота для некоторых категорий, в частности для науки.
4. Не парсили вложенные теги, из-за чего тексты некоторых документов были неполными.
5. При обучении линейного преобразования для векторов кластеризации мы изначально использовали только тексты из датасетов соревнования, из-за чего модель хуже обобщала, и много кластеров распадалось.
6. Закрутили в точность порог кластеризации
7. В некоторых местах некорректно обращались с числами с плавающей запятой, из-за чего немного разъехалось ранжирование документов внутри кластера и ранжирование кластеров.
8. Использовали std::sort вместо std::stable_sort, из-за чего получались невоспроизводимые результаты.
9. Не сделали нормальную токенизацию сразу, из-за чего потеряли пару процентов точности в категоризации и немного в качестве кластеризации.
10. Не написали тесты вовремя, из-за чего произошла часть из описанных выше ошибок.

Итоги

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

Чего же не хватает этой штуке до полноценного новостного агрегатора?

Во-первых, rss-качалки или любого другого способа получить документы на вход. Telegram в этом плане очень сильно считерил — вероятно всё, что проходит через его Instant View, сохраняется у него же на серверах. Данные соревнования получены именно таким образом. Вопрос о правовом статусе таких действий остаётся открытым.

Во-вторых, для ранжирования не хватает сигнала от пользователей. Хоть какого-нибудь: кликов, просмотров, лайков, разметки на интересность или важность. Нельзя нормально отранжировать новости только по их содержанию.

К тому же, очень много мы до сих пор не сделали и в плане машинного обучения, это всё есть в README к репозиторию.

На текущую версию можно посмотреть вот тут, на версию с контеста вот тут.