Phénomènes de Complexité et Concentration en Classification

Phénomènes de Complexité et Concentration en Classification

Richard Nock

rnock@martinique.univ-ag.fr

http://www.martinique.univ-ag.fr/~rnock

Groupe de Recherche en Informatique et Mathématiques Appliquées des Antilles-GuyaneDépartement Scientifique Interfacultaire

Application à l’Apprentissage Automatique,

au Data Mining et à l’Analyse d’Images

Background

• Ingénieur Agronome (1993)

• DEA Informatique (1993)

• Doctorat Informatique (1998)directeur: O. Gascuel

• Mcf UAG Guadeloupe (1998-2000)

• Mcf UAG Martinique (2000-)

Plan

Présentation de l’équipe

Deux résultats...Un résultat négatif (apprentissage/complexité)Un résultat positif (analyse d’images)

Encadrements et collaborationsEncadrement de thèseCollaborations scientifiquesCollaborations industries & collectivités

Production scientifique

Production scientifique

Algorithmes d’apprentissage/classification

Théorie(Complexité, stats/probas)

Analyse d’images

comment clusteriser plus finement ?

Production scientifiqueDonnées

Méthode

Théorie Théorie

imagesimages

Autre Réd. données Induction

non oui non

ALT ’00

oui

PKDD ’99ISIDA ’99CAIC ’98ICML ’98IC2IN ’97ICML ’95

IJ-IDA(99)IJ-PRAI(98)

ICASSP ’02ICIP ’02CVPR ’01ICIP ’00BMVC ’00ICTAI ’98

EWCBR ’00PRL(01)

TCS(02)JAIR(02)PRL(01)

ECML ’02ALT ’99ISAAC ’98ILP ’98ICCS ’98ICML ’96

ICML ’01FLAIRS ’01ICML ’00UAI ’00PKDD ’00CAIC ’00FLAIRS ’00PKDD ’99

JMLR(02)PR(02)IJ-AIT(00)Book(00)IJ-CSS(00)

Deux résultats…

Un résultat Positif« Fast and Reliable Region Merging inspired by Decision-Tree Pruning »R. Nock,IEEE Int. Conf. on Computer Vision and Pattern Recognition

2001

Un résultat (très) Négatifn

n 0

1 « Generalized Colorability and the Compressibility of Boolean Formulae »R. Nock, P. Jappy, J. SallantinInt. Symposium on Algorithms And Computation

1998

Un résultat (très) Négatif

Un résultat Négatif

• Apprendre =capacité pour une entité d’améliorer ses capacités de manière automatique, par l’expérience.

• Valiant (1984) = 2 contraintes:algorithmique: apprendre rapidestatistique: apprendre fiable

Modèle PAC: Probablement Approximativement Correct

Un résultat Négatif

• Valiant (C. ACM 1984, IJCAI 1985):les humains semblent être enclins à utiliser des systèmes de règles pour représenter leur connaissance.

Ces systèmes de règles sont-ils PAC apprenables?

Formes Normales Disjonctives (DNF)

Plan général (résultat Négatif)

• -Observations, Exemples, Concepts• -Le modèle PAC de Valiant• -Optimisation & approximation• -Preuves traditionnelles• -Notre solution: réductions « self-improving »• -Parallèle « intéressant »• -Conclusion & extensions

-Observations et Exemples

vvv n21,...,,

xx 11, xx 22

, xx nn,

On dispose de n variables Booléennes d ’observation:

Chacune génère 2 littéraux

Correspond au test vrai"V" 1

Par ex.:"" ? Leasing-Credit en achatiV

"" permis? de numéro son donné ajV 0,1

-Observations et Exemples

On veut prédire l ’appartenance à une classe, commefonction de ces variables d ’observation:

Par exemple: « bon payeur » « mauvais payeur »versus

Classe « positive » Classe « négative »Classe 1 Classe 0

n0,1Un élément est appelé une observation

0,10,1 nUn élément est appelé un exemple

classesnsobservatio

-Exemples et Concepts

L ’ensemble des exemples observables = domainePar exemple: clients potentiels d ’un assureur

Le sous-ensemble du domaine constitué des exemples positifs=concept cible (à apprendre)

Par exemple: bons payeurs pour un assureur

Représentations extensionnelles de conceptsPour apprendre, représentation intensionnelle d’un concept

Conceptcible domaine

-Exemples et Concepts

Représentation intensionnelle d’un concept= succincteelle est élément d’une classe de représentation de concepts

Par exemple: la classe des monômes Booléens

Un monôme Booléen=conjonction de littéraux

xxx 871Par exemple:

Une observation qui satisfait un monôme est classéepositive par ce monôme (sinon, classée négative)

Par exemple: 0101101100

Concept cible et concept hypothèse (qu’on construit) sont éléments de classes de représentations de concepts

11111110011 0

-Le modèle PAC

Apprendre C au sens de PAC, c’est, étant donné cC, induire à partir d’(un aperçu de) sa représentation extensionnelle, une formule hC:

• dont la représentation extensionnelle soit une bonne approximation de celle de c (whp),

• en temps polynomial en divers paramètres

Pour prouver que C n ’est pas PAC:

• Trop d’exemples nécessairespour satisfaire à la condition statistique

• Temps de calcul rédhibitoirepour satisfaire à la conditionalgorithmique

-Le modèle PAC

Pour prouver que C n ’est pas PAC:

• Temps de calcul rédhibitoirepour satisfaire à la conditionalgorithmique

-Le modèle PAC

On utilise la difficulté d’approximation d’un problème de minimisation (C gde)

-Optimisation & approximation

Définition (pour une classe de rep. de concepts C):

Instance

Solutions faisables

Ensemble d’exemples LS

Formules de C consistantes avec LS

Fonction de coût Taille de la formule

Objectif Trouver une solution faisable minimisant la fonction de coût

…nous étudions un pb d’optimisation

Comment démontrer un ratio d’inapproximabilité

transfert de ratio d’inapprox. d’un pb de min. vers un autre

Le coût d’une instance est le coût optimal d’une solution

pour cette instance

Un problème de minimisation est approximable à moins de

ssi il existe un algorithme poly permettant, pour une instance

de coût de trouver une solution de coût au plus

ρ

π ρπ

-Optimisation & approximation

ρ ?

…définition de l’approximabilité:

…retour sur les pbs d’optimisation

preuves traditionnelles en apprentissage:

-Optimisation & approximation

NPClasse des problèmes de décision admettant un algorithme non déterministe de résolution de temps polynomial en la taille de l’instance

NP

…retour sur les pbs de décision

NP-Complet

Problèmes« difficiles »

-Optimisation & approximation

Sous certaines

…retour sur les pbs de décision

hypothèsesces pbs difficiles n’admettent pas d’algo.

déterministe polynomial PNP

déterministe quasi-polynomial QPNP

déterministe sous-exponentiel ]2DTIME[NP I

randomisé polynomial ZPP,...NP

-Optimisation & approximation…des pbs de décision difficiles aux ratios d’inapproximabilité

Pb. de décision difficile

Oui

Non

Pb. de minimisationCoût des instances

ρα(...)

α(...)

ρ

Réd

uct

ion

« gap »

Un monôme (Booléen): conjonction de littéraux:

xxx 871

Une DNF: disjonction de monômes:

xxxxx 72871

Une k-term-DNF: disjonction d ’au plus k monômes

-Preuves traditionnelles…pour DNF

k=3

« Oui »

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

s1

s2 s3

s4

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

xxx 432

xx 31

xxx 421

« Oui »

-Preuves traditionnelles…la réduction de Kearns, Li, Pitt, Valiant, STOC’87

Graphe k colorable k-term-DNF consistante

Propriété:

Le nombre minimal de couleurs

taille minimale de la DNF consistante=

-Preuves traditionnelles…la réduction de Kearns & al

conservation du ratio d’inapproximabilité

-Preuves traditionnelles…le théorème de départ

La colorabilité de graphe pas approximable à moins de

1δ,nδ

Théorème de Feige & Kilian ’96:

ZPPNP

Renvoie Oui, Non, ? (Pr(?)=cst<1)

-Preuves traditionnelles

En utilisant Kearns & al. ’87 + Feige & Kilian ’96, on obtient:

Théorème:

La DNF minimale consistante pas approximable à moins de

1δ,nδ

Problème ?

ZPPNP

-Preuves traditionnelles

Sachant que la colorabilité est (trivialement) approximableà moins d’un ratio non ne peut donc pas obtenir de ratio d’inapproximabilité

n pour la DNF consistante minimale

De plus, on n’obtient rien d’intéressant en replaçantl’hypothèse de complexité par une hypothèse plus forte

On est très loin de démontrer la non apprenabilité de DNFon a tout juste la non-apprenabilité de minuscules sous-classes

et après ?

-Notre solution: réductions « self-improving »

• A) Faire des réductions directement « à l’intérieur » du problème d’apprentissage.

Réduction ordinaire

A BPbs B B B

d fois

LS1 LS2 LS3

• B) S’arranger pour que le ratio d’inapproximabilité augmente « brutalement » avec les réductions

Réduction ordinaire

Pb A

rati

o

B B B B

d fois

conservation

-Notre solution

• C) S’arranger pour que le ratio d’inapproximabilité « explose » en remplaçant l’hypothèse de complexité

Réduction ordinaire

Pb A

rati

o

B

conservationZPPNP ZQPNP

2IZTIMENP

γ

-Notre solution

• D) Résultat principal: le ratio « devient »

…mais la complexité augmente aussi:

)IO( d

)ρΩ( d

-Notre solution

-Notre solutionréduction deKearns & al.

Co

lora

bil

ité

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

LS1

On combine lesobservations

,1xxxxxxxx 4,23,22,21,24,13,12,11,1

,0xxxxxxxx 4,23,22,21,24,13,12,11,1

On combine lesclasses paret-logique

+

LS2

-Notre solution

On ajoute quelques astuces supplémentaires:

On a besoin de graphes très particuliers

On combine en réalité 4 réductions

• Si d est constant:la réduction est encore polynomiale,mais le ratio « explose »

ZPPNP ZPPNP

nδ n

δ

1δ δ

εLS

191ε

γc

1451γ

-Notre solution…conséquences I

• Si d devient polylog

• La réduction est quasi-polynomiale,

• Mais le ratio est « boosté » d’avantage

• Résultat « extrème » (d encore + gd):

2IZTIMENP

γ 2nδ

0δ

-Notre solution…conséquences II

• Le résultat de complexité permetde donner des bornes inférieures sur la

complexité de tout algorithme PAC pour DNF

de montrer la non-apprenabilité de larges sous-classes de DNF

-Notre solution…conséquences III

On est pas loin de démontrer la non apprenabilité de DNF…mais on ne la démontre pas encore

-Parallèle « intéressant »

• Une technique de classification récente extrèmement puissante (Breiman’96) combine les solutions d’algorithmes d’apprentissage modérément fiables,et retourne une nouvelle solution beaucoup plus fiable (Boosting).

-Parallèle « intéressant »

• Notre technique combine les instances de problèmes d’optimisation en apprentissage/classification modérément difficiles,et retourne une nouvelle instance beaucoup plus difficile.

-Conclusion & extensions

• Apprenabilité et approximabilité de DNF=un des problèmes fondamentaux de la théorie de Valiant, conjecturé négatif par Valiant en 1985.

• En 1998, nous avions le ratio d’inapproximabilité le plus important pour DNF (mais pas encore « maximal » !).

Apparemment toujours le + important (Hellerstein ’01)

-Conclusion & extensions

• J’ai utilisé cette technique « self-improving » dans quelques autres cas:– (In)approximabilité de l’erreur sur de

grands ensembles de Clauses de Horn– Difficulté des problèmes de réduction de

données (variables/exemples)– Et d’autres (en soumission)

Un résultat Positif

Un résultat Positif

• Segmentation d’images =

Pixels Arrangement de régions

=

+ +...

Un résultat Positif

• Notre objectif =

& compromis Complexité algorithmique vs qualité statistique

Segmentation par fusion de régions16 pixels=

16 régions 15 régions 14 régions 2 régions

Plan général (résultat Positif)

• +Segmentation d’images & élagage• +Un modèle de génération d’image• +Théorème (utile)• +L’algorithme + analyse de complexité• +Expérimentations• +Conclusion partielle

extensions actuelles

+Segmentation & élagage• Fusion de régions similaire à l’élagage de DT

• Segmentation d’image = (très) larges domaines

Kearns & MansourICML ’97, ’98

statistiquementalgorithmiquementredoutable

&Théoriquement

Mais, en pratiquepetits domaines=pb

+Modèle : génération d’image

• On crée un modèle supposant que

l’image observée est obtenue à partir d’une image « théorique »

• Dans cette image théorique, on peut « observer » la partition idéale en régions (celle qu’on cherche à reconstruire sur la base de l’image observée seulement)

Modèle donne une mesure objective de la qualité de segm.

+Modèle (2)

• Pixel théorique Pixel observé

Q gv.a. Indép./canal, + sommes born. 1 pixel=3 ens. (RGB) de Q v.a. ind., SANS plus d’hypothèse sur les v.a.

+Modèle (3)

• Image théorique Image observée

objectif

+Modèle (4)

• Dans l’image théorique,

• Peut-on reconnaître les vraies régions sur la seule base de l’image observée ?

R vraie région de I*, a {R,G,B},

L’espérance mathématique de a est la même sur R

RR’ vraies régions de I*

L’espérance mathématique diffère pour R,G, ou B

+Théorème

• Concentration des valeurs observées:

Utilisation pour un algorithme ?

+L’algorithme (1)

• Composants suffisants pour un algorithme de fusion de régions:

• Comment concevoir un algorithme fonctionnant sur notre modèle ?

(I) Prédicat de fusion

(II) Un ordre pour tester les fusions

+L’algorithme (2): prédicat

• Le prédicat de fusion= renvoie « Oui » ssi les valeurs observées ne sont pas trop éloignées RGB, à l’aide du théo.:

+L’algorithme (3): ordre

• Supposons qu’on fasse les tests t.q. chaque test dans une vraie rég. soit fait avant tout test entre un de ses pixels et une région adj.

• Alors, à l’aide du théorème 2 et le prédicat, w.h.p. notre segmentation est une sous-segmentation (toute vraie rég. est inclue dans 1 région segmentée).

• Notre solution: on ordonnance les tests en ordre croissant de la plus grande différence parmi (R, G, B), avant les tests de fusion.

+L’algorithme (4): synthèse

1er 2nd

3me

4me

+L’algorithme (5): complexité

• Complexité en espace : presque O(|I|)

• Complexité en temps :

Notre implémentation : O(|I|log|I|)(en moyenne…)

(presque) optimal

Avec un peu de réflexion : O(|I|)optimal

Possible sans effort : O(|I|loglog|I|)

+Expérimentations (1)

• Setup: pour tous les tests (pas de tuning en fonction des images),

• Les images sont segmentées sans aucun prétraitement (débruitage, filtrage, etc.)

I31 32Q

+Expérimentations (2)Image Originale

Segmentation Plus grandes régions

+Expérimentations (3)

Snowy roadHand

+Expérimentations (4)

VesselRock in sea

+Expérimentations (5)

Formula 1Street

+Expérimentations (6)

LighthouseCastle

+Conclusion partielle

a) Complexité en espace quasiment optimale

b) Complexité en temps optimale

f) Comportement robuste/occlusions ?

c) Prédicat utilise des propriétés de concentration de v.a.

d) Algo approxime une sorte d ’algorithme de « maximum de vraisemblance »

e) Erreur (sous-segmentation limitée ?)

Résultats en soumission (+F. Nielsen): OUI (w.h.p.)

Algorithme robuste ?

+Extensions actuelles(+bruit transmission: 5%)

Noc

k, C

VP

R ’0

1

Fel

zens

zwal

b &

Hut

tenl

oche

r, C

VP

R ’9

7

+Extensions actuelles

(+bruit transmission:15%)

+Extensions actuelles

(+bruit transmission:30%)

+Extensions actuelles

(+bruit poivre etsel: 60%)

+Extensions actuelles(+

brui

t tr

ansm

issi

on:

70%

)

+Extensions actuelles

• Contrat avec Sony CS Labs Tokyo

(invité: Février/Mars 2003)

Objectif: poursuite algorithmique / statistique autour de l’idée (vidéo, images sans bords, …)

Encadrement & collaborations

Encadrement

• Thèses (100%):

(09/01): P. Lefaucheur- Boosting robuste

(09/02): J.-C. Atine- Segmentation et suivi

• Conseils:

2 thèses en Géographie

2 mémoires d’Ingénieur Agronome

1 mémoire MST

Collaborations scientifiquesDonnées

Méthode

Théorie

imagesimages

Autre Réd. données Induction

non oui

Théorienon oui

Stéphane LALLICH (U. Lyon 2)Marc SEBBAN (U. St-Etienne)

Tapio ELOMAA (Helsinki U.)Matti KÄÄRIÄINEN (Helsinki U.)Patrice LEFAUCHEUR (Thésard UAG)Babak ESFANDIARI (Carleton U.)Olivier GASCUEL (LIRMM)Pascal JAPPY (Hummingbird)Joël QUINQUETON (LIRMM)Jean SALLANTIN (LIRMM)

Christophe FIORIO(LIRMM)Frank NIELSEN(Sony CSL Tokyo)

Marc SEBBAN(U. St-Etienne)Didier BERNARD(UAG-LPAT)

Autres collaborations

• Industrielles

SACDROP Antilles – Data Mining

Crédit Moderne Antilles – Data Mining

• Recherche (contrats/financements)

SONY CS Labs Tokyo – Algo/Imagerie

NOKIA (Fondation) – Data Mining

• CollectivitésDDAF Martinique – Analyse de données

CIRAD Martinique – Data Mining

Présentation de l’équipe

Présentation de l’équipeTrès très succincte

Le mot-clef à retenir: turn-over !

Première équipe :

Deuxième équipe : TRIVIA

Troisième équipe : GRIMAAG

E.C.: 5

E.C.: 7

E.C.: 19 !

Th.: 0

Th.: 0

Th.: 6

10/98 06/0201/99

Merci pour votre attention !