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