Explorer le lemme de Johnson-Lindenstrauss avec des projections aléatoires

Introduction

Le lemme de Johnson-Lindenstrauss est un théorème mathématique qui stipule qu'un ensemble de données de haute dimension peut être projeté aléatoirement dans un espace euclidien de dimension inférieure tout en contrôlant la distorsion dans les distances entre paires. Dans ce laboratoire, nous explorerons les limites théoriques du lemme de Johnson-Lindenstrauss pour l'imbrication avec des projections aléatoires et le validerons empiriquement à l'aide de scikit-learn en Python.

Conseils sur la machine virtuelle

Une fois le démarrage de la machine virtuelle terminé, cliquez dans le coin supérieur gauche pour basculer vers l'onglet Carnet de notes pour accéder au carnet Jupyter pour la pratique.

Parfois, vous devrez peut-être attendre quelques secondes pour que le carnet Jupyter ait fini de charger. La validation des opérations ne peut pas être automatisée en raison des limitations du carnet Jupyter.

Si vous rencontrez des problèmes pendant l'apprentissage, n'hésitez pas à demander à Labby. Donnez des commentaires après la session et nous résoudrons rapidement le problème pour vous.

Skills Graph

Bornes théoriques

La première étape consiste à explorer les bornes théoriques du lemme de Johnson-Lindenstrauss. Nous allons tracer le nombre minimum de dimensions nécessaire pour garantir un plongement eps pour un nombre croissant d'échantillons n_samples. La distorsion introduite par une projection aléatoire p est affirmée par le fait que p définit un plongement eps avec une bonne probabilité comme défini par :

(1 - eps) \|u - v\|^2 < \|p(u) - p(v)\|^2 < (1 + eps) \|u - v\|^2

Où u et v sont deux lignes prises au hasard d'un ensemble de données de forme (n_samples, n_features) et p est une projection par une matrice gaussienne aléatoire N(0, 1) de forme (n_components, n_features) (ou une matrice d'Achlioptas sparse).

import numpy as np
import matplotlib.pyplot as plt
from sklearn.random_projection import johnson_lindenstrauss_min_dim

## plage de distorsions admissibles
eps_range = np.linspace(0.1, 0.99, 5)
couleurs = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## plage du nombre d'échantillons (observations) à plonger
n_samples_range = np.logspace(1, 9, 9)

plt.figure()
for eps, couleur in zip(eps_range, couleurs):
    min_n_components = johnson_lindenstrauss_min_dim(n_samples_range, eps=eps)
    plt.loglog(n_samples_range, min_n_components, couleur=couleur)

plt.legend([f"eps = {eps:0.1f}" for eps in eps_range], loc="bas droite")
plt.xlabel("Nombre d'observations pour un plongement eps")
plt.ylabel("Nombre minimum de dimensions")
plt.title("Bornes de Johnson-Lindenstrauss :\nn_samples vs n_components")
plt.show()

Bornes théoriques (suite)

Le second graphique montre qu'une augmentation de la distorsion admissible eps permet de réduire le nombre minimal de dimensions n_components pour un nombre donné d'échantillons n_samples.

## plage de distorsions admissibles
eps_range = np.linspace(0.01, 0.99, 100)

## plage du nombre d'échantillons (observations) à plonger
n_samples_range = np.logspace(2, 6, 5)
couleurs = plt.cm.Blues(np.linspace(0.3, 1.0, len(n_samples_range)))

plt.figure()
for n_samples, couleur in zip(n_samples_range, couleurs):
    min_n_components = johnson_lindenstrauss_min_dim(n_samples, eps=eps_range)
    plt.semilogy(eps_range, min_n_components, couleur=couleur)

plt.legend([f"n_samples = {n}" for n in n_samples_range], loc="haut droite")
plt.xlabel("Distorsion eps")
plt.ylabel("Nombre minimum de dimensions")
plt.title("Bornes de Johnson-Lindenstrauss :\nn_components vs eps")
plt.show()

Validation empirique

L'étape suivante consiste à valider empiriquement les bornes de Johnson-Lindenstrauss sur l'ensemble de données de documents texte 20 newsgroups ou sur l'ensemble de données des chiffres. Nous utiliserons l'ensemble de données 20 newsgroups et projeterons 300 documents avec 100 000 caractéristiques au total en utilisant une matrice aléatoire sparse vers des espaces euclidiens plus petits avec diverses valeurs pour le nombre cible de dimensions n_components.

import sys
from time import time
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import fetch_20newsgroups_vectorized
from sklearn.random_projection import SparseRandomProjection
from sklearn.metrics.pairwise import euclidean_distances

data = fetch_20newsgroups_vectorized().data[:300]

n_samples, n_features = data.shape
print(f"Embedding {n_samples} samples with dim {n_features} using various random projections")

n_components_range = np.array([300, 1_000, 10_000])
dists = euclidean_distances(data, squared=True).ravel()

## select only non-identical samples pairs
nonzero = dists!= 0
dists = dists[nonzero]

for n_components in n_components_range:
    t0 = time()
    rp = SparseRandomProjection(n_components=n_components)
    projected_data = rp.fit_transform(data)
    print(f"Projected {n_samples} samples from {n_features} to {n_components} in {time() - t0:0.3f}s")
    if hasattr(rp, "components_"):
        n_bytes = rp.components_.data.nbytes
        n_bytes += rp.components_.indices.nbytes
        print(f"Random matrix with size: {n_bytes / 1e6:0.3f} MB")

    projected_dists = euclidean_distances(projected_data, squared=True).ravel()[nonzero]

    plt.figure()
    min_dist = min(projected_dists.min(), dists.min())
    max_dist = max(projected_dists.max(), dists.max())
    plt.hexbin(
        dists,
        projected_dists,
        gridsize=100,
        cmap=plt.cm.PuBu,
        extent=[min_dist, max_dist, min_dist, max_dist],
    )
    plt.xlabel("Pairwise squared distances in original space")
    plt.ylabel("Pairwise squared distances in projected space")
    plt.title("Pairwise distances distribution for n_components=%d" % n_components)
    cb = plt.colorbar()
    cb.set_label("Sample pairs counts")

    rates = projected_dists / dists
    print(f"Mean distances rate: {np.mean(rates):.2f} ({np.std(rates):.2f})")

    plt.figure()
    plt.hist(rates, bins=50, range=(0.0, 2.0), edgecolor="k", density=True)
    plt.xlabel("Squared distances rate: projected / original")
    plt.ylabel("Distribution of samples pairs")
    plt.title("Histogram of pairwise distance rates for n_components=%d" % n_components)

Sommaire

Dans ce laboratoire, nous avons exploré les limites théoriques du lemme de Johnson-Lindenstrauss pour l'imbrication avec des projections aléatoires et le validé empiriquement à l'aide de scikit-learn en Python. Nous avons tracé le nombre minimum de dimensions nécessaire pour garantir un plongement eps pour un nombre croissant d'échantillons n_samples. Nous avons également validé empiriquement les bornes de Johnson-Lindenstrauss sur l'ensemble de données de documents texte 20 newsgroups ou sur l'ensemble de données des chiffres. Nous avons projeté 300 documents avec 100 000 caractéristiques au total en utilisant une matrice aléatoire sparse vers des espaces euclidiens plus petits avec diverses valeurs pour le nombre cible de dimensions n_components. Nous pouvons constater que pour de faibles valeurs de n_components, la distribution est large avec de nombreux paires distordues et une distribution asymétrique, tandis que pour de plus grandes valeurs de n_components, la distorsion est contrôlée et les distances sont bien conservées par la projection aléatoire.

Sommaire

Félicitations ! Vous avez terminé le laboratoire sur le lemme de Johnson-Lindenstrauss. Vous pouvez pratiquer d'autres laboratoires sur LabEx pour améliorer vos compétences.