Введение в алгоритм Epsilon Greedy и выборку Томпсона
На июльской встрече тайваньских профессионалов в области данных Гэри Чен из Amex дал отличное введение в предвзятость выживания и алгоритм решения этой проблемы, алгоритм Epsilon Greedy и выборку Томпсона. В этой статье я с нуля объясню, как это работает. Часть кода модифицирована из класса Байесовское машинное обучение на Udemy.com. Это подробный, но краткий материал, который я настоятельно рекомендую.
Хорошо, поехали!
Определение проблемы
Представьте, что ваша компания проводит маркетинговые кампании на основе электронных писем. Естественно, некоторые клиенты с большей вероятностью откроют электронные письма, а некоторые нет. Но перед запуском любой кампании вы ничего не знаете о своих клиентах. Единственный способ узнать, насколько вероятно, что клиент откроет электронное письмо, - это собрать данные, отправив ему целую пачку писем, и понаблюдать за скоростью отклика. Вопрос в том, сколько электронных писем мы должны отправить всем клиентам, чтобы установить статистическую значимость?
Если мы отправим 100 писем каждому покупателю, мы, вероятно, сможем получить некоторое представление о том, кто является нашими оптимальными целями. Но это очень неэффективно! В ходе кампании мы хотим привлечь как можно больше клиентов. Между тем, мы также хотим ориентироваться на клиента, у которого самый высокий уровень отклика, это наши оптимальные клиенты, которые дают лучшее вознаграждение. Это компромисс между исследованием и эксплуатацией.
Компромисс между разведкой и эксплуатацией - это дилемма, с которой мы часто сталкиваемся, выбирая один из вариантов. Следует ли вам выбрать то, что вы знаете, и получить что-то близкое к тому, что вы ожидаете («использовать»), или выбрать то, в чем вы не уверены и, возможно, узнать больше («изучить»)?
проблема может существовать в самых разных контекстах. Например, маркетинговая кампания, A / B-тестирование веб-сайта или ваши стратегии в отношении азартных игр. Суть задачи по сути та же.
Эпсилон Жадный
Чтобы решить проблему использования и исследования, жадный алгоритм epsilon присваивает вероятность ε, что мы случайным образом исследуем больше клиентов. В остальное время мы используем клиента с наивысшей вероятностью p на основе известных нам до сих пор. Псевдокод можно записать следующим образом:
while True:
r = random.random()
if r < eps:
#explore
#show ads to random customer
#update p
pass
else:
#exploit
#show ads customer with highest p
break
Чтобы настроить эксперименты, я написал класс Python, чтобы восстановить внутреннюю вероятность клиента и прошлые записи реакций. Обратите внимание, что внутренняя вероятность считается гауссовским распределением, характеризуемым p_mean и p_sigma. Следовательно, вместо постоянной вероятности каждый раз, когда мы обращаемся к клиенту, вероятность открытия ссылки - это случайное число, полученное из гауссовского.
class Target(object):
def __init__(self,p_mean,p_sigma):
self.p_mean = p_mean
self.p_sigma = p_sigma
self.a = 1
self.b = 1
self.n = 0
def trigger(self):
return np.random.random() < np.random.normal(loc=self.p_mean, scale=self.p_sigma)
def sample(self):
return np.random.beta(self.a, self.b)
def prob(self):
return self.a/(self.a + self.b)
def update(self, x):
self.a += x
self.b += 1 - x
self.n += 1
Конструктор класса __init__ принимает два параметра: p_mean и p_sigma. Мы также запускаем self.a = 1 и self.b = 1, указываем общие успехи и общие неудачи. соответственно. a и b вначале установлены равными 1 для удобства в дальнейших экспериментах. Метод класса trigger () вернет результат теста путем сравнения равномерного случайного числа с выборкой, взятой из гауссовского распределения. Метод prob () вернет эмпирическую вероятность, основанную на предыдущем тесте. Наконец, метод update () записывает историю тестирования цели.
def experiment():
#Create target objects for epsilon greedy
Targets = [Target(p,s) for p,s in zip(p_means,p_sigmas)]
n_pulling = [0,0,0]
regret = 0
cumulative_regret = []
for i in range(num_trials):
best_target = None
max_prob = -1
#with probability epsilon, we explore more data
r = np.random.random()
if r < epsilon: #
index = np.random.randint(0,len(Targets))
best_target = Targets[index]
else:
for n,target in enumerate(Targets):
prob = target.prob()
if prob > max_prob:
maxprob = prob
best_target = target
index = n
x = best_target.trigger()
best_target.update(x)
regret += optimal-x
cumulative_regret.append(regret)
plot(Targets, cumulative_regret, cumulative_reward, num_trials)
num_trials = 1000
p_means = [0.2, 0.5, 0.7]
p_sigmas = [0.1, 0.1, 0.1]
optimal = max(p_means)
epsilon = 0.2
experiment()
Это фрагмент кода на Python, реализованный на основе жадного алгоритма epsilon. Для удобства мы упростили эксперимент до трех вариантов. Мы также вводим новую переменную сожаление для оценки производительности. Сожаление определяется как потеря по сравнению с оптимальным выбором. Другими словами, если мы всегда нацелены на клиента с наибольшей вероятностью, то мы не жалеем. Поэтому наша цель - свести к минимуму кумулятивное сожаление с течением времени.
В левой части показано распределение вероятностей p для каждого варианта после 1000 испытаний. Первое, что мы заметили, это то, что зеленая линия имеет гораздо более узкое распределение, чем другие, это означает, что мы почти уверены, что зеленая линия - лучшая цель, поэтому мы выбираем зеленую цель 872 раза из 1000 испытаний.
Между тем, из-за случайного исследования две другие цели достаточно изучены. Как следствие случайного исследования, кумулятивное сожаление всегда увеличивается! Решение исправить это - Upper Confidence Bond. Алгоритм UBC решит, когда мы сможем с уверенностью остановить случайное исследование с помощью собранных данных. В качестве альтернативы, мы можем подумать о более разумном способе беспрепятственного изучения клиента, не увеличивая сожаления.
Сэмплинг Томпсона
Выборка Томпсона - это приложение теоремы Байеса. Теорема Байеса предоставляет мощный инструмент для оценки распределения вероятностей параметров. Левая часть уравнения является апостериорной, что часто интерпретируется как распределение вероятностей параметра заданных данных. А правая часть - это вероятность, кратная априорному делению на предельную вероятность.
В нашем случае функция правдоподобия - это распределение Бернулли. Распределение Бернулли дает два возможных результата (0,1) и параметризуется с помощью p. То есть каждый раз, когда мы обращаемся к покупателю, он / она имеет внутреннюю вероятность p открыть ссылку (выход = 1) и вероятность 1-p игнорировать его (результат = 0).
Для предыдущего распределения мы используем Бета-распределение. В байесовской статистике мы часто выбираем сопряженное априорное для функции правдоподобия, чтобы гарантировать, что апостериорное распределение такое же, как априорное. В результате мы можем сократить вычисления.
Звучит сложно, но на самом деле очень просто. Бета-распределение характеризуется двумя параметрами и β. Вначале мы берем образец из бета-версии (⍺ = 1, β = 1) и запускаем тест. Если результатом является голова (x = 1) m, мы обновляем апостериорную бета-версию (⍺ ’= ⍺ + 1, β’ = β). И мы запускаем еще один тест, используя новую бета-версию, как и раньше, обновляем гиперпараметры. Снова и снова, в конце концов, апостериорная функция будет давать нам истинное распределение p. В псевдокоде:
⍺1=β1=⍺2=β2...⍺k=βk=1
while True:
# draw samples from Beta_i(⍺i,βi) i=0-k
# show ads to sample with largest number
# receive response x = 0 or 1
# update posterior ⍺'= ⍺+x,β'= β+(1-x)
Чтобы реализовать выборку Томпсона, нам просто нужно добавить несколько строк кода в предыдущую функцию эксперимента ():
#Thompson Sampling
for n, target in enumerate(Targets):
sample = target.sample()
if sample > max_prob:
max_pro = sample
best_target = target
index = n
Обратите внимание, что единственное отличие состоит в том, что мы сравниваем выборки, взятые из бета-распределения, а не напрямую сравниваем с эмпирической вероятностью.
Результат значительно улучшился! С помощью выборки Томпсона алгоритм вскоре узнал, какая из них является лучшей целью, и придерживался ее, не теряя времени, на случайное исследование большего количества данных.
Из графика кумулятивного сожаления мы ясно видим, что кумулятивное сожаление значительно ниже после 300 испытаний и превращается в плоский, что означает, что алгоритм научился всегда выбирать оптимальную цель.
Мы можем извлечь выгоду из Thompson Sampling с меньшим количеством испытаний и максимальным вознаграждением.
Вывод
В реальном мире вероятность открытия ссылки обычно составляет около 3–5% или даже ниже. Также клиентская база намного больше. На следующей неделе я собираюсь провести больше экспериментов на производительности обоих алгоритмов с гораздо большим количеством целей и меньшей вероятностью. Я также попробую другие идеи для улучшения алгоритма, такие как установка другого начального априорного или другого эпсилон.
Полный код Python можно найти на моем гитхабе. Надеюсь, этот пост поможет вам лучше понять жадный алгоритм epsilon и выборку Томпсона. Если у вас есть вопросы, напишите мне в комментариях. Спасибо!
