Introduction au Machine learning

et à la classification supervisée

Agathe Guilloux
Outline I
Big data / Data Science
Big Data? Statistique? AI? ML? DS?

Eco-système de la Data Science

Exemples de cas d’usage

Un focus sur le Machine Learning/Apprentissage statistique
Apprentissage supervisé
Régression
Classification

Apprentissage non-supervisé
Réduction de la dimension / visualisation
Clustering

Retour sur les cas d’usage

Le problème de classification
Exemples
Classification
OutlineApproche
II probabiliste / statistique
Idée générale

Naive Bayes

Analyse discriminante
Analyse discriminante

Linear Discriminant Analysis (LDA)

Classifieur constants sur une partition

k plus proches voisins / k nearest neighbors

Arbres de décisions

Minimisation de l’erreur, méthodes basées sur l’optimisation

Erreur visible / erreur de généralisation

Ensemble methods

Text mining: comment transformer un texte en un vecteur numérique ?

Hashing
Bag of Words
Mots et Word Vectors
Organisation du cours

▶ Programme
▶ Jour 1 : big data / data science + notebook “ds_with_python”
▶ Jour 2 et 3 : algorithmes de classification + “classification_gro”
▶ Jour 4 : text mining + “notebook_imdb”
▶ Evaluation
▶ par équipe de 3, analyser le jeu de données “amazon reviews”
[Link]
▶ soutenances de 15 minutes avec une présentation le 26/09.
Big data / Data Science
Vocabulaire et buzz words

▶ Statistique
▶ Intelligence artificielle (AI)
▶ Machine Learning (ML)
▶ Big Data
▶ Data Science
▶ Deep Learning (DL)
▶ ... ?? ...
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable
de connaissances à partir de données, mais le mot clé est science !
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable
de connaissances à partir de données, mais le mot clé est science !
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable
de connaissances à partir de données, mais le mot clé est science !
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable
de connaissances à partir de données, mais le mot clé est science !
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable
de connaissances à partir de données, mais le mot clé est science !
Wikipedia

▶ Le Big data est un terme désignant des ensembles de données si importants et

complexes qu’il devient difficile de les analyser en utilisant des applications de
traitement de données traditionnelles.
▶ La Statistique est l’étude de la collecte, de l’analyse, de l’interprétation, de la
présentation et de l’organisation des données.
▶ L’Intelligence artificielle est définie comme l’étude d’agents intelligents: tout
appareil qui perçoit son environnement et prend des mesures qui maximisent ses
chances de réussir.
▶ Le Machine learning ou apprentissage statistique est un champ d’étude de
l’intelligence artificielle qui se fonde sur des approches statistiques pour donner
aux ordinateurs la capacité d’ « apprendre » à partir de données.
▶ La Data science/ Science des données est l’étude de l’extraction généralisable de
connaissances à partir de données, mais le mot clé est science !
Data Science

Les influences majeures

Quatre influences majeures agissent aujourd’hui:
▶ La théorie formelle de la statistique
▶ L’accélération du développement des ordinateurs
▶ Le défi, dans de nombreux domaines, de corpus de données toujours plus
grands
▶ L’accent mis sur la quantification dans une variété toujours plus large de
   disciplines
Data Science

Les influences majeures - Tukey (1962)

Quatre influences majeures agissent aujourd’hui:
▶ La théorie formelle de la statistique
▶ L’accélération du développement des ordinateurs
▶ Le défi, dans de nombreux domaines, de corpus de données toujours plus
grands
▶ L’accent mis sur la quantification dans une variété toujours plus large de
   disciplines

▶ Il parlait de l’analyse de données.

▶ Datamining, Machine learning , Big Data, AI ...
Faire de la science des données
Exemples de cas d’usage
Big Data/DS : où et pourquoi ?
Cas d’usage en marketing

▶ Prédiction du churn
▶ Marketing personnalisés et segmentation des clients
▶ ”Sentiment analysis” des clients
▶ Recommandation
Churn/attrition
Segmentation des clients
Sentiment analysis
Recommandation
Machine Learning/Apprentissage statistique
Une définition du Machine Learning

par Tom Mitchell ([Link]

Un programme informatique est réputé apprendre (learn) d’une expérience E
pour certaines classes de tâches T et une mesure de performance P, si ses
performances aux tâches T, mesurée par P, s’améliorent avec l’expérience.
Un robot qui apprend

Un robot doté d’un ensemble de capteurs et d’un algorithme

d’apprentissage en ligne
▶ Tâche: jouer au football
▶ Performance: score
▶ Expérience:
▶ environnement actuel
▶ jeux passés
Reconnaissance d’objets dans une image

Un algorithme de détection/reconnaissance
▶ Tâche : dire si un objet est présent ou non dans l’image
▶ Performance : nombre d’erreurs
▶ Expérience : ensemble d’images ’”labelisées” précédemment vues
Machine Learning

Tom Mitchell ([Link]

Un programme informatique est réputé apprendre (learn) d’une expérience E
pour certaines classes de tâches T et une mesure de performance P, si ses
performances aux tâches T, mesurée par P, s’améliorent avec l’expérience.
Supervisé et non-supervisé

Apprentissage supervisé
▶ Objectif : apprendre une fonction f prédisant une variable Y à partir de
features X.
▶ Données : ensemble d’apprentissage (Xi , Yi )

Apprentissage non-supervisé
▶ Objectif: découvrir une structure au sein d’un ensemble d’individus (Xi ).
▶ Data: Learning set (Xi )
Machine Learning

Méthodes pour le ML
▶ Grand catalogue de méthodes,
▶ Besoin de définir la performance,
▶ Design des features...
Apprentissage supervisé
Apprentissage supervisé
Régression I
Régression II
Classification
Régression logistique: une exemple simple
Régression logistique: une exemple plus compliqué I
Régression logistique: une exemple plus compliqué II
Régression logistique: une exemple plus compliqué III
Apprentissage non-supervisé
Réduction de la dimension / visualisation I

Figure 1: MNIST data

Réduction de la dimension / visualisation II

Figure 2: T-SNE
Clustering

Figure 3: Hierarchical clustering et K-means

Retour sur les cas d’usage
Churn/attrition

Figure 4: Classification : le client reste ou part

Segmentation des clients

Figure 5: Clustering
Sentiment analysis

Figure 6: Classification : le commentaire est positif ou non // Régression : note

Recommandation

Figure 7: Réduction de la dimension

Déclaration de Montréal pour une IA responsable

Dix principes :

▶ le bien-être,
▶ le respect de l’autonomie,
▶ la protection de l’intimité et de la vie privée,
▶ la solidarité, la participation démocratique,
▶ l’équité,
▶ l’inclusion de la diversité,
▶ la prudence,
▶ la responsabilité et
▶ le développement soutenable.

[Link]
Le problème de classification
Exemples
Spam detection

▶ Données : emails
▶ Input : email
▶ Output : Spam or No Spam
Classification binaire : toy datasets

▶ But : retrouver la classe

▶ Input : 2 predicteurs
▶ Output : classe
Classification multi-classes

Figure 8: Jeu de données MNIST

▶ Lire un code postal sur une enveloppe.

▶ But : assigner un chiffre à une image.
▶ Input : image.
▶ Output : chiffre correspondant.
Classification multi-classes : Iris dataset

▶ But : retrouver la classe

▶ Input : 2 predicteurs
▶ Output : classe
Classification
Le problème de classification binaire

On a des données d’apprentissage (learning data) pour des individus

i = 1, . . . , n. Pour chaque individu i :

▶ on a un vecteur de covariables (features) Xi ∈ X ⊂ Rd

▶ la valeur de son label Yi ∈ {−1, 1}.
▶ on suppose que les couples (Xi , Yi ) sont des copies i.i.d. de (X, Y) de loi
inconnue.

But

▶ On veut pour un nouveau vecteur X+ de features prédire la valeur du label

Y+ par Ŷ+ ∈ {−1, 1}
▶ Pour cela, on utilise les données d’apprentissage
Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} pour construire un classifieur ĉ de telle
sorte que
Ŷ+ = ĉ(X+ ).
Classification binaire : toy datasets
Le problème de classification multi-classes

On a des données d’apprentissage (learning data) pour des individus

i = 1, . . . , n. Pour chaque individu i :

▶ on a un vecteur de covariables (features) Xi ∈ Rd

▶ la valeur de son label Yi ∈ C = {1, . . . , K}.
▶ on suppose que les couples (Xi , Yi ) sont des copies i.i.d. de (X, Y) de loi
inconnue.

But

▶ On veut pour un nouveau vecteur X+ de features prédire la valeur du label

Y+ par Ŷ+ ∈ C = {1, . . . , K}
▶ Pour cela, on utilise les données d’apprentissage
Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} pour construire un classifieur ĉ de telle
sorte que
Ŷ+ = ĉ(X+ ).
Classification multi-classes : Iris dataset
Apprentissage statistique supervisé

▶ Input : covariables, variables explicatives, features X = (X1 , . . . , Xd )

▶ Ouput : variable à expliquer, variable dépendante, réponse, label Y
Approche probabiliste / statistique
Approche probabiliste / statistique en classification binaire

▶ Pour construire le classifieur ĉ, on construit des estimateurs p̂1 (x) et

p̂−1 (x) de

p1 (x) = P(Y = 1|X = x) et p−1 (x) = 1 − p1 (x)

▶ en modélisant la loi de Y|X.
▶ Puis, conditionnellement à X+ = x, on classifie en utilisant la règle
{
1 si p̂1 (x) ≥ s
Ŷ+ = ĉ(x) =
−1 sinon

pour un seuil s ∈ (0, 1).

▶ Si on choisit s = 1/2, cela revient à classifier suivant la plus grande valeur
entre p̂1 (x) et p̂−1 (x) (on retient cette règle dans la suite).
Classification binaire : toy datasets
Classification binaire : toy datasets
Classifieur bayésien (1)

Formule de Bayes
Nous savons que
fy (x)P(Y = y)
py (x) = P(Y = y|X = x) =
f(x)
fy (x)P(Y = y)
= ∑
y =−1,1 y
′ f ′ (x)P(Y = y′ )
∝ fy (x)P(Y = y),

où f est la densité jointe de X et fy est la densité de X condionnellement à

Y = y.

Donc si on estime les loi de X|Y et de Y, on a un estimateur de celle de Y|X.

Classifieur bayésien (2)

Classifieur bayésien
On construit un classifieur grâce à la formule de Bayes
▶ en modélisant la loi X|Y puis en l’estimant
▶ et en estimant la loi marginale de Y.

On aura donc

p̂y (x) = b
P(Y = y|X = x) ∝ f̂y (x)b
P(Y = y)

puis
{
1 si p̂1 (x) ≥ p̂−1 (x)
Ŷ+ = ĉ(x) =
−1 sinon
{
1 si f̂1 (x)b
P(Y = 1) ≥ f̂−1 (x)b
P(Y = −1)
=
−1 sinon
=argmaxy=−1,1 f̂y (x)b
P(Y = y).
Maximum a posteriori en classification binaire

Si, conditionnellement à X+ = x, on classifie en utilisant la règle

{
1 si p̂1 (x) ≥ p̂−1 (x)
Ŷ+ = ĉ(x) =
−1 sinon ,

c’est équivalent à utiliser une fonction discriminante.

Fonction discriminante

δ̂y (x) = log b

P(X = x|Y = y) + log b
P(Y = y)
pour y = 1, −1 et de classifier suivant sa valeur pour chaque y.
Classification multi-classes et maximum a posteriori

▶ On modélise la distribution de Y|X

▶ On construit des estimateurs p̂k (x) pour k ∈ C tels que
∑
p̂k (x) = 1
k∈C

▶ Conditionnellement à X+ = x, on classifie en utilisant la règle

Ŷ+ = argmaxk∈C p̂k (x).

On peut alors définir des fonctions discriminantes pour k ∈ C

δ̂k (x) = log b

P(X = x|Y = k) + log b
P(Y = k).

et décider de classifier avec la règle

Ŷ+ = argmaxk∈C δ̂k (x).

Remarque

▶ On peut choisir plusieurs modèles pour la loi de X|Y qui donnent des
classifieurs différents.
▶ Le plus simple est le “Naive Bayes”
▶ Nous verrons aussi l’analyse discriminante linéaire (Linear discriminant
analysis - LDA) et quadratique (Quadratic discriminant Analysis -QDA)
Naive Bayes

▶ On veut un modèle pour la loi de X|Y.

▶ Le plus simple est de considérer que les features Xj (j = 1, . . . , d) sont
indépendantes conditionnellement à Y.
▶ C’est équivalent à supposer que la densité conditionnelle fy (x) de X|Y = y
est donnée par
∏
d

fjy (xj )
j=1

où fjy est la densité de Xj |Y = y.

Quelle loi pour Xj |Y = y ?

▶ Si Xj est une variable continue, on choisit la loi normale

Xj |Y = y ∼ N (µj,y , σj,y
2
),
2
dont les paramètres µj,k et σj,k sont estimés par maximum de
vraisemblance.
2
Il suffit alors d’estimer les µj,y , σj,y pour tous les j = 1, . . . , d et les y ∈ C.
▶ Si Xj est une variable discrète, on choisit la loi de Bernoulli ou la loi
multinomiale.
Exemple sur le dataset Iris
Analyse discriminante
Analyse discriminante

Supposons que
X|Y = y ∼ N (µy , Σy ).
On rappelle que la densité de la loi N (µ, Σ) est donnée par
( )
1 1
f(x) = √ exp − (x − µ)⊤ Σ−1 (x − µ) .
(2π)d/2 det Σ 2
Estimation

On estime les paramètres inconnus par maximum de vraisemblance. Donc pour

y ∈ C, on pose
Iy = {i = 1, . . . , n : Yi = y} ny = |Iy |
et

b ny 1 ∑
P(Y = y) = , µ̂y = Xi ,
n ny
i∈Iy

1 ∑
Σ̂y = (Xi − µ̂y )(Xi − µ̂y )⊤ .
ny
i∈Iy

Ce sont simplement les proportions, moyennes et variances de chaque

sous-groupe de données défini par la valeur du label.
Fonctions discriminantes

Dans ce cas, les fonctions discriminantes sont

δ̂y (x) = log b

P(X = x|Y = y) + log b
P(Y = y)
1 d
= − (x − µ̂y )⊤ Σ̂−1
y (x − µ̂y ) − ln(2π)
2 2
1
− log det Σ̂y + log bP(Y = y)
2
Linear Discriminant Analysis (LDA)

Supposons que Σ = Σy pour tout y ∈ C (cela revient à supposer qu’il y a la

même structure de corrélation dans chaque groupe)
Linear Discriminant Analysis (LDA)
Les frontières de décision sont linéaires et les régions ont la forme (pour la
classification binaire) ⟨x, w⟩ ≥ c avec

w = Σ̂−1 (µ̂1 − µ̂−1 )

1
c = (⟨µ̂1 , Σ̂−1 µ̂1 ⟩ − ⟨µ̂−1 , Σ̂−1 µ̂−1 ⟩)
2
( b P(Y = 1)
)
+ log .
b
P(Y = −1)
Quadratic Discriminant Analysis (QDA)

On n’assume plus que Σ = Σy pour tout y ∈ C. Dans ce cas, les frontières sont
quadratiques.
Exemple sur le dataset Iris
Classifieur constants sur une partition
Rappel sur la classification

On a pour i = 1, . . . , n

▶ Xi ∈ R d
▶ Yi ∈ C = {−1, 1} ou {1, . . . , K}.

But

▶ On veut pour un nouveau vecteur X+ de features prédire la valeur du label

Y+ par Ŷ+ ∈ C = {1, . . . , K}
▶ Pour cela, on utilise les données d’apprentissage
Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} pour construire un classifieur ĉ de telle
sorte que
Ŷ+ = ĉ(X+ ).
Classifieur constants sur une partition

On va considérer

▶ une partition A = {A1 , . . . , AM } de X (qui peut dépendre des données)

▶ l’ensemble FA des fonctions constantes sur A
▶ la perte 0/1 ℓ(y, y′ ) = 1yy′ ≤0

on cherche alors un classifieur ĉ qui vérifie

1∑ 1∑
n n

ĉA = argmin ℓ(Yi , c(Xi )) = argmin 1Yi c(Xi )≤0 .

c∈FA n c∈FA n
i=1 i=1
Vote majoritaire

En classification binaire, on sait alors que ĉA vérifie pour x ∈ Am

{
1 si #{i : Xi ∈ Am , Yi = 1} > #{i : Xi ∈ Am , Yi = −1}
ĉA (x) =
−1 sinon
{
1 si ȲAm > 0
=
−1 sinon

En classification multi-classes, on posera pour x ∈ Am

ĉA (x) = argmax #{i : Xi ∈ Am , Yi = k}

k∈{1,...,K}

Il reste à choisir la partition A = {A1 , . . . , AM } de X !

Exemple: k plus proches voisins (avec k = 3)
1 2

3 4
Exemple: k plus proches voisins (avec k = 4)
k plus proches voisins

k plus proches voisins

On considère l’ensemble Ix composé des k indices de {1, . . . , n} pour lesquels
les distances ∥x − Xi ∥ sont minimales.
On pose
ĉ(x) = argmax #{i ∈ Ix , Yi = k}.
k∈{1,...,K}

▶ En pratique, il faut choisir la distance

▶ et k !!
Partition

On remarque que Ix appartient à l’ensemble {ϕ1 , . . . , ϕM } des combinaisons de

k éléments parmi n avec ( )
n
M= .
k

On peut donc poser

Am = {x ∈ X , Ix = ϕm }.
k-NN
k-NN
Construction de l’arbre

Approche “top-bottom”

▶ On commence par une région qui contient toutes les données

▶ On coupe récursivement les régions par rapport à une variable et une
valeur de cette variable
Heuristique:

On veut choisir la valeur du “split” de telle sorte que les deux nouvelles régions
sont les plus homogènes possible...

L’homogénéité peut se définir par différents critères

▶ la variance empirique
▶ l’indice de Gini
▶ l’entropie.
Arbre de classification à partir de l’indice de Gini

On coupe une région R en deux parties R− and R+ . Pour chaque variable

j = 1, . . . , p et chaque valeur de “split” t, on définit

R− (j, t) = {x ∈ R : xj < t} et R+ (j, t) = {x ∈ R : xj ≥ t}.

on cherche j et t qui minimisent

Gini(R− ) + Gini(R+ )

where ∑
1
Gini(R) = p̂R,k (1 − p̂R,k )
|{i, Xi ∈ R}|
k∈C

où p̂R,k est la proportion d’observations avec le label k dans l’ensemble des

{i, Xi ∈ R}.
Algorithmes CART, C.4.5

▶ l’algorithme CART utilise l’indice de Gini

▶ l’algorithme C.4.5 (pas implementé dans sklearn) utilise l’entropie
∑
E(R) = − p̂R,k log(p̂R,k )
k∈C

▶ il y a d’autres critères possibles (χ2 , etc)

CART
CART
Règles d’arrêt et algorithmes dérivés

Règles d’arrêt
On arrête l’algorithme quand
▶ l’arbre a atteint une taille maximale (fixée à l’avance)
▶ le nombre de feuilles atteint une valeur maximale (fixée à l’avance)
▶ quand les effectifs des noeuds terminaux atteignent une valeur minimale
(fixée à l’avance)

En pratique
En pratique, ce sont des algorithmes instables et qui sur-apprennent, on les
utilisent dans des algorithmes plus complexes qui “mélangent” des arbres
▶ les forêts alétoires (random forests)
▶ le boosting.
Minimisation de l’erreur, méthodes basées sur l’optimisation
Erreur empirique / erreur de généralisation

On se donne une fonction classifiante déterministe c : Rd ∈ C, on définit L la

loi inconnue des couples (Xi , Yi ) et
Erreur empirique ou erreur visible

1∑
n

Rn (c) = ℓ(Yi , c(Xi )).

n
i=1

Erreur de généralisation
( )
R(c) = EL ℓ(Y+ , c(X+ ))
où (X+ , Y+ ) est un couple indépendant de Dn

′
▶ En classification, on prend souvent ℓ(y, y ) = 1y̸=y′ , dans ce cas 1 − Rn (c)
est appelé “accuracy” de c.
Fonctions de perte classiques en classification binaire
▶ Logistic loss (régression logistique) ℓ(y, f(x)) = log(1 + exp(−yf(x)))
▶ Hinge loss (SVM), ℓ(y, f(x)) = (1 − yf(x))+
▶ Quadratic hinge loss (SVM), ℓ(y, f(x)) = 12 (1 − yf(x))2+
▶ Huber loss ℓ(y, f(x)) = −4yy′ 1yf(x)<−1 + (1 − yf(x))2+ 1yf(x)≥−1

▶ Toutes ces pertes peuvent être vues comme des approximations convexe de
la perte 0/1 ℓ(y, y′ ) = 1yy′ ≤0
Sur-apprentissage

Comportement de l’erreur
▶ L’erreur d’apprentissage décroît avec la complexité du modèle.
▶ L’erreur de généralisation (sur le test) a un comportement très différent.
Remarques

▶ On a ( )
R(c) = EL Rn (c) .
▶ On voudrait retrouver
c⋆ = argmin R(c)
c

Mais on se restreint le plus souvent à un sous-ensemble G (par exemple les

fonctions constantes sur une partition A)

coracle
G = argmin R(c)
c∈G

puis, comme la loi L est inconnue, on remplace R par Rn

ĉG = argmin Rn (c).

c∈G

On a bien sûr
R(ĉG ) ≥ R(coracle
G ) ≥ R(c⋆ ).
Cross Validation

Cross Validation
▶ On utilise (1 − ϵ)n observations pour apprendre et ϵn pour vérifier !
▶ On entraîne sur un jeu de données de taille (1 − ϵ) × n à la place de n!
▶ Assez instable si ϵn est trop petit

▶ Most classical variations:

▶ Leave One Out,
▶ K-fold cross validation (K = 3, 5, 10).
Ensemble methods
Le boosting : weak learners

Weak learners
▶ Considérons un ensemble de “weak learners” H
▶ Chaque learner h : Rd → {−1, 1} est un learner très simple
▶ Chaque learner simple est à peine meilleur que celui appris avec les Yi
(moyenne)

Exemples de weak learners

▶ Pour la régression : arbres de régression simple de faible profondeur,
modèle linéaire à quelques variables
▶ Pour la classification : arbre de décision simple de faible profondeur,
modèle logistique à quelques variables.
Principe du boosting

Un ”strong learner”
On combine additivement des weak learners
∑
B

g(B) (x) = η (b) h(b) (x)

b=1

avec η (b) ≥ 0 pour espérer en obtenir un meilleur. g(b) est un learner dans le
sens où on Ŷi = g(b) (Xi ).

▶ Chaque b = 1, . . . , B est un pas/itération de boosting

▶ Le boosting fait partie des ensemble methods puisqu’il combine des
learners faibles pour en fabriquer un meilleur.

Pour aller plus loin : voir Schapire 1999 et Friedman 2001

Text mining: comment transformer un texte en un vecteur
numérique ?
Hashing
Hashing

▶ Idée: réduire le nombre de valeurs d’une variable nominale avec des valeurs
dans un grand ensemble D

Hashing
▶ Construction d’une fonction de hashage H: D → {1, . . . , V} et on utilise
les valeurs hashées au lieu des valeurs originales.
▶ La fonction de hashage doit être la plus injective possible..., du moins au
sens probabiliste.

Construire une telle fonction est un art !

Bag of Words
Bag of Words

▶ Comment transformer un texte en vecteur numérique de features ?

La stratégie “Bag of Words strategy”

▶ Créer un dictionnaire de mots,
▶ Calculer un poids pour chaque mot.

Construction d’une liste

▶ Faire une liste de tous les mots avec le nombre d’occurrence
▶ Réunir les mots qui ont la même racine (stemming)
▶ Hash les racines avec une fonction de hashage (MurmurHash avec 32bits
par exemple)
▶ Calculer l’histogramme hw (d)
TD-IDF

Calcul des poids

▶ Calculer l’histogramme hw (d)
▶ Re-normaliser :
▶ tf transformation (profil du mot):

tfw (d) = ∑hw (d)

w
hw (d)
de telle sorte que tfw (d) est la fréquence dans le document d.
▶ tf-idf transformation (profil du mot re-pondéré par sa rareté):
tf − idfw (d) = idfw × tfw (d)
avec idf un poids dépendant du corpus
n
idfw = log ∑n
1
i=1 hw (di )̸=0

▶ Utiliser le vecteur tf(d) (or tf − idf(d)) pour décrire un document.

▶ C’est le pré-processing le plus classique en textmining.
Clustering de textes

Probabilistic latent semantic analysis (PLSA)

▶ Modèle:

∑
K

P (tf) = P (k) P (tf|k)

k=1

avec k le thème caché, P (k) la probabilité du thème et P (tf|k) une loi

multinomiale pour le thème.
▶ Clustering avec un modèle de mélange

P[ (k)P\ (tf|k)
P (k|tf) = ∑
\ \′
′ P (k )P (tf|k )
′
k

▶ Modèle de mélange
▶ Il existe une variante bayésienne appelée Latent Dirichlet Allocation.
Mots et Word Vectors
Word Vectors

Word Embedding
▶ On construit une représentation des mots dans Rd .
▶ en espérant que la relation entre 2 vecteurs est liée à la relation entre les 2
mots dont ils sont issus.
Word And Context
Look ! A single word and its context
Le mot et son contexte
▶ Idée: caractériser un mot w par son contexte c...
▶ Description probabiliste:
▶ Loi jointe : f(w, c) = P (w, c)
▶ Lois conditionnelles: f(w, c) = P (w|c) or f(w, c) = P (c|w).
▶ Information mutuelle : f(w, c) = P (w, c) /(P (w) P (c))
▶ Le mot w est caractérisé par le vecteur Cw = (f(w, c))c ou
Cw = (log f(w, c))c .

▶ En pratique, on estime C sur un large corpus

▶ Attention : c’est un modèle de très grande dimension !

▶ GloVe (Global Vectors) via les moindres carrés

▶ Word2vec via la régression logistique
▶ Singular value decomposition