От счётчиков к линейным моделям
Линейные модели — это почти самое простое, что бывает в машинном обучении. Но не стоит их недооценивать. Они довольно универсальны, а их предсказательную силу можно увеличивать за счёт фичей. В этом посте — про одно из их применений в рекомендациях и про аналогию с счётчиками.
Итак, начнём с самого простого — линейной модели на двух категориальных фичах: 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) — вопрос неоднозначный. Но по крайней мере, чтобы использовать более сложные модели, вам в любом случае нужно будет решить все сложности, которые есть у линейных.
Линейные модели — это почти самое простое, что бывает в машинном обучении. Но не стоит их недооценивать. Они довольно универсальны, а их предсказательную силу можно увеличивать за счёт фичей. В этом посте — про одно из их применений в рекомендациях и про аналогию с счётчиками.
Итак, начнём с самого простого — линейной модели на двух категориальных фичах: 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) — вопрос неоднозначный. Но по крайней мере, чтобы использовать более сложные модели, вам в любом случае нужно будет решить все сложности, которые есть у линейных.
🔥11👍6❤3
SLIM
Продолжая пост про линейные модели, сегодня разберём один частный случай такой модели — Sparse Linear Methods (SLIM).
Чем примечателен этот метод:
1. Он простой.
2. Модель получается интерпретируемой (а значит — легко отлаживаемой).
3. Он достаточно эффективен, модель обучается быстро (но это, конечно, зависит от размеров задачи).
4. При этом качество рекомендаций получается очень даже пристойное. Этот метод может служить хорошим бейзлайном для других методов. Более того, в 2019 году вышла статья с обзором алгоритмов рекомендаций, опубликованных за последние три года. Оказалось, что при правильном сравнении большинство этих алгоритмов проигрывают SLIM. К этой статье, впрочем, тоже надо относиться с определенным скепсисом, но тем не менее.
А суть метода следующая. Рассмотрим две фичи (точнее, две группы фичей, или неймспейсов, в терминологии Vowpal Wabbit). Первая — категориальная — id оцениваемого объекта. Вторая группа — объекты, с которыми пользователь положительно взаимодействовал (кроме того же самого объекта). И теперь возьмём кросс-фичи — произведение этих двух групп. Получим фичи такого вида: [сейчас мы оцениваем объект i, в истории пользователя встречается объект j]. И вот на таких кросс-фичах обучаем линейную модель. Таргет — 1, если было положительное взаимодействие, 0 во всех остальных случаях (даже если объект не показывали пользователю). MSE loss, регуляризация L1+L2 (как в elastic net). И добавим ограничение, что веса в модели должны быть неотрицательными.
В матричном виде это ещё проще: минимизировать
В итоге получается модель, которая делает предсказание для каждого объекта в виде суммы положительных весов для похожих объектов из истории пользователя. Чем больше вес, тем больше объекты похожи друг на друга. Это и придаёт модели интерпретируемость — она сама объясняет свои же рекомендации через объекты из истории.
Этот метод можно несколько модифицировать. Например, учитывать позитивные взаимодействия только из прошлой истории (чтобы не рекомендовать пользователю телефон после покупки чехла). Но тогда нужно чуть-чуть сложнее негативы сэмплировать, не просто брать все. Можно убрать ограничение на неотрицательность весов (возможно, это немного снизит интерпретируемость). А можно рассматривать это просто как часть большой линейной модели.
Этот метод отлично работает, когда объектов в базе не очень много, скажем, тысячи или десятки тысяч (конечно, эти числа зависят от размера датасета). Например, для рекомендаций фильмов. Но и для "больших" задач это тоже полезно — ведь можно от документов перейти к их категориям, авторам и т.д.
Как обратная сторона медали: с помощью этого метода не получится продемонстрировать "магию искусственного интеллекта", нельзя вызвать wow-эффект.
Магия противоречит интерпретируемости.
Продолжая пост про линейные модели, сегодня разберём один частный случай такой модели — 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-эффект.
Магия противоречит интерпретируемости.
❤15👍4🔥2🎉1
Я завёл английскую версию этого канала, чтобы англоговорящие коллеги тоже могли читать. Решил это сделать в виде блога на Medium: https://roizner.medium.com/.
В ближайшее время он просто будет "догонять" этот канал, переводя большинство постов с самого начала. А здесь буду продолжать с прежним темпом. Так что не отключайтесь :)
Посмотрим, где в итоге популярность и содержательность обсуждения будут выше.
В ближайшее время он просто будет "догонять" этот канал, переводя большинство постов с самого начала. А здесь буду продолжать с прежним темпом. Так что не отключайтесь :)
Посмотрим, где в итоге популярность и содержательность обсуждения будут выше.
Medium
Michael Roizner – Medium
Read writing from Michael Roizner on Medium. ML/AI Engineer at Meta
👍11🔥5❤1
В индустрии в рекомендательных системах очень часто возникают ситуации, когда есть доступ к каким-нибудь внешним эмбеддингам и хочется их наиболее эффективно использовать. "Внешними" я называю такие эмбеддинги, которые обучают без привязки к рекомендательной задаче. Например, по тексту документа можно вычислить BERT или по картинке можно вычислить свою нейросеть. Да и у пользователя откуда-то может взяться внешняя информация (скажем, из его поведения на другом сервисе), представленная в виде эмбеддинга. Задача симметричная, поэтому дальше будем представлять, что эти внешние эмбеддинги именно у документов.
Я знаю 3 проверенных способа, как их использовать:
1) простая агрегация,
2) обучение двойственных эмбеддингов,
3) нейросетевая модель.
1. Агрегация. Берём историю пользователя (все взаимодействия какого-то типа) и как-нибудь агрегируем эмбеддинги соответствующих документов. Самый простой вариант — усредняем (предположим, все эмбеддинги заранее нормированные, иначе тут тоже могут быть разные варианты). Потом просто берём косинус между агрегированным и эмбеддингом ранжируемого документа в качестве фичи для ранкера. В более сложном варианте — считаем агрегацию косинусов между ранжируемым документом и документами из истории. Например, среднее, перцентили (включая максимум), долю или количество косинусов выше какого-то порога. Так можно выразить фичи такого вида: сколько этот пользователь уже лайкал или дизлайкал документы, похожие на данный по этому эмбеддингу. Как и со счётчиками, здесь полезно использовать не простое усреднение, а с экспоненциальным затуханием.
2. Обучение двойственных эмбеддингов. Иногда это называют "одна итерация iALS". Для тех, кто не знаком, ALS — это такой алгоритм матричной факторизации, который попеременно фиксирует вектора пользователей и документов и подбирает в это время оптимальные вектора второй части. А iALS — это ALS с дополнительной идеей, что в качестве негативов с меньшим весом используются все пары пользователь-документ, про которые нет данных о взаимодействии. Так вот, "одна итерация iALS" (точнее, половина итерации) заключается в том, что мы подбираем оптимальный вектор пользователя, который при умножении на зафиксированные внешние эмбеддинги документов будет предсказывать таргет. Если задуматься, то это просто ещё одно применение линейных моделей. Для каждого пользователя можно это делать независимо. Размерность модели равна размерности эмбеддингов. Таргеты, лоссы, веса — всё так же, как и в общем случае с линейными моделями.
Этот метод обычно даёт результаты чуть лучше, чем простая агрегация. Но и цена выше. Тут прямая аналогия с обычными линейными моделями (без эмбеддингов) и счётчиками.
3. Наконец, можно использовать нейронную модель, принимающую на вход историю пользователя. (Если такой модели у вас ещё нет, то очень советую завести. Конечно, при условии, что базовые проблемы в вашей системе уже решены.) История пользователя переводится в эмбеддинги, которые потом агрегируются (attention, рекуррентно или просто pooling-слоями). На входе это история представляется либо каким-то описанием документов (контента), либо просто id, либо их комбинацией. Так вот, это описание можно обогатить внешними эмбеддингами. (Можно и новую модель использовать, а не имеющуюся обогащать.)
Это более мощный подход. В каком-то смысле, модель и сама может посчитать разные агрегации, как метод 1, и может подобрать оптимальный вектор, как метод 2 или даже ещё лучше. Вообще, такие модели заслуживают отдельного обсуждения (в следующих постах).
В целом, на практике я бы тестировал пользу от внешних эмбеддингов именно в такой последовательности, 1->2->3. Каждый следующий метод сложнее предыдущего (это, конечно, зависит от того, насколько они у вас автоматизированы и отлажены), но потенциально даёт больше профита. При этом, если первый метод вообще не показывает профита, то вряд ли более сложный метод покажет.
Я знаю 3 проверенных способа, как их использовать:
1) простая агрегация,
2) обучение двойственных эмбеддингов,
3) нейросетевая модель.
1. Агрегация. Берём историю пользователя (все взаимодействия какого-то типа) и как-нибудь агрегируем эмбеддинги соответствующих документов. Самый простой вариант — усредняем (предположим, все эмбеддинги заранее нормированные, иначе тут тоже могут быть разные варианты). Потом просто берём косинус между агрегированным и эмбеддингом ранжируемого документа в качестве фичи для ранкера. В более сложном варианте — считаем агрегацию косинусов между ранжируемым документом и документами из истории. Например, среднее, перцентили (включая максимум), долю или количество косинусов выше какого-то порога. Так можно выразить фичи такого вида: сколько этот пользователь уже лайкал или дизлайкал документы, похожие на данный по этому эмбеддингу. Как и со счётчиками, здесь полезно использовать не простое усреднение, а с экспоненциальным затуханием.
2. Обучение двойственных эмбеддингов. Иногда это называют "одна итерация iALS". Для тех, кто не знаком, ALS — это такой алгоритм матричной факторизации, который попеременно фиксирует вектора пользователей и документов и подбирает в это время оптимальные вектора второй части. А iALS — это ALS с дополнительной идеей, что в качестве негативов с меньшим весом используются все пары пользователь-документ, про которые нет данных о взаимодействии. Так вот, "одна итерация iALS" (точнее, половина итерации) заключается в том, что мы подбираем оптимальный вектор пользователя, который при умножении на зафиксированные внешние эмбеддинги документов будет предсказывать таргет. Если задуматься, то это просто ещё одно применение линейных моделей. Для каждого пользователя можно это делать независимо. Размерность модели равна размерности эмбеддингов. Таргеты, лоссы, веса — всё так же, как и в общем случае с линейными моделями.
Этот метод обычно даёт результаты чуть лучше, чем простая агрегация. Но и цена выше. Тут прямая аналогия с обычными линейными моделями (без эмбеддингов) и счётчиками.
3. Наконец, можно использовать нейронную модель, принимающую на вход историю пользователя. (Если такой модели у вас ещё нет, то очень советую завести. Конечно, при условии, что базовые проблемы в вашей системе уже решены.) История пользователя переводится в эмбеддинги, которые потом агрегируются (attention, рекуррентно или просто pooling-слоями). На входе это история представляется либо каким-то описанием документов (контента), либо просто id, либо их комбинацией. Так вот, это описание можно обогатить внешними эмбеддингами. (Можно и новую модель использовать, а не имеющуюся обогащать.)
Это более мощный подход. В каком-то смысле, модель и сама может посчитать разные агрегации, как метод 1, и может подобрать оптимальный вектор, как метод 2 или даже ещё лучше. Вообще, такие модели заслуживают отдельного обсуждения (в следующих постах).
В целом, на практике я бы тестировал пользу от внешних эмбеддингов именно в такой последовательности, 1->2->3. Каждый следующий метод сложнее предыдущего (это, конечно, зависит от того, насколько они у вас автоматизированы и отлажены), но потенциально даёт больше профита. При этом, если первый метод вообще не показывает профита, то вряд ли более сложный метод покажет.
Telegram
Wazowski Recommends
Про счётчики.
Как известно, для ML-задач вроде рекомендаций очень популярной техникой являются счётчики в качестве фичей. Например, сколько раз пользователь кликал на документы с того же хоста. Или просто CTR документа (хотя это уже не один счётчик, а выражение…
Как известно, для ML-задач вроде рекомендаций очень популярной техникой являются счётчики в качестве фичей. Например, сколько раз пользователь кликал на документы с того же хоста. Или просто CTR документа (хотя это уже не один счётчик, а выражение…
👍13🔥6❤1
В реальных системах итоговые рекомендации строятся не только машинно-обученными моделями, но и с учётом некоторых эвристических правил. Их называют продуктовыми правилами, бизнес-правилами или просто костылями 🙂
Например:
- нельзя рекомендовать треки одного и того же исполнителя слишком часто;
- надо вставлять в ленту документы из подписок, но при этом не заполонять ими всю ленту;
- если пользователь уже дизлайкал какую-то категорию или автора, то соответствующие документы нужно пенализировать или вообще фильтровать;
- нельзя рекомендовать откровенный контент (кроме специальных случаев).
Правила бывают двух видов: жесткие и мягкие. Жесткие правила — это фильтры, они запрещают рекомендовать какие-то документы в каком-то контексте, иначе это будет восприниматься как баг продукта. В таких правилах нет ничего плохого. Их количество просто нужно ограничивать. Кроме того, их нужно применять на как можно более ранней стадии ранжирования (генерации кандидатов или даже построения индекса). Мягкие же правила имеют такой вид: рекомендовать такое можно, но нежелательно или не слишком много (или наоборот, рекомендовать такое надо больше). Если таких правил становится много, то отлаживать и развивать систему становится очень сложно.
Правила — это техдолг.
Количество таких правил в системе, как мне кажется, часто зависит от соотношения сил в команде: продактам удобнее выражать ограничения через правила, а инженеры обычно такие костыли не любят. В своей прошлой команде я гордился тем, что нам удавалось сводить количество таких правил к минимуму.
На своей практике я достаточное количество раз сталкивался с общим симптомом. У инженерной команды не получалось обучить систему так, чтобы рекомендации были хорошими (в целом или в каком-то конкретном аспекте). Продуктовой команде после этого ничего не остаётся, кроме как лечить такие проблемы тем способом, которым она умеет, — добавлением новых правил. Когда проблему нужно решать быстро, такие заплатки вполне оправданы. Но выпиливать их потом сложно. И система часто так и застревает в заплаточном состоянии, пока не произойдёт большой рефакторинг. Всё как с обычным техдолгом.
Мораль — не скупитесь на сильных инженеров 🙂
В идеальной системе таких правил быть не должно, всю нечёткую логику должна выполнять достаточно продвинутая модель. Я мечтаю, что когда-нибудь мы доживём до такого состояния технологий (и у меня есть гипотеза, как именно этого добиться). Но на текущий момент это малореалистично. Поэтому вместо того, чтобы полностью запрещать такие правила, в следующем посте я расскажу о подходе, который позволяет хоть немного их упорядочивать и ограничивать хаос.
(Я хотел и в этом посте написать про этот подход, но Телеграм ограничивает длину постов. Возможно, это и к лучшему.)
Например:
- нельзя рекомендовать треки одного и того же исполнителя слишком часто;
- надо вставлять в ленту документы из подписок, но при этом не заполонять ими всю ленту;
- если пользователь уже дизлайкал какую-то категорию или автора, то соответствующие документы нужно пенализировать или вообще фильтровать;
- нельзя рекомендовать откровенный контент (кроме специальных случаев).
Правила бывают двух видов: жесткие и мягкие. Жесткие правила — это фильтры, они запрещают рекомендовать какие-то документы в каком-то контексте, иначе это будет восприниматься как баг продукта. В таких правилах нет ничего плохого. Их количество просто нужно ограничивать. Кроме того, их нужно применять на как можно более ранней стадии ранжирования (генерации кандидатов или даже построения индекса). Мягкие же правила имеют такой вид: рекомендовать такое можно, но нежелательно или не слишком много (или наоборот, рекомендовать такое надо больше). Если таких правил становится много, то отлаживать и развивать систему становится очень сложно.
Правила — это техдолг.
Количество таких правил в системе, как мне кажется, часто зависит от соотношения сил в команде: продактам удобнее выражать ограничения через правила, а инженеры обычно такие костыли не любят. В своей прошлой команде я гордился тем, что нам удавалось сводить количество таких правил к минимуму.
На своей практике я достаточное количество раз сталкивался с общим симптомом. У инженерной команды не получалось обучить систему так, чтобы рекомендации были хорошими (в целом или в каком-то конкретном аспекте). Продуктовой команде после этого ничего не остаётся, кроме как лечить такие проблемы тем способом, которым она умеет, — добавлением новых правил. Когда проблему нужно решать быстро, такие заплатки вполне оправданы. Но выпиливать их потом сложно. И система часто так и застревает в заплаточном состоянии, пока не произойдёт большой рефакторинг. Всё как с обычным техдолгом.
Мораль — не скупитесь на сильных инженеров 🙂
В идеальной системе таких правил быть не должно, всю нечёткую логику должна выполнять достаточно продвинутая модель. Я мечтаю, что когда-нибудь мы доживём до такого состояния технологий (и у меня есть гипотеза, как именно этого добиться). Но на текущий момент это малореалистично. Поэтому вместо того, чтобы полностью запрещать такие правила, в следующем посте я расскажу о подходе, который позволяет хоть немного их упорядочивать и ограничивать хаос.
(Я хотел и в этом посте написать про этот подход, но Телеграм ограничивает длину постов. Возможно, это и к лучшему.)
Telegram
Wazowski Recommends
Как и обещал в предыдущему посте, рассказываю про подход для организации правил ранжирования. Это фреймворк, позволяющий сочетать машинно-обученные модели с удовлетворением продуктовых правил, помогающий структурировать эти правила и избежать полной неразберихи.…
🔥23❤7
Как и обещал в предыдущему посте, рассказываю про подход для организации правил ранжирования. Это фреймворк, позволяющий сочетать машинно-обученные модели с удовлетворением продуктовых правил, помогающий структурировать эти правила и избежать полной неразберихи. Но при этом он гибкий и не слишком ограничивающий, поэтому он не может гарантировать полное отсутствие хаоса. В некотором смысле, это просто язык для описания правил. На мой взгляд, достаточно удобный.
Мы будем здесь рассматривать последнюю стадию ранжирования — когда осталось уже не слишком много документов (скажем, от нескольких десятков до пары сотен) и мы хотим из них набрать наилучший набор. Эта стадия примечательна тем, что мы пытаемся не просто как можно точнее оценить каждый документ в текущем контексте, но и учитывать сочетаемость документов друг с другом. Именно в этот момент начинается 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 и контролируемости системы сильно способствует логирование всех выполненных и невыполненных правил.
Мы будем здесь рассматривать последнюю стадию ранжирования — когда осталось уже не слишком много документов (скажем, от нескольких десятков до пары сотен) и мы хотим из них набрать наилучший набор. Эта стадия примечательна тем, что мы пытаемся не просто как можно точнее оценить каждый документ в текущем контексте, но и учитывать сочетаемость документов друг с другом. Именно в этот момент начинается 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 и контролируемости системы сильно способствует логирование всех выполненных и невыполненных правил.
Telegram
Wazowski Recommends
В реальных системах итоговые рекомендации строятся не только машинно-обученными моделями, но и с учётом некоторых эвристических правил. Их называют продуктовыми правилами, бизнес-правилами или просто костылями 🙂
Например:
- нельзя рекомендовать треки одного…
Например:
- нельзя рекомендовать треки одного…
❤15🔥5
Во многих сервисах есть рейтинги объектов: товаров, фильмов, приложений, организаций на карте. Как их правильно считать? Вопрос не такой простой, как кажется на первый взгляд.
Я даже не буду касаться таких важных нюансов, как нечестное накручивание рейтинга, или что сведение "качества" объекта к одному числу — это сильное упрощение. (К счастью. во многих сервисах сейчас показывают разные аспекты качества, вспомните Booking.) И я вообще не фанат числовых шкал оценок. Но в этом посте — о более простых и чисто математических проблемах среднего рейтинга.
Самая стандартная проблема — при простом усреднении всех оценок в топе рейтинга будут объекты с очень малым числом максимальных оценок. Если ваша задача — составить рейтинг лучших объектов, то проще всего рассмотреть только те объекты, которые получили не меньше какого-то числа оценок (100, 1000). Просто и действенно, хотя и на практике в топе всё равно могут оказаться объекты с лишь немного бо́льшим числом оценок, чем этот порог.
Если же вы хотите аккуратно вычислять рейтинг для всех объектов, то самый популярный способ — сглаживание рейтинга. Вместо суммы, разделенной на количество:
У этого способа есть теоретическое обоснование. Те, кто знакомы с байесовской статистикой, его наверняка знают. Если для бинарной шкалы оценок предположить, что априорное распределение среднего рейтинга имеет вид бета-распределения (например, просто равномерного от 0 до 1, это частный случай), то апостериорное распределение тоже будет иметь вид бета-распределения. Матожидание этого распределения как раз и будет сглаженным средним всех оценок.
Ещё одна серьёзная проблема средних рейтингов — selection bias, или ошибка выжившего. Оценки ставят не произвольные пользователи, а несколько специфичные. Усредненная оценка имеет интерпретацию матожидания оценки произвольного пользователя при условии, что он поставит хоть какую-то оценку. Во-первых, сам факт оценки может быть скоррелирован с тем, что пользователя что-то задело, в позитивную или негативную сторону. Многие пользователи не будут ставить оценку, если их опыт был ожидаемо средним. Поэтому нам было бы интереснее более слабое условие: матожидание оценки при условии, что пользователь купил товар, посмотрел фильм, посетил заведение и т.д.
Но во-вторых, даже эта интерпретация имеет большую проблему. В топе глобального рейтинга будет много узких категорий: например, документальные фильмы и артхаус. Уж если пользователь посмотрел такой фильм, то вероятность высокой оценки заметно выше, чем в среднем. Просто мало кто смотрит. Поэтому на самом деле нам интересно матожидание оценки произвольного пользователя без какого-либо условия: как произвольный пользователь оценил бы этот объект?
Как же такое посчитать? Для этого существует техника, хотя и не столь популярная на практике: Inverse Propensity Scoring, или Inverse Probability Weighting. Смысл её в том, чтобы оценить вероятность каждого пользователя поставить оценку и после этого усреднять оценки с весами, обратно пропорциональными этой вероятности. Если пользователь имел очень маленький шанс поставить оценку, но всё же её поставил, то эта оценка учтётся с большим весом. К сожалению, для этого придётся поддерживать модель оценки этой вероятности, а кроме того, дисперсия посчитанного рейтинга достаточно высокая.
А вот отдельный вопрос, на который я так и не знаю правильный ответ: какой должен быть физический смысл у персонального рейтинга ("Этот объект вам подходит на XX%")? Как вы считаете?
Я даже не буду касаться таких важных нюансов, как нечестное накручивание рейтинга, или что сведение "качества" объекта к одному числу — это сильное упрощение. (К счастью. во многих сервисах сейчас показывают разные аспекты качества, вспомните 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%")? Как вы считаете?
❤16👍9🔥8
Один из важнейших типов моделей в рекомендациях на данный момент — это двух-башенные (two tower) нейросети. Они устроены так: одна часть нейросети (башня) обрабатывает всю информацию про запрос (пользователя, контекст), другая башня — про объект. Выходы этих башен — это эмббединги, которые потом перемножаются (dot product или косинус, как уже обсуждалось в этом посте). Одно из первых упоминаний применения таких сетей для рекомендаций можно найти в очень хорошей статье про YouTube. Кстати, именно эту статью я бы сейчас уже называл классикой и наиболее подходящей для входа в область рекомендаций.
Чем характерны такие сети? Они очень похожи на матричную факторизацию, которая на самом деле является частным случаем, принимая на вход только user_id и item_id. Если же сравнивать с произвольными сетями, то это ограничение на позднее связывание (не давать входам из разных башен смешиваться до самого конца) делает двух-башенные сети крайне эффективными при применении. Чтобы построить рекомендации одному пользователю, нам нужно один раз посчитать запросную башню, после чего умножить этот эмбеддинг на эмбеддинги документов, которые обычно заранее предподсчитаны. Это очень быстро. Более того, эти предподсчитанные эмбеддинги документов можно сложить в индекс (например, HNSW), чтобы по ним быстро, не проходясь по всей базе, находить хороших кандидатов.
Можно даже ещё сэкономить, вычисляя пользовательскую часть не на каждый запрос, а асинхронно, с некоторой регулярностью. Но тогда придётся пожертвовать учётом реал-тайм истории и контекста.
Сами башни могут быть довольно навороченными. Например, в пользовательской части можно использовать механизм self-attention для обработки истории (получится трансформер для персонализации). Но чем мы платим, вводя ограничение на позднее связывание? Конечно, качеством. В том же самом attention нельзя использовать объекты, которые мы сейчас хотим оценить/порекомендовать. А ведь хотелось бы для этого как раз обратить внимание на похожие объекты в истории пользователя. Поэтому сети с ранним связыванием обычно применяют на поздних стадиях ранжирования, когда осталось несколько десятков или сотен кандидатов, а с поздним (two tower) — наоборот, на ранних стадиях и кандидато-генерации.
(Впрочем, есть чисто теоретический аргумент, что любое разумное ранжирование документов для разных запросов можно закодировать через эмбеддинги достаточной размерности. Кроме того, декодеры в NLP на самом деле тоже работают по такому же принципу, только перевычисляют запросную башню на каждый токен.)
Отдельный интерес составляет лосс, с которым обучают двух-башенные сети. В принципе, их можно обучать на любой лосс с любыми таргетами и даже иметь несколько разных для разных голов (с разными эмбеддингами в каждой башне). Но один интересный вариант — это обучение с softmax-лоссом на in-batch негативах. Для каждой пары запрос-документ из датасета берутся остальные документы в том же мини-батче и в паре с тем же запросом используются как негативы в softmax loss. Это очень эффективный вариант hard negative mining.
Но важно иметь в виду вероятностную интерпретацию такого лосса (далеко не все её понимают). У обученной сети
Тот же Google в статье предлагал с этим бороться с помощью logQ correction во время обучения. Мы же обычно делали это на этапе применения, а не обучения, — просто умножая на априорную вероятность документа
Чем характерны такие сети? Они очень похожи на матричную факторизацию, которая на самом деле является частным случаем, принимая на вход только 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). Но мы так и не сравнивали эти подходы, а было бы интересно сравнить.Telegram
Wazowski Recommends
Как известно, экзамен прошёл хорошо — это когда ты не просто его сдал, но ещё и узнал на нём что-то новое.
Полгода назад я собеседовался в Microsoft. На одном из собеседований мне задали вопрос, на который я не очень-то хорошо ответил. И даже когда мне сказали…
Полгода назад я собеседовался в Microsoft. На одном из собеседований мне задали вопрос, на который я не очень-то хорошо ответил. И даже когда мне сказали…
👍30❤9🔥8
Есть такой алгоритм коллаборативной фильтрации Implicit ALS (IALS). Я про него уже упомянал. В донейросетевую эпоху это был чуть ли не самый популярный алгоритм. Его отличительная черта — эффективный "майнинг" негативов: все пары пользователь-объект без истории взаимодействия выступают негативами (с меньшим весом, чем настоящие взаимодействия). Причём, в отличие от настоящего майнинга, здесь негативы не сэмплируются, а на каждой итерации используются прямо все такие негативные пары. Такая implicit-регуляризация.
Как же это возможно? Ведь при разумных размерах задачи (количестве пользователей и объектов) негативов должно быть настолько много, что даже их перечисление будет дольше всего процесса обучения. Красота алгоритма в том, что, благодаря использованию MSE-лосса и методу наименьших квадратов, можно заранее (перед каждой полной итерацией) предпосчитать что-то отдельно для всех пользователей и отдельно для всех объектов и этого хватит для того, чтобы делать implicit-регуляризацию. Так удаётся избежать квадратичного размера. (За подробностями предлагаю обратиться к одной из моих любимых статей тех времён.)
Пару лет назад я задумался: а можно ли как-то совместить эту прекрасную идею implicit-регуляризации с более продвинутой технологией двух-башенных нейросетей. Вопрос непростой, ведь там и стохастическая оптимизация вместо full batch, да и переходить обратно на MSE-лосс не хочется (по крайней мере, для всей задачи, конкретно для регуляризации — ещё ладно), он даёт худшие результаты.
Думал, думал и придумал! И пару недель ходил воодушевлённый, в ожидании того, как мы это попробуем вместо in-batch негативов.
А потом, конечно же (как это часто бывает в подобных случаях), прочитал в статье, что всё уже придумали за три года до этого. И снова Google. И потом они в той самой статье про logQ correction, про которую я уже говорил, показали, что softmax loss с in-batch негативами работает лучше, чем implicit-регуляризация.
Вот так мы смогли сэкономить и не проверять эту идею 🙂
А в комментах напишу другую свою идею на схожую тему, которую мы тоже не успели попробовать, но и в литературе я её не встречал.
Как же это возможно? Ведь при разумных размерах задачи (количестве пользователей и объектов) негативов должно быть настолько много, что даже их перечисление будет дольше всего процесса обучения. Красота алгоритма в том, что, благодаря использованию MSE-лосса и методу наименьших квадратов, можно заранее (перед каждой полной итерацией) предпосчитать что-то отдельно для всех пользователей и отдельно для всех объектов и этого хватит для того, чтобы делать implicit-регуляризацию. Так удаётся избежать квадратичного размера. (За подробностями предлагаю обратиться к одной из моих любимых статей тех времён.)
Пару лет назад я задумался: а можно ли как-то совместить эту прекрасную идею implicit-регуляризации с более продвинутой технологией двух-башенных нейросетей. Вопрос непростой, ведь там и стохастическая оптимизация вместо full batch, да и переходить обратно на MSE-лосс не хочется (по крайней мере, для всей задачи, конкретно для регуляризации — ещё ладно), он даёт худшие результаты.
Думал, думал и придумал! И пару недель ходил воодушевлённый, в ожидании того, как мы это попробуем вместо in-batch негативов.
А потом, конечно же (как это часто бывает в подобных случаях), прочитал в статье, что всё уже придумали за три года до этого. И снова Google. И потом они в той самой статье про logQ correction, про которую я уже говорил, показали, что softmax loss с in-batch негативами работает лучше, чем implicit-регуляризация.
Вот так мы смогли сэкономить и не проверять эту идею 🙂
А в комментах напишу другую свою идею на схожую тему, которую мы тоже не успели попробовать, но и в литературе я её не встречал.
Telegram
Wazowski Recommends
В индустрии в рекомендательных системах очень часто возникают ситуации, когда есть доступ к каким-нибудь внешним эмбеддингам и хочется их наиболее эффективно использовать. "Внешними" я называю такие эмбеддинги, которые обучают без привязки к рекомендательной…
🔥12❤3💋1
Вслед за последними постами хочется осветить более общий вопрос.
А нужен ли вообще negative sampling для рекомендательных моделей?
Ведь у нас есть настоящие показы рекомендаций, и если пользователь на них не реагировал, то их можно использовать как сильные негативы. (Тут не рассматриваем случай, когда сам сервис рекомендаций пока не запущен и показов ещё нет.)
Ответ на этот вопрос не такой тривиальный, он зависит от того, как именно мы будем применять обучаемую модель: для финального ранжирования, для генерации кандидатов или просто для фичей на вход в другую модель.
Что происходит, когда мы обучаем модель только на настоящих показах? Происходит довольно сильный selection bias, и модель учится хорошо различать только те документы, которые показывались в данном контексте. На тех документах (точнее, парах запрос-документ), которые не показывались, модель будет работать сильно хуже: каким-то документам завышать предсказания, каким-то — занижать. Безусловно, этот эффект можно снизить, применяя exploration в ранжировании, но чаще всего — лишь частично.
Если генератор кандидатов обучить таким образом, то на запрос он может выдать кучу документов, которые раньше не видел в таком контексте и которым завышает предсказания. Причём среди этих документов часто попадается совсем мусор. Если модель финального ранжирования достаточно хорошая, то она эти документы отфильтрует и не покажет пользователю. Но квоту кандидатов мы тем не менее потратим на них зря (а нормальных документов может и вообще не остаться). Поэтому генераторы кандидатов надо обучать так, чтобы они понимали, что большая часть базы документов совсем плохая и их рекомендовать (номинировать в кандидаты) не надо. Negative sampling — хороший способ для этого.
Модели финального ранжирования в этом плане очень похожи на генерацию кандидатов, но есть важное отличие: они учатся на своих ошибках. Когда модель ошибается, завышая предсказания каким-то документам, эти документы показываются пользователям и после этого могут попасть в следующий датасет для обучения. Мы можем переобучить модель на новом датасете и снова выкатить на пользователей. Появятся новые false positives. И снова можно повторить сбор датасета и переобучение. Происходит такой своеобразный active learning. На практике всего нескольких итераций переобучения хватает, чтобы этот процесс сошёлся и модель больше не рекомендовала дичь. Тут, конечно, надо соизмерять вред от рандомных рекомендаций, иногда стоит как-то подстраховаться. Но в целом, negative sampling здесь не нужен. Наоборот, он может ухудшить exploration, заставляя систему оставаться в локальном оптимуме.
Если же модель используется для фичей на вход в другую модель, то вся та же логика тоже применима, но только вред от завышения предсказаний случайным документам-кандидатам тут ещё меньше, потому что другие фичи могут помочь скорректировать финальное предсказание. (Если документ даже не попал в список кандидатов, то мы и вычислять фичи для него не будем.)
Когда-то мы прямо проверяли, что в качестве фичей обычный ALS работает лучше, чем IALS, но вот для генерации кандидатов его использовать не стоит.
А нужен ли вообще negative sampling для рекомендательных моделей?
Ведь у нас есть настоящие показы рекомендаций, и если пользователь на них не реагировал, то их можно использовать как сильные негативы. (Тут не рассматриваем случай, когда сам сервис рекомендаций пока не запущен и показов ещё нет.)
Ответ на этот вопрос не такой тривиальный, он зависит от того, как именно мы будем применять обучаемую модель: для финального ранжирования, для генерации кандидатов или просто для фичей на вход в другую модель.
Что происходит, когда мы обучаем модель только на настоящих показах? Происходит довольно сильный selection bias, и модель учится хорошо различать только те документы, которые показывались в данном контексте. На тех документах (точнее, парах запрос-документ), которые не показывались, модель будет работать сильно хуже: каким-то документам завышать предсказания, каким-то — занижать. Безусловно, этот эффект можно снизить, применяя exploration в ранжировании, но чаще всего — лишь частично.
Если генератор кандидатов обучить таким образом, то на запрос он может выдать кучу документов, которые раньше не видел в таком контексте и которым завышает предсказания. Причём среди этих документов часто попадается совсем мусор. Если модель финального ранжирования достаточно хорошая, то она эти документы отфильтрует и не покажет пользователю. Но квоту кандидатов мы тем не менее потратим на них зря (а нормальных документов может и вообще не остаться). Поэтому генераторы кандидатов надо обучать так, чтобы они понимали, что большая часть базы документов совсем плохая и их рекомендовать (номинировать в кандидаты) не надо. Negative sampling — хороший способ для этого.
Модели финального ранжирования в этом плане очень похожи на генерацию кандидатов, но есть важное отличие: они учатся на своих ошибках. Когда модель ошибается, завышая предсказания каким-то документам, эти документы показываются пользователям и после этого могут попасть в следующий датасет для обучения. Мы можем переобучить модель на новом датасете и снова выкатить на пользователей. Появятся новые false positives. И снова можно повторить сбор датасета и переобучение. Происходит такой своеобразный active learning. На практике всего нескольких итераций переобучения хватает, чтобы этот процесс сошёлся и модель больше не рекомендовала дичь. Тут, конечно, надо соизмерять вред от рандомных рекомендаций, иногда стоит как-то подстраховаться. Но в целом, negative sampling здесь не нужен. Наоборот, он может ухудшить exploration, заставляя систему оставаться в локальном оптимуме.
Если же модель используется для фичей на вход в другую модель, то вся та же логика тоже применима, но только вред от завышения предсказаний случайным документам-кандидатам тут ещё меньше, потому что другие фичи могут помочь скорректировать финальное предсказание. (Если документ даже не попал в список кандидатов, то мы и вычислять фичи для него не будем.)
Когда-то мы прямо проверяли, что в качестве фичей обычный ALS работает лучше, чем IALS, но вот для генерации кандидатов его использовать не стоит.
Telegram
Wazowski Recommends
Есть такой алгоритм коллаборативной фильтрации Implicit ALS (IALS). Я про него уже упомянал. В донейросетевую эпоху это был чуть ли не самый популярный алгоритм. Его отличительная черта — эффективный "майнинг" негативов: все пары пользователь-объект без истории…
🔥13👍2❤1
Forwarded from Knowledge Accumulator
HNSW [2016] - один из столпов современных рекомендательных систем
В больших системах существуют миллионы вариантов того, что можно порекомендовать пользователю. Это слишком много, чтобы применять ML для оценки релевантности документа, и, чтобы сузить выбор, существует этап кандидатогенерации. Генераторы бывают тупыми - например, какие-нибудь фильтры по ключевым словам, но бывают и умные, основанные на эмбеддингах.
Идея следующая: у нас есть эмбеддинг пользователя
Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору
HNSW добавляет Hierarchical к выше описанной схеме - мы создаём несколько уровней графа для поиска в разных масштабах. На нижнем уровне находятся все вершины, но с каждым повышением уровня остаётся случайный поднабор вершин, таким образом, делая соседей дальше друг от друга и позволяя прыгать дальше на каждом шаге поиска. Поиск начинается с самого верхнего уровня, и, попадая в тупик, мы спускаемся ниже и продолжаем. Это позволяет сократить количество операций. На картинке иллюстрация работа поиска.
Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.
@knowledge_accumulator
В больших системах существуют миллионы вариантов того, что можно порекомендовать пользователю. Это слишком много, чтобы применять ML для оценки релевантности документа, и, чтобы сузить выбор, существует этап кандидатогенерации. Генераторы бывают тупыми - например, какие-нибудь фильтры по ключевым словам, но бывают и умные, основанные на эмбеддингах.
Идея следующая: у нас есть эмбеддинг пользователя
u и N эмбеддингов документов d, и мы хотим взять k ближайших к пользователю документов. Проблема в том, для точного ответа на такой запрос нам придётся считать все N расстояний между u и d, но такие вычисления мы не можем себе позволить. Но нам и не нужен точный ответ, подойдут и просто k близких к u векторов. Такая постановка называется "approximate nearest neighbor search". HNSW - это на сегодня топовый способ решения такой задачи.Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору
q, мы жадно ходим по графу и идём всегда в вершину, которая ближе всего к q. Когда мы попадаем в "локальный минимум", то считаем его ответом. Такая процедура позволяет не считать все расстояния для каждого q.HNSW добавляет Hierarchical к выше описанной схеме - мы создаём несколько уровней графа для поиска в разных масштабах. На нижнем уровне находятся все вершины, но с каждым повышением уровня остаётся случайный поднабор вершин, таким образом, делая соседей дальше друг от друга и позволяя прыгать дальше на каждом шаге поиска. Поиск начинается с самого верхнего уровня, и, попадая в тупик, мы спускаемся ниже и продолжаем. Это позволяет сократить количество операций. На картинке иллюстрация работа поиска.
Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.
@knowledge_accumulator
🔥15👍1
Какое-то время назад я писал о том, как можно использовать внешние эмбеддинги. Сегодня поговорим на связанную (даже пересекающуюся) тему: как использовать внешнюю историю пользователей, т.е. историю на другом сервисе. Типичный пример у поисковых гигантов: поисковая история, довольно богатый источник информации про пользовательские интересы (если privacy policy позволяет).
Если у этой внешней истории пространство объектов совпадает с основным пространством рекомендуемых объектов (или сильно пересекается, или явным образом связанно), то этот случай простой: мы просто можем добавить в нашу систему ещё один тип событий — внешнее взаимодействие — и во всех моделях учитывать ещё и историю этого типа с рекомендуемыми объектами. Даже если рекомендуемые и внешние объекты явно не связаны, иногда их можно связать неявно — обучив контентную модель, которая будет "матчить" внешние объекты и внутренние.
Если же внешние и внутренние объекты совсем разные, то тут интереснее. Могут существовать статистические закономерности, которые можно выучить. Можно либо явным образом их искать ("пользователи, взаимодействующие с внешним объектом A, чаще других пользователей взаимодействуют с внутренним объектом B"), либо обучать модели, похожие на SLIM, — линейные с кросс-фичами [пользователь взаимодействовал с объектом A, мы оцениваем объект B].
Но всё-таки наиболее подходящим способом (хотя и несколько сложнее отлаживаемым), как мне кажется, являются двух-башенные сети. Ведь даже когда они обучаются без внешней истории, они не используют тот факт, что пространства объектов совпадают. Эмбеддинги объектов в левой и правой башнях всё равно полезно не делать связанными (shared), а обучать разными. Поэтому можно просто в пользовательской башне использовать внешнюю историю. Сеть всё равно в конце приведёт и пользователя, и рекомендуемый объект в общее семантическое пространство.
Можно обучить отдельную сеть для внешней истории или же просто добавить внешнюю историю как дополнительный сигнал на вход одной двух-башенной сети. Второй вариант, вероятно, более мощный, т.к. внешняя и внутренняя истории могут нетривиальным образом друг на друга повлиять (особенно если использовать self attention), Но его и сложнее обучать: сеть может просто "забить" на дополнительный, менее информативный и более шумный сигнал. Поэтому я бы начинал с первого варианта. К тому же, сильно проще проверить, что он выучивает что-то разумное.
Отдельный вопрос: а как именно использовать дополнительную модель с внешней историей? Есть несколько вариантов:
1) фичи в ранжирующей модели,
2) кандидаты,
3) продуктовые правила (бустить рекомендации от таких моделей),
4) более изощренные техники вроде модификации лоссов/таргетов ранжирования.
Я сильно рекомендую всегда начинать с пункта 1 — с фичей. Даже если это не самый эффективный способ, без него остальные варианты будут работать совсем не оптимально. Более того, зачастую они могут даже вредить системе.
При этом иногда добавление фичей совсем не помогает (они просто не используются моделью) из-за того, что в датасете просто нет исторических примеров, когда система рекомендовала что-то связанное с внешней историей. Поэтому способ такой: внедряем фичи, добавляем кандидатов, при необходимости бустим этих кандидатов в течение ограниченного времени, после этого уже фичи начинают учитываться в модели, и буст можно отключать. У нас такой способ хорошо работал.
Если у этой внешней истории пространство объектов совпадает с основным пространством рекомендуемых объектов (или сильно пересекается, или явным образом связанно), то этот случай простой: мы просто можем добавить в нашу систему ещё один тип событий — внешнее взаимодействие — и во всех моделях учитывать ещё и историю этого типа с рекомендуемыми объектами. Даже если рекомендуемые и внешние объекты явно не связаны, иногда их можно связать неявно — обучив контентную модель, которая будет "матчить" внешние объекты и внутренние.
Если же внешние и внутренние объекты совсем разные, то тут интереснее. Могут существовать статистические закономерности, которые можно выучить. Можно либо явным образом их искать ("пользователи, взаимодействующие с внешним объектом A, чаще других пользователей взаимодействуют с внутренним объектом B"), либо обучать модели, похожие на SLIM, — линейные с кросс-фичами [пользователь взаимодействовал с объектом A, мы оцениваем объект B].
Но всё-таки наиболее подходящим способом (хотя и несколько сложнее отлаживаемым), как мне кажется, являются двух-башенные сети. Ведь даже когда они обучаются без внешней истории, они не используют тот факт, что пространства объектов совпадают. Эмбеддинги объектов в левой и правой башнях всё равно полезно не делать связанными (shared), а обучать разными. Поэтому можно просто в пользовательской башне использовать внешнюю историю. Сеть всё равно в конце приведёт и пользователя, и рекомендуемый объект в общее семантическое пространство.
Можно обучить отдельную сеть для внешней истории или же просто добавить внешнюю историю как дополнительный сигнал на вход одной двух-башенной сети. Второй вариант, вероятно, более мощный, т.к. внешняя и внутренняя истории могут нетривиальным образом друг на друга повлиять (особенно если использовать self attention), Но его и сложнее обучать: сеть может просто "забить" на дополнительный, менее информативный и более шумный сигнал. Поэтому я бы начинал с первого варианта. К тому же, сильно проще проверить, что он выучивает что-то разумное.
Отдельный вопрос: а как именно использовать дополнительную модель с внешней историей? Есть несколько вариантов:
1) фичи в ранжирующей модели,
2) кандидаты,
3) продуктовые правила (бустить рекомендации от таких моделей),
4) более изощренные техники вроде модификации лоссов/таргетов ранжирования.
Я сильно рекомендую всегда начинать с пункта 1 — с фичей. Даже если это не самый эффективный способ, без него остальные варианты будут работать совсем не оптимально. Более того, зачастую они могут даже вредить системе.
При этом иногда добавление фичей совсем не помогает (они просто не используются моделью) из-за того, что в датасете просто нет исторических примеров, когда система рекомендовала что-то связанное с внешней историей. Поэтому способ такой: внедряем фичи, добавляем кандидатов, при необходимости бустим этих кандидатов в течение ограниченного времени, после этого уже фичи начинают учитываться в модели, и буст можно отключать. У нас такой способ хорошо работал.
Telegram
Wazowski Recommends
В индустрии в рекомендательных системах очень часто возникают ситуации, когда есть доступ к каким-нибудь внешним эмбеддингам и хочется их наиболее эффективно использовать. "Внешними" я называю такие эмбеддинги, которые обучают без привязки к рекомендательной…
🔥8👍7
Forwarded from Knowledge Accumulator
Как и зачем делать exploration в рекомендациях
В схеме Learning to Rank мы обучаем модель Score(user, item), выдающую оценку релевантности каждого из кандидатов. Рассмотрим пример сценария применения такой модели:
Этап кандидатогенерации, к примеру, HNSW, принёс нам 1000 кандидатов. К каждому мы применили нашу модель релевантности и получили 1000 чисел. В качестве результата выполнения запроса мы должны отдать пользователю 10 объектов. Простейшая опция - это отдать пользователю 10 объектов с наибольшей релевантностью. Но у этого есть проблема.
Дело в том, что для качественного обучения модели Score(user, item) у неё должен быть разнообразный набор данных. Если мы всем пользователям выдаём только самые релевантные треки, то может образоваться много треков, которые вообще не попадали в выдачу никому, и тогда модель на них может выдавать нереалистично маленький или большой результат - обе эти ситуации нежелательны и могут привести к плохой выдаче в будущем.
Возникает trade-off - с одной стороны, мы хотим формировать релевантную выдачу, с другой, мы хотим её немного разнообразить для улучшения качества датасета. Этот баланс на практике можно регулировать таким образом:
1) 1000 скоров кандидатов превращаются в вероятности попадания в выдачу:
2) Применяется специальный алгоритм по генерации выборки из такого распределения.
Если T равна 0, мы получаем просто топ-10, и чем она больше, тем больше всё сглаживается в сторону равномерной выдачи.
Самая большая проблема этой схемы заключается в подборе значения T. Я уже объяснял, что когда один элемент влияет на все компоненты системы, для тестирования необходимо дублировать вообще всю систему - здесь именно такой случай, и почти всегда мы не можем этого себе позволить. Как же тогда быть?
Сначала предполагаем на глаз, какой уровень "гладкости" выдачи мы хотим. А затем уже подгоняем T, чтобы был нужный эффект, и по надобности иногда переподгоняем. Вот такая наука.
@knowledge_accumulator
В схеме Learning to Rank мы обучаем модель Score(user, item), выдающую оценку релевантности каждого из кандидатов. Рассмотрим пример сценария применения такой модели:
Этап кандидатогенерации, к примеру, HNSW, принёс нам 1000 кандидатов. К каждому мы применили нашу модель релевантности и получили 1000 чисел. В качестве результата выполнения запроса мы должны отдать пользователю 10 объектов. Простейшая опция - это отдать пользователю 10 объектов с наибольшей релевантностью. Но у этого есть проблема.
Дело в том, что для качественного обучения модели Score(user, item) у неё должен быть разнообразный набор данных. Если мы всем пользователям выдаём только самые релевантные треки, то может образоваться много треков, которые вообще не попадали в выдачу никому, и тогда модель на них может выдавать нереалистично маленький или большой результат - обе эти ситуации нежелательны и могут привести к плохой выдаче в будущем.
Возникает trade-off - с одной стороны, мы хотим формировать релевантную выдачу, с другой, мы хотим её немного разнообразить для улучшения качества датасета. Этот баланс на практике можно регулировать таким образом:
1) 1000 скоров кандидатов превращаются в вероятности попадания в выдачу:
p = exp(score/T) / Z, где T - температура, а Z - нормировочная константа.2) Применяется специальный алгоритм по генерации выборки из такого распределения.
Если T равна 0, мы получаем просто топ-10, и чем она больше, тем больше всё сглаживается в сторону равномерной выдачи.
Самая большая проблема этой схемы заключается в подборе значения T. Я уже объяснял, что когда один элемент влияет на все компоненты системы, для тестирования необходимо дублировать вообще всю систему - здесь именно такой случай, и почти всегда мы не можем этого себе позволить. Как же тогда быть?
Сначала предполагаем на глаз, какой уровень "гладкости" выдачи мы хотим. А затем уже подгоняем T, чтобы был нужный эффект, и по надобности иногда переподгоняем. Вот такая наука.
@knowledge_accumulator
👍6🔥2
Как известно, в рекомендательных системах есть несколько стадий построения рекомендаций: сначала происходит генерация кандидатов, а затем — одна или несколько стадий ранжирования. В статьях уделяют не очень много внимания ранним стадиям. Но на практике они довольно важны. И важно, как измерять их качество.
Чаще всего кандидато-генерация устроена как объединение разных источников:
- самые популярные объекты,
- похожее на историю пользователя,
- ANN — похожее по эмбеддингам (например, HNSW),
- комбинация предыдущих методов на разных уровнях: например, взять категории из истории пользователя (или из ANN, или популярные), а потом из них взять популярные объекты.
Хотя каждый метод тут может быть несложным, вся комбинация получается достаточно нетривиальной, чтобы задуматься: а как её можно оптимизировать? А для этого нужно, конечно, определить, что именно надо оптимизировать, т.е. какой метрикой измерять качество кандидато-генерации (далее будем говорить именно про эту стадию, хотя всё то же самое относится и к ранним стадиям ранжирования).
Существуют разные подходы. Иногда качество просто не замеряют (ну или просто "на глаз") и системно не оптимизируют эту стадию. Иногда каким-то образом замеряют общую релевантность кандидатов. И если система порекомендовала что-то странное, то это считают багом в том числе и кандидато-генерации. Иногда эту релевантность даже противопоставляют тому, что оптимизируется в финальной стадии. Т.е. кандидаты должны быть уже достаточно релевантными (как бы это ни измерялось), а финальное ранжирование выберет из них наиболее engaging (привлекательные/кликабельные/...).
Иногда, особенно в статьях, используют метрики вроде HitRate@k, Recall@k, Precision@k, MRR, NDCG и т.д., фокусируясь только на положительных (релевантных) документах. При этом релевантным считается тот документ, с которым пользователь впоследствии взаимодействовал. Мне этот подход нравится больше предыдущих, хотя тут большая проблема с разными смещениями: например, пользователи чаще взаимодействуют с теми объектами, которые система сама же и рекомендует.
Но в какой-то момент я попытался сформулировать другой подход к кандидато-генерации и с тех пор являюсь его приверженцем. К счастью, оказалось, что я такой не единственный — этот подход уже используется в разных системах (например, в комментариях давали ссылку про Instagram). Но не уверен, что его можно назвать стандартом индустрии — точно есть большие системы, в которых он не используется.
Подход основывается на таком принципе:
Или, простыми словами, цель — найти топ. Топ определяется никакой не релевантностью, а просто текущим финальным ранкером. Те кандидаты, которые в итоге выбираются финальным ранкером, — хорошие, остальные — не очень. Если ранкер поменяется (а он может меняться и довольно часто), то поменяется и оценка качества.
(Тут может быть модификация для многостадийного ранжирования: качество ранней стадии можно оценивать либо с помощью именно финального ранкера, либо с помощью ранкера следующей стадии. Т.е. кандидаты, прошедшие следующую стадию, но не прошедшие финальную, могут считаться как отрицательными, так и положительными. Я не знаю, как лучше.)
Этот принцип превращает кандидато-генерацию в довольно утилитарную задачу с вполне определенной целью. А вся сложность с objectives (какие таргеты и лоссы использовать) перекладывается на финальную стадию ранжирования.
Хотя этот подход и не идеален, лично я считаю его единственным состоятельным, т.е. только с ним можно долгосрочно системно улучшать качество всех стадий и не упереться в фундаментальную проблему. По крайней мере, я не понимаю, как это делать с другими подходами.
В следующий раз я раскрою тему чуть глубже и напишу про плюсы и минусы этого подхода.
Чаще всего кандидато-генерация устроена как объединение разных источников:
- самые популярные объекты,
- похожее на историю пользователя,
- ANN — похожее по эмбеддингам (например, HNSW),
- комбинация предыдущих методов на разных уровнях: например, взять категории из истории пользователя (или из ANN, или популярные), а потом из них взять популярные объекты.
Хотя каждый метод тут может быть несложным, вся комбинация получается достаточно нетривиальной, чтобы задуматься: а как её можно оптимизировать? А для этого нужно, конечно, определить, что именно надо оптимизировать, т.е. какой метрикой измерять качество кандидато-генерации (далее будем говорить именно про эту стадию, хотя всё то же самое относится и к ранним стадиям ранжирования).
Существуют разные подходы. Иногда качество просто не замеряют (ну или просто "на глаз") и системно не оптимизируют эту стадию. Иногда каким-то образом замеряют общую релевантность кандидатов. И если система порекомендовала что-то странное, то это считают багом в том числе и кандидато-генерации. Иногда эту релевантность даже противопоставляют тому, что оптимизируется в финальной стадии. Т.е. кандидаты должны быть уже достаточно релевантными (как бы это ни измерялось), а финальное ранжирование выберет из них наиболее engaging (привлекательные/кликабельные/...).
Иногда, особенно в статьях, используют метрики вроде HitRate@k, Recall@k, Precision@k, MRR, NDCG и т.д., фокусируясь только на положительных (релевантных) документах. При этом релевантным считается тот документ, с которым пользователь впоследствии взаимодействовал. Мне этот подход нравится больше предыдущих, хотя тут большая проблема с разными смещениями: например, пользователи чаще взаимодействуют с теми объектами, которые система сама же и рекомендует.
Но в какой-то момент я попытался сформулировать другой подход к кандидато-генерации и с тех пор являюсь его приверженцем. К счастью, оказалось, что я такой не единственный — этот подход уже используется в разных системах (например, в комментариях давали ссылку про Instagram). Но не уверен, что его можно назвать стандартом индустрии — точно есть большие системы, в которых он не используется.
Подход основывается на таком принципе:
Главная задача ранних стадий состоит в том, чтобы найти наилучшие документы с точки зрения финального ранжирования.
Или, простыми словами, цель — найти топ. Топ определяется никакой не релевантностью, а просто текущим финальным ранкером. Те кандидаты, которые в итоге выбираются финальным ранкером, — хорошие, остальные — не очень. Если ранкер поменяется (а он может меняться и довольно часто), то поменяется и оценка качества.
(Тут может быть модификация для многостадийного ранжирования: качество ранней стадии можно оценивать либо с помощью именно финального ранкера, либо с помощью ранкера следующей стадии. Т.е. кандидаты, прошедшие следующую стадию, но не прошедшие финальную, могут считаться как отрицательными, так и положительными. Я не знаю, как лучше.)
Этот принцип превращает кандидато-генерацию в довольно утилитарную задачу с вполне определенной целью. А вся сложность с objectives (какие таргеты и лоссы использовать) перекладывается на финальную стадию ранжирования.
Хотя этот подход и не идеален, лично я считаю его единственным состоятельным, т.е. только с ним можно долгосрочно системно улучшать качество всех стадий и не упереться в фундаментальную проблему. По крайней мере, я не понимаю, как это делать с другими подходами.
В следующий раз я раскрою тему чуть глубже и напишу про плюсы и минусы этого подхода.
🔥14👍7❤2👌2
Итак, про плюсы и минусы подхода:
Начнём с минусов.
➖ Вся кандидато-генерация, в том числе способ измерения её качества, начинают существенно зависеть от текущего метода ранжирования. Это увеличивает сложность, нужно это учитывать при сравнении. И когда ранкер меняется, ранние стадии нужно переобучать.
➖ Чаще всего системы изначально строятся без следования этому принципу. И перевести систему в состояние следования из другого состояния может быть очень сложно. В частности, если у системы довольно плохое ранжирование (но благодаря разным хакам результат рекомендаций приемлемый), то следование этому принципу не сделает систему лучше, а наоборот, может в моменте сильно ухудшить рекомендации.
➖ Принцип предполагает, что ранкер должен хорошо работать на всей базе. В противном случае, если есть плохие документы, которые ранкер ошибочно порекомендовал бы, то кандидато-генерация, пытаясь угодить ранкеру, рано или поздно тоже их найдёт. Это несколько усложняет обучение ранкера по сравнению со случаем, когда он работает только на множестве уже достаточно неплохих кандидатов.
➖ Кандидато-генерация не пытается улучшить end-to-end метрики сервиса. Можно её улучшить согласно этому принципу, но получить красный эксперимент. (Впрочем, это будет как раз означать, что в ранжировании есть проблема, например неправильный target.) Это усложняет работу: улучшаешь-улучшаешь, а выкатить потом не можешь.
➖ Ограниченная поддержка бизнес-правил. Этот принцип говорит, что все такие правила (кроме жестких) надо применять на финальной стадии, а ранние будут сами приспосабливаться к ним. И это не только про костыли, но и про полезные аспекты рекомендаций вроде exploration, diversity, etc. (Придётся выдавать разнообразных кандидатов, потому что ранжирование их выбирает.)
А теперь к плюсам.
➕ Принцип основан на декомпозиции. У ранних стадий появляется более понятная и измеримая цель, и это сильно упрощает систему. Вся сложность с выбором таргетов и лоссов для рекомендаций концентрируется в ранжировании (где от этого всё равно не уйти), здесь же решается чисто утилитарная задача эффективного нахождения топа. Ранние стадии — просто инструмент для ускорения ранжирования.
➕ В этом принципе нет фундаментальных ограничений. Если представить себе идеальную систему рекомендаций, то ничего не мешает ей быть устроенной именно так. (Чего нельзя сказать про остальные подходы — не обязаны идеальные рекомендации угадывать то, с чем пользователь и сам потом взаимодействовал!) И с улучшением ранжирования такие упрощенные метрики кандидато-генерации становятся всё ближе к end-to-end метрикам. Так же, как в известном в определенном кругу итеративном подходе "улучшаем метрики — улучшаем продукт по этим метрикам".
➕ Разные стадии ранжирования согласованы друг с другом, они не пытаются оптимизировать разные вещи. В системах же, где это не так, если взять и, скажем, увеличить общее число кандидатов вдвое, то качество всей системы может не улучшиться, а, наоборот, деградировать. Например, если ранние стадии оптимизировали некую релевантность, то дополнительные кандидаты будут менее релевантными, и общая релевантность снизится (хотя кликабельность возрастёт).
➕ Как следствие пункта про декомпозицию: ранние стадии намного проще измерять (а значит, и оптимизировать). В упрощённом случае, когда финальное ранжирование определяется только какой-то моделью (без других правил), можно запустить её на двух методах кандидато-генерации и сравнить средние предсказания. А обучение в этом упрощенном случае сводится, по сути, к дистилляции модели ранжирования. (Хотя тут есть нюансы. Например, хорошо бы логировать некоторых кандидатов, которые не попали в топ ранжирования.)
➕ Более того, для обучения и измерения ранних стадий нам теперь не нужны пользователи, и поэтому необязательно выкатывать новый метод на них. Можно, например, использовать scraping, т.е. обстреливать сервис ранжирования новыми кандидатами.
Главная задача ранних стадий состоит в том, чтобы найти наилучшие документы с точки зрения финального ранжирования.
Начнём с минусов.
А теперь к плюсам.
Please open Telegram to view this post
VIEW IN TELEGRAM
Telegram
Wazowski Recommends
Как известно, в рекомендательных системах есть несколько стадий построения рекомендаций: сначала происходит генерация кандидатов, а затем — одна или несколько стадий ранжирования. В статьях уделяют не очень много внимания ранним стадиям. Но на практике они…
❤12🔥5
Из забавного:
Google Discover порекомендовал мне прочитать мою же статью, опубликованную в Towards Data Science 😁
Google Discover порекомендовал мне прочитать мою же статью, опубликованную в Towards Data Science 😁
❤15🔥11😁10🍓4
А теперь обсудим, как именно на практике можно измерять качество кандидато-генерации (или ранних стадий ранжирования), согласно тому самому принципу.
Сначала разберём упрощенный, но довольно важный случай: когда ранжирование производится просто по скорам одной финальной модели. Как я уже упоминал в предыдущем посте, мы просто можем сравнить средние скоры этой модели на двух наборах кандидатов. Если один метод находит кандидатов, которым финальная модель выдаёт бОльшие предсказания, чем у другого метода, то первый метод лучше.
Брать ли средние предсказания по всей выдаче, или только по топовым позициям, или с каким-то затуханием по позициям (получается что-то вроде IDCG — знаменателя в NDCG) — кажется, не очень принципиально. Можно выбрать любое по вкусу.
Есть технический нюанс. Если измерять такую метрику в офлайне, то надо уметь запускать ранжирование (или весь рекомендательный стек) на кастомных кандидатах. Это можно сделать либо через симуляцию (offline replay — т.е. пытаться ретроспективно воспроизвести всю информацию про все сущности) на исторических запросах, либо через scraping — "обстрелять" сервис рекомендаций новыми запросами, чтобы он при этом использовал интересующие методы кандидато-генерации. В обоих случаях получаются результаты (предсказания финальной модели) для разных методов генерации для одних и тех же запросов. Это хорошо для чувствительности метрики.
Если же измерять эту метрику в онлайне, на продакшен-сервисе, то можно всё посчитать просто по залогированным предсказаниям модели. Это сильно проще, но не так гибко, и сравнение будет на разных запросах. Чувствительность метрики снижается (вдруг одному из методов просто достались более сложные запросы).
А теперь перейдём к общему случаю: финальное ранжирование — это не только предсказания какой-то модели, но и много другой логики, переранжирования, бизнес-правил, рандомизации и т.д. Если задуматься, как вообще сравнить разные наборы кандидатов в такой нестрогой формулировке (что такой хорошо и что такое плохо) — совсем не очевидно.
Но когда-то я придумал способ для этого, который получился очень простым и полезным. И до сих пор нигде не видел его упоминания.
Способ такой. Добавляем в список источников кандидатов специальный источник, который выдаёт случайных кандидатов (скажем, равномерно). Назначаем этому источнику небольшую фиксированную квоту (скажем, 50 кандидатов). И смотрим, какая доля порекомендованных документов в итоге из этого источника. Если наша кандидато-генерация достаточно хорошая, то случайные кандидаты крайне редко будут побеждать у неё, т.е. попадать в топ. Если же плохая — то часто.
Конечно, тут мы предполагаем, что добавление случайных кандидатов не сильно ухудшает систему: большинство из них не порекомендуется, а те, которые порекомендуются, не сильно ухудшат жизнь пользователей, да ещё и добавят exploration как пользователям, так и модели ранжирования (она дообучится на этих примерах). Если это не так, то сначала стоит "починить ранжирование". 😉
Самое прикольное в этом методе — что он может служить не только метрикой кандидато-генерации, но и мониторингом здоровья всей системы, в том числе и финального ранжирования. Он проверяет, насколько кандидато-генерация согласована с ранжированием (оптимизирована под ранжирование). Если само ранжирование по каким-то причинам деградирует, то и кандидаты становятся не такими уж хорошими для него. Мы это видели на практике, когда одна из компонент поломалась, доля рандомных кандидатов в ответе увеличилась.
Кстати, случайность этого специального источника можно настраивать. Если использовать не равномерную, а пропорциональную популярности документа, то это будет более сильный "adversarial" игрок (что тоже может увеличить чувствительность). Зато при равномерном сэмплировании можно дать аналитическую оценку того, в какой доле запросов наша кандидато-генерация была идеальной (т.е. результат бы не поменялся, даже если бы мы добавили в кандидаты всю базу).
Сначала разберём упрощенный, но довольно важный случай: когда ранжирование производится просто по скорам одной финальной модели. Как я уже упоминал в предыдущем посте, мы просто можем сравнить средние скоры этой модели на двух наборах кандидатов. Если один метод находит кандидатов, которым финальная модель выдаёт бОльшие предсказания, чем у другого метода, то первый метод лучше.
Брать ли средние предсказания по всей выдаче, или только по топовым позициям, или с каким-то затуханием по позициям (получается что-то вроде IDCG — знаменателя в NDCG) — кажется, не очень принципиально. Можно выбрать любое по вкусу.
Есть технический нюанс. Если измерять такую метрику в офлайне, то надо уметь запускать ранжирование (или весь рекомендательный стек) на кастомных кандидатах. Это можно сделать либо через симуляцию (offline replay — т.е. пытаться ретроспективно воспроизвести всю информацию про все сущности) на исторических запросах, либо через scraping — "обстрелять" сервис рекомендаций новыми запросами, чтобы он при этом использовал интересующие методы кандидато-генерации. В обоих случаях получаются результаты (предсказания финальной модели) для разных методов генерации для одних и тех же запросов. Это хорошо для чувствительности метрики.
Если же измерять эту метрику в онлайне, на продакшен-сервисе, то можно всё посчитать просто по залогированным предсказаниям модели. Это сильно проще, но не так гибко, и сравнение будет на разных запросах. Чувствительность метрики снижается (вдруг одному из методов просто достались более сложные запросы).
А теперь перейдём к общему случаю: финальное ранжирование — это не только предсказания какой-то модели, но и много другой логики, переранжирования, бизнес-правил, рандомизации и т.д. Если задуматься, как вообще сравнить разные наборы кандидатов в такой нестрогой формулировке (что такой хорошо и что такое плохо) — совсем не очевидно.
Но когда-то я придумал способ для этого, который получился очень простым и полезным. И до сих пор нигде не видел его упоминания.
Способ такой. Добавляем в список источников кандидатов специальный источник, который выдаёт случайных кандидатов (скажем, равномерно). Назначаем этому источнику небольшую фиксированную квоту (скажем, 50 кандидатов). И смотрим, какая доля порекомендованных документов в итоге из этого источника. Если наша кандидато-генерация достаточно хорошая, то случайные кандидаты крайне редко будут побеждать у неё, т.е. попадать в топ. Если же плохая — то часто.
Конечно, тут мы предполагаем, что добавление случайных кандидатов не сильно ухудшает систему: большинство из них не порекомендуется, а те, которые порекомендуются, не сильно ухудшат жизнь пользователей, да ещё и добавят exploration как пользователям, так и модели ранжирования (она дообучится на этих примерах). Если это не так, то сначала стоит "починить ранжирование". 😉
Самое прикольное в этом методе — что он может служить не только метрикой кандидато-генерации, но и мониторингом здоровья всей системы, в том числе и финального ранжирования. Он проверяет, насколько кандидато-генерация согласована с ранжированием (оптимизирована под ранжирование). Если само ранжирование по каким-то причинам деградирует, то и кандидаты становятся не такими уж хорошими для него. Мы это видели на практике, когда одна из компонент поломалась, доля рандомных кандидатов в ответе увеличилась.
Кстати, случайность этого специального источника можно настраивать. Если использовать не равномерную, а пропорциональную популярности документа, то это будет более сильный "adversarial" игрок (что тоже может увеличить чувствительность). Зато при равномерном сэмплировании можно дать аналитическую оценку того, в какой доле запросов наша кандидато-генерация была идеальной (т.е. результат бы не поменялся, даже если бы мы добавили в кандидаты всю базу).
Telegram
Wazowski Recommends
Как известно, в рекомендательных системах есть несколько стадий построения рекомендаций: сначала происходит генерация кандидатов, а затем — одна или несколько стадий ранжирования. В статьях уделяют не очень много внимания ранним стадиям. Но на практике они…
👍9🔥4🤔2❤1
Когда этим летом запускался Threads, большая часть ленты состояла из ВП — взаимного пиара.
Так вот, не могу не порекомендовать 😁
Если вам нравится этот канал, то вам обязательно понравится и канал Кирилла Хрыльченко: https://news.1rj.ru/str/inforetriever
Один из типов постов там (не единственный!), который лично для меня очень полезен: Кирилл раз в неделю выкладывает дайджест свежих статей с arxiv на тему рекомендаций, ранжирования и прочего information retrieval. Он это уже делает больше года, но только сейчас это стало публичным.
И про negative sampling, например, Кирилл тоже рассказывает в одном из недавних постов, можете сравнить. (И на меня тоже ссылается, куда ж без взаимности 😉)
Так вот, не могу не порекомендовать 😁
Если вам нравится этот канал, то вам обязательно понравится и канал Кирилла Хрыльченко: https://news.1rj.ru/str/inforetriever
Один из типов постов там (не единственный!), который лично для меня очень полезен: Кирилл раз в неделю выкладывает дайджест свежих статей с arxiv на тему рекомендаций, ранжирования и прочего information retrieval. Он это уже делает больше года, но только сейчас это стало публичным.
И про negative sampling, например, Кирилл тоже рассказывает в одном из недавних постов, можете сравнить. (И на меня тоже ссылается, куда ж без взаимности 😉)
Telegram
Information Retriever
Author: @kkhrylchenko
❤24👍3