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

Меня зовут Александр Сухочев, я работаю в области машинного обучения и возглавляю команду по работе с рекомендациями и развитию сервисов ВКонтакте. Хочу поделиться нашим опытом и результатами внедрения контекстных многоруких бандитов для рекомендации контента на примере игр и стикеров.

Эта статья состоит из четырех частей. Если вы знакомы с темой, вы можете сразу перейти ко второй или третьей части или прочитать ее целиком, чтобы получить полную картину.

  • Введение рассказывает о существующих подходах к построению рекомендательных систем и о том, какое отношение к этому имеют многорукие бандиты. Этот раздел предназначен для тех, кто не знаком с этим подходом.
  • Основные алгоритмы решения задачи о многоруком бандите: эпсилон-жадный подход, выборка Томпсона, верхняя доверительная граница.
  • Алгоритм контекстных многоруких бандитов: в этом разделе рассказывается о контекстных многоруких бандитах и ​​о том, как они обучаются в конкретном сценарии, который мы использовали в нашем решении.
  • Примечания по реализации: описывает детали реализации, бизнес-требования и результаты на примере службы рекомендаций по играм и наклейкам.

Введение

Общий обзор типичной рекомендательной системы выглядит следующим образом:

  • Существует история взаимодействия между пользователем uₛ ∈ U и элементом контента iᵣ ∈ I.
  • В зависимости от бизнес-целей одни виды взаимодействия считаются положительными, а другие — отрицательными. То есть для каждой пары взаимодействий (uₛ, iᵣ) мы присваиваем ответ yₛᵣ ∈ Y и необязательно вес wₛᵣ.
  • Каждой паре (uₛ, iᵣ) присваиваются атрибуты xₛᵣ ∈ X (описания пользователя или контента или только их идентификатор).
  • Наша задача состоит в том, чтобы научить модель распознавать, какие новые пары пользователей и фрагментов контента могут положительно взаимодействовать в будущем, основываясь на X и Y.

Чего не хватает «классическим» рекомендациям по машинному обучению?

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

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

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

В литературе эта проблема называется компромиссом между эксплуатацией и разведкой:

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

Что такое многорукие бандиты?

В машинном обучении проблема многорукого бандита — это проблема эффективного сочетания разведки и эксплуатации. Свое название она получила из-за сходства с игрой в казино:

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

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

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

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

Основные алгоритмы решения задачи о многоруком бандите

Чтобы понять алгоритмы, мы сначала должны формализовать проблему. Существуют разные модели, но в общем случае проблему многоруких бандитов можно представить в виде схемы, как показано на рисунке 2.

Существует агент (алгоритм принятия решений в сети), среда (система) и потенциально бесконечная последовательность итераций взаимодействия между агентом и средой, пронумерованная индексом т. На каждом t-м шаге агент решает выполнить действие aₜ, среда в ответ на это действие дает ответ yₜ, которая прямо или косвенно (через функцию r(y)) характеризует выигрыш агента.

В общем, сигнал yₜ носит стохастический (недетерминированный) характер. Можно сказать, что действие агента aₜ на t-м шаге задает распределение вероятности ответа 𝕐ₜ, из которого конкретная реализация ответа yₜ получается путем случайной выборки (другими словами, берутся конкретные реализации случайной величины). Далее на основе вновь выполненного действия aₜ и полученного сигнала yₜ обновляем аппроксимации θ̂ параметров θ модели , описывающей зависимость откликов среды от выполняемых действий (блок обучение с учителем на схеме). В дальнейшем мы будем для краткости называть этот элемент моделью среды. Затем, основываясь на последних приближениях, алгоритм, который решает, какие действия следует выполнить (оптимизатор), предсказывает следующий шаг, который необходимо предпринять. Так выглядит каждая итерация взаимодействия агента со средой.

Задача о казино — это, пожалуй, один из простейших примеров задачи о многоруком бандите, а именно задачи Бернулли о многоруком бандите. В данной задаче модель зависимости откликов среды от выполняемых действий представляет собой набор бернуллиевских K-распределений: одно распределение на плечо aₖ, k∈ {1 ,…,К}. Каждое k-е распределение Бернулли представляет собой распределение случайной величины, которое может быть равно единице (выигрыш) с вероятностью θₖ или нулю (проигрыш) с вероятностью 1 – θₖ. Эти θₖ, k ∈ {1,…, K} являются параметрами этой модели. Несмотря на свою простоту, эта модель может быть использована для решения прикладных задач, и мы проанализируем основные подходы к решению задачи о многоруком бандите на ее примере. Далее мы опишем его недостатки и способы его усложнения, позволяющие от них избавиться.

Эпсилон-жадный подход

Простейшим подходом является эпсилон-жадный алгоритм. В общем, это работает так:

  • С вероятностью ε выбираем ту руку бандита, которая по уже имеющимся данным имеет наибольший средний выигрыш, а с вероятностью 1–ε — случайную руку.
  • Обновление математических ожиданий выплат для всех рук.
  • Повторить с первого шага.

Этот подход тривиально применяется к задаче Бернулли о бандитах:

  • Отношение побед к количеству попыток рассчитывается для каждой руки.
  • Рукав с максимальным соотношением используется с вероятностью ε — это эксплуатация, случайная рука используется с вероятностью 1–ε — это разведка.
  • Соотношение обновляется на основе новых полученных данных

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

Для ясности скажем, что мы хотим порекомендовать изображения кошек.

Через какое-то время мы собрали следующие данные: первый набрал 2000 лайков и 100000 просмотров, второй не набрал лайков и только 10 просмотров, третий набрал 1 лайк и 10000 просмотров. Здесь мы видим лайки как вознаграждение, а просмотры как попытки.

На этапе эксплуатации будет выбрана первая кошка как наиболее перспективная на основе имеющейся информации.

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

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

Байесовский теоретический минимум

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

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

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

Вместо абстрактных A и B мы можем сразу заменить понятия, относящиеся к машинному обучению, на учитель A= Y|X (отклики модели с учетом факторов) и B = θ (параметры модели машинного обучения). В результате получаем следующее:

где p(θ) — текущие представления модели, выраженные как плотность распределения параметров модели и основанные на предыдущих данных и основных априорных представлениях (или исключительно на априорных представлениях, если данных еще нет). В литературе этот фактор называется априорным распределением.

p(Y|θ, X) содержит информацию о вновь полученных данных в виде их функции правдоподобия . Вероятность — именно так этот фактор называется в литературе.

p(θ|Y, X) — обновленное представление модели, основанное на старой модели в сочетании с новые данные. В литературе этот фактор называется апостериорным распределением.

Фактор

требуется для нормализации. Если его удалить, то

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

Иногда нормализующий коэффициент может быть рассчитан аналитически, и в этом случае мы говорим, что проводим байесовский вывод. Однако, за исключением простейших случаев, вычислить его аналитически крайне сложно или просто невозможно. Численный расчет может занять очень много времени, поэтому мы попытаемся приблизить апостериорное распределение p(θ|X) к некоторому распределению q(θ), с которым удобнее работать для оценки плотности и отбора проб, что позволяет избежать сложных вычислений нормировочных констант. Этот подход называется приближенным вариационным выводом.

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

Давайте посмотрим, как апостериорное распределение в задаче Бернулли о бандитах получается с помощью аналитического вычисления нормировочной константы. Другими словами, мы посмотрим, как делается байесовский вывод. В данном случае у нас нет контекстных факторов, поэтому вместо Y|X рассмотрим только Y.

Параметр θ представляет собой набор параметров θₖ, каждый из которых в данном случае описывает вероятность получения вознаграждения при использовании k-го arm и таким образом задает следующую плотность распределения данных:

Yₖ — ответы на попытки использовать k-ю руку. yₖᵢ — ответ на i-ю итерацию использования k-ой руки.

В качестве априорного распределения параметров θₖ используем бета-распределение:

αₖ и βₖ — параметры k-го бета-распределения (т.е. параметры распределения параметра θₖ). B(α, β) — бета-функция, конкретный вид которой в данном случае не важен. Среди всех семейств дистрибутивов мы выбрали бета-дистрибутивы, потому что:

  • он задает распределение значения на интервале от 0 до 1 (а θ может принимать значения только из этого интервала).
  • Если используется такое априорное распределение, то апостериорное распределение рассчитывается аналитически (это будет продемонстрировано позже).

Обновление апостериорного распределения при сборе новых данных очень просто, по сути, апостериорное распределение, как и априорное здесь, является бета-распределением и имеет следующие параметры:

Таким образом, апостериорное распределение рассчитывается аналитически и поэтому чрезвычайно быстро.

Краткое доказательство этого факта:

В этом случае,

но мы можем его игнорировать, потому что наше апостериорное распределение выглядит так:

то есть апостериорное распределение напоминает бета-распределение с точностью до константы (но теперь αₖ становится ∑ᵢ[yₖᵢ =1]+ αₖ,и βₖ становится ∑ᵢ[yₖᵢ =0]+βₖ.

Таким образом, мы можем легко восстановить нормализующую константу C' = B(∑ᵢ[yₖᵢ =1]+αₖ, ∑ᵢ[yₖᵢ =0]+βₖ) —просто взяв его из определения бета-распределения с обновленными параметрами.

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

Выборка Томпсона

В общем случае сэмплирование Томпсона работает следующим образом:

  • Значения выбираются из заданного апостериорного распределения параметров среды θ.
  • Считая результаты выборки истинными значениями параметров среды, выбираем действие, приводящее к наибольшему математическому ожиданию выигрыша.
  • Получив новые данные, пересчитываем обновленное апостериорное распределение параметров θ, считая предыдущее апостериорное распределение априорным.
  • Повторяем все с первого пункта.

Применительно к задаче бандита Бернулли этот алгоритм выглядит следующим образом. Среда описывается набором параметров θₖ (по одному на каждое k-е плечо), каждый параметр имеет априорное бета-распределение. На каждой итерации делаем следующее:

  • Выберите значения Θₖ ∼ p(θₖ) из каждого бета-распределения параметров θₖ каждой руки.
  • Выбранные значения Θₖ рассматриваются как вероятность выигрыша с каждой руки, таким образом, оптимальное действие равно argmaxₖ Θₖ.
  • Получив новую информацию из среды в ответ на наши действия, мы пересчитываем значения параметров бета-распределения, как описано выше.
  • Повторяем все с первого шага.

Отбор проб Томпсона реализует гораздо более эффективную стратегию компромисса между разведкой и эксплуатацией. Интуитивно это можно понять так: когда мы выбираем Θₖ из распределений p(θₖ), то получаются наибольшие значения либо из распределений с большим математическим ожиданием (в этом случае мы ближе к эксплуатации), либо из распределений с большой дисперсией (в этом случае мы ближе к разведке).

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

  • либо первая картинка с α = 2000 + 1 = 2001 (мы предполагаем, что априорное значение α = 1), β = 100000–2000 + 1 = 98001 (мы предположим, что априорное значение β = 1), а значит, математическое ожидание

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

  • альтернативно, второе фото с α = 0 + 1 = 1, β = 10–0 + 1 = 11, и поэтому дисперсия равна

При такой относительно большой дисперсии высока вероятность появления больших значений Θᵢ.

Третья картинка имеет очень маленькие шансы быть выбранной, так как она имеет как маленькое математическое ожидание, так и

и небольшой разброс

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

где T — количество итераций решения, t — номер текущей итерации, E(yₜ| a*) — математическое ожидание случайной величины yₜ при выполнении оптимального действия a*, E(yₜ|a ᵗ) — математическое ожидание случайной величины yₜ, если действие aᵗ выполняется нашим алгоритмом.

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

Верхняя доверительная граница

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

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

Алгоритм контекстных многоруких бандитов

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

Наивный подход

Самый простой способ учесть контекст — разделить пространство признаков пользователя на отдельные ячейки по значениям признаков, чтобы затем посчитать «бандитскую» статистику по каждой ячейке.

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

Кружки представляют взаимодействия пользователя с контентом в истории. Для простоты учитываем только два фактора: пол и возраст.

Для каждой ячейки существует набор k бета-распределений параметров θ₁ … θₖ, который пересчитывается на основе содержащихся в нем данных , независимо от других ячеек. Другими словами, для каждого плеча мы вычисляем M количество бета-распределений, где M — количество ячеек.

Таким образом, вместо K количества раздач в случае, когда мы обращаемся к контексту, мы должны учитывать и пересчитывать K * M дистрибутивы.

Этот подход имеет несколько недостатков:

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

Логистическая регрессия + вариационный вывод

Пришло время в корне изменить модель среды. Если раньше вероятность бинарного выигрыша при использовании k-й руки зависела от одного параметра θₖ, то теперь введем вектор параметров θₖ = (θₖ¹, …, θₖᵛ) для каждой руки. Пусть контекст характеризуется вектором признаков x = (x¹, …, xᵛ), тогда вероятность выигрыша при использовании k-я рука будет равна

сигмоид здесь гарантирует, что значение, которое мы получаем от модели, будет находиться в диапазоне от 0 до 1.

Вероятность для каждого k-го плеча также рассчитывается отдельно и выглядит так:

Yₖ здесь обозначают исключительно ответы на попытки использовать k-ю руку, yₖᵢ — ответ на i-я итерация использования k-й руки, xₖᵢ — соревнование на i-й итерации использования k-я рука.

В этом случае уже сложно подобрать априорное распределение, которое соответствовало бы распределению правдоподобия и позволяло аналитически вычислить апостериорное распределение.

Поэтому в качестве априорного распределения мы просто берем самое популярное — многомерное нормальное распределение:

апостериорное распределение будет получено с использованием приближенного вариационного вывода, а именно приближения Лапласа.

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

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

Ковариационная матрица приближенного апостериорного распределения находится по формуле:

Вывод формул

Чтобы найти

Рассмотрим отдельно числитель

и его логарифм

После того, как мы найдем θₖ*, ​​можно будет представить g(θₖ) в окрестности этой точки по формуле Тейлора с точностью до второго порядка.

поскольку θₖ* является экстремумом, g’(θₖ*) = 0.

Таким образом, мы получаем:

Взяв экспоненту из обеих частей, мы получим:

Это ненормализованная форма аппроксимации апостериорного распределения. Здесь первый множитель f(θₖ*) — это просто константа, связанная с θₖ, она нас сейчас не интересует. Второй фактор

можно привести к форме экспоненциального множителя:

из формулы плотности многомерного нормального распределения:

Для этого мы должны заменить

Используя эту аналогию и зная нормализующую константу для экспоненциального фактора из формулы плотности нормального распределения, это остальная часть формулы, т.е. е.,

мы также можем найти нормализующую константу для f(θₖ) :

В результате получаем:

Таким образом, мы получили формулу пересчета апостериорного распределения.

Заметки о внедрении и наши результаты

Мы применили метод многоруких контекстных бандитов с лапласовской аппроксимацией и выборкой Томпсона для продвижения игр и стикеров на второй вкладке нашей платформы.

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

Контекст принятия решений

В контекст включались характеристики пользователя: пол, возраст и любые особенности его интересов.

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

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

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

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

Далее мы разложили пользователя по его кластерам групп, и эта раскладка использовалась как особенности интересов пользователя.

Что такое положительные и отрицательные взаимодействия?

Рекомендации по стикерам и играм в мобильных приложениях отображаются пользователю в виде виджета с горизонтальной прокруткой на вкладке Hub.

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

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

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

Мы решили считать взаимодействия отрицательными в случаях, когда пользователь точно видел рекомендуемый объект и намеренно не проявлял к нему интереса. Для этого мы берем все объекты в виджетах горизонтальной прокрутки, расположенные слева от объекта, на который нажал пользователь, как примеры негативного взаимодействия. На картинке ниже такими примерами негативных взаимодействий являются «Дрин» и «Донни».

Различные значения сигнала

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

Квазислучайная выборка

Эксперименты показали, что новые объекты, прежде чем участвовать в выборке Томпсона на равных, должны сначала рекомендоваться квазислучайно.

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

Существует много типов квазислучайной выборки. Наиболее популярным, пожалуй, является квазислучайная выборка на основе последовательности Соболя. Что касается нас, то мы используем семплер, который создали сами.

Полученные результаты

Прежде всего, мы протестировали наш алгоритм на играх для Android. Мы сравнили рекомендации классического машинного обучения, смешанные с бандитскими рекомендациями, и чисто классические рекомендации машинного обучения с помощью A/B-тестирования.

Поначалу показатели в тестовой группе несколько снизились по сравнению с контрольной группой, но уже через две недели начали неуклонно расти. Через два месяца эффект составил +8% установок игры, +2% запусков, после чего мы применили новую систему рекомендаций ко всей аудитории. Что касается наклеек, то выручка от их продажи увеличилась на +5% по сравнению с классическими рекомендациями ML.

В обоих случаях внимание пользователей начало привлекать больше элементов, а именно игр и наклеек.

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

Вы можете узнать больше о других вещах, связанных с машинным обучением, которые мы делаем в нашей компании, просматривая наши сообщения в блогах. Взгляните, например, на наши статьи «Практическое руководство по статистическим тестам» и «ПЮМК в ВК: МО через EGO-NETS».