Возвращение многорукого бандита. Часть 1

Постановка задачи и дилемма исследования и использования

Здравствуйте и вновь добро пожаловать на занятия по теме «Искусственный интеллект: обучение с подкреплением на языке Python».

В этой части курса мы пересмотрим задачу многорукого “бандита”, с которой уже сталкивались в моём первом курсе по байесовскому машинному обучению и А/В-тестированию, рассмотрим эпсилон-жадный алгоритм и сравним разные значения эпсилон. Если вы не проходили этот курс, то не слишком переживайте по этому поводу – эту задачу мы полностью охватим в курсе нынешнем.

Итак,предположим, мы пошли в казино, где оказались перед выбором, на каком из трёхигровых автоматов сыграть. Каждый из автоматов может дать вам вознаграждение –0 или 1, поэтому пока что это похоже на подбрасывание монеты. Это и называется задачеймногорукого бандита – многорукого, потому что, запуская игровой автомат, вытянете за его рычаг («руку»), а бандита – потому что эти автоматы вытягивают изнас деньги. Показатели выигрышей игровых автоматов неизвестен. К примеру, этоможет быть 0,1, 0,3 и 0,5, но мы этого не знаем, мы можем лишь вычислить их,собирая данные. Очевидно, что наша цель пребывания в казино – максимизироватьсвой выигрыш. Будь мы экстрасенсами, мы бы с помощью своих экстрасенсорныхспособностей узнали, у какого из автоматов наибольший показатель выигрышей ииграли бы только с ним, максимизируя таким образом свой выигрыш. Но посколькупоказателей этих мы не знаем, приходится их оценивать, собирая данные. Этозначит, что нужно сыграть на каждом автомате. Вот тут-то и возникает дилемма:чтобы получить точную оценку, нужно собрать много данных, но собирая многоданных, придётся потратить много времени на игры с неоптимальными бандитами.Следовательно, необходимо найти баланс между попытками максимизировать свойзаработок и попытками получить точные значения показателей выигрыша для каждогоиз бандитов, поскольку для максимизации заработка необходимо знать этуинформацию.

Втрадиционном А/В-тестировании нам необходимо заранее определить, сколько разнужно сыграть с каждым из бандитов, чтобы получить статистически значимыйрезультат. Количество необходимых игр зависит от ряда факторов, таких какразница в показателях выигрышей каждого из бандитов: чем разница больше, темменьше нужно игр, а чем разница меньше – тем больше надо сыграть. Это довольноглупо, поскольку этой-то разницы мы и не знаем, пока не начнём тестирование. Вэтом состоит один из недостатков традиционного А/В-тестирования.

Важноеправило А/В-тестирования заключается в том, что нельзя прекращать тестированиедосрочно. Так, если мы заранее решили, что необходимо сыграть с каждым избандитов 1000 раз, а после 500 игр подсчитали, что показатель выигрышей одногобандита составляет 90%, а второго 10%, то останавливаться всё равно нельзя. Ксчастью, в этом курсе нас не интересует статистическая значимость, так что унас нет необходимости следовать такого рода правилам.

Любопытно,что люди ведут себя совершенно иначе. Предположим, вы выиграли два раза из трёху одного бандита и ноль раз из трёх у другого. Тогда, по всей видимости, выбудете испытывать сильнейшее желание играть только с тем бандитом, у которогона данный момент выиграли два раза из трёх, даже несмотря на высокуювероятность того, что второй бандит может быть лучше. При этом если я вас спрошу,значит ли с точки зрения статистики, что два выигрыша из трёх и ноль выигрышейиз трёх дают точные значения, вы ответите «Нет!» Как специалист по обработкеданных вы знаете, что очень низка вероятность того, что первый бандит имеетдействительный показатель выигрышей в 67%, а второй бандит – 0% выигрышей. Выэто знаете, поскольку три – крайне малый размер выборки, и всё же, играя вигровые автоматы, всё равно чувствуете веру в то, что первый бандит лучше.

В следующих лекциях мы поговорим об алгоритмах, системно устанавливающих баланс между исследованием и использованием, что позволяет улучшить результаты по сравнению с такими несовершенными методами, как человеческие эмоции и традиционное А/В-тестирование.

Эпсилон-жадный алгоритм

Первымрешением дилеммы исследования и использования является так называемаяэпсилон-жадная стратегия. Она очень важна, поскольку мы будем ею пользоватьсяна протяжении всего курса. Она хороша и тем, что очень проста. Работает онаследующим образом.

Мыустанавливаем некоторое малое число εв качестве вероятности исследования. Обычно значение ε устанавливается равным 10% или 5%. Вот псевдокод, иллюстрирующийработу стратегии:

p = random()

if p < eps:

    сыграть сослучайным бандитом

else:

    сыграть с лучшим на данный момент бандитом

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

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

В долгосрочной перспективе эпсилон-жадный алгоритм позволяет нам исследовать каждого из бандитов бесконечное количество раз. Проблема тут, впрочем, в том, что в конечном итоге наступает момент, когда мы всё равно будем исследовать, хотя нужды в этом уже нет. Следовательно, если ε = 10%, то 10% времени будет расходоваться на неоптимальных бандитов. Тут может оказаться полезным А/В-тестирование: можно провести тестирование на протяжении заранее определённого времени, чтобы обнаружить статистическую значимость, и, обнаружив таковую, установить ε = 0, таким образом эффективно применив только «жадную» часть. Впрочем, вскоре мы познакомимся и с лучшими способами, как приспособиться к полученному знанию.

Обновление среднего значения выборки

Допустим,что наше вознаграждение – это не просто подбрасывание монеты, а потому мыдолжны сохранять не просто количество успехов и неудач. Общим методом решенияэтой задачи является использование среднего значения. Для подбрасывания монеты,впрочем, он тоже работает, поскольку если сложить все полученные нули и единицыи поделить их на N,то получим вероятность максимального правдоподобия. Как вычислить среднеезначение выборки случайной переменной? Мы знаем, что она равна общей сумме,делённой на количество примеров:

Чтоже не так с этим уравнением? Проблема в том, что необходимо хранить все N элементов,чтобы вычислить среднее значение. А есть ли способ сделать расчёты болееэффективными? Действительно, есть. Хитрость в том, что среднее значение N примеров можновычислить из среднего значения N – 1 примеров. Данное уравнение позволяет нам рассчитатьсреднее значение более эффективно с точки зрения вычислений:

Чтоже не так с этим уравнением? Проблема в том, что необходимо хранить все N элементов,чтобы вычислить среднее значение. А есть ли способ сделать расчёты болееэффективными? Действительно, есть. Хитрость в том, что среднее значение N примеров можновычислить из среднего значения N – 1 примеров. Данное уравнение позволяет нам рассчитатьсреднее значение более эффективно с точки зрения вычислений:

Запомните эту форму обновления уравнения – она будет очень важна на протяжении всего курса.

Сравнение разных значений эпсилон

А сейчас мы реализуем эпсилон-жадный алгоритм в коде и продемонстрируем эффект от различных значений ε. Если вы не хотите попробовать написать код самостоятельно, хотя я настоятельно призываю именно так и сделать, то соответствующий файл в репозитарии курса называется comparing_epsilons.py.

Начинаем мы с класса Bandit, конструктор которого в качестве аргумента принимает один параметр m – истинное среднее значение. Среднее значение переменных экземпляра mean и N устанавливаются равными нулю, причём mean – это наша оценка среднего значения бандита.

import numpy as np

import matplotlib.pyplot as plt

class Bandit:

  def __init__(self, m):

    self.m = m

    self.mean =0

    self.N = 0

Далееидёт функция pull, имитирующая дёрганье за рычаг игрового автомата.Как легко видеть, каждое вознаграждение будет иметь гауссово распределение сединичной дисперсией:

  def pull(self):

    returnnp.random.randn() + self.m

И,наконец, функция update, в качествеаргумента принимающая x – результатпоследней игры с бандитом. Обратите внимание, что среднее значение вычисляетсяпо недавно обсуждавшейся формуле.

  def update(self, x):

    self.N += 1

    self.mean =(1 – 1.0/self.N)*self.mean + 1.0/self.N*x

После этого у нас идёт функция run_experiment с тремя различными средними значениями m1, m2 и m3, поскольку мы сравниваем трёх различных бандитов, а также ε, чтобы реализовать эпсилон-жадный алгоритм, и N – количество игр. Функция возвращает массив, содержащий кумулятивное среднее значение после каждой игры, а также графики, которые мы сравним для различных значений ε. Результаты сохраняются в массиве data размерности N. Обратите внимание, что эпсилон-жадный алгоритм реализуется внутри цикла: мы генерируем случайное число p между 0 и 1; если оно меньше ε, то играем со случайным бандитом, если же больше – играем с бандитом с наибольшим текущим средним значением. После этого обновляем значения, исходя из полученной награды. Когда цикл завершается, мы вычисляем кумулятивное среднее значение, после чего выводим его на экран вместе со столбцами, указывающими среднее значение, чтобы можно было сравнить их соответствие. Делается это с логарифмическим масштабированием, чтобы можно было яснее увидеть колебания на ранних этапах. И наконец, мы выводим на экран каждое из оценочных средних значений – сугубо в целях отладки.

def run_experiment(m1,m2, m3, eps, N):

  bandits =[Bandit(m1), Bandit(m2), Bandit(m3)]

  data =np.empty(N)

  for i in xrange(N):

    # epsilongreedy

    p =np.random.random()

    if p <eps:

      j =np.random.choice(3)

    else:

      j =np.argmax([b.mean for b in bandits])

    x =bandits[j].pull()

   bandits[j].update(x)

    # for theplot

    data[i] = x

 cumulative_average = np.cumsum(data) / (np.arange(N) + 1)

  # plot movingaverage ctr

 plt.plot(cumulative_average)

 plt.plot(np.ones(N)*m1)

 plt.plot(np.ones(N)*m2)

 plt.plot(np.ones(N)*m3)

 plt.xscale(‘log’)

  plt.show()

  for b inbandits:

    print b.mean

  return cumulative_average

В разделе main мы проводим этот эксперимент три раза, каждый с разным значением ε: 10%, 5% и 1%. Далее мы выводим на экран все кумулятивные средние значения, как с логарифмическим масштабированием, так и в линейном виде, поскольку в логарифмическом графике все более поздние данные сжимаются вправо, так что возникает ощущение, что мы тратим больше времени на неоптимальные решения, чем это происходит на самом деле.

if __name__ == ‘__main__’:

  c_1 =run_experiment(1.0, 2.0, 3.0, 0.1, 100000)

  c_05 =run_experiment(1.0, 2.0, 3.0, 0.05, 100000)

  c_01 =run_experiment(1.0, 2.0, 3.0, 0.01, 100000)

  # log scaleplot

  plt.plot(c_1, label=’eps = 0.1′)

  plt.plot(c_05,label=’eps = 0.05′)

  plt.plot(c_01,label=’eps = 0.01′)

  plt.legend()

 plt.xscale(‘log’)

  plt.show()

  # linear plot

  plt.plot(c_1, label=’eps = 0.1′)

  plt.plot(c_05,label=’eps = 0.05′)

  plt.plot(c_01,label=’eps = 0.01′)

  plt.legend()

  plt.show()

Итак,запустим программу и посмотрим, что получится.

Итак, сначала график с ε = 0,1, затем график с ε = 0,05, а затем – график с ε = 0,01.

Продолжение темы смотрите в следующей статье!

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: