Функция протозначения

В прикладной математике функции протозначений (PVF) — это автоматически изучаемые базисные функции , которые полезны при аппроксимации функций значений для конкретных задач, обеспечивая компактное представление степеней матриц перехода. Они обеспечивают новую основу для решения проблемы присвоения кредитов . Структура представляет новый подход к решению марковских процессов принятия решений (MDP) и обучения с подкреплением задач с использованием многомасштабных спектральных и многообразных методов обучения. Функции протозначения генерируются путем спектрального анализа графика с использованием лапласиана графа .

Функции протозначения были впервые представлены в контексте обучения с подкреплением Шридхаром Махадеваном в его статье « Функции протозначения: обучение с подкреплением развития» на ICML 2005. ^[1]

Мотивация

функции значения Аппроксимация является важнейшим компонентом решения марковских процессов принятия решений (MDP), определенных в непрерывном пространстве состояний. Хороший аппроксиматор функций позволяет агенту обучения с подкреплением (RL) точно представлять значение любого состояния, которое он испытал, без явного сохранения его значения. Аппроксимация линейной функции с использованием базисных функций — это распространенный способ построения аппроксимации функции значения, такой как радиальные базисные функции , полиномиальное кодирование состояний и CMAC . Однако параметры, связанные с этими базисными функциями, часто требуют значительной ручной разработки с учетом специфики предметной области. ^[2] Функции протозначений пытаются решить эту проблему, требующую ручной разработки, учитывая основную многообразную структуру проблемной области. ^[1]

Обзор

Функции протозначения — это независимые от задачи глобальные базисные функции, которые в совокупности охватывают все пространство возможных функций значения для данного пространства состояний. ^[1] Они включают в себя геометрические ограничения, присущие окружающей среде. Например, состояния, близкие на евклидовом расстоянии (например, состояния на противоположных сторонах стены), могут находиться далеко друг от друга в пространстве многообразия. Предыдущие подходы к этой проблеме нелинейности не имели широкой теоретической основы и, следовательно, изучались только в контексте дискретных MDP .

Функции протозначения возникают в результате переформулировки проблемы аппроксимации функции цены как аппроксимации действительнозначной функции на графике или многообразии. Это приводит к более широкому применению изученных баз и позволяет создать новый класс алгоритмов обучения, которые одновременно изучают представления и политики. ^[3]

Базисные функции из графа Лапласа

Этот подход строит базисные функции путем спектрального анализа лапласиана графа, самосопряженного (или симметричного) оператора в пространстве функций на графике, тесно связанного с оператором случайного блуждания .

Для простоты предположим, что базовое пространство состояний может быть представлено как неориентированный невзвешенный граф. $G=(V,E)$ Комбинаторный лапласиан $L$ определяется как оператор $L=D-A$ , где $D$ представляет собой диагональную матрицу, называемую матрицей степеней , и $A$ – матрица смежности . ^[1]

Спектральный анализ оператора Лапласа на графе состоит в нахождении собственных значений и собственных функций, которые решают уравнение

L\varphi _{\lambda }=\lambda \varphi _{\lambda },

где $L$ является комбинаторным лапласианом, $\varphi _{\lambda }$ является собственной функцией, связанной с собственным значением $\lambda$ . Здесь термин «собственная функция» используется для обозначения того, что традиционно называют собственным вектором в линейной алгебре, поскольку собственные векторы Лапласа естественным образом можно рассматривать как функции, которые отображают каждую вершину в действительное число. ^[3]

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

Нормализованный лапласиан $L_{\text{normalized}}=I-D^{-1/2}AD^{-1/2}$ ^[4]
Случайное блуждание $P=D^{-1}A$ ^[4]

Построение графа в дискретном пространстве состояний

Для конечного пространства состояний граф $G$ Упомянутое выше можно просто построить, исследуя связи между состояниями. Позволять $S_{i}$ и $S_{j}$ быть любыми двумя состояниями. Затем

G_{i,j}={\begin{cases}1&{\text{if }}S_{i}\leftrightarrow S_{j}\\0&{\text{otherwise}}\end{cases}}

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

Построение графа на непрерывном или большом пространстве состояний

Для непрерывного пространства состояний или просто очень большого дискретного пространства состояний необходимо осуществлять выборку из многообразия в пространстве состояний. Затем построим график $G$ на основе образцов. Здесь следует рассмотреть несколько вопросов: ^[4]

Как взять пробу коллектора
- Случайная прогулка или исследование под руководством гида
Как определить, нужно ли соединять два образца

Приложение

После создания PVF их можно подключить к традиционной системе аппроксимации функций. Одним из таких методов является аппроксимация методом наименьших квадратов.

Приближение методом наименьших квадратов с использованием функций протозначений

Позволять $\Phi _{G}=\left\{V_{1}^{G},\dots ,V_{k}^{G}\right\}$ быть базовым набором PVF, где каждый $V_{i}^{G}$ — собственная функция, определенная для всех состояний графа $G$ . Позволять ${\widehat {V}}^{\pi }$ быть функцией целевого значения, которая известна только для подмножества состояний $S_{M}^{G}=\left\{s_{1},\dots ,s_{m}\right\}$ .

Определите матрицу грамма

K_{G}=\left(\Phi _{m}^{G}\right)^{T}\Phi _{m}^{G}.

Здесь $S_{m}^{G}$ это покомпонентная проекция PVF на состояния в $S_{G}^{m}$ . Следовательно, каждый элемент матрицы грамма есть

K_{G}(i,j)=\sum _{k}V_{i}^{G}(k)V_{j}^{G}(k).

Коэффициенты, минимизирующие ошибку метода наименьших квадратов, затем описываются уравнением

\alpha =K_{G}^{-1}\left(\Phi _{M}^{G}\right)^{T}{\widehat {V}}^{\pi }.

Нелинейный подход наименьших квадратов возможен за счет использования k PVF с наибольшими абсолютными коэффициентами для вычисления аппроксимации. ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Махадеван, С. Функции протоценностей: обучение с подкреплением развития . Материалы Международной конференции по машинному обучению ICML 2005.
^ Джонс Дж. и Махадеван С., Построение базисных функций из ориентированных графов для аппроксимации функции значения , Международная конференция по машинному обучению (ICML), 2007 г.
^ Jump up to: ^а ^б Махадеван С. и Маджионо М., Функции протозначения: лапласова структура для обучения представлению и управлению в марковских процессах принятия решений , Массачусетский университет, Технический отчет факультета компьютерных наук TR-2006-35, 2006 г.
^ Jump up to: ^а ^б ^с Махадеван С. и Маджионо М. Учебное пособие ICML 2006 .

[key1-1] Jump up to: ^а ^б ^с ^д ^и Махадеван, С. Функции протоценностей: обучение с подкреплением развития . Материалы Международной конференции по машинному обучению ICML 2005.

[key2-2] Джонс Дж. и Махадеван С., Построение базисных функций из ориентированных графов для аппроксимации функции значения , Международная конференция по машинному обучению (ICML), 2007 г.

[key3-3] Jump up to: ^а ^б Махадеван С. и Маджионо М., Функции протозначения: лапласова структура для обучения представлению и управлению в марковских процессах принятия решений , Массачусетский университет, Технический отчет факультета компьютерных наук TR-2006-35, 2006 г.

[key4-4] Jump up to: ^а ^б ^с Махадеван С. и Маджионо М. Учебное пособие ICML 2006 .

[1]

[2]

[3]

[4]