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

Оптимистические начальные значения

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

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

Вновь-таки, всё очень просто. Предположим, мы знаем, что истинное среднее значение бандитов намного меньше 10. Суть в том, чтобы выбрать верхнюю границу для нашей начальной оценки среднего значения бандита, а затем на основании этого сделать обновление. Отсюда и «оптимистичность» в названии – ведь начальная величина среднего значения выборки «слишком хороша, чтобы быть правдой». А поскольку она слишком хороша, чтобы быть правдой, то единственное, что может произойти, – это её снижение.

Итак, если среднее значение равно 1, то по мере сбора всё большего количества значений среднее выборки будет стремиться к 1. Действительно, в конечном итоге все средние значения перейдут к своим истинным значениям, после чего мы перейдём к использованию. Но легко показать, что это помогает и исследованию: если бандит не исследован, то его среднее значение выборки будет очень высоким, как и устанавливалось изначально. На самом деле оно будет выше, чем что-либо другое, а это значит, что мы будем вынуждены исследовать его. Таким образом, всё, что нужно сделать в главном цикле, – это реализовать «жадную» стратегию, но с использованием этих оптимистических средних значений.

Для этого в коде для эпсилон-жадного алгоритма достаточно сделать два простых изменения: во-первых, мы устанавливаем начальное значение среднего значения равным 10, а во-вторых, убираем часть с эпсилоном, оставляя только «жадную», что очень просто. Код при этом сравнивает эпсилон-жадную стратегию при ε = 10% со стратегией оптимистических начальных значений. Если вы не хотите писать код сами, хотя я настоятельно рекомендую сделать именно это, соответствующий файл называется optimistic_initial_value.py.

Запустим его и посмотрим, что получится.

Итак, вначале график для эпсилон-жадного алгоритма, а потом – для оптимистических начальных значений. Судя по всему, оптимистические начальные значения выглядят куда лучше, нежели эпсилон-жадный алгоритм. В последнем случае мы всегда заканчиваем неоптимальным поведением в долгосрочной перспективе, а в случае оптимистической стратегии мы вплотную подходим к отметке 3.

UCB1

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

Основная идея UCB1 – доверительные границы. Интуитивно понятно, что если мы соберём 10 примеров и возьмём их среднее значение, то оно будет не столь точным, как если бы мы собрали 1000 примеров и нашли их среднее значение. Если мы графически изобразим доверительные границы каждого из этих средних значений, то граница вокруг среднего значения 10 примеров будет гораздо шире, а граница вокруг среднего значения 1000 примеров – гораздо уже. В статистике существует понятие так называемой границы Чернова-Хоффдинга, причём утверждается, что наша доверительная граница изменяется по экспоненте по мере изменения собранных примеров:

Выглядит эта граница сложной, но становится куда понятнее, если изучить её внимательно. Он утверждает, что вероятность того, что модуль разницы между средним значением выборки и истинным средним значением больше или равно ε, меньше, чем удвоенная экспоненциальная функция в степени -2ε2N, где N – количество собранных примеров, а ε – просто произвольное малое число.

Подробности выходят за рамки этого курса, но алгоритм так же прост, как и уже рассмотренные. Суть в том, что мы берём верхнюю доверительную границу, равную обычному среднему значению выборки плюс квадратный корень из удвоенного натурального логарифма N, делённого на Nj, что эквивалентно выбору ε, равному квадратному корню и всему, что под ним:

Выглядит эта граница сложной, но становится куда понятнее, если изучить её внимательно. Он утверждает, что вероятность того, что модуль разницы между средним значением выборки и истинным средним значением больше или равно ε, меньше, чем удвоенная экспоненциальная функция в степени -2ε2N, где N – количество собранных примеров, а ε – просто произвольное малое число.

Подробности выходят за рамки этого курса, но алгоритм так же прост, как и уже рассмотренные. Суть в том, что мы берём верхнюю доверительную границу, равную обычному среднему значению выборки плюс квадратный корень из удвоенного натурального логарифма N, делённого на Nj, что эквивалентно выбору ε, равному квадратному корню и всему, что под ним:

Теперь поговорим о том, что обозначают все эти символы.  – это просто обычное среднее значение j-го бандита, собственно N – количество игр, сыгранных со всеми бандитами, а Nj – количество игр, сыгранных с j-м бандитом.

Как же использовать эту формулу? Идея похожа на метод оптимистических начальных значений. Мы используем только «жадную» стратегию, но «жадную» относительно не просто среднего значения выборки, а верхней доверительной границы среднего значения выборки. Возникает вопрос: как это работает? Дело в том, что доверительная граница является соотношением двух величин – N, то есть общего количества сыгранных игр, и Nj, то есть количества игр, сыгранных с j-м бандитом. Следовательно, если мы сыграли множество игр с другими бандитами, но Nj мало, то данное соотношение будет большим, что поднимет верхнюю доверительную границу и, свою очередь, будет вынуждать нас сыграть с этим бандитом. В то же время если Nj велико, то рассматриваемое соотношение будет малым, что снизит верхнюю доверительную границу. Ключевым в этом соотношении является то, что верхняя часть растёт пропорционально логарифму от N, а это значит, что в конечном итоге она будет возрастать медленнее, чем Nj. Это приводит к тому, что по мере того, как мы будем всё больше и больше играть со всеми бандитами, их верхние доверительные границы будут снижаться, а мы придём к использованию только средних значений выборок. Это допустимо, поскольку к этому времени мы соберём много данных. Таким образом, и в данном случае всё сводится к чисто «жадной» стратегии, основанной только на средних значениях выборок.

Чтобы лучше понять, как это всё работает, рассмотрим псевдокод:

for n=1..N:

    j = argmax[j’] { bandit[j’].mean + sqrt(2*ln(n) / n_j’) }

    сыграть с бандитом j

    обновить бандита j

По сути, он так же прост, как и метод оптимистических начальных значений. Мы просто помещаем формулу в функцию argmax, которая теперь и является верхней доверительной границей. Обратите внимание, что тут есть небольшая проблема: формула работать не будет, если Nj = 0. Чтобы справиться с ней, достаточно просто добавить некоторое малое число к знаменателю.

Если вы не хотите писать код самостоятельно, то соответствующий файл в репозитарии называется ucb1.py. А сейчас посмотрим на результат.

Итак, вначале видим работу эпсилон-жадного алгоритма, а затем – работу UCB1. Как видим, в конце концов UCB1 превосходит эпсилон-жадный алгоритм.

Байесовское сэмплирование по Томпсону

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

Чтобы объяснить идею, лежащую в основе байесовского метода, мы вновь рассмотрим доверительные интервалы, или границы. Интуитивно мы понимаем, что среднее значение выборки, вычисленное по 10 примерам, не такое точное, как среднее значение, вычисленное по 1000 примерам. Воспользовавшись центральной предельной теоремой, мы можем утверждать, что доверительный интервал приблизительно имеет гауссово распределение с истинным средним значением, равным ожидаемому значению случайной переменной, и дисперсией, равной исходной дисперсии, делённой на N:

Причина, по которой  имеет распределение, заключается в том, что по сути это сумма случайных переменных, а, как вы знаете, функция случайных переменных также является случайной переменной.

Байесовская парадигма развивает эту идею ещё дальше. Вместо того, чтобы быть фиксированной величиной, μ также становится случайной величиной. Основная идея байесовской парадигмы состоит в том, что данные считаются фиксированными, а параметры – случайными. В байесовской парадигме параметры имеют распределения, а мы хотим узнать эти распределения параметров с учётом имеющихся данных. В этом скрыт большой смысл: имеет смысл полагать, что, имея некоторые данные, мы способны найти распределение, основанное на этих данных, более точно, чем если бы данных не было. Это называется апостериорным распределением p(θ|X).

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

Причина, по которой  имеет распределение, заключается в том, что по сути это сумма случайных переменных, а, как вы знаете, функция случайных переменных также является случайной переменной.

Байесовская парадигма развивает эту идею ещё дальше. Вместо того, чтобы быть фиксированной величиной, μ также становится случайной величиной. Основная идея байесовской парадигмы состоит в том, что данные считаются фиксированными, а параметры – случайными. В байесовской парадигме параметры имеют распределения, а мы хотим узнать эти распределения параметров с учётом имеющихся данных. В этом скрыт большой смысл: имеет смысл полагать, что, имея некоторые данные, мы способны найти распределение, основанное на этих данных, более точно, чем если бы данных не было. Это называется апостериорным распределением p(θ|X).

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

С этой формулой есть ряд трудностей. Одна из них состоит в том, что она очень общая – в том смысле, что дифференциальное уравнение очень общее. Интеграл в знаменателе не всегда поддаётся решению, и приходится прибегать к математическим приёмам, чтобы заставить его «работать», что не всегда получается. К счастью, если специальный набор пар распределений, у которых апостериорная вероятность имеет то же распределение, что и априорная. Это и называется сопряжённым априорным распределением, или просто априорным сопряжением.

Рассмотрим небольшой пример того, как метод априорных сопряжений можно использовать для вычисления показателей кликабельности. Мы знаем, что показатели кликабельности схожи с подбрасыванием монеты, а потому имеют распределение Бернулли. Посмотрев в Википедии, какого сопряжённое априорное распределение для распределения Бернулли, мы выясним, что это бета-распределение. Оно всегда находится между 0 и 1, что логично, и имеет два параметра a и b. Зная это, мы можем определиться с порядком вычисления апостериорной вероятности. Так, правдоподобие можно записать в виде произведения, поскольку каждое подбрасывание монеты является независимым:

Априорная же вероятность является функцией распределения вероятностей бета, которую можно просто переписать из Википедии или учебника по статистике:

Чтобы найти апостериорную вероятность, нам необходимо объединить правдоподобие и априорную вероятность и решить уравнение относительно апостериорной вероятности:

Чтобы найти апостериорную вероятность, нам необходимо объединить правдоподобие и априорную вероятность и решить уравнение относительно апостериорной вероятности:

При этом бета-функцию можно вынести за пределы пропорции, поскольку она включается в константу нормализации. Ключевым тут является понимание того, что апостериорная вероятность также имеет форму бета-распределения:

Вследствие этого мы можем вывести новые параметры бета-распределения. Так, новым a будет старое a плюс количество раз, когда x = 1, а новым b – старое b плюс количество раз, когда x = 0:

В моём курсе по А/В-тестированию есть скрипт, который можно запустить и посмотреть, как обновляется апостериорная вероятность по мере сбора всё большего количества примеров. Файл называется demo.py и находится в папке ab_testing. Мы начинаем со значений a0 = 1, b0 = 1, что эквивалентно равномерному распределению. Такая априорная вероятность вполне уместна, поскольку мы вначале ничего не знаем об истинном значении априорной вероятности показателя кликабельности. После одной попытки у нас одно успешное её завершение, и плотность распределения вероятностей выглядит так (см. слайд). После 6 попыток – так, после 11 – так. Прокрутим остальные промежуточные результаты, и после 1500 попыток в конце концов истинное среднее значение оказывается равным оценочному.

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

В моём первом курсе по байесовскому машинному обучению вы узнали, что правдоподобие с гауссовым распределением сопряжено с априорной вероятностью, также имеющей гауссово распределение по среднему значению. Если мы поместим в априорную вероятность только среднее значение μ, считая, что дисперсия фиксирована, то можем начать со следующими формами правдоподобия и априорной вероятности:

В моём курсе по А/В-тестированию есть скрипт, который можно запустить и посмотреть, как обновляется апостериорная вероятность по мере сбора всё большего количества примеров. Файл называется demo.py и находится в папке ab_testing. Мы начинаем со значений a0 = 1, b0 = 1, что эквивалентно равномерному распределению. Такая априорная вероятность вполне уместна, поскольку мы вначале ничего не знаем об истинном значении априорной вероятности показателя кликабельности. После одной попытки у нас одно успешное её завершение, и плотность распределения вероятностей выглядит так (см. слайд). После 6 попыток – так, после 11 – так. Прокрутим остальные промежуточные результаты, и после 1500 попыток в конце концов истинное среднее значение оказывается равным оценочному.

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

В моём первом курсе по байесовскому машинному обучению вы узнали, что правдоподобие с гауссовым распределением сопряжено с априорной вероятностью, также имеющей гауссово распределение по среднему значению. Если мы поместим в априорную вероятность только среднее значение μ, считая, что дисперсия фиксирована, то можем начать со следующими формами правдоподобия и априорной вероятности:

Как можно видеть, тут мы используем параметр точности, являющийся величиной, обратной дисперсии, поскольку это облегчает математические выкладки. Параметрами для распределения μ являются m и λ, и для них же нам нужны обновлённые уравнения.

Первый этап – умножить правдоподобие и априорную вероятность, чтобы получить пропорцию для вероятности апостериорной:

На следующем этапе мы опускаем некоторые константы и оставляем лишь то, что находится под знаком экспоненты, поскольку сейчас нас не интересует константа нормализации:

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

Следующий этап – приведение всех подобных членов с μ. Не забывайте, что нас не интересует всё, что не связано с μ, поскольку эти члены остаются в константе нормализации:

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

Следующий этап – понять, какую форму уравнения мы ищем. Для апостериорной вероятности нужно, чтобы была левая часть – то, что входит в экспоненту гауссового распределения:

Но ведь это именно то, что мы нашли! Следовательно, следующим этапом будет приравнять и решить уравнение

Обратите внимание, что член с точностью проще решить, но после него нужно решить член с m, поскольку он зависит от λ.

Итак, теперь у нас есть решение для нового m и новой λ, основанное на параметрах априорной вероятности и собранных данных. Уделите минутку, чтобы понять, как мы пришли к такому ответу или поставьте видео на паузу и проделайте выкладки на бумаге.

Последний этап – обсудить, как всё это можно применить к задаче многорукого бандита. Ответ в сэмплировании. Ключевой тут является строка кода, в которой мы выбираем бандита. Вместо того, чтобы использовать функцию argmax для верхней доверительной границы, как это было в UCB1, мы используем argmax для образцов средних значений каждого из бандитов. Не забывайте, что средние значения теперь являются распределениями вероятностей, а потому из них можно извлекать образцы.

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

Сэмплирование по Томпсону, эпсилон-жадный алгоритм, оптимистические начальные значения и UCB1

В этой лекции мы напишем большой скрипт для сравнения всех решений дилеммы исследования и использования. У нас их четыре: эпсилон-жадный алгоритм, метод оптимистических начальных значений, UCB1 и байесовское сэмплирование. Поскольку мы уже знакомы с действием эпсилон-жадного алгоритма, мы его несколько модифицируем, использовав затухающее значение ε, а точнее, установим ε = 1/t, где t – номер итерации. Как мы убедимся в конце, все они работают примерно одинаково, что оправдывает использование эпсилон-жадного алгоритма на протяжении всего курса. Если вы не хотите писать код для всего этого самостоятельно, хотя я настоятельно рекомендую сделать именно так, то соответствующий файл в репозитории называется comparing_explore_exploit_methods.py.

Вначале мы кое-что импортируем из уже написанных трёх файлов. Из скрипта с эпсилон-жадным алгоритмом нам понадобится только класс Bandit, который нам понадобится, чтобы переписать алгоритм для случая с затухающим ε:

import numpy as np

import matplotlib.pyplot as plt

from comparing_epsilons import Bandit

from optimistic_initial_values import run_experiment as run_experiment_oiv

from ucb1 import run_experiment as run_experiment_ucb

Далее мы определяем класс BayesianBandit. Не забывайте, что мы больше не пытаемся найти фиксированную оценку μ – теперь это случайная переменная, чьё распределение имеет фиксированные параметры. Поскольку апостериорная вероятность зависит от суммы по x, мы для удобства сохраняем её в качестве переменной экземпляра. Кроме того, мы знаем, что τ = 1.

Новым здесь является метод sample, который генерирует пример из гауссового распределения со средним значением m0 и точностью lambda0. Метод update просто реализует уравнение обновления, показанное в предыдущей лекции.

class BayesianBandit:

  def __init__(self, m):

    self.m = m

    # parameters for mu – prior is N(0,1)

    self.m0 = 0

    self.lambda0 = 1

    self.sum_x = 0 # for convenience

    self.tau = 1

  def pull(self):

    return np.random.randn() + self.m

  def sample(self):

    return np.random.randn() / np.sqrt(self.lambda0) + self.m0

  def update(self, x):

    # assume tau is 1

    self.lambda0 += 1

    self.sum_x += x

    self.m0 = self.tau*self.sum_x / self.lambda0

Следующей у нас идёт функция для запуска опыта с эпсилон-жадным алгоритмом, но ε у нас теперь равно 1/(i+1):

def run_experiment_decaying_epsilon(m1, m2, m3, N):

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

  data = np.empty(N)

  for i in xrange(N):

    # epsilon greedy

    p = np.random.random()

    if p < 1.0/(i+1):

      j = np.random.choice(3)

    else:

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

    x = bandits[j].pull()

    bandits[j].update(x)

    # for the plot

    data[i] = x

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

  # plot moving average 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 in bandits:

    print b.mean

  return cumulative_average

Далее идёт функция run_experiment для байесовского сэмплирования. Единственное существенное изменение здесь, как обычно, – в части, связанной с функцией argmax, когда мы вызываем прежнюю функцию sample.

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

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

  data = np.empty(N)

  for i in xrange(N):

    # optimistic initial values

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

    x = bandits[j].pull()

    bandits[j].update(x)

    # for the plot

    data[i] = x

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

  # plot moving average 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()

  return cumulative_average

И в конце, внизу, мы просто запускаем наши четыре опыта и выводим четыре графика.

if __name__ == ‘__main__’:

  eps = run_experiment_decaying_epsilon(1.0, 2.0, 3.0, 100000)

  oiv = run_experiment_oiv(1.0, 2.0, 3.0, 100000)

  ucb = run_experiment_ucb(1.0, 2.0, 3.0, 100000)

  bayes = run_experiment(1.0, 2.0, 3.0, 100000)

  # log scale plot

  plt.plot(eps, label=’decaying-epsilon-greedy’)

  plt.plot(oiv, label=’optimistic’)

  plt.plot(ucb, label=’ucb1′)

  plt.plot(bayes, label=’bayesian’)

  plt.legend()

  plt.xscale(‘log’)

  plt.show()

  # linear plot

  plt.plot(eps, label=’decaying-epsilon-greedy’)

  plt.plot(oiv, label=’optimistic’)

  plt.plot(ucb, label=’ucb1′)

  plt.plot(bayes, label=’bayesian’)

  plt.legend()

  plt.show()

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

Вначале видим затухающий эпсилон-жадный алгоритм. Далее идёт метод оптимистических начальных значений, потом UCB1, и наконец сэмплирование по Томпсону.

Далее график всех четырёх методов. Байесовский метод не совсем последователен вначале, но все они работают примерно одинаково. Увеличим последнюю часть. Как видим, они очень и очень близки между собой и даже пересекаются. Кроме того, можно обнаружить, что вроде как лучший метод обычно изменяет своё поведение при каждом запуске скрипта, поэтому обоснованно заявлять, что все они примерно одинаковы.

И последним идёт линейный график. Как видим, сходятся они куда быстрее, чем это кажется на логарифмическом графике.

Нестационарные бандиты

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

Итак, что же понимается под нестационарностью? Стационарный процесс – это процесс, чьи статистические показатели не изменяются со временем. Нас интересует среднее значение, но, строго говоря, существуют разные типы стационарности. Стационарность в слабом понимании – это когда среднее значение и автоковариация не изменяются со временем (автоковариация – это статистический показатель второго порядка). Есть и стационарность в сильном понимании, когда вся плотность распределения вероятностей должна оставаться неизменной с течением времени. У нас именно этот вид стационарности, поскольку каждый из бандитов имеет одно и то же распределение при каждой игре. Обратите внимание, что стационарный процесс в сильном понимании также является стационарным и в слабом понимании, однако обратное неверно. Возникает вопрос: а что, если бандиты нестационарны? Имеет ли смысл вычислять их средние значения, как раньше?

Напомню наше уравнение обновления среднего значения из более раннего:

Обозначим для удобства  через Q. Мы можем переставить члены так, чтобы 1/t было отдельно:

Обозначим для удобства  через Q. Мы можем переставить члены так, чтобы 1/t было отдельно:

Мы можем обобщить его даже больше, обозначив 1/t через коэффициент обучения α, так что всё это становится похожим на нечто вроде градиентного спуска:

Ключевым в этом уравнении является то, что не обязательно использовать значение α = 1/t в качестве коэффициента обучения. Если вы помните курс по глубокому обучению, часть 2, 1/t – всего лишь один из изученных нами способов представления адаптивного коэффициента обучения. Но он может быть каким угодно, в том числе и константой.

Следующее уравнение тоже кажется похожим:

Ключевым в этом уравнении является то, что не обязательно использовать значение α = 1/t в качестве коэффициента обучения. Если вы помните курс по глубокому обучению, часть 2, 1/t – всего лишь один из изученных нами способов представления адаптивного коэффициента обучения. Но он может быть каким угодно, в том числе и константой.

Следующее уравнение тоже кажется похожим:

Действительно, это нечто подобное тому, что нам встретилось при рассмотрении функции scan библиотеки Theano. Напомню, что это уравнение описывает простой фильтр низких частот. Если мы избавимся от рекурсии, то можем найти Q  через все прошлые значения X:

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

Если вы хотите запустить такой фильтр из руководства по функции scan библиотеки Theano, то соответствующая папка называется hmm_class, а соответствующий файл – scan3.py. Как можно видеть, мы начинаем с очень зашумленной синусоидальной волны, но после того, как пропускаем её через фильтр низких частот, большая часть высокочастотного шума исчезает.

В литературе по обучению с подкреплением часто встречается вывод о сходимости Q. Он гласит, что Q сходится, если сумма всех α равно бесконечности, а сумма квадратов всех α является константой:

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

Если вы хотите запустить такой фильтр из руководства по функции scan библиотеки Theano, то соответствующая папка называется hmm_class, а соответствующий файл – scan3.py. Как можно видеть, мы начинаем с очень зашумленной синусоидальной волны, но после того, как пропускаем её через фильтр низких частот, большая часть высокочастотного шума исчезает.

В литературе по обучению с подкреплением часто встречается вывод о сходимости Q. Он гласит, что Q сходится, если сумма всех α равно бесконечности, а сумма квадратов всех α является константой:

Отсюда становится ясно, что α в виде константы не удовлетворяет этим двум условиям, а α = 1/t – удовлетворяет. Причина, по которой часто встречается α в виде константы, заключатся в том, что задачи обучения с подкреплением часто являются нестационарными, а следовательно, вообще не имеет смысла пытаться вычислить среднее значение выборки после каждого нового примера.

Теперь решим несколько простых задач, чтобы закрепить это понятие. Мы уже знаем, что при α = 1/t сходится, но как насчёт α = 1/t2? Если вы хотите поставить видео на паузу и подумать над этим – пожалуйста, так и сделайте.

Итак, ответ: нет, не сходится, поскольку сумма по всем α не равна бесконечности.

А что, если α = 1/t2/3? Если вы хотите поставить видео на паузу и подумать над этим – пожалуйста, так и сделайте.

В этом случае сходимость есть, поскольку сумма по всем α равна бесконечности, а если мы возведём α в квадрат, то показатель степени в знаменателе станет больше 1, что приведёт к сходимости к константе.