Реализация алгоритма верхней доверительной границы
В этой статье мы покажем, как работает алгоритм UCB для задачи о многоруком бандите.
Алгоритм UCB в двух словах
В алгоритме UCB мы начинаем исследовать все машины на начальном этапе, а позже, когда мы находим машину с наивысшей долей вероятности, мы начинаем использовать ее, чтобы получить максимальное вознаграждение.
Если вы хотите лучше понять это, вы можете увидеть Верхнюю границу достоверности для проблемы многоруких бандитов. Здесь мы сосредоточимся на алгоритмической части и визуализируем ее с помощью кодирования.
Давайте посмотрим, каковы шаги алгоритма UCB.
Шаги алгоритма UCB
- В каждом раунде n мы рассматриваем два числа для машины m.
-›Nₘ(n) = количество раз, когда машина m выбиралась до раунда n. .
-> Rₘ(n) = количество наград автомата m до раунда n. - На основании этих двух чисел мы должны вычислить,
а. Среднее вознаграждение машины m до раунда n: rₘ(n) = Rₘ(n) / Nₘ(n).
b. Доверительный интервал [rₘ(n) — Δₘ(n), rₘ(n)+Δₘ(n)] в раунде n с Δₘ(n)= sqrt( 1,5 * log(n) / Nₘ(n )) - Мы выбираем машину m с максимальной UCB,(rₘ(n)+Δₘ(n))
Я знаю, что это может показаться вам запутанным, но давайте сделаем это проще!
В эти выходные мне было очень скучно и я пошел к своему другу (Нилешу) домой. После небольшой болтовни мы решили вместе посмотреть фильм. Но проблема заключалась в том, какой фильм смотреть. Я предложил несколько научно-фантастических фильмов, с которыми он не согласился, а он предложил несколько боевиков, с которыми я не согласился. Потом предложил доработать хотя бы 5 фильмов, а потом уже решать, какой смотреть. Я также согласился, поскольку мы предложили много фильмов.
Итак, мы составили список из 5 фильмов:
1. Железный человек
2. Падение ангела
3. Хоббс и Шоу
4. 6 Underground
5. Начало
Теперь мы снова начали спорить, кого смотреть, потому что у всех хорошие рейтинги на IMDB. Потом пришла его мама и спросила, почему мы ссоримся. Мы рассказали ей о нашей проблеме. Она задумалась на секунду и сказала, почему бы тебе не спросить своих друзей, какой фильм посмотреть. Мы подумали, что это хорошая идея. Но звонить всем было не очень хорошей идеей, так как это отнимало бы очень много времени. Мы создали форму Google и отправили ее всем нашим друзьям для заполнения. Это заняло почти 15 минут, и мы получили почти 100 отзывов. Теперь у нас были данные о 100 разных друзьях фильма, которые они предпочли бы посмотреть. Данные содержат двоичные значения, которые предполагают, что при 0 они не предпочитают этот фильм, а при 1 предпочитают.
Нилеш: Отлично, братан! Подсчитаем сумму для каждого фильма и выберем максимальный.
Я: Мы можем это сделать, но есть проблема.
Нилеш: Что, братан?
Я: Братан, наши друзья высказали свое мнение о том, какой фильм они предпочтут из 5, а не на основании рейтинга, который мне больше всего нравится "Железный человек". Я думаю, что мы приняли неправильный отзыв.
Нилеш: Ты сошел с ума? Вы говорите, что мы получили неправильный набор данных. Если вы снова попросите заполнить их всех, на этот раз они, вероятно, проигнорируют нас.
Я: Я не говорю, что нам понадобится еще один набор данных. Я думаю, нам нужно по-другому визуализировать эти данные.
Нилеш: Как?
Я: Нам нужно беспристрастное решение, так как почти в каждом обзоре есть оба фильма, которые мы выбрали, и которые понравились нашим друзьям.
Нилеш: Да, но как мы это сделаем? Мы не можем просто попросить маму выбрать любой фильм из 100 отзывов и посмотреть, понравился он нашим друзьям или нет. Затем посчитайте для каждого фильма в итоге, если он выбран мамой и понравился нашему другу. Чувак, было бы лучше, если бы мы отказались от нашего плана посмотреть фильм и занялись бы чем-нибудь другим.
Я: Я знаю, братан, но почему ты хочешь, чтобы это сделала мама? Мы можем легко решить эту проблему, используя метод верхней доверительной границы, о котором я читал.
Нилеш: Чем эта задача похожа на вашу задачу о многоруких бандитах?
Я: Смотрите, у нас есть 5 фильмов и 100 обзоров фильмов на эти 5 фильмов. Мы хотим, чтобы машина просматривала каждый обзор и случайным образом выбирала один фильм и проверяла, нравится ли он нашему другу или нет. Но в то же время мы не хотим, чтобы машина была предвзятой по отношению к одному фильму, и чтобы она давала шанс и другим. Наконец, мы хотим, чтобы он нашел тот фильм, который выбрало максимальное количество наших друзей, используя верхнюю границу уверенности. Мы также получим хорошую визуализацию и по ней будем смотреть фильм.
Нилеш: Да, вы поняли. Посмотрим, куда это нас приведет.
Я: Да, братан.
Мы запустили следующий код на нашем наборе данных.
Наконец-то мы получили такую визуализацию,
Нилеш: Вау, братан! Я также думал посмотреть «Начало» на случай, если оно не сработает, но модель также предложила сам фильм «Начало».
Я: Верно, братан! Это потрясающе. Давайте посмотримНачало.
Как это произошло на самом деле?
Разбираемся шаг за шагом. Перед этим я хочу, чтобы вы открыли шаги алгоритма в другой вкладке.
- Метод __init__:
В этом методе мы выполнили шаг 1 алгоритма и определили определенные атрибуты.
self.__N → общее количество отзывов
self.__m → общее количество фильмов
self.__movie_selected → список из 100 фильмов, выбранных в каждом раунде
self.__number_of_selection→ сколько раз фильм m был выбран до раунда N.
self.__sum_of_movie_rank →сумма рангов фильма m до раунда N. - Метод реализации_ucb:
В этом методе мы объединили шаги 2 и 3.
В условии If мы проверяем, выбран ли фильм хотя бы один раз или нет. Потому что, если он не будет выбран хотя бы один раз, то по формуле шага 2(а) алгоритма мы получим бесконечность, так как знаменатель станет равным 0. Если фильм не будет выбран хотя бы один раз, то он установит свою верхнюю границу в бесконечность. (здесь обозначено высоким значением 1e500).
В противном случае рассчитайте средний рейтинг фильма по формуле на шаге 2 (а) и вычислите верхнюю достоверность по формуле на шаге 2 (б).
Теперь мы выполнили шаг 2, давайте перейдем к шагу 3.
На шаге 3 мы сравним вычисленную верхнюю границу с максимальной верхней границей, если она больше, чем max_upper_bound, затем сделаем верхнюю границу максимальной верхней границей, а выбранный фильм — текущим фильмом.
Так реализован UCB. Может быть несколько способов реализации. Не стесняйтесь поделиться, если вы решите другим способом.
Ссылки:
