Markov-Ketten sind mathematische Modelle, die Prozesse mit zufälligen Zuständen beschreiben, bei denen die Zukunft nur vom aktuellen Zustand abhängt und nicht von der Vergangenheit. Diese Eigenschaft wird als Markov-Eigenschaft bezeichnet.
Eine Markov-Kette besteht aus:
- einer Menge von Zuständen \( S = \{s_1, s_2, …, s_n\} \)
- einer Übergangsmatrix \( P \), die die Wahrscheinlichkeiten für den Übergang zwischen Zuständen beschreibt
Übergangsmatrix
Die Übergangswahrscheinlichkeiten zwischen Zuständen werden durch die Matrix \( P \) dargestellt:
$$ P = \begin{bmatrix} p_{11} & p_{12} & \dots & p_{1n} \\ p_{21} & p_{22} & \dots & p_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1} & p_{n2} & \dots & p_{nn} \end{bmatrix} $$
Jedes Element \( p_{ij} \) gibt die Wahrscheinlichkeit an, von Zustand \( s_i \) nach Zustand \( s_j \) zu wechseln:
$$ p_{ij} = P(X_{t+1} = s_j | X_t = s_i) $$
Stationäre Verteilung
Eine stationäre Verteilung \( \pi \) ist ein Wahrscheinlichkeitsvektor, der die langfristigen Aufenthaltswahrscheinlichkeiten der Zustände beschreibt:
$$ \pi P = \pi $$
mit der Nebenbedingung:
$$ \sum_{i=1}^{n} \pi_i = 1 $$
Anwendungsgebiete von Markov-Ketten
- Spracherkennung
- Finanzmodellierung
- Suchmaschinen-Algorithmen (z. B. PageRank)
- Genetik und Bioinformatik
- Künstliche Intelligenz (NLP, Reinforcement Learning, HMMs)
Markov-Ketten in der Künstlichen Intelligenz
1. NLP & Sprachmodellierung
Markov-Ketten werden in der Verarbeitung natürlicher Sprache (NLP) für:
- Wortvorhersage & Autovervollständigung
- Textgenerierung basierend auf n-gram Modellen
- Spracherkennung in digitalen Assistenten
Ein Trigramm-Modell sagt das nächste Wort basierend auf den letzten zwei vorher:
$$ P(w_n | w_{n-1}, w_{n-2}) $$
2. Hidden Markov Models (HMMs) in KI
Ein Hidden Markov Model (HMM) erweitert die klassische Markov-Kette um versteckte Zustände und ist essenziell für:
- Spracherkennung (Siri, Google Assistant)
- Maschinelles Übersetzen
- Bioinformatik (DNA-Sequenzanalyse)
3. Reinforcement Learning & Markov-Entscheidungsprozesse (MDPs)
Markov-Entscheidungsprozesse (MDPs) sind die Grundlage für viele Reinforcement-Learning–Algorithmen.