Naive Bayes fr Regressionsprobleme - ke.tu- Annherungsfunktion Algorithmus Evaluation Quellen Naive Bayes fr Regressionsprobleme Vorhersage numerischer Werte mit dem Naive Bayes

  • View
    215

  • Download
    3

Embed Size (px)

Transcript

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes fr RegressionsproblemeVorhersage numerischer Werte mit dem Naive Bayes

    Algorithmus

    Nils Knappmeier

    Fachgebiet Knowledge EngineeringFachbereich Informatik

    Technische Universitt Darmstadt

    14.12.2005

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Gliederung

    1 EinleitungTraditioneller Naive BayesNaive Bayes und Regression

    2 Annherung durch Interpolation mit Gauss-Kurven

    3 Algorithmus: Naive Bayes fr RegressionErmittlung der Teilfunktionen p(Ai |Z ) und p(Z )Berechnung des Zielwerts

    4 EvaluationAllgemeinesProbleme mit unabhngigen AttributenStandard-Datenstze

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Gliederung

    1 EinleitungTraditioneller Naive BayesNaive Bayes und Regression

    2 Annherung durch Interpolation mit Gauss-Kurven

    3 Algorithmus: Naive Bayes fr RegressionErmittlung der Teilfunktionen p(Ai |Z ) und p(Z )Berechnung des Zielwerts

    4 EvaluationAllgemeinesProbleme mit unabhngigen AttributenStandard-Datenstze

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Traditioneller Naive Bayes

    Der Naive Bayes AlgorithmusRahmenbedingungen

    Gegeben: Diskrete Attribute

    Gesucht: Zuordnung zu einer Kategorie

    Trainingsdaten enthalten mglichst zu jedem Zielwertmehrerer Beispiel

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Traditioneller Naive Bayes

    Der Naive Bayes AlgorithmusLsungsmechanismus

    p(K |A1, A2, . . . , An) = p(A1,A2,...,An|K )p(K )p(A1,A2,...,An)Annahme: Ak sind unabhngig voneinander.

    Daher: Whle k mit maximalem

    P(K |A1, A2, . . . , An) = p(K ) n

    i=1

    p(Ai |k)

    p(K ) und p(Ai |K ) kann anhand der Trainingsdatenberechnet werden.

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes und Regression

    Neue Rahmenbedingungen

    Gegeben: Numerische und nominale Attribute

    Gesucht: Ein numerischer Zielwert

    Numerische Attribute knnen auch kontinuierlich sein

    Zielwert ist ebenfalls kontinuierlich

    Zielwert kommt mglicherweise nicht in den Trainingsdatenvor.

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes und Regression

    Allgemeine Vorgehensweise

    Erstellung einer Annherungsfunktion fr p(Z |A)Berechnung der Funktionwerte fr ein diskretisiertesIntervall

    Berechnung des Zielwertes auf Basis der Funktionswerte

    Zielwert ist Durchschnitt oder Median derAnnherungsfunktion

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes und Regression

    Bayes Formel

    Angepasste Bayes-Formel

    p(Z |A) = p(A|Z ) p(Z )p(A|Z ) p(Z )dZ

    Nach Anwendung der Unabhngigkeitsannahme:

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Zu ermitteln: Annherungen an p(Ai |Z ) und p(Z )

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes und Regression

    Bayes Formel

    Angepasste Bayes-Formel

    p(Z |A) = p(A|Z ) p(Z )p(A|Z ) p(Z )dZ

    Nach Anwendung der Unabhngigkeitsannahme:

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Zu ermitteln: Annherungen an p(Ai |Z ) und p(Z )

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Naive Bayes und Regression

    Bayes Formel

    Angepasste Bayes-Formel

    p(Z |A) = p(A|Z ) p(Z )p(A|Z ) p(Z )dZ

    Nach Anwendung der Unabhngigkeitsannahme:

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Zu ermitteln: Annherungen an p(Ai |Z ) und p(Z )

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Gliederung

    1 EinleitungTraditioneller Naive BayesNaive Bayes und Regression

    2 Annherung durch Interpolation mit Gauss-Kurven

    3 Algorithmus: Naive Bayes fr RegressionErmittlung der Teilfunktionen p(Ai |Z ) und p(Z )Berechnung des Zielwerts

    4 EvaluationAllgemeinesProbleme mit unabhngigen AttributenStandard-Datenstze

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Interpolation durch Gauss-KernfunktionenWie leite ich eine kontinuierliche Wahrscheinlichkeitsfunktion aus Beispielwerten ab?

    b sei nunr der Zielwert Wert und bj der Wert der Beispielwert j .

    1h

    K(

    b bih

    )mit K (x) = (2)

    12 e

    x2

    2

    0

    0.5

    1

    1.5

    2

    -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

    h=0.5Beispielwert

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Interpolation durch Gauss-KernfunktionenWie leite ich eine kontinuierliche Wahrscheinlichkeitsfunktion aus Beispielwerten ab?

    b sei nunr der Zielwert Wert und bj der Wert der Beispielwert j .

    1h

    K(

    b bih

    )mit K (x) = (2)

    12 e

    x2

    2

    0

    0.5

    1

    1.5

    2

    -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

    h=0.5Beispielwert

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Interpolation durch Gauss-Kernfunktionen

    1n h

    ni=1

    K(

    b bih

    )h ist zu klein

    0

    0.5

    1

    1.5

    2

    0 0.5 1 1.5 2 2.5 3 3.5 4

    h=0.05

    h=0.05BeispielwertBeispielwertBeispielwertBeispielwert

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Interpolation durch Gauss-Kernfunktionen

    1n h

    ni=1

    K(

    b bih

    )h ist zu gro

    0

    0.5

    1

    1.5

    2

    0 0.5 1 1.5 2 2.5 3 3.5 4

    h=2

    h=2BeispielwertBeispielwertBeispielwertBeispielwert

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Die richtige Wahl des hLeave-One-Out-Cross-Validation

    Intuitiv: Maximale Wahrscheinlichkeit bei denBeispielwerten

    Problem: h 0Lsung: Maximierung einer Pseudo-Wahrscheinlichkeit,bei der alle Kernel ausser dem ber bi bercksichtigtwerden.

    f i (bi) =1

    (n 1)h

    nj=1;i 6=j

    K(

    bi bjh

    )

  • 0

    0.5

    1

    1.5

    2

    2.5

    3

    0 0.5 1 1.5 2 2.5 3 3.5 4

    Pseudowahrscheinlichkeit f*(x)

    Beispielwerth=0.05

  • 0

    0.5

    1

    1.5

    2

    2.5

    3

    0 0.5 1 1.5 2 2.5 3 3.5 4

    Pseudowahrscheinlichkeit f*(x)

    Beispielwerth=0.05

    h=0.5

  • 0

    0.5

    1

    1.5

    2

    2.5

    3

    0 0.5 1 1.5 2 2.5 3 3.5 4

    Pseudowahrscheinlichkeit f*(x)

    Beispielwerth=0.05

    h=0.5h=2

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Exkurs: Die richtige Wahl des h (2)Leave-One-Out-Cross-Validation

    Maximierung der Wahrscheinlichkeit ber alle i

    hCV = arg maxh

    {1n

    ni=1

    log f (bi)

    }

    Vorgehen: Ausprobieren von Werten fr h ber einemfestgelegten Intervall.

  • 0

    0.5

    1

    1.5

    2

    0 0.5 1 1.5 2 2.5 3 3.5 4

    Optimales h

    WahrscheinlichkeitBeispielwertBeispielwertBeispielwertBeispielwert

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Gliederung

    1 EinleitungTraditioneller Naive BayesNaive Bayes und Regression

    2 Annherung durch Interpolation mit Gauss-Kurven

    3 Algorithmus: Naive Bayes fr RegressionErmittlung der Teilfunktionen p(Ai |Z ) und p(Z )Berechnung des Zielwerts

    4 EvaluationAllgemeinesProbleme mit unabhngigen AttributenStandard-Datenstze

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Teilfunktionen

    p(Ai |Z ) fr numerische Attribute

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Gesucht: p(Ai |Z ) =: p(B|Z ) = p(B,Z )p(Z )p(B = b, Z = z) durch zweidimensionaleGauss-Interpolation

    p(Z ): Gauss Interpolation ber alle z

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Teilfunktionen

    p(Ai |Z ) fr numerische Attribute

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Gesucht: p(Ai |Z ) =: p(B|Z ) = p(B,Z )p(Z )p(B = b, Z = z) durch zweidimensionaleGauss-Interpolation

    p(Z ): Gauss Interpolation ber alle z

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Teilfunktionen

    p(Ai |Z ) fr numerische Attribute

    p(Z |A) =p(Z )

    ni=1 p(Ai |Z )

    p(Z ) n

    i=1 p(Ai |Z )dZ

    Gesucht: p(Ai |Z ) =: p(B|Z ) = p(B,Z )p(Z )p(B = b, Z = z) durch zweidimensionaleGauss-Interpolation

    p(Z ): Gauss Interpolation ber alle z

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Teilfunktionen

    Beispiel: Lebensdauer von AmeisenTrainingsdaten: Z [10, 20] Monate, A1 [2.0, 4.0] mm und A2 {rot,schwarz}

    Z A1 A210.5 2.3 rot15.5 3.3 schwarz11.2 2.6 rot12.1 3.5 schwarz

    ? 3.0 rot

    p(Z=z,A1=3.0)

    line 1line 2

    10 12

    14 16

    18 20 2

    2.5

    3

    3.5

    4

    0

    0.02

    0.04

    0.06

    0.08

    0.1

    Berechnung von p(A1 = 3.0|Z = z) fr alle z {10, 10.1, 10.2, ..., 20}

  • Einleitung Annherungsfunktion Algorithmus Evaluation Quellen

    Teilfunktionen

    Beispiel: Lebensdauer von AmeisenTrainingsdaten: Z [10, 20] Monate, A1 [2.0, 4.0] mm und A2 {rot,schwarz}

    Z A1 A210.5 2.3 rot15.5 3.3 schwarz11.2 2.6 rot12.1 3.5 schwarz

    ? 3.0 rot

    0

    0.5

    1

    1.5

    2

    10 12 14 16 18 20

    p(Z=z)

    WahrscheinlichkeitBeispielwertBeispielwertBeispielwertBeispielwert