Выборка Томпсона - Thompson sampling - Wikipedia

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

Описание

Рассмотрим набор контекстов , набор действий и награды в . В каждом раунде игрок получает контекст , играет действие и получает награду следование распределению, которое зависит от контекста и выданного действия. Цель игрока состоит в том, чтобы выполнять действия, направленные на максимальное увеличение совокупных наград.

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

  1. функция правдоподобия ;
  2. множество параметров распределения ;
  3. предварительное распространение по этим параметрам;
  4. тройняшки прошлых наблюдений ;
  5. апостериорное распределение , куда - функция правдоподобия.

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

куда это индикаторная функция.

На практике правило реализуется путем выборки в каждом раунде параметров от заднего , и выбирая действие что максимизирует , т.е. ожидаемое вознаграждение с учетом выбранных параметров, действия и текущего контекста. Концептуально это означает, что игрок случайным образом реализует свои убеждения в каждом раунде в соответствии с апостериорным распределением, а затем действует оптимально в соответствии с ними. В большинстве практических приложений поддержание и выборка из апостериорного распределения по моделям обременительны с вычислительной точки зрения. Таким образом, отбор проб Томпсона часто используется вместе с методами приблизительного отбора проб.[2]

История

Отбор проб Томпсона был первоначально описан Томпсоном в 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] Предложен алгоритм дуэли бандитов, вариант традиционного МАБ, где обратная связь поступает в формате попарного сравнения.

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

Соответствие вероятности

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

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

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

Настройка выглядит следующим образом. Позволять быть действиями, выданными агентом в срок , и разреши быть наблюдениями, собранными агентом до времени . Затем агент выдает действие с вероятностью:[4]

где "шляпа" - обозначение обозначает тот факт, что является причинным вмешательством (см. Причинно-следственная связь ), а не обычное наблюдение. Если агент придерживается убеждений над его поведением, то правило байесовского контроля становится

,

куда - апостериорное распределение по параметру данные действия и наблюдения .

На практике байесовский контроль представляет собой выборку на каждом временном шаге параметра из апостериорного распределения , где апостериорное распределение вычисляется с использованием правила Байеса только с учетом (причинной) вероятности наблюдений и игнорирование (причинной) вероятности действий , а затем путем выборки действия из раздачи действий .

Алгоритмы верхней доверительной границы (UCB)

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

Рекомендации

  1. ^ а б Томпсон, Уильям Р. «О вероятности того, что одна неизвестная вероятность превышает другую с учетом свидетельств двух образцов». Биометрика, 25(3–4):285–294, 1933.
  2. ^ а б Дэниел Дж. Руссо, Бенджамин Ван Рой, Аббас Казеруни, Ян Осбанд и Чжэн Вен (2018), «Учебник по выборке Томпсона», Основы и тенденции в машинном обучении: Vol. 11: No. 1, стр. 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
  3. ^ а б Дж. Вятт. Исследование и вывод при обучении на основе подкрепления. Кандидат наук. защитил диссертацию на кафедре искусственного интеллекта Эдинбургского университета. Март 1997 г.
  4. ^ а б c d Ортега П.А. и Браун Д.А. «Принцип минимальной относительной энтропии для обучения и действий», Журнал исследований искусственного интеллекта, 38, страницы 475–511, 2010.
  5. ^ а б M. J. A. Strens. "Байесовская система обучения с подкреплением", Материалы семнадцатой международной конференции по машинному обучению, Стэнфордский университет, Калифорния, 29 июня - 2 июля 2000 г. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
  6. ^ а б Б. С. Мэй, Б. С., Н. Корда, А. Ли и Д. С. Лесли. «Оптимистическая байесовская выборка в контекстно-бандитских проблемах». Технический отчет, Статистическая группа, Департамент математики, Бристольский университет, 2011 г.
  7. ^ Шапель, Оливье и Лихонг Ли. «Эмпирическая оценка выборки Томпсона». Достижения в области нейронных систем обработки информации. 2011 г.http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
  8. ^ а б О.-К. Гранмо. "Решение задач двурукого бандита Бернулли с помощью байесовского обучающего автомата", Международный журнал интеллектуальных вычислений и кибернетики, 3 (2), 2010, 207-234.
  9. ^ Ян Кларк. «Пропорциональное A / B-тестирование», 22 сентября 2011 г., http://blog.locut.us/2011/09/22/proportionate-ab-testing/
  10. ^ Granmo, O.C .; Глимсдал, С. (2012). «Ускоренное байесовское обучение для децентрализованного принятия решений на основе двурукого бандита с приложениями к игре Goore Game». Прикладной интеллект. 38 (4): 479–488. Дои:10.1007 / s10489-012-0346-z. HDL:11250/137969.
  11. ^ Ву, Хуасень; Лю, Синь; Срикант, Р (2016), Двойная выборка Томпсона для дуэлянтных бандитов, arXiv:1604.07101, Bibcode:2016arXiv160407101W
  12. ^ Дэниел Дж. Руссо и Бенджамин Ван Рой (2014), «Обучение оптимизации с помощью апостериорной выборки», «Математика исследования операций», Vol. 39, No. 4, pp. 1221-1243, 2014. https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650
  13. ^ Дэниел Дж. Руссо и Бенджамин Ван Рой (2013), «Измерение ускользания и примерная сложность оптимистического исследования», «Достижения в системах обработки нейронной информации» 26, стр. 2256-2264. http://papers.nips.cc/paper/4909-eluder-dimension-and-the-sample-complexity-of-optimistic-exploration.pdf