Upload
others
View
15
Download
0
Embed Size (px)
Citation preview
11. Februar 2005 Alexander Gloye 2
Überblick
MotivationDatenaufbereitungMatrixfaktorisierungMethodenvergleichAlgorithmus zur NMFErweiterungenAnwendungsbeispieleZusammenfassung
11. Februar 2005 Alexander Gloye 5
Bild(de)kodierung
≈ ·
v ≈ W · hDatensatz Basis Kodierung
1
0
0
1
1
11. Februar 2005 Alexander Gloye 6
Matrix-FaktorisierungV ≈ V’ = W · H
·=
Datensatz Merkmalsbasis Kodierung
11. Februar 2005 Alexander Gloye 7
Matrixfaktorisierung
Ausgewählte Methoden
VektorquantisierungHauptkomponentenanalyseNicht-negative Matrixfaktorisierung
11. Februar 2005 Alexander Gloye 9
VektorquantisierungRepräsentative Vektorenzur Aufteilung des Raumsals Basis WHier Linde-Buzo-GrayZuordnung durch „nächsten Nachbarn“
20 Basisvektoren
11. Februar 2005 Alexander Gloye 10
VektorquantisierungKodie
rung h
Gew
ichte
teBas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 11
Hauptkomponentenanalyse
Eigenvektoren derKovarianzmatrix der Datenbilden die Basis W “Eigenfaces”
20 Basisvektoren
positivNullnegativ
11. Februar 2005 Alexander Gloye 12
HauptkomponentenanalyseKodie
rung h
Gew
ichte
te
Bas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 13
Nicht-negative Matrixfaktorisierung
Basis W und Kodierung H nur positive Werte oder NullDer Fehler V bzgl. V’ soll minimiert werden
20 Basisvektoren
11. Februar 2005 Alexander Gloye 14
Nicht-negative MatrixfaktorisierungKodie
rung h
Gew
ichte
teBas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 16
VektorquantisierungKodie
rung h
Gew
ichte
teBas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 17
HauptkomponentenanalyseKodie
rung h
Gew
ichte
teBas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 18
Nicht-negative MatrixfaktorisierungKodie
rung h
Gew
ichte
teBas
is W
Original v Rekonstruktion Wh
11. Februar 2005 Alexander Gloye 19
Algorithmus zur NMF
Expectation-Maximization (EM)-AlgorithmusW und H werden wechelseitig optimiertFür die Fehlerfunktion
Euklidische Distanz:
Kullback-Leibler Abweichung:
( )∑ ′−=′−ij
ijij vvVV 22
( ) ∑
′+−
′=′
ijijij
ij
ijij vv
vv
vVVD log||
11. Februar 2005 Alexander Gloye 21
Algorithmus zur NMF
∑
∑
∑
′←
←
′←
i i
iiaaa
jja
iaia
ai
iiaia
vv
whh
www
hvv
ww
µ
µµµ
µµ µ
µ
11. Februar 2005 Alexander Gloye 22
Anpassung von W
µµ µ
µa
i
iiaia h
vv
ww ∑ ′← a
i
iiaia hvvww′
←
∑←
jja
iaia w
ww
W Hh
a
a
i
V/V’v/v’
i
11. Februar 2005 Alexander Gloye 23
Anpassung von W
µµ µ
µa
i
iiaia h
vv
ww ∑ ′←
∑←
jja
iaia w
ww
W H
a
a
i
V/V’
i
µµ
11. Februar 2005 Alexander Gloye 24
Anpassung von HW H
a
a
i
V/V’
i
µµ
∑ ′←
i i
iiaaa vv
whhµ
µµµ
W ist normiert!
11. Februar 2005 Alexander Gloye 25
Gradientenabstieg
( ) ∑
′+−
′=′
ijijij
ij
ijij vv
vv
vVVD log||
1''
)'||(+−=
∂ vv
vvvD
'
1'
1
1'
1'
i
iiaia
i
iiaia
i
iiaiaia
i
iiaia
vvww
vvww
vvwww
vvww
←
−+←
−+←
−+← λ
∂
−+←')'||(
i
iiiaia v
vvDww λ
11. Februar 2005 Alexander Gloye 26
Algorithmus zur NMF
200 Iteration in Matlab implementiert.
20 Basisvektoren
11. Februar 2005 Alexander Gloye 27
Erweiterungen der NMF
Sparsame Repräsentation der BasisLokale Repräsentation der MerkmaleDurch Erweiterung der FehlerfunktionZum Beispiel Lokal NMF (LNMF)
( ) ∑∑∑ ++
′+−
′=′
ijij
ijkijik
ijijij
ij
ijij hwwvv
vv
vVVD 2log||
Kodierung nichtsparsam!
Merkmalsvektorenorthogonal.
11. Februar 2005 Alexander Gloye 28
Erweiterungen der NMF
25 Merkmale je 28×23 PixelLokal NMF (LNMF)Fisher NMF (FNMF)
NMF LNMF FNMF
Quelle: Wang u.a.
11. Februar 2005 Alexander Gloye 29
Anwendungsbeispiele
Semantische Merkmalsextraktionoder thematische Zuordnung ausTexten.Automatische Transkriptionpolyphoner Musik
11. Februar 2005 Alexander Gloye 30
Zusammenfassung
NMF ist eine Alternative zur VQ und PCA Leichte Interpretierbarkeit der MerkmaleEinfache Implementierung. Kodierungsvektor kann für Gesichts-erkennung, Handschrifterkennung usw. benutzt werden.Anwendungsbereich wächst
11. Februar 2005 Alexander Gloye 31
LiteraturDaniel Lee and Sebastian Seung: Learning the parts of objects by non-negative matrix factorization, Nature 401, 788-791 (1999).
Daniel Lee and Sebastian Seung: Algorithms for Non-negative Matrix Factorization,Advances in Neural Information Processing Systems, vol. 13, pp. 556-562, 2001.
Yuan Wang et al.: Fisher Non-negative Matrix Factorization for Learning Local Features,Asian Conference on Computer Vision, Korea, January 27-30, 2004.
Patrik Hoyer: Non-negative Matrix Factorization with Sparseness Constraints, Journal of Machine Learning Research 5:1457-1469, 2004.
Farial Shahnaz et al.: Document Clustering Using Nonnegative Matrix Factorization,To appear in the Journal on Information Processing & Management, Elsevier Preprint, August 2004.
Paris Smaragdis and Judith Brown: Non-Negative Matrix Factorization for Polyphonic Music Transcription, IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2003.