Das Johnson-Lindenstrauss-Lemma mit zufälligen Projekten erkunden

Machine LearningMachine LearningBeginner
Jetzt üben

This tutorial is from open-source community. Access the source code

💡 Dieser Artikel wurde von AI-Assistenten übersetzt. Um die englische Version anzuzeigen, können Sie hier klicken

Einführung

Der Johnson-Lindenstrauss-Lemma ist ein mathematischer Satz, der besagt, dass jeder hochdimensionale Datensatz in einen euklidischen Raum niedriger Dimension zufällig projiziert werden kann, während die Verzerrung der paarweisen Distanzen kontrolliert wird. In diesem Lab werden wir die theoretischen Grenzen des Johnson-Lindenstrauss-Lemmas für die Einbettung mit zufälligen Projekten untersuchen und es empirisch mit Python scikit-learn validieren.

VM-Tipps

Nachdem der VM-Start abgeschlossen ist, klicken Sie in der oberen linken Ecke, um zur Registerkarte Notebook zu wechseln und Jupyter Notebook für die Übung zu nutzen.

Manchmal müssen Sie einige Sekunden warten, bis Jupyter Notebook vollständig geladen ist. Die Validierung von Vorgängen kann aufgrund von Einschränkungen in Jupyter Notebook nicht automatisiert werden.

Wenn Sie bei der Lernphase Probleme haben, können Sie Labby gerne fragen. Geben Sie nach der Sitzung Feedback, und wir werden das Problem für Sie prompt beheben.

Theoretische Grenzen

Der erste Schritt besteht darin, die theoretischen Grenzen des Johnson-Lindenstrauss-Lemmas zu untersuchen. Wir werden die minimale Anzahl an Dimensionen plotten, die erforderlich sind, um eine eps-Einbettung für eine zunehmende Anzahl von Proben n_samples zu gewährleisten. Die durch einen zufälligen Projekion p eingeführte Verzerrung wird dadurch behauptet, dass p mit guter Wahrscheinlichkeit eine eps-Einbettung definiert, wie durch folgende Gleichung definiert:

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

Wobei u und v beliebige Zeilen aus einem Datensatz der Form (n_samples, n_features) sind und p eine Projekion durch eine zufällige Gaußsche N(0, 1)-Matrix der Form (n_components, n_features) (oder eine dünne Achlioptas-Matrix) ist.

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

## Bereich der zulässigen Verzerrungen
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## Bereich der Anzahl von Proben (Beobachtungen) zum Einbetten
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("Anzahl der Beobachtungen zur eps-Einbettung")
plt.ylabel("Minimale Anzahl an Dimensionen")
plt.title("Johnson-Lindenstrauss-Grenzen:\nn_samples vs n_components")
plt.show()

Theoretische Grenzen (Fortsetzung)

Das zweite Diagramm zeigt, dass eine Erhöhung der zulässigen Verzerrung eps es uns ermöglicht, die minimale Anzahl an Dimensionen n_components für eine gegebene Anzahl von Proben n_samples zu verringern.

## Bereich der zulässigen Verzerrungen
eps_range = np.linspace(0.01, 0.99, 100)

## Bereich der Anzahl von Proben (Beobachtungen) zum Einbetten
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("Verzerrung eps")
plt.ylabel("Minimale Anzahl an Dimensionen")
plt.title("Johnson-Lindenstrauss-Grenzen:\nn_components vs eps")
plt.show()

Empirische Validierung

Der nächste Schritt besteht darin, die Johnson-Lindenstrauss-Grenzen empirisch auf dem 20 Newsgroups-Text-Dokumentendataset oder auf dem Digits-Dataset zu validieren. Wir werden das 20 Newsgroups-Dataset verwenden und 300 Dokumente mit insgesamt 100.000 Merkmalen mithilfe einer dünnen Zufallsmatrix in kleinere euklidische Räume mit verschiedenen Werten für die Zielanzahl der Dimensionen n_components projizieren.

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)

Zusammenfassung

In diesem Lab haben wir die theoretischen Grenzen des Johnson-Lindenstrauss-Lemmas für die Einbettung mit zufälligen Projekten untersucht und es empirisch mit Python scikit-learn validiert. Wir haben die minimale Anzahl an Dimensionen geplottet, die erforderlich sind, um eine eps-Einbettung für eine zunehmende Anzahl von Proben n_samples zu gewährleisten. Wir haben auch die Johnson-Lindenstrauss-Grenzen empirisch auf dem 20 Newsgroups-Text-Dokumentendataset oder auf dem Digits-Dataset validiert. Wir haben 300 Dokumente mit insgesamt 100.000 Merkmalen mithilfe einer dünnen Zufallsmatrix in kleinere euklidische Räume mit verschiedenen Werten für die Zielanzahl der Dimensionen n_components projiziert. Wir können sehen, dass für niedrige Werte von n_components die Verteilung weit ist mit vielen verzerrten Paaren und einer schiefen Verteilung, während für größere Werte von n_components die Verzerrung kontrolliert ist und die Distanzen durch die zufällige Projekion gut erhalten bleiben.

Zusammenfassung

Herzlichen Glückwunsch! Sie haben das Johnson-Lindenstrauss-Lemma-Lab abgeschlossen. Sie können in LabEx weitere Labs ausprobieren, um Ihre Fähigkeiten zu verbessern.