Perceptron

Załóżmy, że dane są liniowo separowalne (da się prostą oddzielić klasę od klasy). Będzie chodziło nam o to, żeby znaleźć prostą oddzielającą klasy.

Wagi - tak będziemy nazywać współczynniki \(w = (w_0, w_1, w_2)\) w równaniu prostej: \(w_0 + w_1 x_1 + w_2 x_2 = 0\). Do klasy \(1\) będziemy zaliczać takie punkty \((x_1, x_2)\), że \(w_0 + w_1 x_1 + w_2 x_2 \geq 0\) (po prostu wybieramy sobie stronę prostej, po której będzie klasa \(1\)).

Zaczynamy od losowych wag (czyli losujemy prostą, która miałaby rozdzielać klasy).

Będziemy powtarzać procedurę co najwyżej maxiter razy. Każde powtórzenie będzie się składać z \(n\) kroków (\(n\) - liczba obserwacji). Poniżej omówimy jedno powtórzenie i \(i\)-ty krok.

Krok \(i\)-ty:

• weź \(i\)-tą obserwację \((y_i, x_{i,1}, x_{i,2})\).
• dokonaj predykcji na podstawie aktualnych wag, tzn. jeśli \(w_0 + w_1 x_{i,1} + w_2 x_{i,2} \geq 0\), to \(\hat{y}_i=1\), w przeciwnym wypadku \(\hat{y}_i=0\).
• niech \(e_i = y_i - \hat{y}_i\) (możliwe wartości to \(-1, 0, 1\); jeśli poprawna klasyfikacja to \(0\), jeśli nie, to w zależności od tego, czy \(y_i=0\) czy \(y_i=1\), to mamy wartości \(-1, 1\))
• aktualizujemy wagi \(w_{nowe} = w_{stare} + \alpha e_i \cdot (1, x_{i,1}, x_{i,2})\) (zauważmy, że jeśli \(e_i=0\) to nic nie robimy). Aktualizacja polega na tym, że przekręcamy prostą tak, żeby \(i\)-ta obserwacja była bliżej poprawnej klasy. Parametr \(\alpha\) kontroluje, jak bardzo chcemy przekręcać
• opcjonalnie można znormalizować wagi

Po każdym powtórzeniu (czyli po każdym przejściu po wszystkich obserwacjach) sprawdzamy warunek stopu opisany w poleceniu.

Poniżej na wykresach jest pokazane, co się dzieje w trakcie jednego powtórzenia (czyli wszystkie kroki). Na wykresie start zaznaczona prosta ma współczynniki równe wagom oraz narysowane są punkty, których kolor oznacza prawdziwą klasę. W kroku 1 błędnie klasyfikujemy obserwację czarną jako czerwoną i zmieniamy wagi. W krokach 2-5 poprawnie klasyfikujemy obserwacje, więc \(e_i = 0\) dla \(i=2,3,4,5\). W kroku 6 znów uaktualniamy wagi itd. Kończymy z wagami zaznaczonymi na wykresie koniec Sprawdzamy warunek stopu i albo od nowa wszystko powtarzamy, albo naprawdę koniec.