2.2. Обучение на многообразиях

2.2.1. Введение

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

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

Для решения этой проблемы было разработано множество линейных методов уменьшения размерности с учителем и без учителя, таких как анализ главных компонент (PCA), анализ независимых компонент, линейный дискриминантный анализ и другие. Эти алгоритмы определяют конкретные критерии выбора «интересной» линейной проекции данных. Эти методы могут быть мощными, но часто пропускают важную нелинейную структуру в данных.

Обучение на многообразиях можно рассматривать как попытку обобщить линейные методы, такие как PCA, для чувствительности к нелинейной структуре данных. Хотя существуют варианты с учителем, типичная задача обучения на многообразиях — без учителя: она изучает многомерную структуру данных по самим данным без использования предварительно определённых классификаций.

Примеры

• См. Обучение на многообразиях для рукописных цифр: локально-линейное вложение, изокарта... для примера уменьшения размерности рукописных цифр.
• См. Сравнение методов обучения на многообразиях для примера уменьшения размерности набора данных с «кривой S».
• См. Визуализация структуры фондового рынка для примера использования обучения на многообразиях для отображения структуры фондового рынка на основе исторических цен акций.

Реализации обучения на многообразиях, доступные в scikit-learn, приведены ниже

2.2.2. Изокарта

Один из самых ранних подходов к обучению на многообразиях — алгоритм Isomap, сокращённо от Isometric Mapping. Isomap можно рассматривать как расширение многомерного шкалирования (MDS) или ядра PCA. Isomap стремится к вложению меньшей размерности, которое сохраняет геодезические расстояния между всеми точками. Isomap можно выполнить с объектом Isomap.

Ссылки

• “A global geometric framework for nonlinear dimensionality reduction” Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)

2.2.3. Локально-линейное вложение

Локально-линейное вложение (LLE) ищет проекцию данных меньшей размерности, сохраняя расстояния в локальных окрестностях. Его можно рассматривать как серию локальных анализов главных компонент, которые глобально сравниваются для нахождения наилучшего нелинейного вложения.

Локально-линейное вложение можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding.

Ссылки

• “Nonlinear dimensionality reduction by locally linear embedding” Roweis, S. & Saul, L. Science 290:2323 (2000)

2.2.4. Модифицированное локально-линейное вложение

Одна хорошо известная проблема с LLE — это проблема регуляризации. Когда количество соседей больше, чем количество входных измерений, матрица, определяющая каждый локальный район, имеет недостающую ранг. Для решения этой проблемы стандартное LLE применяет произвольный параметр регуляризации \(r\), который выбирается относительно следа локальной матрицы весов. Хотя формально можно показать, что при \(r \to 0\) решение сходится к желаемому вложению, нет гарантии, что оптимальное решение будет найдено для \(r > 0\). Эта проблема проявляется в виде искажения подлежащей геометрии многообразия вложениях.

Один из способов решения проблемы регуляризации — использование нескольких векторов весов в каждом районе. Это суть модифицированного локально-линейного вложения (MLLE). MLLE можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding, с ключевым словом method = 'modified'. Оно требует n_neighbors > n_components.

Литература

• “MLLE: Modified Locally Linear Embedding Using Multiple Weights” Zhang, Z. & Wang, J.

2.2.5. Вложение собственных значений Гессиана

Вложение собственных значений Гессиана (также известное как LLE, основанное на Гессиане: HLLE) — ещё один метод решения проблемы регуляризации LLE. Он основан на квадратичной форме Гессиана в каждом районе, которая используется для восстановления локальной линейной структуры. Хотя другие реализации отмечают его плохую масштабируемость с размером данных, sklearn реализует некоторые алгоритмические улучшения, которые делают его стоимость сопоставимой с другими вариантами LLE для малой размерности выхода. HLLE можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding, с ключевым словом method = 'hessian'. Оно требует n_neighbors > n_components * (n_components + 3) / 2.

Литература

• “Hessian Eigenmaps: Locally linear embedding techniques for high-dimensional data” Donoho, D. & Grimes, C. Proc Natl Acad Sci USA. 100:5591 (2003)

2.2.6. Спектральное вложение

Спектральное вложение — это подход к вычислению нелинейного вложения. Scikit-learn реализует вложение Лапласиана, которое находит низкоразмерное представление данных с помощью спектрального разложения графового Лапласиана. Сгенерированный граф можно рассматривать как дискретное приближение низкоразмерного многообразия в пространстве высокой размерности. Минимизация функции стоимости, основанной на графе, гарантирует, что точки, близкие друг к другу на многообразии, отображаются близко друг к другу в низкоразмерном пространстве, сохраняя локальные расстояния. Спектральное вложение можно выполнить с помощью функции spectral_embedding или её объектно-ориентированного аналога SpectralEmbedding.

Литература

• “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation” M. Belkin, P. Niyogi, Neural Computation, June 2003; 15 (6):1373-1396

2.2.7. Выравнивание локального касательного пространства

Хотя технически это не вариант LLE, выравнивание локального касательного пространства (LTSA) достаточно алгоритмически схоже с LLE, чтобы его можно было отнести к этой категории. Вместо того, чтобы фокусироваться на сохранении расстояний между соседями, как в LLE, LTSA стремится охарактеризовать локальную геометрию в каждом окрестности через его касательное пространство и выполняет глобальную оптимизацию для выравнивания этих локальных касательных пространств, чтобы обучить вложение. LTSA можно выполнить с помощью функции locally_linear_embedding или ее объектно-ориентированного аналога LocallyLinearEmbedding с ключевым словом method = 'ltsa'.

Литература

• “Principal manifolds and nonlinear dimensionality reduction via tangent space alignment” Zhang, Z. & Zha, H. Journal of Shanghai Univ. 8:406 (2004)

2.2.8. Многомерное шкалирование (MDS)

Многомерное шкалирование (MDS) ищет низкоразмерное представление данных, в котором расстояния хорошо соответствуют расстояниям в исходном пространстве высокой размерности.

В общем случае, MDS является техникой, используемой для анализа данных схожести или несхожести. Она пытается смоделировать данные схожести или несхожести как расстояния в геометрических пространствах. Данные могут представлять собой рейтинги схожести между объектами, частоты взаимодействия молекул или торговые индексы между странами.

Существуют два типа алгоритмов MDS: метрический и неметрический. В scikit-learn класс MDS реализует оба. В метрическом MDS входная матрица схожести происходит из метрики (и, следовательно, соблюдает неравенство треугольника), расстояния между двумя точками вывода затем устанавливаются как можно ближе к данным схожести или несхожести. В неметрической версии алгоритм будет пытаться сохранить порядок расстояний и, следовательно, искать монотонную связь между расстояниями во вложенном пространстве и схожестями/несхожестями.

Пусть \(S\) — матрица схожести, а \(X\) — координаты \(n\) входных точек. Расхождения \(\hat{d}_{ij}\) являются преобразованиями выбранных схожестей оптимальным образом. Тогда целевая функция, называемая напряжением, определяется как \(\sum_{i < j} d_{ij}(X) - \hat{d}_{ij}(X)\)

Неметрическое MDS

Неметрическое MDS фокусируется на упорядочении данных. Если \(S_{ij} > S_{jk}\), то вложение должно обеспечить \(d_{ij} < d_{jk}\). По этой причине мы обсуждаем это в терминах несхожестей (\(\delta_{ij}\)) вместо схожестей (\(S_{ij}\)). Обратите внимание, что несхожести легко получить из схожестей посредством простого преобразования, например, \(\delta_{ij}=c_1-c_2 S_{ij}\) для некоторых вещественных констант \(c_1, c_2\). Простой алгоритм для обеспечения правильного упорядочения — использовать монотонную регрессию \(d_{ij}\) на \(\delta_{ij}\), что даёт расхождения \(\hat{d}_{ij}\) в том же порядке, что и \(\delta_{ij}\).

Тривиальное решение этой проблемы — установить все точки в начале координат. Чтобы избежать этого, расхождения \(\hat{d}_{ij}\) нормализуются. Обратите внимание, что поскольку нас интересует только относительный порядок, наша цель должна быть инвариантной к простым сдвигам и масштабированию, однако напряжение, используемое в метрическом MDS, чувствительно к масштабированию. Для решения этой проблемы неметрическое MDS может использовать нормированное напряжение, известное как Stress-1, определённое как

\[\sqrt{\frac{\sum_{i < j} (d_{ij} - \hat{d}_{ij})^2}{\sum_{i < j} d_{ij}^2}}.\]

Использование нормированного Stress-1 можно включить, установив normalized_stress=True, однако оно совместимо только с неметрической задачей MDS и будет проигнорировано в метрическом случае.

Литература

• “Modern Multidimensional Scaling - Theory and Applications” Borg, I.; Groenen P. Springer Series in Statistics (1997)
• “Nonmetric multidimensional scaling: a numerical method” Kruskal, J. Psychometrika, 29 (1964)
• “Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis” Kruskal, J. Psychometrika, 29, (1964)

2.2.9. Встраивание с распределением t-Студента и случайным выбором ближайших соседей (t-SNE)

t-SNE (TSNE) преобразует сходства точек данных в вероятности. Сходства в исходном пространстве представлены гауссовыми совместными вероятностями, а сходства во встраиваемом пространстве — распределениями t-Студента. Это позволяет t-SNE особенно чувствительно реагировать на локальную структуру и имеет несколько преимуществ перед существующими методами:

• Выявление структуры на многих масштабах на одной карте
• Выявление данных, расположенных на нескольких различных многообразиях или кластерах
• Снижение тенденции к сжатию точек в центре

В то время как Isomap, LLE и их вариации лучше всего подходят для разворачивания одного непрерывного многообразия малой размерности, t-SNE будет сосредоточен на локальной структуре данных и будет склонен к выделению кластеризованных локальных групп выборок, как показано на примере S-образной кривой. Эта способность группировать выборки на основе локальной структуры может быть полезна для визуального разделения набора данных, состоящего из нескольких многообразий одновременно, как в случае набора данных цифр.

Расхождение Кульбака-Лейблера (KL) совместных вероятностей в исходном пространстве и встраиваемом пространстве будет минимизировано методом градиентного спуска. Обратите внимание, что расхождение KL не является выпуклым, т. е. несколько перезапусков с различными начальными значениями приведут к локальным минимумам расхождения KL. Поэтому иногда полезно попробовать разные начальные значения и выбрать встраивание с наименьшим расхождением KL.

Недостатки использования t-SNE примерно следующие:

• t-SNE является вычислительно затратным и может занимать несколько часов для наборов данных в миллионы выборок, в то время как PCA завершит работу за секунды или минуты
• Метод Barnes-Hut t-SNE ограничен встраиванием в двух или трех измерениях.
• Алгоритм является стохастическим, и несколько перезапусков с разными начальными значениями могут привести к различным встраиваниям. Однако совершенно законно выбрать встраивание с наименьшей ошибкой.
• Глобальная структура не сохраняется явно. Эта проблема смягчается инициализацией точек с помощью PCA (используя init='pca').

Литература

• “Визуализация данных высокой размерности с помощью t-SNE” van der Maaten, L.J.P.; Hinton, G. Журнал машинного обучения (2008)
• “t-Распределенное стохастическое встраивание ближайших соседей” van der Maaten, L.J.P.
• “Ускорение t-SNE с помощью древовидных алгоритмов” van der Maaten, L.J.P.; Журнал машинного обучения 15(октябрь):3221-3245, 2014.
• “Автоматизированные оптимизированные параметры для T-распределенного стохастического встраивания ближайших соседей улучшают визуализацию и анализ больших наборов данных” Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., Nature Communications 10, 5415 (2019).

2.2.10. Рекомендации по практическому применению

• Убедитесь, что для всех признаков используется один и тот же масштаб. Методы обучения на многообразиях основаны на поиске ближайших соседей, поэтому в противном случае алгоритм может работать плохо. См. StandardScaler для удобных способов масштабирования разнородных данных.
• Ошибка восстановления, вычисленная каждой процедурой, может использоваться для выбора оптимальной размерности выхода. Для многообразия размерности \(d\), вложенного в параметрическое пространство размерности \(D\), ошибка восстановления будет уменьшаться по мере увеличения n_components, пока не достигнет n_components == d.
• Обратите внимание, что шумные данные могут «складывать» многообразие, по сути, выступая мостом между частями многообразия, которые в противном случае были бы хорошо разделены. Обучение на многообразиях на шумных и/или неполных данных является активной областью исследований.
• Определенные конфигурации входных данных могут привести к сингулярным матрицам весов, например, когда более двух точек в наборе данных идентичны или когда данные разделены на разрозненные группы. В этом случае solver='arpack' не сможет найти нулевое пространство. Самый простой способ решения этой проблемы — использовать solver='dense', который будет работать с сингулярной матрицей, хотя это может быть очень медленно в зависимости от количества входных точек. В качестве альтернативы можно попытаться понять причину сингулярности: если она вызвана разрозненными наборами, увеличение n_neighbors может помочь. Если она вызвана идентичными точками в наборе данных, удаление этих точек может помочь.