Выборка Томпсона

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Выборка Томпсона»  -  новости  · газеты  · книги  · ученый  · JSTOR ( май 2012 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Томпсон выборки , ^{[1] [2]} назван в честь Уильяма Р. Томпсон, эвристика для выбора действия, адреса разведка-добыча дилеммой в нескольких вооруженных бандита проблемы. Он состоит в выборе действия, которое максимизирует ожидаемую награду по отношению к случайно выбранному убеждению.

Описание [ править ]

Этот раздел включает в себя список ссылок , связанных материалов или внешних ссылок , но его источники остаются неясными, поскольку в нем отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить этот раздел, добавив более точные цитаты. ( Май 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Рассмотрим набор контекстов , набор действий и награды . В каждом раунде игрок получает контекст , разыгрывает действие и получает награду в соответствии с распределением, которое зависит от контекста и выполненного действия. Цель игрока состоит в том, чтобы выполнять такие действия, чтобы максимизировать совокупные награды.${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle {\ mathcal {A}}}$${\ Displaystyle \ mathbb {R}}$${\ displaystyle x \ in {\ mathcal {X}}}$${\ displaystyle a \ in {\ mathcal {A}}}$${\ Displaystyle г \ в \ mathbb {R}}$

Элементы выборки Томпсона следующие:

1. функция правдоподобия ;${\ Displaystyle Р (г | \ тета, а, х)}$
2. набор параметров распределения ;${\ displaystyle \ Theta}$${\ displaystyle \ theta}$${\displaystyle r}$
3. предварительное распределение по этим параметрам;${\displaystyle P(\theta )}$
4. тройки прошлых наблюдений ;${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$
5. апостериорное распределение , где - функция правдоподобия.${\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}$${\displaystyle P({\mathcal {D}}|\theta )}$

Выборка Томпсона заключается в воспроизведении действия в соответствии с вероятностью того, что оно максимизирует ожидаемое вознаграждение, т. Е. Действие выбирается с вероятностью.${\displaystyle a^{\ast }\in {\mathcal {A}}}$${\displaystyle a^{\ast }}$

${\displaystyle \int \mathbb {I} \left[\mathbb {E} (r|a^{\ast },x,\theta )=\max _{a'}\mathbb {E} (r|a',x,\theta )\right]P(\theta |{\mathcal {D}})d\theta ,}$

где - индикаторная функция .${\displaystyle \mathbb {I} }$

На практике правило реализуется путем выборки в каждом раунде параметров из апостериорных значений и выбора действия, которое максимизирует , т. Е. Ожидаемого вознаграждения с учетом выбранных параметров, действия и текущего контекста. Концептуально это означает, что игрок случайным образом формирует свои убеждения в каждом раунде в соответствии с апостериорным распределением, а затем действует оптимально в соответствии с ними. В большинстве практических приложений поддерживать и делать выборку из апостериорного распределения по моделям обременительно с вычислительной точки зрения. Таким образом, отбор проб Томпсона часто используется в сочетании с приблизительными методами отбора проб. ^[2]${\displaystyle \theta ^{\ast }}$${\displaystyle P(\theta |{\mathcal {D}})}$${\displaystyle a^{\ast }}$${\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}$

История [ править ]

Отбор проб Томпсона был первоначально описан Томпсоном в 1933 году. ^[1] Впоследствии он был повторно открыт много раз независимо в контексте проблем многоруких бандитов. ^{[3] [4] [5] [6] [7] [8]} Первое доказательство сходимости для случая бандитов было показано в 1997 году. ^[3] Первое приложение к марковским процессам принятия решений было в 2000 году. ^[5] Соответствующий подход (см. Правило байесовского контроля ) был опубликован в 2010 году. ^[4] В 2010 году также было показано, что выборка Томпсона мгновенно самокорректируется . ^[8]Результаты асимптотической конвергенции для контекстных бандитов были опубликованы в 2011 году. ^[6] В настоящее время выборка Томпсона широко используется для решения многих задач онлайн-обучения: выборка Томпсона также применяется к A / B-тестированию в дизайне веб-сайтов и онлайн-рекламе; ^[9] Выборка Томпсона сформировала основу для ускоренного обучения децентрализованному принятию решений; ^[10] алгоритм двойной выборки Томпсона (D-TS) ^[11] был предложен для дуэли бандитов, вариант традиционного MAB, где обратная связь поступает в формате попарного сравнения.

Отношение к другим подходам [ править ]

Вероятность совпадения [ править ]

Сопоставление вероятностей - это стратегия принятия решений, в которой прогнозы членства в классе пропорциональны базовым ставкам класса. Таким образом, если в обучающем наборе положительные примеры наблюдаются в 60% случаев, а отрицательные примеры наблюдаются в 40% случаев, наблюдатель, использующий стратегию сопоставления вероятностей, предсказывает (для немаркированных примеров) метку класса «положительный». в 60% случаев и метка класса «негативный» в 40% случаев.

Правило байесовского контроля [ править ]

Было показано, что обобщение выборки Томпсона на произвольные динамические среды и причинные структуры, известное как правило байесовского управления , является оптимальным решением проблемы адаптивного кодирования с действиями и наблюдениями. ^[4] В этой формулировке агент концептуализируется как смесь набора поведений. По мере того, как агент взаимодействует со своей средой, он изучает причинные свойства и принимает поведение, которое минимизирует относительную энтропию к поведению с наилучшим предсказанием поведения окружающей среды. Если это поведение было выбрано в соответствии с принципом максимальной ожидаемой полезности, то асимптотическое поведение правила байесовского управления соответствует асимптотическому поведению совершенно рационального агента.

Настройка выглядит следующим образом. Пусть будут действия, произведенные агентом до момента времени , и пусть будут наблюдения, собранные агентом к моменту времени . Затем агент с вероятностью выдает действие : ^[4]${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$${\displaystyle T}$${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$${\displaystyle T}$${\displaystyle a_{T+1}}$

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}$

где "шляпа" обозначает факт, который является причинным вмешательством (см. Причинность ), а не обычным наблюдением. Если агент верит в свое поведение, то правило байесовского контроля становится${\displaystyle {\hat {a}}_{t}}$${\displaystyle a_{t}}$${\displaystyle \theta \in \Theta }$

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T})=\int _{\Theta }P(a_{T+1}|\theta ,{\hat {a}}_{1:T},o_{1:T})P(\theta |{\hat {a}}_{1:T},o_{1:T})\,d\theta }$,

где - апостериорное распределение по параметру с учетом действий и наблюдений .${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$${\displaystyle \theta }$${\displaystyle a_{1:T}}$${\displaystyle o_{1:T}}$

На практике байесовский контроль представляет собой выборку на каждом временном шаге параметра из апостериорного распределения , где апостериорное распределение вычисляется с использованием правила Байеса только с учетом (причинной) вероятности наблюдений и игнорирования (причинной) вероятности. действий , а затем путем выборки действия из распределения действий .${\displaystyle \theta ^{\ast }}$${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$${\displaystyle a_{T+1}^{\ast }}$${\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}$

Алгоритмы верхнего уровня достоверности (UCB) [ править ]

Алгоритмы выборки Томпсона и верхней доверительной границы имеют общее фундаментальное свойство, лежащее в основе многих их теоретических гарантий. Грубо говоря, оба алгоритма распределяют исследовательские усилия на действия, которые могут быть оптимальными и в этом смысле «оптимистичными». Используя это свойство, можно преобразовать границы сожаления, установленные для алгоритмов UCB, в байесовские границы сожаления для выборки Томпсона ^[12] или объединить анализ сожалений для обоих этих алгоритмов и многих классов проблем. ^[13]

Ссылки [ править ]