ランダム射影を用いたヨンソン・リンデンシュトラウスの補題の探究

はじめに

ヨンソン・リンデンシュトラウスの補題は、任意の高次元データセットを、2 点間距離の歪みを制御しながら、低次元のユークリッド空間にランダムに射影できるという数学の定理です。この実験では、ランダム射影による埋め込みに対するヨンソン・リンデンシュトラウスの補題の理論的な境界を調べ、Python の scikit - learn を使って経験的に検証します。

VM のヒント

VM の起動が完了したら、左上隅をクリックしてノートブックタブに切り替え、Jupyter Notebook を使って練習しましょう。

時々、Jupyter Notebook が読み込み終わるまで数秒待つ必要があります。Jupyter Notebook の制限により、操作の検証を自動化することはできません。

学習中に問題に直面した場合は、Labby にお尋ねください。セッション後にフィードバックを提供してください。すぐに問題を解決いたします。

理論的な境界

最初のステップは、ヨンソン・リンデンシュトラウスの補題の理論的な境界を調べることです。サンプル数 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

## range of admissible distortions
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

## range of number of samples (observation) to embed
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()

理論的な境界（続き）

2 番目のグラフは、許容可能な歪み eps を増やすことで、与えられたサンプル数 n_samples に対して最小次元数 n_components を減らすことができることを示しています。

## range of admissible distortions
eps_range = np.linspace(0.01, 0.99, 100)

## range of number of samples (observation) to embed
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()

## 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)

まとめ

この実験では、ランダム射影による埋め込みに対するヨンソン・リンデンシュトラウスの補題の理論的な境界を調べ、Python の scikit - learn を使って経験的に検証しました。サンプル数 n_samples が増えるにつれて、eps 埋め込みを保証するために必要な最小次元数をプロットしました。また、20 ニュースグループの文書データセットまたは手書き数字データセットに対して、ヨンソン・リンデンシュトラウスの境界を経験的に検証しました。合計 100k の特徴を持つ 300 個の文書を、疎なランダム行列を使って、目的の次元数 n_components のさまざまな値を持つより低次元のユークリッド空間に射影しました。n_components の値が小さい場合、分布は広く、多くの歪んだペアと歪んだ分布がありますが、n_components の値が大きい場合、歪みが制御され、距離はランダム射影によって良好に保たれます。

まとめ

おめでとうございます！あなたはヨンソン・リンデンシュトラウスの補題の実験を完了しました。あなたのスキルを向上させるために、LabEx でさらに多くの実験を行って練習することができます。