Explorando el lema de Johnson-Lindenstrauss con proyecciones aleatorias

Introducción

El lema de Johnson-Lindenstrauss es un teorema matemático que establece que cualquier conjunto de datos de alta dimensión se puede proyectar aleatoriamente en un espacio euclidiano de dimensión inferior mientras se controla la distorsión en las distancias entre pares. En este laboratorio, exploraremos los límites teóricos del lema de Johnson-Lindenstrauss para la incrustación con proyecciones aleatorias y lo validaremos empíricamente utilizando scikit-learn de Python.

Consejos sobre la VM

Una vez que se haya iniciado la VM, haga clic en la esquina superior izquierda para cambiar a la pestaña Cuaderno y acceder a Jupyter Notebook para practicar.

A veces, es posible que tenga que esperar unos segundos a que Jupyter Notebook termine de cargarse. La validación de las operaciones no se puede automatizar debido a las limitaciones de Jupyter Notebook.

Si tiene problemas durante el aprendizaje, no dude en preguntar a Labby. Deje comentarios después de la sesión y resolveremos rápidamente el problema para usted.

Límites teóricos

El primer paso es explorar los límites teóricos del lema de Johnson-Lindenstrauss. Graficaremos el número mínimo de dimensiones necesario para garantizar una incrustación de eps para un número creciente de muestras n_samples. La distorsión introducida por una proyección aleatoria p se afirma por el hecho de que p está definiendo una incrustación de eps con buena probabilidad como se define por:

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

Donde u y v son cualquier fila tomada de un conjunto de datos de forma (n_samples, n_features) y p es una proyección por una matriz gaussiana aleatoria N(0, 1) de forma (n_components, n_features) (o una matriz esparsa de Achlioptas).

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

## rango de distorsiones admisibles
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## rango de número de muestras (observaciones) a incrustar
n_samples_range = np.logspace(1, 9, 9)

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

plt.legend([f"eps = {eps:0.1f}" for eps in eps_range], loc="lower right")
plt.xlabel("Número de observaciones para incrustar eps")
plt.ylabel("Número mínimo de dimensiones")
plt.title("Límites de Johnson-Lindenstrauss:\nn_samples vs n_components")
plt.show()

Límites teóricos (continuación)

La segunda gráfica muestra que un aumento de la distorsión admisible eps nos permite reducir el número mínimo de dimensiones n_components para un número dado de muestras n_samples.

## rango de distorsiones admisibles
eps_range = np.linspace(0.01, 0.99, 100)

## rango de número de muestras (observaciones) a incrustar
n_samples_range = np.logspace(2, 6, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(n_samples_range)))

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

plt.legend([f"n_samples = {n}" for n in n_samples_range], loc="upper right")
plt.xlabel("Distorsión eps")
plt.ylabel("Número mínimo de dimensiones")
plt.title("Límites de Johnson-Lindenstrauss:\nn_components vs eps")
plt.show()

Validación empírica

El siguiente paso es validar los límites de Johnson-Lindenstrauss empíricamente en el conjunto de datos de documentos de texto 20 newsgroups o en el conjunto de datos de dígitos. Usaremos el conjunto de datos 20 newsgroups y proyectaremos 300 documentos con 100k características en total usando una matriz aleatoria esparsa a espacios euclidianos más pequeños con varios valores para el número objetivo de dimensiones 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)

Resumen

En este laboratorio, exploramos los límites teóricos del lema de Johnson-Lindenstrauss para la incrustación con proyecciones aleatorias y lo validamos empíricamente utilizando scikit-learn de Python. Graficamos el número mínimo de dimensiones necesario para garantizar una incrustación de eps para un número creciente de muestras n_samples. También validamos los límites de Johnson-Lindenstrauss empíricamente en el conjunto de datos de documentos de texto 20 newsgroups o en el conjunto de datos de dígitos. Proyectamos 300 documentos con 100k características en total usando una matriz aleatoria esparsa a espacios euclidianos más pequeños con varios valores para el número objetivo de dimensiones n_components. Podemos ver que para valores bajos de n_components la distribución es amplia con muchos pares distorsionados y una distribución sesgada mientras que para valores más grandes de n_components la distorsión está controlada y las distancias se preservan bien por la proyección aleatoria.

Resumen

¡Felicitaciones! Has completado el laboratorio del lema de Johnson-Lindenstrauss. Puedes practicar más laboratorios en LabEx para mejorar tus habilidades.