Ну, тогда — по просьбам читателей.

Начну с примера из личного опыта. Когда-то я занимался проектом по прогнозированию некоторого value (скажем, денег), которое нам будут приносить пользователи за определенный период в будущем. Если посмотреть на распределение этой величины по пользователям, то оно получается очень сильно перекошенным. Существенная часть пользователей приносили 0, а у остальных распределение было похоже на логнормальное. (Кстати, на практике оказалось полезным независимо предсказывать вероятность того, что value будет больше 0, и матожидание этого value при условии его положительности, а потом перемножать.)

Получается, что при обучении модели в обычном режиме (с MSE-лоссом) мы штрафуем модель за предсказание 1 вместо правильного ответа 2 и за предсказание 99 вместо правильного ответа 100 одинаково. И это, на первый вгляд, не очень интуитивно. Был великий соблазн прологарифмировать все таргеты и уже потом обучить модель, а при применении брать экспоненту от предсказания. Тогда как раз штраф за предсказание вдвое больше или вдвое меньше таргета будет одинаковым, независимо от таргета. Так вот, так делать нельзя. Если так сделать и потом, например, просуммировать экспоненты от предсказаний для всех пользователей, то получится заметно меньше, чем на самом деле. Мы, правда, по-моему, даже пробовать так не стали, заранее подумав про этот эффект.

Почему так? Всё очень просто. Когда модель обучается в режиме стандартной регрессии (т.е. с MSE-лоссом), то она в каждой точке пространства признаков пытается предсказать условное матожидание:

E(y|x)

. А если сделать этот “трюк” с логарифмированием, то мы получим

exp(E(log y|x))

. Экспонента — выпуклая функция, поэтому

exp(E(log y|x)) < E(exp(log y)|x) = E(y|x)

. Т.е. такое предсказание будет заниженным.

Если совсем на примере показывать, то представьте, что в одной и той же точке пространства (т.е. с очень близкими фичами) есть два примера: один с ответом 1 и один с ответом 4. Если сначала прологарифмировать, то получим таргеты 0 и 2 (будем считать, что логарифм двоичный, ну или можно умножить на

ln 2

). Тогда модель в этой точке будет предсказывать их среднее, т.е. 1 (конечно, если у неё достаточно свободы). И при возвращении к исходной шкале будет 2. Хотя понятно, что несмещенным было бы предсказание (1 + 4) / 2 = 2.5.

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

Как известно, экзамен прошёл хорошо — это когда ты не просто его сдал, но ещё и узнал на нём что-то новое.

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

А вопрос был такой. Вот есть много моделей для рекомендаций (и не только), которые устроены как произведение эмбеддинга пользователя/запроса на эмбеддинг объекта/документа. Матричная факторизация, например. Или two tower neural networks (их ещё не очень корректно называют DSSM в определенном кругу 😉). Вот рассмотрим последние. В качестве операции произведения этих эмбеддингов можно использовать dot product (скалярное произведение) или косинус. Так вот и вопрос — что лучше, dot product или косинус?

Опыт в Яндексе у нас был не всегда однозначный — иногда косинус работал стабильнее для обучения, потом вроде бы и dot product стал нормально обучаться и чуть лучше работать. У косинуса же ограниченная область допустимых значений (даже если после этого применяется афинное преобразование), а это не очень хорошо. Но вопрос оказался не совсем про это — т.е. не про качество предсказания самой модели. А про какое-то дополнительное использование обученных эмбеддингов документов. Например, для составления быстрого индекса или для кластеризации. Но и тут я тоже не очень понял, в чём может быть проблема. Для косинуса это вроде попроще, но и для dot product вполне работает (по крайней мере быстрый индекс).

А теперь представим модель, обученную с dot product. Первую координату у всех документных эмбеддингов умножим на большую константу (скажем, 1000), а у всех пользовательских — разделим на эту же константу. Результат произведения не поменяется, т.е. качество предсказания модели не изменится. Однако, если мы будем измерять расстояния между документами (а это обычно тоже через произведение/косинус делается), то всё будет определяться только лишь этой первой координатой, у всех остальных будет сильно меньший масштаб. И значит, кластеризация таких документов будет работать очень плохо. Понятно, что во время обучения модель не будет какую-то координату умножать на такую большую константу. Но в процессе градиентного спуска все координаты (а точнее, направления в этом пространстве) каким-то случайным образом растянутся. Пользовательские эмбеддинги адаптируются к таким растяжениям, но междокументные расстояния — нет.

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

Если кто-то на практике это проверял, расскажите в комментариях.

Попытаюсь прервать тишину здесь.
Начну с рекомендации канала: @knowledge_accumulator
В последних двух постах Саша там рассказывает про проблему RL в рекомендациях. А точнее, про удручающее состояние научных публикаций в этой области.
К счастью, это не помешало нам с Сашей в своё время в этом как-то продвинуться :)
Вообще, на мой личный вкус, это самая привлекательная область в рекомендациях. (Даже круче трансформеров.)
Ведь основная сложность и отличительная черта рекомендаций — как раз в том, на что именно обучать модели, т.е. что принимать за ground truth. И пока что только RL может предложить достаточно фундаментальный подход. Осталось только научиться реализовывать это на практике. Но я верю, что до этого осталось не так много.

Про счётчики.

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

Часто счётчики — это первое, что используют для рекомендаций. (Ну, иногда начинают с какой-нибудь матричной факторизации.) Возникли они как попытка скормить в традиционные модели категориальные фичи (user ID, document ID, topic, ...). Но и сейчас, в эпоху нейросетей, которые сами хорошо умеют использовать категориальные фичи (моделируя их эмбеддингами), счётчики всё ещё продолжают быть очень полезными, даже необходимыми. Просто потому, что они дешевле в обработке: во-первых, их можно посчитать за очень длинный период (тогда как обучать нейросеть за тот же период может быть слишком затратно), во-вторых, их легко обновлять в реальном времени (а обновление нейросетей в реальном времени — довольно сложная вещь, в лучшем случае их обновляют в near real-time, т.е. с какой-то существенной задержкой от реального времени).

Счётчики полезно считать за разные периоды времени — час, день, неделя, месяц и т.д. Ведь если пользователь, например, раньше никогда не интересовался какой-то темой, а в последний день заинтересовался, то это довольно полезный сигнал. А для документов соотношение счётчиков за разные периоды выражает тренды.

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

Обновление обычных счётчиков за конечный период не слишком-то простое. В офлайн-обработке иногда просто заново вычисляют значение за новые период. В realtime же нужно вычесть количество старых событий, выпадающих из окна расчёта, и добавить новые. Чтобы вычитать, нужно хранить все эти старые события, ну или хотя бы их агрегаты за более мелкие периоды (например, за каждые 5 минут или полчаса). Экспоненциальные счётчики же обновлять очень просто: NewCounterValue = OldCounterValue * 2^(-(CurrentTime - LastUpdateTime) / HalfLife) + EventValue
Вместо конечного окна агрегации используется HalfLife — период полураспада, т.е. время, за которое счётчик уменьшается вдвое, если ничего нового не происходит. Для обновления не надо ничего дополнительного хранить, кроме времени последнего обновления. Математическим языком это называется индуктивной функцией — нужно знать только добавленный элемент и старое значение функции. При этом выразительность экспоненциальных счётчиков (т.е. полезность для модели) обычно не меньше обычных, а иногда даже больше.

В следующем посте обсудим ещё одно улучшение счётчиков.

Как улучшить CTR-фичи

Рассмотрим самый стандартный пример — CTR документа. Он вычисляется как число кликов (clicks), деленное на число показов (impressions). Как обсудили в прошлом посте, вместо обычного числа кликов и показов лучше использовать экспоненциально затухающие. Кроме того, и числитель, и знаменатель стоит сглаживать. Но сейчас не об этом, а о том, как снизить влияние разных смещений.

CTR сильно подвержен разным смещениям, в частности — position bias. Представьте себе документ, который получил 10 показов на самом видном месте и из них — 3 клика, и другой документ, получивший 10 показов внизу или сбоку страницы, да ещё и меньших размеров, и из них — 2 клика. Какой из документов лучше априори?

Таким образом, показы бывают «плохие» и «хорошие», и хочется их учитывать с разным весом. В information retrieval для этого давным-давно придумали CoEC — clicks over expected clicks. Как и следует из названия, дробь clicks / impressions заменяется на clicks / (expected clicks). Expected clicks — это сумма по всем показам документа априорной (т.е. независящей от документа) вероятности клика. Если документ получил больше кликов, чем ожидалось по этим показам, то это хороший документ, если меньше — то плохой. Средний документ имеет CoEC = 1.

Как оценивать эту априорную вероятность? Есть разные варианты. Скажем, если не учитывать ничего, а просто взять глобальный средний CTR, то знаменатель будет просто пропорционален числу показов, т.е. итог будет эквивалентен обычному CTR документов. Но если учесть позицию, то станет уже заметно лучше. Для этого нужно посчитать click curve — априорную вероятность клика при показе на каждой позиции. (Как это сделать несмещенно — оставим до следующих постов.)

Это и есть самый популярный вариант CoEC. Он позволяет бороться с position bias для таких фичей. В качестве позиции, конечно, можно брать не просто номер, но и обобщённое понятие: положение на странице, размеры, что за страница, на каком устройстве, и т.д. Главное — уметь посчитать click curve. Но можно пойти и ещё дальше: кроме позиционной информации, учитывать и другие фичи. Например, бывают активные пользователи (clickers) и пассивные (non-clickers). Какому пользователю показали документ — сильно влияет на expected clicks. Можно доводить эту идею до конца и использовать вообще все фичи, независящие от документа. Но насколько это практично — я не знаю, ведь для этого нужно поддерживать отдельную модель вероятности клика.

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

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

От счётчиков к линейным моделям

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

Итак, начнём с самого простого — линейной модели на двух категориальных фичах: user_id и item_id. Таргет тот же, что и обычно в нашей задаче, например, был ли клик на показанный документ. Лосс-функция — либо MSE (линейная регрессия), либо binary log-loss (логистическая регрессия). Последняя обычно работает лучше. И, конечно, регуляризация.

Что выучит данная модель? Во-первых, глобальный сдвиг, соответствующий среднему CTR. Во-вторых, веса для каждого пользователя и документа. Если добавлять в модель другие фичи (категории документов, сегменты пользователей, дни недели и т.д,), то и для них получим соответствующие веса. И тут прослеживается аналогия с счётчиками: вместо явным образом посчитанных CTR мы получаем веса в линейной модели. Причём свойства похожие: чем лучше объект, тем выше у него будет CTR и тем выше вес в линейной модели.

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

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

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

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

Стоит ли использовать в современной рекомендательной системе линейные модели или сразу же переходить к более мощным (factorization machines или сразу neural nets) — вопрос неоднозначный. Но по крайней мере, чтобы использовать более сложные модели, вам в любом случае нужно будет решить все сложности, которые есть у линейных.

SLIM

Продолжая пост про линейные модели, сегодня разберём один частный случай такой модели — Sparse Linear Methods (SLIM).
Чем примечателен этот метод:
1. Он простой.
2. Модель получается интерпретируемой (а значит — легко отлаживаемой).
3. Он достаточно эффективен, модель обучается быстро (но это, конечно, зависит от размеров задачи).
4. При этом качество рекомендаций получается очень даже пристойное. Этот метод может служить хорошим бейзлайном для других методов. Более того, в 2019 году вышла статья с обзором алгоритмов рекомендаций, опубликованных за последние три года. Оказалось, что при правильном сравнении большинство этих алгоритмов проигрывают SLIM. К этой статье, впрочем, тоже надо относиться с определенным скепсисом, но тем не менее.

А суть метода следующая. Рассмотрим две фичи (точнее, две группы фичей, или неймспейсов, в терминологии Vowpal Wabbit). Первая — категориальная — id оцениваемого объекта. Вторая группа — объекты, с которыми пользователь положительно взаимодействовал (кроме того же самого объекта). И теперь возьмём кросс-фичи — произведение этих двух групп. Получим фичи такого вида: [сейчас мы оцениваем объект i, в истории пользователя встречается объект j]. И вот на таких кросс-фичах обучаем линейную модель. Таргет — 1, если было положительное взаимодействие, 0 во всех остальных случаях (даже если объект не показывали пользователю). MSE loss, регуляризация L1+L2 (как в elastic net). И добавим ограничение, что веса в модели должны быть неотрицательными.

В матричном виде это ещё проще: минимизировать

1/2 ||A - AW||^2 + beta/2 ||W||^2 + lambda ||W||_1

с ограничением W >= 0, diag(W) = 0, где A — матрица "рейтингов" (чаще всего рассматривают бинаризированные рейтинги, т.е. было ли позитивное взаимодействие), а W — оптимизируемая квадратная матрица весов. ||W||_1 — L1-норма, т.е. сумма модулей, нужна для разреженности. И чем больше lambda, тем меньше ненулевых весов будет и тем быстрее будет проходить оптимизация. Также стоит заметить, что для каждого столбца матрицы W это независимая задача, поэтому оптимизацию можно распараллелить.

В итоге получается модель, которая делает предсказание для каждого объекта в виде суммы положительных весов для похожих объектов из истории пользователя. Чем больше вес, тем больше объекты похожи друг на друга. Это и придаёт модели интерпретируемость — она сама объясняет свои же рекомендации через объекты из истории.

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

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

Как обратная сторона медали: с помощью этого метода не получится продемонстрировать "магию искусственного интеллекта", нельзя вызвать wow-эффект.

Магия противоречит интерпретируемости.

Я завёл английскую версию этого канала, чтобы англоговорящие коллеги тоже могли читать. Решил это сделать в виде блога на Medium: https://roizner.medium.com/.

В ближайшее время он просто будет "догонять" этот канал, переводя большинство постов с самого начала. А здесь буду продолжать с прежним темпом. Так что не отключайтесь :)
Посмотрим, где в итоге популярность и содержательность обсуждения будут выше.

В индустрии в рекомендательных системах очень часто возникают ситуации, когда есть доступ к каким-нибудь внешним эмбеддингам и хочется их наиболее эффективно использовать. "Внешними" я называю такие эмбеддинги, которые обучают без привязки к рекомендательной задаче. Например, по тексту документа можно вычислить BERT или по картинке можно вычислить свою нейросеть. Да и у пользователя откуда-то может взяться внешняя информация (скажем, из его поведения на другом сервисе), представленная в виде эмбеддинга. Задача симметричная, поэтому дальше будем представлять, что эти внешние эмбеддинги именно у документов.

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

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

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

Этот метод обычно даёт результаты чуть лучше, чем простая агрегация. Но и цена выше. Тут прямая аналогия с обычными линейными моделями (без эмбеддингов) и счётчиками.

3. Наконец, можно использовать нейронную модель, принимающую на вход историю пользователя. (Если такой модели у вас ещё нет, то очень советую завести. Конечно, при условии, что базовые проблемы в вашей системе уже решены.) История пользователя переводится в эмбеддинги, которые потом агрегируются (attention, рекуррентно или просто pooling-слоями). На входе это история представляется либо каким-то описанием документов (контента), либо просто id, либо их комбинацией. Так вот, это описание можно обогатить внешними эмбеддингами. (Можно и новую модель использовать, а не имеющуюся обогащать.)

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

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

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

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

Правила — это техдолг.

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

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

Мораль — не скупитесь на сильных инженеров 🙂

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

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

Мы будем здесь рассматривать последнюю стадию ранжирования — когда осталось уже не слишком много документов (скажем, от нескольких десятков до пары сотен) и мы хотим из них набрать наилучший набор. Эта стадия примечательна тем, что мы пытаемся не просто как можно точнее оценить каждый документ в текущем контексте, но и учитывать сочетаемость документов друг с другом. Именно в этот момент начинается listwise-ранжирование (не путать с listwise-обучением для learning-to-rank, в котором только лосс-функция зависит от всех документов в запросе, но не ранжирующая функция). Типичное применение этого listwise-подхода — повышение разнообразия выдачи.

Вот основные принципы подхода.

1. Мы будем строить выдачу итеративно от первой позиции до последней. На каждой итерации мы будем выбирать наилучший (в каком-то смысле) документ для очередной позиции. Более-менее все подходы к переранжированию, которые я знаю, включая известный алгоритм разнообразия DPP, именно так и работают. Если выдача имеет нелинейный вид, то позиции можно упорядочить по значимости.

2. На каждой итерации мы берём все оставшиеся документы и сортируем их по некоторой функции полезности, value function. Это может быть как нечто простое, вроде выхода кликовой модели, до более сложного: комбинация нескольких выходов модели (или нескольких моделей), предсказывающих разные события, компоненты разнообразия (сходство с предыдущими документами), ручные бусты и т.д. Value function может перевычисляться на каждой итерации и поэтому — зависеть от позиции и от уже набранных в итоговую выдачу документов. Она должна относительно быстро вычисляться. Правильный дизайн такой функции — отдельная богатая тема, фреймворк это никак не ограничивает (и поэтому не снижает сложности).

3. Продуктовые правила выражаются в таком виде: на подмножестве позиций X количество документов со свойством f должно быть не меньше или не больше порога C. Обычно X — это начальный отрезок позиций, например от 1 до 10 (первая страница). Свойство f лучше всего выражать пороговым правилом какой-то фичи, т.е. [feature(doc) > threshold]. Если требуется, можно этот формат обобщить и до небинарных свойств.

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

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

Вот несколько примеров правил в таком формате:
- Количество подписок во всей выдаче должно быть не меньше половины. При этом, если все документы из подписок уже прочитаны, то это правило невыполнимо и будет отброшено.
- Количество документов сомнительного качества на первых 10 позициях должно не превышать 2.
- Среди позиций от 10 до 20 должен быть хоть один документ из новой категории.

Стоит также заметить, что правила вида “на первых 10 позициях должно быть хотя бы 5 документов с каким-то свойством” будут приводить к тому, что на первых 5 позициях будут документы без этого свойства, а на следующих 5 — с ним. Чтобы сделать это более равномерно, надо добавить правила на промежуточные отрезки: на первых 2 позициях хотя бы 1, на первых 4 — хотя бы 2, и так далее.

Конечно, повышению debuggability и контролируемости системы сильно способствует логирование всех выполненных и невыполненных правил.

Во многих сервисах есть рейтинги объектов: товаров, фильмов, приложений, организаций на карте. Как их правильно считать? Вопрос не такой простой, как кажется на первый взгляд.

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

Самая стандартная проблема — при простом усреднении всех оценок в топе рейтинга будут объекты с очень малым числом максимальных оценок. Если ваша задача — составить рейтинг лучших объектов, то проще всего рассмотреть только те объекты, которые получили не меньше какого-то числа оценок (100, 1000). Просто и действенно, хотя и на практике в топе всё равно могут оказаться объекты с лишь немного бо́льшим числом оценок, чем этот порог.

Если же вы хотите аккуратно вычислять рейтинг для всех объектов, то самый популярный способ — сглаживание рейтинга. Вместо суммы, разделенной на количество:
(sum_of_ratings + smoother * prior_rating) / (num_of_ratings + smoother)
Smoother — параметр сглаживания, количество априорных, "виртуальных" оценок. Prior rating — глобально средняя оценка. Если у объекта ещё нет оценок, он начинает с этой усредненной (априорной) оценки, С течением времени он набирает всё больше оценок, и такой сглаженный рейтинг становится всё ближе к простому усреднению. Иногда сглаживание добавляют только в знаменатель, забывая про числитель. Это не совсем правильно, хотя и тоже работает (просто сильнее смещается в сторону популярных объектов).

У этого способа есть теоретическое обоснование. Те, кто знакомы с байесовской статистикой, его наверняка знают. Если для бинарной шкалы оценок предположить, что априорное распределение среднего рейтинга имеет вид бета-распределения (например, просто равномерного от 0 до 1, это частный случай), то апостериорное распределение тоже будет иметь вид бета-распределения. Матожидание этого распределения как раз и будет сглаженным средним всех оценок.

Ещё одна серьёзная проблема средних рейтингов — selection bias, или ошибка выжившего. Оценки ставят не произвольные пользователи, а несколько специфичные. Усредненная оценка имеет интерпретацию матожидания оценки произвольного пользователя при условии, что он поставит хоть какую-то оценку. Во-первых, сам факт оценки может быть скоррелирован с тем, что пользователя что-то задело, в позитивную или негативную сторону. Многие пользователи не будут ставить оценку, если их опыт был ожидаемо средним. Поэтому нам было бы интереснее более слабое условие: матожидание оценки при условии, что пользователь купил товар, посмотрел фильм, посетил заведение и т.д.

Но во-вторых, даже эта интерпретация имеет большую проблему. В топе глобального рейтинга будет много узких категорий: например, документальные фильмы и артхаус. Уж если пользователь посмотрел такой фильм, то вероятность высокой оценки заметно выше, чем в среднем. Просто мало кто смотрит. Поэтому на самом деле нам интересно матожидание оценки произвольного пользователя без какого-либо условия: как произвольный пользователь оценил бы этот объект?

Как же такое посчитать? Для этого существует техника, хотя и не столь популярная на практике: Inverse Propensity Scoring, или Inverse Probability Weighting. Смысл её в том, чтобы оценить вероятность каждого пользователя поставить оценку и после этого усреднять оценки с весами, обратно пропорциональными этой вероятности. Если пользователь имел очень маленький шанс поставить оценку, но всё же её поставил, то эта оценка учтётся с большим весом. К сожалению, для этого придётся поддерживать модель оценки этой вероятности, а кроме того, дисперсия посчитанного рейтинга достаточно высокая.

А вот отдельный вопрос, на который я так и не знаю правильный ответ: какой должен быть физический смысл у персонального рейтинга ("Этот объект вам подходит на XX%")? Как вы считаете?

Один из важнейших типов моделей в рекомендациях на данный момент — это двух-башенные (two tower) нейросети. Они устроены так: одна часть нейросети (башня) обрабатывает всю информацию про запрос (пользователя, контекст), другая башня — про объект. Выходы этих башен — это эмббединги, которые потом перемножаются (dot product или косинус, как уже обсуждалось в этом посте). Одно из первых упоминаний применения таких сетей для рекомендаций можно найти в очень хорошей статье про YouTube. Кстати, именно эту статью я бы сейчас уже называл классикой и наиболее подходящей для входа в область рекомендаций.

Чем характерны такие сети? Они очень похожи на матричную факторизацию, которая на самом деле является частным случаем, принимая на вход только user_id и item_id. Если же сравнивать с произвольными сетями, то это ограничение на позднее связывание (не давать входам из разных башен смешиваться до самого конца) делает двух-башенные сети крайне эффективными при применении. Чтобы построить рекомендации одному пользователю, нам нужно один раз посчитать запросную башню, после чего умножить этот эмбеддинг на эмбеддинги документов, которые обычно заранее предподсчитаны. Это очень быстро. Более того, эти предподсчитанные эмбеддинги документов можно сложить в индекс (например, HNSW), чтобы по ним быстро, не проходясь по всей базе, находить хороших кандидатов.

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

Сами башни могут быть довольно навороченными. Например, в пользовательской части можно использовать механизм self-attention для обработки истории (получится трансформер для персонализации). Но чем мы платим, вводя ограничение на позднее связывание? Конечно, качеством. В том же самом attention нельзя использовать объекты, которые мы сейчас хотим оценить/порекомендовать. А ведь хотелось бы для этого как раз обратить внимание на похожие объекты в истории пользователя. Поэтому сети с ранним связыванием обычно применяют на поздних стадиях ранжирования, когда осталось несколько десятков или сотен кандидатов, а с поздним (two tower) — наоборот, на ранних стадиях и кандидато-генерации.

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

Отдельный интерес составляет лосс, с которым обучают двух-башенные сети. В принципе, их можно обучать на любой лосс с любыми таргетами и даже иметь несколько разных для разных голов (с разными эмбеддингами в каждой башне). Но один интересный вариант — это обучение с softmax-лоссом на in-batch негативах. Для каждой пары запрос-документ из датасета берутся остальные документы в том же мини-батче и в паре с тем же запросом используются как негативы в softmax loss. Это очень эффективный вариант hard negative mining.

Но важно иметь в виду вероятностную интерпретацию такого лосса (далеко не все её понимают). У обученной сети
exp(score(q, d)) ~ P(q, d) / (P(q) * P(d)) = P(d | q) / P(d),
т.е. экспонента скора будет пропорциональна не априорной вероятности документа при условии запроса, а PMI, специфичности для запроса. Более популярные документы в среднем не будут рекомендоваться чаще такой моделью, потому что во время обучения они пропорционально чаще выступают и как негативы. Если использовать скор как фичу, то это даже хорошо, но вот для финального ранжирования и для кандидато-генерации это может приводить к очень специфичным, но плохим документам.

Тот же Google в статье предлагал с этим бороться с помощью logQ correction во время обучения. Мы же обычно делали это на этапе применения, а не обучения, — просто умножая на априорную вероятность документа P(d). Но мы так и не сравнивали эти подходы, а было бы интересно сравнить.

Есть такой алгоритм коллаборативной фильтрации Implicit ALS (IALS). Я про него уже упомянал. В донейросетевую эпоху это был чуть ли не самый популярный алгоритм. Его отличительная черта — эффективный "майнинг" негативов: все пары пользователь-объект без истории взаимодействия выступают негативами (с меньшим весом, чем настоящие взаимодействия). Причём, в отличие от настоящего майнинга, здесь негативы не сэмплируются, а на каждой итерации используются прямо все такие негативные пары. Такая implicit-регуляризация.

Как же это возможно? Ведь при разумных размерах задачи (количестве пользователей и объектов) негативов должно быть настолько много, что даже их перечисление будет дольше всего процесса обучения. Красота алгоритма в том, что, благодаря использованию MSE-лосса и методу наименьших квадратов, можно заранее (перед каждой полной итерацией) предпосчитать что-то отдельно для всех пользователей и отдельно для всех объектов и этого хватит для того, чтобы делать implicit-регуляризацию. Так удаётся избежать квадратичного размера. (За подробностями предлагаю обратиться к одной из моих любимых статей тех времён.)

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

Думал, думал и придумал! И пару недель ходил воодушевлённый, в ожидании того, как мы это попробуем вместо in-batch негативов.

А потом, конечно же (как это часто бывает в подобных случаях), прочитал в статье, что всё уже придумали за три года до этого. И снова Google. И потом они в той самой статье про logQ correction, про которую я уже говорил, показали, что softmax loss с in-batch негативами работает лучше, чем implicit-регуляризация.

Вот так мы смогли сэкономить и не проверять эту идею 🙂

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

Вслед за последними постами хочется осветить более общий вопрос.

А нужен ли вообще negative sampling для рекомендательных моделей?

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

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

Что происходит, когда мы обучаем модель только на настоящих показах? Происходит довольно сильный selection bias, и модель учится хорошо различать только те документы, которые показывались в данном контексте. На тех документах (точнее, парах запрос-документ), которые не показывались, модель будет работать сильно хуже: каким-то документам завышать предсказания, каким-то — занижать. Безусловно, этот эффект можно снизить, применяя exploration в ранжировании, но чаще всего — лишь частично.

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

Модели финального ранжирования в этом плане очень похожи на генерацию кандидатов, но есть важное отличие: они учатся на своих ошибках. Когда модель ошибается, завышая предсказания каким-то документам, эти документы показываются пользователям и после этого могут попасть в следующий датасет для обучения. Мы можем переобучить модель на новом датасете и снова выкатить на пользователей. Появятся новые false positives. И снова можно повторить сбор датасета и переобучение. Происходит такой своеобразный active learning. На практике всего нескольких итераций переобучения хватает, чтобы этот процесс сошёлся и модель больше не рекомендовала дичь. Тут, конечно, надо соизмерять вред от рандомных рекомендаций, иногда стоит как-то подстраховаться. Но в целом, negative sampling здесь не нужен. Наоборот, он может ухудшить exploration, заставляя систему оставаться в локальном оптимуме.

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

Когда-то мы прямо проверяли, что в качестве фичей обычный ALS работает лучше, чем IALS, но вот для генерации кандидатов его использовать не стоит.

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

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

Если же внешние и внутренние объекты совсем разные, то тут интереснее. Могут существовать статистические закономерности, которые можно выучить. Можно либо явным образом их искать ("пользователи, взаимодействующие с внешним объектом A, чаще других пользователей взаимодействуют с внутренним объектом B"), либо обучать модели, похожие на SLIM, — линейные с кросс-фичами [пользователь взаимодействовал с объектом A, мы оцениваем объект B].

Но всё-таки наиболее подходящим способом (хотя и несколько сложнее отлаживаемым), как мне кажется, являются двух-башенные сети. Ведь даже когда они обучаются без внешней истории, они не используют тот факт, что пространства объектов совпадают. Эмбеддинги объектов в левой и правой башнях всё равно полезно не делать связанными (shared), а обучать разными. Поэтому можно просто в пользовательской башне использовать внешнюю историю. Сеть всё равно в конце приведёт и пользователя, и рекомендуемый объект в общее семантическое пространство.

Можно обучить отдельную сеть для внешней истории или же просто добавить внешнюю историю как дополнительный сигнал на вход одной двух-башенной сети. Второй вариант, вероятно, более мощный, т.к. внешняя и внутренняя истории могут нетривиальным образом друг на друга повлиять (особенно если использовать self attention), Но его и сложнее обучать: сеть может просто "забить" на дополнительный, менее информативный и более шумный сигнал. Поэтому я бы начинал с первого варианта. К тому же, сильно проще проверить, что он выучивает что-то разумное.

Отдельный вопрос: а как именно использовать дополнительную модель с внешней историей? Есть несколько вариантов:
1) фичи в ранжирующей модели,
2) кандидаты,
3) продуктовые правила (бустить рекомендации от таких моделей),
4) более изощренные техники вроде модификации лоссов/таргетов ранжирования.

Я сильно рекомендую всегда начинать с пункта 1 — с фичей. Даже если это не самый эффективный способ, без него остальные варианты будут работать совсем не оптимально. Более того, зачастую они могут даже вредить системе.

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

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

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

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

Существуют разные подходы. Иногда качество просто не замеряют (ну или просто "на глаз") и системно не оптимизируют эту стадию. Иногда каким-то образом замеряют общую релевантность кандидатов. И если система порекомендовала что-то странное, то это считают багом в том числе и кандидато-генерации. Иногда эту релевантность даже противопоставляют тому, что оптимизируется в финальной стадии. Т.е. кандидаты должны быть уже достаточно релевантными (как бы это ни измерялось), а финальное ранжирование выберет из них наиболее engaging (привлекательные/кликабельные/...).

Иногда, особенно в статьях, используют метрики вроде HitRate@k, Recall@k, Precision@k, MRR, NDCG и т.д., фокусируясь только на положительных (релевантных) документах. При этом релевантным считается тот документ, с которым пользователь впоследствии взаимодействовал. Мне этот подход нравится больше предыдущих, хотя тут большая проблема с разными смещениями: например, пользователи чаще взаимодействуют с теми объектами, которые система сама же и рекомендует.

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

Подход основывается на таком принципе:

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

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

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

Этот принцип превращает кандидато-генерацию в довольно утилитарную задачу с вполне определенной целью. А вся сложность с objectives (какие таргеты и лоссы использовать) перекладывается на финальную стадию ранжирования.

Хотя этот подход и не идеален, лично я считаю его единственным состоятельным, т.е. только с ним можно долгосрочно системно улучшать качество всех стадий и не упереться в фундаментальную проблему. По крайней мере, я не понимаю, как это делать с другими подходами.

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