🔍 Поиск готовых работ

🔍 Поиск работ

Одна модификация задачи о многоруком бандите

Работа №131332

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы70
Год сдачи2017
Стоимость4910 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
39
Не подходит работа?

Узнай цену на написание


1 Введение 4
1.1 Обзор литературы 7
2 Глава 1. Тестирование интернет-страниц на основе задачи о многоруком бандите 10
2.1 Постановка задачи 10
2.2 Задача о многоруком бандите 10
2.3 Обзор алгоритмов 12
2.4 Тестирование интернет-страниц 19
2.5 Численный эксперимент 20
2.6 Выводы 27
3 Глава 2. Тестирование интернет-страниц на основе задачи о контекстном бандите 29
3.1 Постановка задачи 29
3.2 Задача о контекстном бандите 30
3.3 Алгоритм LinUCB 31
3.4 Численный эксперимент 33
3.5 Выводы 39
4 Глава 3. Задача о многоруком бандите с экспертами 40
4.1 Постановка задачи 40
4.2 Задача о многоруком бандите при наличии эксперта 40
4.3 Модификация алгоритма UCB1 41
4.4 Численный эксперимент (один эксперт) 42
4.5 Задача о многоруком бандите с m экспертами 45
4.6 Численный эксперимент (mэкспертов) 47
4.7 Выводы 50
5 Заключение 51
Литература 52
6 Приложения 56
6.1 Приложение 1. Программный код (глава 1) 56
6.2 Приложение 2. Программный код (глава 2) 60
6.3 Приложение 3. Программный код (глава 3) 65
6.4 Приложение 4. Программный код (глава 3) 69


Машинное обучение (Machine Learning) — чрезвычайно широкая и активно развивающаяся область искусственного интеллекта, которая находится на стыке математической статистики, методов оптимизации и фундаментальных математических дисциплин. Методы машинного обучения все глубже проникают в самые разные области человеческой деятельности.
Одним из разделов машинного обучения является «обучение с подкреплением» [29](reinforcement learning), в котором ключевой задачей выступает так называемая дилемма «исследования-использования». Задача исследования- использования заключается в поиске компромисса между обучением и применением ранее полученных знаний с целью максимизации выигрыша. Такие задачи часто возникают в реальных ситуациях, например, в клинических исследованиях, динамической (адаптивной) маршрутизации, в финансах и интернет-маркетинге.
Одним из способов формализации дилеммы исследования-использования является стохастическая задача о многоруком бандите(multi-armed bandit problem), так же известная как задача оптимального управления в случайной среде [2]. Формальное определение задачи мы дадим ниже, а здесь ограничимся лишь её словесным описанием. Представим ситуацию, в которой игрок многократно выбирает одну из nальтернатив (действий), каждый раз получая за это некоторую награду, величина которой зависит от неизвестного вероятностного распределения выбранной альтернативы. С этого момента каждый такой выбор будем называть игрой. Задача игрока состоит в том, чтобы максимизировать суммарный выигрыш за конечное число последовательных игр. Заметим, что в качестве игрока, как правило, выступает некоторая автоматизированная система. Каждую альтернативу можно интерпретировать как рычаг игрового автомата, называемого «одноруким бандитом». Тогда задача представляется в виде игрового автомата с несколькими рычагами, который по аналогии можно назвать «многоруким бандитом».
Как было отмечено, задача о многоруком бандите находит свое применение в различных сферах человеческой деятельности [6, 13, 16, 17, 27]. Отдельно стоит отметить её многочисленные приложения в интернет-маркетинге [5,21,23,25].
Одной из ключевых задач интернет-маркетинга является увеличение конверсии сайта. Тестирование интернет-страниц — один из способов решения данной задачи. Под конверсией сайта понимается отношение количества посетителей сайта, выполнивших необходимое действие (покупка товара, заказ обратного звонка, подписка на рассылку и т. д.), к общему числу посетителей. Тестирование интернет-страниц, как будет показано ниже, может быть сведено к задаче о многоруком бандите. Такой подход в сравнении с классическим позволяет увеличить конверсию за время тестирования.
На практике в условиях задачи о многоруком бандите кроме значений полученных выигрышей от выбора альтернатив часто доступна некоторая дополнительная информация, которую можно использовать для улучшения выбора. В интернет-маркетинге это может быть индивидуальная информация о посетителе веб-ресурса, например, источник перехода, предполагаемый пол, возраст и т. д. Модификация задачи о многоруком бандите, которая учитывает дополнительную информацию, называется задачей о контекстном бандите. В данной работе будет показано, как, используя дополнительную информацию об источнике перехода, увеличить конверсию за время тестирования.
В работе также выделяется особый тип дополнительной информации, содержащий прямые рекомендации по выбору альтернатив. Такого рода ин-формация формализуется в виде экспертных подсказок. Для учета подсказок эксперта модифицирован алгоритм, решающий задачу о многоруком бандите.
Актуальность исследования данной темы обусловлена возрастающей значимостью интернет-маркетинга для бизнеса и экономики в совокупности с бурным ростом числа приложении методов машинного обучения в данной сфере.
Новизна работы состоит, во-первых, в предложенном подходе к тестированию интернет-страниц на основе задачи о контекстном бандите, во-вторых, в модификации алгоритма UCB1 для решения задачи о многоруком бандите с экспертами.
Основные результаты выпускной квалификационной работы опубликованы в работах [6, 5] и докладывались на двух конференциях: XLVII и XLVIII международной конференции «Процессы управления и устойчивость» Control Processes and Stability (CPS).
Работа состоит из введения, трех глав и заключения.
В главе 1 дается классическая формулировка стохастической задачи о многоруком бандите. Приводится обзор алгоритмов, используемых для решения данной задачи. Тестирование интернет-страниц с целью увеличения конверсии сводится к задаче о многоруком бандите. Демонстрируются результаты численного эксперимента на основе программной реализации симуляции тестирования.
В главе 2 продолжается тема тестирования интернет-страниц. Здесь предложен новый подход к тестированию, основанный на задаче о контекстном бандите. Дается подробное описание алгоритма LinUCB. Разработана программная реализация симуляции тестирования. Приведены результаты численных экспериментов
В главе 3 формулируется задача о многоруком бандите с экспертами. Предложена модификация алгоритма UCB1. Продемонстрированы результаты
численных экспериментов.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В заключении сформулируем основные результаты.
Проведен обзор алгоритмов для решения стохастической задачи о многоруком бандите. Тестирование интернет-страниц свелось к задаче о многоруком бандите. Разработана программная реализация симуляции тестирования. Приведены результаты тестирования страниц с помощью 8-ми алгоритмов. На основании результатов можно утверждать, что использование алгоритмов для решения задачи о многоруком бандите в тестировании страниц увеличивает конверсию за время тестирования.
Предложен новый подход к тестированию интернет-страниц, основанный на задаче о контекстном бандите. Данный способ тестирования позволяет учитывать источник перехода пользователя. А именно в настоящей работе рассматриваются переходы с рекламных объявлений. С учетом нового подхода разработана программная реализация симуляции тестирования, в основе которой лежит алгоритм LinUCB. Конверсия, получаемая в результате применения данного подхода, превосходит результат тестирования на основе задачи о многоруком бандите.
Предложена модификация задачи о многоруком бандите, которая заключается в добавлении экспертных подсказок. Сначала формулируется задача о многоруком бандите с одним экспертом. Для её решения произведена модификация алгоритма UCB1. Затем задача обобщается на случай mэкспертов. Предложены три метода формирования единой экспертной подсказки. Разработана программа, с помощью которой произведен численный эксперимент. На конкретных входных данных показано влияние экспертных подсказок на значение выигрыша.



[1] Буре В. М., Парилина Е. М. Теория вероятностей и математическая статистика. М.: Лань, 2013. 416 c.
[2] Лазутченко А. Н. О робастном управлении в случайной среде, характеризуемой нормальным распределением доходов с различными дисперсиями // Труды Карельского научного центра Российской академии наук. 2015. №. 10.
[3] Программный код для ВКР. URL:https://github.com/
patrickjsmirnov/vkr_master (дата обращения: 21.04.2017).
[4] Смирнов Д. С. Статистический анализ эффективности контекстной рекламы // Процессы управления и устойчивость. 2015. T. 2. № 1. С. 714-719.
[5] Смирнов Д. С. Тестирование интернет-страниц как решение задачи о многоруком бандите // Молодой ученый. 2015. № 19. С. 78-86.
[6] Смирнов Д. С. Использование задачи о многоруком бандите в тестировании веб-страниц // Процессы управления и устойчивость. 2016. Т. 3. № 1. С. 705-710.
[7] Abe N., Biermann A. W., Long P. M. Reinforcement learning with immediate rewards and linear hypotheses // Algorithmica. 2003. Т. 37. №. 4. С. 263-293.
[8] Agrawal S., Goyal N. Analysis of thompson sampling for the multi¬armed bandit problem // Journal of Machine Learning Research: Workshop and Conference Proceedings. 2012. Vol. 23, № 39. P. 1-26.
[9] Agrawal S., Goyal N. Thompson Sampling for Contextual Bandits with Linear Payoffs // ICML (3). 2013. С. 127-135.
[10] Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed Bandit Problem // Machine Learning. 2002. Vol. 47, No 2-3. P. 235-256.
[11] Auer P. et al. The nonstochastic multiarmed bandit problem // SIAM journal on computing. 2002. Т. 32. №. 1. С. 48-77.
[12] Auer P. Using confidence bounds for exploitation-exploration trade-offs // Journal of Machine Learning Research. 2002. Т. 3. №. Nov. С. 397-422.
[13] Awerbuch B., Kleinberg R. Online linear optimization and adaptive routing // Journal of Computer and System Sciences. 2008. Т. 74. № 1. С. 97-114.
[14] Cesa-Bianchi N., Fischer P. Finite-time regret bounds for the multiarmed bandit problem // ICML. 1998. С. 100-108.
[15] Chu W. et al. Contextual Bandits with Linear Payoff Functions // AISTATS. 2011. Т. 15. С. 208-214.
[16] Hardwick J. et al. Bandit strategies for ethical sequential allocation // Computing Science and Statistics. 1991. Т. 23. № 6.1. С. 421-424.
[17] Kuleshov V., Precup D. Algorithms for the multi-armed bandit problem // Journal of Machine Learning Research. 2000. P. 1-48.
[18] Lage R. et al. Choosing which message to publish on social networks: A contextual bandit approach // Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on. IEEE, 2013. С. 620-627.
[19] Lai T. L., Robbins H. Asymptotically efficient adaptive allocation rules // Advances in applied mathematics. 1985. № 6. P. 4-22.
[20] Langford J., Zhang T. The epoch-greedy algorithm for multi-armed bandits with side information // Advances in neural information processing systems. 2008. С. 817-824.
[21] Li L. et al. A contextual-bandit approach to personalized news article recommendation // Proceedings of the 19th international conference on World wide web. ACM, 2010. С. 661-670.
[22] Lu T., Pal D., Pal M. Contextual Multi-Armed Bandits // AISTATS. 2010. С. 485-492.
[23] Pandey S., Olston C. Handling advertisements of unknown quality in search advertising //NIPS. 2006. Т. 20. С. 1065-1072.
[24] Robbins H. Some aspects of the sequential design of experiments // Herbert Robbins Selected Papers. Springer New York, 1985. С. 169-177.
[25] Schwartz E. M., Misra K., Abernethy J. Dynamic Online Pricing with Incomplete Information Using Multi-Armed Bandit Experiments. 2016.
[26] Scott S. L. A modern Bayesian look at the multi-armed bandit // Applied Stochastic Models in Business and Industry. 2010. Vol. 26, № 6. P. 639-658.
[27] Shen W. et al. Portfolio Choices with Orthogonal Bandit Learning // IJCAI. 2015. С. 974-980.
[28] Strehl A. L. et al. Experience-efficient learning in associative bandit problems // Proceedings of the 23rd international conference on Machine learning. ACM, 2006. С. 889-896.
[29] Sutton R. S., Barto A. G. Reinforcement learning: An introduction. Cambridge : MIT press, 1998. Т. 1. №. 1.
[30] Thompson W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples // Biometrika. 1933. Т. 25. №. 3/4. С. 285-294.
[31] Walsh T. J. et al. Exploring compact reinforcement-learning representations with linear regression // Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2009. С. 591-598.
[32] Woodroofe M. A one-armed bandit problem with a concomitant variable // Journal of the American Statistical Association. 1979. Т. 74. №. 368. С. 799¬806.


Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ
.