通过随机投影探索约翰逊 - 林登施特劳斯引理

简介

约翰逊-林登施特劳斯引理（Johnson-Lindenstrauss lemma）是一个数学定理，它表明任何高维数据集都可以随机投影到低维欧几里得空间中，同时控制成对距离的失真。在本实验中，我们将探索使用随机投影进行嵌入时约翰逊-林登施特劳斯引理的理论界限，并使用 Python 的 scikit-learn 进行实证验证。

虚拟机使用提示

虚拟机启动完成后，点击左上角切换到笔记本标签页，以访问 Jupyter Notebook 进行练习。

有时，你可能需要等待几秒钟让 Jupyter Notebook 完成加载。由于 Jupyter Notebook 的限制，操作验证无法自动化。

如果你在学习过程中遇到问题，随时向 Labby 提问。课程结束后提供反馈，我们会及时为你解决问题。

Skills Graph

理论界限

第一步是探索约翰逊 - 林登施特劳斯引理的理论界限。我们将绘制为保证对不断增加的样本数量 n_samples 进行 eps 嵌入所需的最小维度数。随机投影 p 引入的失真由以下事实确定：p 以良好的概率定义了一个 eps 嵌入，定义如下：

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

其中 u 和 v 是从形状为 (n_samples, n_features) 的数据集中选取的任意行，并且 p 是由形状为 (n_components, n_features) 的随机高斯 N(0, 1) 矩阵（或稀疏阿赫利奥普塔斯矩阵）进行的投影。

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

## 可接受失真范围
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## 要嵌入的样本数量（观测值）范围
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("Number of observations to eps-embed")
plt.ylabel("Minimum number of dimensions")
plt.title("Johnson-Lindenstrauss bounds:\nn_samples vs n_components")
plt.show()

理论界限（续）

第二张图表明，对于给定数量的样本 n_samples，增大可接受的失真 eps 能让我们减少最小维度数 n_components。

## 可接受失真范围
eps_range = np.linspace(0.01, 0.99, 100)

## 要嵌入的样本数量（观测值）范围
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("Distortion eps")
plt.ylabel("Minimum number of dimensions")
plt.title("Johnson-Lindenstrauss bounds:\nn_components vs eps")
plt.show()

实证验证

下一步是在20个新闻组文本数据集或手写数字数据集上对约翰逊 - 林登施特劳斯界限进行实证验证。我们将使用20个新闻组数据集，并使用稀疏随机矩阵将总共具有100k特征的300个文档投影到具有不同目标维度数 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()

## 仅选择不相同的样本对
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)

总结

在本实验中，我们探索了使用随机投影进行嵌入时约翰逊 - 林登施特劳斯引理的理论界限，并使用 Python 的 scikit - learn 进行了实证验证。我们绘制了为保证对不断增加的样本数量 n_samples 进行 eps 嵌入所需的最小维度数。我们还在20个新闻组文本数据集或手写数字数据集上对约翰逊 - 林登施特劳斯界限进行了实证验证。我们使用稀疏随机矩阵将总共具有100k特征的300个文档投影到具有不同目标维度数 n_components 的较小欧几里得空间中。我们可以看到，对于较小的 n_components 值，分布范围很广，有许多失真的对且分布呈偏态，而对于较大的 n_components 值，失真得到控制，随机投影能很好地保留距离。

总结

恭喜你！你已经完成了约翰逊 - 林登施特劳斯引理实验。你可以在LabEx中练习更多实验来提升你的技能。