LabEx
ВходРегистрация

Исследование леммы Джонсона-Линденштрасса с использованием случайных проекций

Beginner

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

Введение

Лемма Джонсона-Линденштрасса - это математическая теорема, которая утверждает, что любая высокомерная наборан данных может быть случайным образом проектирована в пространство Евклида с меньшей размерностью, при этом контролируется искажение в попарных расстояниях. В этом лабораторном занятии мы исследуем теоретические границы леммы Джонсона-Линденштрасса для эмбеддинга с помощью случайных проекций и проверяем ее эмпирически с использованием Python scikit-learn.

Советы по работе с ВМ

После запуска ВМ нажмите в левом верхнем углу, чтобы переключиться на вкладку Notebook и получить доступ к Jupyter Notebook для практики.

Иногда вам может потребоваться подождать несколько секунд, пока Jupyter Notebook не загрузится полностью. Валидация операций не может быть автоматизирована из-за ограничений Jupyter Notebook.

Если вы сталкиваетесь с проблемами во время обучения, не стесняйтесь обращаться к Labby. Оставьте отзыв после занятия, и мы оперативно решим проблему для вас.

Теоретические границы

Первым шагом является исследование теоретических границ леммы Джонсона-Линденштрасса. Мы построим график минимального числа размерностей, необходимых для гарантии eps-эмбеддинга для возрастающего числа выборок n_samples. Дисторсия，引入的由随机投影 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(0, 1) формы (n_components, n_features) (или разреженная матрица Ахлиоптаса).

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 vs n_components")
plt.show()

Теоретические границы (продолжение)

Второй график показывает, что увеличение допустимой искажения eps позволяет уменьшить минимальное число размерностей n_components для заданного числа выборок n_samples.

## диапазон допустимых искажений
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 vs eps")
plt.show()

Эмпирическая проверка

Следующим шагом является эмпирическая проверка границ Джонсона-Линденштрасса на наборе текстовых документов 20 newsgroups или на наборе цифр. Мы будем использовать набор данных 20 newsgroups и проектировать 300 документов с общим количеством 100 тыс. признаков с использованием разреженной случайной матрицы в более мелкие евклидовы пространства с различными значениями для целевого числа размерностей 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. Мы построили график минимального числа размерностей, необходимых для гарантии eps-эмбеддинга для возрастающего числа выборок n_samples. Мы также проверили границы Джонсона-Линденштрасса эмпирически на наборе текстовых документов 20 newsgroups или на наборе цифр. Мы проектировали 300 документов с общим количеством 100 тыс. признаков с использованием разреженной случайной матрицы в более мелкие евклидовы пространства с различными значениями для целевого числа размерностей n_components. Мы можем видеть, что для малых значений n_components распределение имеет широкий диапазон с большим количеством искаженных пар и смещенным распределением, в то время как для больших значений n_components искажение контролируется, и расстояния хорошо сохраняются при случайной проекции.

Обзор

Поздравляем! Вы завершили лабораторную работу по лемме Джонсона-Линденштрасса. Вы можете практиковаться в более многих лабораторных работах в LabEx, чтобы улучшить свои навыки.