Один из важнейших типов моделей в рекомендациях на данный момент — это двух-башенные (two tower) нейросети. Они устроены так: одна часть нейросети (башня) обрабатывает всю информацию про запрос (пользователя, контекст), другая башня — про объект. Выходы этих башен — это эмббединги, которые потом перемножаются (dot product или косинус, как уже обсуждалось в этом посте). Одно из первых упоминаний применения таких сетей для рекомендаций можно найти в очень хорошей статье про YouTube. Кстати, именно эту статью я бы сейчас уже называл классикой и наиболее подходящей для входа в область рекомендаций.

Чем характерны такие сети? Они очень похожи на матричную факторизацию, которая на самом деле является частным случаем, принимая на вход только user_id и item_id. Если же сравнивать с произвольными сетями, то это ограничение на позднее связывание (не давать входам из разных башен смешиваться до самого конца) делает двух-башенные сети крайне эффективными при применении. Чтобы построить рекомендации одному пользователю, нам нужно один раз посчитать запросную башню, после чего умножить этот эмбеддинг на эмбеддинги документов, которые обычно заранее предподсчитаны. Это очень быстро. Более того, эти предподсчитанные эмбеддинги документов можно сложить в индекс (например, HNSW), чтобы по ним быстро, не проходясь по всей базе, находить хороших кандидатов.

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

Сами башни могут быть довольно навороченными. Например, в пользовательской части можно использовать механизм self-attention для обработки истории (получится трансформер для персонализации). Но чем мы платим, вводя ограничение на позднее связывание? Конечно, качеством. В том же самом attention нельзя использовать объекты, которые мы сейчас хотим оценить/порекомендовать. А ведь хотелось бы для этого как раз обратить внимание на похожие объекты в истории пользователя. Поэтому сети с ранним связыванием обычно применяют на поздних стадиях ранжирования, когда осталось несколько десятков или сотен кандидатов, а с поздним (two tower) — наоборот, на ранних стадиях и кандидато-генерации.

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

Отдельный интерес составляет лосс, с которым обучают двух-башенные сети. В принципе, их можно обучать на любой лосс с любыми таргетами и даже иметь несколько разных для разных голов (с разными эмбеддингами в каждой башне). Но один интересный вариант — это обучение с softmax-лоссом на in-batch негативах. Для каждой пары запрос-документ из датасета берутся остальные документы в том же мини-батче и в паре с тем же запросом используются как негативы в softmax loss. Это очень эффективный вариант hard negative mining.

Но важно иметь в виду вероятностную интерпретацию такого лосса (далеко не все её понимают). У обученной сети
exp(score(q, d)) ~ P(q, d) / (P(q) * P(d)) = P(d | q) / P(d),
т.е. экспонента скора будет пропорциональна не априорной вероятности документа при условии запроса, а PMI, специфичности для запроса. Более популярные документы в среднем не будут рекомендоваться чаще такой моделью, потому что во время обучения они пропорционально чаще выступают и как негативы. Если использовать скор как фичу, то это даже хорошо, но вот для финального ранжирования и для кандидато-генерации это может приводить к очень специфичным, но плохим документам.

Тот же Google в статье предлагал с этим бороться с помощью logQ correction во время обучения. Мы же обычно делали это на этапе применения, а не обучения, — просто умножая на априорную вероятность документа P(d). Но мы так и не сравнивали эти подходы, а было бы интересно сравнить.

Есть такой алгоритм коллаборативной фильтрации Implicit ALS (IALS). Я про него уже упомянал. В донейросетевую эпоху это был чуть ли не самый популярный алгоритм. Его отличительная черта — эффективный "майнинг" негативов: все пары пользователь-объект без истории взаимодействия выступают негативами (с меньшим весом, чем настоящие взаимодействия). Причём, в отличие от настоящего майнинга, здесь негативы не сэмплируются, а на каждой итерации используются прямо все такие негативные пары. Такая implicit-регуляризация.

Как же это возможно? Ведь при разумных размерах задачи (количестве пользователей и объектов) негативов должно быть настолько много, что даже их перечисление будет дольше всего процесса обучения. Красота алгоритма в том, что, благодаря использованию MSE-лосса и методу наименьших квадратов, можно заранее (перед каждой полной итерацией) предпосчитать что-то отдельно для всех пользователей и отдельно для всех объектов и этого хватит для того, чтобы делать implicit-регуляризацию. Так удаётся избежать квадратичного размера. (За подробностями предлагаю обратиться к одной из моих любимых статей тех времён.)

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

Думал, думал и придумал! И пару недель ходил воодушевлённый, в ожидании того, как мы это попробуем вместо in-batch негативов.

А потом, конечно же (как это часто бывает в подобных случаях), прочитал в статье, что всё уже придумали за три года до этого. И снова Google. И потом они в той самой статье про logQ correction, про которую я уже говорил, показали, что softmax loss с in-batch негативами работает лучше, чем implicit-регуляризация.

Вот так мы смогли сэкономить и не проверять эту идею 🙂

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

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

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

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

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

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

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

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

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

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

HNSW [2016] - один из столпов современных рекомендательных систем

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

Идея следующая: у нас есть эмбеддинг пользователя u и N эмбеддингов документов d, и мы хотим взять k ближайших к пользователю документов. Проблема в том, для точного ответа на такой запрос нам придётся считать все N расстояний между u и d, но такие вычисления мы не можем себе позволить. Но нам и не нужен точный ответ, подойдут и просто k близких к u векторов. Такая постановка называется "approximate nearest neighbor search". HNSW - это на сегодня топовый способ решения такой задачи.

Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору q, мы жадно ходим по графу и идём всегда в вершину, которая ближе всего к q. Когда мы попадаем в "локальный минимум", то считаем его ответом. Такая процедура позволяет не считать все расстояния для каждого q.

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

Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.

@knowledge_accumulator

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

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

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

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

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

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

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

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

Как и зачем делать exploration в рекомендациях

В схеме Learning to Rank мы обучаем модель Score(user, item), выдающую оценку релевантности каждого из кандидатов. Рассмотрим пример сценария применения такой модели:

Этап кандидатогенерации, к примеру, HNSW, принёс нам 1000 кандидатов. К каждому мы применили нашу модель релевантности и получили 1000 чисел. В качестве результата выполнения запроса мы должны отдать пользователю 10 объектов. Простейшая опция - это отдать пользователю 10 объектов с наибольшей релевантностью. Но у этого есть проблема.

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

Возникает trade-off - с одной стороны, мы хотим формировать релевантную выдачу, с другой, мы хотим её немного разнообразить для улучшения качества датасета. Этот баланс на практике можно регулировать таким образом:
1) 1000 скоров кандидатов превращаются в вероятности попадания в выдачу: p = exp(score/T) / Z, где T - температура, а Z - нормировочная константа.
2) Применяется специальный алгоритм по генерации выборки из такого распределения.
Если T равна 0, мы получаем просто топ-10, и чем она больше, тем больше всё сглаживается в сторону равномерной выдачи.

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

Сначала предполагаем на глаз, какой уровень "гладкости" выдачи мы хотим. А затем уже подгоняем T, чтобы был нужный эффект, и по надобности иногда переподгоняем. Вот такая наука.

@knowledge_accumulator

Всех с 1700000000!

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

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

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

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

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

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

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

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

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

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

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

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

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

Так вот, не могу не порекомендовать 😁
Если вам нравится этот канал, то вам обязательно понравится и канал Кирилла Хрыльченко: https://www.tgoop.com/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 есть попытки более принципиального подхода, но нельзя назвать эту область решённой.

Из личных новостей: сегодня я начал работать в 𝕏 (как обычно приписывают — 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.

Что думаете?