Embed Size (px)
Citation preview
Performanz und Probleme von Sparse Embeddings
Katja Markert (einige Folien von Michael Staniek)
Institut fur ComputerlinguistikUni Heidelberg
markertcluni-heidelbergde
May 14 2019
Bisher und heute
1 Bisher Assoziationsmaszlige und Sparse Embeddingsspecies computer animal
cat 59 5 304carnivore 21 1 21
feline 2 0 5airport 4 12 2
2 Bisher Distanzen und Ahnlichkeitsmaszlige zurWortahnlichkeitsbestimmung
Paar cossim
cat carnivore 0828cat feline 098cat airport 0227
3 Jetzt (Wiederholung aus ECL) Umwandlung vonfrequenzbasierten Kokkurrenzmatrizen in PPMI-Matrizen
4 Jetzt Performanz und Probleme von sparse embeddings5 Nachste Folien Vorbereitung von Singular Value Decomposition
mit Hintergrund Unterraumen und Matrizen2
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
3
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
4
PPMI Beispiel I
Term-Term-Matrix mit Frequenzen (aus Jurafsky und Martin Edition 3)
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
Die Randhaufigkeiten entsprechen nicht den Unigramfrequenzender Worter (Warum nicht)
Im Unterschied zur Kollokationsberechnung fur Bigrammeenspricht die Gesamthaufigkeit N der Beobachtungen (hier 19)im Normalfall nicht der Korpusgroszlige (Warum nicht)
5
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Bisher und heute
1 Bisher Assoziationsmaszlige und Sparse Embeddingsspecies computer animal
cat 59 5 304carnivore 21 1 21
feline 2 0 5airport 4 12 2
2 Bisher Distanzen und Ahnlichkeitsmaszlige zurWortahnlichkeitsbestimmung
Paar cossim
cat carnivore 0828cat feline 098cat airport 0227
3 Jetzt (Wiederholung aus ECL) Umwandlung vonfrequenzbasierten Kokkurrenzmatrizen in PPMI-Matrizen
4 Jetzt Performanz und Probleme von sparse embeddings5 Nachste Folien Vorbereitung von Singular Value Decomposition
mit Hintergrund Unterraumen und Matrizen2
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
3
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
4
PPMI Beispiel I
Term-Term-Matrix mit Frequenzen (aus Jurafsky und Martin Edition 3)
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
Die Randhaufigkeiten entsprechen nicht den Unigramfrequenzender Worter (Warum nicht)
Im Unterschied zur Kollokationsberechnung fur Bigrammeenspricht die Gesamthaufigkeit N der Beobachtungen (hier 19)im Normalfall nicht der Korpusgroszlige (Warum nicht)
5
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
3
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
4
PPMI Beispiel I
Term-Term-Matrix mit Frequenzen (aus Jurafsky und Martin Edition 3)
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
Die Randhaufigkeiten entsprechen nicht den Unigramfrequenzender Worter (Warum nicht)
Im Unterschied zur Kollokationsberechnung fur Bigrammeenspricht die Gesamthaufigkeit N der Beobachtungen (hier 19)im Normalfall nicht der Korpusgroszlige (Warum nicht)
5
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
4
PPMI Beispiel I
Term-Term-Matrix mit Frequenzen (aus Jurafsky und Martin Edition 3)
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
Die Randhaufigkeiten entsprechen nicht den Unigramfrequenzender Worter (Warum nicht)
Im Unterschied zur Kollokationsberechnung fur Bigrammeenspricht die Gesamthaufigkeit N der Beobachtungen (hier 19)im Normalfall nicht der Korpusgroszlige (Warum nicht)
5
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel I
Term-Term-Matrix mit Frequenzen (aus Jurafsky und Martin Edition 3)
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
Die Randhaufigkeiten entsprechen nicht den Unigramfrequenzender Worter (Warum nicht)
Im Unterschied zur Kollokationsberechnung fur Bigrammeenspricht die Gesamthaufigkeit N der Beobachtungen (hier 19)im Normalfall nicht der Korpusgroszlige (Warum nicht)
5
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI Beispiel II
Term-Term-Matrix mit Frequenzen
computer data pinch result sugarapricot 0 0 1 0 1 2pineapple 0 0 1 0 1 2digital 2 1 0 1 0 4information 1 6 0 4 0 11
3 7 2 5 2 19
ppmi(informationdata) = max(log2
619
1119 middot
719
0) = 057
ppmi(informationcomputer) = max(log2
119
1119 middot
319
0) = max(log21933
0) = 0
ppmi(apricotcomputer) = max(log2
019
219 middot
319
0) = max(log2 00) = 0
ppmi(apricotpinch) = max(log2
119
219 middot
219
0) = 2256
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI-Beispiel III
Term-Term-Matrix mit PPMI
computer data pinch result sugarapricot 0 0 225 0 225pineapple 0 0 225 0 225digital 166 0 0 0 0information 0 057 0 047 0
Ein Problem PPMI uberschatzt seltene Kontextworter (siehe pinch)Wie lost man das (Smoothing siehe Jurafsky und Martin Kapitel 6)
7
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
PPMI-Beispiel IV Laplace Smoothing
Originalmatrix
computer data pinch result sugarapricot 0 0 1 0 1pineapple 0 0 1 0 1digital 2 1 0 1 0information 1 6 0 4 0
Nach Add-2 Smoothing
computer data pinch result sugarapricot 2 2 3 2 3pineapple 2 2 3 2 3digital 4 3 2 3 2information 3 8 2 6 2
8
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ubung
Konvertiere unsere Standardmatrix in PPMI
species computer animalcat 59 5 304
carnivore 21 1 21feline 2 0 5
airport 4 12 2
9
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Losung
species computer animalcat 59 5 304 368
carnivore 21 1 21 43feline 2 0 5 7
airport 4 12 2 1886 18 332 436
species computer animalcat 0 0 0111
carnivore 13 0 0feline 052 0 0
airport 016 4 0
Warum hat dies nicht gut funktioniert
10
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
11
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Beispielperformanz
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Fur WordSim353 Stopworter gefiltered Korpus 4 MilliardenWebdokumente (16 Terawords) Assoziationsmaszlig χ2
Fenstergroszlige Spearman Rank1 0644 0656 064
1 Warum andert die Fenstergroszlige so wenig2 Warum sind Ihre Ergebnisse im Ubungsblatt so viel schlechter
12
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Lernkurve (Learning curve)
Agirre et al (NAACL 2009) A study on similarity and relatedness using distributional
and wordnet-based approaches
Abhangigkeit der Performanz von Korpusgroszlige
13
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ubersicht
1 Umwandlung der Frequenzmatrizen in PPMI-Matrizen
2 Performanz von sparse embeddings
3 Probleme bei Sparse Embeddings und die Idee der Singular ValueDecomposition
14
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Probleme bei sparse embeddings
Overfitting durch zu viele Tokens mit geringen Frequenzen AlleAssoziationsmaszlige haben Probleme mit seltenen Wortern
Zu viele falschlich unterschiedliche Dimensionen
Nasa kommt mit cosmonaut vorRoscosmos kommt mit astronaut vorcosmonaut und astronaut sind unterschiedliche DimensionenDamit lasst sich die ldquoAhnlichkeit zwischen NASA und roscosmosschwer fassen
Beispiel aus erster Vorlesung
astronaut cosmonaut tomatoNASA 4 0 1
Roscosmos 0 4 0avocado 0 0 7
salad 0 1 10
15
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Ziel
Approximiere den n-dimensionalen Raum mit wenigerDimensionen
Indem wir Achsen rotieren so dass wir einen Raum erhalten indem die erste Dimension die meiste Varianz in den Originaldatenerklart
16
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Motivation fur SVD bzw SVD ohne Details
Gegeben Matrix M der Dimension mtimesn
Gesucht Matrix M mit der Dimension mtimesn die ahnlich zu M istaber niedrigeren Rang hat
Methode Singular Value Decomposition (SVD) Zerlege M indrei Matrizen Mmtimesn = UmtimesmΣmtimesnV T
ntimesn die besonders schoneEigenschaften haben
Methode Aus dieser Zerlegung konnen nun geschickt unwichtigeDimensionen ldquoherausgenommenrdquo werden um dichte Matrizenniedrigeren Ranges zu erhalten mit denen bessereAhnlichkeitsberechnungen moglich sind
17
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
SVD Illustration
Aus Manning et al Figure 181
Da bei m gt n die letzten Zeilen von Σ Nullzeilen sind fallen die letztenSpalten von U nicht ins Gewicht und man kann diese ignorieren und zB U auf mtimesmin(mn) beschranken
18
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
SVD Beispiel
Eine Wort-Dokument-Matrix M aus dem R5times3
d1 d2 d3ship 1 1 0boat 0 0 1
ocean 1 0 1motor 1 0 1wood 0 1 0
cossim(shipboat) = 0
cossim(shipocean) =12
cossim(boatocean) =1radic2
= 07
19
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
SVD Beispiel
Die Matrix U ist eine 5times3 Matrix
ship minus041 07 024boat minus029 minus033 minus072
ocean minus061 minus02 014motor minus061 minus02 014wood minus01 057 minus062
Eine Reihe pro Wort
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
Spalten sind nach Hohe der Varianz geordnet
20
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
SVD Beispiel
Die Matrix Σ ist eine Diagonalmatrix der Dimension 3times3
227 0 00 149 00 0 078
Σ enthalt die Wurzeln der Eigenwerte von MMT in absteigenderReihenfolge Je groszliger desto wichtiger ist eine Dimension
21
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Die Matrix V T
V T ist eine 3times3-Matrix mit einer Spalte pro Dokument
d1 d2 d3minus072 minus023 minus066019 085 minus05067 minus048 minus056
Eine Spalte pro Dokument
Matrix ist orthonormal dh die Spaltenvektoren haben alle dieLange 1 und stehen alle aufeinander senkrecht (Skalarproduktzweier Spaltenvektoren =0)
22
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Stimmt die Zerlegung
Berechnen wir UΣV T
minus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 078
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0187minus0658 minus049 minus056minus138 minus0298 01092minus138 minus0298 minus1092minus0227 084 minus0483
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
1 1 00 0 11 0 11 0 10 1 0
Abweichungen sind Rundungsfehler
23
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Niedrigdimensionale Approximation
Die kleinsten Eigenwerte sind die unwichtigsten Wir konnen dieseldquoweglassenrdquo = auf Null setzenrarr eine Matrix mit kleinerem Rang dieaber relativ ahnlich zur Ausgangsmatrix istminus041 07 024minus029 minus033 minus072minus061 minus02 014minus061 minus02 014minus01 057 minus062
227 0 0
0 149 00 0 0
minus072 minus023 minus066019 085 minus05067 minus048 minus056
=
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
minus072 minus023 minus066
019 085 minus05067 minus048 minus056
=
087 109 011038 minus027 068093 005 106093 005 106032 077 minus027
24
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Die niedrigdimensionale Approximation
Wir interessieren uns fur die Matrix U2 = UΣ2 also die Matrix mit demniedrigerem Rang
minus093 104 0minus0658 minus049 0minus138 minus0298 0minus138 minus0298 0minus0227 084 0
Man kann diese nun als die Reprasentation unserer 5 Worter mit zweiversteckten Dimensionen auffassen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
25
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Neue Ahnlichkeitsberechnungen
h1 h2ship minus093 104boat minus0658 minus049
ocean minus138 minus0298motor minus138 minus0298wood minus0227 084
cossim(shipboat) =(minus093) middot (minus0658) + 104 middot (minus049)radic
(0932 + 1042) middotradic
(06582 + 0492)= 009
cossim(shipocean) =(minus093) middot (minus138) + 104 middot (minus029)radic
(0932 + 1042) middotradic
(1382 + 0292)= 049
cossim(boatocean) = 09
Vorsicht Habe auch schon oft Benutzung von U prime2 (einfach die erstenzwei Spalten von U abgeschnitten ohne Sigmamultiplikation) gesehen
26
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Intuition
Vektoren in U und V sind nach Variation in den Originaldatengeordnet
Loschen von Dimensionen die keine wesentliche Variationbeitragen reduziert ldquoRauschenrdquo
Wortvektoren sind nun kurzer und enthalten nur Elemente die diewichtigsten versteckten Dimensionen aufzeigen
Im Normalfall von Tausenden von Dimensionen zu wenigen 100
27
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Was brauchen wir nun hierfur
Wie berechne ich diese Zerlegung und finde die Matrizen Und wasbedeuten die Fachbegriffe Und warum funktioniert das
Basis Unterraume
Orthonormalisierungen
Matrizenhintergrund
Eigenvektoren Eigenwerte sowie Berechnungsmethoden vonEigenvektoren und Eigenwerten
Range
Ahnlichkeiten von Matrizen (Normen und Distanzen fur Matrizen)
28
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Anwendungen von SVD
Dichte Embeddings von Wortern
Image Compression
Recommendersysteme
Information Retrieval
29
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
Literatur
Jurafsky und Martin (Edition 3) Introduction to Natural LanguageProcessing (Kapitel 6)
Agirre et al (NAACL 2009) A study on similarity and relatednessusing distributional and wordnet-based approaches
Manning et al Introduction to Information Retrieval (Kapitel 18)
SVD Tutorial (ohne vollstandigen Hintergrund) Kirk Baker(2005) Singular Value Decomposition Tutorialhttpsdatajobscomdata-science-repoSVD-Tutorial-[Kirk-Baker]pdf
30
