Узнайте об алгоритме выборки Томпсона (байесовские бандиты).
Вступление
В этой серии публикаций мы экспериментируем с различными алгоритмами бандитов, чтобы оптимизировать наши вечера кино - в частности, с тем, как мы выбираем фильмы и рестораны для доставки еды!
Для новичков название бандит происходит от игровых автоматов (известных как однорукие бандиты). Вы можете думать об этом как о чем-то, что может вознаграждать вас (или нет) каждый раз, когда вы взаимодействуете с ним (дергаете его за руку). Задача состоит в том, чтобы дать группе бандитов, которые дают разные награды, как можно быстрее определить того, кто дает самые высокие. Когда мы начинаем играть и непрерывно собираем данные о каждом бандите, алгоритм бандита помогает нам выбирать между использованием того, который принес нам самые высокие награды, и исследованием других.
Вы и ваш друг использовали алгоритмы бандитов, чтобы оптимизировать, какие рестораны и фильмы выбрать для еженедельного вечера кино. До сих пор вы пробовали различные алгоритмы бандитов, такие как Эпсилон-Жадный, Оптимистические начальные значения и Верхние границы уверенности (UCB). Вы обнаружили, что алгоритм UCB1-Tuned работает немного лучше, чем остальные, как для вознаграждений Бернулли, так и для обычных наград, и в конечном итоге использовали его в течение последних нескольких месяцев.
Несмотря на то, что ваши вечера кино проходят отлично с выбором, сделанным UCB1-Tuned, вам не хватает острых ощущений от опробования нового алгоритма.
«Вы слышали о Thompson Sampling?» - спрашивает твой друг.
В восторге вы берете телефон и начинаете читать об этом.
Алгоритм
Выборка Томпсона, также известная как Байесовские бандиты, представляет собой байесовский подход к проблеме многоруких бандитов. Основная идея состоит в том, чтобы рассматривать среднее вознаграждение 𝛍 от каждого бандита как случайную величину и использовать данные, которые мы уже собрали, для расчета его распределения. Затем на каждом этапе мы будем отбирать точку из среднего распределения вознаграждений каждого бандита и выбирать ту, чья выборка имела наибольшее значение. Впоследствии мы получаем награду от выбранного бандита и обновляем его среднее распределение наград.
Я слышал, вы спросите, как мы рассчитываем / обновляем распределения? Название «Байесовские бандиты», возможно, уже выдало это, но мы воспользуемся теоремой Байеса.
Bayes Theorem P(A|B) = P(B|A) P(A) / P(B) where A, B: events in sample space P(A|B): conditional probability of A given B P(B|A): conditional probability of B given A P(A): probability of A P(B): probability of B
Приведенное выше определение предназначено для дискретных переменных, для непрерывных переменных оно определено для функций плотности вероятности.
В нашем случае для каждого бандита мы хотим вычислить их P (𝛍 | data), то есть насколько вероятны разные значения 𝛍, учитывая данные, которые мы собрали до сих пор.
P( 𝛍 | data ) = P(data | 𝛍) P(𝛍) / P(data)
∝ P(data | 𝛍) P(𝛍)
posterior ∝ likelihood x prior
Бандиты с большим количеством точек данных будут иметь узкое распределение, поэтому точка данных, которую мы отбираем, будет иметь высокий шанс быть близкой к реальному среднему значению. Бандиты с небольшим количеством точек данных, однако, будут иметь широкое распространение, что дает высокие шансы быть выбранными. Этот механизм уравновешивает исследование и эксплуатацию.
Теперь вычислить P (𝛍 | data) сложно, если вероятность и априор не являются сопряженными априорными числами. Это означает, что когда мы объединяем вероятность и априор, мы получаем апостериорное распределение из того же семейства, что и априорное. Это удобно по двум причинам:
- Мы можем избежать неприятных вычислений для определения апостериорного значения, поскольку для него существует выражение в закрытой форме.
- Мы можем использовать апостериорную последовательность из шага i-1 как предыдущую для шага i. Это упрощает переход от P (𝛍 | данные до шага i-1) к P (𝛍 | данные до шага i) и гарантирует, что мы работаем только с сопряженными априорными числами. .
Награды Бернулли
В оставшейся части этого поста мы будем предполагать, что бандит дает награду 1 с вероятностью и 0 в противном случае, т.е.
ith bandit rewards ~ Bernoulli(prob = 𝛍_i)
Теперь нам нужно выбрать априорное распределение для 𝛍. Поскольку 𝛍 - это вероятность успеха, она может принимать только значения от 0 до 1. Следовательно, нам нужно распределение с поддержкой [0, 1]. Одним из таких распределений является бета-распределение с параметрами a и b. Прежде чем мы соберем какие-либо данные, все значения 𝛍 равновероятны, следовательно, единообразное априорное значение по [0, 1] имеет смысл. Выбор a = 1 и b = 1 дает нам именно это.
Затем нам нужно выбрать вероятность и предпочтительно такую, для которой бета-распределение является сопряженным априорным. Биномиальное распределение удовлетворяет этому, и оно также имеет смысл для нашего варианта использования, поскольку моделирует вероятность получения k успехов (сумма наград бандита) из N испытаний (количество раз, когда мы играли бандитом) с вероятностью успеха p ( это, которое мы пытаемся оценить).
If Prior is 𝛍 ~ Beta(𝛼, 𝛽) Likelihood is k | 𝛍 ~ Binomial(N, 𝛍) Then Posterior is 𝛍 ~ Beta(𝛼 + successes, 𝛽 + failures) Where N = successes + failures
Это простое правило обновления: если награда от бандита равна 1, мы увеличиваем его a, если он равен 0, мы увеличиваем его b.
Покажи мне код
Мы определили базовые классы, которые вы увидите здесь, в предыдущих сообщениях, но они снова включены для полноты картины.
В приведенном ниже коде определяется класс BernoulliBandit, который представляет бандитов, базовый класс Agent для представления агентов и вспомогательный класс BanditRewardsLog, который будет отслеживать вознаграждения.
Теперь осталось только создать подкласс класса Agent и реализовать выборку Томпсона.
… И готово! Теперь посмотрим, насколько он соответствует алгоритмам из предыдущих постов, а именно Эпсилон-Жадный, Оптимистические начальные значения и Верхние границы уверенности (UCB).
Эксперименты
Мы будем использовать следующий код для сравнения различных алгоритмов.
Во-первых, давайте определимся с нашими бандитами.
probs = [0.6, 0.7, 0.8, 0.9] bernoulli_bandits = [BernoulliBandit(p) for p in probs]
После этого мы можем просто запустить
compare_agents( get_agents(), bernoulli_bandits, iterations=500, show_plot=True, )
что дает нам следующее.
Хм ... не очень понятно, но похоже, что у Epsilon-Greedy и Bayesian Bandits схожие характеристики. Чтобы найти лучший, давайте повторим описанный выше эксперимент и посчитаем, сколько раз каждый алгоритм давал лучший результат.
wins = run_comparison(bernoulli_bandits)
for g, w in zip(get_agents(), wins):
print(g, w)
Мои результаты составили 397 побед для Epsilon-Greedy, 0 для UCB1, 220 для UCB1-Tuned и 383 для Thompson Sampling. Похоже, что Thompson Sampling и Epsilon-Greedy - победители для наших конкретных условий. Выход UCB1-Tuned на третье место немного удивляет, учитывая, что в предыдущих экспериментах он превосходил алгоритм Epsilon-Greedy. Это могло быть связано с тем, что Thompson Sampling крадет некоторые из своих выигрышей, но это требует дальнейшего расследования.
Заключение
В этом посте мы рассмотрели, как работает алгоритм выборки Томпсона, и реализовали его для бандитов Бернулли. Затем мы сравнили его с другими алгоритмами многоруких бандитов и увидели, что он работает примерно так же, как Epsilon-Greedy.
Станьте участником Medium и получите полный доступ ко всем историям. Ваш членский взнос напрямую поддерживает авторов, которых вы читаете.
От того же автора.
использованная литература
[1] Учебное пособие по семплированию Томпсона. (нет данных). Получено 25 сентября 2021 г. с сайта https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf.
