Perzeptron

Modell von Rosenblatt (1958)

Ziel: Mustererkennung
Minsky und Papert (1969) reduzierten auf das Wesentliche.
u
P
1
P
3
P
2
0/1
w
1
w
2
w
3
P
4
w
4
P
i
: 0/1-Prdikate, typischerweise von beschrnktem Durchmesser,
liefern Information ber die abgetasteten Punkte in der
Projektionsflche (z.B. ob ein bestimmter Lichtreiz vorliegt):
Perzeptron gibt 1 aus, falls w
1
P
1
+ ... + w
n
P
n
> u , sonst 0.
Vereinfachtes Perzeptron-Modell
Von Prdikaten abstrahiert. Keine Einschrnkung, woher die Eingabe kommt.
u
x
1
x
n
x
2
y
w
1
w
2
w
n
y =

0
1
=
n
1 i
i i
x w
falls > u
sonst
1
x
1
x
2
OR

1

1

Einfache Beispiele: 2
x
1
x
2
AND

1

1

1.5
x
1
x
2
2

1
x
1
. x
2
(Integrationsf. g = gewichtete Summe, Aktivierungsf. f = Schwellenwertf.)
Geometrische Interpretation eines Perzeptrons
hnlich wie bei McCulloch-Pitts-Neuronen
u
x
1
x
n
y
w
1
w
n

=
n
1 i
i i
x w {(x
1
, ..., x
n
) : > u}
Beispiel:
1.5
x
1
x
2
2

1
x
1
. x
2

=
n
1 i
i i
x w {(x
1
, ..., x
n
) : < u}
Trennung findet durch die Hyperebene = u statt

=
n
1 i
i i
x w
x
1
x
2
1

-1

ein Perzeptron trennt den Eingaberaum
n
in 2 Regionen:
Lineare Trennbarkeit
Definition: Zwei Mengen A und B in
n
heien linear trennbar,
falls w
1
, ..., w
n
, w
n+1
e existieren, so dass

=
n
1 i
i i
x w (x
1
, ..., x
n
) e A > w
n+1

=
n
1 i
i i
x w (x
1
, ..., x
n
) e B < w
n+1

A

B

x
1
x
2
Definition: Eine binre
Funktion f :
n
{0, 1}
heit linear trennbar, falls
die Mengen A = f
1
(1) und
B = f
1
(0) linear trennbar sind.
Beispiele:
f(x
1
,x
2
) = x
1
OR x
2
linear trennbar:

f
1
(1) = {(0,1), (1,0), (1,1)}
f
1
(0) = {(0,0)}
x
1
x
2
f(x
1
,x
2
) = x
1
XOR x
2
nicht linear trennbar:

f
1
(1) = {(0,1), (1,0)}, f
1
(0) = {(0,0), (1,1)}
x
1
x
2
Satz:
Die XOR-Funktion kann von einem Perzeptron allein nicht
berechnet werden.
Beweis:
Aus 0w
1
+ 1w
2
> w
3
und 1w
1
+ 0w
2
> w
3

folgt w
1
+ w
2
> 2w
3
.
Aus 0w
1
+ 0w
2
< w
3
und 1w
1
+ 1w
2
< w
3

folgt w
1
+ w
2
< 2w
3
. Widerspruch!
Grenzen eines Perzeptrons:
Absolute lineare Trennbarkeit
Definition: Zwei Mengen A und B in
n
heien absolut linear
trennbar, falls w
1
, ..., w
n
, w
n+1
e existieren, so dass

=
n
1 i
i i
x w (x
1
, ..., x
n
) e A > w
n+1

=
n
1 i
i i
x w (x
1
, ..., x
n
) e B < w
n+1

echte Ungleichung in beiden Fllen
Satz: Es seien A und B endliche Mengen in
n
. Dann gilt:
A und B linear trennbar A und B absolut linear trennbar.
Beweis: Die Richtung ist klar.
(:) Angenommen, A und B sind linear trennbar.
Dann existieren w
1
, ..., w
n
, w
n+1
e , so dass

=
n
1 i
i i
x w (x
1
, ..., x
n
) e A > w
n+1

=
n
1 i
i i
x w (x
1
, ..., x
n
) e B < w
n+1

Setze c = min{w
n+1
: (x
1
, ..., x
n
) e B}.
=
n
1 i
i i
x w
c existiert (warum?) und > 0.
Definiere w'
n+1
:= w
n+1
c/2. Dann ist wegen c > 0: w'
n+1
< w
n+1
und deshalb:

=
n
1 i
i i
x w (x
1
, ..., x
n
) e A > w
n+1
> w'
n+1

=
n
1 i
i i
x w (x
1
, ..., x
n
) e B w
n+1
c
Def. von c

=
n
1 i
i i
x w w
n+1
< w'
n+1
w
n+1

=
n
1 i
i i
x w < w'
n+1

Def. von w'
n+1

> c/2
Perzeptron-Lernaufgabe
Gegeben: Endliche linear trennbare Mengen P und N in
n

(positive und negative Muster)
Aufgabe: Finde Gewichtsvektor w = (w
1
, ..., w
n
) und Schwellenwert u,
so dass P und N durch das Perzeptron (absolut) linear getrennt werden:
(x
1
, ..., x
n
) e P xw
T
= x
1
w
1
+ ... + x
n
w
n
> u
(x
1
, ..., x
n
) e N xw
T
= x
1
w
1
+ ... + x
n
w
n
< u
Vereinfachung: Schwellenwert wird als ein weiteres Gewicht interpretiert.
x
1
x
n
w
1
w
n
u
x
1
x
n
w
1
w
n
u
1

0
OBdA kann mit Schwellenwert null gearbeitet werden:
Erweiterter Gewichtsvektor : (w
1
, ..., w
n
, u)
Erweiterter Eingabevektor : (x
1
, ..., x
n
,1)
Definition: Sei w ein Vektor in
n
.
Offener positiver Halbraum: {x e
n
: xw
T
> 0}
Abgeschlossener positiver Halbraum: {x e
n
: xw
T
> 0}
Die Perzeptron-Lernaufgabe
(mit Schwellenwert 0) besteht
darin, einen Gewichtsvektor w
zu finden, so dass die Punkte
aus P im positiven Halbraum und
die Punkte aus N im negativen
Halbraum liegen.
Analog fr (offenen/abgeschlossenen) negativen Halbraum.
xw
T
> 0
xw
T
< 0
w
p
1
p
2
n
2
n
1
Fehler des Perzeptrons (mit Gewichtsvektor w):
Anzahl der Punkte von P im negativen Halbraum
+
Anzahl der Punkte von N im positiven Halbraum

(= Anzahl der falsch klassifizierten Punkte).
Fehler als Funktion der Gewichtsvektoren w soll
durch nderung von w minimiert werden.
Fehlerflchen: (hier fr die OR-Funktion und festen Schwellenwert 1)
Lernen: Wandern im Fehlergebirge
bis Tal (Fehler = 0) erreicht.
Problem: Wie wandern?
w
1
w
2
Fehler
-1 0 3
0 2 1
Perzeptron-Lernalgorithmus
Eingabe: Endliche linear trennbare Mengen P und N in
n
.
Ausgabe: Gewichtsvektor w = (w
1
, ..., w
n
) , der P und N absolut linear trennt,
wobei P im offenen positiven und N im offenen negativen Halbraum liegen.
(1) Whle w = (w
1
, ..., w
n
) mit zuflligen Werten
(2) repeat
(3) fehler: = false /* Fehler des Perzeptrons ? */
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11) until not fehler


for jedes x e P N do
begin




end







if (x e N and xw
T
> 0) then
begin fehler:= true; w:= w x end


Epoche = 1 Durchlauf der for-Schleife



if (x e P and xw
T
s 0) then
begin fehler:= true, w:= w + x end


Geometrische Veranschaulichung
Der Winkel zwischen x und w sei o. Es ist xw
T
= ||x||||w||cos o.
x e N xw
T
< 0 cos o < 0 90
o
< o < 270
o
Lernen:
Falls x e P und |o| > 90
o
, so wird w
(durch Addition von w und x)
in Richtung von x gezogen
( Winkel zwischen x und w wird kleiner).
Falls x e N und |o| s 90
o
, so wird w
(durch Addition von w und x )
in Richtung von x gezogen.
( Winkel zwischen x und w wird grer).
Hier ist o der Winkel zw. x und w.
w
p
1
p
2
n
2
n
1
x e P xw
T
> 0 cos o > 0 90
o
< o < 90
o
Deshalb:
Geometrische Veranschaulichung
w
0
p
1
n
2
n
1
w
1
Anfang (Fehler = 2)
x = p
1
falsch erkannt:
w
1
= w
0
+ p
1
p
1
n
2
n
1
w
0
Geometrische Veranschaulichung
p
1
n
2
n
1
w
1
p
1
n
2
n
1
w
1
-n
2
w
2
Fehler = 1
x = n
2
falsch erkannt:
w
2
= w
1
n
2
Geometrische Veranschaulichung
p
1
n
2
n
1
w
2
Fehler = 0: Alle Punkte sind richtig klassifiziert!
Perzeptron-Konvergenz-Theorem
Wird das Perzeptron irgendwann mit dem Lernen fertig sein?
Satz: Falls P und N linear trennbar sind, dann terminiert der Perzeptron-
Lernalgorithmus mit einem Gewichtsvektor w, der P und N absolut trennt.
Beweis:
Sei w* ein Vektor, der P und N absolut trennt.
Schreibe P' = P {x : x e N}.
Sei w
0
der Anfangsvektor w in Zeile (1) und w
t
die t-te nderung des
Gewichtsvektors w (Zeile (7) bzw. (9)).
Angenommen, w
t+1
sei berechnet worden. D.h. es gibt ein p e P', das bzgl.
w
t
falsch klassifiziert wurde: pw
t
T
s 0, und die Korrektur w
t+1
= w
t
+ p
wurde vorgenommen.
e : = min{w*q
T
: q e P'}.
e existiert, da P' endlich ist, und e > 0, da w* P und N absolut trennt.
O : = max{||q|| : q e P'}.
O existiert, da P' endlich ist, und O > 0, da P und N trennbar sind.
Wiederholte Abschtzung liefert:
w*w
t+1
T
> w*w
0
T
+ (t+1) e.
Nun gilt:
w*w
t+1
T
= w*(w
t
+ p)
T
= w*w
t
T
+ w*p
T
> w*w
t
T
+ e.
Auerdem:
||w
t+1
||
2
= (w
t
+ p)(w
t
+ p)
T
= ||w
t
||
2
+ 2 pw
t
T
+||p||
2
s ||w
t
||
2
+ O
2
.
da pw
t
T
s 0
Wiederholte Abschtzung liefert:
||w
t+1
||
2
s ||w
0
||
2
+ (t+1)O
2
.
Es folgt: ||w*||cos o = (w*w
t+1
T
) ||w
t+1
||
> (w*w
0
T
+ (t+1) e) (||w
0
||
2
+ (t+1)O
2
)

(t )
Da ||w*||cos o s ||w*||, kann t also nicht beliebig gro sein: Die Anzahl der
nderungen von w ist endlich und der Algorithmus terminiert.
Der Winkel zwischen w* und w
t+1
sei o. Es ist:
||w*||cos o = (w*w
t+1
T
) ||w
t+1
||.
Komplexittsbetrachtung
Der Perzeptron-Lernalgorithmus hat im schlechtesten Fall exponentielle
Laufzeit.
Die Perzeptron-Lernaufgabe kann als ein lineares Programm formuliert
werden.
Simplex-Algorithmus
lsbar in Polynomialzeit mit Khachiyan (1979), aber in der Regel
langsamer als der Simplex-Algorithmus. Schneller mit Karmarkar (1984)
Was kann ein Perzeptron im nicht linear trennbaren Fall?
Satz: Gegeben seien Zahlen k, n e und Mengen P, N in
n
. Dann ist das
Entscheidungsproblem, ob es ein Perzeptron gibt, das P und N mit hchstens
k Fehlern trennt, NP-vollstndig.
Beschleunigung: Normierung
Das Problem:
Als falsch erkannte lange Eingabevektoren x verndern den Gewichtsvektor
w bermig stark: w + x ~ x.
Beispiel: P ={(1, 1), (100, 130)} und N = {(1, 1)}
Abhilfe:
Normierung der Vektoren: x ||x||. Dadurch werden alle Eingabevektoren
gleichwertig sein.

Normierung der Eingabevektoren ndert das Problem nicht: Trennt w die
normierten Vektoren, so trennt w auch die ursprnglichen Vektoren.
Als falsch erkannte kurze Vektoren verursachen aber nur geringe
Vernderung des Gewichtsvektors: w + x ~ w.
Das obige Beispiel braucht 8 Epochen (Excel-Test) mit Normierung
(85 Epochen ohne Normierung!)
Perzeptron-Lernalgorithmus mit Delta-Regel
Gewnschte Ausgabe des Perzeptron bei Eingabevektor
x = (x
1
, ..., x
n
) sei t {0, 1}.
Also: t = 1, falls x e P und t = 0, falls x e N.
Der Lernfaktor ist eine Konstante zwischen 0 und 1, und gibt
an, wie viel vom Fehler korrigiert werden soll.
Tatschliche Ausgabe des Perzeptron bei Eingabevektor
x = (x
1
, ..., x
n
) sei y {0, 1}.
Fehlersignal: o = t y.
Lernfaktor (Lernrate): q.
nderung: Aw = q o x.
Korrektur: w := w + Aw (Delta-Regel)
Perzeptron-Lernalgorithmus mit Delta-Regel
Ist x e P falsch erkannt, so o = t y = 1 0 = 1,
und w wird um qx korrigiert: w:= w + Aw = w + qx.
Der diskutierte Perzeptron-Algorithmus hat also einen
Lernfaktor q = 1.
Ist x e P richtig erkannt, so o = t y = 1 1 = 0, und es wird
keine Korrektur fr w vorgenommen: w:= w + Aw = w.
Analog fr Eingabevektoren x e N: Ist x falsch erkannt,
so o = 1 und w wird um qx korrigiert: w:= w qx.
Sonst wird keine Korrektur vorgenommen.