Explorando o Lema de Johnson-Lindenstrauss com Projeções Aleatórias

Introdução

O lema de Johnson-Lindenstrauss é um teorema matemático que afirma que qualquer conjunto de dados de alta dimensionalidade pode ser aleatoriamente projetado em um espaço euclidiano de menor dimensionalidade, controlando a distorção nas distâncias entre pares de pontos. Neste laboratório, exploraremos os limites teóricos do lema de Johnson-Lindenstrauss para incorporação com projeções aleatórias e o validaremos empiricamente usando o Python scikit-learn.

Dicas da Máquina Virtual

Após o término da inicialização da máquina virtual, clique no canto superior esquerdo para mudar para a aba Notebook para acessar o Jupyter Notebook para praticar.

Às vezes, pode ser necessário aguardar alguns segundos para que o Jupyter Notebook termine de carregar. A validação das operações não pode ser automatizada devido a limitações no Jupyter Notebook.

Se você enfrentar problemas durante o aprendizado, sinta-se à vontade para perguntar ao Labby. Forneça feedback após a sessão e resolveremos prontamente o problema para você.

Limites Teóricos

O primeiro passo é explorar os limites teóricos do lema de Johnson-Lindenstrauss. Iremos plotar o número mínimo de dimensões necessárias para garantir uma incorporação eps para um número crescente de amostras n_samples. A distorção introduzida por uma projeção aleatória p é afirmada pelo fato de que p está definindo uma incorporação eps com boa probabilidade, como definido por:

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

Onde u e v são quaisquer linhas retiradas de um conjunto de dados com forma (n_samples, n_features) e p é uma projeção por uma matriz gaussiana aleatória N(0, 1) com forma (n_components, n_features) (ou uma matriz esparsa de Achlioptas).

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

## intervalo de distorções admissíveis
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## intervalo do número de amostras (observações) a serem incorporadas
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 observações a serem incorporadas em eps")
plt.ylabel("Número mínimo de dimensões")
plt.title("Limites de Johnson-Lindenstrauss:\nn_samples vs n_components")
plt.show()

Limites Teóricos (continuação)

O segundo gráfico demonstra que um aumento da distorção admissível eps permite reduzir o número mínimo de dimensões n_components para um determinado número de amostras n_samples.

## intervalo de distorções admissíveis
eps_range = np.linspace(0.01, 0.99, 100)

## intervalo do número de amostras (observações) a serem incorporadas
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("Distorção eps")
plt.ylabel("Número mínimo de dimensões")
plt.title("Limites de Johnson-Lindenstrauss:\nn_components vs eps")
plt.show()

Validação Empírica

O próximo passo é validar os limites de Johnson-Lindenstrauss empiricamente no conjunto de dados de documentos de texto 20 newsgroups ou no conjunto de dados de dígitos. Usaremos o conjunto de dados 20 newsgroups e projetamos 300 documentos com 100k recursos no total usando uma matriz aleatória esparsa para espaços euclidianos menores com vários valores para o número alvo de dimensões 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()

## seleciona apenas pares de amostras não idênticas
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"Matriz aleatória com tamanho: {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("Distâncias quadradas em pares no espaço original")
    plt.ylabel("Distâncias quadradas em pares no espaço projetado")
    plt.title("Distribuição de distâncias em pares para n_components=%d" % n_components)
    cb = plt.colorbar()
    cb.set_label("Contagem de pares de amostras")

    rates = projected_dists / dists
    print(f"Taxa média de distâncias: {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("Taxa de distâncias quadradas: projetada / original")
    plt.ylabel("Distribuição de pares de amostras")
    plt.title("Histograma de taxas de distância em pares para n_components=%d" % n_components)

Resumo

Neste laboratório, exploramos os limites teóricos do lema de Johnson-Lindenstrauss para incorporação com projeções aleatórias e o validamos empiricamente usando Python scikit-learn. Plotamos o número mínimo de dimensões necessárias para garantir uma incorporação eps para um número crescente de amostras n_samples. Também validamos os limites de Johnson-Lindenstrauss empiricamente no conjunto de dados de documentos de texto 20 newsgroups ou no conjunto de dados de dígitos. Projetamos 300 documentos com 100k recursos no total usando uma matriz aleatória esparsa para espaços euclidianos menores com vários valores para o número alvo de dimensões n_components. Podemos observar que para valores baixos de n_components, a distribuição é ampla, com muitos pares distorcidos e uma distribuição assimétrica, enquanto para valores maiores de n_components, a distorção é controlada e as distâncias são bem preservadas pela projeção aleatória.

Resumo

Parabéns! Você concluiu o laboratório do Lema de Johnson-Lindenstrauss. Você pode praticar mais laboratórios no LabEx para aprimorar suas habilidades.