Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen -

Probalistisches Lernen

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Wahrscheinlichkeiten und Bayes Regel

Wahrscheinlichkeiten und Bayes Regel

Witten, DMPMLTaT, pp. 335

• In einem probalistischen Ansatz sind die Dateninstanzen gemessene Ereignesse oder Beobachtungen.
  • Die Dateninstanzen in D bilden Zufallsvariablen ab!

Es sei A eine Zufallsvariable mit diskreten Werten {a_i}. Dann ist P(A) oder kurz P(a) die Wahrscheinlichkeitsfunktion für das Auftreten eines a_i ∈ A!

Es sei x eine Zufallsvariable mit kontinuierlichen Werten [v₀,v₁]. Dann ist p(x) die Wahrscheinlichkeitsverteilung der Werte x ∈ [v₀,v₁].

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Wahrscheinlichkeiten und Bayes Regel

Dann ist p(x=x_i) die Wahrscheinlichkeit des Auftretens des Wertes x_i von x.

• Besondere Rolle nehmen binäre Ereignisse ein (also A={0,1}). Etwas tritt ein oder ist wahr oder nicht.

Wenn A und B diskrete Zufallsvariablen sind, dann kann man über eine Produktregel die gemeinsame (vereinte) Wahrscheinlichkeit für das Auftreten von A und B bestimmen:

$${P}{\left({A},{B}\right)}={P}{\left({A}{\mid}{B}\right)}{P}{\left({B}\right)}$$

Die gemeinsame Wahrscheinlichkeit ist ein statistisches Maß, das die Wahrscheinlichkeit berechnet, dass zwei Ereignisse zusammen und gleichzeitig auftreten. Gemeinsame Wahrscheinlichkeit ist die Wahrscheinlichkeit, dass Ereignis B gleichzeitig mit Ereignis A Auftritt.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Wahrscheinlichkeiten und Bayes Regel

• P(A) ist die Wahrscheinlichkeit eines Ereignisses A

• P(A|B) ist die bedingte Wahrscheinlichkeit von A mit dem bedingten Ereignis B (d.h. B muss eintreten damit auch A eintritt): B → A

• P(B|A) ist dann das "inverse Problem": A → B

Bayes Regel (Umkehr der Schlussfolgerung)

• Interessant wäre es zu wissen wenn P(A|B) bekannt wie es mit P(B|A) aussieht:

$$P(B|A) = \frac{P(A|B)P(B)}{P(A)}$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Binäre Klassifikation

Binäre Klassifikation

Hat man ein Experiment n-mal wieder holt (n Fälle oder Dateninstanzen in der Datentabelle), gibt es vier verschiedene Zähler bei einer binären Klassifiation mit y: Inferenz durch Modell/Vorhersage , y₀: Vorgabe/Wirklicher Wert:

• Ergebnis: {True, False}
• Zähler:
  • True Positiive (TP): Die Anzahl der Fälle, in denen y=y₀=True ist.
  • False Positive (FP): Die Anzhal der Fälle, in denen y₀=False und y=True ist.
  • True Negative (TN): Die Anzahl der Fälle, in denen y=y₀=False ist.
  • False Negative (FN): Die Anzhal der Fälle, in denen y₀=True und y=False ist.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Binäre Klassifikation

Binäre Klassifikation

Statitische Parameter

$$\text{Accuracy}=\frac{{\text{TP}+\text{TN}}}{{\text{TP}+\text{FP}+\text{FN}+\text{TN}}}\\ \text{Precision}=\frac{\text{TP}}{{\text{TP}+\text{FP}}}\\ \text{Recall}=\frac{\text{TP}}{{\text{TP}+\text{FN}}}\\ \text{Specificity}=\frac{\text{TN}}{{\text{TN}+\text{FP}}}\\ {{f}_{{1}}=}\frac{{{2}\cdot\text{Recall}\cdot\text{Precision}}}{{\text{Recall}+\text{Precision}}}$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Ein Beispiel: Der Mythos des Infektionstests

Ein Beispiel: Der Mythos des Infektionstests

• Es gibt einen Test auf eine Virusinfektion
  • Dieser wird im Labor getestet: 100 Proben Klasse negativ (kein Virus, ¬V), 100 Proben Klasse positiv (mit Virus, V)
  • Der Test zeigt T (positiv) an, ansonsten ¬T (negativ)
  • Die Analyse der Testexperimente zeigt: TP=99, FP=2, FN=1, TN=98

Sensitivität

$${P}{\left({T}{\mid}{V}\right)}=\frac{{{T}{P}}}{{{T}{P}+{F}{N}}}=\frac{{99}}{{{99}+{1}}}={0.99}{\left({C}{V}{19}:{0.5},{0.7}-{0.9},\text{Good20}\right)}$$

Spezifizität

$${P}{\left(\neg{T}{\mid}\neg{V}\right)}=\frac{{{T}{N}}}{{{T}{N}+{F}{P}}}=\frac{{98}}{{{98}+{2}}}={0.98}{\left({C}{V}{19}:{0.99},{0.999},\text{Good20}\right)}$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Ein Beispiel: Der Mythos des Infektionstests

Genauigkeit

$${A}{\mathcal{{u}}}{r}{a}{c}{y}=\frac{{{T}{P}+{T}{N}}}{{N}}=\frac{{{99}+{98}}}{{200}}={0.985}$$

Präzision

$${P}{r}{e}{c}{i}{s}{i}{o}{n}=\frac{{{T}{P}}}{{{T}{P}+{F}{P}}}=\frac{{99}}{{{98}+{2}}}={0.99}$$

• Es gibt eine Vorbedingung (Vorwahrsch.) bei einer Testanwendung: Der Wahrscheinlichkeit einer Infektion P(V) wenn eine Stichprobe gemacht wird (also n=1). Diese wird mit P(V)=0.001 angenommen.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Ein Beispiel: Der Mythos des Infektionstests

Anwendung der Bayseschen Regel

$$P(V|T)=\frac{P(T|V)P(V)}{P(T)},\\ P(T)=P(T,V)+P(T,\neg V)=\\ P(T|V)P(V)+(1-P(\neg T|\neg V))(1-P(V))$$

• Bei P(V)=0.001 (zufällige Stichprobe ohne Anlass und Differentialdiagnose) ergibt sich:

$$P(V|T)= \frac{0.99 \times 0.001}{0.99 \times 0.001+(1-\mathbf{0.98})(1-0.001)} = 0.047 \approx P(V)\\ = \frac{0.70 \times 0.001}{0.70 \times 0.001+(1-\mathbf{0.999})(1-0.001)} = 0.41 \\ = \frac{0.50 \times 0.001}{0.50 \times 0.001+(1-\mathbf{0.99})(1-0.001)} = 0.047$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Ein Beispiel: Der Mythos des Infektionstests

$$P(\neg V| \neg T)=\frac{P(\neg T|\neg V)P(\neg V)}{P(\neg T)},\\ P(\neg T)=1-P(T)=\\ P(\neg T|\neg V)P(\neg V)+(1-P(T|V))P(V)$$

• Bei P(V)=0.001 (zufällige Stichprobe ohne Anlass und Differentialdiagnose) ergibt sich:

$$P(\neg V|\neg T)= \frac{0.98 \times 0.999}{0.98 \times 0.999+(1-0.99)0.001} = 0.999$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Naiver Bayes Klassifikator

Naiver Bayes Klassifikator

• Zurück zum Golfspielproblem!

Witten Die Ein- und Ausgabevariablen mit bedingter Verteilung (also Y|X)

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Naiver Bayes Klassifikator

• Wenn es nun eine Messung E=x gibt (Evidenz) mit einer Hypothese vom Ergebnis H=y mit C_y={yes|no}, dann gilt quasi als Training (wir kennen ja den Zusammenhang E ↔ H): P(E|H)

• Es wird angenommen dass alle Variablen gleichwertig sind → unbekannte Modellannahme oder a-priori Wissen!

Nun gibt es ein weiteres unbekanntes Beispiel:

$$P(y=yes)=2/9 \times 3/9 \times 3/9 \times 3/9 \times 9/14 = 0.0053\\ P(y=no)=3/5 \times 1/5 \times 4/5 \times 3/5 \times 5/14 = 0.026$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Naiver Bayes Klassifikator

• Es gilt also nach der Bayes Regel:

$$P(C=yes|E) = \frac{\Pi_i P(E_i|C=yes) \times P(C=yes)}{P(E)}\\ P(C=no|E) = \frac{\Pi_i P(E_i|C=no) \times P(C=no)}{P(E)}$$

• Das ist ein einfacher Klassifikator

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Naiver Bayes Klassifikator

Funktionale Beschreibung

Es gilt:

$$c \in C = {h_{bayes}}(x) = \arg \mathop {\max }\limits_{j = 1,m} P({c_j})\prod\limits_{i = 1,n}^{} {P({x_i}|{c_j})}$$

mit c als eine Klasse aus allen möglichen Klassenwerten C der Zielvariable y und x als eine Dateninstanz.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerke

Bayes Netzwerke

Ein bayesisches Netzwerk ist eine Form eines grafischen Modells zur Darstellung multivariater Wahrscheinlichkeitsverteilungen.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerke

Witten Bayes Netzwerke sind eine Kombination aus Bäumen (gerichteten Graphen) und Wahrscheinlichkeitstabellen (Look-up Tabelle) die dann durch bedingte Wahrscheinlichkeiten das Ergebnis (der Hypothese von y) abschätzen.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerke

Witten Ein anderes Bayes Netzwerk für das gleiche Problem!

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerke

• Für das gleiche Problem können verschiedene Bayes Netzwerke aufgebaut werden, die genau die gleiche Wahrscheinlichkeitsverteilung darstellen.
  • Dies geschieht durch Änderung der Art und Weise, wie die gemeinsame Wahrscheinlichkeitsverteilung faktorisiert wird, um bedingte Unabhängigkeiten auszunutzen.

Barber, BRaML, 2011

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerk: Struktur und Parameter

Bayes Netzwerk: Struktur und Parameter

https://www.uib.no/en/rg/ml/119695/bayesian-networks Bayessche Netzwerke bestehen aus Struktur und Parametern

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerk: Struktur und Parameter

• Die Struktur ist ein gerichteter azyklischer Graph (DAG), der bedingte Unabhängigkeiten und Abhängigkeiten zwischen Random-Variablen ausdrückt, die Knoten zugeordnet sind.

• Die Parameter bestehen aus bedingten Wahrscheinlichkeitsverteilungen, die jedem Knoten zugeordnet sind.

• Ein Bayessches Netzwerk ist daher eine kompakte, flexible und interpretierbare Darstellung einer gemeinsamen Wahrscheinlichkeitsverteilung.

• Es ist auch ein nützliches Werkzeug bei der Wissenserlangung, da gerichtete azyklische Graphen die Darstellung kausaler Beziehungen zwischen Variablen ermöglichen.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Netzwerk: Struktur und Parameter

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Belief Netzwerke

Belief Netzwerke

Ein "Belief" Netzwerk ist eine Verteilung der Form:

$$p(x_1,x_2,..,x_D)=\Pi_{i=1}^D p(x_i|pa(x_i))$$

mit pa(x_i) als die Elternvariable der Variablen x_i.

• Dargestellt als gerichteter Graph, wobei ein Pfeil von einer Elternvariablen auf eine untergeordnete Variable zeigt.

• Ein Belief Netzwerk ist ein gerichteter azyklischer Graph (DAG), wobei der i-te Knoten im Graph dem Faktor p(x_i|pa(x_i)) entspricht.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Entscheidungslerner

Bayes Entscheidungslerner

Bayes Lerner

Es werden zwei Funktionen zum Erlernen der Netzwerke benötigt (Struktur und Berechnung):

1. Eine Funktion um ein gegebenes Netzwerk zu evaluieren
2. Eine Funktion um geeignete Netzwerke aus dem Raum aller möglichen Netzwerke zu finden (Suche)

Barber, BRaML, 2011, pp. 288
Witten, DMPMLTaT, pp. 335

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Entscheidungslerner

Ein einfacher und sehr schneller Lernalgorithmus ist K2

• Er beginnt mit einer bestimmten Reihenfolge der Attribute (d.h. Knoten).

• Dann verarbeitet er jeden Knoten der Reihe nach und wird Kanten von zuvor verarbeiteten Knoten zu dem aktuellen Knoten hinzuzufügen.

• In jedem Schritt wird die Kante hinzugefügt, die die Trefferwahrscheinlichekit (Score) des Netzwerks maximiert. Wenn es keine weitere Verbesserung gibt, wird der nächste Knoten bearbeitet.

• Als zusätzlicher Mechanismus zur Vermeidung von Überanpassungen kann die Anzahl der Eltern für jeden Knoten auf ein vordefiniertes Maximum beschränkt werden.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Entscheidungslerner

• Da nur Kanten von zuvor verarbeiteten Knoten berücksichtigt werden und es eine feste Reihenfolge gibt, kann dieses Verfahren keine Zyklen einführen.

Randomisiertes Sampling

• Das Ergebnis hängt jedoch von der anfänglichen Reihenfolge ab, daher ist es sinnvoll, den Algorithmus mehrmals mit unterschiedlichen zufälligen Ordnungen auszuführen.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Bayes Entscheidungslerner

Klassifikation und Bewertung

• Bei Entscheidungsbäumen gibt es keine Information wie "sicher" eine Klassifikation ist (Vorhersage- oder Vertrauenwahrscheinlichkeit), die aber häufig sehr wicht ist!

• Bei ANN ist der Ausgangswert eines Neurons zwar ein Indikator für die Aktivierungsstärke, ist aber modellbasiert keine Wahrscheinlichkeit der Vorhersage (höchstens grobe Näherung)

• Bei NB Klassifizieren gibt es als Ergebnis immer eine (statistisch) modellbasierte Wahrscheinlichkeit!

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Anwendungen von Naiven Bayes-Algorithmen

Anwendungen von Naiven Bayes-Algorithmen

Echtzeit-Vorhersage

Naive Bayesfunktionen sind ein einfacher und schneller Klassifikator und geben Wahrscheinlichkeiten aus für die Beurteilung. Somit könnte es für Vorhersagen in Echtzeit verwendet werden.

Mehrklassen-Vorhersage

Dieser Algorithmus ist auch für Mehrklassen-Vorhersage Funktionen verwendbar. Hier können die Wahrscheinlichkeiten mehrerer Klassen von Zielvariablen vorhergesagt werden.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Anwendungen von Naiven Bayes-Algorithmen

Textklassifizierung / Spam-Filterung / Stimmungsanalyse

Naive Bayes-Klassifikatoren, die hauptsächlich in der Textklassifizierung verwendet werden (aufgrund eines besseren Ergebnisses bei Problemen mit mehreren Klassen und der Unabhängigkeitsregel), weisen im Vergleich zu anderen Algorithmen eine höhere Erfolgsrate auf. Infolgedessen werden sie häufig in der Spam-Filterung (Identifizierung von spam-e-Mails) und in der Stimmungsanalyse (in der social-media-Analyse) verwendet, um positive und negative Kundenstimmungen zu identifizieren).

Empfehlungssystem

Der Naive Bayes-Klassifikator und die "kollaborative Filterung" erstellen zusammen ein Empfehlungssystem, das maschinelles Lernen und Data Mining Techniken verwendet, um versteckte Informationen zu filtern und vorherzusagen, ob ein Benutzer eine bestimmte Ressource möchte oder nicht.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Zusammenfassung

Zusammenfassung

Trainingsdaten

$${x}∼{p}{\left({x}{\mid}{y}\right)}\\ {y}∼{p}{\left({y}\right)}$$

Vorhersagemodell

$${p}{\left({y}{\mid}{x}\right)}=\frac{{{p}{\left({x}{\mid}{y}\right)}{p}{\left({y}\right)}}}{{{p}{\left({x}\right)}}}$$

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Zusammenfassung

Zusammenfassung

• Bayes Klassifikation erfolgt über die Berechnung bedingter und abhängiger Wahrscheinlichkeitsverteilungen

• Das "Training" liefert P(x|y), die Inferenz benötigt die inverse Abhängigkeit und verwendet P(y|x)

• Ein naiver Bayes Klassifikator nimmt unabhänge Varibalen x_i an → Entspricht nicht immer "physikalischen Modellen und Kausalitäten"!

• Ein Bayes Klassifikator muss Tabellen mit bedingten Verteilungen/Wahrscheinlichkeiten verwenden.

Stefan Bosse - Maschinelles Lernen - Probalistisches Lernen - Zusammenfassung