Testwiki:L'algèbre linéaire numérique randomisée (Big data)

L'algèbre linéaire numérique randomisée (RandNLA) est un ensemble de techniques d'algèbre linéaire pour la résolution des problèmes d'analyse de données à grande échelle, et plus précisément, la réduction des grandes matrices de données. L'aléatoire dans l'algèbre linéaire conduit à des algorithmes plus rapides. Afin de réduire les grandes matrices de données tout en préservant le maximum d'informations, deux méthodes principales sont utilisées: L'échantillonnage des matrices et la projection aléatoire.

Du point de vue fondamental, RandNLA a ses racines dans l'informatique théorique (IT), liens profonds avec les mathématiques (analyse convexe, théorie des probabilités, théorie de l'intégration métrique) et les mathématiques appliquées (calcul scientifique, traitement du signal, algèbre linéaire numérique). Du point de vue applicatif, RandNLA est un nouvel outil essentiel pour l’apprentissage automatique, les statistiques et l’analyse de données.

Introduction

L'échantillonnage aléatoire est devenu un outil essentiel dans la résolution de problèmes matriciels massifs. Les différentes études actuelles mettent en évidence les avancées récentes en matière d’algorithmes pour l’algèbre linéaire numérique, qui découlent de la technique de l’esquisse linéaire. Pour la régression linéaire, un ensemble de lignes de données peut être sélectionné de manière aléatoire pour se rapprocher d'une matrice de données petite, ce qui améliore considérablement le temps de traitement. Pour les garanties de performance théoriques, chaque ligne doit être échantillonnée avec une probabilité proportionnelle à son score de levier statistique. Malheureusement, les scores de levier sont difficiles à calculer. Une alternative simple consiste à échantillonner les rangées uniformément de manière aléatoire. Dans le cas toujours d’une matrice, on la compresse d’abord en une matrice beaucoup plus petite par exemple en la multipliant par une matrice (généralement) aléatoire dotée de certaines propriétés. Une grande partie du calcul coûteux peut alors être effectuée sur une matrice plus petite, accélérant ainsi la solution du problème initial. De tels problèmes sur des ensembles de données volumineux, sont souvent trop lents pour avoir une valeur pratique. En utilisant par exemple la multiplication matricielle naïve ou la sélection de colonnes / lignes, la résolution des équations normales pour les moindres carrés prendrait au moins n.d² temps.

La projection aléatoire (PA) a récemment apparue comme une puissante méthode de réduction de la dimensionnalité. Les résultats théoriques indiquent que la méthode préserve assez bien les distances ; Cependant, les résultats empiriques sont clairsemés. Des résultats expérimentaux seront présentés sur l’utilisation de la projection aléatoire en tant qu’outil de réduction de la dimensionnalité dans un certain nombre de cas où la dimension des données conduirait autrement à des calculs fastidieux. Les domaines dans lesquels on applique le principe de projection sont le traitement d'images à la fois bruitées et non bruitées et la récupération d'informations dans des documents texte. Nous montrons que la projection des données sur un sous-espace de dimension inférieure aléatoire donne des résultats comparables à la réduction de la dimensionnalité conventionnelle des méthodes telles que l'analyse en composantes principales (ACP) : la similarité des vecteurs de données est bien préservée sous projection aléatoire. Cependant, l’utilisation de projections aléatoires est un calcul nettement moins coûteux que, par exemple, l’analyse en composantes principales. L’utilisation d’une matrice aléatoire fragmentée donne également des économies de calcul supplémentaires en projection aléatoire.

Dans de nombreuses applications d’exploration de données, la grande dimension des données limite le choix des méthodes de traitement des données. Ces domaines d'application comprennent l'analyse des données sur les paniers de marché, les documents texte, les données d'image, etc. Dans ces cas, le caractère dimensionnel est important en raison, respectivement, d'une richesse de produits alternatifs, d'un vocabulaire étendu ou de l'utilisation de grandes fenêtres d'image. Une manière statistiquement optimale de réduction de la dimensionnalité consiste à projeter les données sur un sous-espace orthogonal de dimension inférieure qui capture autant de variation des données que possible. Le meilleur moyen (au sens moyen du terme) et le plus largement utilisé est l’analyse en composantes principales (ACP) ; Malheureusement, le calcul des jeux de données de grande dimension est assez coûteux. Une méthode de réduction de la dimensionnalité simple en termes de calcul qui n'introduit pas de distorsion significative dans l'ensemble de données serait donc souhaitable.

En projection aléatoire (PA), les données originales de grande dimension sont projetées sur un sous-espace de plus petite dimension en utilisant une matrice aléatoire dont les colonnes ont des longueurs unitaires. La PA s'est révélée être une méthode de calcul efficace, mais suffisamment précise, pour la réduction de la dimensionnalité de l'ensemble de données de grande dimension. Bien que cette méthode ait suscité beaucoup d’intérêt, les résultats empiriques sont clairsemés.

Des résultats expérimentaux sur l’utilisation de la PA existent en tant qu’outil de réduction de la dimensionnalité sur des ensembles de données (image et texte) d’une grande dimension. Dans les deux domaines d’application, la projection aléatoire est comparée aux méthodes bien connues de réduction de la dimensionnalité. Malgré la simplicité de calcul de la projection aléatoire, elle n'introduit pas de distorsion significative dans les données.

Les ensembles de données utilisés sur lesquels sont appliqués ces méthodes sont de nature très différente. Des images qui sont présentées sous forme des matrices de valeurs de luminosité de pixels, dont la distribution est généralement approximativement gaussienne: symétrique et en forme de cloche. Des documents textes qui sont présentées dans un espace vectoriel ^[1], chaque document constituant un vecteur de dimension $d$ où $d$ est la taille du vocabulaire. Le i-ème élément du vecteur indique la fréquence du i-ème terme de vocabulaire dans le document. Les données de document sont souvent très rares ou surchargées: seuls certains termes du vocabulaire sont présents dans un document et la plupart des entrées du vecteur de document sont nulles. De plus, les données de document ont une distribution asymétrique, car les fréquences de terme ne sont pas négatives. La projection aléatoire fonctionne comme un outil de réduction de la dimensionnalité dans le contexte de ces deux domaines d’application très différents.

Des résultats expérimentaux sont présentés sur des images corrompues par le bruit, et indiquent que la projection aléatoire n’est pas sensible au bruit impulsif. La projection aléatoire est donc une alternative prometteuse à certaines méthodes existantes de réduction du bruit (filtrage médian, par exemple).

Historique

Matrices

Les matrices fournissent une structure naturelle avec laquelle on modélise des données. Par exemple une matrice $A \in R_{m * n}$ donne une vue globale sur le comportement de $m$ objets, où chacun entre eux est décrit par $n$ variables.

D’où l’intérêt des mathématiciens de plus développer, dans la théorie et la pratique, des algorithmes qui facilitent les traitements effectués sur les matrices, en particulier l’utilisation de la randomisation.

L'algèbre linéaire numérique randomisée

L'algèbre linéaire numérique randomisée (RandNLA) est un domaine de recherche interdisciplinaire qui exploite la randomisation en tant qu’une ressource de calcul pour développer des algorithmes améliorés pour les problèmes d'algèbre linéaire à grande échelle.

D’un point de vue historique, RandNLA a une longue histoire dans l’analyse statistique de données statistiques à grande échelle :

La méthode des moindres carrés (LS) est due à Gauss, Legendre et à d’autres, est utilisée au début des années 1800 pour ajuster des équations linéaires afin de déterminer les orbites planétaires.
Les approximations de bas rang basées sur l'analyse en composantes principales (ACP) : sont dues à Pearson, Hotelling et autres, et utilisés au début des années 1900 pour les données exploratoires analyse et analyse prédictive.

Ces méthodes, ainsi que les méthodes associées, présentent un intérêt pour de nombreuses raisons, mais surtout s'il y a du bruit ou du caractère aléatoire dans les données, car le but d’utiliser l’analyse en composantes principales c’est que cette analyse nous permet de capturer le signal et de supprimer le bruit.

Avec l’arrivée des ordinateurs dans les années 50, il est devenu évident que même l’application de nombreux algorithmes a des problèmes bien posés ont très mal fonctionnaient en présence de la précision finie utilisée pour représenter des nombres réels. Ainsi, une grande partie des premiers travaux d’informatique se sont concentrés sur la résolution d’approximations discrètes pour résoudre des problèmes nucléaires continus. Et donc l'algèbre linéaire est devenue le domaine des mathématiques appliquées, et une grande partie de la théorie et de la pratique de l'informatique est devenue discrète et combinatoire; et il s'est concentré sur applications commerciales. Cela a conduit à des codes de haute qualité dans les années 1980 et 1990 (LINPACK, EISPACK, LAPACK, ScaLAPACK) qui restent largement utilisés aujourd'hui.

Pendant ce temps, Turing, Church et d’autres ont commencé l’étude du calcul proprement dit. Il est devenu évident que plusieurs approches apparemment différentes (la théorie de la récursivité et le λ-calcul) définissaient la même classe des fonctions ; et cela a conduit à croire que le concept de calculabilité est formellement capturé dans une manière qualitative et robuste par ces trois processus équivalentes, indépendantes des données d'entrées.

Une perspective historique : maintenant et à l'avenir

Récemment, une convergence de ces deux perspectives très différentes :

Motivé par des applications scientifiques, Internet, des médias sociaux, financiers, etc.

Le calcul en soi est nécessaire mais très insuffisant.

La plupart des gens veulent avoir un aperçu et/ou faire des prédictions à partir des données qu’ils génèrent pour faire des réclamations en aval sur le monde.

Au cœur de ces développements de RandNLA, on trouve notamment :

Caractère aléatoire dans les données et dans l'algorithme.

Continuité (mathématiques) versus discret (informatique).

Algorithmes de pire cas versus mesures de complexité spécifiques à un problème.

Applications scientifiques versus applications commerciales.

Bon "atome d'hydrogène" pour considérer les fondements algorithmiques et statistiques de l'analyse de données à grande échelle moderne.

Principe de la Projection Aléatoire (PA)

En projection aléatoire, les données de dimension $d$ sont projetées dans un sous-espace de dimension $k$ $(k ≪ d)$ , à l'aide d'une matrice aléatoire $R_{k * d}$ dont les colonnes ont des longueurs unitaires. En utilisant la notation matricielle où $X_{d * N}$ est l’ensemble initial de $N$ observations de dimension $d$ , la formule suivante est la projection des données sur un sous-espace de dimension $k$ inférieure :

X_{k * N}^{R P} = R_{k * d} . X_{d * N}

$(1)$

L’idée clé de la cartographie aléatoire découle du lemme de Johnson-Lindenstrauss ^[2]:

«Si des points dans un espace vectoriel sont projetés sur un sous-espace choisi au hasard, de dimension suffisamment élevée, les distances entre les points sont approximativement conservées.»

La projection aléatoire est très simple en calcul, il suffit de former la matrice aléatoire

R

et projeter les données de la matrice

X_{d * N}

en

k

dimensions, on se retrouve avec une complexité d'ordre

O (d k N)

, et si la matrice de données

X

est clairsemé avec environ

c

entrées non nulles par colonne, la complexité est donc d'ordre

O (c k N)

. Proprement parler, l’équation

(1)

n'est pas une projection car

R

n'est généralement pas orthogonal. Un mappage linéaire tel que

(1)

peut causer des distorsions importantes dans l'ensemble de données si

$R$

n'est pas orthogonal. Sauf qu’orthogonaliser

$R$

est malheureusement coûteux en calcul. Au lieu de cela, nous pouvons nous appuyer sur un résultat présenté par Hecht-Nielsen ^[3]:

« Dans un espace de grande dimension, il existe un nombre beaucoup plus grand des orthogonales que des directions orthogonales. Ainsi, les vecteurs ayant des directions aléatoires pourraient être suffisamment proches d’orthogonal, et de manière équivalente,
$R^{T} R$
se rapprocherait d’une matrice d’identité. »

Lorsqu’on compare les performances de la projection aléatoire à celles d'autres méthodes de réduction de dimension, il est instructif de voir comment la similarité de deux vecteurs est faussée dans la réduction de dimension. La mesure de la similarité des vecteurs de données se fait soit par leur distance euclidienne, soit par leur produit intérieur. Dans le cas de d'une image, la distance euclidienne est une mesure de similarité largement utilisée. Les documents texte, en revanche, sont généralement comparés en fonction du cosinus de l'angle entre les vecteurs de document ; si les vecteurs de document sont normalisés à la longueur d'unité, cela correspond au produit interne des vecteurs de document.

Nous écrivons la distance euclidienne entre deux vecteurs de données $x_{1}$ et $x_{2}$ dans l'espace de grande dimension d'origine sous la forme $‖ x_{1} - x_{2} ‖$ . Après la projection aléatoire, cette distance est approximée par la distance euclidienne mise à l'échelle de ces vecteurs dans l'espace réduit :

\sqrt{\frac{d}{k}} . ‖ R x_{1} - R x_{2} ‖

(2)

où

d

est la dimension originale et

k

la dimension réduite de l'ensemble de données. Le terme d'échelle

\sqrt{\frac{k}{d}}

prend en compte la réduction de la dimension des données : selon le lemme de Johnson-Lindenstrauss ^[4]:

«La norme attendue d'une projection d'un vecteur unitaire sur un sous-espace aléatoire par l'origine est
$\sqrt{\frac{k}{d}}$
.»

Le choix de la matrice aléatoire

R

est l’un des principaux points d’intérêt. Les éléments

r_{i j}

de

R

sont souvent distribués, mais ce n'est pas le cas. Achlioptas a récemment montré que la distribution gaussienne peut être remplacée par une distribution plus simple, telle que :

r_{i j} = \sqrt{3} . {\begin{matrix} + 1, & avec une probablilité \frac{1}{6} \\ 0, & avec une probablilité \frac{2}{3} \\ - 1, & avec une probablilité \frac{1}{6} \end{matrix}

(3)

En fait, pratiquement toutes les distributions de variance unitaire moyenne nulle de

r_{i j}

donneraient une cartographie qui satisfait toujours le lemme de Johnson-Lindenstrauss. Le résultat d’Achlioptas se traduit par des économies de calcul supplémentaires dans les applications de base de données, car les calculs peuvent être effectués à l’aide des méthodes arithmétiques entières. Dans les expériences expliquées ci-dessous, des matrices aléatoires distribuées gaussiennes et des matrices creuses (3) sont utilisées, afin de montrer que le résultat théorique d’Achlioptas a bien une signification pratique. Dans le contexte des résultats expérimentaux, nous ferons référence à RP lorsque la matrice de projection est distribuée gaussienne et PAC lorsque la matrice est clairsemée et répartie selon (3). Sinon, le RP abrégé fait référence à toute projection aléatoire.

Échantillonnage des matrices

Etant donné une matrice A de dimension mxn, il est souvent intéressant d'extraire des colonnes ou des lignes pour pouvoir réduire sa taille tout en gardant le maximum d'informations. Avec le grand nombre de données, on se retrouve en général avec une matrice ayant des combinaisons linéaires entre ses colonnes ou lignes.

Échantillonnage des scores de levier

Une façon naïve pour réaliser cet échantillonnage aléatoire serait de sélectionner des colonnes uniformément au hasard, selon une distribution d'échantillonnage d'importance^[5]. L'échantillonnage des scores de levier est une méthode de sélection de colonnes basée sur un vecteur de probabilités. Ce vecteur est calculé à partir de la matrice V, le résultat de la factorisation issue de l'algorithme de la décomposition en valeurs singulières (SVD). Cette méthode permet de réduire une grande matrice A de taille m x n, en une matrice réduite de taille m x s, ∀ s < n. Cette méthode se compose de deux phases:

Calculer les probabilités d'échantillonnage d'importance ${p_{i}}_{i = 1}^{n}$ .
Sélectionnez aléatoirement s colonnes de A en fonction de ces probabilités pour former la matrice réduite C.

Soit A ∈ ℝ^mxn, 𝛒 = rang(A) < n et V ∈ ℝ^nx𝛒. On définit les scores de levier de A par:

           l_i := ǁV_iǁ²₂, pour i=1..,n

Etant donné que $l = (\begin{matrix} l_{1} \\ l_{2} \\ l_{3} \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ l_{n} \end{matrix})$ , il suffit de diviser chaque ligne de ce vecteur par la somme de ses éléments pour le normaliser. Ce vecteur permet de trouver le vecteur de probabilités $p = (\begin{matrix} p_{1} \\ p_{2} \\ p_{3} \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ p_{n} \end{matrix})$ tel que:

                                     $p_{i} = \frac{l_{i}}{\sum_{i = 1}^{n} l_{i}}$

La matrice réduite est finalement construite à partir des colonnes ayant les plus grandes probabilités.

L'implémentation de cette méthode en python sera comme suit:

import numpy as np
def leverageScoreSampling(A, s):
	# n le nombre de colonnes de la matrice
	n = A.shape[1]

	# On récupére la matrice V du SVD en mode 'econ' 
	U, S, Vt = np.linalg.svd(A,False,True)
	V = Vt.T

	# On construit le vecteur de probabilités prob
	product = np.multiply(V,V)
	leveragescores = np.sum(product,axis=1) # somme des élements de chaque ligne 
	prob = leveragescores / np.sum(leveragescores,axis=0) # somme des élements de la colonne

	# idx vecteur d'indices des colonnes choisies basées sur le vecteur prob
	idx = np.random.choice(n,s,True,prob)
	idx = list(set(idx))
	C = A[:,idx]
	return C, idx
	
# Application de la fonction leverageScoreSampling()
A = np.array([[1, 1, 1,5,2],[2,3,2, 3, 4],[2,5,6,5,2]]) 
C, idx = leverageScoreSampling(A,2)
print(A)
print(C) 
print(idx)

La matrice à réduire est: $(\begin{matrix} 1 & 1 & 1 & 5 & 2 \\ 2 & 3 & 2 & 3 & 4 \\ 2 & 5 & 6 & 5 & 2 \end{matrix})$

La matrice réduite est: $(\begin{matrix} 1 & 2 \\ 2 & 4 \\ 6 & 2 \end{matrix})$

L'indice des colonnes sélectionnées: $(\begin{matrix} 2 & 4 \end{matrix})$

Dans ^[6], il est prouvé que cet algorithme fonctionne en O(mn²), la complexité est quasiment la même que celle de l'algorithme de projection aléatoire rapide.

Sélection de points de repères locaux

Cette forme d'échantillonnage est une approximation de bas niveau basée sur la sélection de points de repères locaux^[7]. Ces points de repères sont les clusters de l'algorithme d'apprentissage non-supervisé k-moyennes. L'algorithme regroupe les colonnes de la matrice A en k groupes tel que k est le nombre de colonnes de la matrice réduite. Ce partitionnement conserve toutes les caractéristiques d'une matrice de grande taille et permet d'éviter la perte d'information.

Exemples d'applications

Le cas d'une image non bruitée

Lors de la comparaison de différentes méthodes de réduction de dimensionnalité, les critères qui vont définir le choix de la méthode sont le taux de la distorsion provoqué par la méthode et sa complexité de calcul. Dans le cas des données d'image, nous mesurons la distorsion en comparant la distance euclidienne entre les vecteurs de données réduits à deux dimensionnalités et leur résistance euclidienne dans l'espace haute dimension d'origine. Dans le cas d'une projection aléatoire, la distance euclidienne dans l'espace réduit est mise à l'échelle comme indiqué en $(2)$ ; avec d'autres méthodes, aucune mise à l'échelle n'est effectuée.

La première étape était de tester l'effet de la dimensionnalité réduite en utilisant différentes valeurs de $k$ dans $[1, 800]$ . A chaque $k$ , l'opération de matrice de réduction de dimensionnalité a été calculée à nouveau. La figure 1 montre l'erreur de distance entre les membres d'une paire de vecteurs de données, sur une moyenne de 100 paires. Les résultats de la projection aléatoire avec une matrice aléatoire distribuée gaussienne (PA), de la projection aléatoire avec une matrice aléatoire creuse comme dans $(3)$ (PAC), de l’analyse en composantes principales (ACP) et de la transformée en cosinus discrète (TCD) sont présentés, ainsi que leur Intervalles de confiance de 95%.

La figure 1 montre clairement que la projection aléatoire (PA et PAC) donne des résultats très précis: la réduction de la dimensionnalité par projection aléatoire ne déforme pas les données de manière significative par rapport à la ACP. Aux dimensions $k > 600$ , la projection aléatoire et l’ACP donnent des résultats assez précis mais l’erreur produite par TCD est clairement visible. Aux plus petites dimensions, ACP déforme également les données. Cela nous indique que la variation dans les données est principalement capturée par les 600 premières composantes principales, car l'erreur dans ACP dépend de la somme des valeurs propres omises et k est égal au nombre de valeurs propres conservées. En revanche, la méthode de projection aléatoire continue de donner des résultats précis jusqu'à $k = 10$ . Une explication du succès de la projection aléatoire est le terme d'échelle J-L $\sqrt{d / k}$ (formule $2$ ), qui prend en compte la diminution de la dimensionnalité. En ACP, une telle mise à l'échelle ne serait utile que dans les plus petites dimensions, mais il est difficile de donner une règle simple.

Un autre point intéressant est la complexité de calcul des méthodes. La figure 2 indique le nombre d’opérations en virgule flottante de Matlab nécessaires lors de l’utilisation de PA, SPA, ACP ou TCD pour la réduction de la dimensionnalité, à l’échelle logarithmique. On peut constater que la ACP est beaucoup plus lourde que la projection aléatoire ou la TCD.

Les figures 1–2 permettent de conclure que la projection aléatoire est une méthode de réduction de la dimensionnalité peu coûteuse sur le plan du calcul, tout en préservant les distances des vecteurs de données pratiquement aussi bien que celle de la ACP et nettement supérieure à celle de la TCD. Encore plus, dans les plus petites dimensions, PA surpasse ACP et TCD.

Le cas d'une image bruitée

Dans une deuxième série d'expériences, nous avons considéré des images bruitées. Les images étaient corrompues par le bruit d'impulsion sel-et-poivre: avec une probabilité de $0.2$ , un pixel de l'image devenait noir ou blanc. Nous voulions projeter les données de telle sorte que la distance entre deux vecteurs de données dans l'espace réduit bruité soit aussi proche que possible de la distance entre ces deux vecteurs dans l'espace de données à haute dimension non bruité, même si la réduction de dimensionnalité était appliquée aux images bruitées de grande dimension.

Un moyen simple mais efficace de réduction du bruit, en particulier le bruit impulsif de la boîte à sel-et-poivre, est le filtrage médian (FM), dans lequel chaque pixel de l'image est remplacé par la médiane de la luminosité des pixels du voisinage. La médiane n'est pas affectée par les pics de bruit individuels et le filtrage médian élimine donc assez bien le bruit impulsif ^[8]. Une taille de voisinage commune est de $3 * 3$ pixels, ce qui a également été utilisé dans cette expérience. FM est très efficace du point de vue du calcul, d’ordre $O (d m N)$ pour une image de $d$ pixels, où $m$ désigne la taille du voisinage (dans notre cas, $m = 9$ ). En outre, FM ne nécessite pas de réduction de dimensionnalité; ainsi, son résultat peut être utilisé comme critère lors de la comparaison des méthodes de réduction de dimensionnalité et d’annulation du bruit.

La figure 3 montre comment la réduction de la dimensionnalité de la distance entre deux images bruitées est déformée par rapport à la distance qui les sépare de l'espace sans bruit de grande dimension d'origine. Ici, nous pouvons comparer différentes méthodes de réduction de dimensionnalité en ce qui concerne leur sensibilité au bruit. Nous pouvons voir que le filtrage médian introduit une distorsion assez importante dans les images, bien que, pour un œil humain, il élimine très efficacement le bruit impulsif. La distorsion est due au flou: les pixels sont remplacés par la médiane de leur voisinage, ce qui élimine le bruit mais aussi les petits détails.

La ACP, la PAC et la projection aléatoire fonctionnent de manière assez similaire au cas sans bruit. D'après la figure 3, nous pouvons conclure que la projection aléatoire est une alternative prometteuse à la réduction de la dimensionnalité sur des données bruitées, car elle ne semble pas être sensible au bruit impulsif. Il existe bien entendu de nombreuses autres méthodes de réduction du bruit. Ici, notre intérêt était principalement dans la réduction de la dimensionnalité et non de la réduction du bruit.

Le cas d'un document texte

La troisième expérience consiste à appliquer des techniques de réduction de dimensionnalité aux données textuelles. Les documents ont été convertis en vecteurs de fréquence des termes et certains termes courants ont été supprimés, mais aucun traitement radical n’a été effectué.

Les données n'ont pas été rendues une moyenne nulle et la variance globale des entrées de la matrice de données n'a pas été normalisée. Les vecteurs de document n'ont été normalisés qu'à la longueur d'unité. Ce type de prétraitement était différent de celui appliqué aux données d'images. Avec les natures distinctes des données images et textes, les différences de prétraitement ont donné des résultats légèrement différents sur ces différents ensembles de données. La taille du vocabulaire était $d = 5000$ termes et l'ensemble de données consistait en $N = 2262$ documents.

Nous avons choisi de manière aléatoire des paires de vecteurs de données (des documents) et on a calculé leur similarité comme leur produit intérieur. L'erreur dans la réduction de dimensionnalité a été mesurée en tant que la différence entre les produits internes avant et après la réduction de dimensionnalité. La figure 4 montre l'erreur introduite par la réduction de dimensionnalité. Les résultats de la décomposition en valeurs singulières (DVS) et de la projection aléatoire avec une matrice aléatoire distribuée gaussienne sont présentés, avec des intervalles de confiance de 95%. La dimensionnalité réduite $k$ a pris des valeurs dans $[1, 700]$ . On voit que la projection aléatoire n’est pas aussi précise que la DVS, mais dans de nombreuses applications, l’erreur peut être négligeable.

Le résultat de Johnson-Lindenstrauss ^[4] indique que les distances euclidiennes sont bien retenues dans les projections aléatoires. Le cas des produits internes est différent - les distances euclidiennes des vecteurs de documents auraient probablement été mieux préservées. Il est courant de mesurer la similarité des vecteurs de document par leurs produits internes.

Nos résultats sur les données des documents textes indiquent que la projection aléatoire peut être utilisée pour la réduction de la dimensionnalité de grandes collections de documents, avec une complexité de calcul inférieure à celle de l'indexation sémantique latente (ISL). De la même façon la PA peut accélérer l'indexation sémantique latente (ISL):

«La dimensionnalité des données est d'abord réduite par la RP et le poids lourd du LSI n'est calculé que dans le nouvel espace de faible dimension.»

Dans une autre expérience les documents ont été générés artificiellement et la matrice aléatoire

R

a été supposée strictement orthogonale; les expériences effectuées montrent qu'aucune de ces restrictions n'est en réalité nécessaire. Un autre problème courant dans la récupération de document texte est la correspondance de requêtes. La projection aléatoire peut s'avérer utile lors de la mise en correspondance de requêtes si la requête est longue ou si un ensemble de documents similaires a été recherché à la place d'un document particulier.

↑ Modèle:Article
↑ Dimitris Achlioptas, « Database-friendly random projections: Johnson-Lindenstrauss with binary coins », J. Comput. Syst. Sci., vol. 66, no 4,‎ {2003},, p. 671-687 (DOI 10.1016/S0022-0000(03)00025-4)
↑ Modèle:Ouvrage
↑ ^4,0 et ^4,1 Modèle:Ouvrage
↑ Shusen Wang - A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
↑ P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Technical report. Preprint: arXiv:1109.3843 (2011).
↑ Kai Zhang and James T. Kwok - Clustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction
↑ Modèle:Ouvrage

[1] Modèle:Article

[2] Dimitris Achlioptas, « Database-friendly random projections: Johnson-Lindenstrauss with binary coins », J. Comput. Syst. Sci., vol. 66, no 4,‎ {2003},, p. 671-687 (DOI 10.1016/S0022-0000(03)00025-4)

[3] Modèle:Ouvrage

[:0-4] 4,0 et ^4,1 Modèle:Ouvrage

[5] Shusen Wang - A Practical Guide to Randomized Matrix Computations with MATLAB Implementations

[6] P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Technical report. Preprint: arXiv:1109.3843 (2011).

[7] Kai Zhang and James T. Kwok - Clustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction

[8] Modèle:Ouvrage

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Testwiki:L'algèbre linéaire numérique randomisée (Big data)

Sommaire

Introduction

Historique

Matrices

L'algèbre linéaire numérique randomisée

Une perspective historique : maintenant et à l'avenir

Principe de la Projection Aléatoire (PA)

Échantillonnage des matrices

Échantillonnage des scores de levier

Sélection de points de repères locaux

Exemples d'applications

Le cas d'une image non bruitée

Le cas d'une image bruitée

Le cas d'un document texte

Menu de navigation

Testwiki:L'algèbre linéaire numérique randomisée (Big data)

Introduction

Historique

Matrices

L'algèbre linéaire numérique randomisée

Une perspective historique : maintenant et à l'avenir

Principe de la Projection Aléatoire (PA)

Échantillonnage des matrices

Échantillonnage des scores de levier

Sélection de points de repères locaux

Exemples d'applications

Le cas d'une image non bruitée

Le cas d'une image bruitée

Le cas d'un document texte

Menu de navigation

Rechercher