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

Привет, Хабр!

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

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

Основные алгоритмы

Алгоритм ε-Greedy

Алгоритм ε-Greedy работает следующим образом: с вероятностью ϵ (исследование) выбирается случайное действие, а с вероятностью 1−ϵ (использование) выбирается действие, которое на данный момент кажется наилучшим. Это позволяет алгоритму избежать застревания на локальных оптимумах и способствует более полному изучению пространства возможных действий.

Пример простой реализации алгоритма ε-Greedy на Python:

import numpy as np  class EpsilonGreedy:     def __init__(self, epsilon, n_arms):         self.epsilon = epsilon         self.counts = [0] * n_arms  # количество выборов каждого действия         self.values = [0.0] * n_arms  # среднее вознаграждение каждого действия      def select_arm(self):         if np.random.random() > self.epsilon:             return np.argmax(self.values)  # выбираем лучшее действие         else:             return np.random.randint(0, len(self.values))  # случайное действие      def update(self, chosen_arm, reward):         # обновление счётчика и значения вознаграждения для выбранного действия         self.counts[chosen_arm] += 1         n = self.counts[chosen_arm]         value = self.values[chosen_arm]         new_value = ((n - 1) / float(n)) * value + (1 / float(n)) * reward         self.values[chosen_arm] = new_value  # пример использования n_arms = 5 eps = 0.1 algo = EpsilonGreedy(epsilon=eps, n_arms=n_arms)  # моделирование выбора рук для заданного числа испытаний n_trials = 1000 rewards = np.random.rand(n_trials, n_arms)  # предположим, награды равномерно распределены  for i in range(n_trials):     arm = algo.select_arm()     reward = rewards[i, arm]     algo.update(arm, reward)  print("Средние вознаграждения:", algo.values)

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

И получили такой результат:

Средние вознаграждения: [0.5019984566933633, 0.4981757939224485, 0.3956261386254703, 0.5049212898077463, 0.477639394771559]

Алгоритм Upper confidence bound (UCB)

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

Шаги алгоритма:

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

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

3. Обновление: после выбора действия и получения вознаграждения обновляем среднее вознаграждение и количество выборов для этого действия.

Формула для доверительного интервала UCB выглядит так:

где x — ср. вознаграждение за действие, n — кол-во раз, когда это действие было выбрано, а t — общее кол-во сыгранных раундов.

Реализация UCB для оптимизации кликов по рекламе:

import math import numpy as np  # параметры алгоритма N = 10000  # общее количество раундов d = 10  # количество рекламных объявлений  numbers_of_selections = [0] * d sum_of_rewards = [0] * d ads_selected = [] total_reward = 0  # основной цикл for n in range(1, N):     ad = 0     max_upper_bound = 0     for i in range(d):         if numbers_of_selections[i] > 0:             average_reward = sum_of_rewards[i] / numbers_of_selections[i]             delta_i = math.sqrt(3/2 * math.log(n + 1) / numbers_of_selections[i])             upper_bound = average_reward + delta_i         else:             upper_bound = 1e400  # использовать большое число для исследования всех действий          if upper_bound > max_upper_bound:             max_upper_bound = upper_bound             ad = i      ads_selected.append(ad)     numbers_of_selections[ad] += 1     reward = np.random.randint(2)  # имитация клика (0 или 1)     sum_of_rewards[ad] += reward     total_reward += reward  print("Total Reward:", total_reward)

Смоделировали выбор между разными рекламными объявлениями с использованием UCB, где предполагается, что награда за выбор объявления — это клик или его отсутствие (моделируется случайным образом).

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

Алгоритм LinUCB

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

Алгоритм делится на два основных объекта: linucb_disjoint_arm и linucb_policy.

linucb_disjoint_arm:

• __init__(self, arm_index, d, alpha): инициализация руки, где arm_index — это индекс руки, d — размерность контекста, alpha — параметр, который регулирует баланс между исследованием и использованием.

• calc_UCB(self, x_array): вычисляет верхнюю границу уверенности для данной руки на основе контекста x_array.

• reward_update(self, reward, x_array): обновляет параметры на основе наблюдаемой награды и контекста.

linucb_policy:

• __init__(self, K_arms, d, alpha): инициализация политики с указанным количеством рук, размерностью контекста и параметром alpha.

• select_arm(self, x_array): выбирает руку на основе максимальной оцененной верхней границы уверенности среди всех рук.

Пример:

import numpy as np  class linucb_disjoint_arm:     def __init__(self, arm_index, d, alpha):         self.arm_index = arm_index         self.alpha = alpha         self.A = np.identity(d)         self.b = np.zeros([d, 1])      def calc_UCB(self, x_array):         A_inv = np.linalg.inv(self.A)         theta = np.dot(A_inv, self.b)         x = x_array.reshape([-1, 1])         p = np.dot(theta.T, x) + self.alpha * np.sqrt(np.dot(x.T, np.dot(A_inv, x)))         return p      def reward_update(self, reward, x_array):         x = x_array.reshape([-1, 1])         self.A += np.dot(x, x.T)         self.b += reward * x  class linucb_policy:     def __init__(self, K_arms, d, alpha):         self.K_arms = K_arms         self.linucb_arms = [linucb_disjoint_arm(i, d, alpha) for i in range(K_arms)]      def select_arm(self, x_array):         highest_ucb = -1         candidate_arms = []          for i in range(self.K_arms):             ucb = self.linucb_arms[i].calc_UCB(x_array)             if ucb > highest_ucb:                 highest_ucb = ucb                 candidate_arms = [i]             elif ucb == highest_ucb:                 candidate_arms.append(i)          return np.random.choice(candidate_arms)  # пример использования d = 5  # размерность контекста K_arms = 10  # количество рук alpha = 1.0  # параметр баланса исследования и использования policy = linucb_policy(K_arms, d, alpha)  # допустим, у нас есть контекстный вектор для текущего пользователя x_context = np.random.rand(d)  # выбор руки chosen_arm = policy.select_arm(x_context) print("Выбранная рука:", chosen_arm)

Код создаёт политику с несколькими руками, каждая из которых может оценивать

Алгоритм LinTS (Linear Thompson sampling)

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

Основные шаги алгоритма:

1. Инициализация: На начальном этапе устанавливаются гиперпараметры и начальные значения матриц.

2. Обновление постериорных распределений: после каждого действия алгоритм обновляет постериорное распределение параметров модели на основе полученных наград и контекстов.

3. Выборка и действие: для каждого возможного действия алгоритм генерирует выборку параметров из постериорного распределения и выбирает действие с макс. предсказанным значением награды.

Пример:

import numpy as np  class LinTS:     def __init__(self, d, sigma_prior):         self.d = d         self.sigma_prior = sigma_prior         self.beta = np.zeros(d)         self.A = np.identity(d) * sigma_prior      def select_action(self, contexts):         samples = np.random.multivariate_normal(self.beta, np.linalg.inv(self.A))         idx = np.argmax(np.dot(contexts, samples))         return idx, contexts[idx]      def update(self, chosen_context, reward):         self.A += np.outer(chosen_context, chosen_context)         self.beta += reward * chosen_context  # параметры d = 5  # размерность контекста sigma_prior = 1.0  # дисперсия априорного распределения  # инициализация алгоритма model = LinTS(d, sigma_prior)  # предположим, у нас есть набор контекстов contexts = np.random.rand(10, d)  # 10 возможных действий  # выбор действия action_index, chosen_context = model.select_action(contexts)  # симуляция получения награды reward = np.random.randn()  # обновление модели model.update(chosen_context, reward)

LinUCB обычно дает более консервативные, но стабильные результаты, так как опирается на доверительные интервалы.

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

Углубить свои знания в области рекомендательных систем можно на трёхмесячном онлайн-курсе OTUS под руководством DS & ML экспертов.