Warum schneiden naive Bayes-Klassifikatoren so gut ab?

38

Naive Bayes-Klassifikatoren sind eine beliebte Wahl für Klassifizierungsprobleme. Dafür gibt es viele Gründe, darunter:

  • "Zeitgeist" - weit verbreitetes Bewusstsein nach dem Erfolg von Spam-Filtern vor etwa zehn Jahren
  • Einfach zu schreiben
  • Das Klassifikatormodell ist schnell zu erstellen
  • Das Modell kann mit neuen Trainingsdaten geändert werden, ohne dass das Modell neu erstellt werden muss

Sie sind jedoch "naiv", dh sie gehen davon aus, dass die Funktionen unabhängig sind. Dies steht im Gegensatz zu anderen Klassifikatoren wie Maximum Entropy-Klassifikatoren (die nur langsam berechnet werden).

Die Unabhängigkeitsannahme kann normalerweise nicht angenommen werden und ist in vielen (den meisten?) Fällen, einschließlich des Spam-Filter-Beispiels, einfach falsch.

Warum funktioniert der Naive Bayes-Klassifikator in solchen Anwendungen immer noch sehr gut, auch wenn die Funktionen nicht unabhängig voneinander sind?

winwaed
quelle

Antworten:

23

Dieses Papier scheint zu beweisen (ich kann der Mathematik nicht folgen), dass Bayes nicht nur dann gut ist, wenn Features unabhängig voneinander sind, sondern auch, wenn die Abhängigkeiten von Features zwischen Features ähnlich sind:

In diesem Aufsatz schlagen wir eine neuartige Erklärung für die hervorragende Klassifizierungsleistung von naiven Bayes vor. Wir zeigen im Wesentlichen die Abhängigkeitsverteilung; Das heißt, es spielt eine entscheidende Rolle, wie sich die lokale Abhängigkeit eines Knotens in jeder Klasse gleichmäßig oder ungleichmäßig verteilt und wie die lokalen Abhängigkeiten aller Knoten konsistent (Unterstützung einer bestimmten Klassifizierung) oder inkonsistent (Aufhebung der gegenseitigen Abhängigkeit) zusammenarbeiten. Unabhängig davon, wie stark die Abhängigkeiten zwischen Attributen sind, können naive Bayes immer noch optimal sein, wenn sich die Abhängigkeiten gleichmäßig in Klassen verteilen oder wenn sich die Abhängigkeiten gegenseitig aufheben

jb.
quelle
1
Qualitativ macht das Sinn. Abhängige Features führen zu einer Gewichtung. Eine gleichmäßige Verteilung oder eine Verteilung, die abgebrochen wird, hebt diese Gewichtung auf. Allerdings werden "einseitige" Abhängigkeiten wahrscheinlich immer noch schlecht abschneiden? Ich denke für das Spam-Beispiel sollten wir eine Menge Abhängigkeiten für + Spam-Funktionen erwarten, aber nicht unbedingt -spam-Funktionen im allgemeinen Fall. Es kann jedoch vorkommen, dass eine Person viele legitime E-Mails zu einem bestimmten Thema erhält. In diesem Fall gibt es viele abhängige Funktionen, die die + Spam-Funktionen ausgleichen.
winwaed
3
Ich empfehle auch dieses Papier: cs.stanford.edu/people/ang/papers/…
Dov
25

Die meisten Probleme mit maschinellem Lernen sind einfach!

Siehe zum Beispiel auf John Langfords Blog . Was er wirklich sagt, ist, dass ML Probleme leicht macht, und dies ist ein Problem für Forscher, da sie versuchen sollten, Methoden auf eine breite Palette einfacher Probleme anzuwenden oder schwierigere Probleme anzugreifen. Das Nebenprodukt ist jedoch, dass die Daten bei vielen Problemen linear (oder zumindest nahezu) trennbar sind. In diesem Fall funktioniert jeder lineare Klassifikator gut! Es ist einfach so, dass die Autoren des ursprünglichen Spam-Filterpapiers Naive Bayes gewählt haben, aber wenn sie Perceptron, SVM, Fisher Discriminant Analysis, Logistic Regression, AdaBoost oder so ziemlich alles andere verwendet hätten, hätte es wahrscheinlich auch funktioniert.

Die Tatsache, dass es relativ einfach ist, den Algorithmus zu codieren, hilft. Um beispielsweise die SVM zu codieren, benötigen Sie entweder einen QP-Solver , oder Sie müssen den SMO-Algorithmus codieren, was keine triviale Aufgabe ist. Sie könnten natürlich libsvm herunterladen, aber in den Anfängen war diese Option nicht verfügbar. Es gibt jedoch viele andere einfache Algorithmen (einschließlich des oben erwähnten Perceptron), die genauso einfach zu codieren sind (und inkrementelle Aktualisierungen ermöglichen, wie in der Frage erwähnt).

Für schwierige nichtlineare Probleme werden natürlich Methoden benötigt, die sich mit Nichtlinearitäten befassen können. Aber auch dies kann eine relativ einfache Aufgabe sein, wenn Kernel-Methoden verwendet werden. Die Frage lautet dann oft "Wie entwerfe ich eine effektive Kernelfunktion für meine Daten?" Und nicht "Welchen Klassifikator soll ich verwenden?".

tdc
quelle
Ich denke, "easy" ist vielleicht relativ, aber ja, die Spam-Klassifizierung ist "einfacher" als ich denke, die meisten Leute haben das vor ungefähr 12 Jahren angenommen. Kernel - Methoden könnten ein Ansatz zur Erstellung eines schnellen und einfachen Klassifikators sein, aber "Wie entwerfe ich eine effektive Kernelfunktion für meine Daten?" seine Wechselbeziehungen)?
winwaed
1
Ja, es ist relativ und es gibt auch viele Probleme, also gibt es immer noch viele schwierige! Und ich denke, die Grenze zwischen ML und menschlichem Lernen ist immer verschwommen. Wenn Sie ein überaus ausgefallenes probabilistisches Modell erstellen, tun Sie dasselbe. Die gute alte NFLT sagt uns, dass eine Methode nicht alle Probleme lösen kann, so kompliziert diese Methode auch sein mag. Wir werden immer Menschen brauchen, um Modelle / Kernel / Algorithmen oder was auch immer zu entwerfen, um mehr aus Ihren Daten herauszuholen.
tdc
wahr - definitiv eine verschwommene Linie!
winwaed
1
Warum die Gegenstimme? Möchtest du einen Kommentar abgeben?
TTC
7

Nachdem ich Naive Bayesian Classifiers ausgiebig in Segmentierungsklassifizierungswerkzeugen verwendet habe, stimmen meine Erfahrungen mit veröffentlichten Veröffentlichungen überein, die zeigen, dass NBC in Bezug auf Genauigkeit mit linearer Diskriminante und CART / CHAID vergleichbar ist, wenn alle Prädiktorvariablen verfügbar sind.

(Aufgrund der Genauigkeit sind sowohl die "Trefferquote" bei der Vorhersage der wahrscheinlichsten richtigen Lösung als auch die Kalibrierung, dh eine Schätzung der Mitgliederzahl von beispielsweise 75%, in 70% -80% der Fälle richtig.)

Meine zwei Cent ist, dass NBC so gut funktioniert, weil:

  • Die Interkorrelation zwischen Prädiktorvariablen ist nicht so stark, wie man meinen könnte (gegenseitige Informationsbewertungen von 0,05 bis 0,15 sind typisch).
  • NBC kann mit diskreten polytomen Variablen gut umgehen, ohne dass wir sie grob dichotomisieren oder ordinale Variablen als Kardinal behandeln müssen.
  • NBC verwendet alle Variablen gleichzeitig, während CART / CHAID nur wenige verwendet

Und dann werden alle Variablen beobachtet. Was NBC wirklich davon abhält, ist, dass es sich elegant verschlechtert, wenn eine oder mehrere Prädiktorvariablen fehlen oder nicht beobachtet werden. In diesem Fall bleiben CART / CHAID und die lineare Diskriminanzanalyse unverändert.

Prototyp
quelle