존슨 - 린덴슈트라우스 보조정리 | 무작위 투영 | 유클리드 공간

소개

존슨 - 린덴슈트라우스 보조정리는 고차원 데이터셋을 낮은 차원의 유클리드 공간으로 무작위 투영하면서 쌍대 거리의 왜곡을 제어할 수 있다는 수학적 정리입니다. 이 실습에서는 무작위 투영을 이용한 임베딩에 대한 존슨 - 린덴슈트라우스 보조정리의 이론적 한계를 탐구하고 파이썬 scikit-learn 을 사용하여 실험적으로 검증할 것입니다.

VM 팁

VM 시작이 완료되면 왼쪽 상단 모서리를 클릭하여 Notebook 탭으로 전환하여 연습을 위한 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

## 허용 가능한 왜곡의 범위
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("eps-임베딩할 관측치의 수")
plt.ylabel("최소 차원 수")
plt.title("존슨 - 린덴슈트라우스 한계:\nn_samples 대 n_components")
plt.show()

이론적 한계 (계속)

두 번째 플롯은 허용 가능한 왜곡 eps가 증가함에 따라 주어진 샘플 수 n_samples에 대해 최소 차원 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("왜곡 eps")
plt.ylabel("최소 차원 수")
plt.title("존슨 - 린덴슈트라우스 한계:\nn_components 대 eps")
plt.show()

실험적 검증

다음 단계는 20 뉴스그룹 텍스트 문서 데이터셋 또는 숫자 데이터셋에서 존슨 - 린덴슈트라우스 경계를 실험적으로 검증하는 것입니다. 20 뉴스그룹 데이터셋을 사용하고 총 100,000 개의 특징을 가진 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("원래 공간의 쌍별 제곱 거리")
    plt.ylabel("투영된 공간의 쌍별 제곱 거리")
    plt.title("n_components=%d에 대한 쌍별 거리 분포" % n_components)
    cb = plt.colorbar()
    cb.set_label("샘플 쌍 개수")

    rates = projected_dists / dists
    print(f"평균 거리 비율: {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("제곱 거리 비율: 투영된 / 원래")
    plt.ylabel("샘플 쌍의 분포")
    plt.title("n_components=%d에 대한 쌍별 거리 비율 히스토그램" % n_components)

요약

이 실험에서는 무작위 투영을 이용한 임베딩에 대한 존슨 - 린덴슈트라우스 보조정리의 이론적 한계를 탐구하고 파이썬 scikit-learn 을 사용하여 실험적으로 검증했습니다. 샘플 수 n_samples가 증가함에 따라 eps-임베딩을 보장하기 위해 필요한 최소 차원 수를 플롯했습니다. 또한, 20 뉴스그룹 텍스트 문서 데이터셋 또는 숫자 데이터셋에서 존슨 - 린덴슈트라우스 보조정리를 실험적으로 검증했습니다. 총 100,000 개의 특징을 가진 300 개의 문서를 희소 무작위 행렬을 사용하여 목표 차원 수 n_components가 다양한 값을 갖는 더 작은 유클리드 공간으로 투영했습니다. n_components 값이 낮을 경우 분포가 넓고 많은 왜곡된 쌍과 치우친 분포를 보이는 반면, n_components 값이 높을 경우 왜곡이 제어되고 무작위 투영으로 거리가 잘 보존됨을 확인할 수 있습니다.

요약

축하합니다! 존슨 - 린덴슈트라우스 보조정리 실험을 완료했습니다. LabEx 에서 더 많은 실험을 통해 기술을 향상시킬 수 있습니다.

무작위 투영을 이용한 존슨 - 린덴슈트라우스 보조정리 탐색

소개

VM 팁

이론적 한계

이론적 한계 (계속)

실험적 검증

요약

요약