Методы приближений

Введение в метод приближений

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

В этой последней части курса мы изучим методы приближений. Мы рассмотрим линейные модели обучения с подкреплением, признаки, предсказание методом Монте-Карло с приближением и напишем код.

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

Напомнюранние курсы по глубокому обучению, где нейронные сети выступают в ролиуниверсальных «приблизителей» функций. Это значит, что при правильнойархитектуре нейронные сети могут приближённо смоделировать любую функцию слюбой степенью точности. На практике они работают не идеально, но всё же оченьхорошо. С математической точки зрения мы вначале извлекаем признаки; тогда изсостояния sмы можем извлечь признак x:

Нашацель – найти такую функцию, принимающую в качестве аргументов вектор признаков x и наборпараметров θ, которая даёт верноеприближённое представление функции ценности V(s):

Нашацель – найти такую функцию, принимающую в качестве аргументов вектор признаков x и наборпараметров θ, которая даёт верноеприближённое представление функции ценности V(s):

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

Планэтой части курса следующий. Вначале мы используем методы приближений кпредсказанию методом Монте-Карло, что значит, что мы будем оценивать функциюценности с заданной фиксированной стратегией. Однако вместо представленияфункции ценности в виде словаря с индексированием по состояниям мы используемлинейное приближение функции. Напомню, что метод Монте-Карло требует, чтобы мысыграли весь эпизод и вычислили отдачи до выполнения каких-либо обновлений.Поэтому следующим будет использование методов приближений к предсказанию пометоду TD0. Не забывайте, что TD0сочетает аспекты как выборок методом Монте-Карло, так и метода бутстреппинга издинамического программирования. После решения проблемы предсказания мы перейдёмк проблеме управления и используем для её решения SARSA,но, разумеется, заменив Q на линейное приближение функции.

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

Линейные модели обучения с подкреплением

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

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

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

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

Имеябазовую функцию ошибок, подставим вместо V её определение, то есть ожидаемое значение отдачи:

Имеябазовую функцию ошибок, подставим вместо V её определение, то есть ожидаемое значение отдачи:

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

Напомню,что именно этот подход мы использовали при изучении метода Монте-Карло.

Наэто можно взглянуть и по-другому, считая, что мы принимаем каждую парусостояние-действие в качестве учебного примера. В этом случае мы пытаемсяминимизировать квадрат разницы между одновременно всеми G и . Это выглядит куда более привычно, как врегрессии, когда вычисляется сумма квадратов разниц между y и ŷ:

Напомню,что именно этот подход мы использовали при изучении метода Монте-Карло.

Наэто можно взглянуть и по-другому, считая, что мы принимаем каждую парусостояние-действие в качестве учебного примера. В этом случае мы пытаемсяминимизировать квадрат разницы между одновременно всеми G и . Это выглядит куда более привычно, как врегрессии, когда вычисляется сумма квадратов разниц между y и ŷ:

Преимуществомтакого представления функции ошибок является то, что оно позволяет нам выполнитьстохастический градиентный спуск. Если помните, это когда мы небольшими шагамидвижемся в направлении градиента относительно ошибки одного примера за раз. Этоидеально подходит для нас, поскольку на каждой итерации игры рассматриваетсятолько одна пара состояние-отдача.

Каквы, должно быть, помните, ŷхарактеризуется параметром θ. Другимисловами, мы пытаемся найти такое θ,при котором давало бы лучшее приближение. Чтобы этогодобиться, выполняется градиентный спуск относительно θ и минимизируется ошибка, выведенная ранее:

где αвновь-таки представляет коэффициент обучения.

Можнопойти дальше и заменить ошибку на виденный ранее квадрат разницы:

где αвновь-таки представляет коэффициент обучения.

Можнопойти дальше и заменить ошибку на виденный ранее квадрат разницы:

Незабывайте, что это стохастический градиентный спуск, поэтому рассматриваетсялишь один пример Gза раз. Напомню также, что в этом курсе мы рассматриваем лишь линейные модели,поэтому Vпредставляет собой скалярное произведение вектора признаков x и θ. Другими словами, производная V относительно θ равна x:

Самоеинтересное начинается, когда мы возвращаемся к методу Монте-Карло или, другимисловами, когда мы не параметризуем V, а наоборот, хотим найти сам параметр , причём для всех состояний s. Если  само является параметром, то мы получаемследующее уравнение:

Однако, если помните, это в точности то же самое уравнение, которое у нас было раньше для обновления среднего значения. Следовательно, производимые нами ранее действия для нахождения V на самом деле были ничем иным, как примером градиентного спуска.

Признаки

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

Состоянияможно рассматривать как категориальные переменные. Например, в мире-решёткепозицию (0, 0) можно рассматривать как категорию 1, позицию (0, 1) – каккатегорию 2 и так далее. Как вы знаете, категории переводятся в векторыпризнаков с помощью прямого кодирования (one-hot encoding).Обсудим, что будет, если мы так закодируем каждое состояние. У нас s состояний, поэтомуразмерность x,которую мы обозначим через D, равна мощности s:

D = |S|.

Следовательно,у нас есть один длинный вектор признаков x размерности s, и для каждого из состояний мы присваиваем одному из значений x единицу:

Проблематут в том, что это не позволяет нам сжимать количество места, необходимого дляхранения функции ценности, хотя это первоочередная наша задача. Напомню, чтоесли сохранять Vв виде словаря, то оно будет иметь S ключей и S значений, поэтому применение прямого кодированияникак не улучшает ситуацию. На самом деле это эквивалентно тому, что делалосьранее, поскольку в этом случае каждое θбудет представлять ценность для соответствующего состояния.

Однаков применении прямого кодирования для преобразования признаков имеется иположительный аспект. Предположим, наш алгоритм не работает –  плохо представляет истинное V. Одной из причин этогоможет быть то, что плохими являются наши признаки. Код может быть безупречным ине содержать ни единой ошибки, но из-за плохих признаков не получается достичьхороших результатов. В этом случае можно изменить наше преобразование признаковс применением прямого кодирования, когда можно предсказывать каждое V(s) по отдельности. Еслитак и сделать и код будет работать, значит, проблема в признаках.

Ноесли прямое кодирование – это плохо, то что тогда хорошо? В случае мира-решёткипредставим, что каждая позиция (i, j) на самом делепредставляет позицию в двухмерном пространстве. Тогда она скорее походит надействительное число, а не на категорию, так что мы можем представить вектор x просто как само (i, j), отмасштабировав еготак, чтобы среднее значение было равно 0, а дисперсия была равна 1. Такойвектор признаков можно просто считать необработанными данными, без какого-либоконструирования данных:

Проблематут в том, что это не позволяет нам сжимать количество места, необходимого дляхранения функции ценности, хотя это первоочередная наша задача. Напомню, чтоесли сохранять Vв виде словаря, то оно будет иметь S ключей и S значений, поэтому применение прямого кодированияникак не улучшает ситуацию. На самом деле это эквивалентно тому, что делалосьранее, поскольку в этом случае каждое θбудет представлять ценность для соответствующего состояния.

Однаков применении прямого кодирования для преобразования признаков имеется иположительный аспект. Предположим, наш алгоритм не работает –  плохо представляет истинное V. Одной из причин этогоможет быть то, что плохими являются наши признаки. Код может быть безупречным ине содержать ни единой ошибки, но из-за плохих признаков не получается достичьхороших результатов. В этом случае можно изменить наше преобразование признаковс применением прямого кодирования, когда можно предсказывать каждое V(s) по отдельности. Еслитак и сделать и код будет работать, значит, проблема в признаках.

Ноесли прямое кодирование – это плохо, то что тогда хорошо? В случае мира-решёткипредставим, что каждая позиция (i, j) на самом делепредставляет позицию в двухмерном пространстве. Тогда она скорее походит надействительное число, а не на категорию, так что мы можем представить вектор x просто как само (i, j), отмасштабировав еготак, чтобы среднее значение было равно 0, а дисперсия была равна 1. Такойвектор признаков можно просто считать необработанными данными, без какого-либоконструирования данных:

Вчём же трудность представления x как простого местоположения агента? Не забывайте, что у наслинейная модель. Допустим, j фиксировано. Это значит, что V может изменяться только линейно относительно i, то есть, толькоотносительно координаты x. Значит, оно будет либо всегда увеличиваться, либо всегдауменьшаться, что не очень гибко.

Напомню мой курс по линейной регрессии. Есть простой способ создания новых признаков путём создания многочленов. Из курса дифференциального счисления вы, вероятно, знаете, что бесконечное разложение в ряд Тейлора может приближённо представить любую функцию. Поэтому, начав с x1 и x2, мы можем создать члены с x12, x22 и x1x2. При желании можно создать многочлены и более высоких степеней, однако следует опасаться переобученности. Именно этот метод мы и используем в данном курсе, хотя если вы знаете какие-либо другие способы ручного создания признаков, можете использовать и их.

Предсказание методом Монте-Карло с приближением

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

Напомню,что при оценивании методом Монте-Карло мы многократно повторяем два основныхэтапа: первый – игра и нахождение списка состояний и отдач, и второй –обновление V(s) с использованием отдачи как целевойпеременной и V(s) как предсказания:

Незабывайте, что это градиентный спуск, однако эквивалентный вычислению среднегозначения всех отдач для данного состояния. Поскольку в этой лекции мыприближённо представляем V(s) с помощью параметра θ, на самом деле обновлять мы будем θ и выполнять градиентный спуск мы будемотносительно θ, а не V:

Незабывайте, что это градиентный спуск, однако эквивалентный вычислению среднегозначения всех отдач для данного состояния. Поскольку в этой лекции мыприближённо представляем V(s) с помощью параметра θ, на самом деле обновлять мы будем θ и выполнять градиентный спуск мы будемотносительно θ, а не V:

Незабывайте, что всё это касается фиксированной стратегии, поскольку сейчас мыразбираем проблему предсказания. Рассмотрим псевдокод, чтобы закрепить идею:

def mc_approx_prediction(π):

    θ = случайное

    for i=1..N

   states_and_returnes = play_game

    for s, g instates_and_returnes:

        x = φ(s)

Мы начинаем с принятия входящей стратегии π и случайным образом инициируем вектор θ. Затем мы входим в цикл на некоторое количество итераций. На каждой из них мы играем в игру, что возвращает нам последовательность состояний и отдач. Мы просматриваем эти состояния и отдачи и используем их для нашего уравнения обновления θ, рассматривая отдачу как целевую переменную.

Предсказание методом Монте-Карло с приближением в коде

Реализуем предсказание методом Монте-Карло с параметризованной функцией ценности в коде. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую именно это, то соответствующий файл в репозитарии называется approx_mc_prediction.py.

Вначалеу нас идут все обычные импорты библиотек, а также некоторые полезные функции изпредыдущего скрипта, посвящённого методу Монте-Карло.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

# NOTE: this is only policy evaluation, notoptimization

# we’ll try to obtain the same result as our other MCscript

from monte_carlo_random import random_action,play_game, SMALL_ENOUGH, GAMMA, ALL_POSSIBLE_ACTIONS

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

LEARNING_RATE= 0.001

Затем у нас идёт раздел main. Для данной демонстрации мы воспользуемся standard_grid, после чего определяем стратегию.

if __name__ == ‘__main__’:

  # use thestandard grid again (0 for every step) so that we can compare

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # found bypolicy_iteration_random on standard_grid

  # MC methodwon’t get exactly this, but should be close

  # values:

  #—————————

  #  0.43| 0.56|  0.72|  0.00|

  #—————————

  #  0.33| 0.00|  0.21|  0.00|

  # —————————

  #  0.25| 0.18|  0.11| -0.17|

  # policy:

  #—————————

  #   R |   R  |   R  |     |

  #—————————

  #   U |      |   U  |      |

  #—————————

  #   U |   L  |   U  |  L  |

  policy = {

    (2, 0): ‘U’,

    (1, 0): ‘U’,

    (0, 0): ‘R’,

    (0, 1): ‘R’,

    (0, 2): ‘R’,

    (1, 2): ‘U’,

    (2, 1): ‘L’,

    (2, 2): ‘U’,

    (2, 3): ‘L’,

  }

Затемслучайным образом инициируется вектор θи определяется функция, преобразовывающая состояние в вектор признаков x. Обратитевнимание, что признаками здесь являются строка, столбец, произведение строки истолбца, и ещё один для свободного члена, так что единственным нелинейнымпризнаком тут является эффект взаимодействия между координатами i и j:

  # initializetheta

  # our model isV_hat = theta.dot(x)

  # where x = [row, col, row*col, 1] – 1 for bias term

  theta =np.random.randn(4) / 2

  def s2x(s):

    returnnp.array([s[0] – 1, s[1] – 1.5, s[0]*s[1] – 3, 1])

Далееу нас идёт основной цикл. Обратите внимание, что используется затухающийкоэффициент обучения, поэтому α равноисходному коэффициенту обучения, делённому на t. Схема та же, что и в обычномметоде Монте-Карло: мы играем в игру и получаем последовательность состояний иотдач, затем перебираем их, но вместо обновления V теперь обновляется параметр θс использованием ранее виденного уравнения для стохастического градиентногоспуска. Мы также отслеживаем все Δ,которые теперь представляют абсолютную величину разниц θ:

  # repeatuntil convergence

  deltas = []

  t = 1.0

  for it in xrange(20000):

    if it % 100== 0:

      t += 0.01

    alpha =LEARNING_RATE/t

    # generatean episode using pi

   biggest_change = 0

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      if s notin seen_states:

       old_theta = theta.copy()

        x =s2x(s)

        V_hat =theta.dot(x)

        #grad(V_hat) wrt theta = x

        theta +=alpha*(G – V_hat)*x

       biggest_change = max(biggest_change, np.abs(old_theta – theta).sum())

       seen_states.add(s)

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

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

  # obtainpredicted values

  V = {}

  states =grid.all_states()

  for s instates:

    if s ingrid.actions:

      V[s] =theta.dot(s2x(s))

    else:

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

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

Мы начинаем с принятия входящей стратегии π и случайным образом инициируем вектор θ. Затем мы входим в цикл на некоторое количество итераций. На каждой из них мы играем в игру, что возвращает нам последовательность состояний и отдач. Мы просматриваем эти состояния и отдачи и используем их для нашего уравнения обновления θ, рассматривая отдачу как целевую переменную.

Предсказание методом Монте-Карло с приближением в коде

Реализуем предсказание методом Монте-Карло с параметризованной функцией ценности в коде. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую именно это, то соответствующий файл в репозитарии называется approx_mc_prediction.py.

Вначалеу нас идут все обычные импорты библиотек, а также некоторые полезные функции изпредыдущего скрипта, посвящённого методу Монте-Карло.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

# NOTE: this is only policy evaluation, notoptimization

# we’ll try to obtain the same result as our other MCscript

from monte_carlo_random import random_action,play_game, SMALL_ENOUGH, GAMMA, ALL_POSSIBLE_ACTIONS

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

LEARNING_RATE= 0.001

Затем у нас идёт раздел main. Для данной демонстрации мы воспользуемся standard_grid, после чего определяем стратегию.

if __name__ == ‘__main__’:

  # use thestandard grid again (0 for every step) so that we can compare

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # found bypolicy_iteration_random on standard_grid

  # MC methodwon’t get exactly this, but should be close

  # values:

  #—————————

  #  0.43| 0.56|  0.72|  0.00|

  #—————————

  #  0.33| 0.00|  0.21|  0.00|

  # —————————

  #  0.25| 0.18|  0.11| -0.17|

  # policy:

  #—————————

  #   R |   R  |   R  |     |

  #—————————

  #   U |      |   U  |      |

  #—————————

  #   U |   L  |   U  |  L  |

  policy = {

    (2, 0): ‘U’,

    (1, 0): ‘U’,

    (0, 0): ‘R’,

    (0, 1): ‘R’,

    (0, 2): ‘R’,

    (1, 2): ‘U’,

    (2, 1): ‘L’,

    (2, 2): ‘U’,

    (2, 3): ‘L’,

  }

Затемслучайным образом инициируется вектор θи определяется функция, преобразовывающая состояние в вектор признаков x. Обратитевнимание, что признаками здесь являются строка, столбец, произведение строки истолбца, и ещё один для свободного члена, так что единственным нелинейнымпризнаком тут является эффект взаимодействия между координатами i и j:

  # initializetheta

  # our model isV_hat = theta.dot(x)

  # where x = [row, col, row*col, 1] – 1 for bias term

  theta =np.random.randn(4) / 2

  def s2x(s):

    returnnp.array([s[0] – 1, s[1] – 1.5, s[0]*s[1] – 3, 1])

Далееу нас идёт основной цикл. Обратите внимание, что используется затухающийкоэффициент обучения, поэтому α равноисходному коэффициенту обучения, делённому на t. Схема та же, что и в обычномметоде Монте-Карло: мы играем в игру и получаем последовательность состояний иотдач, затем перебираем их, но вместо обновления V теперь обновляется параметр θс использованием ранее виденного уравнения для стохастического градиентногоспуска. Мы также отслеживаем все Δ,которые теперь представляют абсолютную величину разниц θ:

  # repeatuntil convergence

  deltas = []

  t = 1.0

  for it in xrange(20000):

    if it % 100== 0:

      t += 0.01

    alpha =LEARNING_RATE/t

    # generatean episode using pi

   biggest_change = 0

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      if s notin seen_states:

       old_theta = theta.copy()

        x =s2x(s)

        V_hat =theta.dot(x)

        #grad(V_hat) wrt theta = x

        theta +=alpha*(G – V_hat)*x

       biggest_change = max(biggest_change, np.abs(old_theta – theta).sum())

       seen_states.add(s)

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

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

  # obtainpredicted values

  V = {}

  states =grid.all_states()

  for s instates:

    if s ingrid.actions:

      V[s] =theta.dot(s2x(s))

    else:

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

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

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

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