Kombinieren Sie Klassifikatoren, indem Sie eine Münze werfen

15

Ich lerne einen maschinellen Lernkurs und die Vorlesungsfolien enthalten Informationen, die dem empfohlenen Buch widersprechen.

Das Problem ist folgendes: Es gibt drei Klassifikatoren:

  • Klassifikator A, der eine bessere Leistung im unteren Bereich der Schwellenwerte bietet,
  • Klassifikator B, der eine bessere Leistung im höheren Bereich der Schwellenwerte bietet,
  • Klassifikator C was wir bekommen, wenn wir eine p-Münze werfen und aus den beiden Klassifikatoren auswählen.

Wie wird sich der Klassifikator C auf einer ROC-Kurve verhalten?

In den Vorlesungsfolien heißt es, dass wir durch einfaches Umwerfen dieser Münze die magische " konvexe Hülle " der ROC-Kurve der Klassifikatoren A und B erhalten.

Ich verstehe diesen Punkt nicht. Wie können wir Informationen erhalten, indem wir einfach eine Münze werfen?

Die Vorlesungsfolie

Vorlesungsfolien

Was das Buch sagt

In dem empfohlenen Buch ( Data Mining ... von Ian H. Witten, Eibe Frank und Mark A. Hall ) heißt es dagegen:

Um dies zu sehen, wählen Sie eine bestimmte Wahrscheinlichkeitsgrenze für Methode A, die wahre und falsche positive Raten von tA bzw. fA ergibt, und eine andere Grenze für Methode B, die tB und fB ergibt. Wenn Sie diese beiden Schemata zufällig mit den Wahrscheinlichkeiten p und q verwenden, wobei p + q = 1 ist, erhalten Sie wahre und falsch positive Raten von p. tA + q. tB und p. fA + q. fB. Dies stellt einen Punkt dar, der auf der geraden Linie liegt, die die Punkte (tA, fA) und (tB, fB) verbindet. Indem Sie p und q variieren, können Sie die gesamte Linie zwischen diesen beiden Punkten nachzeichnen.

Um Informationen zu erhalten und den konvexen Rumpf zu erreichen, müssen wir meines Erachtens etwas Fortgeschritteneres tun, als nur eine P-Münze zu werfen.

AFAIK, der richtige Weg (wie im Buch vorgeschlagen) ist der folgende:

  1. wir sollten eine optimale Schwelle Oa für den Klassifikator A finden
  2. wir sollten eine optimale Schwelle Ob für den Klassifikator B finden
  3. definiere C wie folgt:

    • Wenn t <Oa, verwenden Sie den Klassifikator A mit t
    • Wenn t> Ob, verwenden Sie den Klassifikator B mit t
    • Wenn Oa <t <Ob, wählen Sie zwischen Klassifikator A mit Oa und B mit Ob anhand der Wahrscheinlichkeit als Linearkombination, in der wir uns zwischen Oa und Ob befinden.

Ist das richtig? Wenn ja, gibt es ein paar wesentliche Unterschiede zu den Vorschlägen der Folien.

  1. Es ist kein einfaches Münzwerfen, sondern ein fortschrittlicherer Algorithmus, der manuell definierte Punkte und Picks basierend auf der Region benötigt, in die wir fallen.
  2. Es werden niemals die Klassifizierer A und B mit Schwellenwerten zwischen Oa und Ob verwendet.

Können Sie das Problem mir erklären , und was ist der richtige Weg , es zu verstehen , wenn mein Verständnis nicht richtig war?

Was würde passieren, wenn wir einfach eine P-Münze werfen würden, wie es die Folien suggerieren würden? Ich würde denken, dass wir eine ROC-Kurve erhalten würden, die zwischen A und B liegt, aber niemals "besser" als die bessere an einem bestimmten Punkt.

Soweit ich sehen kann, verstehe ich wirklich nicht, wie die Folien richtig sein könnten. Die Wahrscheinlichkeitsrechnung auf der linken Seite macht für mich keinen Sinn.

Update: Den Artikel des ursprünglichen Autors gefunden, der die Methode der konvexen Hülle erfunden hat: http://www.bmva.org/bmvc/1998/pdf/p082.pdf

Hyperknot
quelle
Nach meiner Lektüre sowohl der von Ihnen geposteten Folie als auch des Buchauszugs scheinen sie genau dasselbe zu beschreiben, und die Folien sind nicht fehlerhaft.
Kardinal
Beachten Sie, dass es auch nicht allzu schwierig ist, eine Simulation zu erstellen, um sich von der auf der Folie angegebenen Tatsache zu überzeugen. Die einzige Schwierigkeit, die Sie möglicherweise haben, besteht darin, zwei ROC-Kurven zu konstruieren, die ungefähr so ​​aussehen. Sie können jedoch beispielsweise mithilfe eines Gaußschen Mischungsmodells die Beobachtungen und einige suboptimale Entscheidungsregeln erstellen.
Kardinal

Antworten:

12

(Bearbeitet)

Die Vorlesungsfolien sind richtig.

Methode A hat einen "optimalen Punkt", der wahre und falsch positive Raten von (TPA, FPA in der Grafik) ergibt. Dieser Punkt würde einer Schwelle entsprechen, oder allgemeiner [*] einer optimalen Entscheidungsgrenze für A. Gleiches gilt für B. (Aber die Schwellen und die Grenzen hängen nicht zusammen).

Es hat sich gezeigt, dass Klassifikator A unter der Präferenz "Minimieren von False Positives" (konservative Strategie) und Klassifikator B eine gute Leistung erbringt, wenn wir "True Positives" (eifrige Strategie) maximieren möchten.

Die Antwort auf Ihre erste Frage lautet im Grunde ja, mit der Ausnahme, dass die Wahrscheinlichkeit der Münze (in gewissem Sinne) willkürlich ist. Das letzte Clasiffier wäre:

xxp

(Korrigiert: Eigentlich sind die Vorlesungen völlig richtig, wir können auf jeden Fall nur die Münze werfen. Siehe Diagramme)

p

[*] Du solltest hier allgemein sein: Wenn du in Bezug auf eine einzige skalare Schwelle denkst, macht all dies wenig Sinn; Ein eindimensionales Feature mit einem schwellenwertbasierten Klassifikator bietet nicht genügend Freiheitsgrade, um verschiedene Klassifikatoren wie A und B zu haben, die sich entlang verschiedener Kurven verhalten, wenn die freien Parameter (Entscheidungsgrenze = Schwelle) variieren. Mit anderen Worten: A und B heißen "Methoden" oder "Systeme", nicht "Klassifikatoren"; weil A eine ganze Familie von Klassifikatoren ist, parametrisiert durch einen Parameter (Skalar), der eine Entscheidungsgrenze bestimmt, nicht nur einen Skalar]

Ich habe einige Diagramme hinzugefügt, um es klarer zu machen:

Bildbeschreibung hier eingeben

ttttEIN=2ttB=4

In diesem Szenario kann man dann sagen, dass die gefüllte orange Linie der "optimale A-Klassifikator" (innerhalb seiner Familie) ist, und dasselbe für B. Man kann jedoch nicht sagen, ob die orange Linie besser ist als die blaue Linie: Man führt aus Besser, wenn wir den falschen Positiven hohe Kosten zuweisen, die anderen, wenn falsche Negative viel teurer sind.

Bildbeschreibung hier eingeben

Es kann nun vorkommen, dass diese beiden Klassifikatoren für unsere Anforderungen zu extrem sind. Wir möchten, dass beide Fehlertypen ähnliche Gewichte haben. Wir würden es vorziehen, anstatt den Klassifikator A (orangefarbener Punkt) oder B (blauer Punkt) zu verwenden, um eine Leistung zu erzielen, die zwischen ihnen liegt. Wie der Kurs sagt, kann man dieses Ergebnis erreichen, indem man einfach eine Münze wirft und zufällig einen der Klassifikatoren auswählt.

Wie können wir Informationen erhalten, indem wir einfach eine Münze werfen?

Wir erhalten keine Informationen. Unser neuer randomisierter Klassifikator ist nicht einfach "besser" als A oder B, seine Leistung ist eine Art Durchschnitt von A und B, in Bezug auf die Kosten, die jeder Art von Fehler zugeordnet sind. Das kann für uns von Vorteil sein oder auch nicht, je nachdem, was unsere Kosten sind.

AFAIK, der richtige Weg (wie im Buch vorgeschlagen) ist der folgende ... Ist das richtig?

p , wähle einen Klassifikator (das optimale A oder das optimale B) und klassifiziere mit diesem Klassifikator.

Leonbloy
quelle
@leonboy Ich glaube, dass x die Schwelle ist und für niedrige Werte von x Klassifikator A am besten funktioniert. Für hohe Werte von x funktioniert Klassifikator B am besten. Mit best meine ich, dass für die angegebene falsch positive Rate die richtig positive Rate die höchste ist. Wenn wir nur wissen, dass A bis zu einem einzigen Punkt, an dem sie sich kreuzen, und B für alle darüber liegenden Schwellen am besten funktioniert, dann kann kein Algorithmus, der A in dem Bereich zwischen FPa und FPb, in dem A die höhere TP hat, eine Gewichtung von weniger als 1 gibt, keine Leistung erbringen so wie A. Also muss ein solcher Algorithmus C in diesem Bereich unter A fallen.
Michael R. Chernick
In ähnlicher Weise ist in dem Bereich zwischen FPa und FPb, in dem TP für B höher ist, kein Algorithmus mit p größer als 0 besser als B. Die Formel für TPc ist korrekt, aber ein fester gewichteter Durchschnitt zwischen TPb und TPa kann nicht größer als der größere von TPa sein und TPb. Es muss zwischen sie fallen. Das Diagramm zeigt jedoch immer TPc über TPa und TPb in der gesamten Region von FPa und FPb. Sehen Sie hier etwas, das uns fehlt? Ich finde es nicht in deiner Antwort.
Michael R. Chernick
1
Okay, die Glühbirne ging aus! X ist in Ihrem Kopf eher ein Vektor als eine skalare Schwelle. Ändert das wirklich etwas? Die FP-Äxte sind eine skalare Wahrscheinlichkeit. Mein Kreuzungspunkt ist der FP-Gleichheitspunkt für A und B. Es könnte viele Vektoren X geben, die dorthin führen. Ich sage das nur an jedem Punkt entlang der FP-Achse zwischen FPa und FPb. TPc = p TPa + (1-p) TPb. Die Linie im Plot liegt in der Ebene TP vs FP. Wie konnte diese Linie durch die Punkte über den Kurven für A und B gehen, als das OP befragt wurde (ich denke richtig)?
Michael R. Chernick
1
@Michael: Ich denke A und B sind unterschiedliche Methoden, die unterschiedliche Grenzentscheidungen treffen. Jeder hat einen einstellbaren Parameter (was in 1D ein Schwellenwert ist), die Parameter sind unabhängig und geben (für jeden) eine Familie von Klassifikatoren an. Ich werde versuchen, ein Diagramm zu zeichnen, um es zu verdeutlichen.
Leonbloy
1
Ich habe Leonbloy eine positive Bewertung für diese hübsche Beschreibung gegeben. Aber ich mag die abschließende Bemerkung von Kardinal, weil mir dieses Argument klar ist und mit meiner jüngsten Überlegung übereinstimmt. @leobloy Das einzige, was in Ihrem Diagramm fehlt, ist eine grafische Darstellung der Punkte für die zufällige Regel, die beide einzelnen Regeln übertrifft. Ich denke, Sie können die neue Regel als eine beschreiben, die die beiden Fehler unterschiedlich gewichtet, aber es ist nicht notwendig, und ich denke weniger verwirrend, wenn Sie dieses Argument weglassen.
Michael R. Chernick
2

Ich stimme Ihrer Argumentation zu. Wenn Sie den Klassifikator durch Münzwurf verwenden, um einen zu wählen, wenn Sie sich zwischen den Punkten A und B befinden, liegt Ihr Punkt auf der Kurve immer unter dem besseren Klassifikator und über dem ärmeren und möglicherweise nicht über beiden! Mit dem Diagramm muss etwas nicht in Ordnung sein. An dem Punkt, an dem sich die 2 ROC-Kurven kreuzen, hat der Zufallsauswahlalgorithmus die gleiche Leistung wie die beiden Algorithmen. Es wird nicht so darüber sein, wie es im Diagramm dargestellt ist.

Michael R. Chernick
quelle
1
Ich glaube die Folie ist richtig. Wenn Sie zwei verschiedene Entscheidungsverfahren mit zwei verschiedenen Schwellenwerten verwenden und dann eine zufällige Entscheidung treffen, erhalten Sie eine konvexe Kombination, die einen Punkt ergibt, der zwischen den beiden liegt. Dieser Punkt kann mit der gleichen falsch positiven Rate über beiden ( ! ) Kurven liegen. Dies liegt daran, dass der für jede Prozedur verwendete Schwellenwert zu diesem Zeitpunkt unterschiedlich ist.
Kardinal
1
Das A und B in der konvexen Kombination unterscheidet sich also von dem A und B, die einzeln mit dieser falsch positiven Rate ausgewählt werden. Ich denke nur, dass das Diagramm verwirrend war, da ich nicht sah, dass A und B aus einer Familie von Klassifikatoren ausgewählt wurden.
Michael R. Chernick
1
EINB
Ich glaube, dass diese Antwort die richtige ist, zusammen mit dem Kommentar des Kardinals! Das Verlassen des Kreuzungsbereichs kann passieren, ist aber keine Methode. Ich habe das Originalpapier von dem Typ gefunden, der diese Methode erfunden hat, und es erklärt es sehr gut! bmva.org/bmvc/1998/pdf/p082.pdf
hyperknot
@zsero: Ich glaube, sogar Michael wird zugeben, dass diese Antwort auf dem Verständnis des Diagramms zum Zeitpunkt der Veröffentlichung der Antwort beruhte und dass sich seine Interpretation geändert hat, seit die Kommentare und andere Antworten erschienen. Wie in der Abbildung dargestellt, kann man durch Randomisierung jeden Punkt auf jeder Linie zwischen einem Punkt auf der ersten Kurve und einem Punkt auf der zweiten Kurve erzielen, selbst wenn die resultierende wahre positive Rate die beiden anderen Kurven für eine gegebene falsche positive Rate dominiert.
Kardinal