Интуиция, Байес и пример
Представьте, что перед вами стоит ряд игровых автоматов. Вы не знаете, какая машина даст вам больше шансов на победу. Как найти лучший игровой автомат для игры? Что делать, чтобы увеличить шансы на победу? В более распространенном сценарии, представляя, что у вас есть различные версии объявлений или макетов веб-сайтов, которые вы хотели бы протестировать, какова наилучшая стратегия? Эта статья познакомит вас с алгоритмом выборки Томпсона для решения этих проблем.
Ранее я сделал два видео об интуиции двух очень простых алгоритмов: ETC (исследуй-затем-фиксируй) и эпсилон-жадный. Оба этих алгоритма занимают много времени, чтобы найти лучший игровой автомат, и иногда они не могут найти лучшее решение. Лучшим алгоритмом многорукого бандита для рассмотрения является выборка Томпсона. Выборка Томпсона также называется апостериорной выборкой. Это рандомизированный байесовский алгоритм, который легко понять и реализовать, и он намного быстрее с логарифмическим сожалением.
Thompson Sampling также широко используется в промышленности для различных вариантов использования. Например,
- Doordash использует выборку Томпсона, чтобы динамически определять, какие Dashers более реагируют на сообщения, а затем оптимизировать решения о том, кому отправлять сообщения в течение заданного времени.
- Amazon использует выборку Томпсона для выбора оптимального макета сайта и повышения конверсии на 21% за неделю.
- Facebook использует модифицированный алгоритм сэмплирования Томпсона под названием Constrained Thompson Sampling для оптимизации качества видео в процессе загрузки видео.
- Netflix использует выборку Томпсона наряду с другими бандитскими фреймворками в своих рекомендательных системах.
- Stitch Fix добавила Thompson Sampling к своей экспериментальной платформе.
Байесовская статистика
Давайте сначала начнем с некоторой базовой байесовской статистики. Предположим, что рука может только дать нам награду или не дать нам награду. Вознаграждение руки (X) следует распределению Бернулли: X ~ Бернулли (θ), что означает, что эта рука преуспеет с вознаграждением с вероятностью θ и потерпит неудачу без вознаграждения с вероятностью 1-θ.
Если мы сыграем эту руку n раз, общая награда/количество успехов (Y) подчиняется биномиальному распределению: Y ~ биномиальное (n, θ).
Предположим, что априорное распределение θ равно Beta(α, β): θ ~ Beta(α, β)
Опять же, θ — это вероятность выигрыша для каждого игрового автомата/руки. Наша цель состоит в том, чтобы найти, что это θ при данных данных, т. е. p(θ|y).
На основе правила Байеса мы можем вычислить апостериорное распределение θ, которое пропорционально вероятности и априорному, а затем мы запишем уравнения для биномиального распределения и бета-распределения, которое затем пропорционально θ в степени y+α+1 и (1-θ) в степени n-y+β-1, которая пропорциональна бета(y+α, n-y+β).
Интересно отметить, что бета-распределение сопряжено с биномиальным семейством, а это означает, что если мы начнем с априорной бета-версии, мы получим апостериорную бета-распределение.
Здесь в уравнении у — количество успехов, а n-y — количество проигрышей. Это означает, что для каждой руки на каждом временном шаге, если мы получаем вознаграждение, мы добавляем 1 к первому параметру, а если нам не удается получить вознаграждение, мы добавляем 1 ко второму параметру. В конце концов, первым параметром должно быть количество успехов плюс альфа, а вторым параметром должно быть количество неудач плюс бета. Далее я покажу вам конкретный пример.
Пример выборки Бернулли-Томпсона
Давайте начнем, например, с двух игровых автоматов (две руки). Обратите внимание, что мы не знаем реальную вероятность выигрыша для двух рук, но допустим, что они равны 0,6 и 0,2.
На временном шаге 1:
Предположим, что у нас нет априорной информации о вероятностях выигрыша каждой руки, и поэтому воспользуемся бета-версией (1,1), т. е. равномерным распределением, для обеих рук.
Затем давайте случайным образом возьмем выборку из каждого распределения, например, мы возьмем 0,8 для руки 1 и 0,4 для руки 2. Поскольку 0,8 > 0,4, мы играем руку 1. С неизвестной истинной вероятностью 0,6 рука 1 даст нам вознаграждение. . Предположим, что рука 1 действительно дает нам вознаграждение. Затем апостериорное распределение для плеча 1 обновляется до бета (2,1):
На временном шаге 2:
Снова давайте случайным образом возьмем выборку из каждого распределения. Как видно из новых распределений, у руки 1 больше шансов вытянуть более высокие числа, у руки 2 равные шансы вытянуть любые числа. Хотя по сравнению с рукой 2 у руки 1 больше шансов получить большее число. Поскольку мы выбираем числа случайным образом, у руки 2 все еще есть шанс получить большее число. Например, мы вытягиваем 0,7 для руки 1 и 0,9 для руки 2. Поскольку 0,7 ‹ 0,9, мы играем руку 2. С вероятностью 0,2 рука 2 даст нам вознаграждение, давайте предположим, что рука 2 не дала нам вознаграждение. Затем апостериорное распределение для плеча 2 обновляется до Beta(1,2):
На временном шаге 3:
Снова давайте случайным образом возьмем выборку из каждого распределения. Предположим, мы рисуем 0,8 для руки 1 и 0,3 для руки 2. Мы играем руку 1. С вероятностью 0,6 рука 1 даст нам вознаграждение. Допустим, в этот раз рука 1 не дала нам вознаграждение. Затем апостериорное распределение для плеча 1 обновляется до бета (2,2):
И мы продолжаем весь этот процесс снова и снова. По мере увеличения количества временных шагов апостериорное распределение должно становиться все ближе и ближе к реальному значению. Например, на временном шаге 100 мы могли бы получить бета (40, 30) для руки 1 и бета (8, 26) для руки 2. Обратите внимание, что эти четыре числа должны в сумме давать 104, так как мы начинаем с Бета (1,1) для обеих рук.
А затем на временном шаге 1000 мы могли бы получить бета-версию (432, 290) для ветви 1 и бета-версию (56, 226) для ветви 2, при этом средние значения распределений почти точно соответствуют фактической вероятности выигрыша. Стандартное отклонение должно становиться все меньше и меньше с течением времени. И стандартное отклонение для выигрышной руки должно быть меньше, чем для другой руки, потому что в целом у нас должен быть более высокий шанс получить большее значение от выигрышной руки, и, таким образом, мы играем с этой рукой чаще. Но все равно у нас будет очень маленькая ненулевая вероятность разыграть руку 2, а это означает, что на этом этапе мы будем в основном заниматься эксплуатацией, а не разведкой. Для выборки Томпсона нет конечного предела, когда мы исследуем, а когда эксплуатируем, как вы, возможно, видели в других алгоритмах.
Таким образом, выборка Томпсона делает следующее:
- На каждом временном шаге мы вычисляем апостериорное распределение θ для каждого плеча.
- Мы берем выборку из каждого из апостериорных распределений и проигрываем руку с наибольшим значением.
В нашем примере мы предположили, что каждое плечо на каждом временном шаге следует распределению Бернулли, а априорное распределение вероятности выигрыша соответствует бета-априорному. Также часто используются другие распределения, например, можно использовать распределение Гаусса с априорным значением Гаусса или другие распределения в общих экспоненциальных семействах.
Надеюсь, что эта статья поможет вам лучше понять алгоритм выборки Томпсона. Подробный анализ сожалений можно найти в этой книге. Спасибо!
Использованная литература:
https://multithreaded.stitchfix.com/blog/2020/08/05/бандиты/
https://dl.acm.org/doi/pdf/10.1145/3097983.3098184
