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

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

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

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

Алгоритм ε-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 экспертов.