Machine Learning and Natural Language Processing Lab

Student's Project

Logische Markov Modelle

Ingo Thon , 2004

---

Zur Analyse von sequentiellen Daten sind Hidden-Markov-Modelle gängig. Hidden-Markov-Modelle sind jedoch nicht in der Lage, relationale Daten darzustellen. Da jedoch relationale Daten in vielen Anwendungen gängig sind - der Erfolg der relationalen Datenbanken begründet sich immerhin darauf -, wurden sie von Kersting et al. [10] zu Logical-Hidden-Markov-Modellen erweitert. Diese sind in der Lage, anstatt propositionaler Zustände und Ausgabesymbole auch Atome der Logik erster Stufe als Zustände und Ausgabesymbole zu nutzen. Wir werden diese Erweiterung analog fuer Markov-Modelle zu Logische-Markov-Modellen wiederholen und die Basisalgorithmen sowie eine Erweiterung zur Beschleunigung des Lernalgorithmuses angeben. Die Ziele dabei sind, eine theoretische Grundlage fuer Logical-Hidden-Markov-Modelle zu entwickeln und ein Framework zu erstellen, welches zwar eine geringere Ausdrucksstärke als Logical-Hidden-Markov-Modelle hat, jedoch auch eine geringere Laufzeitkomplexitaet. Anschliessend werden wir durch Experimente zeigen, dass die neue Darstellung Vorteile gegenüber klassischen Markov-Modellen bringt. Der Text ist wie folgt aufgebaut. In Abschnitt 2 wird die Syntax und die Semantik von LoMMs vorgestellt. In Abschnitt 3 werde die Basis Algorithmen für die LoMMs vorgestellt. Anschliessend wird in Abschnitt 4 ein verbesserter Lernalgorithmus vorgestellt. Die Evaluation der LoMMs findet in Abschnitt 5 statt. In den letzten zwei Abschnitten werden verwandte Arbeiten diskutiert und eine Fazit gezogen. [10] Kristian Kersting, Luc de Raedt, and Raiko Tapani. Logical hidden markov models.