Accès à l'information multimédia classifiée

M. Gelgon, J. Martinez, G. Raschia et al.

Réunion des GDR ISIS et I3 du 9 juin 2009

« Passage à l'échelle dans la recherche d'information multimédia »

Plan● Préliminaires

● Exemples ?● Problèmes● Quelques solutions

● Approches combinant classification & parallélisme● Classification (et parallélisme) (et visualisation)● Parallélisme (et classification)● Classification et parallélisme

● Courte conclusion

Recherche multicritère – multidimensionnelle ? – dans la

« vie quotidienne »● Ressources bibliographiques

– (ex. : « Pour la Science » : revue, année, numéro, rubrique, thème, sous-thème, titre – exact –, auteurs, mots clés)

● Tourisme– (ex. : « Club Med » : date, adultes, enfants, confort, lieu,

âge des enfants, paramètres « d'atmosphère », listes de sports, activités de détente, excursions)

● Véhicules d'occasion● Annuaire des entreprises de France (2 millions)● Catalogues de produits (techniques), etc.

Exemple des véhicules d'occasion(idem pour certaines bases d'images)

● Renault Occasions : jusqu'à 18 critères (quelques dizaines de milliers de véhicules)● Marque, Modèle, 19 Carrosseries (benne, berline,

break, etc.), Énergie (électrique, diesel, essence, éthanol, gaz, sans plomb), Visuel (oui / non), Montant max (0 à 30 000 €), Localisation (code postal), Distance au domicile (5 à 50 km), Kilométrages min et max (0 à 100 000 km), Année min et max (1995 à 2009), Boîte de vitesse (automatique, automatisée, manuelle), Puissance fiscale, Portes (2 à 9), Couleur, Offre spéciale (oui / non), Rétroviseur électrique (oui /non), Airbag (oui / non), Climatisation (oui / non)

● La Centrale : jusqu'à 20 critères (plus de 200 000 annonces)

Quelques difficultés bien connues● Description

● Nombreuses caractéristiques● « Orthogonalité » / corrélations (ex. : modèle → marque) /

hiérarchie● « Inhomogénéité » (ex. : booléens, entiers, énumérations,

« coordonnées »...)● Mises à jour● Recherches

● Spécifications partielles / incomplètes● Disjonctions● Bases importantes

● Visualisation

Quelques solutions (ad hoc)

● Indexation « classique » (monodimensionnelle)● Très insuffisante (arbres-B)● Très particulière

– Bitmaps (mais suffisants pour l' exemple précédent)– Fichiers inverses (adaptables à l'exemple)

● Indexation « spatiale » (multidimensionnelle)● Peu de dimensions (une dizaine, voire quelques

dizaines)● Réduction de la dimensionalité...

Quelques directions de recherche et solutions (partielles)

● Proposition : deux approches à combiner● Classification● Parallélisme

Classification (et visualisation)● Logique floue

● Rendre les descripteurs compatibles● Classifications

● Arborescente– Incrémentale– Linéaire

● Treillis de Galois– Multi-point de vue– Quadratique

● Combinaison– Passage à l'échelle (construction en n.log n, exploration

en temps constant)

Schémas de principeCouleur = <…>Texture = <…>Forme = <…>…

3) Processus de résumé – O(n)2) Extraction des propriétés - O(n)1) Base d’images

……

4) Sélection de n1 résumés

R

R.3R.2R.1

R.1.1 R.1.1 …

R.1.2Colour = <…>…

R.1.2Colour = <…>…

R.1.2Couleur = <…>…

inf (D, O)

sup (O, I)

5) Classification dans le Treillis de Galois – O(n1²)

n1=O(n.log2n)1/2

6) Navigation Hypertexteinterface graphique utilisateur

Parallélisme (et classification)● Hypothèses

● Aucune indexation mais classification ~ uniforme– n = 106, 107

– √n à √n log n classes– rapport 1 à 9 en cardinalités– rapport 1 à 3 en rayon– [0, 1]10...1 000

● Algorithmes de base :– k premiers éléments (n.log k)– voire simple tri (n.log

2 n)

● Grappe de machines– p = log n– placement quasi aléatoire (round-robin)

● Résultat● Passage à l'échelle : recherches k-NN exactes sous-linéaires, en

√n

p1

p2

pi

plog n

p1

p2

pi

plog n

0

5000

10000

15000

20000

25000

30000

50 100 150 256 500 600 700 800 900 1000

dimension

time

mill

isec

minmaxavg

1 000 requêtes sur 50 NN pour n = 107

Parallélisme et classification● Données réparties

● Propagation par rumeur

● Estimation de modèle de classe● combiner des modèles locaux● exploiter des modèles de type « mélange » (Gauss, Student...)● combiner des composantes (Variational-Bayes EM sur paramètres)

● But et résultat● estimation du modèle à faible coût (transport et calcul)● estimation presque aussi bonne (meilleure ?) qu'en local

Conclusion (très partielle)● Le mélange classification / parallélisme donne

de bons résultats● Le passage à l'échelle est asymptotiquement

assuré● La prise en compte de :

● types de descripteurs variés (et similarités associées)

● très grandes collections réellesest à poursuivre