It’s been a long time (AI tutorial 1)

Sporo czasu upłynęło od ostatniego razu. Po raz kolejny wznawiam bloga, tym razem mając konkretne cele. Blog ma mi towarzyszyć w moich zmaganiach na drodze do zostania wymiataczem w AI. Temat bardzo ciekawy, bardzo trudny, bardzo nęcący ale zawsze odstawiany przeze mnie na bok ze względu na różne wymówki. Wystarczy, w końcu coś pęka i człowiek zaczyna robić to co powinien zacząć już dawno. Każda kolejna rzecz opisana na blogu w celu raz usystematyzowania wiedzy, dwa posiadania notatek.

Na początek odświeżenie tego co już wiadomo.

Wyobraźmy sobie taką sytuację. Jest egzamin, jedni zdają inni nie zdają, wszystko w normie. Każdy jednak woli być w tym zbiorze studentów który zdał. A najlepiej było by wiedzieć czy się zdało jeszcze przed. Można wykorzystać dane historyczne aby spróbować przewidzieć przyszłość. Czy można to nazwać AI? IMO tak. Naturalne jest że wiele decyzji podejmujemy na postawie poprzednich doświadczeń. Niech komputer na podstawie tego co zdarzyło się wcześniej przewidzi przyszłość. Możemy to nazwać uczeniem maszynowym. Pewne dane są dostępne i zrozumiane. Przekazujemy je do programu, który na ich podstawie uczy się pewnych wzorców. Kiedy skończy podajemy nowe dane a on przekazuje przewidywany wynik. Brzmi nieźle.

Drawing1

Zacznijmy od czegoś prostego.

Mamy dostępne dane na temat zdobytych punktów z egzaminu oraz opuszczonych wykładów. Na tej podstawie spróbujmy przewidzieć jaki wynik uzyska ktoś kto był dokładnie na połowie wykładów.
Zobaczmy jak to wygląda na wykresie.

dd

Jak widać dane układają się mniej więcej wzdłuż pewnej linii. Spróbujmy ją naszkicować na oko.

łan

Widać że dla 50% obecności możemy oczekiwać wyniku w okolicach 5 punktów. No dobrze, ale jak komputer ma do tego dojść?

Regresja liniowa jednej zmiennej.

Podsumujmy co mamy do tej pory: zbiór par wartości (obecność, punkty). Szukamy pewnej funkcji liniowej która pozwoli przewidywać wynik. Postać ogólną, którą wszyscy znają wygląda tak:
y = ax + b
Dalej będę używał formy:
h_\theta(x) = \theta_0 + \theta_1 x

Potrzebujemy wyznaczyć dwa współczynniki \theta_0 i \theta_1 . Tym zajmie się tytułowy algorytm.

Aby stwierdzić czy rozwiązanie jest dobre zdefiniujmy sobie coś co pozwoli ocenić jego jakość. Taka funkcja musi sprawdzać jak bardzo rzeczywiste dane różnią się od przewidywanych. Najprościej będzie użyć sumy kwadratów różnic, innymi słowy metody najmniejszych kwadratów.

Dla pojedynczej pary wyrażenie będzie wyglądać tak:
(h_\theta(x) - y)^2
Podnosimy do kwadratu różnicę między tymi wartościami. Gratisowo pozbywamy się ew. wartości ujemnych.
Jak będzie to wyglądać dla całego zbioru danych?

\sum\limits_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2
Gdzie x^{(i)} i y^{(i)} oznaczają po prostu i-tego x i y, a m liczność zbioru z danymi.

Ostatecznie zapiszmy to jako średnią powyższych odchyleń:
J(\theta_0, \theta_1) = \frac{1}{m} \sum\limits_{i=1}^m \left ( h_\theta(x^{(i)}) - y^{(i)} \right )^2

Warto zauważyć, że h_\theta(x^{(i)}) to to samo co \theta_0 + \theta_1 x

Będziemy starali się tak manipulować parametrami \theta_0 i \theta_1 aby zminimalizować funkcję J i w efekcie uzyskać lepsze dopasowanie.

Minimalizacja

Pamiętajmy, że rozwiązanie problemu sprowadza się teraz do znalezienia minimum funkcji J.

Funkcja J jest dwuargumentowa. Do wyznaczenia minimum (niekoniecznie globalnego!!!) posłużymy się algorytmem gradientu prostego. Nazwa sugeruje że jest to prosta metoda i tak jest w istocie.

Pomysł jest następujący:
1. Wybierz punkt początkowy (wartości dla \theta_0 i \theta_1 ).
2. Rozejrzyj się dookoła gdzie możesz zejść w dół (i zejdź).
3. Powtarzaj tak długo aż znajdziesz optimum/skończy się czas/etc.

Krok 1 jest oczywisty. Zastanówmy się nad drugim. Aby zdecydować w którym kierunku iść, będziemy potrzebowali pochodnych cząstkowych (jak zmienia się funkcja w obecnym położeniu). Wyglądają one następująco:

\frac{\partial}{\partial \theta_0} J(\theta_0, \theta_1) = \frac{2}{m} \sum\limits_{i=1}^m \left (h_\theta \left (x^{(i)} \right ) - y^{(i)}\right)
\frac{\partial}{\partial \theta_1} J(\theta_0, \theta_1) = \frac{2}{m} \sum\limits_{i=1}^m \left (h_\theta \left (x^{(i)} \right ) - y^{(i)}\right) \cdot x^{(i)}

W jaki sposób pochodne mają nam pomóc? Aby zobaczyć jak to działa weźmy funkcję kwadratową.
y=x^2-2x+3
Jej pochodna
y'=2x-2
Weźmy punkt startowy x = 10 i poszukajmy minimum. Będzie nam potrzebny jeszcze współczynnik \alpha . O nim za chwilę, przyjmijmy że ma wartość \alpha=0.1

Pochodna w tym miejscu jest równa y'(10) = 18
Zmodyfikujmy x następująco:
x_{i+1} = x_i - \alpha \cdot 18 1iter
Przesunęliśmy się we właściwym kierunku!
Wykonajmy więcej iteracji.

10iter

Jak widać osiągnęliśmy optimum. Czym jest \alpha? Jest to współczynnik mówiący jak ostro mamy iść w kierunku rozwiązania. Im mniejszy tym więcej iteracji trzeba wykonać, im większy tym szybciej ale musimy uważać na zbyt dużą wartość. Ustawmy \alpha=1.2, 20 iteracji.

overshoot

Coś nie zagrało. Nad przyczyną polecam zastanowić się samemu.

OK, sprawdziliśmy że metoda działa, przełóżmy ją na dwie zmienne.
Rozumowanie jest identyczne, jedyne o czym musimy pamiętać to jednoczesna zmiana obu parametrów (liczymy krok dla \theta_0 oraz \theta_1 a dopiero potem zmieniamy wartości tych zmiennych).

Co zobaczymy po implementacji?

lech

Seems legit

 

Zobaczmy jak będzie wyglądał kod.

X = [10,9,8,7,6,5,4,3,2,1,0]
Y = [1,2,4,3,5,4,6,7,4,8,9]

m = len(X)
alpha = 0.01

Wprowadzamy dane, ustawiamy m oraz α.

def h(x, theta):
    return theta[0] + theta[1] * x


def J_partial0(theta):
    sum = 0
    for i in range(m):
        sum += h(X[i], theta) - Y[i]

return 2 * sum / m;

def J_partial1(theta):
    sum = 0
    for i in range(m):
        sum += (h(X[i], theta) - Y[i]) * X[i]

    return 2 * sum / m;

Definiujemy fukcję h oraz pochodne funckcji J.

def gradient_descent(startTheta):
    theta = startTheta
    for i in range(5000):
        d0 = J_partial0(theta)
        d1 = J_partial1(theta)
        theta[0] -= alpha * d0
        theta[1] -= alpha * d1

    return theta

Pamiętamy aby obliczyć d0 oraz d1 przed ich dodaniem do aktualnego wyniku.

Podsumowanie

To wszystko, metoda jest bardzo prosta ale to dopiero pierwszy krok. Następnym razem: co jeśli mamy dodatkowe dane i chcemy je uwzględnić w uczeniu.

Cały kod dostępny tutaj: https://gist.github.com/Xevaquor/e128c3c31c48dafd5766

DISCLAIMER: Używana notacja jest luźna, niekoniecznie musi być w pełni formalnie poprawna.

Reklamy

5 comments

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s