1 Uczenie konkurencyjne.Wykład 6 Włodzisław Duch Uniwersytet Mikołaja Kopernika Google: W. Duch (c) Tralvex Yeap. All Rights Reserved

2 Mapy w mózgu Samoorganizacja Sieci SOM Kohonena Co było(c) Tralvex Yeap. All Rights Reserved

3 Mapy ekwiprobabilistyczne Zwycięzca bierze wszystko Gaz neuronowy Co będzie Mapy ekwiprobabilistyczne Zwycięzca bierze wszystko Gaz neuronowy Demonstracje w Javie (c) Tralvex Yeap. All Rights Reserved

4 Mapy ekwiprobabilistyczneDla 1 wymiaru można pokazać, że uporządkowanie jest prawidłowe, ale p(Wi)  p(X)2/3 w granicy ciągłego rozkładu. Stosowanie lokalnych funkcji błędu prowadzi do p(Wi)  p(X)1/3 SOM przecenia rejony mało prawdopodobnych danych i niedocenia rejony o dużym prawdopodobieństwie. Powstają neurony bezużyteczne; jak wykorzystać całą sieć? Conscience Learning (DeSieno 1988; Hecht-Nielsen 1988). fi - częstość wygrywania neuronu i, C - stała. Zasada jednakowego zniekształcenia: każdy neuron powinien mieć podobny wkład do końcowego błędu kwantyzacji (klasyfikacji). (c) Tralvex Yeap. All Rights Reserved

5 Maksymalizacja entropiiKwantyzator maksymalizujący entropię (MEQ): w każdym przedziale takie samo prawdopodobieństwo. Można to osiągnąć maksymalizując entropię: Jak znaleźć optymalne przedziały by osiągnąć ekwiprobabilistyczny podział? (c) Tralvex Yeap. All Rights Reserved

6 BAR Reguła Adaptacji Granic, Boundry Adaptation Rule.Jeśli P(Hi) jest za duże (zbyt często pojawiają się wektory z tego przedziału) to wielkość przedziału należy zmniejszyć. Przedział w 1D określony jest przez wagi. Jeśli dane są z przedziału Hi to Wi przesuwamy w lewo (zmniejszamy przedział Hi), jeśli z Hi+1 to w prawo (zmniejszamy przedział Hi+1). Zmiany ustają gdy mamy ekwiprobabilistyczny podział: (c) Tralvex Yeap. All Rights Reserved

7 Konstruktywny SOM Growing Cell Structures (Fritzke 1993).Początkowa topologia: k-wymiarowy sympleks (k=1, 2, 3). Dodaje się nowe neurony i usuwa stare. Algorytm SOM, ale bez zmniejszania sąsiedztwa i adaptacji dokonuje się tylko dla zwycięzcy i bezpośrednich sąsiadów. Znajdź neuron-zwycięzcę c. Popraw jego wagi: DWc=hs(X-Ws). Popraw wagi sąsiadów DWs=hs(X-Ws). Zwiększ licznik częstości Dtc=1, zmniejsz wszystkie Dtc=-a tc. Policz zrenormalizowane częstości fi = ti/Sjtj Po ustalonej liczbie epok L znajdź neuron o największej częstości i wstaw pomiędzy ten neuron i najdalszego sąsiada nowy neuron tworząc lokalny sympleks; nowy wektor weź z interpolacji. (c) Tralvex Yeap. All Rights Reserved

8 Rozwój GCS (c) Tralvex Yeap. All Rights Reserved

9 GCS - 2 obszary Sytuacja w 3-wym. przestrzeni danych - 2 oddzielone skupienia. Sieć GCS rosnąca w dwóch wymiarach - odpowiednia topologia. (c) Tralvex Yeap. All Rights Reserved

10 Voronoi i Delaunay Punkty granice decyzji Triangulacjadanych Voronoia Delaunaya Obszary Voronoia - neuron zwycięża konkurencję. Zbiór Voronoia - zbiór wektorów wewnątrz obszaru Voronoia. Łącząc neurony, których obszary Voronoia mają wspólną krawędź otrzymujemy traingulację Delaunaya. (c) Tralvex Yeap. All Rights Reserved

11 WTA Algorytm LBG typu WTA:Uczenie konkurencyjne - WTA, Winner Takes All. Nazywane też Hard Competitive Learning. Jeden zwycięzca, dane pojedynczo (on-line) lub wszystkie (batch). Mogą powstawać bezużyteczne neurony - konieczna incjalizacja zgodna z rozkładem danych. Algorytm LBG typu WTA: przypadkowa inicjalizacja; Powtarzaj aż ustaną zmiany: pokaż wszystkie dane i znajdź zbiory Voronoia; przesuń wagi neuronu do centrum obszaru Wariant LBG-U: przesuń mało użyteczne (zerowy zbiór Voronoia) neurony w lokalne minima błędu. (c) Tralvex Yeap. All Rights Reserved

12 Gas neuronowy Algorytm NG typu SOM:Wariant uczenia konkurencyjnego (Schulten i Martinez 1991) Algorytm NG typu SOM: przypadkowa inicjalizacja N wektorów; t=0; Wybierz przypadkowy wektor V Zrób ranking wag najbliższych V; k=1..N Zastosuj regułę adaptacji: zmniejszając eksponencjalnie obszar l i stałą uczenia e(t). (c) Tralvex Yeap. All Rights Reserved

13 Co dalej? Wizualizacja Systemy rozmyte i neurorozmyte.Podstawy teoretyczne CI. Inspiracje statystyczne. Drzewa decyzji. Metody oparte na podobieństwie. Uczenie maszynowe, indukcja reguł logicznych. Zastosowania. (c) Tralvex Yeap. All Rights Reserved

14 Koniec wykładu 6 Dobranoc !(c) Tralvex Yeap. All Rights Reserved