Вслед за последними постами хочется осветить более общий вопрос.

А нужен ли вообще negative sampling для рекомендательных моделей?

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

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

Что происходит, когда мы обучаем модель только на настоящих показах? Происходит довольно сильный selection bias, и модель учится хорошо различать только те документы, которые показывались в данном контексте. На тех документах (точнее, парах запрос-документ), которые не показывались, модель будет работать сильно хуже: каким-то документам завышать предсказания, каким-то — занижать. Безусловно, этот эффект можно снизить, применяя exploration в ранжировании, но чаще всего — лишь частично.

Если генератор кандидатов обучить таким образом, то на запрос он может выдать кучу документов, которые раньше не видел в таком контексте и которым завышает предсказания. Причём среди этих документов часто попадается совсем мусор. Если модель финального ранжирования достаточно хорошая, то она эти документы отфильтрует и не покажет пользователю. Но квоту кандидатов мы тем не менее потратим на них зря (а нормальных документов может и вообще не остаться). Поэтому генераторы кандидатов надо обучать так, чтобы они понимали, что большая часть базы документов совсем плохая и их рекомендовать (номинировать в кандидаты) не надо. Negative sampling — хороший способ для этого.

Модели финального ранжирования в этом плане очень похожи на генерацию кандидатов, но есть важное отличие: они учатся на своих ошибках. Когда модель ошибается, завышая предсказания каким-то документам, эти документы показываются пользователям и после этого могут попасть в следующий датасет для обучения. Мы можем переобучить модель на новом датасете и снова выкатить на пользователей. Появятся новые false positives. И снова можно повторить сбор датасета и переобучение. Происходит такой своеобразный active learning. На практике всего нескольких итераций переобучения хватает, чтобы этот процесс сошёлся и модель больше не рекомендовала дичь. Тут, конечно, надо соизмерять вред от рандомных рекомендаций, иногда стоит как-то подстраховаться. Но в целом, negative sampling здесь не нужен. Наоборот, он может ухудшить exploration, заставляя систему оставаться в локальном оптимуме.

Если же модель используется для фичей на вход в другую модель, то вся та же логика тоже применима, но только вред от завышения предсказаний случайным документам-кандидатам тут ещё меньше, потому что другие фичи могут помочь скорректировать финальное предсказание. (Если документ даже не попал в список кандидатов, то мы и вычислять фичи для него не будем.)

Когда-то мы прямо проверяли, что в качестве фичей обычный ALS работает лучше, чем IALS, но вот для генерации кандидатов его использовать не стоит.

Какое-то время назад я писал о том, как можно использовать внешние эмбеддинги. Сегодня поговорим на связанную (даже пересекающуюся) тему: как использовать внешнюю историю пользователей, т.е. историю на другом сервисе. Типичный пример у поисковых гигантов: поисковая история, довольно богатый источник информации про пользовательские интересы (если privacy policy позволяет).

Если у этой внешней истории пространство объектов совпадает с основным пространством рекомендуемых объектов (или сильно пересекается, или явным образом связанно), то этот случай простой: мы просто можем добавить в нашу систему ещё один тип событий — внешнее взаимодействие — и во всех моделях учитывать ещё и историю этого типа с рекомендуемыми объектами. Даже если рекомендуемые и внешние объекты явно не связаны, иногда их можно связать неявно — обучив контентную модель, которая будет "матчить" внешние объекты и внутренние.

Если же внешние и внутренние объекты совсем разные, то тут интереснее. Могут существовать статистические закономерности, которые можно выучить. Можно либо явным образом их искать ("пользователи, взаимодействующие с внешним объектом A, чаще других пользователей взаимодействуют с внутренним объектом B"), либо обучать модели, похожие на SLIM, — линейные с кросс-фичами [пользователь взаимодействовал с объектом A, мы оцениваем объект B].

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

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

Отдельный вопрос: а как именно использовать дополнительную модель с внешней историей? Есть несколько вариантов:
1) фичи в ранжирующей модели,
2) кандидаты,
3) продуктовые правила (бустить рекомендации от таких моделей),
4) более изощренные техники вроде модификации лоссов/таргетов ранжирования.

Я сильно рекомендую всегда начинать с пункта 1 — с фичей. Даже если это не самый эффективный способ, без него остальные варианты будут работать совсем не оптимально. Более того, зачастую они могут даже вредить системе.

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

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

Чаще всего кандидато-генерация устроена как объединение разных источников:
- самые популярные объекты,
- похожее на историю пользователя,
- ANN — похожее по эмбеддингам (например, HNSW),
- комбинация предыдущих методов на разных уровнях: например, взять категории из истории пользователя (или из ANN, или популярные), а потом из них взять популярные объекты.

Хотя каждый метод тут может быть несложным, вся комбинация получается достаточно нетривиальной, чтобы задуматься: а как её можно оптимизировать? А для этого нужно, конечно, определить, что именно надо оптимизировать, т.е. какой метрикой измерять качество кандидато-генерации (далее будем говорить именно про эту стадию, хотя всё то же самое относится и к ранним стадиям ранжирования).

Существуют разные подходы. Иногда качество просто не замеряют (ну или просто "на глаз") и системно не оптимизируют эту стадию. Иногда каким-то образом замеряют общую релевантность кандидатов. И если система порекомендовала что-то странное, то это считают багом в том числе и кандидато-генерации. Иногда эту релевантность даже противопоставляют тому, что оптимизируется в финальной стадии. Т.е. кандидаты должны быть уже достаточно релевантными (как бы это ни измерялось), а финальное ранжирование выберет из них наиболее engaging (привлекательные/кликабельные/...).

Иногда, особенно в статьях, используют метрики вроде HitRate@k, Recall@k, Precision@k, MRR, NDCG и т.д., фокусируясь только на положительных (релевантных) документах. При этом релевантным считается тот документ, с которым пользователь впоследствии взаимодействовал. Мне этот подход нравится больше предыдущих, хотя тут большая проблема с разными смещениями: например, пользователи чаще взаимодействуют с теми объектами, которые система сама же и рекомендует.

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

Подход основывается на таком принципе:

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

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

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

Этот принцип превращает кандидато-генерацию в довольно утилитарную задачу с вполне определенной целью. А вся сложность с objectives (какие таргеты и лоссы использовать) перекладывается на финальную стадию ранжирования.

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

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

Всех с 1700000000!

Из забавного:
Google Discover порекомендовал мне прочитать мою же статью, опубликованную в Towards Data Science 😁

А теперь обсудим, как именно на практике можно измерять качество кандидато-генерации (или ранних стадий ранжирования), согласно тому самому принципу.

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

Брать ли средние предсказания по всей выдаче, или только по топовым позициям, или с каким-то затуханием по позициям (получается что-то вроде IDCG — знаменателя в NDCG) — кажется, не очень принципиально. Можно выбрать любое по вкусу.

Есть технический нюанс. Если измерять такую метрику в офлайне, то надо уметь запускать ранжирование (или весь рекомендательный стек) на кастомных кандидатах. Это можно сделать либо через симуляцию (offline replay — т.е. пытаться ретроспективно воспроизвести всю информацию про все сущности) на исторических запросах, либо через scraping — "обстрелять" сервис рекомендаций новыми запросами, чтобы он при этом использовал интересующие методы кандидато-генерации. В обоих случаях получаются результаты (предсказания финальной модели) для разных методов генерации для одних и тех же запросов. Это хорошо для чувствительности метрики.

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

А теперь перейдём к общему случаю: финальное ранжирование — это не только предсказания какой-то модели, но и много другой логики, переранжирования, бизнес-правил, рандомизации и т.д. Если задуматься, как вообще сравнить разные наборы кандидатов в такой нестрогой формулировке (что такой хорошо и что такое плохо) — совсем не очевидно.

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

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

Конечно, тут мы предполагаем, что добавление случайных кандидатов не сильно ухудшает систему: большинство из них не порекомендуется, а те, которые порекомендуются, не сильно ухудшат жизнь пользователей, да ещё и добавят exploration как пользователям, так и модели ранжирования (она дообучится на этих примерах). Если это не так, то сначала стоит "починить ранжирование". 😉

Самое прикольное в этом методе — что он может служить не только метрикой кандидато-генерации, но и мониторингом здоровья всей системы, в том числе и финального ранжирования. Он проверяет, насколько кандидато-генерация согласована с ранжированием (оптимизирована под ранжирование). Если само ранжирование по каким-то причинам деградирует, то и кандидаты становятся не такими уж хорошими для него. Мы это видели на практике, когда одна из компонент поломалась, доля рандомных кандидатов в ответе увеличилась.

Кстати, случайность этого специального источника можно настраивать. Если использовать не равномерную, а пропорциональную популярности документа, то это будет более сильный "adversarial" игрок (что тоже может увеличить чувствительность). Зато при равномерном сэмплировании можно дать аналитическую оценку того, в какой доле запросов наша кандидато-генерация была идеальной (т.е. результат бы не поменялся, даже если бы мы добавили в кандидаты всю базу).

Когда этим летом запускался Threads, большая часть ленты состояла из ВП — взаимного пиара.

Так вот, не могу не порекомендовать 😁
Если вам нравится этот канал, то вам обязательно понравится и канал Кирилла Хрыльченко: https://news.1rj.ru/str/inforetriever

Один из типов постов там (не единственный!), который лично для меня очень полезен: Кирилл раз в неделю выкладывает дайджест свежих статей с arxiv на тему рекомендаций, ранжирования и прочего information retrieval. Он это уже делает больше года, но только сейчас это стало публичным.

И про negative sampling, например, Кирилл тоже рассказывает в одном из недавних постов, можете сравнить. (И на меня тоже ссылается, куда ж без взаимности 😉)

Персонализация и popularity bias

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

В сообществе есть известная проблема popularity bias. Но что это в точности такое? Bias — это системное смещение. А где здесь смещение? И есть ли оно вообще?

Если общими словами, то под popularity bias понимается ситуация "the rich get richer", когда популярные документы рекомендуются системой непропорционально чаще непопулярных. Причины у этого могут быть разные, и в литературе освещаются разные аспекты этого явления. Важно разделять эти причины, потому что это сильно помогает дебажить систему.

В работе над рекомендациями очень полезно выделять два важных шага:
1) Обучение модели предсказания отклика пользователя на рекомендованный объект. В простом случае это просто вероятность клика, в более общем — E(engagement | item, user, context).
2) Собственно, построение рекомендаций с помощью этой модели. Простое ранжирование по предсказаниям — не самый оптимальный, хотя и хороший бейзлайн.

Во многих случаях, говоря о popularity bias, подразумевают неоптимальность шага 2. То есть, даже если более популярный объект вызовет у пользователя с большей вероятностью позитивный отклик, может быть лучше порекомендовать ему менее популярный объект. Причин тут тоже может быть несколько — как пользователецентричные (долгосрочно клик на популярный объект менее ценен для этого пользователя, чем клик на непопулярный), так и с точки зрения всей экосистемы (этому пользователю станет чуть хуже, но зато мы выровняем распределение потребления по всей базе объектов). Это, в целом, разумные мысли, но надо честно себе признаться: мы жертвуем engagement-ом в момент конкретного запроса ради светлого будущего.

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

В других же случаях popularity bias относят к первому пункту: дисбаланс объектов мешает нам хорошо обучить модель E(engagement | item, user, context). В частности, она может плохо учитывать пользовательские фичи и, по сути, просто выучить E(engagement | item), тесно связанную с популярностью (кстати, в этом посте я тоже иногда под популярностью имею в виду не P(item), а E(engagement | item)). Вот это уже очень ощутимая проблема. Хотя я не очень понимаю, почему её называют баисом.

Тут советы зависят от конкретной модели. Вот несколько:
- Убедитесь, что у модели есть информативные персональные фичи.
- Введите отдельный член внутри модели, отвечающий за популярность, чтобы оставшаяся часть модели могла сфокусироваться на специфичности.
- Если модель выучивает эмбеддинги объектов, проверьте, хорошо ли они выучились. Например, посмотрев на самые похожие объекты на данный.
- Если используется negative sampling, то учитывайте в нём популярность. Только не забудьте при применении обратно умножить на неё, чтобы получить E(engagement | ...), как обсуждали в том же посте.
- Ну и просто проверьте, что модель нормально выучилась. Да, это не так-то просто. Это часть довольно сложной, но критически важной темы ML Debugging.

Кстати про "непропорционально чаще". Никто ведь не обещал, что при простом ранжировании вероятность быть порекомендованным будет пропорциональна популярности или CTR документа. Это совсем не так. Может быть, поэтому это и называют bias-ом?

На моей же практике было очень много случаев, когда команды
а) не задумываются, что именно они называют popularity bias-ом и в чём его причины,
б) имеют проблемы с недостатком персонализации просто из-за плохо обученной модели E(engagement | ...).

Очень важно понимать — это мир так устроен, что у популярных, но менее релевантных объектов действительно в среднем лучше отклики, или просто мы модель плохо обучили.

Намного чаще popularity bias — это просто популярный миф, скрывающий баги системы.

Не стоит недооценивать важность хорошей engagement-модели.

Хотя и не все соглашаются с таким подходом, но я считаю, что в рекомендациях надо исходить из того, что главная цель любой рекомендательной системы — оптимизация суммарного value. Это value может измеряться разными метриками. Главные четыре типа, которые я видел: DAU, time spent, транзакции (GMV) и подпиcки. Кроме того, иногда это value не только обычных потребляющих пользователей, но и других сторон — провайдеров контента.

Как я писал в предыдущем посте, основная часть рекомендательной системы — это engagement-модель E(engagement | item, user, context), которая предсказывает это самое value (или какое-то его осмысленное упрощение) для одного порекомендованного объекта. И можно строить рекомендации, просто сортируя по предсказаниям этой модели, не обращая внимания ни на что другое. Назовём этот бейзлайн циничным ранжированием.

Циничное ранжирование не является оптимальным для заявленной цели оптимизации суммарного value. Вы часто можете услышать про разные "beyond accuracy" аспекты рекомендаций вроде exploration, diversity, novelty, serendipity. Давайте переведём эти понятия с языка ощущений и "продуктового видения" на язык оптимизации суммарного value.

В этом посте начнём с exploration. Все слышали о дилемме exploration vs. exploitation. Это о том, что зачастую выгодно пожертвовать value (наградой) в текущем моменте ради того, чтобы узнать что-то новое и в будущем действовать более оптимально.

Довольно важно разделять user exploration и system exploration, потому что работать с ними надо по-разному. В первом случае мы жертвуем value пользователя в моменте ради него же самого, чтобы узнать о нём больше. Проверить, насколько хорошо нам это удаётся, можно с помощью обычных A/B-тестов. Только иногда нужно увеличивать их длительность, чтобы уловить более долгосрочные эффекты.

В system exploration же мы хотим узнать больше о всей системе. Одним важным частным случаем является item exploration — узнать больше про недоисследованные объекты (особенно недавно появившиеся в системе). Также можно исследовать разные области в пространстве признаков любой из использующихся моделей (model exploration). Про это уже был пост от Саши.

В отличие от user exploration, в system exploration всё сильно сложнее с замерами. Мы приносим пользователя в жертву ради остальных, а остальные могут оказаться в другой выборке A/B-теста.

При этом какие-то простые и полезные метрики item exploration всё же можно использовать: доля объектов, которые получают не меньше X показов/кликов за первые Y часов, — как метрика на дашборде, и доли кликов и показов на такие "недоисследованные" (новые с малым числом показов) объекты — как метрики в A/B. Эти метрики позволяют сравнить уровень exploration, но не отвечают на вопрос, какой уровень был бы оптимальным.

У YouTube есть попытки более принципиального подхода, но нельзя назвать эту область решённой.

Diversity

В некоторых продуктах сразу понятно, что без разнообразия рекомендации будут ужасными (понравится ли вам слушать в рекомендациях музыки только лишь одного исполнителя?), в некоторых — не так очевидно. Говоря о разнообразии, имеют в виду несколько разных вещей.

Есть intra-list diversity — разнообразие в рамках одной страницы (одного запроса, request-level). Циничное ранжирование не разнообразно, потому что каждый объект оценивается независимо и все они имеют один и тот же контекст. На самом же деле пользователи видят порекомендованные объекты в контексте друг друга. Например, если два объекта очень похожи друг на друга, то, скорее всего, пользователь кликнет лишь на один из них.

Поэтому стоит динамически обогащать этот контекст объектами из начала списка во время listwise-ранжирования — как я описывал. Хотя и это еще не идеально, т.к. на каждом шаге жадно оптимизируется value одного объекта, а не всего запроса.

Есть разнообразие в рамках истории пользователя — user-level. В этом случае оно очень сильно пересекается с user exploration. Но не полностью — можно себе попытаться представить ситуации с достаточным diversity, но недостаточным user exploration, и наоборот, а также и другие комбинации с novelty и serendipity. Суть у этих эффектов одна — краткосрочность оптимизации. Если мы научимся оптимизировать долгосрочное value пользователя, то мы сразу решим все эти вопросы user-level diversity, user exploration, novelty, serendipity etc.

Кстати, в сервисах, где потребляется один объект за раз (TikTok или радио), граница между этими двумя видами разнообразия размыта. Технически, на один запрос всё равно обычно выдаётся список объектов (скажем, пять), который показывается пользователю последовательно. Меняя этот параметр — размер списка — мы переходим между request-level (intra-list) и user-level diversity.

Есть также и system-level diversity. Как несложно догадаться, оно нацелено на экосистемную оптимизацию — т.е. суммарного value всех пользователей. Мы его затрагивали, говоря о popularity bias.

—

А всё ли разнообразие покрывается этими аспектами? А если для максимизации value (даже долгосрочного) не нужно разнообразие, или его нужно мало? А интуитивно кажется, что разнообразия не хватает?
Это достаточно частая ситуация — когда любое повышение разнообразия только ухудшает метрики.
Как я и говорил, я приверженец подхода:

главная цель любой рекомендательной системы — оптимизация суммарного value

Если интуиция противоречит наблюдениям по метрикам, то либо надо подправить метрики, либо — интуицию.

Метрики:
Возможно, мы неправильно выбрали определение value. Например, оптимизируем time spent, а с интуицией (счастьем пользователей?) больше согласуется оптимизация DAU/retention. Или измеряем их на недостаточном периоде времени. Или (что тоже очень частый случай!) просто пока не нашли хороший способ, как оптимизировать value согласованно с интуицией.

Интуиция:
А может, и не надо повышать разнообразие и выводить пользователей из пузыря? Может, им на самом деле это не нужно, или, если и нужно, то, скажем, покупать они всё равно от этого больше не станут?

Философский вопрос. Можете высказать своё мнение в комментариях :)

—

Если обобщить этот и предыдущий посты, то эволюция рекомендательных таргетов может быть такая:
1. E(value | item, user, context) — циничное ранжирование, оптимизация value каждого конкретного айтема.
2. E(value | request) — listwise-ранжирование, оптимизация суммарного value каждого запроса.
3. E(value | user) — оптимизация долгосрочного value каждого пользователя.
4. E(value) — оптимизация суммарного value всей системы.

При этом на каждом уровне можно выбирать своё определение value. (И именно так каждый следующий уровень может использовать предыдущий.)

Из личных новостей: сегодня я начал работать в 𝕏 (как обычно приписывают — formerly known as Twitter). Теперь буду там улучшать качество рекомендаций.

Почему именно X? За последние полгода мне не раз приходилось отвечать на этот вопрос и для себя, и для других.

В мире не так много крупномасштабных рекомендательных систем. И практически все они принадлежат большим корпорациям. Я несколько устал от корпораций (особенно после Microsoft), мне очень хотелось в компанию поменьше. И вот как раз таким исключением и является X. И там уже даже работает пара моих бывших коллег: Сева @yalinter и недавно вышедший туда Саша @knowledge_accumulator. Поэтому я приблизительно знал, на что иду. И надеюсь, что со временем еще больше наших бывших коллег присоединятся.

Рекомендации — это core функциональность для X, и я вижу в них большой потенциал.

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

А Саша недавно писал более подробно про свои причины, и с ними я тоже согласен.

Надеюсь, у нас получится.

Больше года назад я начал второй сезон в этом канале. Но в последние полгода случилось много всего: переезд, новая работа (а работать здесь и правда надо и хочется побольше, это вам не Майкрософт 😁). Времени регулярно писать не было, поэтому пришлось снова уйти на каникулы.

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

По традиции, тишину прерываю дружеским пиаром рекомендациями. Мы с авторами нескольких каналов о рекомендательных системах (и не только) собрали папку, на которую можно подписаться.

Подключайтесь!

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

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

Так вот, сначала Meta, а потом LinkedIn (и по слухам — ТикТок тоже) показали, что в современном мире это можно делать лучше.

Двух-башенные сети на первой стадии всё ещё остаются. Но вот складывать в ANN-индекс не нужно. А нужно… Просто использовать GPU!

При небольшой размерности эмбеддингов, да ещё и в квантизованном виде, на одной карточке A100 можно хранить порядка 100 миллионов документов (а этого хватит, конечно же, всем... ну почти) и успевать с ними со всеми посчитать скалярное произведение за несколько десятков миллисекунд. А для хорошего throughput запросные эмбеддинги стоит собирать в батчи (матрицы), чтобы всё это можно было сделать одним матричным перемножением.

Какие у этого преимущества?

1) Полнота поиска выше. Как бы мы ни любили ANN, их полнота на практике выше 95%, но всё-таки не 100%. А тут мы считаем произведение со всеми объектами в базе.

2) Если обычно мы отбираем одну или несколько тысяч кандидатов из ANN, то здесь можно выдавать сразу 100'000. ANN с таким количеством работают уже не очень хорошо. Только вот что делать дальше с этими 100000? Мета предлагает на следующей стадии ранжировать их моделью потяжелее, mixture-of-logits, MoL (всё ещё двух-башенная, но в конце не произведение, а более сложная сеть), тоже на GPU. И уже результат этого выдавать в тяжелое ранжирование, как и раньше.

3) А ещё такой подход позволяет намного быстрее и чаще обновлять эмбеддинги документов. Их же просто нужно обновить в памяти GPU. В ANN-индексе же это сложнее, поэтому обычно так часто не обновляют.

Выглядит перспективно.

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

Но, на удивление, ни там, ни там не было настоящего работающего механизма feature selection.

Уточню, что я называю «настоящим». Все градиентные бустинги предоставляют feature importance — насколько они каждый признак использовали и насколько это помогло оптимизации лосса. Также бывают SHAP values. Но все грамотные ML-инженеры знают, что всё это совсем не настоящая полезность фичей. Их нужно использовать так: если importance нулевая (или очень маленькая), то фича бесполезная, ее можно убрать. Но не в обратную сторону.

В Яндексе был (есть) настоящий feature evaluation — убрать фичи и посмотреть, как меняется качество, да еще и стат-тест запустить. И даже была (есть) более дешевая приближенная модификация.

Но вот именно полноценного feature selection не было. Точнее, при мне даже была попытка его сделать, но вроде как большого успеха (распространения) она не достигла. Может быть, спрос на этот инструмент был недостаточным, а может, сделать его эффективным очень сложно. Задача же нетривиальная — есть N (тысячи) фичей, нужно среди 2^N наборов выбрать оптимальный (с точки зрения качества и какого-то понятия стоимости — например, количества фичей). А протестировать каждый набор может занимать часы.

Год назад я над этим размышлял-размышлял... И подумал, что можно это попробовать сделать сильно более эффективно с помощью Random Forest. Предлагаю вам оценить. (Я уже с бустингами перестал работать и вряд ли буду тестировать.) Сразу оговорюсь, что я никогда ничего про feature selection для random forest не читал и не слышал. Вполне вероятно, что уже давным-давно придумали либо то же самое (тогда почему не используют? не работает?), либо что-то ещё получше. Расскажите в комментах, если знаете.

Итак, идея:
- Предположим, что для отбора фичей можно временно заменить бустинг на random forest. (Это слишком сильное предположение?)
- Обучим random forest на всех фичах с раз в сто большим количеством деревьев. (Его же обучать дешевле, чем бустинг, он очень легко параллелится.)
- Затем запускаем любой стандартный алгоритм отбора фичей. И когда тестируем очередной набор, то не обучаем модель заново, а просто выбираем те деревья, которые не используют выкинутых фичей.
- Обычно нас интересуют наборы, в которых большая часть фичей не выкинуты, поэтому таких деревьев должно быть не слишком мало. И можно оценить, какое качество будет у модели с ровно M такими деревьями.
- ...
- Profit.

Что думаете?

В рекомендательных системах, как и в некоторых других областях ML, практически во всех данных присутствует важное поле — таймстемп. Почти всё, с чем мы работаем, — это события, и нам важно, когда они произошли. И на этом можно было бы не заострять внимание. Но есть нюансы.

Почему важны таймстемпы? Во-первых, конечно, самый правильный способ измерять качество моделей в офлайне — разделяя trainset и testset по времени (причём глобально, а не для каждого пользователя отдельно, как любят делать в научных статьях). Потому что в реальной жизни всё будет работать именно так: мы обучаем модель, потом выкатываем её, и потом уже она работает на пользователях. А вообще-то, чаще всего у нас модели постоянно инкрементально дообучаются, поэтому и тестировать хорошо бы в таком же инкрементальном/онлайн режиме, а не с отложенным тестсетом.

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

Но всё-таки иногда приходится фичи вычислять заново («вычисление» может быть и очень простым — просто подджойнить таблицу), например, когда это новая фича и нам надо её сначала протестировать перед тем, как выкатывать на логирование. В этом случае надо строго следить за тем, чтобы при вычислении мы использовали данные, максимально похожие на те, которые были бы в онлайне. В том числе — не заглядывать в будущее. Иногда для надежности делают некоторое отставание в несколько минут или часов.

Этот механизм — приджойнить или вычислить фичи ретроспективно, с заданным отставанием по времени — достаточно общий, и его имеет смысл реализовать один раз в обобщенном виде.

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

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

Наконец, мало где можно встретить такое параноидальное внимание к деталям, но всё-таки уточню, что у пользовательских событий (взаимодействий с объектами) есть не один таймстемп и не два, а много:
T_req_start — пришёл пользовательский запрос на рекомендации;
T_req_end — мы построили рекомендации;
T_impression — пользователь увидел (начал смотреть/слушать) порекомендованный объект;
T_click, T_like, ... — пользователь совершил какое-то действие с объектом;
T_ingest — наша система узнала про всё это (что в свою очередь, конечно, зависит от конкретной части системы, которая узнала).

С точки зрения правильного тестирования модели, самые главные из этих таймстемпов — T_req_start и T_ingest. Но, к сожалению, не часто их разделяют, а вместо этого используют один таймстемп и иногда добавляют отставание. Так проще, а разница между ними обычно незначительная. Но думаю, что чем сложнее и мощнее становятся наши модели, тем больше проблем будет у неправильного учёта таймстемпов. С транформерами, например, это уже стало выстреливать намного чаще, чем раньше.

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

А теперь давайте подумаем, в какой момент времени относительно времени показа (T_impression) и времени разных взаимодействий (T_click, etc.), о которых говорили в прошлом посте, наша модель должна получить новый сэмпл для обучения (т.е. каким должен быть T_ingest в обучатор модели). Конечно, нам хочется, чтобы это происходило как можно раньше, чтобы мы могли быстро выявлять очень популярные новости. Но сделать это прямо в момент показа мы не можем, так как еще не знаем, произойдёт ли клик.

Самый простой вариант — подождать X времени (скажем, несколько минут) после показа и соответствующим образом решить, положительный ли этот сэмпл или нет. Тогда модель будет предсказывать, с какой вероятностью пользователь кликнет/полайкает/… документ за время X. Если X будет слишком большим, реакция системы будет медленнее. Если X будет слишком маленьким, то мы упустим часть положительных взаимодействий из-за того, что они не успели произойти за X. Эта часть может оказаться совсем не нулевой, больше, чем кажется на первый взгляд, особенно для более сложных таргетов (например, подписался ли пользователь на источник новости). У каждого таргета есть своё вероятностное распределение времени, через которое он случается после показа. И у этих распределений тяжелые хвосты.

Есть ли способы эффективнее?

Например, можно было бы завести несколько разных событий с разными X: кликнул ли за 30 секунд, за 2 минуты, за 5 минут и т.д. Но тогда мы увеличим объём данных для обучения в несколько раз, хотя информации для обучения мы будем выдавать не сильно больше, чем раньше. Это очень большая нагрузка на инфраструктуру и на обучение.

Можно было бы сразу же в момент показа использовать негативный сэмпл, а потом в случае, если какое-то действие произойдёт, сделать новый сэмпл, «уточняющий» предыдущий. (А если еще одно действие произойдёт — то еще одно уточнение, и так далее.) Так как уточнений будет на порядок меньше, чем показов, то нагрузка на инфраструктуру возрастёт не слишком сильно. Понятно, как обрабатывать такие уточнения для счетчиков. А вот как это делать для обучающихся эмбеддингов? Т.е. как «отменить» действие предыдущего негативного сэмпла? Возможно, можно просто сделать обратный шаг — шаг по градиенту (т.е. шаг градиентного подъёма вместо градиентного спуска). Но параметры модели на этот момент уже не те, которые были при прямом шаге, поэтому это не будет совсем точной его отменой. Не разнесёт ли модель от этого? Кроме того, как только новость появляется, она сразу получает много негативных сэмплов, а позитивные придут только с задержкой, из-за чего получается сильное смещение в негативную сторону.

Можно также комбинировать этот способ с изначальным простым — сначала чуть-чуть подождать (маленькое X), использовать первый сэмпл и уже только после этого начинать делать уточнения. Это снизит степень проблем, связанных с уточнениями. Но решит ли полностью? Да и сложновато получается.

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

Что думаете?