Принцип работы Thompson Sampling: просто о сложном

Thompson Sampling — один из самых популярных и понятных алгоритмов для многоруких бандитов. Он прост в реализации и очень эффективен, особенно когда данных мало.

Интуиция Thompson Sampling

Представьте, что вы в казино. Перед вами несколько игровых автоматов — «рук». Вы не знаете, какой из них самый щедрый. Thompson Sampling предлагает такой подход:

Вместо того чтобы просто считать средний выигрыш, алгоритм предполагает, какова истинная вероятность выигрыша для каждой руки. Это предположение выражается в виде распределения вероятностей.

Каждый раз, когда вы выбираете руку, Thompson Sampling делает следующее:

1. «Рисует» (семплирует) значение из распределения вероятностей для каждой руки. Это как бросить кубик для каждой руки, чтобы узнать её потенциальную прибыльность.
2. Выбирает руку, которая показала наибольшее «нарисованное» значение.
3. Обновляет распределение для выбранной руки на основе результата (выигрыш или проигрыш). Если рука оказалась успешной, её распределение смещается к более высоким вероятностям. Если нет — к более низким.

Важно: Чем больше данных мы собираем по руке, тем уже становится её распределение. Это значит, мы точнее знаем её истинную прибыльность. Так алгоритм балансирует между исследованием (изучением новых рук) и эксплуатацией (использованием лучших рук).

Как это работает на практике?

Для бинарных исходов (например, клик/не клик, покупка/не покупка) Thompson Sampling часто использует бета-распределение. Оно отлично подходит для моделирования вероятностей успеха.

• Параметры бета-распределения: У бета-распределения два параметра: alpha (количество успехов + 1) и beta (количество неудач + 1).
• Инициализация: Для каждой руки начинаем с alpha = 1 и beta = 1. Это означает, что изначально мы считаем все руки одинаково хорошими (равномерное распределение).
• Обновление:
  • Если рука выбрана и дала успех, увеличиваем её alpha на 1.
  • Если рука выбрана и дала неудачу, увеличиваем её beta на 1.

Пример: Выбор заголовка для рекламного объявления

Представьте, что у вас три варианта заголовка для рекламы: A, B, C. Цель — максимизировать кликабельность (CTR).

1. Инициализация:

   • Заголовок A: alpha = 1, beta = 1
   • Заголовок B: alpha = 1, beta = 1
   • Заголовок C: alpha = 1, beta = 1

2. Первый раунд:

   • Thompson Sampling «рисует» случайное значение из бета-распределения для каждого заголовка.
   • Допустим, A = 0.6, B = 0.4, C = 0.7.
   • Выбираем заголовок C (он показал наибольшее значение).
   • Пользователь видит заголовок C и кликает (успех).
   • Обновляем заголовок C: alpha = 2, beta = 1.

3. Второй раунд:

   • Thompson Sampling снова «рисует» значения. Теперь распределение для C уже немного смещено в сторону успеха.
   • Допустим, A = 0.5, B = 0.6, C = 0.8.
   • Выбираем заголовок C.
   • Пользователь видит заголовок C и не кликает (неудача).
   • Обновляем заголовок C: alpha = 2, beta = 2.

И так далее. Со временем распределения для более эффективных заголовков будут смещаться вправо (к 1), а для менее эффективных — влево (к 0). Thompson Sampling будет всё чаще выбирать те заголовки, которые, по его текущим данным, имеют наибольшую вероятность успеха.

Преимущества Thompson Sampling

• Понятный: Легко разобраться, как он работает, даже без глубокой математики.
• Эффективный: Отлично балансирует между исследованием и эксплуатацией, быстро находя лучшие варианты.
• Простой в реализации: Для базовых задач можно написать за несколько строк кода.
• Адаптивный: Автоматически учитывает неопределенность. Если данных по руке мало, её распределение широкое, и есть шанс, что она будет выбрана для исследования. Если данных много, распределение узкое, и выбор более предсказуем.

Thompson Sampling — мощный инструмент, который помогает не только найти лучший вариант, но и минимизировать потери в процессе поиска. Но когда именно стоит его выбирать? И есть ли у него альтернативы? Об этом мы поговорим далее.