Месяц назад мне скинули ссылку на выступление от Яндекс Маркета на Highload++ (аж 2023, но, видимо, видео не так давно выложили) про их персональные рекомендации. Ничего особенного в нём нет, но зато есть кусок и про платформу DJ, и про алгоритм Mixigen — результаты работы нашей команды. (Кстати, если кто знает ещё публичные рассказы про DJ — дайте знать.)

Про Миксиджен хочется рассказать подробнее, потому что это штука хорошая, а настоящую статью про него уже всё равно вряд ли кто-нибудь напишет. А жаль!
(Про DJ когда-нибудь, может быть, тоже ещё подробнее напишу.)

В индустриальных рекомендательных системах есть стадии генерации кандидатов и ранжирования, и первая обычно устроена примерно так: взять 100 кандидатов из генератора A, 200 кандидатов из генератора B и т.д. Эти числа — количество кандидатов из каждого источника — чаще всего заданы конфигом и подбираются, например, путём онлайн-экспериментов. Ну и если добавляется новый источник, ему нужно выделить какую-то квоту, уменьшив квоты остальных.

Но как-то раз, когда наша команда представила очередной новый генератор кандидатов, одна из продуктовых команд нас спросила: а есть ли какой-то способ более оптимально и автоматически подбирать эти параметры? Мы тогда такого способа не знали. Но один из разработчиков в нашей команде об этом подумал-подумал и в итоге придумал несложный алгоритм, который мы и назвали Миксидженом (по созвучию с MixCG — mixing candidate generator). Точнее, мы потом назвали его Mixigen 1.0, потому что еще через какое-то время я придумал его усовершенствование — Mixigen 2.0 🙂 Но про него уже будет в следующий раз.

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

И вот тот разработчик придумал, что если суммарно нам нужно выдать N кандидатов, мы знаем (залогировали или ретроспективно восстановили) списки из N кандидатов из каждого источника к каждому запросу и знаем, какие из них — те положительные, полноту которых мы хотим повысить, то задача просто сводится к задаче о максимальном покрытии. Эта задача NP-полная, но у неё есть очень простой жадный алгоритм с гарантией аппроксимации 1 - 1/e. А на практике оказалось, что он выдаёт полноту около 99% от идеальной.

После реализации этого алгоритма и первого эксперимента на данных Яндекс Музыки оказалось, что он повышает полноту в полтора раза! Конечно, в онлайне выигрыш получился не такой большой, но всё же положительный.

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

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

Из необычных, но прикольных примеров рекомендательных систем в повседневной жизни: динамические обои на лок-скрине iPhone.

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

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

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

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

Если кто хочет тоже себе такое настроить: Settings -> Wallpaper -> Add New Wallpaper -> Photo Shuffle -> выбрать интересующие категории фото (например, я выбрал и природу, и города, и свою семью). Для Android такое тоже наверняка есть, да?

Обычно у рекомендательных сервисов есть главная метрика, которую они пытаются растить, north star. Насколько я могу судить (и когда-то я уже писал об этом), в большинстве случаев это одна из четырех:
1) Time spent (сколько времени пользователи проводят на сервисе)
2) Транзакции (количество или суммарная стоимость, GMV)
3) Подписки
4) DAU (или похожие метрики user retention)

Конечно же, это исходит от бизнес-модели сервиса.

У меня есть мнение (или лучше сказать — гипотеза), что среди этих метрик самая близкая к «чистому качеству» рекомендаций (user satisfaction, «счастью пользователей» и т.п.) — это именно DAU.

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

Не очень сложно представить, как можно накрутить time spent. GMV — наверно, тоже (хотя тут слово «накрутить» не обязательно означает что-то плохое, деньги же тоже нужно зарабатывать, просто это может быть не сонаправленно с user satisfaction). Подписки — легко, если на сервисе есть контент, доступный только подписчикам (а если нет, то и оптимизировать эту метрику будет на порядок сложнее, чем остальные).

Для DAU тоже есть известный простой способ накрутки — присылать пуши (не говоря уже про дистрибуцию). Но это всё-таки немного про другой сценарий. А вот может ли система (или команда), которая управляет только тем, какой контент она рекомендует, накрутить DAU (т.е. заставить пользователей больше возвращаться в последующие дни), но понизить при этом user satisfaction? Я простых способов не знаю.

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

Расскажите, знаете ли вы способы накрутки DAU и что вообще думаете про метрики верхнего уровня для рекомендаций?

Я уже пару раз писал про счётчики и про то, как убирать из них смещение. Но так и не затронул некоторые важные технические моменты. А именно — что счётчики занимают место в профилях пользователей и объектов. (Профиль объекта — это вся накопленная информация про объект; он не обязательно должен быть физически одной структурой.) И это значит, что мы не можем хранить бесконечное число счётчиков. Например, если профиль пользователя занимает 1 Мб, то с этим уже довольно сложно работать в realtime-системе.

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

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

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

Кстати, в нашей платформе в Яндексе мы сделали более эффективную по месту реализацию фильтра — quotient filter.

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

А можно ли избавиться от первого недостатка? Можно ли сделать структуру, которая будет хранить небинарные значения, как у счётчиков, но делать это приближенно (нам же это для фичей в основном нужно) и за счёт этого — более компактно?

Можно! Это называется count-min sketch, и это простое обобщение фильтра Блума (counting Bloom filter) с той же самой идеей использовать несколько хеш-функций. И, кстати, с экспоненциальным затуханием прекрасно совмещается.

К сожалению, у меня нет практического опыта с этим, чтобы сказать — эффективнее ли для фичей использовать count-min sketch или обычное обрезание счётчиков.

Невероятно.

Разработчик Алексей рассказал в комментах, что Стихолюб до сих пор жив!

Попав в Яндекс, мы получили проект от Ильи Сегаловича. Илья умел очень классно делиться идеями и объяснять суть. Он нам рассказал, что на самом деле Гугл в своё время выиграл у всех предыдущих поисковиков за счёт хорошо сделанных сниппетов. А теперь для нас самое главное — сделать так, чтобы поисковые результаты не были сплошь одинаковыми. Надо бороться с полу-дублями.

Только сделать это у нас не удалось. Зато мне удалось получить свою первую психологическую травму на работе.

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

Когда нужно было разобраться в каком-то куске поискового кода, Макс сказал:
— Ну давай посмотрим, кто автор этого кода... Ага, некий Антон с ником pg@. Просто сходи и спроси у него, что здесь происходит.

Я сходил и спросил. Антон с ником pg@ ответил мне, чтобы я просто прочитал код.

Прочитать и понять код у меня не получилось. А так как работали мы на четверть ставки, то в следующий раз мы с Максом встретились примерно через неделю. Узнав, что прогресса особо нет, Макс сказал:
— Нет, ну так дело не пойдёт. Пойдём вместе сходим и спросим.

Сходили и спросили. На что Антон с ником pg@ просто накричал на нас обоих: какого чёрта какие-то стажёры его отвлекают и не могут даже за неделю самостоятельно прочитать код?!

С тех пор ни я, ни Макс уже больше никогда не хотели работать в Яндекс.Поиске.

#lifestories

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

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

Что думаете?