docFolien - Institut für Informatik
download 
Denúncia Transcrição
Folien - Institut für Informatik
Universität Potsdam Institut für Informatik Lehrstuhl Maschinelles Lernen Lineare Klassifikatoren IV Christoph Sawade, Blaine Nelson, Tobias Scheffer Klassifikationsproblem Perzeptron, Support Vector Machine Ridge Regression, LASSO Kernel Bayes‘sche Klassenentscheidung MAP-Modell Logistische Regression Empirische Risikominimierung Maschinelles Lernen Inhalt Representer Theorem Duales Perzeptron, Duale SVM Mercer Map Lernen mit strukturierter Ein- und Ausgabe Taxonomie, Sequenzen, Ranking,… Dekoder, Schnittebenenalgorithmus 2 Maschinelles Lernen Review: Binäre SVM Klassifikation bei mehr als zwei Klassen: 𝑦 𝐱 = sign 𝑓𝛉 𝐱 , Ein Parametervektor 𝛉 Optimierungsproblem: min 𝜆 𝛉,𝛏 𝑛 𝑖=1 𝜉𝑖 𝑓𝛉 𝐱 = 𝜙 𝐱 T 𝛉 1 2 + 𝛉T 𝛉 unter den Nebenbedingungen 𝜉𝑖 ≥ 0 und 𝑦𝑖 𝜙 𝐱 𝑖 T 𝛉 ≥ 1 − 𝜉𝑖 Verallgemeinerung für 𝑘 Klassen? 3 In der Multi-Klassen Fall hat das lineare Modell Entscheidungsfunktion : 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T 𝛉𝑦 + 𝑏 𝑦 & Klassifikator : 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑧 𝑧∈𝑌 Logistisches Modell für den Multi-Klassen Fall: 𝑃 𝑦|𝐱, 𝛉 = Maschinelles Lernen Review: Multi-Klassen Logistische Regression exp 𝜙 𝐱 T 𝛉𝑦 + 𝑏 𝑦 𝑧∈𝑌 exp 𝜙 𝐱 T𝛉𝑧 + 𝑏 𝑧 Der Prior ist eine Normalverteilung; 𝑝 𝛉 = 𝑁 𝛉; 𝟎, 𝚺 Die Maximum-A-Posteriori-Parameter ist 𝛉MAP = argmin 𝛉 𝑛 𝑖=1 log Σ𝑧∈𝑌 exp 𝑓𝛉 𝑥𝑖 , 𝑧 − 𝑓𝛉 𝐱 𝑖 , 𝑦𝑖 Verlustfunktion 𝛉T 𝚺 −1 𝛉 + 2 Regularisierer 4 Multi-Klassen logistische Regression 𝑦 𝐱 = sign 𝑓𝛉 𝐱 Ein einziger Parametervektor 𝛉 wurde zu 𝛉 = T 1 𝑘 𝛉 ,…,𝛉 Maschinelles Lernen Verallgemeinerung auf Multi-Klassen Probleme wurde 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑦 mit einer Komponente für jede Klasse Für eine SVM mit 𝑘 Klassen Regularisierer? 1 T 1 𝛉 𝛉 becomes 2 2 𝑇 𝑗 𝑘 𝑗 𝑗=1 𝛉 𝛉 Abstand (Margin) Nebenbedingungen? 5 Multi-Klassen logistische Regression 𝑦 𝐱 = sign 𝑓𝛉 𝐱 Ein einziger Parametervektor 𝛉 wurde zu 𝛉 = T 1 𝑘 𝛉 ,…,𝛉 Maschinelles Lernen Verallgemeinerung auf Multi-Klassen Probleme wurde 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑦 mit einer Komponente für jede Klasse Für eine SVM mit 𝑘 Klassen Regularisierer? 1 T 1 𝛉 𝛉 wird 2 2 𝑇 𝑗 𝑘 𝑗 𝑗=1 𝛉 𝛉 Abstand (Margin) Nebenbedingungen? 𝑦𝑖 𝜙 𝐱 𝑖 T 𝛉 ≥ 1 − 𝜉𝑖 wird ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱 𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱 𝑖 , 𝑦 + 1 − 𝜉𝑖 6 Klassifikation mit mehr als zwei Klassen: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 , 𝑦 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T 𝛉𝑦 Parametervektor für jede der möglichen 𝑘 Klassen Maschinelles Lernen Multi-Klassen SVM 𝛉 = 𝛉1 , … , 𝛉𝑘 T Optimierungsproblem: min 𝜆 𝛉,𝛏 𝑛 𝑖=1 𝜉𝑖 1 + 2 𝑇 𝑗 𝑘 𝑗 𝑗=1 𝛉 𝛉 unter den Nebenbedingungen 𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱 𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖 [J.Weston, C.Watkins, 1999] 7 Verschiedene Gewichtsvektoren kann auch als unterschiedliche Abschnitte eines Gewichtsvektors gesehen werden (vgl. Logistische Regression): 𝛉= Maschinelles Lernen Multi-Klassen Feature-Mapping T 1 𝑘 𝛉 ,…,𝛉 Gemeinsame Repräsentation von Ein- und Ausgabe: Φ 𝐱, 𝑦 = 2 = 𝟎 𝜙 𝐱 ⋮ 𝟎 𝑘 gestapelte Featurevektoren 8 Klassifikation mit mehr als zwei Klassen: Maschinelles Lernen Multi-Klassen Feature-Mapping 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑦 Multi-Klassen-Kernel: 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉 I𝑦=1 ⋮ Λ 𝑦 = I𝑦=𝑘 𝜙 𝐱 I𝑦=1 ⋮ Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦 = 𝜙 𝐱 I𝑦=𝑘 9 Klassifikation mit mehr als zwei Klassen: Maschinelles Lernen Multi-Klassen Kernel-Kodierung 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑦 Multi-Klassen-Kernel: 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉 𝑥1 I𝑦=1 Φ 𝐱, 𝑦 = 𝑥 ⨂ I𝑦=2 2 = 𝑥1 I 𝑥2 I 𝑥1 I 𝑥2 I 𝑦=1 𝑦=1 𝑦=2 𝑦=2 𝑘 𝐱 𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱 𝑖 , 𝑦𝑖 𝑇 Φ 𝐱𝑗 , 𝑦𝑗 = I 𝑦𝑖 = 𝑦𝑗 1 if𝑦𝑖 =𝑦𝑗 0 otherwise 10 Klassifikation mit mehr als zwei Klassen: Maschinelles Lernen Multi-Klassen Kernel-Kodierung 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑦 Multi-Klassen-Kernel: 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉 𝑥1 I𝑦=1 Φ 𝐱, 𝑦 = 𝑥 ⨂ I𝑦=2 2 = 𝑥1 I 𝑥2 I 𝑥1 I 𝑥2 I 𝑦=1 𝑦=1 𝑦=2 𝑦=2 𝑘 𝐱 𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱 𝑖 , 𝑦𝑖 𝑇 Φ 𝐱𝑗 , 𝑦𝑗 = I 𝑦𝑖 = 𝑦𝑗 1 falls 𝑦𝑖 =𝑦𝑗 0 sonst 11 Maschinelles Lernen Klassifikation mit Information über Klassen Klassen haben gewisse Merkmale: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉, 𝑘 𝐱 𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱 𝑖 , 𝑦𝑖 𝑦 Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦 TΦ 𝐱𝑗 , 𝑦𝑗 = 𝜙 𝐱 𝑖 T 𝜙 𝐱𝑗 Λ 𝑦𝑖 TΛ = 𝑘 𝐱 𝑖 , 𝐱𝑗 Λ 𝑦𝑖 T Λ 𝑦𝑗 𝑦𝑗 𝐾𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑧 𝑧𝑤𝑖𝑠𝑐ℎ𝑒𝑛 𝐾𝑙𝑎𝑠𝑠𝑒𝑛 12 Klassen haben gewisse Merkmale: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉, 𝑘 𝐱 𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱 𝑖 , 𝑦𝑖 𝑦 Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦 TΦ 𝐱𝑗 , 𝑦𝑗 = 𝜙 𝐱 𝑖 T 𝜙 𝐱𝑗 Λ 𝑦𝑖 TΛ = 𝑘 𝐱 𝑖 , 𝐱𝑗 Λ 𝑦𝑖 T Λ 𝑦𝑗 𝑦𝑗 𝐾𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑧 𝑧𝑤𝑖𝑠𝑐ℎ𝑒𝑛 𝐾𝑙𝑎𝑠𝑠𝑒𝑛 Korrespondenz der Klassen Λ 𝑦𝑖 T Λ 𝑦𝑗 : z.B. Skalarprodukt der Klassenbeschreibungen. Λ 𝑦𝑖 : TF-Vektor über alle Wörter. 13 Maschinelles Lernen Klassifikation mit Informationen über Klassen Klassifikation mit mehr als zwei Klassen: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 . 𝑓 hat jetzt zwei Parameter. 𝑦 Gemeinsame Merkmale von Ein- und Ausgabe: Maschinelles Lernen Multi-Klassen SVM 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉. Gleicher Ansatz für Multiklassen, Sequenz- und Struktur-Lernen, Ranking. 14 Maschinelles Lernen Multi-Klassen SVM Beispiel 𝐱 kodiert z.B. ein Dokument 𝑦 = 2 kodiert Klasse Φ 𝐱, 𝑦 = I I I I I I 𝑦=1 𝑦=2 𝑦=3 𝑦=4 𝑦=5 𝑦=6 ⋮ 𝐱 𝐱 𝐱 𝐱 𝐱 𝐱 = 𝟎 𝐱 𝟎 𝟎 𝟎 𝟎 ⋮ 1 2 3 4 5 6 15 Maschinelles Lernen Multi-Klassen SVM Beispiel 𝐱 kodiert z.B. ein Dokument 𝑦 = 2 kodiert Klasse Φ 𝐱, 𝑦 = I I I I I I 𝑦=1 𝑦=2 𝑦=3 𝑦=4 𝑦=5 𝑦=6 ⋮ 𝐱 𝐱 𝐱 𝐱 𝐱 𝐱 = 𝟎 𝐱 𝟎 𝟎 𝟎 𝟎 ⋮ 1 2 3 4 5 6 16 Klassifikation mit mehr als zwei Klassen: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T 𝛉𝑦 𝑦 Parametervektor für jede der möglichen 𝑘 Klassen Maschinelles Lernen Multi-Klassen SVM 𝛉 = 𝛉1 , … , 𝛉𝑘 T Optimierungsproblem: min 𝜆 𝛉,𝛏 𝑛 𝑖=1 𝜉𝑖 1 + 2 𝑇 𝑗 𝑘 𝑗 𝑗=1 𝛉 𝛉 unter den Nebenbedingungen 𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱 𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖 17 Klassifikation mit mehr als zwei Klassen: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉 𝑦 Parametervektor für jede der möglichen 𝑘 Klassen Maschinelles Lernen Multi-Klassen SVM 𝛉 = 𝛉1 , … , 𝛉𝑘 T Optimierungsproblem: min 𝜆 𝛉,𝛏 𝑛 𝑖=1 𝜉𝑖 1 T + 𝛉 𝛉 2 unter den Nebenbedingungen 𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱 𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖 18 Maschinelles Lernen STRUKTURIERTE AUSGABE 19 Angenommen die Ähnlichkeiten der 𝑘 Klassen sind durch eine Baumstruktur (Tiefe 𝑑) gegeben: 𝑣11 Hominini Homininae 𝑣22 𝑣12 Pan Homo 𝑣13 Maschinelles Lernen Taxonomien 𝑣23 Gorillini Gorilla 𝑣33 Jede Klasse entspricht einem Pfad im Baum; 𝐲 = 𝑦1 , … , 𝑦 𝑑 . 20 Angenommen die Ähnlichkeiten der 𝑘 Klassen sind durch eine Baumstruktur (Tiefe 𝑑) gegeben: 𝑣11 Hominini Homininae 𝑣22 𝑣12 Pan Homo 𝑣13 Maschinelles Lernen Taxonomien 𝑣23 Gorillini Gorilla 𝑣33 Jede Klasse entspricht einem Pfad im Baum; 𝐲 = 𝑦1 , … , 𝑦 𝑑 . 𝐶ℎ𝑖𝑚𝑝𝑎𝑛𝑧𝑒𝑒 = 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑖, 𝑃𝑎𝑛 21 Angenommen die Ähnlichkeiten der 𝑘 Klassen sind durch eine Baumstruktur (Tiefe 𝑑) gegeben: 𝑣11 Hominini Homininae 𝑣22 𝑣12 Pan Homo 𝑣13 Maschinelles Lernen Taxonomien 𝑣23 Gorillini Gorilla 𝑣33 Jede Klasse entspricht einem Pfad im Baum; 𝐲 = 𝑦1 , … , 𝑦 𝑑 . 𝐻𝑢𝑚𝑎𝑛 = 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑖, 𝐻𝑜𝑚𝑜 22 Angenommen die Ähnlichkeiten der 𝑘 Klassen sind durch eine Baumstruktur (Tiefe 𝑑) gegeben: 𝑣11 Hominini Homininae 𝑣22 𝑣12 Pan Homo 𝑣13 Maschinelles Lernen Taxonomien 𝑣23 Gorillini Gorilla 𝑣33 Jede Klasse entspricht einem Pfad im Baum; 𝐲 = 𝑦1 , … , 𝑦 𝑑 . W. Gorilla= 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐺𝑜𝑟𝑖𝑙𝑙𝑖𝑛𝑖, 𝐺𝑜𝑟𝑖𝑙𝑙𝑎 23 𝑣11 Klassen in Baumstruktur (Tiefe 𝑑) Die Klasse für ein 𝐱 ist ein Pfad im Klassenbaum 𝐲 = 𝑦1 , … , 𝑦 𝑑 . 𝑣22 𝑣12 𝑣13 𝑣23 𝑣33 Kodierung der gemeinsamen Merkmale von Einund Ausgabe? 24 Maschinelles Lernen Klassifikation mit Taxonomien 𝑣11 Klassen in Baumstruktur (Tiefe 𝑑): 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T 𝛉 𝐲 = 𝑦1 , … , 𝑦 𝑑 𝑣22 𝑣12 𝐲 Λ 𝑦1 ⋮ Λ 𝐲 = Λ 𝑦𝑑 𝑣13 Λ 𝑦𝑖 𝑣23 𝑣33 𝐼 𝑦 𝑖 = 𝑣1𝑖 = ⋮ 𝐼 𝑦 𝑖 = 𝑣𝑛𝑖 𝑖 Λ 𝑦1 ⋮ Φ 𝐱, 𝐲 = 𝜙 𝐱 ⨂Λ 𝑦 = 𝜙 𝐱 ⨂ Λ 𝑦𝑑 I 𝑦 1 = 𝑣11 ⋮ I 𝑦 1 = 𝑣𝑛11 ⋮ =𝜙 𝐱 ⨂ I 𝑦 𝑑 = 𝑣1𝑑 ⋮ 𝑑 I 𝑦 = 𝑣𝑛𝑑𝑑 25 Maschinelles Lernen Klassifikation mit Taxonomien Maschinelles Lernen Klassifikation mit Taxonomien Beispiel 𝐱 kodiert z.B. ein Dokument 𝐲 = 𝑣11 , 𝑣22 , 𝑣33 T ist ein Pfad z.B. in einem Themenbaum Φ 𝐱, 𝐲 = I I I I I I 𝑦1 𝑦2 𝑦2 𝑦3 𝑦3 𝑦3 = = = = = = ⋮ 𝑣11 𝑣12 𝑣22 𝑣13 𝑣23 𝑣33 𝐱 𝐱 𝐱 𝐱 𝐱 𝐱 = 𝐱 𝟎 𝐱 𝟎 𝟎 𝐱 ⋮ 𝑣11 𝑣22 𝑣12 𝑣13 𝑣23 𝑣33 26 Maschinelles Lernen Klassifikation mit Taxonomien Beispiel 𝐱 kodiert z.B. ein Dokument 𝐲 = 𝑣11 , 𝑣22 , 𝑣33 T ist ein Pfad z.B. in einem Themenbaum Φ 𝐱, 𝐲 = I I I I I I 𝑦1 𝑦2 𝑦2 𝑦3 𝑦3 𝑦3 = = = = = = ⋮ 𝑣11 𝑣12 𝑣22 𝑣13 𝑣23 𝑣33 𝐱 𝐱 𝐱 𝐱 𝐱 𝐱 = 𝐱 𝟎 𝐱 𝟎 𝟎 𝐱 ⋮ 𝑣11 𝑣22 𝑣12 𝑣13 𝑣23 𝑣33 27 Kernelisierung 𝑣11 Klassen in Baumstruktur (Tiefe 𝑑): 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T 𝛉 𝐲 = 𝑦1 , … , 𝑦 𝑑 𝑘 𝐱 𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = Φ 𝐱 𝑖 , 𝐲𝑖 𝑇 Φ 𝐱𝑗 , 𝐲𝑗 𝑣22 𝑣12 𝐲 𝑣13 = 𝜙 𝐱 𝑖 T 𝜙 𝐱𝑗 = 𝑘 𝐱 𝑖 , 𝐱𝑗 𝑑 𝑙=1 Λ 𝑣23 𝑣33 Λ 𝐲𝑖 𝑇 Λ 𝐲𝑗 𝑙 T 𝑦𝑖 Λ 𝑦𝑗𝑙 28 Maschinelles Lernen Klassifikation mit Taxonomien Dekoding / Vorhersage 𝑣11 Klassen in Baumstruktur (Tiefe 𝑑) : 𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T 𝛉 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 𝐲 𝑣13 = argmax 𝑛 𝑖=1 𝛼𝑖 𝑘 𝐱 𝑖 , 𝐲𝑖 , 𝐱, 𝐲 = argmax 𝑛 𝑖=1 𝛼𝑖 𝑘 𝐱 𝑖 , 𝐱 Λ 𝐲𝑖 𝑇 Λ 𝐲 = argmax 𝑛 𝑖=1 𝛼𝑖 𝑘 𝐲 𝐲 𝐲 𝐱𝑖 , 𝐱 𝑑 𝑙=1 Λ 𝑙 𝑇 𝑦𝑖 Λ 𝑣22 𝑣12 𝑣23 𝑣33 𝑦𝑙 29 Maschinelles Lernen Klassifikation mit Taxonomien: Maschinelles Lernen Klassifikation mit strukturierten Labeln Die Struktur der Ausgabeklasse 𝑌 wird in der Definition von Λ 𝐲 kodiert. Das gemeinsame Featuremap Φ 𝐱, 𝐲 = 𝜙 𝐱 ⨂Λ 𝐲 erfasst die Struktur des Eingabe- und des Klassenraums und ermöglicht das Lernen auf diesen Strukturen. Dies definiert einen Multi-Klassen-Kernel auf dem Ein- und Ausgaberaum: 𝑘 𝐱 𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = 𝑘 𝐱 𝑖 , 𝐱𝑗 Λ 𝐲𝑖 T Λ 𝐲𝑗 30 Maschinelles Lernen KOMPLEXE STRUKTUREN 31 Maschinelles Lernen Komplexe strukturierte Ausgaben Ausgaberaum Y beinhaltet komplexe Objekte Darstellung als Kombination von binären Vorhersageproblemen? Beispiele: Wortart- und Eigennamenerkennung Natural Language Parsing Sequence Alignment … 32 Maschinelles Lernen Komplexe Ausgabe Tagging Sequentielle Ein-/Ausgaben Wortarterkennung 𝐱 = “Curiosity kills the cat“ → 𝐲 = Noun, Verb, Determiner, Noun Eigennamenerkennung, Informationsextraktion: 𝐱 = “Barbie meets Ken“ → 𝐲 = 𝑃𝑒𝑟𝑠𝑜𝑛, −, 𝑃𝑒𝑟𝑠𝑜𝑛 33 Maschinelles Lernen Komplexe Ausgabe Parsing Natural Language Parsing S 𝐱 =“Curiosity killed the cat.” → NP VP NP N V Det N Curiosity killed the cat 34 Maschinelles Lernen Komplexe Ausgabe Alignments Sequence Alignment 𝐱= Gegeben seien zwei Sequenzen Vorhersage ist ein Alignment s=(ABJLHBNJYAUGAI) t=(BHJKBNYGU) → AB-JLHBNJYAUGAI BHJK-BN-YGU 35 Ausgaberaum Y beinhaltet komplexe Objekte Mehrstufenverfahren propagieren Fehler Warum ist das kein einfaches MultiklassenProblem? 1 𝐲 S VP VP NP V 𝐲2 The dog chased the cat V N S NP Det N VP NP Det V N Det N … Maschinelles Lernen Komplexe strukturierte Ausgaben 𝐲𝑘 S VP NP NP Det N V Det N 36 Maschinelles Lernen Lernen mit strukturierten Ausgaben Beispiel: POS-Tagging (Wortarterkennung) Satz 𝐱 =“Curiosity killed the cat” Gewünscht: argmax Φ 𝐱, 𝐲 T 𝛉 ≡ N, V, Det, N 𝑦 Φ Φ Φ Φ Φ Explizit: 𝐱, 𝐱, 𝐱, 𝐱, 𝐱, N, V, Det, N N, V, Det, N N, V, Det, N N, V, Det, N N, V, Det, N ⋮ T 𝛉 T 𝛉 T 𝛉 T 𝛉 T𝛉 ≥ ≥ ≥ ≥ ≥ Φ Φ Φ Φ Φ 𝐱, 𝐱, 𝐱, 𝐱, 𝐱, N, N, N, N N, N, N, V N, N, V, N N, N, V, V N, V, N, N ⋮ T 𝛉 T 𝛉 T 𝛉 T 𝛉 T𝛉 ZU VIELE!!! 37 Maschinelles Lernen Komplexe strukturierte Ausgaben Ausgaberaum Y beinhaltet komplexe Objekte. Mehrstufenverfahren propagieren Fehler Exponentielle Anzahl von Klassen führt potentiell zu exponentiell vielen zu schätzenden Parametern; uneffizienter Vorhersage; uneffizientem Lernalgorithmus. 38 Exponentielle Anzahl von Klassen führt potentiell zu exponentiell vielen zu schätzenden Parametern; uneffizienter Vorhersage; uneffizientem Lernalgorithmus. Klassifikation bei mehr als zwei Klassen: 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 = argmax Φ 𝐱, 𝐲 T 𝛉 𝐲 Maschinelles Lernen Komplexe strukturierte Ausgaben 𝐲 Um Anzahl der Parameter zu reduzieren, benötigt man effiziente Repräsentation der Ein- und Ausgabe Φ 𝐱, 𝐲 . Repräsentation hängt von konkreter Problemstellung ab. 39 Beispiel: Sequentielle Ein-/Ausgaben 𝑦1 𝑦2 𝑦3 𝑦4 𝑥1 𝑥2 𝑥3 𝑥4 Curiosity killed the cat Attribut für jedes Paar benachbarter Labels 𝑦𝑡 und 𝑦𝑡+1 . Φ𝑖 = Φ𝑗 = Attribut für jedes Paar aus Eingabe und Ausgabe. 𝜙𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = 𝐈 𝑥𝑡 = cat ∧ 𝑦𝑡 = Noun 𝑡 𝜙𝑖 𝑦𝑡 , 𝑦𝑡+1 𝑡 𝜙𝑗 𝑥𝑡 , 𝑦𝑡 Label-label: Label-observation: gemeinsames Featurmapping: Φ 𝐱, 𝐲 = 𝑡 𝜙𝑁,𝑉 𝑦𝑡 , 𝑦𝑡+1 = 𝐈 𝑦𝑡 = Noun ∧ 𝑦𝑡+1 = Verb … , 𝜙𝑁,𝑉 𝑦𝑡 , 𝑦𝑡+1 , … , 𝜙𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 , … Gewichtsvektor 𝐰 = … , 𝑤𝑁,𝑉 , … , 𝑤𝑐𝑎𝑡,𝑁 , … T T 40 Maschinelles Lernen (Feature-Mapping) Beispiel: Sequentielle Ein-/Ausgaben Maschinelles Lernen (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, muss 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 berechnet werden. Das argmax geht über alle möglichen Sequenzen (exponentiell viele in der Länge). T 𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 𝛉 summiert über Merkmale benachbarter Label-Paare und Merkmale von 𝐱 𝑖 , 𝐲𝑖 Paaren. Die Summanden unterscheiden sich nur dort, wo sich auch die 𝐲-Sequenzen unterscheiden. Mit dynamischer Programmierung kann argmax in linearer Zeit berechnet werden (Viterbi Algorithmus). 41 (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi). Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen 𝑦𝑡−1 𝛾𝑁𝑡−1 𝛾𝑉𝑡−1 𝛾𝐷𝑡−1 𝑁 = 𝑉 𝐷 𝑁 𝑦𝑡 = 𝑉 𝐷 𝛾𝑁𝑡 𝛾𝑉𝑡 𝛾𝐷𝑡 𝛾𝑁𝑡 = max 𝑤𝑧,𝑁 + 𝛾𝑧𝑡−1 + 𝑤𝑐𝑎𝑡,𝑁 𝑧 𝑡 𝑝𝑁 = argmax … 𝑧 𝑥𝑡 = 𝑐𝑎𝑡 42 Maschinelles Lernen Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi). Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen 𝑦𝑡−1 𝛾𝑁𝑡−1 𝛾𝑉𝑡−1 𝛾𝐷𝑡−1 𝑁 = 𝑉 𝐷 𝑁 𝑦𝑡 = 𝑉 𝐷 𝛾𝑁𝑡 𝛾𝑉𝑡 𝛾𝐷𝑡 𝛾𝑁𝑡 = max 𝑤𝑧,𝑁 + 𝛾𝑧𝑡−1 + 𝑤𝑐𝑎𝑡,𝑁 𝑧 𝑡 𝑝𝑁 = argmax … 𝑧 𝑥𝑡 = 𝑐𝑎𝑡 43 Maschinelles Lernen Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi). 𝑦𝑡−1 Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen 𝛾𝑁𝑡−1 𝛾𝑉𝑡−1 𝛾𝐷𝑡−1 𝑁 = 𝑉 𝐷 𝑁 𝑦𝑡 = 𝑉 𝐷 𝛾𝑁𝑡 𝛾𝑉𝑡 𝛾𝐷𝑡 𝛾𝑉𝑡 = max 𝑤𝑧,𝑉 + 𝛾𝑧𝑡−1 + 𝑤𝑐𝑎𝑡,𝑉 𝑧 𝑝𝑉𝑡 = argmax … 𝑧 𝑥𝑡 = 𝑐𝑎𝑡 44 Maschinelles Lernen Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi). Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen 𝑦𝑡−1 𝛾𝑁𝑡−1 𝛾𝑉𝑡−1 𝛾𝐷𝑡−1 𝑁 = 𝑉 𝐷 𝑁 𝑦𝑡 = 𝑉 𝐷 𝛾𝑁𝑡 𝛾𝑉𝑡 𝛾𝐷𝑡 𝛾𝐷𝑡 = max 𝑤𝑧,𝐷 + 𝛾𝑧𝑡−1 + 𝑤𝑐𝑎𝑡,𝐷 𝑧 𝑝𝐷𝑡 = argmax … 𝑧 𝑥𝑡 = 𝑐𝑎𝑡 45 Maschinelles Lernen Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage) Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax 𝑓𝛉 𝐱, 𝐲 𝐲 Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi). Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen Sobald 𝛾∗𝑡 für die gesamte Sequenz berechnet wurde, maximieren wir 𝛾∗𝑇 und folgen den Zeigern 𝑝∗𝑡 rückwärts, um die maximale Sequenz zu finden. 𝑦1 𝑥1 N 𝑦2 V 𝑦3 𝑥2 𝑥3 D Curiosity killed the 𝑦4 N 𝑥4 cat 46 Maschinelles Lernen Beispiel: Sequentielle Ein-/Ausgaben Strukturierte Ausgaberäume Maschinelles Lernen Sequentielle Ein-/Ausgaben Dekoderierung: Viterbi-Algorithmus Feature-Mapping: Einträge für benachbarte Zustände 𝜙𝑁,𝑉 𝑦𝑡 , 𝑦𝑡+1 = 𝐈 𝑦𝑡 = Noun ∧ 𝑦𝑡+1 = Verb Einträge für Beobachtungen in einem Zustand 𝜙𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = 𝐈 𝑥𝑡 = cat ∧ 𝑦𝑡 = Noun 47 Strukturierte Ausgaberäume S NP VP 𝐲= NP N 𝐱= 𝜙𝑁→𝑐𝑎𝑡 𝐱, 𝐲 = Det N Curiosity killed the 𝜙𝑁𝑃→𝑁 𝐲 = V cat Φ 𝐱, 𝐲 = 𝐈 𝑦𝑝 = 𝑁𝑃 → 𝑁 𝑝∈𝐲 1 𝑆 1 𝑁𝑃 0 𝑉𝑃 1 𝑉𝑃 ⋮ 0 𝑁 1 𝑁 → → → → 𝑁𝑃, 𝑉𝑃 𝑁 𝑉 𝑉, 𝑁𝑃 → → 𝑎𝑡𝑒 𝑐𝑎𝑡 𝐈 𝑦𝑝 = 𝑁 → 𝑐𝑎𝑡 𝑝∈𝐲 gemeinsames Featuremapping: Φ 𝐱, 𝐲 = … , 𝜙𝑁𝑃→𝑁 𝐲 , … , 𝜙𝑁→𝑐𝑎𝑡 (x, y), … T Gewichtsvektor: 𝐰 = … , 𝑤𝑁𝑃→𝑁 , … , 𝑤𝑁→𝑐𝑎𝑡 , … T Dekodierung mit dynamischer Programmierung 3 CKY-Parser, 𝑂 𝑛 . 48 Maschinelles Lernen Natural Language Parsing Strukturierte Ausgaberäume x1 y1 y4 x4 Attribut für jedes Paar benachbarter Labels 𝐲𝑡 und 𝐲𝑡+1 . y2 y3 x2 x3 𝜙123 𝑦𝑖 , 𝑦𝑗 Attribut für jedes Paar aus Eingabe und Ausgabe. 𝜙𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = I 𝑦𝑡 = 𝐼𝑛𝑠𝑡𝑖𝑡𝑢𝑡𝑒 ∧ 𝑥𝑡 = Dekoder: Message Passing Algorithmus. 49 Maschinelles Lernen Kollektive Klassifikation Exponentielle Anzahl von Klassen führt potentiell zu Maschinelles Lernen Komplexe strukturierte Ausgaben exponentiell vielen zu schätzenden Parametern; uneffizienter Vorhersage; uneffizientem Lernalgorithmus. Optimierungsproblem: min 𝜆 𝛉,𝛏 𝑛 𝑖=1 𝜉𝑖 + 1 2 𝛉 2 2 unter den Nebenbedingungen Exponentielle Anzahl 𝜉𝑖 ≥ 0 and ∀𝐲 ≠ 𝐲𝑖 𝑓𝛉 𝐱 𝑖 , 𝐲𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝐲 + 1 − 𝜉𝑖 Effiziente Kodierung 50 Optimierungsproblem: min 𝜆 𝛉,𝛏 Maschinelles Lernen Lernen mit strukturierten Ausgaben 𝑛 𝑖=1 𝜉𝑖 + 1 2 𝛉 2 2 unter den Nebenbedingungen Exponentielle Anzahl 𝜉𝑖 ≥ 0 and ∀𝐲 ≠ 𝐲𝑖 𝑓𝛉 𝐱 𝑖 , 𝐲𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝐲 + 1 − 𝜉𝑖 Optimierung durch iteratives Training. Negative Constraints werden hinzugefügt, wenn beim Training Fehler auftritt. [Tsochantaridis et al., 2004] 51 Maschinelles Lernen Lernen mit strukturierten Ausgaben Schnittebenenalgorithmus Gegeben: 𝐿 = 𝐱1 , 𝐲1 , … , 𝐱𝑛 , 𝐲𝑛 Wiederhole bis alle Sequenzen korrekt vorhergesagt werden. Iteriere über alle Beispiele 𝐱 𝑖 , 𝐲𝑖 . Bestimme 𝐲 = argmax Φ 𝐱 𝑖 , 𝐲 T 𝛉 𝐲≠𝐲𝑖 Wenn Φ 𝐱 𝑖 , 𝐲𝑖 T 𝛉 < Φ 𝐱 𝑖 , 𝐲 T 𝛉 + 1 (Margin-Verletzung) dann füge Constraint Φ 𝐱 𝑖 , 𝐲𝑖 T 𝛉 < Φ 𝐱 𝑖 , 𝐲 T 𝛉 + 1 − 𝜉𝑖 dem Working Set hinzu. Löse Optimierungsproblem für Eingabe 𝐱 𝑖 , Ausgabe 𝐲𝑖 , und negative Pseudo-Beispiele 𝐲 (working set). Liefere 𝛉 zurück. 52 Allgemeines Framework Anpassen von Maschinelles Lernen Strukturierte Ausgaberäume Verlustfunktion Gemeinsamer Repräsentation der Ein- und Ausgabe Dekoder 𝐲 = argmax Φ 𝐱 𝑖 , 𝐲 T 𝛉 ggf. mit Verlustfunktion 𝐲≠𝐲𝑖 Implementation: http://www.cs.cornell.edu/People/tj/svm_light/svm_struct.html 53 Ausgaberaum Y beinhaltet komplexe Objekte. Mehrstufenverfahren propagieren Fehler Exponentielle Anzahl von Klassen, aber weniger zu schätzende Parameter; effiziente Vorhersage; effizienter Lernalgorithmus. Schnittebenenalgorithmus Maschinelles Lernen Strukturierte Ein-/Ausgaben Feature-Mapping: reduziert die Anzahl der Parameter für jede Klasse Problemspezifische Kodierung 54 Maschinelles Lernen RANKING 55 Können wir das Lernen auch auf andere Arten von strukturierten Ausgaben erweitern? Maschinelles Lernen Ranking Ranking – jede Ausgabe ist eine Sortierung Wir wollen diese Reihenfolge benutzen, um den Lernalgorithmus zu verbessern. 56 Instanzen sollen in die richtige Reihenfolge gebracht werden. Maschinelles Lernen Ranking z.B. Relevanz-Ranking von Suchergebnissen. z.B. Relevanz-Ranking von Produktempfehlungen. Beispiele sind Paare: 𝐿 = 𝑓 𝐱 𝑖 ≥ 𝑓 𝐱𝑗 , … ≡ 𝐱 𝑖 soll im Ranking vor 𝐱𝑗 stehen 57 Relevanz-Ranking von Suchergebnissen. Maschinelles Lernen Ranking Webseiten 𝐱 𝑖 , Suchanfrage 𝐪. Gemeinsame Merkmalsrepräsentation Φ 𝐱 𝑖 , 𝐪 von Webseite und Suchanfrage. Φ 𝐱 𝑖 , 𝐪 kann Vektor verschiedener Merkmale der Übereinstimmung von 𝐱 𝑖 und 𝐪 sein. z.B. Anzahl übereinstimmende, Wörter; Übereinstimmungen in H1-Umgebung, PageRank, … Beispiele sind Paare: 𝐿 = 𝑓 𝐱 𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 , … ≡ 𝐱 𝑖 soll für Anfrage 𝐪 im Ranking vor 𝐱𝑗 stehen 58 Relevanz-Ranking von Suchergebnissen. Beispiele sind Paare: Maschinelles Lernen Ranking 𝐿 = 𝑓 𝐱 𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 , … ≡ 𝐱 𝑖 soll für Anfrage 𝐪 im Ranking vor 𝐱𝑗 stehen Beispiele können z.B. aus Klick-Daten gewonnen werden. Ein Benutzer stellt Anfrage 𝐪, bekommt Ergebnisliste, klickt dann auf i-tes Listenelement 𝐱 𝑖 . Verwirft damit Listenelemente 1..i-1 implizit. Für diesen Benutzer und Anfrage 𝐪 hätte 𝐱 𝑖 an erster Stelle stehen sollen. 59 Maschinelles Lernen Ranking Relevanz-Ranking von Suchergebnissen. Beispiele sind Paare: 𝐿= 𝑓 𝐱 𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 ,… Ein Benutzer stellt Anfrage 𝐪, bekommt Ergebnisliste, klickt dann auf i-tes Listenelement 𝐱 𝑖 . Für diesen Benutzer und Anfrage 𝐪 hätte 𝐱 𝑖 an erster Stelle stehen sollen. Daraus ergeben sich Beispiele: 𝐿𝐪 = 𝑓 𝐱 𝑖 , 𝐪 ≥ 𝑓 𝐱1 , 𝐪 , … , 𝑓 𝐱 𝑖 , 𝐪 ≥ 𝑓 𝐱 𝑖−1 , 𝐪 60 Gegeben: Beispiele 𝑓 𝐱1𝑖1 , 𝐪1 ≥ 𝑓 𝐱11 , 𝐪1 𝐿= 𝑓 𝐱 𝑚𝑖𝑚 , 𝐪𝑚 ≥ 𝑓 𝐱 𝑚1 , 𝐪𝑚 Maschinelles Lernen Ranking , … , 𝑓 𝐱1𝑖1 , 𝐪1 ≥ 𝑓 𝐱1𝑖1−1 , 𝐪1 ⋮ , … , 𝑓 𝐱 𝑚𝑖𝑚 , 𝐪𝑚 ≥ 𝑓 𝐱 𝑚𝑖𝑚−1 , 𝐪𝑚 Löse min 𝐰,𝛏 𝑠. 𝑡. 1 2 𝐰 2 +𝐶 ∀𝑗 ∀ 𝑖 < 𝑖𝑗 ∀𝑗 ∀𝑖 𝑗 𝑖 𝜉𝑗𝑖 𝑤 T Φ 𝐱𝑗𝑖𝑗 , 𝐪𝑗 − Φ 𝐱𝑗𝑖 , 𝐪𝑗 ≥ 1 − 𝜉𝑗𝑖 𝜉𝑗𝑖 ≥ 0 61 Klassifikation bei mehr als zwei Klassen: 𝑦 𝐱 = argmax 𝑓𝛉 𝐱, 𝑦 , 𝑦 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T 𝛉 Lernen formuliert als Multi-Klassen SVM Struktur der 𝑌 ist durch Λ 𝐲 gegeben: Φ 𝐱, 𝐲 = 𝜙 𝐱 ⨂Λ 𝐲 & 𝑘 𝐱 𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝐲𝑖 T Λ 𝐲𝑗 Strukturierte Ausgabe – hochdimensionale 𝑌 Maschinelles Lernen Lernen mit strukturierter Ein- und Ausgabe - Zusammenfassung weniger zu schätzende Parameter – Featuremapping effiziente Vorhersage – problemspezifische Kodierung effizienter Lernalgorithmus – Schnittebenenalgorithmus Andere strukturierte Probleme: Ranking benutzt Sortierungs-Constraints 62
