Месяц назад мне скинули ссылку на выступление от Яндекс Маркета на 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 сам решит, полезный ли он или его можно выкинуть. В следующем посте опишу недостатки этой первой версии алгоритма и вторую версию, которой я до сих пор немного горжусь.