Perceptron
Jacek Kluska
Politechnika Rzeszowska
2010
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 1 / 11
Klasyfikator ciągły
Perceptron z ciągłą funkcją aktywacji - wejścia (x1, . . . xN), wyjście y
y = f (n) ; n = w,x + b = w1x1 + . . . + wNxN + b
f - różniczkowalna, np.
Znany jest zbiór par uczących {(x1, d1) , (x2, d2) , . . . , (xQ, dQ)} .
2
y = f (n) = - 1,  > 0, y " (-1, 1) - bipolarna
1 + e-n
1
y = f (n) = ,  > 0, y " (0, 1) - unipolarna
1 + e-n
Dane: Zbiór par uczących {(x1, d1) , (x2, d2) , . . . , (xQ, dQ)}, gdzie
di " {-1, 1} lub di " {0, 1}.
BÅ‚Ä…d
1
E (k) = [d (k) - y (k)]2 , k = 0, 1, 2, . . .
2
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 2 / 11
Problem
Znalez
ć taki algorytm uczenia w i b, aby
E (k) - min , " k
Gradienty
îÅ‚ Å‚Å‚
"n
ïÅ‚ śł
"w1
ïÅ‚ śł
"E "y "E "y
.
ïÅ‚ śł
.
"wE = "wn =
.
ïÅ‚ śł
"y "n "y "n
ðÅ‚ ûÅ‚
"n
"wN
"E "y "n
"bE =
"y "n "b
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 3 / 11
Algorytm uczenia perceptronu - metoda  delta
w (k + 1) = w (k) - ·"wE
b (k + 1) = b (k) - ·"bE , · > 0
f - bipolarna
"f " 2 
= - 1 = 1 - y2
"n "n 1 + e-n 2
f - unipolarna
"f " 1
= = y (1 - y)
"n "n 1 + e-n
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 4 / 11
Algorytm uczenia perceptronu dla funkcji bipolarnej i
unipolarnej
Algorytm uczenia perceptronu dla funkcji bipolarnej

w (k + 1) = w (k) + · [d (k) - y (k)] 1 - y2 (k) x (k)
2

b (k + 1) = b (k) + · [d (k) - y (k)] 1 - y2 (k)
2
Algorytm uczenia perceptronu dla funkcji unipolarnej
w (k + 1) = w (k) + · [d (k) - y (k)] y (k) [1 - y (k)] x (k)
b (k + 1) = b (k) + · [d (k) - y (k)] y (k) [1 - y (k)]
Uwaga: Uczenie klasyfikatora ciągłego nawet dla problemów liniowo
separowalnych nie zawsze prowadzi do poprawnej klasyfikacji (Wittner,
Denker, 1988).
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 5 / 11
Klasyfikator dyskretny
Perceptron ze skokową funkcją aktywacji - wejścia (x1, . . . xN),
wyjście y
y = f (n) ; n = w,x + b = w1x1 + . . . + wNxN + b
Funkcja aktywacji
1 Ô! n e" 0
y = f (n) = sign (n) =
-1 Ô! n < 0
Dane: Zbiór par uczących {(x1, d1) , (x2, d2) , . . . , (xQ, dQ)}, gdzie
di " {-1, 1} lub di " {0, 1}.
BÅ‚Ä…d
1
E (k) = [d (k) - y (k)]2 , k = 0, 1, 2, . . .
2
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 6 / 11
Problem
Znalez
ć taki algorytm uczenia w i b, aby
E (k) = 0 , "k e" k0
Algorytm uczenia perceptronu dyskretnego
1
w (k + 1) = w (k) + c [d (k) - y (k)] x (k)
2
1
b (k + 1) = b (k) + c [d (k) - y (k)]
2
Wskazówka: współczynnik korekcji
| w (k) ,x (k) |
c (k) = c0 , c0 > 0
x (k) 2
Uwaga: Uczenie klasyfikatora dyskretnego według wzoru jak wyżej, dla
problemów liniowo separowalnych - zawsze prowadzi do poprawnej
klasyfikacji w skończonej liczbie kroków.
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 7 / 11
Dowód zbieżności reguły uczenia klasyfikatora dyskretnego
Funkcja aktywacji każdego neuronu jest typu  signum : y " {-1, 1}.
Mamy 2 klasy punktów: K1 i K2.
x " K1 Ô! w,x d" 0 Ô! sign w,x = -1
x " K2 Ô! w,x > 0 Ô! sign w,x = +1
Fakt:
x " K2 Ò! (-x) " K1
ponieważ w,x > 0 Ò! w, (-x) < 0
Modyfikujemy ciąg uczący: eliminujemy te x, które nie powodują
zmiany wag. Jeżeli x " K1 i [d (k) - y (k)] = [1 - (-1)] = 2.
Wtedy w (k + 1) = w (k) + cx (k), c > 0. Nie będziemy podawać w
trakcie uczenia punktów x " K2, lecz (-x) " K1. Zatem
w (k + 1) = w (k) + cx (k). Zmodyfikowany ciÄ…g uczÄ…cy:
K1 = K1 *" {(-x) : x " K2}
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 8 / 11
Dowód zbieżności reguły uczenia klasyfikatora dyskretnego
- założenia i fakty
Założenia:
1
Problem jest liniowo separowalny:
"w" = wopt : w",x > 0, "x
2
Bez utraty ogólności: w (1) = 0.
Fakt 1
- wynika z modyfikacji ciągu uczącego i stąd, że w (1) = 0:
w (k + 1) = w (k) + cx (k) , "x " K1
Ó!
w (k + 1) = cx (1) + cx (2) + ... + cx (k)
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 9 / 11
Dowód zbieżności reguły uczenia klasyfikatora dyskretnego
- fakty
Fakt 2
- wynika z liniowej separowalności:
"´ : inf w",x = ´ > 0
x
Rozpatrzmy w",w (k + 1) :
w" w (k + 1) e" w",w (k + 1)
= w", cx (1) + w", cx (2) + ... + w", cx (k)
e" ck´
c2k2´2
2
w (k + 1) e"
w" 2
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 10 / 11
Dowód zbieżności reguły uczenia klasyfikatora dyskretnego
- fakty, c.d.
Z drugiej strony:
2
w (k + 1) = w (k) + cx (k) ,w (k) + cx (k)
2
= w (k) + 2c w (k) ,x (k) + c2 x (k) 2
Korekcja wag następuje dopóty, dopóki w (k) ,x (k) d" 0, więc
2 2
w (k + 1) d" w (k) + c2 x (k) 2
2
d" w (k) + c2M2 d" kc2M2
gdzie M = sup x . Czyli
x
2
c2k2´2 M w"
2
kc2M2 e" w (k + 1) e" Ò! k d" .
´
w" 2
J. Kluska (Politechnika Rzeszowska) Perceptron 2010 11 / 11