SSignalverarbeitung 2ignalverarbeitung 2 - Mitarbeiter …mitarbeiter.hs-heilbronn.de/~vstahl/signalverarbeitung2/matching.pdf · Signalverarbeitung 2 Volker Stahl - 5 - Maximum Likelihood

- 1 - Signalverarbeitung 2 Volker Stahl

Signalverarbeitung 2 Signalverarbeitung 2 Volker Stahl


Spracherkennung gestern

… und morgen


Klassifikation von Signalen, Mustererkennung z.B. Sprache, Gestik, Handschrift, EKG, Verkehrssituationen, …

Ziel

Vorverarbeitung: Berechnung von Merkmalvektoren

…

Klasse 2

Klasse n

Klasse 1

Klassifikation: Vergleich mit Referenzmustern

Sensor Signal


Abstandsmaß für Vektorfolgen unterschiedlicher Länge Dynamische Zeitverzerrung, Dynamische Programmierung

Inhalt

Berechnung eines Referenzmusters aus mehreren Beispielen Mittelwert, Varianz, Mahalanobis Abstand

Zufallsvariablen Modellieren von Unsicherheit, Normalverteilung

Hidden Markov Modelle, Lernen aus Beispielen Viterbi Training, Expectation Maximization (EM), k-means Algorithmus, Mischverteilungen

Statistische Abhängigkeit, Kovarianz Vermeiden von Fehlklassifikationen, n-dimensionale Normalverteilung


Maximum Likelihood Schätzung Theoretischer Hintergrund statistischer Lernverfahren

Inhalt (optional)

Dekorrelation, Hauptachsentransformation Vereinfachung des Klassifikationsproblems durch Vorverarbeitung


Ilias bzw. http://mitarbeiter.hs-heilbronn.de/~vstahl

Vorlesungsunterlagen

Folien der Vorlesung

Übungsaufgaben

Daten für Experimente

Literaturhinweise

http://mitarbeiter.hs-heilbronn.de/~vstahl


Vorlesungsbegleitendes Programmierprojekt Entwicklung eines zuverlässigen Klassifikators Sukzessive Verbesserung, Hausaufgaben Programmiersprache C oder Matlab Abgabe in letzter Vorlesungswoche (Ausarbeitung und Software)

Leistungsnachweis


Elementare Einführung in die Wahrscheinlichkeitsrechnung Karl Bosch (E-Book, 519.Bosch)

Literatur

Elementare Einführung in die angewandte Statistik Karl Bosch (519.Bosch)

Mustererkennung mit Markov-Modellen – Theorie, Praxis, Anwendungsgebiete Gernot A. Fink (621.841 Fin)

Pattern Classification and Scene Analysis Richard O. Duda, Peter E. Hart (519.Dud)

Mathematical Methods and Algorithms for Signal Processing Todd K. Moon, Wynn C. Stirling

The Elements of Statistical Learning Trevor Hastie, Robert Tibshirani, Jerome Friedman (519.Has)


Beispiel: DARPA Grand Challenge

1957 „Sputnik Schock“

Gründung der ARPA 1958 (Advanced Research Projects Agency) als Behörde des US Verteidigungsministeriums DARPA (1972-1993), ARPA (1993-1996), DARPA (1996-…) Aktuelles Budget ≈ 3 Mrd. $


Beispiel: DARPA Grand Challenge

1969 Arpanet

Weitere Projekte: Tarnkappentechnologie, GPS, …

Grand Challenge 2004, Mohave Wüste Nevada, 241km.

Grand Challenge 2005 Urban Challenge 2007





Military Bioengineering & Human Enhancing … Das Ziel heißt „Human Enhancing“, Soldaten sollen mit Hilfe von Drogen, Genen und Mikrochips schneller, härter und kampffähiger werden – ein Motto, dem sich die Darpa mit viel Geld und Know-How widmet.

Continuous Assisted Performance … „mit biotechnologischen Mitteln (Implantaten, Manipulation des Stoffwechsels, etc.)“ erreichen, dass Soldaten bis zu sieben Tage lang wach bleiben können, ohne dabei den Verstand zu verlieren.

Brain Machine Interfaces … ein Programm, für das der Darpa zurzeit 24 Millionen Dollar zur Verfügung stehen. Ziel von „Brain Machine Interfaces“ (Hirn-Maschine-Schnittstellen) ist es, aus menschlichen Gehirnen Informationen zu gewinnen, die für Computer verwertbar sind – Chips im Kopf sollen Panzer oder Hubschrauber oder auch den Soldaten steuern, dem sie implantiert wurden. … „Stellen Sie sich eine Zeit vor, in der Soldaten allein mittels Gedanken kommunizieren, stellen sie sich eine Zeit vor, in der menschliche Gehirne ihre eigenen drahtlosen Modems besitzen – statt auf der Basis von Gedanken zu handeln, haben Kampfflugzeuge dann Gedanken, die handeln.“

Aktuelle DARPA Projekte (Quelle: http://de.wikipedia.org/wiki/DARPA, Download 20.11.2010)

http://de.wikipedia.org/wiki/DARPA


(Quelle: Zeit Online, Download 8.10.2011)


Beispiel Schriftzeichenerkennung

Mustererkennung

A


Erkennen heißt Klassifizieren

Gegeben:

Signal (bzw. daraus berechnete Merkmale): Muster Endlich viele Klassen

Gesucht:

Klasse, zu der das Signal „gehört“.

Beispiele: Buchstabenerkennung

Visuelle Qualitätskontrolle (ok, Ausschuss) Spracherkennung (Phonemerkennung, Worterkennung)

Medizinische Diagnostik (Röntgenbilder, EKG, …) …


Klassifizieren heißt Vergleichen mit Bekanntem

Gegeben:

Zu klassifizierendes Muster Ein Referenzmuster zu jeder Klasse

Gesucht: Die Klasse, deren Referenzmuster am „ähnlichsten“ zu dem zu klassifizierenden Muster ist.

Problem: „Geeignetes“ Ähnlichkeitsmaß zwischen Mustern?


A Referenzmuster Klasse A:

Referenzmuster Klasse B: B

Beispiel Schriftzeichenerkennung

Zu klassifizierendes Muster: A

Ähnlichkeits- / Abstandsmaß?


Vorverarbeitung Berechnung trennscharfer Merkmale eines Musters: Merkmalvektoren.

Folge von Merkmalvektoren

Vorverarbeitung ist anwendungsabhängig! Unterschiedliche Merkmale für Sprache, Gesten, Handschrift, Bilder, …

Zeitsignal (Sprache, Gesten, EKG…)


Abstandsmaß zwischen Folgen von Merkmalvektoren

Referenzmuster Klasse A:

Referenzmuster Klasse B:

Zu klassifizierendes Muster:


Euklidischer Abstand


Referenzmuster Klasse A:

Referenzmuster Klasse B:

Zu klassifizierendes Muster:

Abstandsmaß für unterschiedlich lange Folgen?


Referenz

Test

Matching


Darstellung als Pfad in einem Suchgitter

Refe

renz

Test

Test

Referenz


Einschränkungen beim Matching

Jedem Testvektor muss genau ein Referenzvektor zugeordnet werden! (Zuordnungsfunktion)

Verboten!

Zeitliche Reihenfolge muss beibehalten werden! (Monotone Zuordnungsfunktion)

Verboten!

dreihundertzwei

zweihundertdrei


Einschränkungen beim Matching

Die ersten und letzten Vektoren müssen einander zugeordnet werden!

Erzwungen!

Keine zwei aufeinanderfolgenden Referenzvektoren dürfen übersprungen werden!

Verboten!

…

… hoch

Siebenundzwanzig

Fachhochschule

Siebenhundertfünfundzwanzig


Gesucht: Pfad durch Gitter mit minimalen Kosten

von links unten nach rechts oben monoton steigend maximale Steigung 2 (einen Referenzvektor überspringen)

Refe

renz

Test


Konsequenz: Nur 3 Arten von Übergängen im Gitter

Next Übergang

Loop Übergang

Skip Übergang


Berechnung des optimalen Pfades Viterbi Algorithmus:









Verbesserung: Mehrere Referenzmuster pro Klasse

Referenzmuster einer Klasse:

Mittelwert für die Klasse: Modell

Zustände


Problem: Referenzfolgen einer Klasse unterschiedlich lang

Lösung: Alle Referenzvektorfolgen einer Klasse auf ein gemeinsames Modell fester Länge matchen!

Referenzmuster einer Klasse:


Überblick:

Bestimme Modell Länge Matching (Annahme lineare Zeitverzerrung) Initiale Schätzung der Modellvektoren

Matching (dynamische Zeitverzerrung, Viterbi) Neuberechnung der Modellvektoren

Iteriere

Viterbi Training eines Modells


Wahl der Modell Länge

Modell zu lang!

Wahl der Modell Länge z.B. ½ × Median der Längen der Referenzvektorfolgen


Lineare Segmentierung

Lineare Zuordnung der Merkmalvektoren einer Referenzaufnahme zu den Modellzuständen.

Mod

ell

Referenzmuster


Beispiel

Referenzmuster einer Klasse (gegeben)

Modell für die Klasse (gesucht)

Länge 6

Länge 7

Länge 3


Lineare Segmentierung


Initiale Schätzung der Modellvektoren

Modellvektor = Mittelwert über alle Referenzvektoren, die dem Modellzustand zugeordnet wurden


Matchen der Referenzfolgen gegen das Modell mit Viterbi Algorithmus (Segmentierung)


Neuschätzung der Modellvektoren Modellvektor = Mittelwert über alle Referenzvektoren, die dem Modellzustand zugeordnet wurden

Matching mit neuem Modell, Modell neu schätzen aus neuer Zuordnung

Iteration:


Zahlenbeispiel

Documents

SSignalverarbeitung 2ignalverarbeitung 2 - Mitarbeiter …mitarbeiter.hs-heilbronn.de/~vstahl/signalverarbeitung2/matching.pdf · Signalverarbeitung 2 Volker Stahl - 5 - Maximum Likelihood