S. Hellbach Grundlagen der Informatik II SoSe 20171
Matrixzerlegungsalgorithmen in
der Mensch-Maschine-Interaktion
Dr.-Ing. Sven Hellbach
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20132
• Eigenwerte & -vektoren: revisited
• Wie sehen unsere Daten aus?
• Was wollen wir mit den Daten machen
• Über Ellipsen und Gaussverteilungen
• Kleiner Exkurs in die Statistik
• Jetzt geht‘s los: Ein Überblick:
– PCA
– ICA
– NMF
• So funktioniert‘s: Theorie & Praxis
– PCA, ICA, NMF
Inhalt
(not necessarily in order of appearance)
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20133
• Forschungsarbeiten Dariu Gavrila, Stefan Munder, Jan Giebel
(Daimler Research Ulm)
PCA - Fußgängererkennung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20134
PCA – Fußgängererkennung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20135
• Daten meist durch große Anzahl an einzelnen Features beschrieben
z.B. Bildpixel in Grauwertbild 640x320 = 204 800
• Einzelne Features werden als Dimension eines Vektorraumes
aufgefasst
• 1 Bild entspricht damit einem
Datenpunkt im Vektorraum
• Randbemerkung: Daten liegen sehr oft
auf niedrigdimensionaler Manigfaltigkeit
Wie sehen unsere Daten aus?
DA Nils Einecke, TU Ilmenau 2007
vT={g11,g12,…,g1w,…, gh1,gh2,…,ghw}
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20136
• Prinzipiell nahezu beliebige Anordnung
• Für viele Algorithmen (z.B. PCA) wird eine gaussförmige Verteilung
vorausgesetzt
• Kann durch Clusterung der Daten erreicht werden
Wie sehen unsere Daten aus?
DA Nils Einecke, TU Ilmenau 2007
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20137
Active Shape Model - Training
• Bestimmen der Form
Überführung der Formen in
einen Vektorraum
Principal Component Analysis
(PCA)
Ausrichten der Formen
aneinander
http://personalpages.manchaster.ac.uk/staff/timothy.f.cootes/Models/pdms.html
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20138
Active Shape Model - PCA
• Bestimmung eines Repräsentanten z.B. eine mittlere Form
• Berechnung der Distanz zwischen jeder Form und dem Repräsentanten:
N .. Anzahl der Templates
xi .. Vektorrepräsentation
des Templates i
• Aufstellen der Kovarianz-Matrix
Bsp.:
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/20139
• Bestimmung der Eigenvektoren und -werte der Kovarianzmatrix:
• Eigenvektoren stehen paarweise orthogonal aufeinander
• Eigenvektoren zeigen in Richtungder größten Varianzen
• Eigenwerte beschreiben die Größe der Varianz entlang des zugehörigen Eigenvektors:
• Durch Mittelwert- und Kovarianzberechnung wird angenommen, dass die Daten gaußverteilt sind.
Active Shape Model – PCA(2)
lk .. Eigenwert
pk .. Eigenvektor
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201310
• Jede gelernte Form lässt sich mit einem Gewichtsvektor, einer Eigenvektormatrix und dem Mittelwert errechnen.
Active Shape Model – PCA(2)
b1
b2
b3
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201311
• 1-dimensional:
• Mehr-dimensional (multivariat):
• Warum jetzt eigentlich Ellipsen?
Mehrdimensionale Gaussverteilung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201314
• Fragestellung: Wie sieht die Schnittfigur aus, wenn man mit einer
Ebene einen Kegel
schneidet?
• Kreis
• Ellipse
• Parabel
• Hyperbel
• Allgemein:
• Oder mal ganz anders:
Kegelschnitte
www.wikipedia.de
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201315
• Analytische Berechnung über det 𝐴 − λ ∙ 𝐼 = 0
• Führt zu charakteristischen Polynom n-ten Grades
• Nullstellen dieses Polynoms = Eigenwerte der Matrix
• Eigenvektoren ergeben sich durch Lösen des
Gleichungssystems 𝐴 − λ ∙ 𝐼 ∙ 𝑥 = 0
• Ist A symmetrisch, dann
– sind die Eigenvektoren paarweise orthogonal und
– die Eigenwerte sind reell
• In der Praxis ist n sehr groß → numerische Approximation
Eigenwertanalyse
Finckenstein,2006
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201316
• Der Vollständigkeit halber: B .. Basisübergangsmatrix
Eigenwerte und Kegelschnitte
Stramp,2012
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201317
• Hochdimensionale Datenräume u.U. problematisch für
nachfolgende Algorithmen (z.B. Klassifikatoren)
• Stichwort: Curse of dimensionality
• Eleminieren von Dimensionen, die keine wesentliche
Information kodieren
• Idee: Dimensionen mit kleiner Varianz Rauschen
PCA zur Dimensionsreduktion
DA Nils Einecke, TU Ilmenau 2007
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201318
• PCA: Principal Component Analysis
• PPCA: Probabilistic PCA
→ Generalisierung der PCA (nicht-Linearität)
• DPPCA: Dual PPCA
→ Trick: neue Sicht auf PPCA DPPCA
• GPLVM = Gaussian Process Latent Variable Model
→ Trick: Interpretation der Transformationen als Gauss-Prozesse
PCA und wie weiter?
GPLVM
PCA
PPCA DPPCA Linearer Spezialfall
Unverrauschter Spezialfall
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201319
PCA auf Bewegungsdaten
• PCA über intrinsisch repräsentierte Trajektorie
• Darstellung wieder im kartesischen Raum
x x
xy y
y
Einfluss der
1. Eigentrajektorie
Einfluss der
2. Eigentrajektorie
Einfluss der
3. Eigentrajektorie
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201320
• Cootes, Edwards & Taylor
ECCV 1998
• Kombination aus
– ASM
– Appearence Model
• Appearence Model:
Modellierung der Grauwert-
verteilung mittels PCA
PCA – Active Appearance Models
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201321
• L. Sirovich and M. Kirby (1987). "Low-dimensional procedure for the
characterization of human faces". Journal of the Optical Society of
America A 4 (3): 519–524.
PCA – Eigenfaces
Mittelwertgesicht
Ersten 20 Eigenfaces, zu den 20
größten Eigenwerten
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201322
• Vervollständigen und animieren von
menschlichen Formen
SCAPE-Körpermodell
Anguelov, D., Srinivasan, P., Koller, D.,
Thrun, S., Rodgers, J., Davis, J.:
SCAPE: Shape completion and animation
of people. In: SIGGRAPH (2005)
Figure 8: Motion capture animation. (a) Subject wearing motion capture markers (b) Motion capture markers in a single frame (c) An animation of a subjectbased on a motion capture sequence, with the markers from which the animation was derived superimposed on the meshes. (d) An example of motion transferto a different subject in our data set. (e) Animation based on motion capture, but where we change the body shape parameters in PCA space as we movethrough the sequence.
is used for all people, we do not capture the fact that more muscularpeople are likely to exhibit greater muscle deformation than others,and, conversely, that muscle deformation may be obscured in peo-ple with significant body fat. To capture these correlations, a moreexpressive model would be needed.
Our current approach requires a set of scans of a single personin different poses to learn the space of pose deformations. Oncewe have done this, we can use scans of different people in differentposes to learn the space of body shapes. We are currently not pro-viding a method to learn both spaces from a random mix of scansfrom different people in different poses. Our assumption on thetraining set structure is not particularly restrictive, and it simplifiesour data collection and learning procedures. We could try to learnour model from a non-uniform data set, by iterating between esti-mating either the pose or the body shape model while keeping theother one fixed. This process would result in a local minimum in thejoint space of deformations. We cannot predict how good this localminimum would be; it depends specifically on the training data weare given, and on the search method used.
The pose deformation in our model is determined by linear re-gression from adjacent joint angles. We found that this assump-tion provides surprisingly good animation results, and simplifies thetask of shape completion. For many instances of partial view com-pletion, a more accurate model may not be necessary, because oursolution is allowed to deform outside of SCAPE space in order to
fit the observed surface. Thus, partial view data can correct someof the (fairly small) errors resulting from the assumption of a lin-ear regression model. When the SCAPE model is used purely foranimation, a more complex model may be required in some cases.Extending our approach with a non-linear regression method is anarea of our future work.
The SCAPE model is focused on representing muscle deforma-tions resulting from articulated body motion. Deformations result-ing from other factors are not encoded. One such factor is deforma-tion resulting from pure muscle activity. Thus, the model is not ex-pressive enough to distinguish between a flexed bicep muscle and alax one in cases where the joint angle is the same. For the same rea-son, it is not appropriate to deal with faces, where most of the mo-tion is purely muscle-based. Another factor leading to muscle de-formation is tissue perturbations due to motion (e.g., fat wiggling),which our model also does not represent.
Currently, our framework includes no prior over poses. Thus,when encountering occlusions, we cannot use the observed positionof some body parts to constrain the likely location of others. Ourmodel can easily be extended to encompass such a prior, in a mod-ular way. For example, in the case of static scans, a kinematic priorsuch as that of Popovic et al.[2004] could simply be introduced asan additional term into our optimization. When animating dynamicsequences, we can use a tracking algorithm (e.g., a Kalman filter) togenerate a pose prior for any frame given all or part of the observa-
Figure 8: Motion capture animation. (a) Subject wearing motion capture markers (b) Motion capture markers in a single frame (c) An animation of a subjectbased on a motion capture sequence, with the markers from which the animation was derived superimposed on the meshes. (d) An example of motion transferto a different subject in our data set. (e) Animation based on motion capture, but where we change the body shape parameters in PCA space as we movethrough the sequence.
is used for all people, we do not capture the fact that more muscularpeople are likely to exhibit greater muscle deformation than others,and, conversely, that muscle deformation may be obscured in peo-ple with significant body fat. To capture these correlations, a moreexpressive model would be needed.
Our current approach requires a set of scans of a single personin different poses to learn the space of pose deformations. Oncewe have done this, we can use scans of different people in differentposes to learn the space of body shapes. We are currently not pro-viding a method to learn both spaces from a random mix of scansfrom different people in different poses. Our assumption on thetraining set structure is not particularly restrictive, and it simplifiesour data collection and learning procedures. We could try to learnour model from a non-uniform data set, by iterating between esti-mating either the pose or the body shape model while keeping theother one fixed. This process would result in a local minimum in thejoint space of deformations. We cannot predict how good this localminimum would be; it depends specifically on the training data weare given, and on the search method used.
The pose deformation in our model is determined by linear re-gression from adjacent joint angles. We found that this assump-tion provides surprisingly good animation results, and simplifies thetask of shape completion. For many instances of partial view com-pletion, a more accurate model may not be necessary, because oursolution is allowed to deform outside of SCAPE space in order to
fit the observed surface. Thus, partial view data can correct someof the (fairly small) errors resulting from the assumption of a lin-ear regression model. When the SCAPE model is used purely foranimation, a more complex model may be required in some cases.Extending our approach with a non-linear regression method is anarea of our future work.
The SCAPE model is focused on representing muscle deforma-tions resulting from articulated body motion. Deformations result-ing from other factors are not encoded. One such factor is deforma-tion resulting from pure muscle activity. Thus, the model is not ex-pressive enough to distinguish between a flexed bicep muscle and alax one in cases where the joint angle is the same. For the same rea-son, it is not appropriate to deal with faces, where most of the mo-tion is purely muscle-based. Another factor leading to muscle de-formation is tissue perturbations due to motion (e.g., fat wiggling),which our model also does not represent.
Currently, our framework includes no prior over poses. Thus,when encountering occlusions, we cannot use the observed positionof some body parts to constrain the likely location of others. Ourmodel can easily be extended to encompass such a prior, in a mod-ular way. For example, in the case of static scans, a kinematic priorsuch as that of Popovic et al.[2004] could simply be introduced asan additional term into our optimization. When animating dynamicsequences, we can use a tracking algorithm (e.g., a Kalman filter) togenerate a pose prior for any frame given all or part of the observa-
Figure 8: Motion capture animation. (a) Subject wearing motion capture markers (b) Motion capture markers in a single frame (c) An animation of a subjectbased on a motion capture sequence, with the markers from which the animation was derived superimposed on the meshes. (d) An example of motion transferto a different subject in our data set. (e) Animation based on motion capture, but where we change the body shape parameters in PCA space as we movethrough the sequence.
is used for all people, we do not capture the fact that more muscularpeople are likely to exhibit greater muscle deformation than others,and, conversely, that muscle deformation may be obscured in peo-ple with significant body fat. To capture these correlations, a moreexpressive model would be needed.
Our current approach requires a set of scans of a single personin different poses to learn the space of pose deformations. Oncewe have done this, we can use scans of different people in differentposes to learn the space of body shapes. We are currently not pro-viding a method to learn both spaces from a random mix of scansfrom different people in different poses. Our assumption on thetraining set structure is not particularly restrictive, and it simplifiesour data collection and learning procedures. We could try to learnour model from a non-uniform data set, by iterating between esti-mating either the pose or the body shape model while keeping theother one fixed. This process would result in a local minimum in thejoint space of deformations. We cannot predict how good this localminimum would be; it depends specifically on the training data weare given, and on the search method used.
The pose deformation in our model is determined by linear re-gression from adjacent joint angles. We found that this assump-tion provides surprisingly good animation results, and simplifies thetask of shape completion. For many instances of partial view com-pletion, a more accurate model may not be necessary, because oursolution is allowed to deform outside of SCAPE space in order to
fit the observed surface. Thus, partial view data can correct someof the (fairly small) errors resulting from the assumption of a lin-ear regression model. When the SCAPE model is used purely foranimation, a more complex model may be required in some cases.Extending our approach with a non-linear regression method is anarea of our future work.
The SCAPE model is focused on representing muscle deforma-tions resulting from articulated body motion. Deformations result-ing from other factors are not encoded. One such factor is deforma-tion resulting from pure muscle activity. Thus, the model is not ex-pressive enough to distinguish between a flexed bicep muscle and alax one in cases where the joint angle is the same. For the same rea-son, it is not appropriate to deal with faces, where most of the mo-tion is purely muscle-based. Another factor leading to muscle de-formation is tissue perturbations due to motion (e.g., fat wiggling),which our model also does not represent.
Currently, our framework includes no prior over poses. Thus,when encountering occlusions, we cannot use the observed positionof some body parts to constrain the likely location of others. Ourmodel can easily be extended to encompass such a prior, in a mod-ular way. For example, in the case of static scans, a kinematic priorsuch as that of Popovic et al.[2004] could simply be introduced asan additional term into our optimization. When animating dynamicsequences, we can use a tracking algorithm (e.g., a Kalman filter) togenerate a pose prior for any frame given all or part of the observa-
Figure 8: Motion capture animation. (a) Subject wearing motion capture markers (b) Motion capture markers in a single frame (c) An animation of a subjectbased on a motion capture sequence, with the markers from which the animation was derived superimposed on the meshes. (d) An example of motion transferto a different subject in our data set. (e) Animation based on motion capture, but where we change the body shape parameters in PCA space as we movethrough the sequence.
is used for all people, we do not capture the fact that more muscularpeople are likely to exhibit greater muscle deformation than others,and, conversely, that muscle deformation may be obscured in peo-ple with significant body fat. To capture these correlations, a moreexpressive model would be needed.
Our current approach requires a set of scans of a single personin different poses to learn the space of pose deformations. Oncewe have done this, we can use scans of different people in differentposes to learn the space of body shapes. We are currently not pro-viding a method to learn both spaces from a random mix of scansfrom different people in different poses. Our assumption on thetraining set structure is not particularly restrictive, and it simplifiesour data collection and learning procedures. We could try to learnour model from a non-uniform data set, by iterating between esti-mating either the pose or the body shape model while keeping theother one fixed. This process would result in a local minimum in thejoint space of deformations. We cannot predict how good this localminimum would be; it depends specifically on the training data weare given, and on the search method used.
The pose deformation in our model is determined by linear re-gression from adjacent joint angles. We found that this assump-tion provides surprisingly good animation results, and simplifies thetask of shape completion. For many instances of partial view com-pletion, a more accurate model may not be necessary, because oursolution is allowed to deform outside of SCAPE space in order to
fit the observed surface. Thus, partial view data can correct someof the (fairly small) errors resulting from the assumption of a lin-ear regression model. When the SCAPE model is used purely foranimation, a more complex model may be required in some cases.Extending our approach with a non-linear regression method is anarea of our future work.
The SCAPE model is focused on representing muscle deforma-tions resulting from articulated body motion. Deformations result-ing from other factors are not encoded. One such factor is deforma-tion resulting from pure muscle activity. Thus, the model is not ex-pressive enough to distinguish between a flexed bicep muscle and alax one in cases where the joint angle is the same. For the same rea-son, it is not appropriate to deal with faces, where most of the mo-tion is purely muscle-based. Another factor leading to muscle de-formation is tissue perturbations due to motion (e.g., fat wiggling),which our model also does not represent.
Currently, our framework includes no prior over poses. Thus,when encountering occlusions, we cannot use the observed positionof some body parts to constrain the likely location of others. Ourmodel can easily be extended to encompass such a prior, in a mod-ular way. For example, in the case of static scans, a kinematic priorsuch as that of Popovic et al.[2004] could simply be introduced asan additional term into our optimization. When animating dynamicsequences, we can use a tracking algorithm (e.g., a Kalman filter) togenerate a pose prior for any frame given all or part of the observa-
Figure 8: Motion capture animation. (a) Subject wearing motion capture markers (b) Motion capture markers in a single frame (c) An animation of a subjectbased on a motion capture sequence, with the markers from which the animation was derived superimposed on the meshes. (d) An example of motion transferto a different subject in our data set. (e) Animation based on motion capture, but where we change the body shape parameters in PCA space as we movethrough the sequence.
is used for all people, we do not capture the fact that more muscularpeople are likely to exhibit greater muscle deformation than others,and, conversely, that muscle deformation may be obscured in peo-ple with significant body fat. To capture these correlations, a moreexpressive model would be needed.
Our current approach requires a set of scans of a single personin different poses to learn the space of pose deformations. Oncewe have done this, we can use scans of different people in differentposes to learn the space of body shapes. We are currently not pro-viding a method to learn both spaces from a random mix of scansfrom different people in different poses. Our assumption on thetraining set structure is not particularly restrictive, and it simplifiesour data collection and learning procedures. We could try to learnour model from a non-uniform data set, by iterating between esti-mating either the pose or the body shape model while keeping theother one fixed. This process would result in a local minimum in thejoint space of deformations. We cannot predict how good this localminimum would be; it depends specifically on the training data weare given, and on the search method used.
The pose deformation in our model is determined by linear re-gression from adjacent joint angles. We found that this assump-tion provides surprisingly good animation results, and simplifies thetask of shape completion. For many instances of partial view com-pletion, a more accurate model may not be necessary, because oursolution is allowed to deform outside of SCAPE space in order to
fit the observed surface. Thus, partial view data can correct someof the (fairly small) errors resulting from the assumption of a lin-ear regression model. When the SCAPE model is used purely foranimation, a more complex model may be required in some cases.Extending our approach with a non-linear regression method is anarea of our future work.
The SCAPE model is focused on representing muscle deforma-tions resulting from articulated body motion. Deformations result-ing from other factors are not encoded. One such factor is deforma-tion resulting from pure muscle activity. Thus, the model is not ex-pressive enough to distinguish between a flexed bicep muscle and alax one in cases where the joint angle is the same. For the same rea-son, it is not appropriate to deal with faces, where most of the mo-tion is purely muscle-based. Another factor leading to muscle de-formation is tissue perturbations due to motion (e.g., fat wiggling),which our model also does not represent.
Currently, our framework includes no prior over poses. Thus,when encountering occlusions, we cannot use the observed positionof some body parts to constrain the likely location of others. Ourmodel can easily be extended to encompass such a prior, in a mod-ular way. For example, in the case of static scans, a kinematic priorsuch as that of Popovic et al.[2004] could simply be introduced asan additional term into our optimization. When animating dynamicsequences, we can use a tracking algorithm (e.g., a Kalman filter) togenerate a pose prior for any frame given all or part of the observa-
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201323
• Frei verfügbarer Datensatz des Max-Planck-Instituts für Informatik
• 520 registrierte 3D-Scans von 114 Personen
(59 männlich + 55 weiblich, 17-61 Jahre)
• Pro Person 9 zufällig ausgewählte Posen aus insgesamt 34 möglichen
Posen
• Wavefront Technologies OBJ-Dateiformat
Datensatz
N. Hasler, C. Stoll, M. Sunkel, B. Rosenhahn, H.-P. Seidel: A
Statistical Model of Human Pose and Body Shape, Computer
Graphics Forum. Eurographics (2009)
v 0.001888 -0.058120 -0.069146
v 0.007348 -0.066757 -0.062134
...
v 0.198797 -0.139671 -0.912381
v 0.215532 -0.113257 -0.913934
f 2 1 3557
f 6129 6133 6131
...
f 6436 6445 6447
f 6436 6439 6445
f 6446 6445 6430
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201324
• Modellerstellung in Python (Version 2.7)
– Einlesen des Datensatzes (liegt als Sammlung von .obj-File vor)
• Trick für heute: Import über zuvor erzeugtes HDF5-File
(Hierarchical Data Format Version 5)
Umsetzung Modellerzeugung
import h5py
...
class objData(HasTraits):
...
def loadData(self, filename):
f = h5py.File(filename, 'r+')
self.setData(f['verts'][...], f['tris'][...])
def setData(self, verts, triangles):
self.vertices = verts
self.triangles = triangles
self.n_example_high=self.vertices.shape[0]-1
...
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201325
• Modellerstellung in Python
– Erstellen des Modells auf Basis der Daten
• scikit-learn Machine Learning in Python enthält PCA
Implementierung
– sklearn.decomposition.PCA:
• NumPy: Package für numerisches wissenschaftliches
Rechnen
Umsetzung Modellerzeugung
import numpy as np
from sklearn.decomposition import PCA
...
class objData(HasTraits):
...
pca = PCA(svd_solver='full')
def computeModel(self):
dims = self.vertices.shape
X = self.vertices.reshape([dims[0], dims[1] * dims[2]])
self.pca.fit(X)
self.factor = np.zeros([1,self.pca.components_.shape[0]])
...
[<sample>, <vertex>, <dimension>]
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201326
• Modellerstellung in Python
– Visualisieren der Daten zum Verifizieren des Modells
• MayaVi zur Datenvisualisierung
• Traits / TraitsUI: GUI-Komponenten in Zusammenhang mit MayaVi
Umsetzung Modellerzeugung
import numpy as np
...
class objData(HasTraits):
...
@on_trait_change('n_component_factor')
def updateModel(self):
...
self.factor[0,component] = 3 *
np.sqrt(self.pca.explained_variance_[component]) *
self.n_component_factor
sample=self.pca.mean_ + np.dot(self.factor, self.pca.components_)
...
...
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201328
• Ausgangpunkt ist eine Menge von n Trainingsdaten v1 , … , vn
(in vektorieller Form), z.B.: vi = (x0 , y0 ,…, xm-1 , ym-1)T
• Ergebnis sollen r Basiskomponenten sein,
die durch (gewichtete) Linearkombination wieder die Ausgangsdaten
beschreiben
• Die Basiskomponenten sollen alle Trainingsdaten durch
unterschiedliche Wichtung beschreiben
Matrixzerlegung zur
Basisdekomposition
vi w1 wr≈ …+ +
v1 vn… w1 wr
… · a1 an…≈
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201329
Matrixzerlegung zur Basisdekomposition
Interpretation
• PCA:
• ICA:
• NMF:
Trainingsdaten Matrix der
Eigenvektoren
Punkte im PCA
Koordinatensystem
Trainingsdaten Beschreibung
der Quellen
(Independent
Components)
Überlagerung
der Quellen
Trainingsdaten Nicht negative
Zerlegung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201330
ICA: Was wollen wir eigentlich?
Stone, TRENDS 2002
• Modellannahme: Beobachtung von n Signalen 𝑥1, … , 𝑥𝑛, die linear
aus n Quellen 𝑠1, … , 𝑠𝑛 überlagert sind:
also:
• Wir wollen‘s genau anders herum:
• Blind Source Separation Problem
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201331
• Der eigentliche ICA Algorithmus arbeitet nur auf mittelwertfreien,
„weißen“ Daten
1. Mittelwertfreiheit: Centering
Von jedem Datenpunkt wird der Mittelwert abgezogen
𝑥𝑖 = 𝑥𝑖 − 𝜇 mit 𝜇 =1
𝑛
𝑖=1
𝑛
𝑥𝑖
2. Kovarianzematrix=Einheitsmatrix: Whitening
Das kennen wir schon!
1. Rechnen einer PCA auf der Kovarianzmatrix und
2. Transformation der Daten in den PCA Raum
𝒙 = 𝑬𝑫− Τ1 2𝑬𝑻𝒙
E .. Orthogonale Matrix der Eigenvektoren
D .. Diagonalmatrix der Eigenwerte
ICA: Vorverarbeitung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201332
• Statistische Unabhängigkeit:
Zwei Wkt.-Variablen X und Y sind unabhängig gdw. gilt
𝑝 𝑋, 𝑌 = 𝑝 𝑋 ∙ 𝑝 𝑌
• Wenn zwei Variablen unabhängig sind, sind sie auch unkorreliert,
aber nicht umgekehrt
• Zentraler Grenzwertsatz: Die Verteilung der Summe von
unabhängigen Variablen konvergiert gegen eine Gaussverteilung
• Die „Gausshaftigkeit“ nimmt also zu, die Unabhängigkeit ab
• Annahme für die ICA: Nicht-Gausshaftigkeit = Unabhängigkeit
Einschub: Ein bisschen Statistik
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201333
• Wir brauchen ein Maß: die Negentropie
• Entropie:
𝐻(𝑌)) = −𝑃 𝑌 = 𝑎𝑖 log𝑃(𝑌 = 𝑎𝑖)
• Maß für den Informationsgehalt einer Verteilung
• Negentropie: 𝐽 𝑦 = 𝐻 𝑦𝑔𝑎𝑢𝑠𝑠 − 𝐻(𝑦)
• Schön, aber schwer zu berechnen, daher Approximation:
𝐽 𝑦 ≈
𝑖=1
𝑝
𝑘𝑖 𝐸 𝐺𝑖 𝑦 − 𝐸 𝐺𝑖 𝑦𝑔𝑎𝑢𝑠𝑠2mit𝑦𝑔𝑎𝑢𝑠𝑠~N(∙,∙)
• Sinnvolle Wahl für G: 𝐺1(𝑢) =1
𝑎1log cosh 𝑎1𝑢
𝐺2 𝑢 = −exp −𝑢2
2
Einschub: Ein bisschen Statistik
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201334
1. Wähle einen initialen (z.B. zufälligen) Gewichtsvektor
2. Optimierungsschritt:
mit g als Ableitung von G (siehe Negentropie)
3. Normalisierung:
4. Wiederhole ab 2 bis Konvergenz:
• Konvergenzmaß ist Negentropie mit den
üblichen Abbruchkriterien:
1. Negentropie klein genug
2. Änderung der Negentropie klein genug
• Optimierungsschritt ist eigentlich ein
Gradientenabstieg
Durch Vereinfachung erhält man
multiplikative Updateregel
FastICA
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201335
ICA: Anwendungen
Stone, TRENDS 2002
Tritionia diomeda
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201336
• Klassisches Blind Source Separation Problem
• http://research.ics.aalto.fi/ica/cocktail/cocktail_en.cgi
ICA: Cocktail Party
A W
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201337
• Bartlett et al.: Face recognition by independent component analysis. IEEE Trans. On Neural Networks. 2002
ICA – Gesichtserkennung
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201338
Motion Decomposition: Basic Idea
• Oriented on Piano Model
• Decomposing motion trajectories into basis primitives
(like an alphabet, or music notes)
• Decomposition based on
training examples
• Observed motion is represented
by „activating“ the basis primitives
at a certain position and a
certain time
Cemgil, A.; Kappen, B. & Barber, D. A generative
model for music transcription. TASLP, 2006
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201339
Representing the Motion Information
• Transfer each dimension of trajectory into grid-based
representation
• Data can be interpreted as image ) apply NMF as known from
images
• Advantage: Overlapping of basis primitives leads to
– Multiple hypotheses,
– For which their relevance is represented by their intensity value
t
x
t
y
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201340
Given:
training
data V
Demanded: Set of basis primitives W
Goal: Reconstructing the training data using the basis primitives
For each basis primitive the corresponding
activities H are computed
Phase I: Training
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201341
Algorithm – A closer look
• Standard NMF Approach with
multiplicative update rule
• Alternating adaption of basis primitives W and activation H until
convergence
• Parameter l controls sparseness of activities to avoid
– Trivial solutions
– redundant basis primitives
• Weight matrix W needs to be normalized to compute unique
solutions
• Transformation matrix T allows arbitrary placement of basis
primitives W
• In that way, basis primitives can be „sticked“ together
Lee, D.D., Seung, H.S.: Algorithms for non-
negative matrix factorization. NIPS 2001
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201342
Given:
Observation V
Basis primitives W (from training)
Demanded: Activities H (chronology of basis primitives)
Goal: Reconstructing the observation
using the basis primitives
Initialization by using the shifted
activities of the previous time step
Phase IIa: Observation
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201343
Given:
Activities H
Basis primitives W (from training)
Demanded: Prediction
Extending the reconstruction window R
to gain a prediction horizon P (about the width of the basis primitives)
Exploits the overlap of the basis primitives
Phase IIb: Prediction
R P Ground
truth
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201344
• NMF mit Multiplikativer Update-Regel
• Alternativen:
– Alternating Least Squares Algorithms
– Gradient projection method
NMF – Algorithmus
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201345
• Comparing 3 prediction results
• Prediction starts at certain time
step (green line)
• Using standard Kalmanfilter as
reference
a) Using position and velocity within the
model
b) Using position, velocity and
acceleration within the model
• No sensor update is applied from
the start of the prediction
• NMF results closer to actual
characteristics
a)
b)
Can we compare?
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201346
Bach’s Fuge Nr. XVI in G-Moll
t
Fre
qu
en
z
NMF
• Smaragdis: Non-Negative Matrix Factorization for Polyphonic Music
Transcription; IEEE Workshop on Applications of Signal Processing to
Audio and Acoustics, 2003
NMF – Beispiele
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201347
• Brunet JP, Tamayo P, Golub TR, Mesirov JP.: Metagenes and
molecular pattern discovery using matrix factorization. Proc Natl
Acad Sci U S A. 2004 Mar 23;101(12):4164-9. Epub 2004 Mar 11.
• Metagene: A pattern of gene expression. Not an actual gene.
NMF – Genanalyse
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201348
• D. D. Lee and H. S. Seung: Learning the parts of objects with
nonnegative matrix factorization. Nature 401, 788 (1999).
NMF – Gesichtsanalyse
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201349
• PCA:
– Eigenwertzerlegung der Matrix V
– Eigenvektoren bilden Achsen des dekorrelierten
Koordinatensystems
• ICA:
– Ziele:
• Statistische Unabhängigkeit
• Minimierung der Ähnlichkeit zu einer Normalverteilung
• NMF:
– Forderung: Nichtnegativität
– Aufstellen einer Energiefunktion
• Üblicherweise: Multiplikative Updateregel
• Gradientenabstieg mit „Projection Step“
• Alternating Least Square
– Kann um beliebige Forderungen erweitert werden
Matrixzerlegung zur Basisdekomposition
Prinzip
S. Hellbach Matrixzerlegungsalgorithmen in der Mensch-Maschine-Interaktion WS 2012/201350
• BERRY, M. W.; BROWNE, M.; LANGVILLE, A. N.; PAUCA, V. P. & PLEMMONS, R. J.:
Algorithms and applications for approximate nonnegative matrix factorization. In:: . :
Computational Statistics and Data Analysis., 2006, S. 155--173
• FINCKENSTEIN, K. G. F.; LEHN, J.; SCHELLHAAS, H. & WEGMANN, H.: Eigenwert-Theorie
und quadratische Formen: Teubner. : Arbeitsbuch Mathematik für Ingenieure., 2006, S.
144-155
• HYVÄRINEN, A. & OJA, E.: Independent Component Analysis: A Tutorial,
http://cis.legacy.ics.tkk.fi/aapo/papers/IJCNN99_tutorialweb/IJCNN99_tutorial3.html
• LAU, D. & LAU, D.: Eigenwerte, Eigenvektoren und Normalformen von Matrizen: Springer
Berlin Heidelberg. : Algebra und Diskrete Mathematik 1., 2011, S. 253-295
• LEE, D. D. & SEUNG, H. S.: Learning the parts of objects by non-negative matrix
factorization. In: Nature 401 (1999), Nr. 6755, S. 788--791
• STONE, J. V.: Independent component analysis: an introduction. In: Trends in Cognitive
Sciences 6 (2002), Nr. 2, S. 59--64
• STRAMPP, W. & STRAMPP, W.: Eigenwerte und Eigenvektoren: Vieweg+Teubner Verlag. :
Höhere Mathematik 1., 2012, S. 219-242
Suggested Reading