Le classification naïf de Bayes repose, comme l’analyse discrimnante linéaire, sur un modèle génératif et la règle de décision optimale
f(\boldsymbol{x}) = \arg\max_{y\in\mathcal{Y}} P(Y=y | \boldsymbol{X}=\boldsymbol{x})
qui peut se réécrire grâce à la règle de Bayes comme
f(\boldsymbol{x}) = \arg\max_{y\in\mathcal{Y}} \frac{ p(\boldsymbol{x} | y) P(Y=y)}{p(\boldsymbol{x})} = \arg\max_{y} p(\boldsymbol{x} | y) P(Y=y)
où le dénominateur est constant par rapport à y et peut être ignorer pour la classification.
11.1 Hypothèses sur le modèle génératif
Le classifieur naïf de Bayes ne présume pas d’un modèle génératif particulier : il peut s’appliquer à différents modèles. En revanche, une hypothèse forte est ajoutée : l’indépendance conditionnelle des composantesx_k de \boldsymbol{x}=[x_1, \dots, x_d]^T \in\mathbb{R}^d, c’est-à-dire
p(\boldsymbol{x} | Y =y) = \prod_{k=1}^d p(x_k | Y=y)
Par exemple, pour un modèle gaussien
p(\boldsymbol{x}\ |\ Y = y) = \frac{1}{(2\pi)^{d/2} |\textcolor{blue}{\boldsymbol{C}_y}|^{1/2}} \exp\left(-\frac{1}{2} ( \boldsymbol{x} - \textcolor{blue}{\boldsymbol{\mu}_y})^T \textcolor{blue}{\boldsymbol{C}_y}^{-1}( \boldsymbol{x} - \textcolor{blue}{\boldsymbol{\mu}_y})\right),
les paramètres à estimer sont au nombre de d (pour la moyenne \boldsymbol{\mu}_y) + d^2 (pour \boldsymbol{C}_y) pour chaque catégorie. Mais sous l’hypothèse d’indépendance conditionnelle, cela se ramène à l’estimation de d gaussiennes unidimensionnelles
p(x_k\ |\ Y = y) = \frac{1}{\textcolor{blue}{\sigma_{y,k}}\sqrt{2\pi}} \exp\left(-\frac{( x - \textcolor{blue}{\mu_{y,k}})^2}{2\textcolor{blue}{\sigma_{y,k}^2}}\right)
et donc à d estimations indépendantes de 2 paramètres.
11.2 Application à des données binaires
Pour \boldsymbol{X}\in\{0,1\}^d, sous l’hypothèse d’indépendance des composantes, nous pouvons écrire \begin{align*}
P(\boldsymbol{X}=\boldsymbol{x} | Y =y) &= \prod_{k=1}^d P(X_k = x_k | Y=y) \\
&= \prod_{k=1}^d (b^{y}_k)^{x_k} (1-b^{y}_k)^{1-x_k}
\end{align*} car chaque composante X_k peut être modélisée par une loi de Bernouilli :
P(X_k = 1 | Y=y) = b^y_k ,\quad P(X_k=0 | Y=y) = 1-b^y_k
\Rightarrow P(X_k=x_k | Y=y ) =(b^{y}_k)^{x_k} (1-b^{y}_k)^{1-x_k}
Les paramètres b^y_k correspondant à de simples probabilités d’occurrence de x_k=1, ils peuvent être simplement estimés par les pourcentages d’exemples pour lesquel x_k=1 :
b^y_k = \frac{\#exemples\ de\ la\ cat.\ y\ avec\ x_k=1}{m_y}
Cependant, pour éviter b^y_k = 0 ou b^y_k = 1 qui risquerait de compromettre le calcul du produit P(\boldsymbol{X}=\boldsymbol{x} | Y =y), il est nécessaire de régulariser, avec pour \epsilon >0 (typiquement \epsilon=1) :
b^y_k = \frac{(\#exemples\ de\ la\ cat.\ y\ avec\ x_k=1) + \epsilon}{m_y + 2\epsilon}
Exemple d’application : filtre anti-spam
Le classifieur naïf de Bayes est très souvent utilisé dans la filtres anti-spam pour classer les mails en deux catégories : SPAM ou HAM (mail légitime). Dans ce contexte, il est courant de représenter un mail par un sac de mots : un vecteur \boldsymbol{x} binaire de la taille d d’un dictionnaire prédéfini où chaque composante x_k indique la présence du kème mot du dictionnaire.
Dans ce cas, les paramètres b^{SPAM}_k et b^{HAM}_k correspondent aux probabilité de voir le kème mot du dictionnaire dans un SPAM ou un HAM. Les probabilités P(Y=SPAM) et P(Y=HAM) sont estimées par
P(Y=SPAM) = \frac{\#spams}{m}\qquad P(Y=HAM) = 1-P(Y=SPAM)
et correspondent à la probabilité qu’un mail quelconque soit un SPAM ou HAM.
Dans ce type d’applications, la dimension d correspond à la taille du dicitonnaire et peut être très grande et le produit P(\boldsymbol{X}=\boldsymbol{x} | Y =y) = \prod_{k=1}^d (b^{y}_k)^{x_k} (1-b^{y}_k)^{1-x_k} de d nombres entre 0 et 1 peut être trop proche de zéro pour permettre de calculer une classification correcte sur une machine à précision limitée. Il est donc courant de passer par les log car
f(\boldsymbol{x}) = \arg\max_{y\in\mathcal{Y}} P(\boldsymbol{X}=\boldsymbol{x} | Y=y ) P(Y=y) = \arg\max_{y\in\mathcal{Y}} \log P(\boldsymbol{X}=\boldsymbol{x} | Y=y ) + \log P(Y=y)
et
\log P(\boldsymbol{X}=\boldsymbol{x} | Y=y ) = \sum_{k=1}^d \log (b^{y}_k)^{x_k} (1-b^{y}_k)^{1-x_k}
= \sum_{x_k=1} \log b^{y}_k + \sum_{x_k=0} \log (1-b^{y}_k)
est une somme qui aura tendance à rester dans des plages de valeurs beaucoup plus raisonnables.
from math import log# imaginons que tous les termes du produit valent b =0.9print("valeur de P(X=x|Y=y) pour d=1 000, 5 000 et 10 000 : ")print(b**1000)print(b**5000)print(b**10000)print("valeur de log P(X=x|Y=y) pour d=1 000, 5 000 et 10 000 : ")print(1000* log(b))print(5000* log(b))print(10000* log(b))
valeur de P(X=x|Y=y) pour d=1 000, 5 000 et 10 000 :
1.7478712517226947e-46
1.631350185342827e-229
0.0
valeur de log P(X=x|Y=y) pour d=1 000, 5 000 et 10 000 :
-105.36051565782628
-526.8025782891314
-1053.6051565782627
Pour d=10000, sans passer par les log, la classification sera donc donnée par le résultat de la comparaison de 0 avec 0, ce qui n’est pas raisonnable, alors que la comparaison des log restera correcte.