Простой и быстрый подход к категоризации и кластеризации новостей

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

Несмотря на то, что конкурс завершился 2 декабря 2019 года, организаторы объявили результаты неделю назад. Наша команда Mindful Squirrel занимает 3-е место в итоговой таблице лидеров. В этом посте мы даем краткий обзор нашего подхода и обсуждаем основные проблемы, с которыми мы столкнулись. Полное решение доступно на GitHub. Все учебные сценарии доступны в Colab.

Обзор задачи

Конкурс включал пять подзадач, которые, как предполагалось, должны были выполняться последовательно на необработанных данных:

  1. Идентификация языка (нужны были только английский и русский тексты)
  2. Фильтрация новостей из других текстов
  3. Разделение на 7 тем
  4. Кластеризация статей, связанных с одним и тем же событием, в потоки
  5. Ранжирование тем в каждой теме

Шаг определения языка казался очень понятным, в то время как другие задачи вызвали кучу вопросов. Строгое определение «новости» не дано; критерии темы не были четко определены; также отсутствовали критерии гранулярности кластеризации и ранжирования.

Правила конкурса требовали, чтобы финальная отправка выполнялась локально на машине под Debian с 8 ядрами и 16 ГБ ОЗУ без использования сети. Более того, приложение должно было обрабатывать любую партию из 1000 статей в течение 60 секунд. Первая версия ограничений также включала штраф за решения, превышающие 200 МБ дискового пространства.

Решение

Эти ограничения сильно повлияли на диапазон применяемых инструментов и алгоритмов. Первой идеей было перенимать модели SOTA, такие как ELMo или BERT. Однако они слишком велики, чтобы соответствовать требованиям. Поэтому мы широко использовали библиотеку fastText. Это библиотека для изучения встраивания слов и обучения моделям классификации текста, созданная компанией Facebook AI Research в 2016 году. Весь код отправки был написан на C ++, а единственная сложная модель была обучена на Python с помощью Keras.

Определение языка

Решение этой задачи было незамысловатым. Мы использовали предварительно обученную модель, предоставленную командой fastText.

Фильтрация и классификация тем

Мы объединили эти две задачи в одну задачу классификации на несколько классов. Поскольку любой контролируемый классификатор требует некоторого количества обучающих данных, мы использовали Яндекс.Толоку для разметки части входных данных. Толока - российская краудсорсинговая площадка, как и Amazon Mechanical Turk. Мы потратили 60 $ на всю маркировку как для русского, так и для английского языков. Мы использовали машинный перевод на русский язык для английских текстов, чтобы облегчить работу русскоговорящим сотрудникам.

Также мы расширили базу данных общедоступными данными из новостной базы Лента.ру для русского языка и данными BBC и HuffPost для английского.

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

Кластеризация новостей

Две важные вещи для кластеризации новостей - это встраивание форматированного текста и надежный алгоритм кластеризации.

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

Модель по-прежнему была максимально простой и имела только одну обучаемую матрицу. Мы не использовали никакие нейронные сети в реальном приложении C ++, только библиотеку Eigen для умножения матриц.

Мы использовали агломеративную кластеризацию SLINK. У алгоритма есть недостатки, и самый главный из них - транзитивное связывание. Первая точка может быть связана со второй, вторая с третьей, и в результате первая и третья точки попадают в один кластер, хотя могут находиться далеко друг от друга.

Временная сложность SLINK, равная O (n²), не позволяла нам кластеризовать все документы сразу. Для решения этой проблемы мы предположили, что далекие по времени документы не должны принадлежать к одному кластеру. Это предположение позволило нам разделить всю временную шкалу на блоки по 10 000 документов с перекрытием в 2 000 элементов. Затем мы применили кластеризацию внутри каждого фрагмента и, наконец, связали последовательные фрагменты через перекрывающиеся документы.

Именование и рейтинг темы

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

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

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

Алгоритм PageRank по ссылкам внутри документов позволил нам оценить важность источника.

Свежесть, вес источника и размер кластера легли в основу ранжирования потоков. 99-й процентиль всех дат публикации был выбран в качестве «текущего момента» для всего набора данных из-за возможных выбросов. Возраст нити был рассчитан от этого «текущего момента».

Заключение

Самой важной частью задачи было создание системы, отвечающей строгим аппаратным ограничениям. Эти ограничения, а также короткая продолжительность конкурса заставили нас полагаться на простые алгоритмы машинного обучения (такие как fastText) вместо сложных моделей SOTA. У нас не было достаточно времени, чтобы провести все эксперименты, которые мы хотели, или довести до окончательного решения. Еще есть возможности для улучшения, хотя мы внесли некоторые изменения после окончания конкурса. Мы также создали рабочий процесс CI, который сопоставляет вывод каждой версии кода с каноническими результатами и публикует верхнюю часть страниц GitHub.

Напоследок хотим поблагодарить организаторов конкурса за интересное задание. Это определенно была огромная проблема.

Ссылки:

  1. Репозиторий GitHub: Решение для конкурса Telegram Data Clustering от Mindful Squirrel
  2. Эта статья на русском языке: Новостной агрегатор за две недели
  3. Еще одна статья о конкурсе Data Clustering: Построение агрегатора новостей с нуля: фильтрация новостей, классификация, группировка по тредам и ранжирование