Inteligentne uczenie AI - optymalizacja bayesowska
Wraz z rozwojem sztucznej inteligencji pojawia się zapotrzebowanie na coraz bardziej złożone modele uczenia maszynowego. Chęć wyprzedzenia konkurencji oraz zainteresowanie jak największym stopniem automatyzacji procesów wymagają przy tym coraz większej skuteczności wdrażanych metod. Zbudowanie dobrego modelu nie jest jednak łatwym zadaniem. Pomijając cały trud związany z pozyskaniem oraz przygotowaniem danych, pozostaje jeszcze kwestia właściwego skonfigurowania algorytmu. Konfiguracja ta polega między innymi na wyborze odpowiednich hiperparametrów, czyli takich parametrów, których model nie jest w stanie nauczyć się samodzielnie na podstawie dostarczonych danych. Może to być na przykład liczba neuronów w jednej z warstw ukrytych sieci neuronowej. Odpowiedni dobór hiperparametrów wymaga znacznej wiedzy eksperckiej oraz wielu testów, gdyż każdy taki problem jest w pewnym stopniu wyjątkowy. Zwykle metoda prób i błędów nie jest niestety najbardziej wydajna, dlatego w ostatnich latach rozwijane są sposoby automatycznej optymalizacji wyboru hiperparametrów algorytmów uczenia maszynowego.
Najprostszym podejściem do tego zadania jest przeszukiwanie po siatce (z ang. grid search) oraz przeszukiwanie losowe. Pierwszy sposób polega na sprawdzeniu wszystkich możliwych kombinacji wskazanych wartości hiperparametrów. Drugi natomiast, jak sama nazwa wskazuje, opiera się na wybieraniu losowych wartości określoną liczbę razy. W obu sytuacjach zwracana jest konfiguracja hiperparametrów, która charakteryzowała się najkorzystniejszym wynikiem w wybranej metryce błędu. Metody te, choć bywają skuteczne, nie są zbyt wydajne. Sposób wybierania kolejnych sprawdzanych kombinacji jest arbitralny, przez co wymagają one dużej liczby iteracji dla osiągnięcia dobrych efektów. Szczególnie źle wypada tutaj przeszukiwanie po siatce, gdzie liczba możliwych konfiguracji rośnie wykładniczo wraz z rozszerzaniem przestrzeni przeszukiwania.
Takie procesy są kosztowne obliczeniowo. Trening pojedynczego modelu uczenia maszynowego potrafi zająć bardzo dużo czasu, dlatego optymalizacja hiperparametrów wymagająca setek powtórzeń często okazuje się nieosiągalna. W sytuacjach biznesowych rzadko kiedy można pozwolić sobie na poświęcenie bliżej nieokreślonej ilości czasu na wypróbowanie kilkuset konfiguracji hiperparametrów w poszukiwaniu tej najlepszej. Zastosowanie przy tym, czasami wręcz niezbędnej, walidacji krzyżowej dodatkowo potęguje problem. Dlatego tak ważne jest ograniczenie liczby wymaganych iteracji do minimum. Potrzebny jest więc algorytm, który będzie przeszukiwał jedynie najbardziej obiecujące punkty – w ten właśnie sposób działa optymalizacja bayesowska. Przed opisaniem jej działania warto poznać podstawy teoretyczne, na których się opiera.
Matematyka na pochmurne dni
Wyobraźmy sobie sytuację, w której przed wyjściem rano do pracy zauważamy chmury za oknem. W naturalny sposób możemy spodziewać się, że w trakcie dnia zacznie padać deszcz. Z drugiej jednak strony wiemy, że w naszym mieście wiele poranków rozpoczyna się pochmurnie, a mimo to deszcz pada dość rzadko. Jak dużą możemy mieć pewność, że ten dzień będzie deszczowy?
Problemy tego rodzaju związane są z prawdopodobieństwem warunkowym. Pojęciem tym określamy prawdopodobieństwo wystąpienia pewnego zdarzenia A pod warunkiem, że wystąpiło zdarzenie B, czyli P(A|B). W przypadku naszego pochmurnego poranka będzie to P(Deszcz|Chmury), a więc prawdopodobieństwo opadów pod warunkiem zachmurzonego nieba rano. Obliczenie takiej wartości może okazać się bardzo proste dzięki twierdzeniu Bayesa.
Twierdzenie Bayesa z pomocą
Twierdzenie to pokazuje, w jaki sposób przedstawić można prawdopodobieństwo warunkowe przy pomocy prawdopodobieństwa występowania poszczególnych zdarzeń. Oprócz P(A) oraz P(B), potrzebujemy jeszcze prawdopodobieństwa występowania B, jeśli wystąpiło A. Formalnie twierdzenie zapisać można jako:
To niezwykle proste równanie jest jedną z podstaw statystyki matematycznej [1].
Co właściwie oznacza? Mając pewną wiedzę o zdarzeniach A oraz B, możemy stwierdzić z jakim prawdopodobieństwem zajdzie A, jeśli właśnie zaobserwowaliśmy B. Wracając do opisanego problemu, załóżmy, że poczyniliśmy kilka dodatkowych obserwacji meteorologicznych. Deszcz w naszym mieście pada średnio zaledwie 6 razy w miesiącu, natomiast aż połowa dni rozpoczyna się pochmurnie. Dodatkowo wiemy, że zwykle tylko 4 z tych 6 deszczowych dni są zwiastowane przez poranne chmury. W ten sposób możemy obliczyć prawdopodobieństwo deszczu (P(Deszcz) = 6/30), pochmurnego poranka (P(Chmury) = 1/2) oraz prawdopodobieństwo, że deszczowy dzień rozpoczął się chmurami (P(Chmury|Deszcz) = 4/6). Podstawiając do wzoru z twierdzenia Bayesa otrzymujemy:
Szukane prawdopodobieństwo wynosi więc 26,7%. Jest to bardzo prosty przykład wykorzystania wiedzy a priori (prawa część równania) do określenia prawdopodobieństwa wystąpienia jakiegoś zjawiska.
Idź na całość!
Ciekawym zastosowaniem przytoczonego twierdzenia jest problem zainspirowany popularnym w Stanach Zjednoczonych teleturniejem Let’s Make A Deal. W Polsce znacznie bardziej rozpoznawana jest emitowana w latach 1997-2001 adaptacja programu – Idź na całość. Wyobraźmy sobie sytuację, w której uczestnik zabawy staje przed wyborem jednej z trzech „bramek”. Dwie z nich są puste, natomiast trzecia ukrywa dużą nagrodę. Gracz wybiera swoją bramkę w ciemno. Następnie prowadzący, wiedząc za którą z nich kryje się nagroda, otwiera jedną pustą z pozostałych bramek. W grze zostają więc już tylko dwie zakryte bramki. Uczestnik dostaje wtedy propozycję: może zostać przy swoim początkowym wyborze, albo zaryzykować i zmienić bramkę. Jaką strategię powinien przyjąć, aby zwiększyć swoje szanse na zwycięstwo?
Wbrew intuicji, prawdopodobieństwo wygranej w każdej z pozostałych bramek nie wynosi 50%. Aby znaleźć wyjaśnienie tego, być może zaskakującego, stwierdzenia, ponownie możemy posłużyć się twierdzeniem Bayesa. Przyjmijmy, że do wyboru były bramki A, B oraz C. Gracz zdecydował się na pierwszą z nich, natomiast prowadzący odsłonił C, pokazując, że jest pusta. Oznaczmy to zdarzenie jako (Hc). Niech (Wb) określa sytuację, w której nagroda jest w bramce niewybranej przez gracza (w tym przypadku w B). Szukamy prawdopodobieństwa, że wygrana czeka w B, pod warunkiem, że prowadzący odsłonił C:
Nagroda może znajdować się w dowolnej z trzech bramek, zatem (P(Wb) = 1/3). Prowadzący odsłania jedną z bramek niewybranych przez gracza, dlatego (P(Hc) = 1/2). Zauważmy też, że jeśli nagroda znajduje się w B, to prowadzący nie ma wyboru w odkrywaniu zawartości pozostałych bramek – musi odsłonić C. Stąd (P(Hc|Wb) = 1). Po podstawieniu do wzoru:
Analogicznie szansa na wygranie, jeśli gracz pozostałby przy początkowym wyborze, wynosi 1 do 3. A zatem strategia zmiany bramki dwukrotnie zwiększa prawdopodobieństwo wygranej! Problem został opisany w literaturze dziesiątki razy i znany jest jako paradoks Monty’ego Halla od nazwiska prowadzącego oryginalną edycję teleturnieju [2].
Optymalizacja bayesowska
Jak nietrudno się domyślić, algorytm bayesowski opiera się właśnie na twierdzeniu Bayesa. Jego działanie polega na próbach oszacowania optymalizowanej funkcji korzystając z poznanych wcześniej wartości. W przypadku modeli uczenia maszynowego dziedziną tej funkcji jest przestrzeń hiperparametrów, natomiast zbiorem wartości pewna przyjęta metryka błędu. Przekładając to bezpośrednio na twierdzenie Bayesa, szukamy odpowiedzi na pytanie jaka w punkcie xₙ będzie wartość funkcji:
jeśli znamy jej wartość w punktach: x₁, ..., xₙ₋₁.
Na potrzeby wizualizacji działania mechanizmu, przeprowadzimy optymalizację prostej funkcji jednej zmiennej. Algorytm składa się z dwóch funkcji pomocniczych. Są one dobrane tak, aby w stosunku do funkcji celu f były znacznie mniej kosztowne obliczeniowo oraz łatwe w optymalizacji prostymi sposobami.
Pierwszą z nich jest funkcja zastępcza, której zadaniem jest określenie potencjalnych wartości f w punktach kandydujących. W tym celu często wykorzystuje się regresję opartą na procesach gaussowskich. Na podstawie poznanych punktów wyznaczany jest prawdopodobny obszar, w którym może przebiegać funkcja. Na rysunku 1. możemy zaobserwować, jak funkcja pomocnicza oszacowała funkcję f z jedną zmienną po trzech iteracjach algorytmu. Czarne punkty prezentują oszacowane wcześniej wartości f, natomiast niebieska linia wyznacza średnią z możliwych przebiegów. Zacieniony obszar to przedział ufności, który wskazuje jak pewni możemy być naszego oszacowania w każdym punkcie. Im szerszy przedział ufności, tym mniejsza pewność na temat tego, jak wygląda f w danym miejscu. Zauważmy, że niepewność jest tym większa, im dalej jesteśmy od poznanych już punktów.
Drugim niezbędnym narzędziem jest funkcja akwizycji. To do niej należy wytypowanie punktu o największym potencjale, który następnie zostanie poddany kosztownej ewaluacji. Popularnym wyborem jest tutaj wartość oczekiwanej poprawy f. Jest to metoda, która bierze pod uwagę jednocześnie oszacowaną średnią oraz niepewność, dzięki czemu algorytm nie boi się „ryzykować” w przeszukiwaniu nieznanych obszarów. W tym przypadku największej możliwej poprawy możemy spodziewać się w punkcie xₙ = −0,5, dla którego zostanie obliczona wartość f. Oszacowanie funkcji zastępczej zostanie zaktualizowane, a cały proces powtarza się aż do osiągnięcia określonego warunku stopu. Przebieg kilku takich iteracji przedstawiony został na rysunku 3.
Rzeczywisty przebieg optymalizowanej funkcji wraz ze znalezionym optimum przedstawiony jest na rysunku 4. Algorytm w zaledwie kilku iteracjach był w stanie znaleźć globalne maksimum funkcji, unikając przy tym wpadania w optimum lokalne.
Nie jest to szczególnie wymagający przykład, jednak dobrze obrazuje mechanizm działania optymalizacji bayesowskiej. Jej niewątpliwą zaletą jest względnie mała w stosunku do innych metod liczba iteracji wymagana do osiągnięcia satysfakcjonujących wyników. Dodatkowo metoda ta dobrze radzi sobie w sytuacji, gdzie występuje wiele optimów lokalnych [3]. Minusem może być relatywnie trudna implementacja rozwiązania. Z pomocą przychodzą jednak dynamicznie rozwijane biblioteki open source, takie jak Spearmint [4], Hyperopt [5] czy SMAC [6]. Oczywiście optymalizacja hiperparametrów nie jest jedynym zastosowaniem algorytmu. Z powodzeniem jest on wykorzystywany w takich obszarach jak systemy rekomendacyjne, robotyka oraz grafika komputerowa [7].
Adrian Stworzyjanek
Junior Data Scientist
adrian.stworzyjanek@bitpeak.pl
Bibliografia
[1] „What Is Bayes’ Theorem? A Friendly Introduction”, Probabilistic World, luty 22, 2016. https://www.probabilisticworld.com/what-is-bayes-theorem/ (udostępniono lip. 15, 2020).
[2] J. Rosenhouse, „The Monty Hall problem. The remarkable story of math’s most contentious brain teaser”, sty. 2009.
[3] E. Brochu, V. M. Cora, i N. de Freitas, „A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning”, arXiv:1012.2599 [cs], grudz. 2010
[4] https://github.com/HIPS/Spearmint
[5] https://github.com/hyperopt/hyperopt
[6] https://github.com/automl/SMAC3
[7] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, i N. de Freitas, „Taking the Human Out of the Loop: A Review of Bayesian Optimization”, Proc. IEEE, t. 104, nr 1, s. 148–175, sty. 2016, doi: 10.1109/JPROC.2015.2494218.