Ещё год назад я слышал, что ТикТок начал заменять людям поиск. Тогда я очень удивился — казалось бы, где поиск, а где короткие видео. И вот недавно вышла статья на The Verge ровно об этом. Спойлер: нет, весь поиск ТикТок не поглотит. Но в некоторых сценариях (что посмотреть, где поесть, DIY) контент, визуальность и простота интерфейса перевешивают неидеальное качество поиска и замкнутость системы.

Я сам уже давно разным знакомым высказывал мысль, что ТикТок скоро завоюет мир. Если пару лет назад он казался помойкой для подростков, год назад эта помойка начала затягивать, то сейчас он мне рекомендует видео про изучение английского, про работу в корпорациях и лидерские качества, даже про gRPC vs REST, и что расширение вселенной превышает скорость света. Жаль, ещё про ML/DL не встречал. Но думаю, дело не за горами. Не вижу серьёзных причин, почему бы через год-два по всевозможным интересным темам не было бы контента в формате коротких видео. И новости могли бы уже быть в ТикТоке.

Единственное, что смущает со стороны сreator-ов, — снимать видео кажется сильно более напряжным занятием, чем писать текст или выкладывать фоточки (конечно, если пытаться делать это качественно). Поэтому вряд ли уж он совсем убьёт традиционные форматы.

Но за рекомендательную индустрию приятно 🙂

И ещё одна занятная статья с The Verge: дизлайки не работают. Речь про YouTube, хотя и про другие сервисы тоже. Т.е. если поставить дизлайк или даже “не рекомендуйте” какому-то видео, то оно действительно пропадёт из ленты рекомендаций. Но только оно, похожих видео не станет меньше.

Это хорошо согласуется с моим опытом: практически всегда, когда мы добавляли в фичи явные негативные сигналы, они почти никак не влияли. Оно и понятно — слишком уж они разреженные (хотя интересно, так ли это в Тиндере). А кроме того, не всегда очевидно, как на самом деле они должны влиять в теории: если пользователь поставил дизлайк одному объекту, означает ли это, что вероятность позитивного взаимодействия с похожимим объектами становится меньше? Я вот не уверен. Ведь чаще всего пользователь ставит дизлайки хотя бы в той теме, которая ему интересна.
Так что просто добавлять дизлайки в фичи без толку, по крайней мере, если не добавлять негативный сигнал ещё и в таргет.

С этим у меня ещё связана такая история с незапамятных времен персонального радио на Яндекс.Музыке. Тогда наша основная модель обучалась по принципу ранжирования позитивных взаимодействий против 5 случайных негативов (сэмплированных по популярности, насколько я помню). Так вот, в какой-то момент обнаружилось, что если поставить дизлайк какому-то треку, то треки того же исполнителя якобы начинают ещё больше рекомендоваться. И на это начали жаловаться. Мы проверили — и правда, от дизлайка скоры треков того же исполнителя только увеличиваются. Разгадка оказалась простой. Если модели нужно выбрать прослушенный трек из группы ранжирования, в которой остальные треки случайные, и у одного трека из этой группы есть дизлайк на трек того же исполнителя, то к гадалке не ходи — этот трек и есть прослушанный.

Месяц назад читал статью про Power Law (также известный как закон Ципфа или распределение Парето — известный принцип “80 на 20”). Не поверите — эту статью мне тоже порекомендовал ТикТок!

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

- Для многих распространенных показателей степени (< 2) в этом распределении бесконечное матожидание. Т.е. в любой конечной выборке среднее будет, конечно, конечным (🙂). Но ни к чему сходиться оно не будет, закон больших чисел для такого не работает. И даже когда матожидание конечно, практически у всех примеров бесконечная дисперсия. В частности, это всё означает, что не надо, например, для измерения использовать метрики, которые распределены по power law. Впрочем, про этот факт я уже более-менее знал раньше.

- Когда-то я пытался проверить, как распределена одна важная метрика в сервисе, над которым работал, — не power law ли. Ну я помнил, что плотность распределения нужно построить в логарифмической шкале, и, если это действительно power law, то там будет видна прямая. Ну а как нарисовать плотность? Через гистограмму. Ну и дальше надо подбирать размеры бинов (например, тоже геометрически), чтобы красиво получилось. А дальше оказалось, что в том SQL-подобном инструменте, которым я тогда пользовался, гистограммы для плотностей строились неправильно (не нормировались на размер бина). Так вот, всё это было зря. В статье приведён простой факт, что нужно перейти от плотности распределения (или PMF для дискретного случая) к его функции распределения (CDF), и уже 1 – CDF нарисовать в логарифмическом масштабе, там-то и будет прямая. И никаких гистограмм, бинов и т.п., это всё будет и проще, и менее шумным.

- А ещё, чтобы оценить показатель распределения, хочется в том логарифмическом масштабе найти угол наклона прямой, приближающей плотность или 1 – CDF. И интуитивно тут сразу начинаешь пользоваться методом наименьших квадратов, т.к. он очень простой. Так вот, оказывается, он даёт в этом случае смещенный показатель распределения. (Минимизация суммы квадратов в логарифмической шкале закономерно влечёт за собой какое-то смещение.) А вместо этого надо просто воспользоваться формулой с Википедии (а для оценки погрешности — (alpha – 1) / sqrt(n) ).

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

Начну с примера из личного опыта. Когда-то я занимался проектом по прогнозированию некоторого 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%")? Как вы считаете?