Introduction

Classical Machine Learning - cf slides

Motivation

• Connaissances
  • Terminologie
  • Fonctionnement des méthodes
  • Faire des liens entre les méthodes
• Savoir Faire
  • Méthodologie
  • Utilisation de lib (paramètres)
  • Analyse et présentation de résultats
• TP = TD
  • Exercices en relation avec le cours
  • Compréhension des lib & illustration des notions
  • Python, keras, scikit-learn, scikit-image, panda, matplotlib
• Evaluation
  • CC1 : Supervised ML (hors NN)
  • CC2 : Unsupervised ML, NN, deep learning
  • Progression TD + Rapport TP final

Premier contact

Entrée : Ensemble d’exemples étiquetés.

Objectif : Pouvoir attribuer ue étiquette à un nouvel exemple.

Cadre

Apprentissage d’une fonction \(f\) à partir d’exemples. On ne pourra pas trouver \(f\) mais une hypothèse \(h\) parmi un ensemble \(\mathbb{H}\) d’hypothèses qui s’approche le plus de \(f\).

=> Apprentissage = problème de recherche dans un espace

Inférence

Syllogisme : a : tout homme est mortel b : socrate est un homme c : socrate est mortel

• Inférence déductive : a & b -> c
• Inférence abductive a & c -> b
• Inférence inductive b & c -> a

Problématique de l’apprentissage inductif

• Choix de description des exemples
• Choix de l’espace d’hypothèses : quelles fonctions s’autorise t on ?
• Algorithme d’apprentissage
• Évaluation de l’apprentissage

Erreurs

• Mauvais exemple d’apprentissage : Erreur intrinsèque
• H trop petit : Erreur d’approximation (Biais)
• Apprentissage pas assez poussé : Erreur d’estimation (Variance)

Principe inductife ERM (Empirical Risk Minimisation) : On cherche la fonction de H minimisant le risque empirique (erreur sur les données d’entrainement)

MAIS : Over Fitting

Solution : Séparer jeu d’apprentissage & de test

Apprentissage supervisé

Taux d’erreur apparent et réel

On peut s’intéresser aux matrices de confusions :

• En indice de colonne : la valeur attendue (réelle)
• En indice de ligne : la valeur obtenue (prédit)

-> Erreur empirique = \(\frac{1+1}{9+1+1+11} = 9\%\)

Validation croisée et leave-one-out

Cas d’application :

• Peu de données
• Meilleure estimation de l’erreur réelle

NB : En gros, on essaie d’évaluer la qualité de l’approche, plutôt que d’obtenir le meilleur classifieur possible.

Arbre de décision

Construction

• On choisit itérativement un attribut et un test (sélecteur) sur cet attribut, en accord avec un certain critère (celui qui sépare le mieux les classes)
• À la fin, on obtient un arbre maximal \(T_{max}\)
• On élague cet arbre pour éviter l’apprentissage par coeur

1. \(T_{max}\) Comment on choisit le meilleur test… ? On essaie de minimiser l’enthropie.

À chaque étape, on calcule l’entropie conditionée par chaque attribut restant. On discrimine selon l’attribut fournissant l’entropie la plus faible.

Autre critère :

• critère de Gini : \(Gini(X) = 1 - \sum_{x \in X} P(x)^2\)
• Pleins d’autres, tant qu’ils discriminent la déseorganisation

Que faire en cas d’attributs continus (par exemple numériques) ? On fixe un certain seuil discriminant.

En pratique :

• On prend un seuil égal à la valeur de l’exemple minimisant l’entropie.

RQ : On garde l’exemple pour un potentiel usage futur.

PB : Biaisé vers les attributs avec une grande arrité (beaucoup de valeurs possibles), car on peut classifier plus facilement avec, et donc on peut plus facilement diminuer l’entropie.

En maximisant cette métrique, on mitige ce pb.

Il reste encore un pb : On fait une séparation orthogonalement aux axes. Pas très opti dans certains cas… On peut utiliser des arbres obliques, mais c’est complexe et coûteux.

2. Pruning

• Pre prunning : On s’arrête avant qu’on ait convergé.
  • On s’arrête quand on est en dessous d’une certaine entropie
  • À partir d’une certaine profondeur
  • …
  • Mauvais en général, dur de trouver une bonne heuristique et choix arbitraires
• Post pruning
  • On élague en accord avec les résultats sur un ensemble de validation

Linear models

Linear regression

Univariate

PB : Find \(theta_0\) and \(theta_1\) such that \(h_{theta} : x \mapsto theta_0 + theta_1 x\) approximate the best (for a certain distance)

Usually, we want to minimise the quadratic mean cost : \(\frac{1}{2} \sum_{i=1}^m (h_{theta} (x_i) - y_i) ^ 2\).

Multivariate

PB : Find \(\mathbf{theta}\) such that \(h_{\mathbf{theta}} : \mathbf{x} \mapsto \left< \mathbf{theta} | (1, \mathbf{x}) \right>\) approximate the best (for a certain distance)

(One can also note \(\mathbf{x}_0 = 1\))

Logistic regression (GLM : Generalised Linear Model)

Like linear regression, but we want to classify in 2 classes.

We define the sigmoid / logistic function :

\(g : z \mapsto \frac{1}{1+exp(-z)}\)

We then take the hypothesis : \(h_{\theta} (x) = g(\theta^T x)\).

• We take two random variables \(Y, X\), and we want to deduce the best \(p = \mathbb{P}(Y = 1 | X = x)\) (\(Y\) is a bernoulli random variable).
• let \(x \in \mathbb{R}^{d+1}\), with \(x_0 = 1\)
• \(\mathbb{P}(Y=1)\) is a nonlinear function of a linear function of \(X\)
• The logistic condiational model is \(p = \mathbb{P}(Y=1|x;\theta)=h_{\theta}(x)=g(\theta^T x)\)

Then, we can classify, according to the following decision boundary :

• if \(h_{\theta}(x) \geq 0.5\), predicts \(y = 1\)
• otherwise, \(h_{\theta} (x) < 0.5\), predicts \(y = 0\)

Learning : by minimising negative log likelihood (or binary cross enthropy).

Multinomial

Use binomial law for \(Y\).

Generalised sigmoid : \(\mathbb{P}(Y=k|x;theta) = \frac{\theta_k^T x}{\sum_{c=1}^K exp(\theta_c^T x)}\) (again, proba to be in a class)

Also named MaxEnt, softmax regression, multinomial logit, multiclass LR, cond MaxEnt model…

How to get a non linear classifier ?

Basis expension

We were using a linear function basis for our search space. Use a bigger base for the search, for instance, polynomials functions \(\rightarrow\) polynomial regression.

But : no longer one unique solution ?

Method : gradient descent (cf stat course).

Overfitting and reularisation

Idea : add a cost to the loss function (\(+ \lambda reg(\theta)\)), increasing in \(\theta\).

• Ridge regularisation : \(l_2\) norm on \(\theta\), but cluster correlated variables.
• Lasso regularisation : \(l_1\) norm on \(\theta\), act as feature selection. But no longer one unique solution (not convex).
• Elastic net : ponderised sum of both using a parameter \(\alpha\).

Terminology

MAIN WEBPAGE