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

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

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

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

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

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

Алгоритм ε-Greedy

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

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

import numpy as npclass 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 = 5eps = 0.1algo = EpsilonGreedy(epsilon=eps, n_arms=n_arms)# моделирование выбора рук для заданного числа испытанийn_trials = 1000rewards = 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, который может выбирать одно из нескольких возможных действий и обновлять их оценки на основе получаемого вознаграждения.

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

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

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

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

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

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

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

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

import mathimport numpy as np# параметры алгоритмаN = 10000 # общее количество раундовd = 10 # количество рекламных объявленийnumbers_of_selections = [0] * dsum_of_rewards = [0] * dads_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 += rewardprint("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 npclass 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 * xclass 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 выбирает действия на основе выборок из постериорного распределения параметров этой модели.

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

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

Пример:

import numpy as npclass 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 экспертов.