Funkcja protowartości

W matematyce stosowanej funkcje protowartości (PVF) to automatycznie wyuczone funkcje bazowe , które są przydatne w aproksymacji funkcji wartości specyficznych dla zadania, zapewniając zwartą reprezentację potęg macierzy przejść. Stanowią one nowatorskie ramy rozwiązywania problemu przypisania punktów . Ramy wprowadzają nowatorskie podejście do rozwiązywania procesów decyzyjnych Markowa (MDP) i problemów z uczeniem się przez wzmacnianie , wykorzystując wieloskalowe uczenie spektralne i wielokrotne metody. Funkcje protowartościowe są generowane poprzez analizę widmową wykresu przy użyciu wykresu Laplaciana .

Funkcje protowartości zostały po raz pierwszy wprowadzone w kontekście uczenia się przez wzmacnianie przez Sridhara Mahadevana w jego artykule pt. Funkcje protowartości: uczenie się przez wzmocnienie rozwojowe na ICML 2005.

Motywacja

Aproksymacja funkcji wartości jest kluczowym elementem rozwiązywania procesów decyzyjnych Markowa (MDP) zdefiniowanych w ciągłej przestrzeni stanów. Dobry aproksymator funkcji umożliwia uczenia się przez wzmacnianie (RL) dokładne przedstawienie wartości dowolnego stanu, którego doświadczył, bez jawnego przechowywania jego wartości. Aproksymacja funkcji liniowej przy użyciu funkcji bazowych jest powszechnym sposobem konstruowania aproksymacji funkcji wartości, na przykład radialnych funkcji bazowych , kodowania stanów wielomianowych i CMAC . Jednakże parametry związane z tymi funkcjami podstawowymi często wymagają znacznej ręcznej inżynierii specyficznej dla danej dziedziny. Funkcje proto-wartości próbują rozwiązać tę wymaganą ręczną inżynierię poprzez uwzględnienie podstawowej struktury rozmaitości domeny problemowej.

Przegląd

Funkcje protowartości są niezależnymi od zadań globalnymi funkcjami bazowymi, które łącznie obejmują całą przestrzeń możliwych funkcji wartości dla danej przestrzeni stanów. Zawierają ograniczenia geometryczne nieodłącznie związane ze środowiskiem. Na przykład stany bliskie odległości euklidesowej (takie jak stany po przeciwnych stronach ściany) mogą być daleko od siebie w przestrzeni rozmaitej. Poprzednim podejściu do tego problemu nieliniowości brakowało szerokich ram teoretycznych, w związku z czym badano je jedynie w kontekście dyskretnych MDP .

Funkcje protowartości powstają w wyniku przeformułowania problemu aproksymacji funkcji wartości na przybliżenie funkcji o wartościach rzeczywistych na wykresie lub rozmaitości. Powoduje to szersze zastosowanie wyuczonych baz i umożliwia nową klasę algorytmów uczenia się, które jednocześnie uczą się reprezentacji i polityk.

Funkcje bazowe z wykresu Laplaciana

Podejście to konstruuje funkcje bazowe poprzez analizę widmową grafu Laplaciana, operatora samosprzężonego (lub symetrycznego) na przestrzeni funkcji na wykresie, ściśle powiązanego z operatorem błądzenia losowego .

Dla uproszczenia załóżmy, że podstawową przestrzeń stanów można przedstawić jako nieskierowany nieważony graf nieważony. Kombinatoryczny Laplacian jest zdefiniowany jako $= (V, E)}$ $\ displaystyle$ operator ${\ displaystyle L = DA}$ , gdzie jest $diagonalną$ zwaną macierzą stopni i ${\ displaystyle A}$ jest macierzą sąsiedztwa .

Analiza widmowa operatora Laplace'a na wykresie polega na znalezieniu wartości własnych i funkcji własnych rozwiązujących równanie

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

gdzie $.$ $kombinatorycznym$ Laplacianem, $jest$ z wartością Tutaj termin „funkcja własna” jest używany do określenia tego, co tradycyjnie nazywa się wektorem własnym w algebrze liniowej, ponieważ wektory własne Laplaciana można naturalnie postrzegać jako funkcje, które odwzorowują każdy wierzchołek na liczbę rzeczywistą.

Kombinatoryczny Laplacian nie jest jedynym operatorem na grafach, z którego można wybierać. Inne możliwe operatory grafów obejmują:

${\ Displaystyle L _ {\ tekst {znormalizowany}} = ID ^ {-1/2} AD ^ {$ Laplacian
Losowy spacer ${\ displaystyle P = D ^ {-1} A}$

Budowa grafów na dyskretnej przestrzeni stanów

Dla skończonej przestrzeni stanów wykres wspomniany powyżej można po prostu skonstruować, badając połączenia między $stanami$ Niech $S_ {i}}$ ${\$ displaystyle będą dowolnymi dwoma stanami Następnie

{\ Displaystyle G_ {i, j} = {\ początek {przypadków} 1 i {\ tekst {jeśli}} S_ {i} \ leftrightarrow S_ {j} \\ 0&{\text{w przeciwnym razie}}\end{przypadki}}}

Należy zauważyć, że można to zrobić tylko wtedy, gdy przestrzeń stanów jest skończona i ma rozsądny rozmiar.

Budowa grafów na ciągłej lub dużej przestrzeni stanów

W przypadku ciągłej przestrzeni stanów lub po prostu bardzo dużej dyskretnej przestrzeni stanów konieczne jest próbkowanie z rozmaitości w przestrzeni stanów. $.$ konstruowanie wykresu na podstawie próbek Należy tutaj rozważyć kilka kwestii:

Jak wypróbować różnorodność.
- Losowy spacer lub eksploracja z przewodnikiem
Jak ustalić, czy należy połączyć dwie próbki

Aplikacja

Po wygenerowaniu PVF można je podłączyć do tradycyjnego frameworku aproksymacji funkcji. Jedną z takich metod jest przybliżenie metodą najmniejszych kwadratów.

Aproksymacja metodą najmniejszych kwadratów przy użyciu funkcji protowartości

Niech $}}$ ${\ Displaystyle \ Phi _ {G} = \ lewo \ {V_ {1} ^ {G}, \ kropki, V_ {k} ^ {G} \ prawo$ $będzie$ podstawowym zbiorem PVF, gdzie każdy $jest$ funkcją własną zdefiniowaną dla wszystkich na Niech ${\ displaystyle {\ widehat {V}} ^ {\ pi}}$ być funkcją wartości docelowej, która jest znana tylko dla podzbioru stanów. ${\ Displaystyle S_ {M} ^ {G} = \ lewo \ {s_ {1}, \ kropki ,s_{m}\right\}}$ .

Zdefiniuj macierz gramową

{\ Displaystyle K_ {G} = \ lewo (\ Phi _ {m} ^ {G} \ prawo) ^ {T} \ Phi _ {m} ^ {G}.}

Tutaj $.$ $_$ PVF _ Zatem każdy wpis macierzy gramowej jest

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

Współczynniki minimalizujące błąd najmniejszych kwadratów opisuje się następnie równaniem

{\ Displaystyle \ alfa = K_ {G} ^ {-1} \ lewo (\ Phi _ {M} ^ {G} \ prawo) ^ {T} {\ widehat {V}} ^ {\ pi}.}

Nieliniowe podejście metodą najmniejszych kwadratów jest możliwe poprzez użycie k PVF z największymi współczynnikami bezwzględnymi do obliczenia przybliżenia.

Zobacz też