Uczenie maszynowe i sztuczne sieci neuronowe/Wykład 11

Uczenie ze wzmocnieniem

W dotychczasowych wykładach zajmowaliśmy się dwoma skrajnymi typami uczenia: uczenie z nadzorem i bez nadzoru. W pierwszym typie ciąg uczący zawiera wektory wejściowe i pożądane wartości wyjściowe. Na podstawie takiego zbioru możliwe jest bezpośrednie policzenie błędu popełnionego przez algorytm uczący i wyliczenie konkretnych poprawek. Drugą skrajnością były algorytmy analizy skupień bazujące na korelacjach między wejściem i wyjściem oraz na strukturze danych wejściowych.

W tym wykładzie zajmiemy się sytuacją pośrednią. Dla każdego wejścia nie znamy co prawda prawidłowej wartości wyjścia, ale umiemy powiedzieć czy było ono dobre czy złe. Przypomina to trochę uczenie psa aportowania. Nie da się psu wytłumaczyć jak ma to zrobić, jedynie w wypadku powodzenia pies dostaje pochwałę/nagrodę a w przypadku niepowodzenia nic. Podobnie w uczeniu ze wzmocnieniem będziemy jedynie wiedzieli kiedy algorytm nagrodzić (będziemy do tego używać funkcji nagrody) a kiedy karać.

Specyficznym problemem jest tu przypisanie kary za błąd. Zwykle w zadaniach których rozwiązania chcielibyśmy nauczyć maszynę występuje wiele etapów i nie jest do końca jasne który z nich przyczynił się do ostatecznego błędu. Można tu jako przykład rozważyć grę w szachy. Jeśli po 60 posunięciach partia się kończy naszą przegraną to nie jest jasne, który z naszych ruchów był nieprawidłowy.

Algorytmy tego typu znajdują bardzo wiele praktycznych zastosowań np: algorytmy do gier strategicznych, sterowanie robotami, optymalizacja przesyłania danych w sieciach komórkowych, efektywne indeksowanie stron internetowych itp. Zaczniemy od omówienia procesu decyzyjnego Markowa (ang. Markov decision process MDP), który dostarcza formalizmu do opisu uczenia ze wzmocnieniem.

Proces decyzyjny Markowa

Aby mówić o procesie decyzyjnym Markowa musimy zdefiniować następujący zestaw (krotkę): [math](S,A,\lbrace P_{sa}\rbrace ,\gamma ,R)[/math] gdzie:

• [math]S[/math] jest zbiorem możliwych stanów, w jakich może znajdować się rozważany układ.
• [math]A[/math] to zbiór możliwych akcji
• [math]P_{s,a}[/math] to rozkład prawdopodobieństwa przejścia z bieżącego stanu do każdego z możliwych stanów, tak, że [math]P_{s,a_{i}}(s^{\prime })[/math] określa prawdopodobieństwo z jakim układ znajdujący się w stanie [math]s[/math] po wyborze akcji [math]a_{i}[/math] znajdzie się w stanie [math]s^{\prime }[/math].
• [math]\gamma [/math] to współczynnik o wartości [math][0,1)[/math]
• [math]R: S\times A \mapsto \mathcal {R}[/math] to funkcja nagrody.

Aby "uruchomić" MDP potrzebna jest strategia, czyli mechanizm wybierania akcji. Formalnie strategia [math]\pi : S \mapsto A[/math] to funkcja, która mapuje stany na akcje. Czyli jeśli znajdujemy się w stanie [math]s[/math] to akcje wybieramy tak: [math] a= \pi (s)[/math].

Działanie MDP można opisać następująco: Początkowo układ znajduje się w stanie [math]s_{0}[/math]. Zgodnie ze strategią [math]\pi (s_{0})[/math] wybierana jest akcja [math]a_{0}[/math]. W sposób losowy, zgodnie z rozkładem [math]P_{s_{0},a_{0}}[/math] akcja [math]a_{0}[/math] przenosi układ do stanu [math]s_{1}[/math]. Następnie strategia [math]\pi (s_{1})[/math] decyduje jaką akcję [math]a_{1}[/math] wykonamy i z prawdopodobieństwem [math]P_{s_{1},a_{1}}[/math] przejdziemy do stanu [math]s_{2}[/math], itd. Na obrazku wygląda to tak:

@=0.5cm s0 [r]a0 s1 [r]a1 s2 [r]a2 s3[r]a3 …

Aby te pojęcia nabrały znaczenia rozważmy konkretny przykład. Mamy robota, "żyjącego" w świecie złożonym z 12 pól takim jak na poniższym rysunku (RYS).

Zajmowanie przez robota pola o konkretnych współrzędnych to jego stan, np. jeśli robot znajduje się w lewym górnym rogu to jest w stanie [math]s = (1,3)[/math]. Jego zbiór akcji to przemieszczenie się o jedną pozycję w jednym z czterech kierunków: [math]A = \lbrace N,E,S,W\rbrace [/math]. Robot nie może wejść na czarne pole, ani przeniknąć przez ściany. Próba podjęcia takiej niemożliwej akcji skutkuje tym, że robot pozostaje w dotychczasowym stanie. Chcielibyśmy, aby robot uruchomiony w takim świecie dotarł do stanu [math](4,3)[/math] i jak tylko to możliwe unikał stanu [math](4,2)[/math]. Przebywanie w każdym ze stanów związane jest z funkcją nagrody, zaznaczoną kolorami. Dla ustalenia uwagi weźmy funkcję nagrody taką, że stan [math](4,3)[/math] ma nagrodę [math]R((4,3)) = +1[/math], [math]R((4,2)) = -1[/math], pozostałe stany mają wartość [math]R = -0.02[/math]. Widać, że możemy nadawać funkcji nagrody wartości dodatnie (za przebywanie systemu w stanach, które uznajemy za korzystne) lub ujemne (w stanach mniej korzystnych). Dodatkowo załóżmy, że dynamika naszego robota jest stochastyczna. Innymi słowy ruchy naszego robota nie są idealnie precyzyjne, np. jeśli dostanie polecenie [math]N[/math] to przemieści się do góry z prawdopodobieństwem powiedzmy 0.8, na lewo z prawdopodobieństwem 0.1 i na prawo z prawdopodobieństwem 0.1.

Przy takiej dynamice rozkład prawdopodobieństwa przejścia między stanami może wyglądać np. tak:

[math]P_{(3,1),N}(3,2) = 0.8[/math] (Notacja ta oznacza prawdopodobieństwo przejścia ze stanu (3,1) do (3,2) po wybraniu akcji [math]N[/math])

[math]P_{(3,1),N}(2,1) = 0.1[/math]

[math]P_{(3,1),N}(4,1) = 0.1[/math]

[math]P_{(3,1),N}(3,3) = 0[/math]

[math]\vdots [/math]

Rozważmy teraz przykładowe działanie naszego robota, przyjmując strategię taką jak na poniższym rysunku. (RYS)

E	E	E	+1
N	•	N	-1
N	W	W	W

• Umieszczamy go w chwili [math]t_{0}[/math] w jakimś stanie [math]s_{0}[/math] (tzn. na którymś konkretnym polu)

• Wybieramy akcję [math]a_{0}[/math]

• W zależności od [math]s_{0}[/math] i [math]a_{0}[/math] robot znajdzie się w stanie [math]s_{1}[/math] (Stan [math]s_{1}[/math] jest losowany z rozkładu prawdopodobieństwa [math]P_{s_{0},a_{0}}[/math] ; możemy to zapisać [math]s_{1} \sim P_{s_{0},a_{0}}[/math])

• Wybieramy akcję [math]a_{1}[/math]

• Losujemy stan [math]s_{2} \sim P_{s_{1},a_{1}}[/math]

• [math]\dots [/math]

Z przebyciem konkretnej sekwencji stanów związany jest całkowity zysk, który może być obliczony z funkcji nagrody w następujący sposób:

[math]Z = R(s_{0}) + \gamma R(s_{1})+ \gamma ^{2} R(s_{2}) + \dots [/math]

Widzimy że współczynnik [math]\gamma [/math] odpowiadający krokowi [math]k[/math] występuje w potędze [math]k[/math]. Ponieważ jest on dodatni i mniejszy niż 1 oznacza to, że na wartość oczekiwaną zysku mają największy wpływ wartości funkcji nagrody w najwcześniejszych korkach. Możemy o tym myśleć w analogii do pieniędzy: Dobrze ulokowane pieniądze przynoszą tym większy zysk im wcześniej je ulokowaliśmy.

Naszym celem w uczeniu ze wzmocnieniem jest takie wybieranie akcji (znalezienie takiej strategii) aby zmaksymalizować wartość oczekiwaną całkowitego zysku:

[math]E [Z] =E [R(s_{0}) + \gamma R(s_{1})+ \gamma ^{2} R(s_{2}) + \dots ][/math]

Jak wyznaczyć optymalną strategię?

Pora wprowadzić pojęcie funkcji wartościującej, która posłuży do oceniania strategii: Funkcja wartościująca dla danej strategii [math]\pi [/math] jest to wartość oczekiwana całkowitego zysku dla przypadku gdy startujemy ze stanu [math]s_{0}[/math] i podejmujemy akcje zgodnie ze strategią [math]\pi [/math]. Można to zapisać następująco:

[math] V^{\pi }(s) = E[R(s_{0}) + \gamma R(s_{1})+ \gamma ^{2} R(s_{2}) + \dots | s_{0}=s, \pi ] [/math]

Dla przykładu policzmy tą funkcje dla konkretnej strategii: Strategia:

E	E	E	+1
S	•	E	-1
E	E	N	N

Funkcja wartościująca dla tej strategii:

0.52	0.73	0.77	+1
-0.90	•	-0.82	-1
-0.88	-0.87	-0.85	-1

Równanie %i 1 można przepisać w postaci:

[math] V^{\pi }(s) = E[R(s_{0}) + \gamma \left( R(s_{1})+ \gamma ^{1} R(s_{2}) + \gamma ^{2} R(s_{3})+ \dots \right) | s_{0}=s, \pi ] [/math]

Zauważmy, że wyrażenie w nawiasie: [math] R(s_{1})+ \gamma ^{1} R(s_{2}) + \gamma ^{2} R(s_{3})+ \dots [/math] to funkcja wartościująca strategi dla stanu [math]s_{1}[/math]: [math]V^{\pi }(s_{1})[/math].

Przechodząc do notacji: [math]s_{0} \rightarrow s[/math] i [math]s_{1} \rightarrow s^{\prime }[/math] możemy funkcję wartościującą strategii wyrazić w sposób rekurencyjny:

[math] V^{\pi }(s) = E[R(s) + \gamma V^{\pi }(s^{\prime }) | s_{0}=s, \pi ] [/math]

W tym wyrażeniu [math]s[/math] jest już ustalone więc [math]E[R(s)] = R(s)[/math] natomiast [math]s^{\prime }[/math] jest zmienną losową pochodzącą z rozkładu [math]P_{s, \pi (s)}[/math] więc [math]E[V^{\pi }(s^{\prime }) ] = \sum _{s^{\prime }} P_{s, \pi (s)}(s^{\prime }) V^{\pi }(s^{\prime }) [/math]. Zbierając razem te obserwacje i podstawiając je do równania (%i 3) otrzymujemy tzw. równanie Bellmana:

[math]V^{\pi }(s) = R(s) +\gamma \sum _{s^{\prime } \in S} P_{s,\pi (s)}(s^{\prime }) V^{\pi }(s^{\prime })[/math]

W szczególności dla MDP o skończonej ilości stanów [math]N[/math] można napisać równanie Bellmana dla każdego stanu [math]s[/math]. Otrzymamy wtedy układ [math]N[/math] równań liniowych z [math]N[/math] niewiadomymi ([math]V^{\pi }(s)[/math]) , który można łatwo rozwiązać. Popatrzmy na przykład z robotem. Weźmy stan [math](3,1)[/math] i strategię [math]\pi ((3,1)) = N[/math]. Równanie Bellmana dla tego stanu to:

[math]V^{\pi }\left( (3,1) \right) = R((3,1)) + \gamma [ 0.8 V^{\pi }((3,2)) +0.1 V^{\pi }((4,1)) +0.1 V^{\pi }((2,1)) ][/math]

Dla każdego z 11 stanów można napisać takie równanie. Otrzymamy 11 równań zawierających 11 niewiadomych [math]V^{\pi }(i,j)[/math].

Zdefiniujmy optymalną funkcję wartościującą strategi jako:

[math] V^{*}(s) = \max _{\pi } V^{\pi }(s) [/math]

Innymi słowy jest to największa możliwa suma nagród (ważonych przez [math]\gamma [/math]) przy pomocy najlepszej strategii.

Można napisać równanie Bellmana dla [math]V^{*}(s)[/math]:

[math]V^{*}(s) = R(s) +\max _{a}\gamma \sum _{s^{\prime } \in S} P_{s,a}(s^{\prime }) V^{*}(s^{\prime })[/math]

Pierwszy człon to natychmiastowa nagroda. W drugim członie suma wyraża wartość oczekiwaną zysku jeśli wybralibyśmy akcję [math]a[/math]. Wartość ta jest maksymalizowana po [math]a[/math].

To prowadzi do definicji strategii [math]\pi ^{*}(s)[/math], czyli takiej strategii, która maksymalizuje zysk:

[math] \pi ^{*}(s) = \arg \max _{a} \sum _{s^{\prime }} P_{sa}(s^{\prime }) V^{*}(s^{\prime }) [/math]

W definicji tej nie musimy już uwzględniać [math]\gamma [/math] bo nie ma ona znaczenia dla operatora [math]\arg \max [/math]. Taka definicja powoduje, że akcje podejmowane zgodnie ze strategią [math]\pi ^{*}[/math] prowadzą do maksymalizacji drugiego członu w równaniu Bellmana na [math]V^{*}[/math]. W tym sensie strategia [math]\pi ^{*}[/math] jest strategią optymalną. Zauważmy, że [math]\pi ^{*}(s)[/math] jest strategią optymalną bez względu na to, z którego stanu uruchamiany jest proces.

Algorytm iteracji funkcji wartościującej

Powyższe definicje nie dają niestety przepisu jak obliczyć [math]\pi ^{*}[/math]. Właściwe algorytmy przedstawione są poniżej. Zauważmy, że gdybyśmy znali [math]V^{*}[/math] to można by je podstawić do (%i 4) aby wyznaczyć [math]\pi ^{*}[/math]. Zatem pierwszy algorytm, który prowadzi do wyznaczenia optymalnej strategi to: iteracja funkcji wartościującej:

1. inicjuj dla każdego [math]s[/math]: [math]V(s) = 0[/math] (wypełniamy tablicę V zerami)

2. Powtarzaj aż zbiegniesz: {

dla każdego stanu [math]s[/math]

[math]V(s) = R(s) + \max _{a} \gamma \sum _{s^{\prime }} P_{sa}(s^{\prime }) V(s^{\prime }) [/math]

}

Tak iterowane [math]V(s) \rightarrow V^{*}(s)[/math]

W algorytmie tym można zastosować uaktualnianie synchroniczne - wtedy najpierw obliczamy wszystkie prawe strony, wyniki obliczeń przechowując w zmiennej tymczasowej i dopiero po przebiegnięciu pętlą przez wszystkie stany następuje przypisanie uaktualniające. Druga możliwość to uaktualnianie asynchroniczne, tzn. w każdym kroku wybieramy jeden stan i uaktualniamy [math]V(s)[/math] dla tego stanu. W kolejnym kroku do obliczeń używamy już tego uaktualnionego [math]V[/math]. Algorytm asynchroniczny jest zwykle nieco szybciej zbieżny niż synchroniczny. Po wyznaczeniu [math]V^{*}[/math] można go podstawić do równania %i 4 i wyznaczyć optymalną strategię.

Stosując ten algorytm do naszego przykładu można otrzymać np. taka funkcję wartościującą [math]V^{*}[/math]:

0.86	0.90	0.93	+1
0.82	•	0.69	-1
0.78	0.73	0.71	0.49

Podstawiając do równania na [math]\pi ^{*}[/math] dostajemy, przykładowo dla stanu s= (3,1): Dla akcji W:

[math]\sum _{s^{\prime }} P_{sa}(s^{\prime })V^{*}(s^{\prime }) = 0.8\cdot 0.73 + 0.1\cdot 0.69 + 0.1\cdot 0.71 = 0.724 [/math]

Dla akcji N:

[math]\sum _{s^{\prime }} P_{sa}(s^{\prime })V^{*}(s^{\prime }) = 0.8\cdot 0.69 + 0.1\cdot 0.73 + 0.1\cdot 0.49 = 0.674 [/math]

Dla akcji E:

[math]\sum _{s^{\prime }} P_{sa}(s^{\prime })V^{*}(s^{\prime }) = 0.8\cdot 0.49 + 0.1\cdot 0.69 + 0.1\cdot 0.71 = 0.532 [/math]

Dla akcji S:

[math]\sum _{s^{\prime }} P_{sa}(s^{\prime })V^{*}(s^{\prime }) = 0.8\cdot 0.71 + 0.1\cdot 0.73 + 0.1\cdot 0.49 = 0.690 [/math]

Zatem dla tego stanu wybrana byłaby akcja W. Analogiczne obliczenia trzeba przeprowadzić dla pozostałych stanów. Wyniki końcowe prezentuje poniższa tabela.

E	E	E	+1
N	•	N	-1
N	W	W	W

Algorytm iteracji strategii

Poniżej zaprezentowany jest algorytm iteracji strategii.

1. inicjujemy [math]\pi [/math] w sposób losowy.
2. Powtarzaj, aż zbiegniesz: { rozwiąż równania Bellmana dla aktualnej strategii (dla procesów o bardzo dużej ilości stanów może to być nieefektywne):

   [math]V = V^{\pi }[/math]

   Następnie oblicz lepsze [math]\pi [/math]:

   [math]\pi (s) = \arg \max _{a} \sum _{s^{\prime }}P_{sa}(s^{\prime }) V(s^{\prime })[/math]

   }

Okazuje się, że powyższa iteracja daje [math]V \rightarrow V^{*}[/math] zaś [math]\pi \rightarrow \pi ^{*}[/math].

Dla małych i średnich problemów MDP iteracja strategii jest szybko zbieżna, ale dla dużych problemów staje się kosztowna obliczeniowo.

Algorytm aktualizacji funkcji Q

Optymalną strategię można też wyznaczyć wprowadzając funkcje jakości [math]Q[/math] (quality). Funkcja [math]Q[/math] zwraca jakość dla kombinacji stan-akcja:

[math]Q: S \times A \to \mathbb{R}[/math] .

Jakość ta mierzona jest przez oczekiwaną wartość całkowitej nagrody za wykonanie danej akcji [math]a[/math] w stanie [math]s[/math]. Czyli dla optymalnej funkcji [math]Q^*[/math] i [math]V^*[/math] zachodzi związek:

[math]V^*(s) = \max_a Q^*(s,a) [/math]

Najlepszą strategią jest zatem wybieranie akcji [math]\arg \max_a Q^*(s,a) [/math]:

[math]\pi^*(s) = \arg \max_a Q^*(s,a) [/math].

Funkcję [math]Q[/math] można znaleźć poprzez aktualizacje ważoną średnią dotychczasowej wartości i nowej informacji: iteracja funkcji Q:

1. inicjuj dla każdego [math]s[/math]: [math]Q(s,a) = 0[/math] (wypełniamy tablicę Q zerami)

2. Powtarzaj aż zbiegniesz: {

• Robot ustawiany jest w losowej pozycji.
• Przejdź epizod:
  • w każdej kolejnej chwili czasu [math]t[/math] robot wybiera akcję [math]a_t[/math],
  • dostaje nagrodę [math]R_t[/math],
  • przechodzi do nowego stanu [math]s_{t+1}[/math] ( to może zależeć od poprzedniego stanu [math]s_t[/math] i wybranej akcji),
  • [math]Q[/math] jest uaktualniane:

[math]Q(s_{t},a_{t}) := (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\textrm{ stara~wartosc}} + \alpha \cdot \overbrace{\bigg( R_{t} +{\gamma} \cdot \underbrace{\max_{a}Q(s_{t+1}, a)}_{\textrm{ estymata~optymalnej~przyszlej~wartosci}} \bigg) }^{\textrm{nowa~informacja~o~wartości~pary } (s_t,a_t)}[/math],

• • gdzie [math]R_{t}[/math] nagroda w bieżącym stanie [math]s_t[/math], i [math]\alpha[/math] jest prędkością uczenia ([math]0 \lt \alpha \le 1[/math]).
  • Epizod nauki kończy się gdy [math]s_{t+1}[/math] jest stanem końcowym.

}

Estymowanie modelu dla MDP

Na początku powiedzieliśmy, że MDP jest określony przez podanie następującej krotki: [math](S,A,\lbrace P_{sa}\rbrace ,\gamma ,R)[/math].

Stany i możliwe akcje zwykle wynikają w sposób naturalny z rozważanego problemu. [math]\gamma [/math] i [math]R[/math] wybieramy sami. Najtrudniejsze do wymyślenia ad hoc są prawdopodobieństwa przejść. Można jednak wyestymować je z danych (przez obserwację wielu realizacji procesu). Używamy wtedy estymatora największej wiarygodności, tzn:

[math]P_{sa}(s^{\prime }) = \frac{\#\text{ kiedy wybrano akcje }a\text{ w stanie }s\text{ i otrzymano stan }s^{\prime }}{\#\text{ kiedy wybrano akcję }a\text{ w stanie }s}[/math]

Zatem dla MDP o nieznanych prawdopodobieństwach przejść można zastosować następujący algorytm:

1. inicjalizuj [math]\pi [/math] losowo
2. powtarzaj aż zbiegniesz:
   1. Wykonaj strategię [math]\pi [/math] w MDP dla pewnej liczby prób.
   2. Na podstawie zaobserwowanych sekwencji stanów estymuj [math]P_{sa}[/math]
   3. zastosuj algorytm iteracji funkcji wartościującej aby oszacować [math]V[/math]
   4. Uaktualnij [math]\pi [/math]

   
   

W powyższym zastosowaniu algorytm iteracji funkcji wartościującej można zmodyfikować tak, aby nie zaczynał on za każdym razem inicjalizacji od [math]V(s) = 0[/math], ale od [math]V[/math] które uzyskano w poprzednim kroku zewnętrznej pętli.