Complexité et Classification Quelques aspects algorithmiques de problèmes de classification...

Complexité et Classification

Quelques aspects algorithmiques de problèmes de

classificationRichard NockDSI-GRIMAAG

Université Antilles-Guyane,

Campus de Schoelcher,

Schoelcher, Martinique, France

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

Background

• Ingénieur Agronome (1993)• DEA Informatique (1993)• Doctorat Informatique (1998)

directeur: O. Gascuel• Mcf UAG Guadeloupe (1998-2000)• Mcf UAG Martinique (2000-)

Thèmes de recherche actuels

Algorithmes d’apprentissage/classification

Théorie

(Complexité, stats/probas)

Analyse d’images

Thèmes de recherche actuels

NP-Complétude

Résultats d’inapproximabilité « appliqués » en ML/C

Concentration de v.a.

Bornes d’erreur sur algorithmes d’apprentissage+

-

Résumé

Apprentissage et classification

Complexité algorithmique

Application à l’apprentissage

Conclusion

Apprentissage et classification

Introduction

Apprendre ?

• 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

Apprendre ??

• Qu’apprends-t’on d’un point de vue informatique ?

• Détail des contraintes du modèle de Valiant ?

Apprentissage et classification

Le modèle PACde L. Valiant

Observations et Exemples

Domaine

Concept

Exemples

y

x

<(x,y), >

Un exemple

« cible »

tirés selon D

2 classes

Grandes étapesy

x

1- Collecte des exemples

2- Construction d’une hypothèse

3- Qualité de l’hypothèse ?

Evaluationy

x

A

B

C

Prob. Err.=BA

D(x)

Problème ?

?

Evaluationy

x

1- Pas d’accès à Prob. Err. !

2- Uniquement Freq. Err.

3- Comment « assurer » qualité ?

Problème !

Freq. Err. =04- Et si distrib. quelconque ??

5- Et si distrib. inconnue ???

Solution: modèle PAC Iy

x

1- Requérir Prob. Err. limitée

avec une forte probabilité

2- Sachant la distribution

… mais fixe

quelconqueinconnue

3- Tirer suffisamment d’exemples

Modèle PAC II

1- A partir de là, comment trouver la meilleure formule ?

Indép. du nb d’exemples

2- Il suffirait de disposer d’un algorithme énumérant

toutes les formules possibles

Problème ?

3- Enumération souvent exponentielle

donc inutilisable

Problème !

Solution

1- Exiger que l’algorithme fonctionne rapidement

2- Exiger un algorithme polynomial

Rectangles en 2D: facile

Modèle de Valiant (1984)

• Une classe de représentation de concepts C est apprenable au sens du modèle PAC ssi il existe un algorithme A vérifiant les deux conditions suivantes:

Modèle de Valiant

• cC, A a accès à un Oracle rétribuant des exemples selon c et une distribution D inconnue, quelconque, mais fixée, et, étant donnés deux paramètres 0<,<1, renvoie une hypothèse h de C telle que

δεchPrPr

c(x)h(x)D(x)

Modèle de Valiant

• A fonctionne en temps polynomial

cn,,11p ,,Taille du concept

cible# Variables de description

Confiance

Fiabilité

Prouver que C n’est pas PAC

• Trop d’exemples nécessairespour satisfaire à la première condition

• Temps de calcul rhédibitoirepour satisfaire à la deuxièmecondition

Complexité algorithmique

Introduction

Les problèmes de décision

Problème de décision:

Instance

Question

Ensemble d’exemples

Formule de C consistante ?

? Oui

Les problèmes de décision

Problème de décision:

Instance

Question

Ensemble d’exemples

Formule de C consistante ?

?Non

Classes de complexité

?

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

NP

NPP

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

P

Hypothèse(s) fondamentale(s)

NPNP

P

P

=P +temps f(I)O

P=

f(I)DTIME

Ic

0cDTIME

Hypothèse(s) fondamentale(s)

NPNP

P

QP

QP

QP=

II

0c

logDTIMEc

QPP…et bien sur

Hypothèse(s) fondamentale(s)

NPNP

PQP

2IDTIMEQPP

γ…et bien sur

2IDTIME

2IDTIME

0γ…pour un

Hypothèse(s) fondamentale(s)

NP

PQP

…et bien sur

2IDTIME

2IDTIMENP 2

IDTIME

???…Qu’y a-t’il ici ?

Problèmes « difficiles »

instances

A B

solutionsOui Oui

poly

Un est Poly Tous sont Poly

NP-Complets

Hyp. de comp. Tous difficiles !

Complexité algorithmique

Décision etoptimisation

Problème d ’optimisation

Définition:

Instance

Ens. Solutions

Ensemble d’exemples LS

Formules de C consistantes avec LS

Fonction de Coût Taille de la formule

Objectif Trouver une sol. min. (max.) la fonct. de coût

Décision vs Optimisation:

La plupart des problèmes de décision admettent (au moins) une version d ’optimisation « naturelle »

Problème d ’optimisation

Problèmes d ’optimisation difficiles

Existence ?

Procédure ?

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

Difficulté d ’approximation I

Prob. déc. NP-Complet

Oui

Non

Prob. Minimisation

Coût des instances

(...)

(...)

Réd

uct

ion

« gap »

Difficulté d ’approximation II

Hypothèse: le problème de minimisation

d’approximation de ratioρadmet un algorithme

Comment arriver à une contradiction ?

Difficulté d ’approximation II

Oui

Non(...)

(...)

Alg

ori

thm

e h

yp

oth

éti

qu

ed

 ’ap

pro

xim

ati

on

Instances Solutions

Etapes A B C

Oui

Non

On

réso

ud

le p

rob

lèm

e N

P-C

om

ple

t !!

Difficulté d ’approximation III

Si il existe une réduction de temps polynomial depuis un

prob. NP-Complet vers un problème de minimisation, t.q.

Les instances « Oui » sont transformées en inst. de coût

(...)Les instances « Non » sont transformées en inst. de coût

(...)

Alors, sous l ’hypothèse PNP le prob. de minimisation

n ’est pas approximable à moins de

Remplacement de P par QP

Si on remplace l ’exigence polynomiale par une exigence

Quasi-Polynomiale

Temps de la réduction

Temps de l ’algorithme d ’approximation hypothétique

Alors, sous l ’hypothèse QPNP le prob. de minimisation

n ’est pas approximable à moins de

Définition de l ’approximabilité

Pourquoi remplacer P par QP ?

Avantage direct:

Les ratios d ’inapproximabilité peuvent être bcp + grands

Hypothèse bcp plus forte, et donc « moins » réaliste

Inconvénient:

PNP devient

Avantage indirect:

On peut aussi remplacerQP par

2IDTIME

…et (espérer) des ratios encore + grands !

QPNP

Application à l ’apprentissage

Réductions« traditionnelles »

Preuves directes

• On part d’un problème difficile (NP-Complet) traditionnel

• On construit une instance difficile d ’un problème de classification, formulé comme un problème de décision, ou d ’optimisation

Exemple

• Kearns, Li, Pitt, Valiant (STOC ’87++)

• Problèmes:Consistance (DNF):

Instance

Question

Ensemble d’exemples, entier k>0

k-term-DNF consistante ?

Optimisation (DNF):

Instance

Ens. Solutions

Ensemble d’exemples

DNF consistantes

Fonction de Coût Nb de monomes de la DNF

(k-term-)DNF vvv n21

,...,,

xx 11, xx 22

, xx nn,

Un monome (Booléen): conjonction de littéraux:

xxx 871

Une DNF: disjonction de monomes:

xxxxx 72871

Une k-term-DNF: disjonction d ’au plus k monomes

2 classes: exemples positifs et négatifs(10110110,1) (0101010,0)

Représentation du problème

,0xxxx 4321

,1xxxx 4321

,1xxxx 4321

LS 2-term-DNF cons. ??

xxx 421

« OUI »

La réduction

Instance

Question

G=(X,E), entier k>0

k-coloration de G ?

k=3

« Oui »

Instance

Question

Ech. d’ex., k>0

k-term-DNF ?

,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 »

La réduction

Propriété:

Le nombre minimal de couleurs

taille minimale de la DNF consistante=

Résultat d’inapproximabilité

Oui

Non

Colorabilité minimale

Nombre de couleurs

(...)n

(...)

1, n

Réd

uct

ion

« gap »

SAT

Feig

e,

Kili

an

 ’9

6

Théorème

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

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

Commentaires

Sachant que la colorabilité est (trivialement) approximableà un ratio

On ne peut donc pas obtenir de ratio d ’inapproximabilité

n

De plus, on n ’obtient rien d ’intéressant en replaçant

npour la DNF consistante minimale

l ’hypothèse de complexité par une hypothèse plus forte

Application à l ’apprentissage

Réductions« self-improving »

Notre Solution

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

Réduction ordinaire

A B

Problèmes

B B B

d fois

Notre Solution

• 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

conservation

ZPPNP ZQPNP

2IZTIMENP

Propriété

• La complexité de la réduction est

• Le ratio d’inapproximabilité est en

dIO

dO

Application à l ’apprentissage

SynthèsePour DNF

La réduction II

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

,1xxxx 4321

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

,0xxxx 4321

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

+

La réduction II

On ajoute quelques astuces supplémentaires:

On a besoin de graphes très particuliers

On combine en réalité 4 réductions

Conséquence I

• Si d est constant:La réduction est toujours polynomiale,Le ratio « explose »n

ZPPNP

n1

LS

191

c

1451

1

ZPPNP

Conséquence II

• 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

Conséquence III

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

sur le complexité de tout algorithme PAC pour DNF

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

Application à l ’apprentissage

ProgrammationLogique Inductive

Application II: ILP

• ILP= Programmation Logique Inductive

• Formalisme puissant de représentation de connaissance

• Utilisation de Clauses de Horn plus ou moins contraintes, en présence de Background Knowledge

Application II: ILP

R)Z,(X,...(X)Y)(X,p(X) pppn21

Objectif:

…et réaliser le moins d’erreurs !

const),...(const,pBKk

...)'p(c',)p(c',p(c)E ...)'p(k',)p(k',p(k)E-

En utilisant:

Couvrir le plus d’exemples positifs,Couvrir le moins d’exemples négatifs…

Application II: ILP

Problème:

Instance

Ens. Solutions

Fonction de Coût

Ens. d’ex. LS, poids w/chaque exemple

NomWapprox(g(.)-function-free-Horn-Clauses)

g(.)-function-free-Horn-Clauses

))()(,(

)(xcxhLSx

xw (erreur de h sur LS)

Application II: ILP

Théorème(s):

constante 0, dd PNP

Valeur de g(.) Ratio d’inapprox. hypothèse

polylog ngd

log2

(.)

nnd

log QPNP

Sans utiliser les réductions « self-improving »

En utilisant les réductions « self-improving »

Application à l ’apprentissage

Sélection deVariables/Prototypes

Application III: Sélection de variables/prototypes

Blum’94: « nearly all results in machinelearning deal with problems ofseparating relevant from irrelevantinformation in some way »

Question: difficulté algorithmique de latâche?

Application III: Sélection de variables/prototypes

variables

exemples

1) enlève une variable

2) enlève un exemple

classe

Application III: Sélection de variables/prototypes

#Variables

#Exemples

Mesured’information

Approximationd’un concept

Contrainte

Fct. de coût

Réductions « self-improving »

Application III: Sélection de variables/prototypes

Exemples/Mesure d’information:Fonction f permissible:

f: [0,1][0,1]f symmétrique / x=1/2f(1/2)=1, f(0)=f(1)=0f concave

x)x)log(1(1xlogxH(x) Entropie bin.x)-4x(1G(x)x)-x(12A(x)

Critère de Gini

Critère de Boosting

Application III: Sélection de variables/prototypes

Exemples/Mesure d’information:

))(p(LS

LSLS

))(p(LSLS

LS(p(LS))LS)(v, 0v

0v1v

1v

I ffff

Quantité « d’information » d’une variable

Objectif (informel):

Réduire le nombre d’exemples en assurant

que les variables informatives le restent

Application III: Sélection de variables/prototypes

Théorème(s):

0εε)logn,(1ρ IloglogI

DTIMENPRatio d’inapprox. hypothèse

Sans utiliser les réductions « self-improving »

En utilisant les réductions « self-improving »

0εn,ρ logε)loglogn(1

I

loglogIDTIMENP

0δ,ρ nδ QPNP

0εε)logn,-(1 0εε)logn,-(1

0εε)logn,-(1

Application III: Sélection de variables/prototypes

#Variables

#Exemples

Mesured’information

Approximationd’un concept

0δ,n2loglogn

δ

0εε)logn,-(1

0δ,nδ 0δ,n

δ

0δ,δ n

Contrainte

Fct. de coût

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.

Application à l ’apprentissage

Autresrésultats

Autres résultats de complexité

• Kohavi et al.’98: l’erreur n’est pas le meilleur critère à optimiser pour le Data Mining.

• Utilisation de nouveaux critères (courbes ROC, contraintes, etc.).

• Quelle est la difficulté algorithmique de ces nouveaux critères ?

Autres résultats de complexité

• En utilisant un sous-ensemble des clauses de Horn, on a montré

que ces critères entrainent une difficulté algorithmique considérable (même si on autorise la multiplication arbitraire des clauses de Horn).

que l’optimisation de l’erreur seule est « facile » en comparaison.

Publications directement concernées

• International Conference on Inductive Logic Programming (ILP’98, ed. Springer Verlag)

• International Symposium on Algorithms and Computation (ISAAC’98, ed. Springer Verlag)

• International Conference on Algorithmic Learning Theory (ALT’99, ALT’00, ed. Springer Verlag)

• …et d’autres indirectement concernées.

Conclusion

• 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 encore très loin de l’ « optimum » !).

ConclusionLes problèmes d’apprentissage semblent être de bons candidats aux réductions self-improving.…mais l’intérêt des résultats négatifs reste limité en apprentissage.

…heureusement, je développe aussi des résultats positifs sur quelques problématiques de classification (voir diapositive suivante)

Merci pour votre attention !

dans R.Nock, « Fast and Reliable Region Merging inspired byDecision-Tree Pruning »

IEEE Int. Conf. on Computer Vision and Pattern Recognition(Décembre 2001)