Обычно у рекомендательных сервисов есть главная метрика, которую они пытаются растить, 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 и что вообще думаете про метрики верхнего уровня для рекомендаций?

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

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

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

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

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

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

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

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

Какие недостатки у Mixigen 1.0?

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

Хотелось перейти к принципу, который я описывал в серии постов об измерении качества генерации кандидатов:

Главная задача ранних стадий состоит в том, чтобы найти наилучшие документы с точки зрения финального ранжирования.

Второй недостаток: часто высказывалась мысль о том, что фиксированные веса для всех источников — это недостаточно гибко. Например, для холодных пользователей не очень хочется брать много кандидатов из матричного разложения, которое про этих пользователей почти ничего не знает, а можно просто взять больше популярных объектов. И продуктовые команды начинали сами сегментировать все запросы и на разных сегментах запускать отдельные версии Миксиджена. Трудоемко и не оптимально.

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

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

В новой версии модель Миксиджена оценивает про каждого кандидата, насколько он понравится финальному ранжированию. При этом модель может использовать все запросные фичи, а про кандидатов — только их источник и позицию в этом источнике. В качестве таргета берём ранг в финальном ранжировании или бинарную метку — попал ли в итоговый список порекомендованного. Лучше обучаться в listwise режиме (например, с cross entropy loss), потому что таргет зависит не только от самого кандидата.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#lifestories

Кирилл @inforetriever недавно в подкасте затронул тему сравнения нейросетевого ранжирования со старым добрым градиентным бустингом. Я когда-то тоже хотел про это написать.

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

К концу моей работы в Яндексе наша команда была в ситуации, когда по офлайн-метрикам мы смогли сравнять качество несложной нейросети и CatBoost на одном и том же датасете. В онлайн, правда, не решились запускать, потому что для этого нужны были инфраструктурные изменения. Но у меня было предчувствие, что когда-нибудь надо будет переходить на нейросети полностью и забыть про родной Катбуст. Я тогда для себя выделил 4 критерия для этого:
- Качество модели
- Скорость обучения
- Скорость (и стоимость) инференса
- Тулинг (feature importance, feature selection, etc.)

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

Затем в Майкрософте я застал попытку замены GBDT (LightGBM) на нейросети. Но делали это настолько странно, с некорректными сравнениями и без хорошего бейзлайна, что смысла в этом было мало. Не удивлюсь, если в итоге они всё равно это так и внедрили. Но оптимизма это не прибавило.

А затем я перешёл в X, и тут уже всё полностью на нейросетях. И GBDT уже не может их догнать.

Так что теперь могу сравнить эти два мира, побывав и там, и там.

- Качество модели. Допустим, мы сравниваем в одной и той же постановке: одинаковые фичи, одинаковые таргеты и лоссы. По предыдущему опыту, бустинг насыщается примерно на десятках или сотнях миллионов сэмплов (наверно, это зависит от числа фичей и чего-то ещё). А нейросети — нет. И если у вас есть больше, скажем, миллиарда сэмплов в обучении, то нейросети уже оказываются лучше. А если нет, то лучше действительно оставаться на бустинге, наверно.
- Но если вспомнить, что нейросети более «нативно» поддерживают спарс-фичи и их можно учить end-to-end (а не отдельно матричную факторизацию, которую потом вставлять фичами в бустинг), то они ещё сильнее вырываются вперед по качеству.
- Часто в задаче нужно предсказывать несколько таргетов: клики, конверсии, лайки и т.д. В нейросетях можно применить multi-task learning, который тоже может улучшить качество.
- Скорость обучения. Да, на фиксированном датасете обучить модель с нуля для нейросетей дольше — несколько дней против нескольких часов в бустинге. Но в реальной жизни мы же делаем постоянное дообучение. Для бустинга (из-за full batch optimization) для этого нужно каждый раз собирать большой датасет и заново обучать на нем. А нейросети можно дообучать только на новых данных — небольшой дельте. И тут бустинг начинает уже проигрывать.
- Отдельно стоит упомянуть возможность обучения в реальном времени. Впрочем, без end-to-end обучения и спарс-фичей (user_id и item_id) это и не особо важно.
- Скорость и стоимость инференса. Тут бустинг выигрывает. Но не катастрофически. Всё равно часто в продакшене какие-то нейросети в онлайне применяют (хотя бы user tower для генерации кандидатов). И ещё иногда (если у компании много денег) можно разменять скорость на стоимость и перейти на GPU inference.
- Тулинг. Тут всё похуже, не так удобно, как с Катбустом. А некоторые вещи вообще не понятно, как делать за вменяемое время (например, feature evaluation).
- В целом, нейросети более гибкие. Есть много примеров, что в них дополнительно можно делать и при этом нельзя (или совсем не тривиально) делать в бустинге. Например, разный debiasing через представление модели в виде суммы двух совместно обучаемых.

Если суммировать, то для масштабного сервиса явный выигрыш за нейросетями.

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

Давно веду канал, а так до сих пор и не написал про метрики ранжирования.

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

В то же время, как известно, all models are wrong, but some are useful. И на практике все используют какие-то метрики для оценки качества моделей на исторических данных. Это позволяет хоть как-то сравнивать модели между собой, выбирать наиболее перспективные, подбирать гипер-параметры и запускать их в онлайн-эксперимент, в котором мы уже узнаем правильный ответ (на самом деле — тоже не совсем).

Если говорить про конкретные метрики (их формулы), есть разные варианты. Но они не очень сильно отличаются друг от друга, и я считаю, что можно всё упростить и считать, что есть более-менее одно семейство метрик — DCG. Многие другие метрики (например, HitRate, Recall@k, MRR) — это всё частные случаи.

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

Очень часто используют нормированный вариант метрики — NDCG. Но на самом деле это чаще вредит, чем помогает. Если релевантность не бинарная (например, у клика вес 1, у лайка — 10), то NDCG забудет про разные веса, когда они не в одной группе. Т.е. поставить на первое место лайк в одной группе или клик в другой — для NDCG одно и то же.

Ещё один частный случай метрики, который лично я часто использовал на практике — это AUC. Почти тот самый всем известный ROC AUC, только посчитанный не сразу для всех примеров, а отдельно для всех групп, а потом усредненный между группами. У AUC есть хорошая интерпретация — это доля правильно отранжированнах пар объектов с разными таргетами. Если использовать эту интерпретацию, то можно даже убрать ограничение на бинарность таргета. И если задуматься, то такой AUC — тоже частный случай DCG (точнее, NDCG), просто с линейным дисконтированием.

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

Например, не стоит включать в примеры те объекты, которые мы порекомендовали, но пользователь не увидел. Мы не знаем реакцию пользователя на них.

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

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

Эта ошибка не всегда критична, но чем более продвинутая модель будет оптимизировать такую неправильную метрику, тем сильнее эта проблема будет проявляться.

С начала 2012 года (где-то в период «map к новому году») я начал заниматься одним из любимых видов спорта (чем-то напоминающим спортивное программирование) — хождением по собеседованиям. В ту пору бигтех-компании периодически приезжали в Москву с hiring event-ами. Сначала я успешно прособеседовался в Бинг (и отказался потом от оффера). А вот с Амазоном у меня не получилось. Во-первых, в этот раз они прицельно нанимали в AWS, а я на каждом собеседовании на вопросы общего характера отвечал, что хотел бы заниматься ML. Во-вторых, я провалил оба систем-дизайна (не уверен, что он тогда уже так назывался): не спроектировал ни систему парковки, ни диспетчеризацию лифтов. Даже не понял, что вообще от меня хотят. И очень негодовал от таких бессмысленных секций.

И я, и многие мои знакомые действительно воспринимали это как вид спорта. Но параллельно я попробовал пойти за своей старой мечтой и собеседоваться в Гугл — уже с серьёзными намерениями. Тогда ещё был офис в Москве.

Месяца через три меня обрадовали оффером. А я «обрадовал» Макса и Лену Бунину тем, что хочу уходить. Макс понимал, что меня надо отпустить из команды YT (на самом деле, его и самого в это же время хантили в Гугл). Но Лена не была готова отпустить меня просто так из Яндекса и попыталась найти мне более удачное место.

Несколько недель я встречался с разными командами Яндекса, а также несколько раз ездил в офис Гугла, чтобы узнать, что же конкретно мне предлагают там.

Среди команд в Яндексе чего-то зажигательного для меня не нашлось.

А вот в Гугл меня звали в команду Пети Митричева (первая ракетка мира в спортивном программировании на тот момент). Но только на вопрос, каким проектом я буду там заниматься, всё, что мне смогли ответить: это проект, связанный с ML. И на вопрос, хотя бы на каком языке надо будет программировать, ответили, что в Гугле, как известно, используют C++, Java и Python (Go тогда ещё не было), поэтому — «на каком-то подмножестве из этих трёх языков». Ладно, потом Петя сжалился и раскрыл страшный секрет, что Java в этом подмножестве нет.

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

Но Волож, прочитав его, высказал только претензию Лене:

Почему у вас сильные разработчики занимаются какой-то фигней, а не качество поиска улучшают?

А могли бы сейчас жить в мире с нормальной системой рекомендаций!

И всё-таки Лена смогла найти одну команду, которая как раз в перспективе хотела заниматься рекомендациями — рекомендациями фильмов.

Настал первый в моей карьере момент серьёзного выбора — выбора 2012. Пойти в компанию мечты, в сильную команду, но заниматься неизвестно чем на «каком-то подмножестве из трёх языков», или же остаться в Яндексе и заниматься задачей, о которой давно мечтал.

Компания мечты или задача мечты?

Я выбрал задачу.

Кажется, не прогадал. Но A/B-тестов в нашей жизни не бывает. Поэтому могу только сказать, что не жалею о своём выборе.

#lifestories

Канал Коли, из которого два предыдущих поста, обещает быть интересным.

Когда я уходил из Яндекса почти три года назад, Коля приходил (возвращался) практически как моя замена. С тех пор служба рекомендательных технологий выросла раза в два и продолжает демонстрировать весьма достойные результаты.

Экс-Экс

Многие из вас могут помнить, как почти год назад я расписывал, насколько классно мне работалось в X.

И вот, это путешествие подошло к концу — я больше не работаю в Х.

Сейчас у меня небольшой отдых, а что будет дальше — stay tuned.

На этой неделе я начал работать в организации-которую-нельзя-называть-без-звёздочки.

По многим аспектам новый работодатель кажется полной противоположностью предыдущего. Например, по размеру.

От области рекомендаций я ушёл совсем недалеко: буду заниматься рекламой. Причём одной из моих любимых тем — long-term value optimization.

Мой менеджер пытался меня нанять ещё с 2021 года. На третий раз я всё-таки согласился 😊

Регрессия и распределение шума

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

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

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

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

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

Но у этих подходов есть проблема — они не mean-proper. Mean-proper функции ошибок — это у которых минимум достигается, когда предсказание равно матожиданию таргета. Например, L2 (MSE) или Binary Cross-Entropy (в случае бинарных таргетов) — mean-proper. А вот L1 (MAE), MAPE, MSE логарифмов — нет. Попросту говоря, при использовании таких лоссов предсказания будут смещенными. Я когда-то уже писал про это для логарифмов.

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

Поэтому я к этим трюкам с преобразованием таргета всегда относился скептически — не хочется терять калиброванность из-за того, что шум как-то не так распределен. И вообще, казалось бы, как бы ни был распределен шум, практика нас обычно учит: что вы хотите улучшить на test set — то и оптимизируйте на train set. Хотите MSE — используйте MSE. Просто разные лоссы ведут к разным компромиссам, когда не получается точно описать данные. Так ведь?

Оказалось — нет. За последние несколько дней я провёл небольшой эксперимент на искусственных данных. Пусть у нас одномерный случай, x распределен равномерно на [0, 1], «настоящая» зависимость выглядит как z = exp(a*x + b), а наблюдаемые таргеты сэмплируются не из нормального, а из экспоненциального распределения с матожиданием z(x). Обучаем модель y_pred = exp(a*x + b), т.е. просто подбираем параметры a и b по датасету, используя либо обычный L2 loss, либо специальный экспоненциальный лосс log(y_pred) + y / y_pred — это negative log-likelihood экспоненциального распределения (он тоже mean-proper!).

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

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

Эксперимент показал, что лосс, адаптированный к настоящему распределению шума, ведёт именно к лучшей генерализации — а не просто к другому компромиссу.

Иллюстрация (cherry-pick) — ниже. Типичная чувствительность L2 к выбросам.

P.S. Эксперимент выглядит очень простым. Но пока я его делал, я напоролся на несколько удивительных подводных камней. Оказалось, что использование
1) линейной зависимости z = a*x + b (без exp)
2) оптимизаторов Adam и (S)GD
3) mean(x) ± 2 * std(x) / sqrt(N) в качестве доверительного интервала среднего
— всё это делает эксперимент очень нестабильным. Угадайте, почему 😉