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

Но, на удивление, ни там, ни там не было настоящего работающего механизма 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.

Что думаете?

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

Как мы уже не раз обсуждали, для генерации кандидатов лучше всего работают двух-башенные сети и 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-индексе же это сложнее, поэтому обычно так часто не обновляют.

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

arXiv.org

Revisiting Neural Retrieval on Accelerators

Retrieval finds a small number of relevant candidates from a large corpus for information retrieval and recommendation applications. A key component of retrieval is to model (user, item)...

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

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

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

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

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

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

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

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

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

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

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

Хотя и не все соглашаются с таким подходом, но я считаю, что в рекомендациях надо исходить из того, что главная цель любой рекомендательной системы — оптимизация суммарного 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 есть попытки более принципиального подхода, но нельзя назвать эту область решённой.

Telegram

Wazowski Recommends

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

Персонализация и 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-модели.

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

Так вот, не могу не порекомендовать ?
Если вам нравится этот канал, то вам обязательно понравится и канал Кирилла Хрыльченко: https://t.me/inforetriever

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

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

Telegram

Information Retriever

Рекомендательные системы глазами RecSys R&D лида Яндекса Недельные дайджесты arxiv/cs.IR, обзоры статей, образовательные посты и не только Author: @kkhrylchenko

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

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

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

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

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

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

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

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

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

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

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

Telegram

Wazowski Recommends

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

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