Почти год назад Илон Маск предложил сделать алгоритм рекомендаций Twitter общедоступным. Недавно компания выложила исходный код своего алгоритма на GitHub.

В статье — перевод их блог‑поста с описанием работы алгоритма рекомендаций. Он подойдет:

• любым желающим узнать, как алгоритмы выбирают, что вам показать в ленте,

• Data Scientist‑ам и ML‑инженерам, как уникальный источник инсайтов о работе большой рекомендательной системы.

Twitter стремится показать вам наиболее релевантное из того, что происходит в мире в данный момент. Для этого нужен алгоритм рекомендаций, который сможет извлечь из 500 миллионов твитов ежедневно те лучшие, которые в итоге будут показаны в разделе «Для вас» (For You). В этой статье мы расскажем, как алгоритм выбирает твиты для вашей ленты.

Как мы выбираем твиты?

Основой рекомендаций Twitter является набор алгоритмов и функций, которые извлекают скрытую информацию из твитов, пользователей и данных о взаимодействиях. Эти модели стремятся ответить на важные вопросы, например, «Какова вероятность того, что вы будете взаимодействовать с этим пользователем в будущем?» или «Какие сообщества выделяются в Twitter и какие твиты в них популярны?» Точные ответы на эти вопросы позволяют делать более релевантные рекомендации.

Система рекомендаций состоит из трех основных этапов:

1. Отбор кандидатов — извлечение лучших твитов из разных источников рекомендаций.

2. Ранжирование этих твитов с помощью модели машинного обучения.

3. Применение эвристик и фильтров, например, фильтрация твитов от пользователей, которых вы заблокировали, NSFW‑контента и твитов, которые вы уже видели.

Сервис, который отвечает за создание и предоставление ленты For You, называется Home Mixer. Home Mixer создан на основе Product Mixer, нашей специальной платформы на Scala, которая облегчает создание ленты контента. Этот сервис связывает различные источники кандидатов, функции скоринга, эвристики и фильтры.

Диаграмма ниже иллюстрирует основные компоненты, используемые для создания ленты:

Рассмотрим ключевые элементы этой системы примерно в том порядке, в котором они вызываются во время одного запроса на показ ленты. Начинем с получения кандидатов из Источников кандидатов.

Источники кандидатов

У Twitter есть несколько источников кандидатов для получения свежих и актуальных твитов. Через эти источники мы пытаемся извлечь лучшие 1500 твитов из сотен миллионов для каждого запроса. Мы находим кандидатов от пользователей, на которых вы подписаны (In‑Network), и от пользователей, на которых вы не подписаны (Out‑of‑Network). Лента For You состоит в среднем на 50% из твитов In‑Network и на 50% из твитов Out‑of‑Network, хотя этот процент может варьироваться от пользователя к пользователю.

Источник In-Network

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

Самый важный компонент в ранжировании твитов In-Network - это Real Graph. Real Graph - это модель, которая предсказывает вероятность взаимодействия между двумя пользователями. Чем выше показатель Real Graph между вами и автором твита, тем больше мы будем включать его твиты.

Источник In-Network был недавно переработан. Мы перестали использовать Fanout Service - 12-летний сервис, который предоставлял твиты из кэша для каждого пользователя. Также мы перерабатываем модель ранжирования логистической регрессии, которая последний раз была обновлена и обучена несколько лет назад!

Источники Out-of-Network

Нахождение релевантных твитов вне сети пользователя - более сложная проблема: Как мы можем определить, будут ли определенные твиты для вас актуальны, если вы не подписаны на автора? Twitter использует два подхода для решения этой проблемы.

1. Social Graph

Первый подход анализирует лайки людей, на которых вы подписаны, или тех, кто имеет похожие на вас интересы.

Мы проходим по графу взаимодействий и подписок, чтобы ответить на следующие вопросы:

• Какие твиты недавно лайкнули люди, на которых я подписан?

• Кто лайкает те же твиты, что я, и что еще они лайкнули недавно?

Мы создаем кандидатов на основе ответов на эти вопросы и ранжируем полученные твиты, используя модель логистической регрессии. Такие обходы графа критичны для наших рекомендаций. Для этого мы разработали GraphJet, движок обработки графов, который в реальном времени поддерживает граф взаимодействий между пользователями и твитами. Хотя этот подход оказался полезным (на него приходится около 15% твитов ленты домашней страницы), подходы, основанные на пространстве эмбеддингов, дают больший вклад.

2. Пространства эмбеддингов (Embedding Spaces)

Подходы на основе эбеддингов хотят получить ответ на более общий вопрос о схожести контента: Какие твиты и пользователи похожи на мои интересы?

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

Одним из наиболее полезных пространств эмбеддингов в Twitter являются SimClusters. SimClusters находят сообщества вокруг влиятельных пользователей (инфлюенсеров), используя собственный алгоритм матричного разложения. Существует 145 тыс. сообществ, которые обновляются каждые три недели. Пользователи и твиты могут принадлежать нескольким сообществам. Сообщества имеют размер от нескольких тысяч пользователей для отдельных групп друзей до сотен миллионов пользователей для новостей или поп-культуры. Вот некоторые из самых больших сообществ:

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

Ранжирование

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

Ранжирование достигается с помощью нейронной сети с ~48 миллионами параметров, которая непрерывно обучается на взаимодействии с твитами. Она оптимизирует положительную обратную связь (например, лайки, ретвиты и ответы). Этот механизм ранжирования учитывает тысячи признаков и выдает десять меток. Таким образом, каждый твит получает составную оценку, где каждая метка показывает вероятность взаимодействия. Мы ранжируем твиты на основе этих оценок.

Эвристики, фильтры и дополнительные функции

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

• Фильтрация по видимости: фильтрация твитов на основе их содержания и ваших предпочтений. Например, убрать твиты от аккаунтов, которые вы заблокировали.

• Разнообразие авторов: избегание длинных последовательностей твитов от одного автора.

• Баланс контента: обеспечение баланса In-Network и Out-of-Network твитов.

• Учет негативного фидбека: снижение скора твитов, близких к тем, где вы дали отрицательную обратную связь.

• Подтверждение от окружения: исключение твитов пользователей более 2-го уровня связи. То есть, гарантируется, что среди ваших подписок есть пользователь, который взаимодействовал с данным твитом или подписан на его автора.

• Переписка: добавление оригинального твита к ответу.

• Отредактированные твиты: определение твитов, устаревших сейчас на устройстве, и замена их отредактированными версиями.

Обогащение и передача данных

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

Вышеописанный пайплайн работает примерно 5 миллиардов раз в день и выполняется в среднем за 1,5 секунды. При этом один запуск пайплайна требует 220 секунд времени CPU — почти в 150 раз больше, чем задержка, которую вы видите в приложении.

Основная цель в рамках проекта с открытым исходным кодом — полностью прозрачно предоставить вам, нашим пользователям, информацию о том, как работают наши системы. Мы сделали код рекомендаций доступным для более детального ознакомления с нашим алгоритмом, его можно посмотреть здесь (и здесь). Также мы работаем над предоставлением большей прозрачности по другим функциям внутри нашего приложения. Некоторые из планируемых новых разработок включают в себя:

• Лучшая аналитическая платформа для создателей контента с более подробной информацией об охватах и вовлеченности.

• Большая прозрачность в отношении любых меток безопасности, применяемых к вашим твитам или аккаунтам.

• Большая наглядность в том, почему твиты появляются в вашей ленте.

Если вы хотите больше читать про Data Science, машинное обучение и не только, подписывайтесь на мой телеграм‑канал.