Présentation du problème de reconnaissance de caractères manuscrits (MNIST DataBase à partir d’images numérisées. L’objectif est de comparer les performances (qualité de prévision, temps d'exécution) en fonction de latechnologie, ici R, et en fonction de la taille de l'échantillon. R n'est pas spécialement véloce comparativmeents aux autres technologies testées, notamment à cause des difficultés à paralléliser.
L'objectif général est la construction d'un meilleur modèle de reconnaissance de chiffres manuscrits. Ce problème est ancien (zipcodes) et sert souvent de base pour la comparaison de méthodes et d'algorithmes d'apprentissage. Le site de Yann Le Cun: MNIST DataBase, est à la source des données étudiées, il décrit précisément le problème et les modes d'acquisition. Il tenait à jour la liste des publications proposant des solutions avec la qualité de prévision obtenue. Ce problème a également été proposé comme sujet d'un concours Kaggle mais sur un sous-ensemble des données.
De façon très schématique, plusieurs stratégies sont développées dans une vaste littérature sur ces données.
L'objectif de cet atelier est de comparer sur des données relativement volumineuses les performances de différents environnements technologiques et librairies. Une dernière question est abordée, elle concerne l'influence de la taille de l'échantillon d'apprentissage sur le temps d'exécution ainsi que sur la qualité des prévisions.
Analyse des données en R, noter les temps d'exécution, la précision estimée sur l'échantillon test.
Les données peuvent être préalablement téléchargées ou directement lues. Ce sont celles originales du site MNIST DataBase mais préalablement converties au format .csv, certes plus volumineux mais plus facile à lire. Attention le fichier mnist_train.zip présent dans le dépôt est compressé.
In [ ]:
# Après avoir téléchargé les données
# Fichier train.csv
# Lecture des données
path="http://www.math.univ-toulouse.fr/~besse/Wikistat/data/"
# path=""
Dtrain=read.csv(paste(path,"mnist_train.csv",sep=""),header=F)
dim(Dtrain)
In [ ]:
# Variable Label
Ltrain=as.factor(Dtrain[,785])
Dtrain=Dtrain[,-785]
In [ ]:
# Même chose avec les données de test
Dtest=read.csv(paste(path,"mnist_test.csv",sep=""),header=F)
Ltest=as.factor(Dtest[,785])
Dtest=Dtest[,-785]
dim(Dtest)
Les données ont déjà été normalisées centrées et sont complètes. Elles ne nécessitent pas d'autre "nettoyage" au moins rudimentaire.
Le tutoriel d'introduction à Scikit-learn montre comment représenter les images des caractères ainsi qu'une ACP qui n'est pas reprise ici.
On s'intéresse, à titre indicatif, aux performances de l'implémentation de k-means en R sur un tel volume même son utilisation n'est pas très utile.
In [ ]:
t1=Sys.time()
# Problème de convergence selon l'algorithme utilisé
clas.dig=kmeans(Dtrain,10, algorithm="Forgy",iter.max=50)
t2=Sys.time()
# temps d'exécution
difftime(t2,t1)
In [ ]:
classe=clas.dig$cluster
# Homogénéité des classes
table(Ltrain, classe)
Tester ensuite différents modèles de discrimination. Bien entendu, il s'agirait d'optimiser les paramètres des modèles mais en prévoyant de restreindre la taille de l'échantillon d'apprentissage lorque les temps de calcul sont importants...
Les exécutions sont proposés sur un sous échantillon de l'échantillon d'apprentissage initial. Estimer le temps d'exécution sur tout l'échantillon ou l'obtenir ... de nuit!
La complexité de l'algorithme $k$-nn est en $O(nkd)$ où $d$ est la dimension, $k$, le nombre de voisins et $n$ la taille de l'échantillon d'apprentissage.
In [ ]:
# Sous échantillonnage
set.seed(11)
SousEch=sample(1:nrow(Dtrain),nrow(Dtrain)/5)
EchDtrain=Dtrain[SousEch,]
EchLtrain=Ltrain[SousEch]
dim(EchDtrain)
In [ ]:
library(class)
t1=Sys.time()
prev.knn=knn(EchDtrain,Dtest,EchLtrain,k=10)
t2=Sys.time()
difftime(t2,t1)
In [ ]:
# matrice de confusion
conf=table(prev.knn,Ltest)
conf
In [ ]:
#taux d'erreur
(sum(conf)-sum(diag(conf)))/sum(conf)
L'algorithme random forest de la librairie randomForest est implémenté en fortran puis interfacé avec R. Il se montre plus efficace que celle de $k$-nn mais nettement plus long que l'implémentation de la librairie ranger par Wright et Ziegler (2015).
In [ ]:
## Random Forest avec sous-échantillon
library(randomForest)
t1=Sys.time()
rf.fit=randomForest(x=EchDtrain,y=EchLtrain,xtest=Dtest,ytest=Ltest,ntree=100)
# mtry par défaut (sqrt(p))
t2=Sys.time()
difftime(t2,t1)
In [ ]:
rf.fit$test$err.rate[100,1]
Même calcul avec l'échantillon complet mais en utilisant l'implémentation de "ranger". Seul souci, la parallélisation (multithreading) n'est pas possible sous Windows alors qu'elle est automatique avec un autre système. Le temps d'apprentissage pourrait être encore sensiblement amélioré.
In [ ]:
library(ranger)
t1=Sys.time()
DataF=data.frame("Ltrain"=Ltrain,Dtrain)
rf.fit=ranger(Ltrain~.,data=DataF,num.trees=100,write.forest=TRUE)
# mtry par défaut (sqrt(p))
t2=Sys.time()
difftime(t2,t1)
In [ ]:
predY=predict(rf.fit,dat=Dtest)
predY$class
conf=table(predY$predictions,Ltest)
erreur=(sum(as.vector(conf))-sum(diag(conf)))/nrow(Dtest)
print(erreur)
La procédure d'estimation du modèle puis de prévision de l'échantillon test est itérée en fonction de la taille croissante de l'échantillon d'apprentissage.
In [ ]:
ntree=250
errMat=matrix(rep(0,36),nrow=12,ncol=3 )
dimnames(errMat)[[2]]=c("Taille","Temps","Erreur")
for (i in 1:12) {
SousEch=sample(1:60000,5000*i)
EchDtrain=Dtrain[SousEch,]
EchLtrain=Ltrain[SousEch]
n=dim(EchDtrain)
t1=Sys.time()
DataF=data.frame("Ltrain"=EchLtrain,EchDtrain)
rf.fit=ranger(Ltrain~.,data=DataF,num.trees=ntree,write.forest=TRUE)
t2=Sys.time()
errMat[i,1]=5000*i
errMat[i,2]=difftime(t2,t1)
predY=predict(rf.fit,dat=Dtest)
conf=table(predY$predictions,Ltest)
errMat[i,3]=(sum(as.vector(conf))-sum(diag(conf)))/nrow(Dtest)
}
print(errMat)
Résultats
| Taille | Temps | Erreur |
|---|---|---|
| 5000 | 0.14 | 0.0545 |
| 10000 | 0.30 | 0.0454 |
| 15000 | 0.48 | 0.0419 |
| 20000 | 1.12 | 0.0384 |
| 25000 | 1.51 | 0.0359 |
| 30000 | 1.85 | 0.0334 |
| 35000 | 2.15 | 0.0341 |
| 40000 | 2.56 | 0.0320 |
| 45000 | 3.00 | 0.0320 |
| 50000 | 3.33 | 0.0298 |
| 55000 | 3.60 | 0.0287 |
| 60000 | 4.01 | 0.0283 |