Upload
hoangtuong
View
216
Download
1
Embed Size (px)
Citation preview
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vorlesung 9
Unüberwachtes Lernen I
Martin Giese
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Übersicht
EinführungClustermethodenHauptkomponentenanalyse (PCA)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Unüberwachtes LernenBisher: Überwachtes LernenDaten: Paare (x, y)
Statistik: p(x, y)
Gesucht: Funktion y = f(x)
Heute: Unüberwachtes LernenDaten: Vektoren x
Statistik: p(x)
Gesucht: Modellierung spezifischer
Eigenschaften von p(x)
x y“Lerner”
x“Lerner”
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Unüberwachtes LernenPrinzipelle Methoden
Dichteschätzung von p(x)(Schwierig für höhere Dimensionen; Curse of Dimensionality !)
Modellierung von p(x):
– Mehrere konvexe Regionen: Clusteranalyse
– Mischung von Verteilungen (z.B. gaussian
mixture)
– Mannigfaltigkeiten: PCA, ICA, LLE
(Funktion latenter Variablen)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Unüberwachtes Lernen
Kein “Lehrersignal”
Validität von statistischen Inferenzschlüssen
wesentlich schwieriger zu evaluieren als bei
überwachtem Lernen (keine Kostenfunktion gegeben)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Ziel der ClusteranalyseGegeben: l Datenpunkte xi mit 1 ≤ i ≤ l
Ziel: Modellierung mit Mischverteilung:
Beispiel: Gauss-Mischverteilung:
Problem: Schätzen der Cluster-Zentren: µk
Direkte Methode: Maximum-Linkelihood-Schätzung ⇒
unangenehmes nichtlineares Optimierungsproblem !
∑=
− −−−K
kkk
Tkkcp
1
1 ))()(21exp(~)( µµ xKxx x1
x2
µ1
µ2
)()|()(1
ii
K
k
YpYpp ∑=
= xx
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
K-means-Cluster-AlgorithmusEinfach, funktioniert sehr gut in der Praxis
Vorgabe der Zahl der Cluster: k
Euklidsches Abstandsmass
Algorithmus:1. Initialisierung: Wahl von k Datenpunkten als Cluster-Zentren µi
2. Zuweisung aller l Datenpunkte zum nächsten Cluster-Zentrum
3. Ersetzen von µi durch Mittelwert aller zugewiesenen
Datenpunkte
4. Iteration ab 2. bis sich die Werte von µi nicht mehr ändern
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
K-means-Cluster-AlgorithmusAlgorithmische Komplexität: O(lnk) (n: Dimensionalität
von xi)
Man kann beweisen, dass Algorithmus terminiert.
Lokale Minima; daher verschiedene Startkonfigurationen
ausprobieren.
Moore (2001)
Suboptimale Lösung
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
K-means-Cluster-Algorithmus
Auswahl der Zahl der Cluster schwierig
Möglich durch Vergleich der Varianzen innerhalb /
zwischen Clustern
Komplexitätskriterien (z.B. Schwartz-Kriterium)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
K-means-Cluster-AlgorithmusBeispiel
Zuordnung der Daten-punkte zu Zentren Neue ZentrenStartkonfiguration
Iteration 1
Moore (2001)
Letzte iteration
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
VektorquantisierungMethode zur Datenkompression
Datenpunkte xi mit 1 ≤ i ≤ l ersetzt durch jeweils
nächstes Cluster-Zentrum µk mit 1 ≤ k ≤ K
Typischerweise K << l
Clusterzentren definieren ein “Codebuch”
Encodierung Kanal Decodierer
)(ˆxfµx
== k
Kod
e-Sy
mbo
le
Kod
e-Sy
mbo
le
Rek
onst
ruie
rtes
Sign
al
Sign
al
xk k
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: Theorie
Daten: xi ∈ IRn ; endliches Codebuch: C={µ1,…, µK},
µk ∈ IRn
Jedem Element µk ist Region Rk ⊂ IRn zugeordnet.
Regionen Rk , 1 ≤ k ≤ K, sind disjunkt und überdecken
ganzen Eingangsraum.
Vektorquantisierer entspricht Funktion:
∑=
∈=K
kkk RIf
1
)()( xµx
Indikatorfunktion
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: Theorie
Folgende Kostenfunktion misst die “Störung” des
rekonstruierten Signals:
Minimierung dieser Risikofunktion liefert notwendige
Bedingungen für optimalen Vektorquantifizierer
(Loyd-Max-Bedingungen)
∫ −= xxxx dpfR )(|)(| 2
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: Theorie
Lloyd-Max-BedingungenFeste Regionen Rk, Optimierung der µk
Minimierung von
liefert
Optimaler Decoder:
∈−= ∑=
2
11 )(),...,(
K
kkkK RIER xµxµµ
≤≤=
∈−∈ ∑=
KlRIRIEK
kkkl 10)()(
1
xµxx
{ } KkRIE lk ≤≤=∈= 10)(|* xxµ
⇒
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: Theorie
Lloyd-Max-Bedingungen (Forts.)
Feste Eingangssignale xi , Optimierung der Regionen Rk
Annahme: beliebiges x ∈ IRn, Regionen Rk gegeben
Sei x ∈ Rk, aber |x– µk| > |x– µl|.
Beitrag zur Kostenfunktion: |x– µk|2
Dann kann die Kostenfunktion
verringert werden indem x zu Rl hinzugenommen wird.
∈−= ∑=
2
11 )(),...,(
K
kkkK RIER xµxµµ
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: Theorie
Lloyd-Max-Bedingungen (Forts.) Voronoi-Partitionierung
Optimale Regionen ordnen jedem
x ∈ IRn das nächste µk zu
Nächster-Nachbar- oder Voronoi-
Partitionierung
D. h. Optimaler Encoder erfüllt:
{ }klR lkn
k ≠−<−∈= falls |||||IR µxµxx µkRk
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: AnwendungOriginalbild: 1024 x 1024 Pixel, 8 Bit
Grauwertinformation
Aufteilen in Pixelblöcke der Grösse 2 x 2
Grauwerte der Blöcke aufgefasst als Vektor in IR4
K-Means-Methode angewendet auf diesen 4D-Raum
Kompression von 8 Bit / Pixel auf 1.9 bzw. 0.5 Bit / Pixel
Nur geringe Zahl von verschiedenen Viererblocks treten
in natürlichen Bildern auf
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Vektorquantisierung: AnwendungOriginal 200 Kodevektoren 4 Kodevektoren
Hastie et al. (2001)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
III. Hauptkomponentenanalyse (PCA)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
DimensionalitätsreduktionAnnahme: Datenpunkte xi bedecken nur einen Teil des
hochdimensionalen Raumes IRn
Ziel: Modellieren des “erzeugenden Prozesses”
, wobei für z geeignete Verteilungsannahmen
gemacht werden
Typischerweise z ∈ IRm mit m << n
: Schätzer für z
Gute Lösung sollte Risiko der Form minimieren:
)(zfx=
∫= xxxzx dpfVR )()))(ˆ(,(
)(ˆ xz
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Annahme: Datenpunkte xi , mit 1 ≤ i ≤ l, liegen in linearem
Unterraum
Modellierung der Daten durch Linearkombination von
Basisvektoren zk, Offset z0
Annahme:
Basisvektoren orthonormal, d.h.o
oo
o
x1(x)
x2(x)∑=
+==K
kk
iki w
10)(ˆ zzzfx
Krkkr
k
rTk
≤≤=≠=
,11|| falls 0
zzz
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Mit L2-Kostenfunktion und Z = [z1, …, zK] folgt:
Minimierung nach z0:
Minimierung nach wi:
Mit und folgt:
∑∑ ∑== =
+−=+−=l
i
ii
l
i
K
kk
iki lw
lR
1
2
01
2
100emp
11),( ZwzxzzxZz
∑=
=l
iil 1
01ˆ xz
( ) 0wzxZw =−= ∑=
l
iii
Ti
10 ˆmit ˆˆ
( )0ˆ~ zxx −= ii ]~,...,~[ 1 lxxX =
∑=
−=l
ii
Til
R1
2
0emp~~1),( xZZxZz
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Die Matrix P = ZZT ist eine Projektionsmatrix auf einen
Unterraum mit der Dimensionalität K
Die ideale Wahl für diesen Projektor selektiert
Dimensionen im Raum IRn, die am meisten Varianz von X
erklären
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Singulärwertzerlegung(Singular value decomposition, SVD)
Sei A eine n x m Matrix mit Rang r
Dann kann A immer zerlegt werden in der Form
A = UΣVT mit
U = UT: n x n Orthogonalmatrix
V = VT: m x m Orthogonalmatrix
Σ: n x m Matrix mit
≤=≥
=Σsonst 0
und falls 0 rijiiij
σSingulärwerte
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Singulärwertzerlegung (Forts.)(Singular value decomposition, SVD)
Beachte:
– Spalten von U sind Eigenvektoren von AAT
– Spalten von V sind Eigenvektoren von ATA
– Die σi2 sind die Eigenwerte von AAT und ATA
Wenn die Singulärwerte geordnet sind, so dass
σi ≥ σi+1 ≥ 0, gilt mit den Spaltenvektoren ui und vj
∑=
==r
k
Tkkk
T
1
vuVUΣA σ
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Singulärwertzerlegung (Forts.)(Singular value decomposition, SVD)
Def.: Die Matrixnorm ||.||2 ist definiert als
Satz (Approximationseigenschaft):
Die Matrix
ist die Matrix vom Rang s, die Matrix A am besten im
Sinne der Matrixnorm ||.||2 approximiert, d.h.
||||||sup||2 x
AxA0x≠
=
rss
k
Tkkks ≤=∑
=
mit 1
vuA σ
12s)rang(2 ||||min|||| +≤=−=− ss σQAAA
Q
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Singulärwertzerlegung (Forts.)(Singular value decomposition, SVD)
Beachte: mit
d.h. nur die ersten s Singulärwerte werden berücksichtigt;
oder mit
Tss VUΣA =
≤=≥
=Σsonst 0
und falls 0,
sijiiijs
σ
Tss VUΣA = ],...,,,...,[ 1 00uuU ss =
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Wenn n mit |n|=1 ein Normalenvektor ist, dann definiert
y = nTx neues skalares Merkmal
y = XT n die Projektion der Daten auf dieses Merkmal
Die Richtung n mit maximaler Varianz ergibt sich aus:
22
2
1||
1||1||
||||1-l
1||1-l
1max
)(Varmax)(Varmax
XnX
nXy
n
nn
=
==
=
==
T
T
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Die Matrixnorm von X bestimmt also die Varianz entlang
der Merkmalsrichtung mit maximaler Varianz
Wird X mit einer Q Matrix mit Rang s approximiert, so ist
yu = (X-Q)Tn der Teil der Variation entlang der Merkmals-
dimension, die nicht durch die Approximation erklärt wird
Der nichterklärte Anteil der Variation ist somit:
221||u1||
||||1-l
1))((Varmax)(Varmax QXnQXynn
−=−===
T
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Wegen der Approximationseigenschaft ist somit Xs die
Matrix mit Rang s die die maximale Varianz der Daten X
erklärt
Wegen impliziert dies mit
⇒ Z = Us (Spalten orthonormal !)
Tss VΣUX = i
i Zwx =~
[ ] [ ]llss
s
k
Tkkk
s
k
Tkkk
Tss
ZwZwwUwU
vuvuVΣUX
,...,,...,
)()(
1111
==
=== ∑∑==
σσ
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkomponentenanalyse (Principal Components Analysis)
Die Korrelationsmatrix von X ist XXT = UΣ2UT
Σ2 ist die diagonalisierte Kovarianzmatrix
Es gilt X = UΣVT und Xs = UsΣVT
Die Spalten von UΣ heissen Hauptkomponenten
Nur die ersten s Hauptkomponenten tragen bei zur
Approximation
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Eigengesichter (eigen faces)
(Sirovitch & Kirby, 1987; Turk & Pentland, 1991)
Heute Standardmethode; sehr populär
In Signalverabeitung auch bekannt als Karhunen-Loewe-
Transformation
Grauwertvektoren von Bildern als Daten xi
Bei meisten Bildern starker Abfall der Singulärwerte für grosse s;
daher relativ niedrigdimensionale Approximation möglich
Für (normalisierte !) Gesichter s≈40 erforderlich für gute
Approximation.
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Eigengesichter (eigen faces)
(Sirovitch & Kirby, 1987; Turk & Pentland, 1991)
Anwendungsbeispiel
TestbildTrainingsgesichter
KLT, PCA
Projektion aufEigengesichter
Hauptkomponenten“Eigengesichter”
k=0 k=1 k=2 k=3
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Eigengesichter (eigen faces)
(Sirovitch & Kirby, 1987; Turk & Pentland, 1991)
AnwendungsbeispielRekonstruktion
Approximationsgüte stark abhängig von Zahl der
Hauptkomponenten
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Eigengesichter (eigen faces)
Anwendung für Klassifikation (Turk & Pentland, 1991):
– Klassifikation (nearest neighbour)
im Gewichtsraum der Eigengesichter
– Gesicht vs. Nicht-Gesicht bei zu
grossem Abstand von linearem
Gesichtsraum
– Gesichteridentifikation durch Vergleich mit
Mittelwertsgewichtsvektor einer Person aus
Training
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Eigengesichter (eigen faces)
Resultate:
– Ideale Orientierung der Gesichter: 96 % korrekt
– Variation der Orientierung: 85 % korrekt
– Skalieren der bilder: 64 % korrekt
Echtzeitfähigkeit
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkurven (Principal Curves)
Verallgemeinerung der PCA für gekrümmte
Mannigfaltigkeiten
Kurve parametrisiert als Funktion von Kurvenparameter z:
f(z): IR → IRn
Für jeden Datenpunkt parametrisiere zf(x) den Punkt der
Kurve, der am nächsten ist.
Def.: f(z) heisst Hauptkurve falls für die Verteilung p(x)
gilt:
(Hastie, 1984; Hastie & Stützle, 1989)
})(|{)( zzEz == xxf f
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Hauptkurven (Principal Curves)
Algorithmus ähnlich k-means
Zwei Schritte alternieren:
– Schätzen der nächsten Punkte zf(xi)
– Schätzen der Funktion f(z) unter Nutzung von
(Hastie, 1984; Hastie & Stützle, 1989)
})(|{)( zzEz == xxf f
o o
oo
x2(x)o o
x1(x)
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Wichtige Punkte
Definition / Probleme: Unüberwachtes LernenVektorquantisierungK-means-ClusteringEigengesichter / PCA
M. Giese: Lernmethoden in Computervision und Computer Grafik14 December 2002
Literatur
Cherkassky, V., Mulier, F. (1998). Learning From Data. John-Wiley & Sons Inc, New York.
Duda, R.O., Hart, P.E., Stork, D.G. (2001). Pattern Classification. John-Wiley & Sons Inc, New York.
Forsyth, D.A. & Ponce, J. (2003). Computer Vision: A modern Approach. Prentice-Hall. Upper Saddle River, NJ.
Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning Theory. Springer, Berlin.