Wazowski Recommends

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

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

Через год стало чуть-чуть понятнее, что именно мы хотим сделать. В Яндексе на тот момент уже была своя система MapReduce, но к ней было много нареканий. Ну и... не исправлять же их! Лучше напишем новую!
Если серьёзно, то на этот раз, думаю, на то и правда были разумные причины — иногда систему действительно лучше переписать с нуля.

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

Одним из основных референсов для такой системы у нас был BigTable от Гугла. Поэтому, когда нужно было как-то назвать папку с кодом, я назвал ее YandexTable. А через некоторое время к нам присоединился и главный разработчик предыдущего MapReduce и сказал, что это отличное название, только нужно сократить до YT и читать «Ыть». Возможно, название — это мой самый большой вклад в этот проект. Кода-то моего там уже не осталось, скорее всего.

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

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

Хотя это и не было проектом моей мечты, всё-таки опыт был незаменимый. Работая с Максом рука об руку, я научился писать асинхронный код, разрабатывать сложные компоненты и избегать костылей. Спасибо тебе, Макс!

Через несколько лет YT выиграл тендер в Яндексе и вытеснил другие MapReduce-системы (которых всего было от 3 до 5, по разным подсчётам). А два года назад вышел в open source как YTsaurus. На картинке снизу носохвост — он был любимой мягкой игрушкой Макса и символом нашей команды. Видимо, он и стал логотипом YTsaurus.

#lifestories

А теперь о разных особенностях Mixigen 2.0.

🔹 Наивная имплементация описанной идеи будет тормозить, потому что инференс модели вызывается отдельно на каждую позицию каждого источника (кроме начальных позиций, их можно отскорить вместе). Но это легко исправить, если предположить, что близкие позиции имеют близкий скор. Тогда можно набирать из очередного источника не по одному кандидату, а сразу небольшими пачками (скажем, по 10). В таком варианте у нас это работало в пределах 10мс на запрос. Кроме того, вероятно, можно ещё сэкономить, вызывая инференс батчами.
🔹 Я не проверял на практике, но, судя по графикам из предыдущего поста, предсказания должны хорошо выражаться какой-то параметрической функцией от позиции — например, суммой сигмоид. Если обучить нейронную модель в таком виде, то инференс можно будет запускать вообще один раз — чтобы получить параметры этих функций для разных источников. А пересчитывать для разных позиций будет уже почти бесплатно.
🔹 Модель обучается на том же, что используется в продакшене. Если какие-то позиции источников никогда не используются, то и модель про них ничего не узнает. Поэтому стоит добавить немного эксплорейшена: после основного цикла алгоритма добавить ещё несколько очередных позиций из случайных источников.
🔹 Легко поддержать параметры, позволяющие ограничить снизу и сверху количество кандидатов из каждого источника. Это может быть полезно, в частности при добавлении нового источника. Но опять-таки, если посмотреть на графики, то обычно это не обязательно, новые источники и так предсказываются не очень плохо.
🔹 Как следствие из предыдущих двух пунктов, а также из-за обновлений модели ранжирования — модель Миксиджена важно регулярно дообучать.
🔹 Как и с многими дополнительными компонентами, здесь возникает нюанс при экспериментировании с разными ранкерами. Можно это делать, не меняя модель Миксиджена. Но т.к. она обучалась для продакшен-ранжирования, то и результат у продакшена будет чуть-чуть лучше. Обычно это почти ничего принципиально не меняет. Но можно и использовать разные модели под разные ранкеры. Более того, чтобы обучить новую модель Миксиджена под новый ранкер, даже необязательно запускать их в онлайн — ведь учимся мы на выходах ранкера, а не на реакциях пользователей.
🔹 Тоже не проверял на практике, но есть идея, что с помощью Миксиджена можно даже динамически контролировать суммарное число кандидатов. Если мы видим в какой-то момент, что вероятность быть порекомендованным опускается ниже порога, то можно уже на этом остановиться, выдать меньше кандидатов и сэкономить ресурсы следующих стадий.

Нельзя не сравнить Миксиджен с использованием дополнительной, легкой стадии ранжирования, потому что цель у них одна и та же.

🔸 Сразу скажу, что у меня не было полноценного опыта их сравнения в одном и том же проекте.
🔸 Очевидно, что легкое ранжирование сильно лучше по качеству, потому что использует информацию про объекты. Миксиджен использует только источники и позиции.
🔸 Но это требует и больших затрат как для инференса, так и для логирования. Чтобы хорошо обучить легкое ранжирование, нужно логировать фичи от хоть каких-то не порекомендованных кандидатов. В Миксиджене же это необязательно.
🔸 Миксиджен принципиально более масштабируем. Ведь ему всё равно, сколько суммарно кандидатов на входе. Ему только важно, сколько источников и сколько кандидатов нужно отдать на выходе.
🔸 Кстати, пока я писал эту серию постов, я осознал, что эту масштабируемость можно довести до предела. И по сути, именно это сделали ByteDance в своей последней статье про real-time индекс: merge статических списков объектов из 16К кластеров — частный случай Миксиджена.
🔸 Главное — эти подходы можно совмещать. На вход в легкое ранжирование тоже обычно идут кандидаты из разных источников, и вполне не бессмысленно этот этап так же оптимизировать.

Месяц назад мне скинули ссылку на выступление от Яндекс Маркета на 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 такое тоже наверняка есть, да?