Analyse du livre "Big Data et machine learning" (dernier article, point de vue "computer vision")

Introduction

Cet article est le dernier (sur quatre au total) présentant un livre très récent dédié au Big Data, à la Data Science et notamment au Machine Learning.

Ce dernier article donnera ma vision du livre d'un point de vue de la vision par ordinateur.

Les 3 "V" du Big Data et la vision artificielle

Le spécialiste de la vision par ordinateur se retrouve confronté d'une manière beaucoup plus marquée que n'importe quel "Data Miner" ou "Data Scientist" aux 3 "V" du Big Data :

• Variété: Ici, une image où seuls les pixels peuvent nous donner des informations de plus haut niveau est autrement plus difficile à traiter qu'une table SQL ou même des données au format XML ou JSON

• Volume: Une image couleur au format FullHD (1920*1024) prend 3 à 4 octets par pixel.  Soit lorsque l'image est traitée sans compression en mémoire pour analyse, cela prend 5,6Mo d'emprunte mémoire.  Si nous devons analyser une image (ou sa signature c.a.d un résumé) de manière naïve dans une vidéo FullHD de 2 heures (2h*3600sec*24image/sec) soit 172 800 images, cela représente 945Go. Bien sûr, on peut analyser plus intelligemment, cependant, certains descripteurs d'une image sont plus volumineux que l'image elle-même (surtout lorsqu'on utilise les points d'intérêts voir la 2ème illustration) 

Exemple de point d'intérêt SIFT (vecteur à 128 dimensions)
Crédit Wikimedia CC by 2.0

A titre d'exemple dans cette petite image à gauche (320*288 en JPG de 56Ko) 

on a 2128pts d'intérêts d'une taille de 128 dimensions soit en mémoire RAM ~290Ko soit plus de 5 fois la taille JPG) voir l'image de droite indiquant les points d'intérêts en rouge.

à gauche, l'image originale, à droite les points d'intérêts repérés
où chaque point d'intérêt est une donnée à 128 dimensions

• Vitesse:  En vision par ordinateur, certains traitements demandent d'être traités en temps réel (par exemple la réalité augmentée ou la vision des robots). Il faut donc en général, analyser l'image en moins de 33 millisecondes (1 seconde divisée par le nombre d'image seconde de la caméra, soit 30ips d'où 1000/30).

La malédiction de la dimension, un mal nécessaire en vision artificielle

Autre point où le spécialiste en vision artificielle va plus loin que les Data Miner/Scientist, il manipule de multiples données avec des dimensions supérieures à 10 très souvent :

• Les point d'intérêts sont des tableaux(vecteurs) contenant entre 32 à 128 dimensions et on peut facilement avoir plus de 300 points d'intérêts par image (en fait plus l'image est grande, plus elle en aura)

  

  Descripteur de point d'intérêt SIFT à 128 dimensions prenant en compte
  des informations sur les pixels voisins à de multiple échelle de l'image.
  Crédit par Indif - Wikimedia - CC BY-SA 3.0

• La signature sur les couleurs d'une image (dans sa globalité) peuvent prendre entre 32 à 216 dimensions (on parle d'histogramme de couleur) 

Le vrai "machine learning"

Avec ces notions en tête, on comprendra que le "Machine Learning" abordé dans le livre fera gentiment sourire le spécialiste en vision par ordinateur qui pourra conseiller le livre à toute personne ne connaissant pas son travail et les notions qu'il doit pratiquer.

Cependant, en vision par ordinateur, le "machine learning" prend vraiment tout son sens.  On ne travaille qu'avec des données non structurées auxquelles il faut trouver du sens pour en faire de la classification ou de la prévision.

Pour s'en convaincre, voici des liens vers l'API OpenCV permettant de faciliter la vision par ordinateur:

• Sur le pré-traitement des données (notamment les filtres) : http://docs.opencv.org/modules/imgproc/doc/filtering.html
• Sur les algorithmes de Machine Learning : http://docs.opencv.org/modules/ml/doc/ml.html

Toujours en parlant d'apprentissage, aucun référence à l'apprentissage par renforcement n'est indiquée dans l'ouvrage. Pourtant, ce type d'apprentissage qui prend en compte le feedback de l'utilisateur est assez fréquent en "Machine Learning" pour l'analyse d'images (mais également utile pour réduire le fossé sémantique qui est la différence entre les descripteurs "bas niveau" de l'image et sa représentation sémantique).

Machine Learning et 64 dimensions ou plus

Comme le spécialiste en vision artificielle ne peut pas tout réduire à 2 ou 3 dimensions et faire des analyse en composante principale (ACP) à tout va, il doit être plus malin qu'un Data Scientist / Miner.

Pour continuer à travailler avec 64 dimensions ou beaucoup plus, il faut améliorer les algorithmes existants et la façon de stocker/rechercher les données.

Techniques d'indexation multi-dimensionnelles:

Les bases de données relationnelles reposent sur des données à une dimension (on n'a des index que sur un seul entier/flottant d'une colonne de la table SQL). Le type d'index le plus approprié pour retrouver des valeurs dans un intervalle est l'arbre B+ qui est la référence de nombreux SGBDR.

En augmentant à 3 dimensions il faut oublier l'arbre B qui commence déjà à montrer ces limites, on lui préférera le Kd-tree ou un octree.

Mais dès qu'on dépasse 4 dimensions, les algos classiques s'écroulent vite en pertinence et temps de traitement. D'autres structures d'arbres existent pour indexer des données à forte dimensions :

• R-tree : reprend le principe des octree & kd-tree mais en ayant un système de zone de regroupement de données locales (ex : cube pour des données en 3D) avec possibilités de recoupement entre zones.
• M-tree : reprend le principe d'un arbre B mais avec des calculs de distances basés sur des métriques (permettant de travailler avec des données non numériques).

Pour aller encore plus vite car l'analyse d'image le permet, on peut indexer de manière approximative :

• VA-File (Vector Approximation) (PDF) Ici, l'idée est d'affecter un index binaire (ex:  0010001) en découpant l'espace où se trouvent les données. Cela reprend un peu le système de hachage où l'index est prévu pour tenir en mémoire RAM et donc de pouvoir stocker facilement et accéder rapidement aux vecteurs tout en permettant une recherche approximative des k plus proches voisins car affectés localement à priori au même index. Dans un second temps, on peut faire une recherche plus précise en regardant sur disque les données exactes des points associées à la "page" indexée par un numéro binaire unique.

Exemple de VA File.  Credit SCL

• LSH (Locality Sensitive Hashing) où l'idée est que des points proches en terme de coordonnées multi-dimentionnelle aient la même signature de hachage (et facilite ainsi le regroupement et la recherche des k plus proche voisin).

Crédit TU-Berlin

Pour info, des index existent aussi dans les bases NoSQL mais se limitent toutes à un ArbreB. Donc aucune base NoSQL ne peut correctement contenir des données multimédias.

Cependant, du côté des SGBDR "classiques", il faut surveiller les index de type GIST qui peuvent généraliser le principe d'index.

Algorithmes améliorés:

L'algorithme des k plus proches voisins et celui du k-means sont très couramment utilisés en vision par ordinateur.

Il existe des variantes des KNN et K-means qui vont utiliser les index R ou M-tree pour accélérer la recherche des plus proches voisins.

On trouvera aussi des variantes utilisant les index approximatifs. Exemple à lire ici.

Grâce à ce genre d'améliorations, les données à dimensions multiples n'effraient plus un spécialiste en vision artificielle alors que cela laissera un mauvais souvenir à un Data Scientist et un Data Miner.

Pour aller plus loin 

Toujours en analyse d'images, il est intéressant de suivre les projets autour de la robotique comme PCL (Point Cloud Library). On y trouve des techniques :

• sur la géométrie et l'indexation de nuage de point 3D (octree et Kd-tree)
• la gestion des points d'intérêts
• l'algo RANSAC pour pré-traiter les données. Il permet d'éliminer les "outliers" (valeurs extrêmes ou aberrantes) pour aider à la fusion d'images (voir la 2ème image ci-dessous).

Exemple d'ensemble de points d'intérêts ayant été utilisés pour reconstituer en 3D des objets et la géométrie du monde réel
Crédit PCL (CC By CA 3.0)

Exemple de fusion d'images en mode Panorama (image stitching) grâce aux points d'intérêts et à l'algo RANSAC
Crédit Wikimédia par Noso CC By SA 3.0

Conclusion

Le lecteur qui aura eu le courage de lire les 4 articles l'aura compris, le livre est une très bonne introduction, suffisamment abordable pour servir de base à un travail commun entre différents acteurs dont certains n'ayant jamais entendu parler de Big Data et encore moins de Machine Learning.

Ne faisant que 220 pages, les auteurs ont fait des choix sur les sujets à présenter cependant l'essentiel y est.

Avant de s'auto-proclamer "Data Scientist" après la lecture du livre, celui-ci reste néanmoins une invitation à pousser encore plus loin la porte de la curiosité et de plonger dans des notions approfondies dans les domaines suivants :

• Statistique et probabilité
• Data Mining (et aussi les réseaux de neurones au sens large)
• Text Mining et analyse d'opinion
• Machine Learning en Vision artificielle (ou en multimédia en général)

J'espère au travers des 3 derniers articles vous avoir donner envie de creuser par vous-même les aspects abordés et de vous en faire votre propre opinion.