Künstliche Intelligenz II - Cheatsheet

A*-Algorithmus

Definition:

A* (A-Stern) ist ein Suchalgorithmus, der in Graphen die kostengünstigste Route von einem Startknoten zu einem Zielknoten sucht. Nutzt eine Kombination aus g(n) und h(n).

Details:

• g(n): Kosten vom Startknoten bis zum Knoten n
• h(n): Heuristische Schätzung der Kosten von n zum Ziel
• f(n) = g(n) + h(n): geschätzte Gesamtkosten
• Verwendet eine Prioritätswarteschlange (Open-List)
• Starte mit dem initialen Knoten; verschiebe nach Open-List
• Wiederhole: Nimm Knoten mit kleinstem f(n) aus der Open-List, verschiebe nach Closed-List
• Überprüfe Nachbarn des aktuellen Knotens
• Beende: Zielknoten erreicht oder Open-List leer

Convolutional Neural Networks (CNN)

Definition:

Convolutional Neural Networks (CNN) sind eine Klasse von tiefen, neuronalen Netzwerken, die hauptsächlich für die Verarbeitung von Bilddaten verwendet werden.

Details:

• Besteht aus Faltungs- und Pooling-Schichten.
• Faltungsschicht: Wendet Filter an, um Merkmale zu extrahieren.
• Pooling-Schicht: Reduziert die Dimensionalität (z.B. Max-Pooling).
• Aktivierungsfunktion: Häufig ReLU.
• Fully-Connected-Schicht am Ende für Klassifikation.
• Wichtige Parameter: Filtergröße, Stride, Padding.

Tokenisierung und Wortvektoren

Definition:

Tokenisierung segmentiert Text in kleinere Einheiten (Tokens), Wortvektoren wandeln Wörter in numerische Vektoren um.

Details:

• Tokenisierung zerlegt Text in Wörter, Phrasen oder Symbole.
• Wortvektoren repräsentieren semantische Beziehungen zwischen Wörtern.
• Populäre Modelle: Word2Vec, GloVe, FastText.
• Wortvektoren in niedriger Dimension: \vec{w} \in \mathbb{R}^n
• Kollokationen und Kontext durch umgebende Wörter erfasst.

Maschinelle Übersetzung

Definition:

Automatisierte Übersetzung von Text oder Sprache von einer natürlichen Sprache in eine andere mithilfe von Algorithmen und Modellen der künstlichen Intelligenz.

Details:

• Verfahren: Statistische MT (SMT), Neuronale MT (NMT), Regelbasierte MT
• NMT-Modell: Encoder-Decoder-Struktur
• Verwendung von Rekurrenten Neuronalen Netzwerken (RNN) und Long Short-Term Memory (LSTM)
• Aktuelle Modelle nutzen Transformer-Architekturen: Multi-Head Attention, Positionskodierung
• Wichtig: Training mit umfangreichen, annotierten Datensätzen; Qualität der Daten entscheidend
• Evaluation: BLEU-Score als Standard-Metrik

Supervised Learning (überwachtes Lernen)

Definition:

Form von maschinellem Lernen, bei der ein Modell aus gekennzeichneten Trainingsdaten lernt, um auf neue, ungekennzeichnete Daten zu schließen.

Details:

• Trainingsdaten bestehen aus Eingabe-Ausgabe-Paaren \((x, y)\).
• Ziel: Vorhersagemodell \(h: X \rightarrow Y\).
• Typische Algorithmen: Lineare Regression, Entscheidungsbäume, Neuronale Netze.
• Fehlerfunktion \({J(\theta)}\) zur Optimierung verwenden.
• Überwachtes Lernen umfasst Klassifikation (diskret) und Regression (kontinuierlich).

Reinforcement Learning

Definition:

Lernmethode, bei der ein Agent durch Handlungen in einer Umgebung Belohnungen maximiert.

Details:

• Agent wählt Aktionen basierend auf einer Politik \(\pi\)
• State \(s\), Aktion \(a\), Belohnung \(r\), Transition-Funktion \(P(s'|s,a)\)
• Q-Learning und SARSA als Beispiele
• Q-Funktion: \[Q(s,a) = E[\sum_{t=0}^\infty \gamma^t r_t|s_0 = s, a_0 = a]\]
• Erkundung vs. Ausnutzung
• \(\alpha\): Lernrate, \(\gamma\): Diskontfaktor

Nash-Gleichgewicht

Definition:

Situation in einem Spiel, in der kein Spieler seinen Nutzen durch einseitige Änderung der Strategie verbessern kann. Jede Strategie eines Spielers ist die beste Antwort auf die Strategien der anderen Spieler.

Details:

• Formale Definition: Strategiekombination \(s_1, s_2, ..., s_n\) ist ein Nash-Gleichgewicht, wenn keine Spielerstrategie \(s_i\) so geändert werden kann, dass der Nutzen \(u_i\) zunimmt, gegeben die anderen Strategien \(s_{-i}\).
• Mathematisch: \[ \forall i, \forall s_i' : u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i}) \]
• Relevanz in KI: Verwendung in Multi-Agenten-Systemen zur Vorhersage stabiler Zustände.
• Beispiele: Gefangenendilemma, Cournot-Wettbewerb.
• Existenz: Jedes endliche Spiel mit gemischten Strategien hat mindestens ein Nash-Gleichgewicht (Nashs Existenztheorem).

Markov-Entscheidungsprozesse (MDP)

Definition:

Formales Modell zur Entscheidungsfindung in stochastischen Umgebungen.

Details:

• MDP durch Tupel \(S, A, P, R\) definiert:
• S: Zustandsraum
• A: Aktionsraum
• P: Übergangswahrscheinlichkeiten, \(P(s'|s, a)\)
• R: Belohnungsfunktion, \(R(s, a)\)
• Ziel: Policy \(\pi: S \rightarrow A\) finden, die erwarteten kumulativen Belohnungen maximiert.
• Bellman-Gleichungen für Wertfunktion \(V(s)\) und Q-Funktion \(Q(s, a)\):
• Wertfunktion: \[ V(s) = \mathbb{E}[R(s, \pi(s)) + \gamma V(s')] \]
• Q-Funktion: \[ Q(s, a) = R(s, a) + \gamma \sum_{s'} P(s'|s, a) V(s') \]
• Diskontfaktor \(0 \leq \gamma < 1\)