Classification

Classification

Compare to : Regression

Decision Trees

L’idée de base derrière la construction d’un arbre de décision est de :

1. Trouver une séparation optimale (caractéristique + seuil). C’est-à-dire la séparation qui minimise l’impureté (maximise le gain d’information).
2. Diviser le jeu de données en 2 sous-ensembles basés sur la séparation ci-dessus.
3. Appliquer récursivement les étapes $1$ et $2$ à chaque nouveau sous-ensemble jusqu’à ce qu’un critère d’arrêt soit atteint.
4. Pour éviter le surapprentissage : élaguer les nœuds qui “ne sont pas très utiles”.

Voici un petit GIF montrant ces étapes :

Note: For more information, please see the "details" and "Pseudocode and Complexity" drop-down below.

def buildTree(X,Y):
    if stop_criteria(X,Y) :
        # if stop then store the majority class
        tree.class = mode(X) 
        return Null

    minImpurity = infinity
    bestSplit = None
    for j in features:
        for T in thresholds:
            if impurity(X,Y,j,T) < minImpurity:
                bestSplit = (j,T)
                minImpurity = impurity(X,Y,j,T) 

    X_left,Y_Left,X_right,Y_right = split(X,Y,bestSplit)

    tree.split = bestSplit # adds current split
    tree.left = buildTree(X_left,Y_Left) # adds subsequent left splits
    tree.right buildTree(X_right,Y_right) # adds subsequent right splits

return tree

def singlePredictTree(tree,xi):
    if tree.class is not Null:
        return tree.class

    j,T = tree.split
    if xi[j] >= T:
        return singlePredictTree(tree.right,xi)
    else:
        return singlePredictTree(tree.left,xi)

def allPredictTree(tree,Xt):
    t,d = Xt.shape
    Yt = vector(d)
    for i in t:
        Yt[i] = singlePredictTree(tree,Xt[i,:])

    return Yt

Naive Bayes

Naive Bayes est une famille de modèles génératifs qui prédit $p(y=c \vert\mathbf{x})$ en supposant que toutes les caractéristiques sont conditionnellement indépendantes, étant donné l’étiquette : $x_i \perp x_j \vert y , \forall i,j$. Il s’agit d’une hypothèse simplificatrice qui est très rarement vraie en pratique, ce qui rend l’algorithme “naïf”. Classifier avec une telle hypothèse est très simple :

Notez que, puisque nous sommes dans un cadre de classification, $y$ prend des valeurs discrètes, donc $p(y=c, \pmb\theta)=\pi_c$ est une distribution catégorielle.

Vous vous demandez peut-être pourquoi nous utilisons l’hypothèse simplificatrice d’indépendance conditionnelle. Nous pourrions directement prédire en utilisant $\hat{y} = arg\max_c p(y=c, \pmb\theta)p(\mathbf{x} \vert y=c, \pmb\theta)$. L’hypothèse d’indépendance conditionnelle nous permet d’avoir de meilleures estimations des paramètres $\theta$ en utilisant moins de données . En effet, $p(\mathbf{x} \vert y=c, \pmb\theta)$ nécessite beaucoup plus de données car il s’agit d’une distribution en $D$ dimensions (pour chaque étiquette possible $c$), tandis que $\prod_{j=1}^D p(x_j \vert y=c, \pmb\theta)$ la factorise en $D$ 1-distributions unidimensionnelles, ce qui nécessite beaucoup moins de données en raison de la malédiction de la dimensionnalité. En plus de nécessiter moins de données, cela permet également de facilement combiner différentes familles de distributions pour chaque caractéristique.

Nous devons encore aborder deux questions importantes :

• Quelle famille de distributions utiliser pour $p(x_j \vert y=c, \pmb\theta)$ (souvent appelée le modèle d’événements du classificateur Naive Bayes) ?
• Comment estimer les paramètres $\theta$?

Modèles d’événements de Naive Bayes

La famille de distributions à utiliser est un choix de conception important qui donnera lieu à des types spécifiques de classificateurs Naive Bayes. Il est important de noter que la famille de distributions $p(x_j \vert y=c, \pmb\theta)$ n’a pas besoin d’être la même pour tous les $j$, ce qui permet d’utiliser des caractéristiques très différentes (par exemple des données continues et discrètes). En pratique, on utilise souvent la distribution gaussienne pour les caractéristiques continues, et les distributions multinomiale ou de Bernoulli pour les caractéristiques discrètes :

Gaussian Naive Bayes :

L’utilisation d’une distribution gaussienne est une hypothèse typique lorsqu’on traite des données continues $x_j \in \mathbb{R}$. L’utilisation d’une distribution gaussienne est une hypothèse typique lorsqu’on traite des données continues.

Notez que si toutes les caractéristiques sont supposées gaussiennes, cela correspond à ajuster une gaussienne multivariée avec une matrice de covariance diagonale : $p(\mathbf{x} \vert y=c, \pmb\theta)= \mathcal{N}(\mathbf{x};\pmb\mu_{c},\text{diag}(\pmb\sigma_{c}^2))$.

La frontière de décision est quadratique car elle correspond à des ellipses (gaussiennes) qui se croisent . .

Multinomial Naive Bayes :

Dans le cas des caractéristiques catégorielles $x_j \in \{1,…, K\}$ nous pouvons utiliser une distribution multinomiale, où $\theta_{jc}$ désigne la probabilité d’avoir la caractéristique $j$à n’importe quelle étape d’un exemple de classe $c$ :

Naive Bayes multinomial est typiquement utilisé pour la classification de documents , et correspond à représenter tous les documents comme un sac de mots (sans ordre). Nous estimons ensuite (voir ci-dessous) $\theta_{jc}$ en comptant les occurrences des mots pour trouver les proportions de fois où le mot $j$ est trouvé dans un document classé comme $c$.

L’équation ci-dessus est appelée Naive Bayes bien que les caractéristiques $x_j$ ne soient techniquement pas indépendantes en raison de la contrainte $\sum_j x_j = const$. La procédure d’entraînement reste cependant la même car, pour la classification, nous nous soucions uniquement de comparer les probabilités plutôt que de leurs valeurs absolues. Dans ce cas, Naive Bayes multinomial donne en fait les mêmes résultats qu’un produit de Naive Bayes catégoriel dont les caractéristiques respectent la propriété d’indépendance conditionnelle.

Naive Bayes multinomial est un classificateur linéaire lorsqu’il est exprimé dans l’espace logarithmique :

Naive Bayes Bernoulli multivarié :

Dans le cas des caractéristiques binaires $x_j \in \{0,1\}$ nous pouvons utiliser une distribution de Bernoulli, où $\theta_{jc}$ représente la probabilité que la caractéristique $j$ se manifeste dans la classe $c$:

Naive Bayes Bernoulli est typiquement utilisé pour classifier des textes courts , et correspond à l’observation de la présence ou de l’absence de mots dans une phrase (sans compter les occurrences).

Naive Bayes Bernoulli multivarié n’est pas identique à l’utilisation de Naive Bayes multinomial avec les fréquences d’occurrence tronquées à 1. En effet, il modélise l’absence des mots en plus de leur présence.

Entraînement

Enfin, nous devons entraîner le modèle en trouvant les meilleurs paramètres estimés $\hat\theta$. Cela peut être fait soit en utilisant des estimations ponctuelles (par exemple MLE), soit avec une approche bayésienne.

Estimation du Maximum de Vraisemblance (MLE) :

La log-vraisemblance négative du jeu de données $\mathcal{D}=\{\mathbf{x}^{(n)},y^{(n)}\}_{n=1}^N$ est :

Comme la log-vraisemblance négative se décompose en termes qui dépendent uniquement de $\pi$ et de chaque $\theta_{jc}$ nous pouvons optimiser tous les paramètres séparément.

En minimisant le premier terme en utilisant des multiplicateurs de Lagrange pour imposer $\sum_c \pi_c$,, nous obtenons que $\hat\pi_c = \frac{N_c}{N}$. ce qui correspond naturellement à la proportion d’exemples étiquetés avec $y=c$.

La valeur de $\theta_{jc}$ dépend de la famille de distribution que nous utilisons. Dans le cas du modèle multinomial, il peut être démontré que $\hat\theta_{jc}=\frac{N_{jc}}{N_c}$. Cela est très facile à calculer, car il suffit de compter le nombre de fois où une certaine caractéristique $x_j$ est observée dans un exemple avec l’étiquette $y=c$.

Estimation Bayésienne :

Le problème avec l’estimation du maximum de vraisemblance (MLE) est qu’elle conduit à du surapprentissage. Par exemple, si une caractéristique est toujours présente dans tous les échantillons d’entraînement (par exemple le mot “the” dans la classification de documents), le modèle échouera s’il rencontre un échantillon de test sans cette caractéristique, car il attribuerait une probabilité de 0 à toutes les étiquettes.

En adoptant une approche bayésienne, le surapprentissage est atténué grâce à l’utilisation de priors (a priori). Pour ce faire, il est nécessaire de calculer la probabilité a posteriori : \(\begin{aligned} p(\pmb\theta \vert \mathcal{D}) &= \prod_{n=1}^N p(\pmb\theta \vert \mathbf{x}^{(n)},y^{(n)}) & \textit{i.i.d} \text{ dataset} \\ &\propto \prod_{n=1}^N p(\mathbf{x}^{(n)},y^{(n)} \vert \pmb\theta)p(\pmb\theta) \\ &\propto \prod_{c=1}^C \left( \pi_c^{N_c} \cdot p(\pi_c) \right) \prod_{j=1}^D \prod_{c=1}^C \prod_{n : y^{(n)}=c} \left( p(x_{j}^{(n)} \vert \theta_{jc}) \cdot p(\theta_{jc}) \right) \\ \end{aligned}\)

En utilisant des priors conjugués (facteurs) (Dirichlet pour le Multinomial, Beta pour le Bernoulli, Gaussienne pour le Gaussien), cela donne les mêmes estimations que dans le cas de l’estimation du maximum de vraisemblance (MLE) (le prior a la même forme que la vraisemblance et la probabilité a posteriori), mais avec régularisation.

Le cadre bayésien nécessite de prédire en intégrant tous les paramètres $\pmb\theta$. La seule différence avec le premier ensemble d’équations que nous avons dérivé pour la classification en utilisant Naive Bayes, est que la distribution prédictive est conditionnée par les données d’entraînement $\mathcal{D}$ au lieu des paramètres $\pmb\theta$: \(\begin{aligned} \hat{y} &= arg\max_c p(y=c \vert \pmb{x},\mathcal{D}) \\ &= arg\max_c \int p(y=c\vert \pmb{x},\pmb\theta) p(\pmb\theta \vert \mathcal{D}) d\pmb\theta\\ &= arg\max_c \int p(\pmb\theta\vert\mathcal{D}) p(y=c \vert\pmb\theta) \prod_{j=1}^D p(x_j\vert y=c, \pmb\theta) d\pmb\theta \\ &= arg\max_c \left( \int p(y=c\vert\pmb\pi) p(\pmb\pi \vert \mathcal{D}) d\pmb\pi \right) \prod_{j=1}^D \int p(x_j\vert y=c, \theta_{jc}) p(\theta_{jc}\vert\mathcal{D}) d\theta_{jc} & & \text{Factored prior} \\ \end{aligned}\)

Comme précédemment, le terme à maximiser se décompose en un terme par paramètre. Tous les paramètres peuvent donc être maximisés indépendamment. Ces intégrales sont généralement intraitables, mais dans le cas de la Gaussienne, du Multinomial et du Bernoulli avec leurs priors conjugués correspondants, nous pouvons heureusement calculer une solution sous forme fermée.

Dans le cas du Multinomial (et du Bernoulli), la solution équivaut à prédire avec une estimation ponctuelle $\hat{\pmb\theta}=\bar{\pmb\theta}$. Où $\bar{\pmb\theta}$ est la moyenne de la distribution a posteriori.

En utilisant un prior Dirichlet symétrique : $p(\pmb\pi)=\text{Dir}(\pmb\pi; \pmb{1}\alpha\pi)$ nous obtenons que $\hat\pi_c = \bar\pi_c = \frac{N_c + \alpha\pi }{N + \alpha_\pi C}$.

Le Naive Bayes Multinomial bayésien équivaut à prédire avec une estimation ponctuelle :

I.e. Naive Bayes Multinomial Bayésien avec un prior Dirichlet symétrique attribue une distribution a posteriori prédictive :

Le modèle graphique correspondant est :

Lorsqu’on utilise un prior uniforme $\alpha_\theta=1$,cette équation est appelée lissage de Laplace ou lissage additif. Intuitivement, $\alpha$ représente un “pseudo-comptage” $\alpha_\theta$ des caractéristiques $x_{jc}$ . Pour la classification de documents , cela correspond simplement à attribuer un comptage initial non nul à tous les mots, ce qui évite le problème d’avoir un document de test $x^{(t)}$ avec $p(y=c\vert x^{(t)})=0$ s’il contient un seul mot $x_{j}^*$ qui n’a jamais été vu dans un document d’entraînement avec l’étiquette $c$. $\alpha=1$ est un choix courant dans les exemples, bien que des valeurs plus petites fonctionnent souvent mieux . .

Notes supplémentaires :

• Le terme “Naïf” vient de l’indépendance conditionnelle des caractéristiques étant donné l’étiquette. La partie “Bayes” du nom vient de l’utilisation du théorème de Bayes pour utiliser un modèle génératif, mais ce n’est pas une méthode bayésienne car elle ne nécessite pas de marginaliser sur tous les paramètres.

• Si nous estimions le Naive Bayes multinomial en utilisant l’estimation du maximum a posteriori (MAP) au lieu de la MSE ou de la méthode bayésienne, nous prédirions en utilisant la mode de la distribution a posteriori (au lieu de la moyenne dans le cas bayésien) : $\hat\theta_{jc}=\frac{N_{jc} + \alpha - 1}{N_c + (\alpha -1)D}$ (de même pour $\pmb\pi$). Cela signifie que le lissage de Laplace pourrait également être interprété comme utilisant MAP avec un prior non uniforme $\text{Dir}(\pmb\theta; \pmb{2})$. Mais lorsque l’on utilise un prior Dirichlet uniforme, MAP coïncide avec la MSE.

• Le Naive Bayes gaussien est équivalent à l’analyse discriminante quadratique lorsque chaque matrice de covariance $\Sigma_c$ est diagonale.

• Naive Bayes discrète et la régression logistique forment un “couple génératif-discriminatif”, car ils prennent la même forme (linéaire dans les probabilités logarithmiques) mais estiment les paramètres différemment. Par exemple, dans le cas binaire, Naive Bayes prédit la classe avec la plus grande probabilité. C’est-à-dire qu’il prédit $C_1$ si $\log \frac{p(C_1 \vert \pmb{x})}{p(C_2 \vert \pmb{x})} = \log \frac{p(C_1 \vert \pmb{x})}{1-p(C_1 \vert \pmb{x})} > 0$. Nous avons vu que Naive Bayes discrète est linéaire dans l’espace logarithmique, donc nous pouvons réécrire l’équation comme $\log \frac{p(C_1 \vert \pmb{x})}{1-p(C_1 \vert \pmb{x})} = 2 \log p(C_1 \vert \pmb{x}) - 1 = 2 \left( b + \mathbf{w}^T_c \mathbf{x} \right) - 1 = b' + \mathbf{w'}^T_c \mathbf{x} > 0$. Cette régression linéaire sur le ratio de cotes logarithmiques est exactement la forme de la régression logistique (l’équation habituelle est retrouvée en résolvant $\log \frac{p}{1-p} = b + \mathbf{w'}^T \mathbf{x}$). La même chose peut être démontrée pour Naive Bayes multinomial et la régression logistique multinomiale.

• Pour la classification de documents, il est courant de remplacer les comptages bruts dans Naive Bayes multinomial par des poids tf-idf.

Ressources : Voir la section 3.5 du livre de K. Murphy pour tous les détails de la dérivation et des exemples.

Regression

Arbres de décision

Les arbres de décision sont plus souvent utilisés pour les problèmes de classification.

Les deux différences avec les arbres de décision pour la classification sont :

• Quelle erreur minimiser pour une séparation optimale ? Cela remplace la mesure d’impureté dans le cadre de la classification. Une fonction d’erreur largement utilisée pour la régression est la somme des erreurs au carré. Nous n’utilisons pas l’erreur quadratique moyenne afin que la soustraction de l’erreur avant et après une séparation ait du sens. La somme des erreurs au carré pour la région $R$ est :

• Que prédire pour une région donnée ? Dans le cadre de la classification, nous prédisions la mode du sous-ensemble des données d’entraînement dans cette région. Prendre la mode n’a pas de sens pour une variable continue. Maintenant que nous avons défini une fonction d’erreur ci-dessus, nous voudrions prédire une valeur qui minimise cette somme des erreurs au carré. Cela correspond à la valeur moyenne de la région. Prédire la moyenne est intuitivement ce que nous aurions fait.

Jetons un coup d’œil à un graphique simple pour mieux comprendre l’algorithme :

En plus des inconvénients vus dans les arbres de décision pour la classification, les arbres de décision pour la régression souffrent du fait qu’ils prédisent une fonction non lisse .