En effet, à l’heure actuelle où le phénomène de Big Data envahit le monde professionnel et notre société, les algorithmes sont devenus un outil puissant qui semble être capable de tout faire, et règner sur nous comme laisse croire cet article les algorithmes vont-ils gouverner notre vie, ou est-ce peut-être déjà le cas ?.
En entrant des mots clés comme “algorithme machine learning”, “apprentissage automatique” dans un moteur de recherche, on peut trouver de nombreuses méthodes. Par exemple, je suis tombé sur cet article qui parle de l’apprentissage automatique. On peut trouver plusieurs algorithmes :
La classification naïve bayésienne (naive bayes en anglais) était un algorithme que je ne connaissais pas. Après quelques recherches, j’ai trouvé de nombreux articles assez facilement qui m’ont permis de comprendre le principe, puis j’ai trouvé également une fonction R toute faite, qui permet d’appliquer cet algorithme. Afin de vérifier que j’ai bien compris, j’ai reproduit moi-même le résultat de l’algorithme sous R.
J’ai tiré quelques conclusions intéressantes :
Ainsi, je me suis dit qu’il vallait le coup de partager cet expérience, en écrivant comment j’ai fait.
Pour comprendre le principe de l’algorithme, j’ai entré plusieurs mots clés comme “naive bayes explanation”, “naive bayes intuition”. En effet, il faut admettre que les ressources en anglais plus beaucoup plus riches qu’en français; aussi au lieu de chercher des articles scientifiques, avec plein de formules mathématiques, je préfère d’abord avoir des explications en français (ou plôtut en anglais). En général, les autres se sont déjà posés les mêmes questions, et il n’est difficile de tomber sur de bons résultats facilement. Avec le temps, je commence aussi à avoir deux sites en tête stackoverflow et quora sur lesquels j’y vais parfois directement. Justement l’article suivant a simple explanation of naive bayes classification est sur le site de stackoverflow.
En survolant la page en 30 secondes, il est intéressant de remarquer:
En tout cas, vu le nombre de votes, je me suis dit, cela vaut le coup de lire. Et en effet l’explication est assez intuitive et le théorème de Bayes est le principe appliqué.
Une autre question que je me suis posé, c’est sur le mot “naïve”, j’ai commencé alors à réfléchir ce qui est naïf dans le principe de cet algorithme, quelqu’un s’est douté posé la même question, en effet, j’ai trouvé assez rapidement pourquoi la classificaiton naïve bayésienne est-elle naïve ?. La réponse qui a le plus de votes dit que c’est en raison de la distribution normale de X|Y qui suppose une corrélation nulle entre les composantes de X. Si on essaie de creuser, l’hythèse de l’indépendance porte sans doute sur les différentes variables pour le calcul du produit des vraisemblances. Mais pourquoi la loi normale ? Enfin bon, faisons semblant de comprendre, si j’essayais d’appliquer l’algorithme sur un exemple, je comprendrai sans doute plus.
Pour avoir un exemple concret, je sais que de nombreux packages R existent, de ce fait, j’ai cherché avec des mots clés comme “r naive bayes example”, et j’ai trouvé la fonction naiveBayes du packge e1071 :
library("e1071")
library(knitr)
## Categorical data only:
data(HouseVotes84, package = "mlbench")
model <- naiveBayes(Class ~ ., data = HouseVotes84)
predict(model, HouseVotes84[1:10,])
predict(model, HouseVotes84[1:10,], type = "raw")
pred <- predict(model, HouseVotes84)
table(pred, HouseVotes84$Class)
## using laplace smoothing:
model <- naiveBayes(Class ~ ., data = HouseVotes84, laplace = 3)
pred <- predict(model, HouseVotes84[,-1])
table(pred, HouseVotes84$Class)
## Example of using a contingency table:
data(Titanic)
m <- naiveBayes(Survived ~ ., data = Titanic)
m
predict(m, as.data.frame(Titanic))
## Example with metric predictors:
data(iris)
m <- naiveBayes(Species ~ ., data = iris)
## alternatively:
m <- naiveBayes(iris[,-5], iris[,5])Le code est très facile à exécuter, en une dizine de secondes, j’ai appliqué donc cet algorithme sur plusieurs exemples. D’après les tables de confusion, cet algorithme fonctionne plutôt bien sur ces bases de données. (En réalité, comme l’algorithme est appliqué sur la même base, on ne peut pas conclure a priori, on a un grand risque de surapprentissage.)
La prochaine fois en entretien, je pourrais dire que je connais la classification bayésienne et en plus, je sais l’appliquer. Exécuter le code en appuyant sur ctrl+Entrée, tout le monde sait le faire. Pour vraiment comprendre l’algorithme, je me suis dit que je pourrais retrouver le résultat en faisant moi-même le code.
J’ai pris le premier exemple du code R. D’abord, j’ai regardé un échantillon des données pour savoir de quoi il s’agit:
library("e1071")
library(knitr)data(HouseVotes84, package = "mlbench")
data=HouseVotes84
kable(head(data))| Class | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | V11 | V12 | V13 | V14 | V15 | V16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| republican | n | y | n | y | y | y | n | n | n | y | NA | y | y | y | n | y |
| republican | n | y | n | y | y | y | n | n | n | n | n | y | y | y | n | NA |
| democrat | NA | y | y | NA | y | y | n | n | n | n | y | n | y | y | n | n |
| democrat | n | y | y | n | NA | y | n | n | n | n | y | n | y | n | n | y |
| democrat | y | y | y | n | y | y | n | n | n | n | y | NA | y | y | y | y |
| democrat | n | y | y | n | y | y | n | n | n | n | n | n | y | y | y | y |
dim(data)## [1] 435 17D’après le titre et l’aperçu de la base, il s’agit du résultat de vote en fonction de plusieurs caractéristiques anonymisés (pour en savoir plus sur la base, une rapide recherche m’a donné ce lien). Aussi, la base contient 16 variables explicatives et 435 observations.
Pour avoir les probabilités a priori, j’ai regardé la répartition des votes entre “republican” et “democrat”.
table(data$Class)##
## democrat republican
## 267 168Pour avoir les pourcentages, on peut utiliser une autre fonction prop.table. Même si c’est aussi simple de faire l’opération soi-même :
prop.table(table(data$Class))##
## democrat republican
## 0.6137931 0.3862069Pour étudier la première variable V1, il faut construire la table de contingence suivante :
t=prop.table(table(data$Class,data[,2]))
t##
## n y
## democrat 0.24113475 0.36879433
## republican 0.31678487 0.07328605Ainsi, sans plus de connaissances sur une personne on pourrait prédire son vote selon le pourcentage global. Ici on approxime le pourcentage global par rapport à la base à disposition, cela suppose que l’échantillon est représentatif.
A partir de ce tableau, on est prêt à calculer les probabilités a posteriori. Si une observation prend la valeur “n”, on peut calculer successivement :
# probabilités conditionnelles pour le calcul de la vraisemblance
t[,"n"]/rowSums(t)## democrat republican
## 0.3953488 0.8121212# constante ce normalisation
sum(t[,"n"])## [1] 0.5579196# probabilités a posteriori
t[,"n"]/rowSums(t)/sum(t[,"n"])*prop.table(table(data$Class))##
## democrat republican
## 0.4349415 0.5621720En réalité, comme je ne comprends pas bien la théorie sur la statistique bayésienne, et que la simplification saute aux yeux, j’ai bien envie de faire calculer la probabilité a posteriori directement en applicant la formule de calcul de probabilité conditionnelle :
t[,"n"]/sum(t[,"n"])## democrat republican
## 0.4322034 0.5677966Mais le calcul devient plus intéressant quand il s’agit de plusieurs variables.
Il suffit maintenant de calculer le produit des probabilités pour toutes les variables. Je vais construire l’algorithme en l’appliquant directement sur une observation.
La valeur prise par une obervation de chacune des variable permet de calculer les probabilités a posteriori. Il suffit de construire une boucle pour le calcul du produit. J’ai suivi la formule donnée dans la réponse de Stackoverflow :
o=as.vector(unlist(data[1,]))
p=prop.table(table(data$Class))
for (i in 2:17){
if (is.na(o[i])==FALSE){
t=prop.table(table(data$Class,data[,i]))
p=p*t[,o[i]]/rowSums(t)/sum(t[,o[i]])
}
}
p##
## democrat republican
## 3.966888e-05 3.854309e+02Sans trop creuser, je me suis dit que j’avais peut-être commencé à entrevoir l’intérêt du théorème de Bayes dans le cas où on a plusieurs variables : l’opération d’effectuer le produit des vraisemblances semble en effet plus simples que si on cherchait à calculer les probabilités a posteriori directement.
Quand je lis le résultat, la somme des deux probabilités n’est pa égale à 1: j’ai donc fait une erreur.
J’ai trouvé l’erreur, j’ai essayé de faire un print de chaque élément du produit de la boucle. Mais je ne voyais pas d’erreurs. Puis j’ai comparé le résultat aux prédictions de l’algorithme du package R :
model <- naiveBayes(Class ~ ., data = HouseVotes84)
predr=predict(model, HouseVotes84[1:10,])
pred=predict(model, HouseVotes84[1:10,], type = "raw")
head(pred)## democrat republican
## [1,] 1.029209e-07 0.999999897
## [2,] 5.820415e-08 0.999999942
## [3,] 5.684937e-03 0.994315063
## [4,] 9.985798e-01 0.001420152
## [5,] 9.666720e-01 0.033328022
## [6,] 8.121430e-01 0.187857022pred[1,]/p##
## democrat republican
## 0.002594499 0.002594499Les probabilités sont proportionnelles. Cela nous permet de conclure. On peut sortir les réponses de prédiction pour les 10 premières observations :
reponse=rep(1,10)
for (k in 1:10){
o=as.vector(unlist(data[k,]))
p=prop.table(table(data$Class))
for (i in 2:17){
if (is.na(o[i])==FALSE){
t=prop.table(table(data$Class,data[,i]))
p=p*t[,o[i]]/rowSums(t)/sum(t[,o[i]])
}
}
reponse[k]=(which.max(p))
}
reponse## [1] 2 2 2 1 1 1 2 2 2 1as.numeric(predr)## [1] 2 2 2 1 1 1 2 2 2 1J’ai donc réussi à reproduire les mêmes prédictions que l’algorithmes du package. Cependant, le fait qu’il y a une erreur de proportionnalité sur les probabilités ne hante…
Pourtant j’ai suivi exactement la formule donnée.
Pour retrouver la bonne constante, ou une éventuelle erreur, j’ai commencé à réfléchir sur les formules utilisées, j’ai entré des mots clés comme “naive bayes with multi conditions”, “naive bayes multiple variables”, “naive bayes multi evidence”, etc. et je suis tombé sur cet article : Combining evidence using Bayes’ Rule. La démonstration y est assez claire.
La solution est donc tout simplement de normaliser à la fin, selon la formule indiquée :
\[P(D|\cap_{i=1}^n{V_i})=\frac{P(D) \cdot \prod_{i=1}^n{P(V_i|D)}}{P(D) \cdot \prod_{i=1}^n{P(V_i|D)}+P(R) \cdot \prod_{i=1}^n{P(V_i|D)}}\]
o=as.vector(unlist(data[1,]))
p=prop.table(table(data$Class))
for (i in 2:17){
if (is.na(o[i])==FALSE){
t=prop.table(table(data$Class,data[,i]))
p=p*t[,o[i]]/rowSums(t)/sum(t[,o[i]])
}
}
p/(sum(p))##
## democrat republican
## 1.029209e-07 9.999999e-01Il s’avère ainsi qu’il y a une petite coquille dans la réponse de Stackoverflow. Il est vrai que cela ne change pas le résultat de prédiction, néanmoins, il y une erreur de principe dans la formule. Je voulais commenter la réponse, car il est important de participer, à la fois important pour les autres car on partages nos expériences et remarques, et à la fois pour soi-même, car c’est un excellent moyen d’apprendre. Cependant, mais comme il faut un certain nombres de points de réputation pour pouvoir commenter, je n’ai pas pu le faire avec un nouveau compte. Je ferai quand j’aurai assez de points.
Par ailleurs, l’auteur a cité le livre sur lequel les calculs sont basés, et il semble que ce soit un excellent livre : Artificial Intelligence: A Modern Approach de Russell et Norvig, qu’on pourrait lire.
Puis, je me suis dit que je pourrais appliquer le même algorithme sur un autre example de base, iris, par exemple. Mais bien sûr, je ne peux plus faire de tables de contingence, comme les variables sont continues. Si j’avais été plus attentif, j’aurais dû voir les commentaires dans le code R : “categorical data only” pour la base des votes, et “exemple with metric predictors” pour la base iris.
Ainsi, j’ai commencé à réfléchir je me suis dit que des articles existent certainement pour expliquer comment l’algorithme marche pour les données numériques. Ainsi, j’ai entré les mots clés : “naive bayes numerical data”. J’ai trouvé l’article suivant : deux façons d’utiliser NB pour les données numériques. La première solution est plutôt une astuce : transformer les données numériques en données catégoriques; la deuxième propose de calibrer une densité de probablité, et la loi gaussienne a été citée.
Dans un premier temps, je calcule les moyennes les écarts types de toutes les variables par classe d’iris. Pour ce faire, j’ai cherché une fonction qui permet de calculer les moyennes par facteur.
Il y a certainement d’autres manières sans doute plus simples de le faire, mais c’était la première idée qui me venait à l’esprit :
data=iris
head(iris)## Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
## 6 5.4 3.9 1.7 0.4 setosameanl=list()
sdl=list()
for (i in 1:4){
meanl[[i]]=with(iris, tapply(data[,i], Species, mean))
sdl[[i]]=with(iris, tapply(data[,i], Species, sd))
}
meanl## [[1]]
## setosa versicolor virginica
## 5.006 5.936 6.588
##
## [[2]]
## setosa versicolor virginica
## 3.428 2.770 2.974
##
## [[3]]
## setosa versicolor virginica
## 1.462 4.260 5.552
##
## [[4]]
## setosa versicolor virginica
## 0.246 1.326 2.026La struction de calcul est légèrement différent que celle pour la base des votes, en effet, j’ai procédé à une boucle sur le nombre d’espèces comme il est rapide de calculer les vraisemblances pour toutes les observations :
# calcul des probabilités
pm=matrix(1,nrow(data),3)
for (k in 1:3){
p=rep(1,nrow(data))
for (i in 1:4){
p=p*dnorm(data[,i],meanl[[i]][k],sdl[[i]][k])
}
pm[,k]=p
}
# calcul des prédictions pour toutes les observations
apply(pm,1,which.max)## [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [36] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [71] 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3
## [106] 3 2 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
## [141] 3 3 3 3 3 3 3 3 3 3# modèle
m <- naiveBayes(Species ~ ., data = iris)
# comparaison des deux prédictions
sum(as.numeric(predict(m, iris))==apply(pm,1,which.max))## [1] 150C’est également sur cet exemple que je me suis dit que j’ai commencé à comprendre l’intérêt du théorème de Bayes: il est sans doute plus facile de passer par la loi de probabilité d’une caractéristique sachant l’espèce (qui est la vraisemblance) que de calculer directement la probabilité d’avoir une telle espèce en connaissant la valeur d’une caractéristique.
Par ailleurs, il semble aussi qu’on pourrait améliorer l’algorithme de NB pour les pistes suivantes :
Chercher : Les ressources sont abondantes sur internet, pour trouver les bons articles, il s’agit d’abord d’entrer de bons mots clés sur les algorithmes, il faut avoir des mots clés. Au début, on commence toujours par des mots clés simples, en entrant par exemple tout simplement le nom de l’algorithme. Ensuite, quand on commence à comprendre la base, on se posera également d’autres questions un peu plus précises, pour “naive bayes”, on peut citer :
Puis, les autres mots clés connexes font apparition également :
Comprendre : Avant d’utiliser l’algorithme, il faut comprendre le principe. En effet, il est presque plus facile de trouver des codes R qui donnent des exemples d’application que des articles qui l’expliquent.
Si on ne comprends pas exactement ce qui est fait, il est difficile de
comprendre les forces et faiblesses de l’algorithme
Appliquer : Pour bien retenir le fonctionnement, il faut aussi l’appliquer sur un exemple simple. En réalité, je me suis souvenu que j’avais déjà lu article pour l’explication de NB (NB en termes simples), il est important de combiner l’explication en français (ou en anglais) et les calculs simples.
Expliquer : Si je n’avais pas décidé de l’écrire et m’appliquer dans l’explication. Je n’aurais pas vu certaines subtilités, comme l’erreur dans la constante de normalisation des probabilités a posteriori. Le fait d’écrire un code R clair nécessite aussi des entraînements, plus on écrit, plus on acquiert certains automatismes.
J’ai montré également une première version à certains amis et collègues, en effet, tout seul, il faut qu’on se pose de bonnes questions, les autres aident à repérer d’autres points moins clairs.
Pour aller plus loin, plusieurs problématiques importantes n’étaient pas soulevées :