Dea instrumentation et commande Reconnaissance des formes

DEA instrumentation et commande

• Reconnaissance des formes

• Erreurs et coûts des algorithmes

• S. Canu

• http://psichaud.insa-rouen.fr/~scanu/RdF

Buts de la RdF

RdF et apprentissage

Grandes déviations

Grandes déviations Bienaimé Tchebitchev

• pour tout P

• Démonstration

Grande déviation

Application : comparaison d’algorithmes

Application : comparaison d’algorithmes

Application : Choix de la taille de l’ensemble test

Comment améliorer cette borne ?

• Améliorer l’inégalité des grandes déviations.

• Inégalité de markov

• Hoeffding erreur bornée

• Chernov Classification

• Bernstein

• Bennet

Grandes déviations généralisation de Bienaimé Tchebitchev

• pour tout P

• Démonstration

Lemme de Markov

• soit (A,,D) un espace probabilisé

• soit X une v.a. sur (A,)

• soit  > 0

• Alors :

• Démonstration

• comme Bienaymé Tchébychev

Comment choisir h(x) ?

Récapitulons

Taille de l’échantillon pour une précision

Exemples

Exemples

Estimation de l’erreur d’un classifieur

Estimation de l’erreur

• Beaucoup d’exemples : ensemble test DONNEES

• Peu d’exemples : le rééchantillonnage TEMPS

• Validation croisée
• Jackknife
• Bootstrap

• Analyse théorique : PRECISION

Ensemble test

• grandes déviations

Rééchantillonnage

• Validation croisée

• Jackknife

• Bootstrap

Bootstrap

Bootstrap

Exemple de Bootstrap

Validation par Bootstrap

Validation par Bootstrap

• Faire B fois (B ­ 50)

• 1 : Générer un nouvel échantillon : x*b(t) ; t = 1:T
• x*b(t+1) = r(x*b(t)) + b(t)
• 2 : Apprendre ce nouvel échantillon : r*b(x)

• Biais b :  (x(t+1) - r*b(x(t))) -

•  (x*b(t+1) - r*b(x*b(t)))

Exemple de bootstrap

Théorie des bornes

• Avec une probabilité (1 - ), pour tous les :

• EP(w) < Cemp(w) + (VCdim(B), Cemp(w), n, )

• erreur < coût visible + complexité, nb d’exemples, précision

• mesure de complexité :

• Taille de B ?
• Nombre de paramètres ?
• dimension de Vapnik - Chervonenkis (pire des cas)

• e.g. Dim VC d'un ensemble de fonctions à seuil = taille du plus grand ensemble S pour lequel le système peut implémenter les 2|S| dichotomies sur S.

Un exemple de grande déviation

• T une v.a.

• de bernouilli

Convergence uniforme

Borne sur l’erreur d’apprentissage