Обучение с подкреплением связано с попыткой агента достичь оптимального поведения в неизвестных средах, которые обычно проявляют стохастичность. Несмотря на минимальный контроль, алгоритмы обучения с подкреплением продемонстрировали многочисленные успехи - от решения игр ATARI с использованием Deep Q-Networks до триумфальной победы над чемпионами мира в игре GO, а недавно и в Start Craft.
Возможно, наиболее интуитивно понятная формулировка обучения с подкреплением исходит из книги Эндрю и Рича, в которой агент обучения с подкреплением рассматривается как действующий в процессе принятия решений Маркова с целью изучения оптимального правила или политики выбора действий. Хотя это и было интересно, со временем я пришел к пониманию другого взгляда на обучение с подкреплением, уходящего корнями в вероятностное моделирование и вариационный вывод. Я обнаружил, что такое определение объединяет различные взгляды на обучение с подкреплением в рамках одной общей концепции и дает более формальный подход к данной области в целом. Я подробно расскажу о такой формулировке и объясню некоторые возникающие особые случаи, например, обучение с подкреплением с максимальной энтропией и другие. Чтобы полностью понять такую формулировку, читатель должен иметь доступ к сведениям о вероятностном моделировании, моделях со скрытыми переменными и нижней границе свидетельств (ELBO). Таким образом, я разделил этот пост на две части. В этой части мы обсудим основы, открывающие путь к формулировке обучения с подкреплением во второй части.
Вероятностное моделирование и модели со скрытыми переменными.
Представьте, что вам дан набор данных о некоторых наблюдаемых переменных. Вы заинтересованы в понимании распределения, определяющего эти наблюдения. Для этого вы предполагаете существование скрытой или скрытой переменной, которая не является наблюдаемой напрямую, но предполагается, что она влияет на ваши наблюдения. Эти переменные обычно вводятся в статистическую модель, которую мы называем моделью скрытых переменных, с разными целями, например, представление ненаблюдаемых факторов, учет ошибок измерения, среди прочего. В машинном обучении модели со скрытыми переменными находят множество приложений в различных областях, например, для кластеризации, уменьшения размерности и, в первую очередь, для анализа временных рядов. Такие приложения важны в реальном мире. Например, понимание того, как моделировать данные временных рядов, можно адаптировать к приложениям в робототехнике и на фондовом рынке.
Чтобы лучше понять скрытые модели, давайте рассмотрим пример моделирования данных временных рядов. Допустим, вы собрали набор данных, описывающих совместные движения руки робота за некоторый временной горизонт. Учитывая эту коллекцию, наша цель - понять скрытый или скрытый процесс (т. Е. Динамику), с помощью которого были созданы эти данные. Если бы эти данные были (незначительно) одинаково независимо распределены, наша проблема была бы намного проще. К сожалению, суставы в какой-то момент в будущем могут (и действительно зависят) от значений суставов на предыдущих временных шагах. Таким образом, нам нужно более осторожно обращаться с нашими вероятностными предположениями о данных. Здесь есть разные типы моделей, которые мы можем использовать, но нас будет интересовать так называемая Марковская модель первого порядка, как подробно описано ниже. Интуитивно это предположение относится к отношениям условной независимости, когда при текущем наблюдении будущее не зависит от прошлого.
Я могу начать философское обсуждение, мотивируя это. Но это не доклад конференции, так что давайте продолжим! Это просто математически удобное предположение, чтобы сделать нашу проблему более разрешимой.
Рисунок (вероятностная графическая модель) ниже иллюстрирует наши исходные предположения при моделировании. Стрелки на рисунке представляют собой вероятностную связь. Например, переменная на 3-м временном шаге зависит только от переменной на 2-м временном шаге, а не одновременно на 2-м и 1-м. Другими словами, плотность переменной на временном шаге 3 зависит только от плотности переменной на 2-м временном шаге.
До сих пор мы не вводили никаких скрытых или скрытых переменных и делали вероятностные предположения непосредственно на наших наблюдаемых переменных. Помимо других ограничений, такой тип моделей не может хорошо справляться с проблемами данных большой размерности, например, когда наблюдения представляют собой последовательность изображений. Это не только позволит масштабировать нашу модель, но также может представить интерпретируемые сводки наблюдаемых данных.
Таким образом, мы введем скрытую (обычно низкоразмерную) переменную, которая определяет переходы между временными шагами. Это приводит нас к графической модели, изображенной ниже. Как вы можете видеть, теперь у нас есть скрытый слой, который зависит от времени, что, в свою очередь, вызывает наблюдения.
Другими словами, нам удалось ввести скрытый случайный процесс, который генерирует наблюдаемые нами наблюдения. Если бы мы смогли найти такой процесс, мы бы обнаружили фундаментальное свойство системы (например, нашего робота), которое можно использовать для предсказаний и прогнозов на будущее. Учитывая приведенную выше графическую модель, теперь нам нужно официально заявить о наших предположениях, которые позволят нам узнать о таком скрытом процессе. Например, нам нужно понять, что диктует переходы в нашем скрытом слое или как наблюдение будет генерироваться из скрытого слоя. Конечно, мы заранее не знали бы точное распределение. Скорее, мы трансформируем проблему в проблему машинного обучения, где мы параметризируем широкий класс распределений и подбираем параметры в соответствии с наблюдаемыми данными.
Изложение наших предположений:
Наиболее близким к сердцу разработчику вероятностных моделей является четкое изложение предположений, которые используются для определения проблемы. Лично я их не виню, поскольку считаю, что четкое определение проблемы является ключом к любому алгоритму машинного обучения. Инженерия приходит позже! Математика на первом месте! Я не могу не подчеркнуть этого, инженерия приходит позже! Математика на первом месте!
Надеюсь, вы все еще читаете такое провокационное заявление. Как вы знаете, также можно кодировать то, что вы еще не определили.
В любом случае, давайте теперь начнем делать некоторые предположения о наших скрытых процессах и процессах наблюдения. Далее следует специальный набор предположений, которые я выбрал для презентации. Вы можете сделать эту задачу настолько сложной, насколько захотите, в зависимости от ваших данных, например, дискретные или непрерывные, типа скрытых функций и т. Д.
Начиная со скрытых переменных, мы знаем, что информация на текущем временном шаге зависит только от предыдущего. Мы также знаем, что наша скрытая переменная является непрерывной (также может быть дискретной, но пока давайте остановимся на непрерывной). Таким образом, мы параметризуем функцию, которая связывает непрерывную переменную на текущем временном шаге с таковой на предыдущем. Пока эта функция детерминирована. Мы собираемся вызвать распределение в скрытом пространстве, используя очень примитивную и простую структуру. А именно, мы предполагаем, что наше наблюдение скрытой переменной является значением функции в дополнение к возмущению гауссовского шума. Формально мы говорим:
Вышеприведенное уравнение просто устанавливает временные отношения в скрытом пространстве. Говоря более формально, наша функция, по сути, представляет собой карту, связанную с измерением скрытой переменной обратно в это измерение. Что касается распределения по эпсилону, мы просто выбираем многомерное гауссовское. Если вы не знакомы с этой концепцией, просто подумайте о ней как об обобщении одномерного распределения Гаусса на большее количество измерений. Вместо того, чтобы иметь среднее значение и значения ковариации. Теперь у нас есть средний вектор и ковариационная матрица, чтобы рассматривать более высокие измерения. Здесь вы можете найти хорошее введение в них.
На приведенном выше рисунке я проиллюстрировал, как ведет себя гауссово распределение в двух измерениях. На поведение этих графиков влияют два компонента. Первый - это средний вектор, а второй - ковариационная матрица. Вектор среднего просто указывает, где находится центр распределения, а ковариационная матрица определяет «растяжение» в каждом измерении. Чтобы проиллюстрировать этот момент, обратите внимание, что ковариационная матрица имеет размер 2 x 2 для двумерной задачи. Записи в верхнем левом и нижнем правом углу отражают дисперсию в каждом измерении, а другой представляет ковариацию по этим измерениям (то есть, как одно измерение будет отличаться по отношению к другому). Таким образом, если вы установите высокие дисперсии в каждом из измерений и нулевые ковариации, можно ожидать плоского распределения, как показано в правой части рисунка выше.
Учитывая сделанное выше предположение о временной структуре скрытых переменных, мы можем легко вывести условное распределение переменной на текущем временном шаге, обусловленном предыдущим. Обычно людям предлагаются эти уравнения, которые принимаются как должное, но вывести такое распределение действительно просто. В этом нет ничего особенного. Давай сделаем так. Вот как это можно понять:
- Мы знаем, что условное распределение является гауссовым, поскольку мы просто преобразуем гауссовский шум
- Мы знаем, что гауссовское распределение в больших размерностях имеет средний вектор и ковариационную матрицу.
- Мы знаем, что среднее значение - это просто математическое ожидание, которое, как известно, является линейным (т.е. мы можем добавить ожидания).
- Мы знаем определение ковариационной матрицы
- Мы умеем делать простую арифметику.
Начнем с вычисления среднего значения распределения. Эти отведения показаны на рисунках ниже:
Здесь мы впервые поняли, что среднее - это ожидание. Затем мы использовали определение нашей временной модели из прошлого. При этом мы использовали линейное свойство математического ожидания и поняли, что функция детерминирована (так что среднее значение - это само значение), а эпсилон имеет среднее значение, равное нулю. Конечно, это правда, поскольку мы принимаем ожидаемые значения в отношении нашего шума-эпсилон. Обратите внимание, что скрытая переменная сама по себе является стохастической, но наши ожидания выше относятся к аддитивному шумовому эпсилону. Итак, теперь мы знаем, что среднее значение - это просто значение функции на предыдущем временном шаге. Теперь мы приступаем к построению ковариационной матрицы нашего распределения. Это можно сделать аналогичным образом:
Опять же, мы начали с определения ковариационной матрицы и использовали среднее значение, полученное нами на предыдущем шаге. Учитывая среднее значение, выражение в середине оказывается просто эпсилон. Таким образом, в последнем уравнении мы понимаем, что не ищем ничего, кроме ковариации самого эпсилона. Следовательно, наше условное распределение - это не что иное, как гауссово, сосредоточенное вокруг значения функции и имеющее ту же ковариацию, что и эпсилон. Обратите внимание: нам нужно подобрать как свободные параметры модели, так и ковариационную матрицу. Интересно, что ковариационная матрица должна быть положительно полуопределенной. Поэтому при его оптимизации нам нужно использовать некоторые приемы, например, либо полуопределенную программу, либо треугольную факторизацию. Я расскажу об этом позже.
После определения нашей динамики состояния или временного уравнения в скрытом пространстве у нас теперь остается еще один ингредиент для заключения сделки. То есть мы должны определить распределение, с помощью которого создается наблюдение, учитывая скрытое представление. Из вероятностной графической модели выше мы понимаем, что наблюдение на текущем временном шаге зависит от скрытой переменной на том же временном шаге. Это можно получить, как показано на изображении ниже.
Здесь мы просто параметризовали функцию, чтобы связать скрытые переменные с наблюдениями. Эта функция сама по себе детерминирована. Таким образом, мы ввели гауссовский шум, чтобы вызвать распределение. Следуя шагам, аналогичным предыдущему выводу, мы пришли к условному распределению наблюдаемой переменной с учетом латентности, которое представляет собой не что иное, как еще одну многомерную гауссову функцию с детерминированной функцией, являющейся средним значением и имеющей ту же ковариационную матрицу, что и шум. В дополнение к предыдущим свободным параметрам это определение вводит набор из 2 новых свободных переменных для подгонки, являющихся параметрами неизвестной функции и шума. Также обратите внимание, что если бы мы выбрали линейную скрытую модель и модель наблюдения, а ковариации шума не зависели от времени, мы бы пришли к стандартному методу фильтрации Калмана.
Вывод проблемы оптимизации:
Сформулировав все наши предположения, теперь мы готовы приступить к оптимизации под свободные параметры модели. Обычно в машинном обучении начинают непосредственно с проблемы оптимизации, практически не обращая внимания на то, откуда она взялась. Например, многие люди знают цель оптимизации ошибок методом наименьших квадратов и аргументируют это интуитивно. Хорошо! Но откуда взялась эта цель?
Оказывается, эта цель - не что иное, как максимизация оценки правдоподобия в условиях гауссовского шума! Мы не собираемся выводить его здесь, но этот пример предназначен для иллюстрации того, что цели оптимизации могут быть в основном получены из предположений вероятностного моделирования. Мы собираемся проиллюстрировать эту идею на нашем рабочем примере моделей обучения для задач временных рядов.
Как вывести нашу задачу оптимизации? У нас есть доступ только к наблюдениям (например, к записанным значениям суставов), и мы хотели бы обучить все наши свободные переменные. В ПОРЯДКЕ! Итак, давайте попробуем найти модель, которая максимизирует совместное распределение - также называемое маргинальным - наших наблюдений. Чтобы понять это, вам нужно знать следующие два понятия:
Концепция I. Маргинализация плотностей вероятностей: Я уверен, что вы видели это раньше, возможно, в другом контексте. Предположим, у нас есть две дискретные случайные величины X и Y, которые взаимозависимы. Если мы хотим найти распределение X равным некоторому значению x из соединения, мы просто маргинализуем Y. Другими словами, если вы просуммируете совместное распределение по всем возможным значениям Y, вы получите распределение над X. Мы можем сделать то же самое для непрерывных случайных величин. Вместо того, чтобы подводить итоги, нам просто нужно интегрироваться. Это то, что мы видим в приведенном ниже уравнении:
Пояснение: в правой части уравнения у нас просто совместное распределение наших наблюдений. Это количество, которое мы хотели бы максимизировать. В частности, мы хотели бы подогнать наши свободные параметры таким образом, чтобы максимизировать плотность наших наблюдений. Все идет нормально! Но в чем же заключаются предположения, которые мы разработали до сих пор? Что ж, наше предположение гласило, что на наблюдения влияют скрытые переменные, которые придерживаются некоторой временной структуры. Следовательно, мы можем рассматривать плотность наших наблюдений как результат маргинализации скрытых явлений. Именно для этого предназначены интегралы в правой части уравнения. Мы просто интегрируем из общей плотности (сверх наблюдаемой и скрытой) все скрытые переменные.
Концепция II - Факторизация распределений вероятностей: Чтобы начать наши выводы, нам нужно обработать совместное распределение в правой части приведенного выше уравнения, которое принимает во внимание допущения моделирования, которые мы ввели ранее. Это тоже несложно. Все, что вам нужно знать, это как разложить на множители совместные плотности с точки зрения условных выражений, что также известно как цепное правило вероятности. Это просто говорит о следующем:
- Объяснение: Итак, если у нас есть набор случайных величин, мы можем факторизовать их совместное распределение, связав последнюю случайную переменную с предыдущей, а затем умножив на совокупность оставшихся переменных. Обратите внимание, что мы можем применить это дальше, просто обусловив переменную n-1 на остальном, а затем умножив на соединение остатка.
Здорово! Применим эту идею к нашей проблеме. Если мы это сделаем, то получим:
Теперь мы можем рекурсивно применять ту же идею к последнему члену в правой части приведенного выше уравнения, пока не дойдем до переменных на первом временном шаге. Ниже приведены основные шаги, которые необходимо выполнить:
Таким образом, вы сможете убедиться, что наше совместное распределение как по скрытым, так и по наблюдаемым переменным удобно разлагается на множители до формы, показанной в уравнении ниже:
Интересно, что форма, к которой мы пришли, позволяет нам использовать полученные выше распределения (например, распределение эмиссионной модели и временные распределения скрытого пространства). Теперь должно быть более ясно, почему мы решили выбрать многомерные гауссовы возмущения во время фазы предположений. На самом деле это не философия! (А теперь давайте послушаем это от «Центральных ограничителей»)
Это просто математическое удобство. Как видите, приведенное выше уравнение требует, чтобы мы умножили различные плотности вероятности. Умножение гауссианов легко, и поэтому мы выбрали наши предположения. Это не значит, что вы не можете выбирать другие формы. На самом деле, существует множество исследований по обработке трудноразрешимых моделей, которые я оставлю для будущих публикаций.
Внимательно изучив приведенное выше уравнение, мы понимаем, что знаем о нем все, кроме распределения по скрытой переменной на первом временном шаге. Есть несколько способов справиться с этим. А пока давайте предположим, что это априор для скрытой переменной на первом временном шаге, который мы указываем.
Нижняя граница доказательств (ELBO):
До сих пор мы вывели основные уравнения, необходимые для нашей модели. Мы обсудили вероятностные допущения, вывели некоторые условные распределения и подробно описали (на высоком уровне) величину, которую мы хотели бы максимизировать, чтобы соответствовать нашим свободным параметрам. Перед тем, как опубликовать полную проблему оптимизации, необходимо внимательно изучить еще одну проблему.
Помните уравнение со всеми интегралами? Ага, это страшно! Видите ли, мы еще не обсуждали, как вычислять или обрабатывать какие-либо из этих интегралов. Фактически, это самая сложная часть нашей проблемы, которая легко может стать неразрешимой.
Мой блестящий коллега, который является экспертом в этих проблемах, однажды сказал, и я перефразирую: «Вы знаете, я провел свою карьеру, изучая множество методов, которые позволяют мне интегрировать чрезвычайно сложные проблемы. Я никогда не думал, что интеграционный курс, который я прошел в первый год обучения в колледже, может оказать на меня такое сильное влияние ». Потягивая свой напиток, я был уверен, что интеграция, хочешь еще выпить?
Я так и не понял этого утверждения, пока не столкнулся с вариационным выводом. Помимо других многочисленных приложений, вот он снова. Интеграция также проявляется в машинном обучении. Хм! Мой коллега может что-то понять!
С моей точки зрения, прелесть вариационного вывода заключалась в том, чтобы преобразовывать жесткие интегралы (как тот, который у нас есть выше) в задачи оптимизации, с которыми можно легче справиться. Что ж, это утверждение является спорным, поскольку в результате возникают проблемы оптимизации, которые становятся невыпуклыми, что сами по себе трудно решить. Тем не менее, мы все еще можем найти приемлемое решение, используя такие алгоритмы, как Adam, SGD и другие.
Вместо того, чтобы точно вычислять наши интегралы, мы собираемся прибегнуть к приближению. Другими словами, знайте, что величина, которую мы хотим аппроксимировать, является плотностью вероятности, которую мы не можем вычислить точно. Следовательно, мы собираемся принять семейство параметризованных распределений (в скрытом пространстве) и попытаться подогнать его параметры так, чтобы получить «наилучшее» возможное приближение. Мы называем распределение вариационным распределением, а его параметры - вариационными параметрами.
Исходя из этого предположения, мы теперь можем переписать нашу исходную проблему в более решаемую. Мы собираемся сделать это в три этапа:
Шаг 1. Внесите вариационное распределение в уравнение маргинализации. На этом этапе мы просто берем наше уравнение маргинализации, умножаем и делим на вариационное распределение. Это показано на рисунке ниже:
Шаг 2. Введите логарифм в задачу оптимизации. Как вы помните, наша цель - максимизировать предельную плотность наших наблюдений. Вместо максимизации самой функции можно максимизировать логарифм этой функции. Здесь у вас могут возникнуть два вопроса:
1) Почему это утверждение верно? и 2) Зачем нам нужно вводить такую функцию в нашу задачу.
2) Зачем нам нужно вводить такую функцию: Позвольте мне сначала ответить на второй вопрос. У логарифма есть несколько интересных свойств, которые позволят нам в конце концов решить более простую задачу. Например, журнал продукта становится суммой журналов. Это свойство, например, может быть полезно для нас, поскольку в нашей проблеме много таких продуктов (помните, что мы учли наше распределение в Концепции II).
1) Почему это утверждение верно? Относительно того, почему введение журнала сохраняет решение проблемы неизменным, есть два объяснения. Этакий интуитивный выглядит следующим образом. Представьте, что вы хотите максимизировать функцию в одном измерении. Это означает, что его производная установлена в ноль где-то в ваших вычислениях. Хорошо, когда производная логарифма функции будет равна нулю? Зацени. Теперь к более формальному объяснению. Я обнаружил, что этот источник дает хорошее объяснение этого факта, что вы можете проверить его на том же сайте. Это выглядит следующим образом:
Как видно из рисунка выше, это работает не только для логарифма, но и для любой возрастающей функции. Круто, теперь мы знаем, почему введение журнала не причиняет нам вреда и даже помогает нам.
Вводя логарифм, нашу задачу теперь можно записать так:
Шаг 3 - Неравенство Дженсена: если мы хотим извлечь выгоду из логарифма, нам лучше попытаться поместить его внутри знака интеграции - тогда мы можем, например, преобразовать все продукты в суммы - Какое удовольствие! Но как мы собираемся это сделать? Здесь на помощь приходит неравенство Дженсена. Итак, что говорит Дженсен:
А именно, если у нас есть случайная величина с некоторым ожиданием и мы применяем выпуклую функцию к этому ожиданию, мы можем взять функцию внутри математического ожидания, введя знак «меньше» или «равно». Это можно сделать аналогично для вогнутой функции (наш случай), но со знаком больше или равно.
Прохладный! Тогда как это применимо к нашей проблеме? Что ж, знаки интегрирования - ничто по математическому ожиданию, которое мы преобразуем с помощью вогнутой функции. Следовательно, мы можем написать:
Проще говоря, мы поняли, что все интегралы соответствуют математическому ожиданию (при вариационном распределении) отношения совместного наблюдения и маргиналов к вариационному распределению. Это должно быть легко увидеть из определения математического ожидания для непрерывных случайных величин.
Проблема оптимизации:
Теперь мы на последнем этапе, где мы собираем все вместе и рассматриваем нашу проблему оптимизации. Ура!
При этом мы понимаем, что нам нужно сделать некоторые предположения о структуре нашего вариационного распределения. Есть множество способов выбрать такое распределение. Чем лучше структура, чем информативнее распределение, тем лучше наше приближение. Я собираюсь придерживаться простого, в котором факторы моего вариационного распределения аналогичны распределению скрытых переменных. Ни в коем случае, это единственный способ сделать. Заинтересованных читателей отсылают сюда для более глубокого обсуждения этой темы. При этом наши выводы можно записать как:
Наконец, мы достигли цели оптимизации, которую мы хотели бы максимизировать, чтобы соответствовать свободным параметрам. Теперь мы можем заменить все наши предположения моделирования (например, гауссовские распределения) и приступить к оптимизации. Обратите внимание, что эти параметры включают в себя все параметры из наших предположений моделирования (например, параметры для функций f и g, ковариационные матрицы, распределение начального состояния - мы называем их параметрами модели, а также вариационным распределением). Чтобы изучить эти два набора параметров (то есть модельный и вариационный), мы можем продолжить, используя, например, альтернативную оптимизацию, где мы исправляем первый, обновляем второй набор и затем повторяем. Другие авторы применяют шаг градиента к обоим параметрам совместно (например, выполнить Адама на обоих наборах). Также есть интересное направление работы, которое выполняет естественные градиенты, что может быть очень эффективным для гауссовых распределений и естественной параметризации.
В качестве последнего предостережения обратите внимание, что количество параметров нашего вариационного распределения может стать большим, поскольку каждый временной шаг требует другого набора параметров. С этим можно справиться по-разному. В одном интересном подходе, который я прочитал, использовалась рекуррентная нейронная сеть для их параметризации. Возможно, вы захотите посмотреть:
Прохладный! Теперь вы должны быть готовы к применению таких идей в обучении с подкреплением для более общего определения проблемы. Оставайтесь в курсе второй части!
Это сообщение в блоге было бы невозможно без помощи других. Крик:
Расул Тутунов (Вычитка и проверка математики)
Лекции гуру моделирования, смотрите:
