Ещё год назад я слышал, что ТикТок начал заменять людям поиск. Тогда я очень удивился — казалось бы, где поиск, а где короткие видео. И вот недавно вышла статья на 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-эффект.

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