49
ADM (Subject) / Applied Discrete Modelling (Lesson)
Advertisement
- Was ist eine DTMC? - Discrete Time Markov Chain - Markov CHains sind stochastische Prozesse, bei denen endlich viele States durch Transitions verbunden sind - Wird als Directed Graph dargestellt und die Summe der Transition-Wahrscheinlichkeiten von einem State muss 1 ergeben - Das System kann sich nur an diskreten Zeitpunkten ändern und State Changes finden nur an diesen Zeitpunkten statt - Wahrscheinlichkeiten sind deterministisch
- Was ist die Markov Property und gebe Beispiele welche diese erfüllen? - Die Auswahl des nächsten States hängt nur von den momentanen States ab - Also ist die Wahrscheinlichkeitverteilung "memoryless" - DTMC müssen die Markov Property erfüllen - Beispiele: Roulette, Münzwurf, Lotto
- Gebe ein Beispiel für eine DTMC an! - Münzwurf zweier Spieler um Geld (Random Walk) - Jeder besitzt am Anfang 100€ und setzt pro Wurd 50€ - Zeichnung auf den Blättern
- Wie werden DTMCs mathematisch beschrieben? 1. State Probability Vektor (Stochastischer Vektor -> Summe der Elemente = 1) - Gibt an zu welcher Wahrscheinlichkeit man sich in welchem State befindet 2. Transition Probability Matrix (Stochastische Matrix -> Summe der Elemente jeder Zeile = 1) - Gibt an mit welcher Wahrscheinlichkeit man von State i zu State j wechselt bzw. in State i bleibt
- Wie werden DTMCs simuliert? 1. Power Method - In jedem Zeitschritt den aktuellen State Vektor mit der Transition Matrix multiplizieren - Probleme bei sehr kleinen Wahrscheinlichkeiten (wie bei einer nearly decomposable DTMC) 2. Matrix Powering - π12 = (π0 * P^8) * p^4
- Was ist eine Steady-State Solution? Ein Systemstate der sich im nächsten und allen darauffolgenden Zeitschritten nicht mehr verändert
- Was ist eine Stationary Solution? Die Werte des State Vektors bleiben gleich aber eigentlich vertauschen sich die Werte π0 = (0,1 0,9) πx = (0,5 0,5) πx+1 = (0,5 0,5)
- Was ist eine Transient Solution? Man schaut nach den Wahrscheinlichkeiten der States an einem bestimmten Zeitpunkt
- Was ist ein absorbing State? Die Wahrscheinlichkeit in diesem State zu bleiben ist 1
- Erkläre die Google Pagerank-Berechnung! - Menschen benutzen zu 85% Links und zu 15% schreiben sie URLs - Für beides werden Transitions Probability Matrizen aufgestellt - Die Matrix für die Links beschreibt welche Links von einer zu einer anderen Seite führen - Zeichnung auf den Blättern - Die Matrix für die URLs hat überall den selben Wert. Bei 3 Seiten überall 1/3 - Jetzt wird die Matrix der Links mit 0,85 und die der URLs mit 0,15 multipliziert - Dann werden beide addiert und man erhält wieder eine stochastische Matrix
- Advertisement
- Was ist eine CTMC? - Continuous Time Markov Chain - Markov Chains sind stochastische Prozesse, bei denen endlich viele States durch Transitions verbunden sind - Das System verändert sich kontinuierlich - Die Transition-Wahrscheinlichkeiten sind bei CTMCs Rates - Die Rates müssen konstant sein und sind daher auf die Exponentialverteilung begrenzt - Werden dargestellt durch einen Directed Graph ohne Kanten, die auf den eigenen State zeigen
- Beschreibe ein Beispiel einer CTMC - Wasserfluss von einem Eimer in einen anderen - Skizzen und Matrix auf dem Blatt - Inflow - Outlow - bekanntestes Beispiel: M / M 1 Queueing System - Ist wie bei dem Birth-Death Beispiel
- Wie werden CTMCs mathematisch beschrieben? - Die Transition Rate ist der Parameter der Probability Density Funcation und der Cumulative Distribution Function der Exponentialverteilung - Diese Funktionen beschreiben den Flow von einem State in den Nächsten - Die Rates werden in einer Generator Matrix festgehalten - Die diagonalen Werte der Matrix sind die negativen Summen aller Rate-Werte dieser Reihe - Die Summe jeder Reihe ergibt somit 0 - Der System-State wird wie bei der CTMC in einem Vektor festgehalten
- Gebe eine intuitive Erklärung der CTMC Gleichung! - Inflow - Outflow - Zeichnung mit Crossover Areas auf dem Blatt - Gleichungen auf dem Blatt - Wird für den ganzen Vektor zu Q*π generalisiert
- Wie findet man die Steady State Solution einer CTMC? - Steady State: Q*π = 0 - Teile Q in 2 Matrizen M und N - Iterativer Algorithmus - Umformung nach πk+1 = M^-1 * N - Methoden zum Teilen der Generator Matrix 1. Jacobi: - M ist der diagonale Teil der Generator Matrix - N is die negative Summe des oberen und unteren dreieckigen Teil der Generator Matrix 2. Gauss-Seidel: - M ist die Summe der Diagonalen und des oberen Teils der Generator Matrix - N ist der negative Teil des unteren dreieckigen Teils der Generator Matrix 3. SOR (Successive Overrelaxation) - beschleunigt den Gauss-Seidel durch einen Relaxionsparameter - Gauss-Seidel (+SOR) viel schneller als Jacobi
- Wie berechnet man die Transient Dolution einer CTMC? Ergeben sich bei einer der Methoden Nachteile? 1. Lösen des Initial Value Problems mit der Runge-Kutta Methode 2. Uniformization mit der Jensen Methode 3. Konvertieren der CTMC in eine DTMC - Diskretisierung durch Timesteps - Timestep sollte kleiner als 1 / das größte Matrix Element sein - Bilden einer stochastischen Transition Probability Matrix -> P = I + Δt * Q --> Generator matrix mit dem Timestep multiplizieren --> Identity Matrix addieren um eine stochastische Matrix zu erzeugen - Nachteile: -- keine Solutions zwischen den Timesteps -- Veränderungen zwischen den Timesteps können vorkommen und werden nicht von der DTMC erfasst, was das Ergebnis verfälscht
- Was ist ein GSPN? - Generalized Stochastic Petri Net - Dienen zur Modellierung von Discrete Event Simulation - Die Timed Transitions sind auf die Exponentialverteilung limitiert und Imidiate Transtitions sind erlaubt - Sie bestehen aus: Places, Transitions, Arcs, Tokens
- Was sind Markings, State Space und State Space Explosion? - Markings beschreiben die Anzahl Tokens in jedem Place - State Space sind alle erreichbaren Markings - State State Explosion: Durch hinzufügen von Tokens oder Places entstehen ungleich mehr Markings
- Was sind Vanishing und Tangile Markings? - Vanishing Markings sind Markings, die durch eine Immediate Transition mit dem nächsten Marking verbunden sind --> Daher können sie bei der Modellierung der CTMC entfernt werden - Tangile (handfeste) Markings sind alle anderen Markings
- Was ist eine (Extendable) Reachability Graph? - Ein Extendable Reachability Graph stellt alle erreichbaren Markings und ihre Transitions dar - Ein Reachability Graph hat keine Vanishing States
- Was ist die Verbindung zwischen GSPNs und CTMCs? - Beide sind reduziert auf Transitions mit Exponentialverteilung
- Was sind die Vor- und Nachteile von Discrete Event Simulation gegenüber Aufsetzen und Läsen einer CTMC? Vorteile: - keine State Space Explosion beim Nutzen von vielen Places und Tokens Nachteile: - man braucht in den meisten Fällen sehr viele Wiederholungen um eine Steady State Solution zu erzeugen - Man braucht auch sehr viele Wiederholungen um seltene Events zu simulieren
- Was sind Messgrößen für GSPNs? - Durchschnittliche Anzahl an Tokens in einem Place (Länge der Schlange) - Wahrscheinlichkeit, dass ein Place leer ist - Wahrscheinlichkeit, dass eine Transition aktiv ist - Durchschnittlicher Throughput ( Durchschnittliche Anzahl an Firings pro Zeiteinheit)
- Was ist ein Proxel? - Probability Element - Können im Gegensatz zu Markov Chains alle Wahrscheinlichkeitsverteilungen simulieren - SImulation findet in diskreten Timesteps statt (wie bei DTMCs) - Berechnet nur die Transitions, die wirklich möglich sind (nicht wie bei DTMCs mit der ganzen Matrix)
- Welche Informationen enthält ein Proxel? P = (s, t, R, Pr) - State des Systems s = (m, τ->) -- Markings (welcher State) m -- τ-> ist der Age Vektor --- Age bedeutet die Zeit, welche die Transition aktiv ist ohne zu feuern - Systemzeit t - Baum von der Vergangenheit des Proxels R - Wahrscheinlichkeit des Proxels Pr _______________ Meistens reicht P = (m, τ->, Pr) für die Simulation
- Was sind mögliche Probleme, Fehler und Ungenauigkeiten von Proxels? Fehler - Es ist nur ein State Change pro Timestep möglich - Nur Approximation einer Euler Integration Probleme - Die Proxelanzahl wächst exponentiell und verdoppelt sich pro Timestep -----> Mergen von Proxeln mit denselben State und Timestep durch Addieren der Wahrscheinlichkeiten -----> Wenn die Wahrscheinlichkeit eines Proxels unter eine Grenze fällt, den Proxel löschen Tradeoff - Bei der Wahl des Timesteps findet ein Tradeoff zwischen Genauigkeit und Effizienz statt
- Was ist Rage Enable und Race Age? Race Enable - Die Transition startet die zeit neu wenn sie deaktiviert und wieder aktiviert wurde Race Age - Die Transition merkt sich die zeit bei der Deaktivierung und führt sie bei Aktivierung fort
- Was ist Rate Reward und Impulse Reward? Rate Reward - Für jeden Timestep bei dem man sich in einem bestimmten State aufhält, werden Kosten von x hinzugerechnet ----> Auto hält im Parkhaus Impulse Reward - Bei bestimmten Transitions werden Kosten von x hinzugerechnet ----> Auto kommt aus der Werkstatt
- Was ist die Hazard Rate Function? - Wenn ein Event noch nicht passiert ist, brauchen wir zur Berechnung, mit nicht memoryless Wahrscheinlichkeitsverteilungen, die Wahrscheinlichkeit ob das Event im nächsten Zeitintervall passiert UNTER DER BEDINGUNG, dass es noch nicht passiert ist. - μ(x) = Probability Density Function / (1 - Cumulative Distribution Function) - Also in jedem Timestep μ(x) = [ f(x) / (1-F(x)) ] * Δt
- Wie werden Proxels bei der Analyse von SPNs genutzt? - Geeigneten Timestep auswählen -> Tradeoff - Initialen Proxel bestimmen (In welchem State befindet man sich) - Für jeden Timestep schauen welche Transitions möglich sind und dem entsprechend eine neue Ebene im Baum mit Proxeln füllen. ---> Wahrscheinlichkeiten berechnen, Age erhöhen oder auf 0 setzen und schauen ob man Mergen kann
- Advertisement
- Für welche Modelle ist die Proxel-basierte Simulation besonders geeignet? - Für Modelle die nicht nur aus exponentiellen Transitions bestehen - Wenn Rare Events auftreten: Da man für diese bei Event-basierter Simulation viel zu viele Durchläufe braucht
- Was ist eine HMM? - Hidden Markov Model - Ein doppelt stochastischer Prozess - Es ist eine Markov Chain, dessen States mit bestimmter Wahrscheinlichkeit verschiedene Symbole ausgeben
- Was sind die Elemente eines HMM? HMM = (s, v, A, B, π) - States s = (s1, ... , sn) Bsp (Rainy, Sunny) - Symbole v = (v1, ... , vn) Bsp (clean, shop, walk) - Transition Probability Matrix A = P = { aij } NxN - Matrix des 2. stochastischen Prozesses B = { bi(vk) } - Probability State Vektor π
- Was sind Trace, Path und Model bei HMM? - Path Q ist die Sequenz der States - Trace O ist die Ausgabesequenz der Symbole - Model = (A, B, π) -> Bestimmt das Verhalten des Systems
- Was ist ein typisches Beispiel einer HMM? Abhängigkeit der Aktivitäten vom Wetter -> Skizze auf dem Blatt
- Was sind die 3 Probleme, die man mit einem HMM lösen kann? 1. Evaluation - Trace ist gegeben - Berechnen der Wahrscheinlichkeit des Modells - Dient zum Vergleich von Modellen - Dient zum Vergleich von Traces in einem Modell - Wird mit dem Forward Algorithmus berechnet 2. Decoding - Trace ist gegeben - Bestimmen welcher Path die höchste Wahrscheinlichkeit hat - Forward Algorithmus und am Ende gucken welcher der beste Path ist - Viterbi Algorithmus, der ähnlich wie der Forward Algorithmus funktioniert aber immer nur den besten Path behält 3. Training - gegeben ist ein großer Satz von Ausgabe-Symbol-Sequenzen - Ein Model finden, welches die Evaluationswahrscheinlichkeit maximiert - Man trainiert also das Model - Baum-Welsh Algorithmus
- Wie berechnet man Evaluation, Decoding und Training? 1. Evaluation - Wahrscheinlichkeit für alle möglichen Paths berechnen - (csw|RRS) = πr * Brc * Arr * Brs * Ars * Bsw - Also berechnet man die Wahrscheinlichkeit in dem jeweiligen State zu sein und mit welcher Wahrscheinlichkeit man in diesem State das Symbol ausgibt - Die Summe aller Path-Wahrscheinlichkeiten ergibt die Wahrscheinlichkeit des Modells - Forward Algorithmus genannt 2. Decoding - Entweder Foward Algorithmus und am Ende gucken welcher der beste Path ist - Oder Viterbi Algorithmus, der so ähnlich abläuft aber immer nur den besten Path behält 3. Training - Iterativer Ansatz um das Model schrittweise zu verbessern - Es wird dafür der Baum-Welsh Algorithmus verwendet
- Was ist ein HnMM? - Hidden non-Markovian Model - Kombination von Discrete Stochastic Models (DSM) und Hidden Markov Models (HMM) - Es sind alle Wahrscheinlichkeitsverteilungen möglich - Die Transitions geben die Symbole aus und nich die Places
- Was sind die Elemente eines HnMM? HnMM = (S, v, TR, A, R0) - States s = {s1, ... , sn} - Symbole v = {v1, ... , vn} - Transitions/Activities = {TR1, ... , TRn} ----- TR = (Wahrscheinlichkeitsverteilung mit Parametern, ID, Wahrscheinlichkeit des Ausgabe-Symbols, Race Enable oder Race Age) - Transition Probability Matrix A = { aij } - Initiale States R0 = π0
- Gebe ein Beispiel für ein HnMM an! - Maschine mit 3 Places (Wartung, OK, Fehler) und einem Token. - Zwei der Transition geben verschiedene Euro Beträge als Symbol aus - Die Ausgabe-Sequenz besteht aus dem Zeitpunkt und dem Ausgabe-Symbol O = (Tag, Symbol) = (2, 30€)
- Was ist die Motivation beim Kombinieren von SPNs und HMMs? - Nutzen aller Wahrscheinlichkeitsverteilungen - realistischer/flexibler - Herausfinden was passiert ist, damit diese Trace entstanden ist - Patient: Mögliche Krankheitsverläufe anhand der Sequenz der Symptome bestimmen
- Was sind valide Paths bei HnMMs? 1. Kein Symbol ausgeben - Im selben State bleiben - Transition gibt kein Symbol aus 2. Symbole im Timestep - Transition gibt Symbol aus mit einer Wahrscheinlichkeit größer als 0 3. Symbolausgabe hängt nicht vom State Change ab (Patient)
- Wie würdest du die Proxeldefinition erweitern um Path und Symbol Ausgabesequenz Analyse zu ermöglichen? - Proxels nicht mergen - Durch einen Baum für alle möglichen Symbole und dessen Wahrscheinlichkeit, die durch den Verlauf der Simulation bei diesem Proxel enstanden sein können
- Was ist ein Anwendungsfall für HnMMs? Gestenerkennung bei Multitouchgeräten (Pad, Smartphone)
- Was für Modeltypen gibt es bei HnMMs? Esome = Manche Transitions geben Symbole aus Eall = alle Transitions geben Symbole aus
- Was für Transition-Verhalten gibt es bei HnMMs? Tkeep = non-Markovian Transitions werden nicht zurückgesetzt Treset = wenn eine non-Markovian Transition feuert, werden alle Transitions zurückgesetzt
- Was für State Change-Arten gibt es bei HnMMs? SCnT = mehrere State Changes pro Transition SConeT = nur ein State Change pro Transition
- Wie sieht die Variationsmatrix bei HnMM aus? Esome & Tkeep = HnMM -> Proxel Esome & Treset = Proxel mit Regeneration Points Eall & Tkepp = CHnMM Eall & Treset = GHSMM
- Was sind CHnMM und GHSMM? CHMM = Conversive Hidden non-Markovian Model - hat keine festen Timesteps - der nächste Timestep immer beim nächsten State Change GHSMM = Generalised Hidden Semi Markov Model