Dea instrumentation et commande Reconnaissance des formes



Yüklə 445 b.
tarix11.08.2018
ölçüsü445 b.
#69097


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



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin