Принципиальный подход к ранним стадиям ранжирования

Использование принципиального подхода к ранним стадиям ранжирования

Систематический метод проектирования и оценки этапов генерации кандидатов и ранней ранжировки в рекомендательных системах с подробным анализом основного принципа.

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

Иллюстрация от автора

Генерация кандидатов чаще всего организована как сочетание различных источников:

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

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

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

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

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

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

Подход основан на следующем принципе:

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

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

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

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

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

Недостатки подхода

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

От хаков к гармонии: структурирование продуктовых правил в рекомендациях

Не позволяйте эвристикам подрывать ваше МО, научитесь их объединять

towardsdatascience.com

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

Преимущества подхода

  • Принцип основан на декомпозиции. Он предоставляет начальным стадиям более ясную и измеримую цель, существенно упрощая систему. Сложность, связанная с выбором целей и потерь для рекомендаций, концентрируется на стадии ранжирования (аспект, который нельзя избежать), в то время как начальные стадии в основном сосредоточены на утилитарной задаче эффективного поиска лучших кандидатов. Таким образом, начальные стадии служат просто инструментом для ускорения процесса ранжирования.
  • В этом принципе нет фундаментальных ограничений. Если представить себе идеальную систему рекомендаций, ничто не мешает ей быть структурированной таким образом. (В отличие от других подходов – идеальные рекомендации не обязаны угадывать, с чем пользователь взаимодействует!) И по мере улучшения ранжирования, такие упрощенные метрики для генерации кандидатов становятся все ближе к конечным метрикам. Это подобно известному итерационному подходу в некоторых кругах: “улучшайте метрики – улучшайте продукт на основе этих метрик”.
  • Разные стадии ранжирования выровнены между собой; они не пытаются оптимизировать разные вещи. В системах, где это не так, например, если вы удвоите общее количество кандидатов, общее качество системы может не улучшиться, а на самом деле ухудшиться. Например, если начальные стадии оптимизированы по отношению к некоей релевантности, то дополнительные кандидаты будут менее релевантными, и общая релевантность уменьшится (хотя кликабельность может увеличиться).
  • В результате аспекта декомпозиции: начальные стадии гораздо легче измерять (и, следовательно, оптимизировать). Процесс оценки будет рассмотрен в следующем разделе. Обучение, по сути, сводится к сжатию модели ранжирования. (Хотя есть нюансы. Например, было бы хорошо записывать некоторых кандидатов, которые не прошли на верхнюю позицию в ранжировании.)
  • Более того, для обучения и измерения начальных стадий нам уже не нужны пользователи, что означает, что нет необходимости выпускать для них новый метод. Например, можно использовать скрапинг, как мы обсудим позже, отправляя несколько запросов с помощью новых кандидатов в службе ранжирования.

Измерение генерации кандидатов

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

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

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

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

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

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

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

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

Искусственные данные только для иллюстрации

Конечно, здесь мы предполагаем, что добавление случайных кандидатов не приведет к существенному ухудшению системы: большинство из них не будут рекомендоваться, и те, которые рекомендуются, не сильно ухудшат пользовательский опыт и даже добавят возможность для исследования как для пользователей, так и для модели ранжирования (она дополнительно обучится на этих примерах). Если это не так, тогда сначала необходимо “исправить ранжировку”. 😉

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

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

В этой формуле N представляет собой общее количество кандидатов в базе данных, k – количество случайных кандидатов, используемых, а R обозначает отношение запросов, в которых по крайней мере один случайный кандидат появляется в выводе.

Заключение

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