8.6. Случайная проекция

8.6.1. Лемма Джонсона — Линденштраусса

Основной теоретический результат, объясняющий эффективность случайной проекции, — это лемма Джонсона — Линденштраусса (цитата из Википедии):

В математике лемма Джонсона — Линденштраусса — это результат, касающийся вложений точек из пространства высокой размерности в евклидово пространство меньшей размерности с малым искажением. Согласно лемме, небольшое множество точек в пространстве высокой размерности можно вложить в пространство значительно меньшей размерности так, чтобы расстояния между точками почти не изменились. Отображение, используемое для вложения, является как минимум липшицевым и может даже быть ортогональной проекцией.

Зная только количество образцов, функция johnson_lindenstrauss_min_dim консервативно оценивает минимальный размер случайного подпространства, необходимый для ограничения искажения, вносимого случайной проекцией:

>>> from sklearn.random_projection import johnson_lindenstrauss_min_dim
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=0.5)
np.int64(663)
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=[0.5, 0.1, 0.01])
array([    663,   11841, 1112658])
>>> johnson_lindenstrauss_min_dim(n_samples=[1e4, 1e5, 1e6], eps=0.1)
array([ 7894,  9868, 11841])

Примеры

• См. Граница Джонсона — Линденштраусса для вложения с помощью случайных проекций: теоретическое объяснение леммы Джонсона — Линденштраусса и её эмпирическая проверка с использованием разреженных случайных матриц.

Литература

• Sanjoy Dasgupta и Anupam Gupta, 1999. Элементарное доказательство леммы Джонсона — Линденштраусса.

8.6.2. Гауссова случайная проекция

GaussianRandomProjection уменьшает размерность, проецируя исходное пространство входных данных на случайно сгенерированную матрицу, компоненты которой выбираются из следующего распределения \(N(0, \frac{1}{n_{components}})\).

Ниже приведен небольшой фрагмент, иллюстрирующий использование трансформера гауссовой случайной проекции:

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.GaussianRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

8.6.3. Разреженная случайная проекция

SparseRandomProjection уменьшает размерность, проецируя исходное пространство входных данных с помощью разреженной случайной матрицы.

Разреженные случайные матрицы служат альтернативой плотным матрицам гауссовой случайной проекции: они обеспечивают сопоставимое качество вложения, при этом требуют значительно меньше памяти и позволяют быстрее вычислять проецированные данные.

Если определить s = 1 / density, элементы случайной матрицы выбираются из распределения

где \(n_{\text{components}}\) — размер проецируемого подпространства. По умолчанию плотность ненулевых элементов установлена на минимальном уровне, рекомендованном Ping Li и соавторами: \(1 / \sqrt{n_{\text{features}}}\).

Ниже приведен небольшой фрагмент, иллюстрирующий использование трансформера разреженной случайной проекции:

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.SparseRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

Литература

• D. Achlioptas. 2003. Случайные проекции, удобные для баз данных: Джонсон — Линденштраусс с помощью бинарных монет. Journal of Computer and System Sciences 66 (2003), 671–687.
• Ping Li, Trevor J. Hastie и Kenneth W. Church. 2006. Очень разреженные случайные проекции. В материалах двенадцатой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных (KDD ‘06). ACM, Нью-Йорк, штат Нью-Йорк, США, 287–296.

8.6.4. Обратное преобразование

У трансформеров случайной проекции есть параметр compute_inverse_components. Если установить его в True, после создания случайной матрицы components_ во время обучения трансформер вычисляет псевдообратную матрицу и сохраняет её как inverse_components_. Матрица inverse_components_ имеет размер \(n_{features} \times n_{components}\) и всегда является плотной, независимо от того, является ли матрица компонентов разреженной или плотной. Поэтому, в зависимости от количества признаков и компонентов, она может занимать много памяти.

При вызове метода inverse_transform вычисляется произведение входной матрицы X и транспонированной обратной матрицы компонентов. Если обратная матрица компонентов была вычислена во время обучения, она повторно используется при каждом вызове inverse_transform. В противном случае она вычисляется заново при каждом вызове, что может быть затратным. Результат всегда плотный, даже если X является разреженной матрицей.

Ниже приведен небольшой пример кода, иллюстрирующий использование функции обратного преобразования:

>>> import numpy as np
>>> from sklearn.random_projection import SparseRandomProjection
>>> X = np.random.rand(100, 10000)
>>> transformer = SparseRandomProjection(
...   compute_inverse_components=True
... )
...
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)
>>> X_new_inversed = transformer.inverse_transform(X_new)
>>> X_new_inversed.shape
(100, 10000)
>>> X_new_again = transformer.transform(X_new_inversed)
>>> np.allclose(X_new, X_new_again)
True