Click here to load reader

Accès à l'information multimédia classifié crucianm/src/echelle/JMartinez.pdf · PDF file Accès à l'information multimédia classifiée M. Gelgon, J. Martinez, G. Raschia et

  • View
    3

  • Download
    0

Embed Size (px)

Text of Accès à l'information multimédia classifié...

  • 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 principe Couleur = 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.2 Colour = …

    R.1.2 Colour = …

    R.1.2 Couleur = …

    inf (D, O)

    sup (O, I)

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

    n1=O(n.log2n)1/2

    6) Navigation Hypertexte interface 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.log2 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

  • p 1

    p 2

    p i

    p log n

    p 1

    p 2

    p i

    p log n

    0

    5000

    10000

    15000

    20000

    25000

    30000

    50 100 150 256 500 600 700 800 900 1000

    dimension

    tim e

    m ill

    is ec

    min max avg

    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éelles est à poursuivre

    Diapo 1 Diapo 2 Diapo 3 Diapo 4 Diapo 5 Diapo 6 Diapo 7 Diapo 8 Diapo 9 Diapo 10 Diapo 11 Diapo 12 Diapo 13 Diapo 14

Search related