Возвращение многорукого бандита. Часть 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_experimentas 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

    # parametersfor mu – prior is N(0,1)

    self.m0 = 0

    self.lambda0= 1

    self.sum_x =0 # for convenience

    self.tau = 1

  def pull(self):

    returnnp.random.randn() + self.m

  def sample(self):

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

  def update(self, x):

    # assume tauis 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):

    # epsilongreedy

    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 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

  returncumulative_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):

    # optimisticinitial values

    j =np.argmax([b.sample() 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()

  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 scaleplot

  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,что приведёт к сходимости к константе.

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

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