Pourquoi les classificateurs bayésiens naïfs fonctionnent-ils si bien?

38

Les classificateurs Naive Bayes sont un choix populaire pour les problèmes de classification. Il y a plusieurs raisons à cela, notamment:

  • "Zeitgeist" - une notoriété généralisée après le succès des filtres anti-spam il y a une dizaine d'années
  • Facile à écrire
  • Le modèle de classificateur est rapide à construire
  • Le modèle peut être modifié avec de nouvelles données d'apprentissage sans avoir à reconstruire le modèle

Cependant, ils sont «naïfs» - c'est-à-dire qu'ils supposent que les fonctionnalités sont indépendantes - cela contraste avec d'autres classificateurs tels que les classificateurs Maximum Entropy (dont le calcul est lent).

L'hypothèse d'indépendance ne peut généralement pas être supposée, et dans de nombreux cas (la plupart?), Y compris l'exemple du filtre anti-spam, elle est tout simplement fausse.

Alors, pourquoi le classificateur Naive Bayes fonctionne-t-il toujours très bien dans de telles applications, même lorsque les fonctionnalités ne sont pas indépendantes les unes des autres?

Winwaed
la source

Réponses:

23

Cet article semble prouver (je ne peux pas suivre les calculs) que bayes est bon non seulement lorsque les fonctionnalités sont indépendantes, mais également lorsque les dépendances de fonctionnalités sont similaires entre elles:

Dans cet article, nous proposons une nouvelle explication sur la superbe performance de classification de Bayes naïf. Nous montrons que, essentiellement, la distribution de dépendance; C'est-à-dire que la manière dont la dépendance locale d'un nœud se répartit dans chaque classe, de manière égale ou inégale, et la manière dont les dépendances locales de tous les nœuds fonctionnent ensemble, de manière cohérente (supportant une certaine classi fi cation) ou de manière incohérente (en s'annulant) jouent un rôle crucial. Par conséquent, quelle que soit la force des dépendances entre attributs, Bayes naïf peut toujours être optimal si les dépendances sont réparties de manière égale dans les classes ou si les dépendances s’annulent.

jb.
la source
1
Qualitativement, cela a du sens. Les caractéristiques dépendantes vont entraîner une pondération - donc une distribution égale ou une distribution qui annule annulera cette pondération. Cependant, les dépendances "asymétriques" vont probablement mal fonctionner encore? Je suppose que pour le spam, par exemple, nous devrions nous attendre à beaucoup de dépendances pour les + fonctionnalités de spam, mais pas nécessairement pour les fonctionnalités de spam dans le cas général. Cependant, une personne peut recevoir de nombreux courriels légitimes sur un sujet spécifique. Dans ce cas, il y aurait beaucoup de fonctionnalités dépendantes - qui équilibreraient les fonctionnalités + spam.
winwaed
3
Je recommande aussi ce papier: cs.stanford.edu/people/ang/papers/…
Dov
25

La plupart des problèmes d'apprentissage automatique sont faciles!

Voir par exemple sur le blog de John Langford . Ce qu'il dit en réalité, c'est que ML facilite les problèmes, ce qui pose un problème aux chercheurs, qui doivent essayer d'appliquer des méthodes à un large éventail de problèmes simples ou s'attaquer à des problèmes plus difficiles. Cependant, le sous-produit est que, pour de nombreux problèmes, les données sont séparables linéairement (ou du moins presque), auquel cas tout classificateur linéaire fonctionnera bien! Il se trouve que les auteurs du document de filtrage antispam original ont choisi Naive Bayes, mais s’ils avaient utilisé Perceptron, SVM, l’analyse discriminante de Fisher, la régression logistique, AdaBoost, ou presque, ils auraient probablement aussi bien fonctionné.

Le fait qu'il soit relativement facile de coder l'algorithme aide. Par exemple, pour coder le SVM, vous devez disposer d'un solveur QP ou coder l' algorithme SMO qui n'est pas une tâche triviale. Vous pouvez bien sûr télécharger libsvm mais cette option n’était pas disponible dans les premiers temps. Cependant, il existe de nombreux autres algorithmes simples (y compris le Perceptron mentionné ci-dessus) qui sont tout aussi faciles à coder (et permettent des mises à jour incrémentielles comme le mentionne la question).

Pour les problèmes non linéaires difficiles, des méthodes pouvant traiter les non-linéarités sont bien sûr nécessaires. Mais même cela peut être une tâche relativement simple lorsque des méthodes de noyau sont utilisées. La question devient alors "Comment concevoir une fonction de noyau efficace pour mes données" plutôt que "Quel classificateur dois-je utiliser".

tdc
la source
Je pense que "facile" est peut-être relatif, mais oui, la classification du spam est "plus facile" que la plupart des gens ne le supposaient il y a 12 ans. Les méthodes de noyau peuvent être une approche pour produire un classificateur simple et rapide, mais "Comment concevoir une fonction de noyau efficace pour mes données" semble qu'une partie de l'apprentissage automatique devient un "apprentissage humain" (c'est-à-dire une meilleure compréhension des données et ses inter-relations)?
winwaed
1
Oui, c'est relatif, et il y a aussi beaucoup de problèmes, donc il y a encore beaucoup de problèmes difficiles! Et je pense que la frontière entre l'apprentissage du vivant et l'humain est toujours floue ... si vous créez un modèle probabiliste extravagant, vous faites la même chose. Le bon vieux NFLT nous dit qu'une méthode ne peut résoudre tous les problèmes, aussi complexe soit-elle. Nous aurons donc toujours besoin d'humains pour concevoir des modèles / noyaux / algorithmes ou tout ce qui est nécessaire pour tirer le meilleur parti de vos données.
TDC
vrai - certainement une ligne floue!
winwaed
1
Pourquoi le vote négatif? Envie de commenter?
TDC
7

Ayant utilisé abondamment les classificateurs naïfs bayésiens dans les outils de classification par segmentation, mon expérience est cohérente avec les documents publiés montrant que NBC est d'une précision comparable à celle du discriminant linéaire et de CART / CHAID lorsque toutes les variables prédictives sont disponibles.

(Par précision, le "taux de réussite" permettant de prédire la solution correcte comme solution la plus probable, ainsi que l'étalonnage, ce qui signifie qu'une estimation de 75% des membres est exacte dans 70% à 80% des cas.)

Mes deux cents est que NBC fonctionne si bien parce que:

  • L'inter-corrélation entre les variables prédictives n'est pas aussi forte qu'on pourrait le penser (des scores d'information mutuelle de 0,05 à 0,15 sont typiques)
  • NBC sait bien gérer les variables polytomiques discrètes, sans devoir les dichotomiser grossièrement ni traiter les variables ordinales comme des valeurs cardinales.
  • NBC utilise toutes les variables simultanément, tandis que CART / CHAID en utilise quelques-unes.

Et c'est à ce moment que toutes les variables sont observées. NBC se démarque vraiment du lot, c’est qu’elle se dégrade gracieusement quand une ou plusieurs variables prédites manquent ou ne sont pas observées. L'analyse CART / CHAID et le discriminant linéaire s'arrêtent dans ce cas.

prototype
la source