1 Inteligencja Obliczeniowa Perceptrony o dużym marginesie błęduWykład 9 Włodzisław Duch Katedra Informatyki Stosowanej UMK Google: W. Duch (c) Tralvex Yeap. All Rights Reserved

2 Co było Perceptron jednowarstwowy. Uczenie się perceptronówDemo w NeuroSolutions (c) Tralvex Yeap. All Rights Reserved

3 Co będzie Nieliniowa reguła delta Adatron Perceptron wielowarstwowy(c) Tralvex Yeap. All Rights Reserved

4 Perceptron dla M klas Reguła uczenia perceptronu:skończona liczba kroków sensowna generalizacja Granice decyzji perceptronu: dla klasy Ci wyjście gi(X) Decyzja: maxi gi(X), więc na granicy gi(X)=gj(X) Dla M klas jest M(M – 1)/2 granic; część jest redundantna. Obszary decyzyjne – zawsze wypukłe. Klasa Ci, wymagane gi(X)= 1, gj(X)= 0 Niektóre obszary – niesklasyfikowane bo wszystkie gi(X)= 0 lub kilka gi(X)=1 Przykład: granice decyzji perceptronu dla 3 klas. (c) Tralvex Yeap. All Rights Reserved

5 Niestabilności Granice decyzji mogą się całkowicie zmienić pod wpływem jednego punktu, który odpowiada wartości odstającej. (c) Tralvex Yeap. All Rights Reserved

6 Reguła delta - nieliniowaUczenie zgodne z regułą perceptronu: skoki, niestabilne granice. Błąd przy prezentacji pary (Xp,Yp) dla jednego perceptronu: Funkcja błędu: Szukamy minimum błędu ze względu na Wi (c) Tralvex Yeap. All Rights Reserved

7 Reguła delta cd. Poprawki do wag: Dla funkcji logistycznej Dla tanghPrzykłady działania takiej reguły w Neurosolutions: trening 10 perceptronów do rozpoznawania cyfr (każdy cyfra-reszta); efekty dodawania szumu do znaków – granice się poprawiają! (c) Tralvex Yeap. All Rights Reserved

8 Adatron i maksymalizacja marginesu.Cel: maksymalizacja odległości granicy decyzji od danych. Trening z szumem – prosty, ale kosztowny. Dla 2 klas i funkcji liniowej WX+b marginesy powinny być jak największe by zapewnić generalizację. Znajdź wektor najbliższy granicy i wagi zwiększające margines. Rozwiązanie: liniowe - Adatron nieliniowe - SVM (Support Vector Machines) (c) Tralvex Yeap. All Rights Reserved

9 Marginesy i hiperpłaszczyzny.(c) Tralvex Yeap. All Rights Reserved

10 Odległość od hiperpłaszczyzny.(c) Tralvex Yeap. All Rights Reserved

11 Adatron: algorytm Przyjmijmy (Xi,Yi), i=1 .. N, oraz Yi = ±1Progowe neurony, f(X)=sgn(g(X;W,b)) = sgn(W·X+b) Margines rośnie dla min||W|| pod warunkiem poprawnej klasyfikacji. Problem można sformułować jako minimalizację bez ograniczeń; ai = mnożniki Lagrange’a; f. dyskryminująca jest liniową kombinacją iloczynów (c) Tralvex Yeap. All Rights Reserved

12 Adatron: algorytm cd. Wstawiając za W i b poprzednie wartości Adatron minimalizuje: dodatkowe warunki Zdefiniujmy pomocnicze funkcje (najpierw policzmy il. skalarne): Algorytm iteracyjny: start a = 0.1, h, t = 0.01 mały próg czyli Xi jest odsunięte od granicy Jeśli ai + Dai  0 to zmień lub jeśli < 0 nic nie zmieniaj. (c) Tralvex Yeap. All Rights Reserved

13 Sieciowa realizacja AdatronuEfekt działania algorytmu: większość wsp. się zeruje, zostają niezerowe tylko przy wektorach granicznych. Wektory danych pamiętane są w węzłach jako wagi. Węzły obliczają iloczyny skalarne. Wagi ai łączą z neuronem wyjściowym obliczającym g(x) (c) Tralvex Yeap. All Rights Reserved

14 Adatron – efekty. Tyko pary klas są rozróżniane;potrzeba m(m-1)/2 klasyfikatorów dla m klas. Wektory, dla których ai >0 to wektory brzegowe (Support Vectors). Uczenie – na końcu procesu głównie w pobliżu granic decyzji. Złożoność O(n2) redukuje się do O(nsv2) Złożoność minimalizacji – eksponencjalna w N (wymiar wektora). Rezultaty podobne jak z perceptronem z gładką funkcja zamiast skokowej (znaku). (c) Tralvex Yeap. All Rights Reserved

15 Uczenie na brzegach Dla algorytmu Adatron pozostają tylko wektory brzegowe. Dla neuronów logicznych f. błędu zmienia się skokowo. Dla neuronów sigmoidalnych o dużym nachyleniu największy gradient jest w pobliżu granicy decyzji. (c) Tralvex Yeap. All Rights Reserved

16 Co dalej? Perceptrony wielowarstwowe Sieci HopfieldaSieci Hebbowskie i modele mózgu Samoorganizacja Perceptrony wielowarstwowe (c) Tralvex Yeap. All Rights Reserved

17 Koniec wykładu 9 Dobranoc (c) Tralvex Yeap. All Rights Reserved