Seminare Flashcards
Zeitreihen Def
- Gegeben sei eine Folge Events/forensische Beobachtungen
- Jedes Event wird einer endlichen Symbol-/Indexmenge zugeordnet
- wie viel Zeit vergangen ist, ist irrelevant, geht nur um Ablauf/Reihenfolge
Zeitreihenvergleich Def
- Vgl. zweier Wörter
- Hamming-Abstand: Anzahl unterschiedl. Events/Symbole zwischen 2 gleichlangen Wörtern
- Levenstein Algorithmus/Ablauf: Anzahl unterschiedlciher Events/Symbole zwischen 2 ungleichlangen Wörtern
- Wörter entsprechen Abfolge der Indexmengen
Plausibilität im quantitativen Sinne
- f(H) → f(H, D) (a posteriori)
- D = Beobachtungen / Daten f(H) = Plausibilität
- man hat 2 Hypothesen. Frage: welche Hypothese ist wie plausibel? wir aktualisieren unser Vorabwissen, was ist plausibel
- H1/H2 -> sind etwa 50/50 (apriori) -> X: Daten/Beobachtung => damit können wir unser aprioriwissen aktualisierien
-> wohin verschiebt sich Plausibilität?
-> P(h1|X) über Bayes (für die Aktualisierung des a priori wissens)
Was ist ein Modell?
Abbildung (Reflektion) unseres Grundverständinisses über die natürliche Realität/Ist nicht Realität, bildet sie nur ab
-> mathematische Struktur
Arten von Modellen
nicht linguistisch
* materielles
* graphisches
linguistisch
* Kalkülmodelle
-> Prädikaten Logik: es ist dies und jenes gegeben, also gilt das
* mathematisch
-> modellhafte Reduktion der Sprache
-> progosefähig
-> z.B.: Semantik, phys. Formeln, Fallsimulation
Eigenschaften mathematischer Modelle
- formelle Repräsentation eines Systems
- zweckmäßige Vereinfachung
-> berechenbar
Mathematische Modelle können in verschiedene Klassen unterteilt werden.
- Dynamisches Modell
-> Zustandsgrößen und Signale hängen von der Zeit ab. Gegenteil: statisches Modell. - Deterministisches Modell
-> Zu jedem Zeitpunkt sind die Zustandsgrößen und Signale eindeutig bestimmt. Gegenteil: stochastisches Modell; Größen können zufällige Werte annehmen. - Diskretes Modell
-> Werte der Zustandsgrößen sind nur für diskrete Zeitpunkte, etwa t∈N , erklärt. Zusätzlich kann auch die Wertemenge diskret (abzählbar) sein. Gegenteil: kontinuierliches Modell; Werte sind für t∈[a,b]⊂R+ erklärt.” - Bei der Modellbildung lassen sich folgende Prozesse differenzieren:
1. Abgrenzung - Nichtberücksichtigung irrelevanter Objekte
2. Reduktion - Weglassen von Objektdetails
3. Dekomposition- Zerlegung, Auflösung in einzelne Segmente
4. Aggregation - Vereinigung von Segmenten zu einem Ganzen
5. Abstraktion - Begriffs- bzw. Klassenbildung.
Aufgaben mathematischer Modelle
- Beschreibung des Verhaltens komplexer Systeme
- gesuchte wird ein mathemat. Zusammenhand, der die zeitlichen Entwicklung wiedergibt, dass zudem prognosefähig ist
- Prognose: Risultat einer Simmulation <-> forensische Beobachtung/Daten <-> Experiment
Simulation
- Anwendung von Modellen zum Zwecke der Datenerzeugung mit Hilfe der Modellstruktur, z.B. zur Validierung oder zur Vorhersage der Systemreaktion.
oder
- eine Vorgehensweise zur Analyse von Systemen, die für die theoretische oder formelmäßige Behandlung zu komplex sind. Dies ist überwiegend bei dynamischem Systemverhalten gegeben. Bei der Simulation werden Experimente an einem Modell durchgeführt, um Erkenntnisse über das reale System zu gewinnen.
Simulation versus Beobachtung
- nach Modellbildung u. Simulation sind Simulationsergebnisse mit Wirklichkeit zu vergleichen
- Entsprechen Abweichungen nicht den Erwartungen (das Maß für einen akzeptablen Fehler hängt vom Problembereich ab) beginnt die Suche nach dem Grund für die Abweichung
-> Hierfür sind dann die einzelnen Teilschritte zu hinterfragen - Insbesondere unterscheidet man zwischen:
- Modellfehler
-> Nicht erfasste physikalische Prozesse, Annahmen über Homogenität, Verteilungen, Form von Abhängigkeiten, etc. - Datenfehler
-> Ungenügend genau erfasste Daten an der Systemgrenze (Rand- und Anfangsbedingungen) oder Parameter. - Simulationsfehler (auch Approximationsfehler)
-> Fehler die durch Approximation des Modells zum Zwecke der numerischen Lösung entstehen.
Posterior odds ratio versus Bayes factor
P(H1 = Löwe|D)/P(H2=nichtLöwe|D) = (P(D|H1=Löwe)/P(D|H2=nichtLöwe)) * ((P(H1=Löwe)/P(H2=nichtLöwe))
Posterior odds ratio = Bayes factor * Prior odds ratio
- Vorteil:
-> hierbei die schwerbestimmbare (und oftmals nicht analytisch beschreibbare) marginalisierende Konstante herausfällt.
Definition relative Plausibilität
- gegeben zwei konkurrierende Hypothesen:
-> Hi, Hj ∈ M : P(Hi | D) / P(Hj | D) ∈ [0, ∞]
-> posterior odds ratio versus Bayes factor
Satz von Bayes - gegeben sei eine Menge von Hypothesen
- ℌ = (H1, H2, …, Hn) Hi ∈ ℌ
- P(Hi | D) = P(D | Hi) P(Hi) / ⅀k=1 bis n P(D | Hk) P(Hk)
- P(Hi | D) = a posteriori Wkt.
- P(D | Hi) = Wkt., dass Hi die Daten erklärt
- P(Hk) = a priori Wkt. und marginalisierende Konstante
- Marginalisierende Konstante benötigen wir, damit:
1) ∀ Hi ∈ ℌ: P(Hi | D) ∈ [0, 1]
2) ⅀k=1 bis n P(Hk | D) - gegeben seien neue Beobachtungen D2, dann kann man schreiben: (Bayesian Updating)
-> P(Hi | D2) ∝ P(D | Hi) * P(Hi | D)
-> P(Hi | D) → alte posteriori entspricht der neuen a priori Wkt.
∝ = proportional
Absolute Plausibilität
P(H|E)
Maximum-Likelihood Prinzip
Sofern keine weiteren Randannahmen existieren, ist jedes Modell zu wählen, welches auf gegebenen Daten D maximal wahrscheinlich ist.
Bsp: Eine Stichprobe einer metrischen Variablen X sei gegeben.
Dann ist das arithmetische Mittel X̅ der SP jene Punktschätzung für 𝞵, die die Annahme X ~ N (𝞵, 𝞼) mit Wkt P(X | 𝞵, 𝞼) maximiert.
- Was ist eine Theorie?
Bezeichnet das systematische und nach bestimmten Prinzipien geordnete Beobachtung und erklären der Realität - Bewertung eines binären Klassifikationsmodells
Bewertungsmaße bekannt:
sensitivity (recall, true-positive rate, TPR)
specificity (true-negative rate, TNR)
precision (true-positive predictive value)
- Welcher punktgeschätzten a posteriori Wahrscheinlichkeit entspricht sie?
-> Inhaltliche Bedeutung wie TP - Was besagt die posterior odds ratio P(y+|y^+)/P(y−|y^+)? (Querverweis: Seite 1 Abb. unten)
-> Allgemein: Verhältnis zw. den posterio Wahrscheinlichkeiten zweier Events / Hypothesen → Kontrast der Hypothesen P(y+/y+)/P(y-|y+) → Unter Bedingung, dass klassifizierter Datenpunkt positiv ist, wie groß die ist wkt, dass Datenpunkt tatsächlich positiv ist? (Verhältnis zw. TP und FP)
-> Im Zähler: Wkt, gegeben ein pos. klass. Datenpunkt, dass Datenpunkt tatsächlich positiv ist;
-> Im Nenner: Wkt, gegeben ein pos. klass. Datenpunkt, dass Datenpunkt tatsächlich negativ ist - Wie liest man diese bedingte Wahrscheinlichkeit ab?
-> von rechts nach links! - P(Spurenverursacher|Spuren)/P(Spurenverursacher|Spuren)
→ gegeben der Spuren, wie groß ist die Wahrscheinlichkeit, dass sie vom Spurenverursacher sind GETEILT DURCH gegeben der Spuren, wie groß ist die Wahrscheinlichkeit, dass sie nicht vom Spurenverursacher sind - Inwiefern können wir den Zeugen als binären Klassifikator verstehen? Beim Taxiproblem: Entweder grünes Taxi → als grün erkannt oder als blau erkannt oder blaues Taxi → als grün erkannt oder als blau erkannt
- Was sind, in diesem Kontext, TPR und false-positive rate?
-> TPR: TP / P = wie oft wird die tatsächliche Farbe erkannt?
-> FPR: FP / N = wie oft wird die tatsächliche Farbe nicht erkannt?
- „Konkret: Es ist ein Wahrscheinlichkeitsmodell M zu definieren, das den Beobachtungen D eine Wahrscheinlichkeit zu ordnen kann. Somit sind auch darin eingeschlossene Zufallsvariablen X={X1,X2,…,XK} festzulegende Modellannahmen. Je nach Fragestellung treffen wir gemäß P(X=D|M) bzw. P(M|X=D) Signfikanzaussagen“ - Seminar
=> Signifikanz ist also immer Signifikanz mit Bezug auf ein Zufallsexperiment
-> Signifikanz nur bei Hypothesen Prüfen
keine Verallgemeinerungen
* Forensisch: je nach Kontext anders bewerten, bevor man in Modellierung kommt muss man sagen: “DAS MUSS SIGNIFIKANT SEIN”
-> Was ist Signifikant in diesem Kontext? Prüfungsfrage! -> P(H1|X) hinreichend klein (nicht mehr plausibel) => H1 bspw. nicht plausibel
Monte Carlo Simulation
- Verfahren aus der Stochastik
- sehr große Zahl gleichartiger Zufallsexperimente ist Basis
Es wird dabei versucht, analytisch nicht oder nur aufwendig lösbare Probleme mit Hilfe der Wahrscheinlichkeitstheorie numerisch zu lösen“ – Seminar - probabilistisches Modell, das ein Element der Unsicherheit oder Zufälligkeit in seine Vorhersage einbeziehen kann
- jedes Mal andere Ergebnisse
- Fungiert nach dem Gesetz der großen Zahlen → wie wahrscheinlich, dass Person diagonal gelaufen ist? → Binomialverteilung
- Problem: Wenn KEINE analytische Betrachtung möglich, müssen wir uns annähern
- In Bezug auf die Forensik: Fluchtweg eines Verdächtigen.
-> Wie plausibel ist, dass Spur zum Täter passt?
-> Wie wahrscheinlich, dass Person gesehen wurde, aber nur „zufällig“ da war?
-> Wie viele der Fluchtwege gehen am gelben Haus vorbei?
-> Oder Fallsimulation: freier Fall statisch ausschließbar (unter Annahme, dass das Modell korrekt ist)
Zeitreihen - Modell
- Die zeitliche Relation zwischen zwei Ereignissen, kodiert si und sj, geht verloren. Wir abstrahieren im Modell die Ereignisabfolge - aber nicht wie viel Zeit zwischen Ereignissen vergangen ist.“
=> keine Zeitstempel nur chronologischer Ablauf
Dotplot Allgemein
- Gegeben seien zwei Sequenzen X=(x1,…,xm) und Y=(y1,…,yn) mit Längen m bzw. n sowie eine binäre Matrix M mit Größe m×n. Dann entspricht der Dotplot der Matrix M mit den Einträgen:
Mi,j={1 xi=yj
0 xi≠yj
Alignment Definition
- Gegeben seien zwei Sequenzen X=(x1,…,xm) und Y=(y1,…,yn) sowie das um das Lückensymbol “−” erweiterte Alphabet Ω∗=Ω∪{−}.
- Dann entspricht das Alignment von X und Y den editierten Wörtern X∗=(x∗1,…,x∗k) und Y∗ (y∗1,…,y∗k) gleicher Länge k über dem Alphabet Ω∗.
- Die Abfolgen der Editieroperationen, mit denen X in X∗ und Y in Y∗ überführt wird, ist gemäß einem Kostenmodell optimal.
=> wird mit dem Lückensymbol – erweitert
=> Fehlpaarung = Mismatch
=> wir können ein Alignment als einen “Pfad durch die Optimierungs-Matrix / Dotplotmatrix verstehen”, wobei wir von einem Matrixelement gehen können - diagonal = Match/Missmatch
- nach oben = Lücke in y
- nach links = Lücke in x
Hamming-Abstand
- Eines der einfachsten Abstandsmaße für Sequenzen
- Minimaler Abstand zweier Sequenzen keine Lücken
→ nur Anzahl von Fehlpaarungen berücksichtigen gleiche Länge (Sequenz)
Levenshtein - Alignment und Abstand Definition
- Gegeben seien zwei Sequenzen X=(x1,…,xm) und Y=(y1,…,yn) sowie das um das Lückensymbol “−” erweiterte Alphabet Ω∗=Ω∪{−}.
- Dann entspricht das Alignment von X und Y den editierten Wörtern X∗=(x∗1,…,x∗k) und Y∗ (y∗1,…,y∗k) gleicher Länge k über dem Alphabet Ω∗. Die Abfolgen der Editieroperationen, mit denen X in X∗ und Y in Y∗ überführt wird, ist optimal dadurch, dass die Anzahl von Editieroperationen minimal ist.
- Kostenmodell:
-> fügen einer Lücke: +1
-> assen eines Mismatches: +1
-> assen eines Matches: 0 - Bemerkungen:
1. x * & y * haben am Ende gleiche Länge ^= K
2. Levenshtein-Abstand dl(x,y) entspricht Anzahl-s-terminale Lücken und Anzahl-e-terminale Lücken sofern x & y in orangenen Abschnitt identisch sind. (= Abstand muss minimal sein)
dj(x,y)= ∑ { 0, xt^ * = yt^ *
1, xt^ * ≠ yt^ *
K (oben), k=1 (unten)
venshtein-Abstand entspricht dieser minimalen Anzahl an Editieroperationen.
Optimierungs-Matrix
- Di größe: (m+1)(n+1)
- Erweiterung durch (damit wir Lücken einfügen können!)
-> Nullzeile
-> Nullspalte
-> um s-terminale Lücken in x & y abbilden zu können - Doo: Element oben links in der Matrix („Startpunkt“)
- Dm,n: Element unten rechts („Endpunkt“)
- Di,o: i-tes Element in der Nullspalte
- Do,j: j-tes Element in der Nullzeile
** Bemerkung: Da eine s-terminale Lücke in x / y mit länge i / j uns + 1 * i / j kosten, initialisieren wir Di,o = +1 * i bzw. Do,j = + 1 * j ** - di,j = kürzester Weg von Doo nach Dij
- es folgt:
dj(x,y)= ∑ { 0, xt^ * = yt^ *
1, xt^ * ≠ yt^ * } = min = { Dm-1, n-1 (0 od. +1)
Dm-1,n (+1)
Dm,n-1 (+1)
K (oben), k=1 (unten)
Dotplot vs Optimierungsmatrix vs Scoringmatrix
- Dotplot: Kein Kostenmodell, sondern visualisiert gleiche Elemente zweier Sequenzen
- Optimierungsmatrix: Berechnungstruktur, Bei Optimierungsmatrix soll das beste/optimale Alignment zu finden, ist die Berechnungsstruktur
- Scoringmatrix: Zeigt die Kosten an
Was ist eine sog. Scoring-Matrix/Austauschmatrix (Vo4.28)? Stimmt die folgende Aussage: “Die Scoring-Matrix entspricht nicht der Optimierungs-Matrix”? Begründen Sie Ihre Entscheidung.
- Bei Scoring-Matrix werden Austauschwahrscheinlichkeiten eingetragen, sind alle Austausche gleich wahrscheinlich? Wie viel kostet es ein Element durch ein anderes zu ersetzen (siehe Übung 8) -> Hat nix mit einem optimalen Pfad zu tun, sondern zeigt nur Kosten an
Weshalb ist unter folgenden Bedingungen eine Matrix nicht mit dem Levenshtein erzeugt wurden? Gap = 2, Mismatch = 1
Levensthein: Lücke und Missmatch = 1
→ Bei Kosten hat Gap=2
Berechnung einer Matrix
- Hinweis: Labud’sche Regel: Diagonal schlägt bei Gleichstands des Scorings die jeweils anderen Editiertoperation
- Iterative Berechnung
-> 2. Schritt des NWL-Algo.
-> für i=1,…,n (Zeilenweise)
-> für j=1,…,n (Zeilenweise) - Rekursive Berechnung
Dm,n = min = { Dm-1, n-1 + s(xm,yn)
Dm-1,n +Lückenkosten
Dm,n-1 +Lückenkosten
Di,j = min = { Di-1, j-1 + s(xi,yj)
Di-1,j +Lückenkosten
Di,j-1 +Lückenkosten
K (oben), k=1 (unten)
Was bedeutet der Begriff Dynamische Programmierung? In wie fern wird zur Lösung des Alignment-Problems das Gesamtproblem in Teilprobleme zerlegt und ersteres dadurch optimal gelöst?
Beim dynamischen Programmieren unterteilt man das Problem in eine Einzelentscheidungen und kleiner dimensionierte Probleme.
Bei der Überführung von einem Alignment in ein anderes wird bei jedem einzelnen Element eine Editieroperation so gewählt, dass die Kosten dabei minimal sind.
+ : Das Verfahren findet ein globales Optimum, findet das Aligment mit dem besten Score bei gegebenen Parametern
- : Häufig haben viele Aligments den selben Score
