15
Apprentissage et Fouilles de données Salma Najar 20 Mars 2008 FilterBoost: Regression et Classification On Large Datasets Joseph K. Bradley et Robert E.Schapire

Apprentissage et Fouilles de données

  • Upload
    roger

  • View
    35

  • Download
    0

Embed Size (px)

DESCRIPTION

Apprentissage et Fouilles de données. FilterBoost : Regression et Classification On Large Datasets. Joseph K. Bradley et Robert E.Schapire. Salma Najar 20 Mars 2008 . Plan. Introduction Filterboost - PowerPoint PPT Presentation

Citation preview

Page 1: Apprentissage  et Fouilles de données

Apprentissage et Fouilles de données

Salma Najar 20 Mars 2008

FilterBoost: Regression et ClassificationOn Large Datasets

Joseph K. Bradley et

Robert E.Schapire

Page 2: Apprentissage  et Fouilles de données

Plan

• Introduction

• Filterboost

• Analyse

• Expérimentations

• Conclusion

Page 3: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Introduction

Introduction • Analyse FilterBoost Expérimentations Conclusion Introduction Problématique Motivation

Batch Boosting• Weak Learner• S: Ensemble fixe d’exemple d’entrainement• Après T ronds

-+

--+

Booster Hypothèse Finale

H

Dtεt αt

ht

Dt

Page 4: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

ProblématiqueBatch Booster accède à l’ensemble entier des exemples

d’entrainement

Traitement très cher pour les larges bases de données.

• Limite son application: Problème de classification des sites en ligne par exemple

• Limite son efficacité: A chaque rond Un traitement dans la base de données entière.

Introduction Problématique Motivation Introduction • Analyse FilterBoost Expérimentations Conclusion

Page 5: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

MotivationLe but principal : Rendre le boosting faisable dans de large base de données

Idée principle: Utiliser un flux de données au lieu d’utiliser la base de données enentier.

Entrainer un nouveau sous ensemble de données à chaque rond.

Introduction Problématique Motivation Introduction • Analyse FilterBoost Expérimentations Conclusion

FilterBoost

Page 6: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Présentation du FilterBoostPrésentation Batch Algorithme FilterBoost Algorithme Filtre

Oracle Nouveaux exemples IID de D dans chaque rond.

Algorithme :• Adaptif• Basé sur une logique de régression logistique.• Moins d’assomptions exigées que les travaux antérieurs.

Applicable:• Estimation de la probabilité conditionnelle

plus robuste au bruit et au sur apprentissage.• Classification

prouve compétitivité.

Introduction • Analyse FilterBoost Expérimentations Conclusion

Page 7: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Batch Algorithme Etant donné: Un ensemble fixe d’entrainement SPour t = 1,…,T

• Construire la distribution Dt de S• Faire fonctionner le Weak Learner• Choix hypothèse ht• Estimer Erreur εt de ht • Donner un poids αt à ht

Sortie : Hypothèse Finale H(x) = Σt αt ht(x)

Présentation Batch Algorithme FilterBoost Algorithme Filtre

Dans le Filtrage :Il n’ya pas d’ensemble fixe d’entrainement.

Mécanisme du Filtre:Simuler Dt

Accepter ou rejeter les exemples selon une probabilité qt

Introduction • Analyse FilterBoost Expérimentations Conclusion

Page 8: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

FilterBoost AlgorithmeEtant donné: OraclePour t = 1,…,T• Filtre donne acces à Dt• Tirer mt exemple du filtre

Choisir l’hypothèse ht• Tirer de nouveax exemples du filtre • Estimer l’erreur εt de ht

• Donner un poids αt à htOutput: Hypothèse Finale

Le nombre mt d’exemple doit être suffisamment large pour assurer que

l’erreur εt < ½ avec une forte probabilité.

Présentation Batch Algorithme FilterBoost Algorithme Filtre

• Tirer mt exemple du filtre

L’erreur de l’hypothèse finale < ε

Output: Hypothèse Finale

Introduction • Analyse FilterBoost Expérimentations Conclusion

Page 9: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Filtre

+

Label = + 1 Booster prédit -1 Mal classé Poids élevé Probabilité élevé d’être accepté

Accepter

Refuser

-

Label = -1 Booster prédit -1 Bien classé Poids faible Probabilité faible d’être accepté

Le filtre accepte l’exemple (x,y) avec une probabilité proportionnelle à l’erreur de la

prédiction du booster H(x)

Introduction • Analyse FilterBoost Expérimentations Conclusion Présentation Batch Algorithme FilterBoost Algorithme Filtre

Oracle

Page 10: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Analyse• Condition d’arrêt du boosting?

Si le filtre rejète suffisament d’exemples dans un seul appel, pt est petite

Ht est suffisamment correcte.

• Nombre de ronds que le boosting a besoin? Si l’erreur de ht : εt < ½ progrés significatif dans ce rond.

• Estimation des limites de l’Hypothèse faible? Utilisation du Nonmonotonic Adative Sampling

Introduction • Analyse FilterBoost Expérimentations Conclusion

Page 11: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Expérimentation (1/2)• La pondération au lieu du filtrage des exemples.

Augmente l’exactitude. Augmente la taille de l’ensemble d’entrainement.

• Simulation Oracle Permutation par hasard des données et utilisation des exemples dans le nouvel ordre.

Filtrer lors de l’entrainement du Weak Learner.Pondérer lors de l’estimation des limites.

Introduction • Analyse FilterBoost Expérimentations Conclusion Expérimentation Expérimentation :CPE Expérimentation: Classification

Page 12: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Expérimentation (2/2)• Tester FilterBoost avec et sans Confidence-Rated predictions.

•Tester FilterBoost contre d’autres Batch et Filtering Boostings: MadaBoost, AdaBoost, Logistic AdaBoost

• Tester: classification et conditional probability estimation

Filtering Boster est plus long que les batch dans de petite base de données.

Mais plus rapide dans les larges base de données.

Introduction • Analyse FilterBoost Expérimentations Conclusion Expérimentation Expérimentation :CPE Expérimentation: Classification

Page 13: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Expérimentation: CPE

Introduction • Analyse FilterBoost Expérimentations Conclusion Expérimentation Expérimentation :CPE Expérimentation: Classification

Décision Expert Arbre de Décision

Page 14: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Expérimentation: Classification

Introduction • Analyse FilterBoost Expérimentations Conclusion Expérimentation Expérimentation :CPE Expérimentation: Classification

Page 15: Apprentissage  et Fouilles de données

• Introduction • Travaux antérieurs • Problématique & motivations • Contribution • Conclusion

Conclusion• FilterBooster utilise des techniques de régression logistique, pour l’Estimation des probabilités conditionnelles et la classification.

• Boosting-by-Filtering Utilisation d’un oracle et non pas d’un ensemble fixe

d’entraînement.

• Résultats: Plus efficace et plus robuste pour apprendre avec de large bases de données. Plus rapide et plus robuste que le batch booster sans sacrifié l’exactitude.

Introduction • Analyse FilterBoost Expérimentations Conclusion