10 Bayes Flashcards
Lernen nach Bayes
statistisches Lernverfahren:
- kombinieren vorhandenen Wissens (a priori Wahrscheinlichkeiten) mit beobachteten Daten
- Hypothesen können mit einer Wahrscheinlichkeit angegeben werden
- Jedes Beispiel kann die Glaubwürdigkeit einer bestehenden Hypothese erhöhen oder verringern –> kein Ausschluss bestehender Hypothesen
- Mehrere mögliche Hypothesen können gemeinsam ausgewertet werden, um genauere Ergebnisse zu erzielen
Erfolgreiche Lernverfahren nach Bayes
Voting Gibbs (Optimaler Bayes-Klassifikator)
Niver Bayes-Klassifikator
Bayessche Netze
Lernen nach Bayes: Herausforderungen
praktische Probleme:
- initiales Wissen über viele Wahrscehinlichkeiten / Verteilungen notwendig
- aber: oft schätzung basierend auf Hintergrundwissen, vorhandenen Daten, etc. möglcih
Erheblicher Rechenaufwand:
- linear mit anzahl der möglichen Hypothesen
- aber : in speziellen Fällen deutliche Reduzierung des Rechenaufands möglich
Definition: bedingte Unabhängigkeit
X ist bedingt unabhängig von Y gegeben Z, wenn die Wahrscheinlichkeitsverteilung von X bei gegebenem Wert von Z unabhängig vom Wert von Y ist
P(X|Y,Z) = P(X|Z)
MAP
Maximum a posteriori Hypothese:
Ziel: Finden der Hypothese h aus H mit der größten Wahrscheinlichkeit gegeben die beobachteten Daten D
h_{MAP} = arg max{h} P(h|D)
= arg max P(D|h)P(h) / P(D)
[ P(D) = const. ]
= arg max P(D|h)*P(h)
ML Hypothese
Maximum Likelihood Hypothese
unter der Annahme P(h_i) = P(h_j):
h_{ML} = arg max{h_i} P(D|h_i)
Definition: konsitente Lerner
Ein Lernverfahren ist ein konsistenter Lerner, wenn es eine Hypothese liefert, die keine Fehler auf den Trainingsdaten macht
Optimaler Bayes Klassifikator
V_ob = arg max{v} ∑ P(v_j | h–i) P(h_i | D)
Vorteil: Kein anderes Klassifikationsverfahren (bei gleichem Hypothesenraum und Vorwissen) schneidet im Durchschnitt besser ab!
Nachteil: Sehr kostenintensiv bei großer Hypothesenanzahl
Naiver Bayes-Klassifikator
Gegeben:
- instanz x : konjunktion von Attributen a1 … an
- endliche Menge von klassen V
- Menge klassifizierter Beispiele
Gesucht
Wahrscheinlichste Klasse für eine neue Instanz
v_{MAP} = arg max{v} P(vj | a1 … an)
= arg max P(a1 … an | vj)P(vj)
P(vj) lässt sich leicht aus dem Auftreten der Klasse vj in der Trainingsmenge berechnen (einfach zählen)
P(a1…an | vj) ist schwer zu berechnen: Auszählen aller Kombinationen über Attributwerte –> riesige Trainigsmenge notwendig!
=> vereinfachte Annahme ai bedingt unabhängig:
P(a1 … an | vj) = ∏ P(ai | vj)
Naiver Bayes-Klassifikator:
v_{NB} = arg max{v} P(v_j) ∏ P(a_i | v_j)
Naiver Bayes Klassifikator Zusammenfassung
P(vj) und P(ai | vj) werden basierend auf den Häufigkeiten in den Trainingsdaten geschätzt
Wahrscheinlcihkeiten für Klassifikation ergibt gelernte Hypothese
Neue Instanzen werden klassifiziert unter Anwendung MAP Regel
Wenn annahme (bedingt Unabhängigkeit der Attribute) erfüllt ist, ist v(nb) äquivalent zu einer MAP-Klassifikation
=> keine explizite Suche im Hypothesenraum!
Bayesche Netze
beschreiben bedingte Abhängigkeiten / Unabhängigkeiten bzgl. Untermengen von Variablen
=> erlauben somit die Kombination von a priori Wissen über bedingte (Un-) abhängigkeiten von Variablen mit den beobachteten Trainingsdaten
- gerichteter azyklischer Graph
- jede Zufallsvariable wird durch eine nKnoten im Graph repräsentiert
- Definition: X ist Nachfolger von Y, wenn ein gerichteter Pfad von Y nach X existiert.
- Die Kanten repräsentieren die Zusicherung ,dass eine Variable von ihren Nicht-Nachfolgern bedingt unabhängig ist, gegeben ihre direkten Vorgänger
- für diskrete Zufallsvariablen: lokale Tabelle mit bedingten Wahrscheinlichkeiten für jede Variable gegeben ihre direkten Vorgänger
Beyessch Netze: Lernen
Struktur bekannt, alle Variablen beobachtbar:
* lernen der bedingten aBhängigkeiten wie für naiven bayes klassifikator
Struktur bekannt, nur einige Variablen beobachtbar:
* gradientenanstieg, EM-Methode
Strutkur unbekannt:
* heuristische Verfahren
EM Algorithmus
Expectation Maximization
Problemstellung allgemein:
- daten sind nur partiell beobachtbar
- parameter einer (teil-)hypothese sollen geschätzt werden
Grundidee:
Interativer Ansatz - schätzen der nicht beobachtbaren Werte (E) und Anpassung der Parameter (M)
Einordnung
Typ der Inferenz: induktiv Ebene des Lernens: subsymbolisch Lernvorgang: überwacht Beispielgenerierung: nicht inkrementell Umfang der Beispiele: umfangreich Hintergrundwissen: empirisch
