Автоматическое построение базисной функции

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

Мотивация

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

Linear function approximators (LFAs) are widely adopted for their low theoretical complexity. Two sub-problems needs to be solved for better approximation: weight optimization and basis construction. To solve the second problem, one way is to design special basis functions. Those basis functions work well in specific tasks but are significantly restricted to domains. Thus constructing basis construction functions automatically is preferred for broader applications.

Определение проблемы

Марковский процесс принятия решений с конечным пространством состояний и фиксированной политикой определяется с помощью пятикортежа ${s,a,p,\gamma ,r}$, который включает конечное пространство состояний $S={1,2,\ldots ,s}$, конечное пространство действия $A$, функция вознаграждения $r$, коэффициент дисконтирования $\gamma \in [0,1)$и модель перехода $P$.

Уравнение Беллмана определяется как:

$v=r+\gamma Pv.\,$

Когда количество элементов в $S$ маленький, $v$ обычно сохраняется в табличной форме. Пока $S$ становится слишком большим для такого рода представления. $v$ обычно аппроксимируется с помощью линейной комбинации базисной функции $\Phi ={\phi _{1},\phi _{2},\ldots ,\phi _{n}}$, чтобы у нас было:

$v\approx {\hat {v}}=\sum _{i=1}^{n}\theta _{n}\phi _{n}$

Здесь $\Phi$ это $|S|\times n$ матрица, в которой каждая строка содержит вектор признаков для соответствующей строки, $\theta$ представляет собой весовой вектор с n параметрами и обычно $n\ll |s|$.

Построение базиса ищет способы автоматического построения лучшей базисной функции. $\Phi$ который может хорошо представлять функцию ценности.

Хороший метод строительства должен обладать следующими характеристиками:

• Границы небольшой ошибки между оценкой и функцией реального значения
• Сформируйте ортогональный базис в пространстве функции ценности
• Быстрое переход к функции стационарного значения

Популярные методы

Протоценностная основа

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

Нормализованный лапласиан графа определяется как:

$L=I-D^{-{\frac {1}{2}}}WD^{-{\frac {1}{2}}}$

Здесь W — матрица смежности , которая представляет состояния фиксированной политики MDP, которая образует неориентированный граф (N,E). D — диагональная матрица, связанная со степенями узлов.

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

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

Krylov basis

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

Векторы в рядах Неймана обозначаются как $y_{i}=P^{i}r$ для всех $i\in [0,infty)$.

Это показывает, что пространство Крылова, натянутое на $y_{0},y_{1},\ldots ,y_{m-1}$ достаточно для представления любой функции значения, а m — степень минимального многочлена $(I-\gamma P)$.

Предположим, что минимальный многочлен равен $p(A)={\frac {1}{\alpha _{0}}}\sum _{i=0}^{m-1}\alpha _{i+1}A^{i}$, и у нас есть $BA=I$, функцию значения можно записать как:

$v=Br={\frac {1}{\alpha _{0}}}\sum _{i=0}^{m-1}\alpha _{i+1}(I-\gamma P)^{i}r=\sum _{i=0}^{m-1}\alpha _{i+1}\beta _{i}y_{i}.$

Алгоритм Расширенный метод Крылова

$z_{1},z_{2},\ldots ,z_{k}$ являются верхними действительными собственными векторами P

$z_{k+1}:=r$

для $i:=1:(l+k)$ делать

если $i>k+1$ затем

$z_{i}:=Pz_{i-1}$;

конец, если

для $j:=1:(i-1)$ делать

$z_{i}:=z_{i}-<z_{j},z_{i}>z_{j};$

конец для

если $\parallel z_{i}\parallel \approx 0$ затем

перерыв ;

конец, если

конец для

• k: количество собственных векторов в базисе
• l: общее количество векторов

Основа ошибки Беллмана

Ошибка Беллмана (или BEBF) определяется как: $\varepsilon =r+\gamma P{\hat {v}}-{\hat {v}}=r+\gamma P\Phi \theta -\Phi \theta$.

Грубо говоря, ошибка Беллмана указывает на функцию оптимального значения. Последовательность BEBF образует базисное пространство, ортогональное пространству функций действительного значения; таким образом, при достаточном количестве BEBF любая функция значения может быть представлена ​​точно.

Алгоритм BEBF

этап этап i=1, $\phi _{1}=r$;

этап $i\in [2,N]$

вычислить весовой вектор $\theta _{i}$ согласно текущей базисной функции $\Phi _{i}$;

вычислить новую ошибку Беллмана с помощью $\varepsilon =r+\gamma P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}$;

добавьте ошибку Беллмана, чтобы сформировать новую базисную функцию: $\Phi _{i+1}=[\Phi _{i}:\varepsilon ]$;

• N представляет количество итераций до сходимости.
• «:» означает сопоставление матриц или векторов.

Базы среднего вознаграждения Беллмана

База среднего вознаграждения Беллмана (или BARB) аналогично «Базисам Крылова», но функция вознаграждения расширяется за счет средней скорректированной матрицы перехода $P-P^{*}$. Здесь $P^{*}$ можно рассчитать многими методами.

BARB сходятся быстрее, чем BEBF и Крылов, когда $\gamma$ близко к 1.

Алгоритм BARB

этап этап i=1, $P^{*}r$;

этап $i\in [2,N]$

вычислить весовой вектор $\theta _{i}$ согласно текущей базисной функции $\Phi _{i}$;

вычислить новый базис: $:\phi _{i+1}=r-P^{*}r+P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}$и добавьте его, чтобы сформировать новую базовую матрицу $\Phi _{i+1}=[\Phi _{i}:\phi _{i+1}]$;

• N представляет количество итераций до сходимости.
• «:» означает сопоставление матриц или векторов.

Обсуждение и анализ

Существует два основных типа методов построения базиса.

Первый тип методов чувствителен к вознаграждению, как Крылов и BEBF; они геометрически расширяют функцию вознаграждения за счет матрицы перехода. Однако, когда коэффициент дисконтирования $\gamma$ при приближении к 1 Крылова и BEBF сходятся медленно. Это связано с тем, что погрешность методов, основанных на Крылове, ограничена полиномом Чебышева. Для решения этой проблемы предлагаются такие методы, как BARB. BARB — это инкрементный вариант оснований Дразина, который сходится быстрее, чем Крылов и BEBF, когда $\gamma$ становится большим.

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

См. также

• Динамическое программирование
• уравнение Беллмана
• Оптимальное управление

Внешние ссылки

• [1] Лаборатория UMASS ALL