2.5. Декомпозиция сигналов на компоненты (Матричная факторизация)

2.5.1. Анализ главных компонент (Principal component analysis - PCA)

2.5.1.1. Точный PCA и вероятностная интерпретация

PCA используется для разложения многомерного набора данных на множество последовательных ортогональных компонент, которые объясняют максимальную часть дисперсии. В scikit-learn PCA реализован как объект transformer, который изучает \(n\) компоненты в своем методе fit, и может быть использован на новых данных для проецирования их на эти компоненты.

PCA центрирует, но не масштабирует входные данные для каждого признака перед применением SVD. Необязательный параметр whiten=True позволяет проецировать данные на сингулярное пространство, масштабируя каждую компоненту до единичной дисперсии. Это часто бывает полезно, если последующие модели делают сильные предположения об изотропии сигнала: например, это касается метода опорных векторов (SVM) с ядром RBF и алгоритма кластеризации K-Means.

Ниже приведен пример набора данных Ирис, состоящего из 4 признаков, спроецированных на 2 измерения, которые объясняют наибольшую дисперсию:

Объект PCA также обеспечивает вероятностную интерпретацию PCA, которая может дать вероятность данных, основанную на количестве дисперсии, которую они объясняют. Как таковой, он реализует метод score, который можно использовать при перекрестной проверке:

Примеры:

• PCA example with Iris Data-set

• Comparison of LDA and PCA 2D projection of Iris dataset

• Model selection with Probabilistic PCA and Factor Analysis (FA)

2.5.1.2. Инкрементальный PCA

Объект PCA очень полезен, но имеет определенные ограничения для больших наборов данных. Самое большое ограничение заключается в том, что PCA поддерживает только пакетную обработку, то есть все обрабатываемые данные должны помещаться в оперативной памяти. Объект IncrementalPCA использует другую форму обработки и позволяет выполнять частичные вычисления, которые почти точно соответствуют результатам PCA при обработке данных в мини-пакетном режиме. IncrementalPCA позволяет реализовать внеядерный (out-of-core) анализ главных компонент либо путем:

• Используя его метод partial_fit на фрагментах данных, последовательно получаемых с локального жесткого диска или из сетевой базы данных.

• Вызывая его метод fit на файле, отображенном в памяти, с помощью numpy.memmap.

IncrementalPCA хранит только оценки компонентных и шумовых дисперсий, чтобы обновлять explained_variance_ratio_ инкрементально. Поэтому использование памяти зависит от количества выборок в батче, а не от количества обрабатываемых выборок в наборе данных.

Как и в PCA, IncrementalPCA центрирует, но не масштабирует входные данные для каждого признака перед применением SVD.

Примеры:

• Incremental PCA

2.5.1.3. PCA с использованием рандомизированного SVD

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

Например, если мы работаем с черно-белыми картинками 64x64 пикселя для распознавания лиц, размерность данных составляет 4096, и обучение метода опорных векторов RBF на таких широких данных будет медленным. Кроме того, мы знаем, что внутренняя размерность данных гораздо меньше 4096, поскольку все изображения человеческих лиц выглядят несколько одинаково. Образцы лежат на многообразии гораздо меньшей размерности (например, около 200). Алгоритм PCA может быть использован для линейного преобразования данных с одновременным снижением размерности и сохранением большей части объясненной дисперсии.

Класс PCA, используемый с дополнительным параметром svd_solver='randomized', очень полезен в этом случае: поскольку мы собираемся отбросить большинство сингулярных векторов, гораздо эффективнее ограничить вычисления приближенной оценкой сингулярных векторов, которые мы оставим для выполнения преобразования.

Например, ниже показаны 16 образцов портретов (с центром в районе 0.0) из набора данных Olivetti. Справа показаны первые 16 сингулярных векторов, преобразованных в портреты. Поскольку нам нужны только 16 первых сингулярных векторов из набора данных размером \(n_{samples} = 400\) и \(n_{features} = 64 \times 64 = 4096\), время вычислений составляет менее 1 с:

Если отметить \(n_{\max} = \max(n_{\mathrm{samples}}, n_{\mathrm{features}})\) и \(n_{\min} = \min(n_{\mathrm{samples}}, n_{\mathrm{features}})\), то временная сложность рандомизированного PCA составляет \(O(n_{\max}^2 \cdot n_{\mathrm{components}})\) вместо \(O(n_{\max}^2 \cdot n_{\min})\) для точного метода, реализованного в PCA.

Объем памяти, занимаемый рандомизированным PCA, также пропорционален \(2 \cdot n_{\max} \cdot n_{\mathrm{components}}\) вместо \(n_{\max} \cdot n_{\min}\) для точного метода.

Замечание: реализация inverse_transform в PCA с svd_solver='randomized' не является точным обратным преобразованием transform даже при whiten=False (по умолчанию).

Примеры:

• Faces recognition example using eigenfaces and SVMs

• Faces dataset decompositions

Ссылки:

• Алгоритм 4.3 в “Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions” Halko, et al., 2009

• “An implementation of a randomized algorithm for principal component analysis” A. Szlam et al. 2014

2.5.1.4. Анализ разреженных главных компонентов (SparsePCA и MiniBatchSparsePCA)

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

Mini-batch sparse PCA (MiniBatchSparsePCA) - это вариант SparsePCA, который быстрее, но менее точен. Увеличение скорости достигается за счет перебора небольших фрагментов набора признаков при заданном количестве итераций.

Анализ главных компонент (PCA) имеет тот недостаток, что компоненты, извлеченные этим методом, имеют исключительно плотные выражения, то есть имеют ненулевые коэффициенты при выражении в виде линейных комбинаций исходных переменных. Это может затруднить интерпретацию. Во многих случаях реальные компоненты можно более естественно представить как разреженные векторы; например, при распознавании лиц компоненты могут быть естественным образом отображены на части лиц.

Разрозненные главные компоненты дают более упрощенное и интерпретируемое представление, четко подчеркивая, какие из исходных признаков вносят вклад в различия между образцами.

Следующий пример иллюстрирует 16 компонентов, извлеченных с помощью разреженного PCA из набора данных Olivetti faces. Видно, как член регуляризации приводит к появлению большого количества нулей. Кроме того, естественная структура данных приводит к тому, что ненулевые коэффициенты располагаются рядом по вертикали. Модель не обеспечивает этого математически: каждый компонент является вектором \(h \in \mathbf{R}^{4096}\), и нет понятия вертикальной смежности, кроме как при удобной для человека визуализации в виде изображений 64x64 пикселей. Тот факт, что показанные ниже компоненты выглядят локальными, является следствием присущей данным структуры, благодаря которой такие локальные паттерны минимизируют ошибку реконструкции. Существуют нормы, вызывающие разреженность, которые учитывают смежность и различные виды структуры; обзор таких методов см. в [Jen09].

Более подробно о том, как использовать Sparse PCA, см. в разделе “Примеры” ниже.

Обратите внимание, что существует множество различных формулировок задачи Sparse PCA. Та, что реализована здесь, основана на [Mrl09] . Решаемая задача оптимизации - это задача PCA (изучение словаря) со штрафом \(\ell_1\) на компоненты:

\[\begin{split}(U^*, V^*) = \underset{U, V}{\operatorname{arg\,min\,}} & \frac{1}{2} ||X-UV||_{\text{Fro}}^2+\alpha||V||_{1,1} \\ \text{subject to } & ||U_k||_2 <= 1 \text{ for all } 0 \leq k < n_{components}\end{split}\]

\(||.||_{\text{Fro}}\) обозначает норму Фробениуса, а \(||.||_{1,1}\) обозначает норму матрицы по записи, которая является суммой абсолютных значений всех записей в матрице.

Матричная норма, вызывающая разреженность \(||.||_{1,1}\), также предотвращает обучение компонентов из шума, когда доступно мало обучающих выборок. Степень штрафа (и, следовательно, разреженности) можно регулировать с помощью гиперпараметра alpha. Малые значения приводят к мягкой регуляризованной факторизации, в то время как большие значения уменьшают многие коэффициенты до нуля.

Примечание

Несмотря на то, что класс MiniBatchSparsePCA соответствует духу онлайн алгоритма, он не реализует partial_fit, потому что алгоритм работает онлайн в направлении признаков, а не образцов.

Примеры:

• Faces dataset decompositions

Ссылки:

[Mrl09]

“Online Dictionary Learning for Sparse Coding” J. Mairal, F. Bach, J. Ponce, G. Sapiro, 2009

[Jen09]

“Structured Sparse Principal Component Analysis” R. Jenatton, G. Obozinski, F. Bach, 2009

2.5.2. Ядерный анализ главных компонент (kPCA)

2.5.2.1. Точный ядерный PCA

KernelPCA - это расширение PCA, в котором достигается нелинейное сокращение размерности за счет использования ядер (см. Парные метрики, Cходство и Ядра) [Scholkopf1997]. Оно имеет множество применений, включая шумоподавление, сжатие и структурированное предсказание (оценка зависимостей по ядрам). KernelPCA поддерживает как transform, так и inverse_transform.

Примечание

KernelPCA.inverse_transform опирается на хребет ядра для обучения функции, отображающей образцы из базиса PCA в исходное пространство признаков [Bakir2003]. Таким образом, реконструкция, полученная с помощью KernelPCA.inverse_transform, является приближенной. Подробнее см. пример по ссылке ниже.

Примеры:

• Kernel PCA

Ссылки:

[Scholkopf1997]

Schölkopf, Bernhard, Alexander Smola, and Klaus-Robert Müller. “Kernel principal component analysis.” International conference on artificial neural networks. Springer, Berlin, Heidelberg, 1997.

[Bakir2003]

Bakır, Gökhan H., Jason Weston, and Bernhard Schölkopf. “Learning to find pre-images.” Advances in neural information processing systems 16 (2003): 449-456.

2.5.2.2. Выбор алгоритма для Kernel PCA

Если в PCA число компонент ограничено числом признаков, то в KernelPCA число компонент ограничено числом выборок. Многие реальные наборы данных содержат большое количество образцов! В таких случаях поиск всех компонент с помощью полного kPCA является пустой тратой времени, так как данные в основном описываются первыми несколькими компонентами (например, n_components<=100). Другими словами, центрированная матрица Грама, которая подвергается Спектральному разложению в процессе подгонки Kernel PCA, имеет эффективный ранг, который намного меньше ее размера. Это та ситуация, когда приближенный Eigensolver может обеспечить ускорение при очень малой потере точности.

Eigensolver Click for more details

Необязательный параметр eigen_solver='randomized' может быть использован для значительного сокращения времени вычислений, когда количество запрашиваемых n_components мало по сравнению с количеством образцов. Он использует методы рандомизированного разложения для нахождения приближенного решения за более короткое время.

Временная сложность рандомизированного KernelPCA составляет \(O(n_{\mathrm{samples}}^2 \cdot n_{\mathrm{components}})\) вместо \(O(n_{\mathrm{samples}}^3)\) для точного метода, реализованного с eigen_solver='dense'.

Объем памяти рандомизированного KernelPCA также пропорционален \(2 \cdot n_{\mathrm{samples}} \cdot n_{\mathrm{components}}\) вместо \(n_{\mathrm{samples}}^2\) для точного метода.

Примечание: эта техника такая же, как и в PCA с использованием рандомизированного SVD.

В дополнение к двум вышеперечисленным алгоритмам, eigen_solver='arpack' может быть использован как альтернативный способ получения приближенного разложения. На практике этот метод обеспечивает приемлемое время выполнения только в том случае, если количество компонентов, которые необходимо найти, очень мало. По умолчанию он включен, когда желаемое число компонентов меньше 10 (strict), а число образцов больше 200 (strict). Подробности см. в разделе KernelPCA.

Ссылки:

• dense solver: scipy.linalg.eigh documentation

• randomized solver:

  • Algorithm 4.3 in “Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions” Halko, et al. (2009)

  • “An implementation of a randomized algorithm for principal component analysis” A. Szlam et al. (2014)

• arpack solver: scipy.sparse.linalg.eigsh documentation R. B. Lehoucq, D. C. Sorensen, and C. Yang, (1998)

2.5.3. Усеченное разложение сингулярных значений и латентный семантический анализ (Latent Semantic Analysis - LSA)

TruncatedSVD реализует вариант разложения по сингулярным значениям (singular value decomposition - SVD), который вычисляет только \(k\) наибольших сингулярных значений, где \(k\) - заданный пользователем параметр.

TruncatedSVD очень похож на PCA, но отличается тем, что матрицу \(X\) не нужно центрировать. Когда из значений признаков вычитаются столбцовые (по каждому признаку) средние значения \(X\), усеченный SVD для результирующей матрицы эквивалентен PCA.

Об усеченном SVD и латентном семантическом анализе (latent semantic analysis - LSA). Click for more details

Когда усеченный SVD применяется к матрицам терминов и документ (как возвращается CountVectorizer или TfidfVectorizer), это преобразование известно как латентный семантический анализ (latent semantic analysis - LSA), поскольку оно преобразует такие матрицы в “семантическое” пространство низкой размерности. В частности, известно, что LSA борется с эффектами синонимии и полисемии (оба эти явления означают наличие нескольких значений у одного слова), которые приводят к тому, что матрицы терминов и документов становятся слишком разреженными и демонстрируют низкое сходство по таким показателям, как косинусное сходство (cosine similarity).

Примечание

LSA также известен как скрытое семантическое индексирование, (latent semantic indexing - LSI), хотя строго это относится к его использованию в постоянных индексах для целей поиска информации.

С математической точки зрения, усеченный SVD, примененный к обучающим выборкам \(X\), дает низкоранговую аппроксимацию \(X\):

\[X \approx X_k = U_k \Sigma_k V_k^\top\]

После этой операции \(U_k \Sigma_k\) - это преобразованный обучающий набор с \(k\) признаками (называемыми в API n_components).

Чтобы также преобразовать тестовый набор \(X\), мы умножаем его на \(V_k\):

\[X' = X V_k\]

Примечание

В большинстве работ по LSA в литературе по обработке естественного языка (NLP) и информационному поиску (IR) оси матрицы \(X\) поменяны местами, так что она имеет форму n_features × n_samples.

Мы представляем LSA в другом виде, который лучше соответствует API scikit-learn, но найденные сингулярные значения остаются теми же.

Хотя преобразование TruncatedSVD работает с любой матрицей признаков, в LSA / в обработке текста рекомендуется использовать его для матриц tf-idf, а не для сырых подсчетов частот. В частности, следует включить сублинейное масштабирование и обратную частоту документа (sublinear_tf=True, use_idf=True), чтобы приблизить значения признаков к гауссовскому распределению, компенсируя ошибочные предположения LSA о текстовых данных.

Примеры:

• Clustering text documents using k-means

Ссылки:

• Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze (2008), Introduction to Information Retrieval, Cambridge University Press, chapter 18: Matrix decompositions & latent semantic indexing

2.5.4. Обучение на основе словоря

2.5.4.1. Разреженное кодирование с предварительно вычисленным словарем

Объект SparseCoder это модель, которая может быть использовано для преобразования сигналов в разреженную линейную комбинацию атомов из фиксированного, предварительно вычисленного словаря, такого как дискретный вейвлет-базис (wavelet basis известного как Вейвлет-преобразование). Поэтому этот объект не реализует метод fit. Преобразование сводится к задаче разреженного кодирования: найти представление данных в виде линейной комбинации как можно меньшего числа атомов словаря. Все варианты обучения словаря реализуют следующие методы преобразования, управляемые через параметр инициализации transform_method:

• Ортогональное преобразование (Ортогональное соответствие (Orthogonal Matching Pursuit - OMP))

• Регрессия наименьшего угла (Регрессия наименьшего угла)

• Лассо, вычисленное по регрессии наименьшего угла

• Лассо с использованием координатного спуска (Лассо (Lasso))

• Пороговое выделение

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

Объекты обучения по словарю предлагают через параметр split_code возможность разделить положительные и отрицательные значения в результатах разреженного кодирования. Это полезно, когда словарное обучение используется для извлечения признаков, которые будут использоваться для контролируемого обучения, поскольку позволяет алгоритму обучения присваивать отрицательным нагрузкам определенного атома различные веса по сравнению с соответствующими положительными нагрузками.

split_code для одного образца имеет длину 2 * n_components и строится по следующему правилу: Сначала вычисляется обычный код длины n_components. Затем первые n_components записи split_code заполняются положительной частью вектора регулярного кода. Вторая половина разделенного кода заполняется отрицательной частью кодового вектора, только с положительным знаком. Таким образом, split_code является неотрицательным.

Примеры:

• Sparse coding with a precomputed dictionary

2.5.4.2. Обучение по общему словарю

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

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

Изучение словаря - это оптимизационная задача, решаемая путем альтернативного обновления разреженного кода, как решение нескольких задач Лассо, считая словарь фиксированным, а затем обновляя словарь для наилучшего соответствия разреженному коду.

\[\begin{split}(U^*, V^*) = \underset{U, V}{\operatorname{arg\,min\,}} & \frac{1}{2} ||X-UV||_{\text{Fro}}^2+\alpha||U||_{1,1} \\ \text{subject to } & ||V_k||_2 <= 1 \text{ for all } 0 \leq k < n_{\mathrm{atoms}}\end{split}\]

\(||.||_{\text{Fro}}\) означает норму Фробениуса, а \(||.||_{1,1}\) - норму матрицы по входу, которая представляет собой сумму абсолютных значений всех записей в матрице. После использования такой процедуры для подгонки словаря преобразование представляет собой просто шаг разреженного кодирования, который имеет одинаковую реализацию со всеми объектами обучения словарям (см. Разреженное кодирование с предварительно вычисленным словарем).

Также можно ограничить словарь и/или код положительными значениями, чтобы соответствовать ограничениям, которые могут присутствовать в данных. Ниже показаны лица с различными ограничениями позитивности. Красным цветом обозначены отрицательные значения, синим - положительные, а белым - нули.

На следующем изображении показано, как выглядит словарь, составленный на основе фрагментов изображения размером 4x4 пикселя, извлеченных из части изображения морды енота.

Примеры:

• Image denoising using dictionary learning

Ссылки:

• “Online dictionary learning for sparse coding” J. Mairal, F. Bach, J. Ponce, G. Sapiro, 2009

2.5.4.3. Мини-батчевое обучение словаря

MiniBatchDictionaryLearning реализует более быструю, но менее точную версию алгоритма обучения словарей, которая лучше подходит для больших наборов данных.

По умолчанию, MiniBatchDictionaryLearning делит данные на мини-батчи и оптимизирует в режиме онлайн, перебирая мини-батчи в течение заданного количества итераций. Однако на данный момент в нем не реализовано условие остановки.

Модель также реализует partial_fit, который обновляет словарь, выполняя итерацию только один раз над мини-батчем. Это может быть использовано для онлайн-обучения, когда данные не доступны с самого начала, или когда данные не помещаются в память.

Кластеризация для обучения по словарю

Обратите внимание, что при использовании обучения по словарю для извлечения представления (например, для разреженного кодирования) кластеризация может быть хорошим прокси для изучения словаря. Например, модель MiniBatchKMeans является вычислительно эффективным и реализует обучение в режиме реального времени с помощью метода partial_fit.

Пример: Online learning of a dictionary of parts of faces

2.5.5. Факторный анализ

В обучении без учителя у нас есть только набор данных \(X = \{x_1, x_2, \dots, x_n \}\). Как можно описать этот набор данных математически? Очень простая модель непрерывной латентной переменной (continuous latent variable) для \(X\) имеет вид

\[x_i = W h_i + \mu + \epsilon\]

Вектор \(h_i\) называется “латентным”, потому что он ненаблюдаем. \(\epsilon\) рассматривается как шумовой член, распределенный по гауссу со средним 0 и ковариацией \(\Psi\) (т.е. \(\epsilon \sim \mathcal{N}(0, \Psi)\)), \(\mu\) - некоторый произвольный вектор смещения. Такая модель называется “генеративной”, поскольку она описывает, как \(x_i\) генерируется из \(h_i\). Если мы используем все \(x_i\) как столбцы матрицы \(\mathbf{X}\) и все \(h_i\) как столбцы матрицы \(\mathbf{H}\), то мы можем написать (с соответствующими определениями \(\mathbf{M}\) и \(\mathbf{E}\)):

\[\mathbf{X} = W \mathbf{H} + \mathbf{M} + \mathbf{E}\]

Другими словами, мы разложили (декомпозировали) матрицу \(\mathbf{X}\).

Если задано \(h_i\), то из приведенного выше уравнения автоматически вытекает следующая вероятностная интерпретация:

\[p(x_i|h_i) = \mathcal{N}(Wh_i + \mu, \Psi)\]

Для полной вероятностной модели нам также необходимо предварительное распределение для латентной переменной \(h\). Наиболее простое предположение (основанное на свойствах гауссова распределения) - это \(h \sim \mathcal{N}(0, \mathbf{I})\). Это даёт Гауссиану в качестве маргинального распределения \(x\):

\[p(x) = \mathcal{N}(\mu, WW^T + \Psi)\]

Теперь, без дальнейших предположений, идея наличия латентной переменной \(h\) была бы излишней - \(x\) может быть полностью смоделировано со средним и ковариацией. Нам нужно наложить какую-то более специфическую структуру на один из этих двух параметров. Простое дополнительное предположение касается структуры ковариации ошибки \(\Psi\):

• \(\Psi = \sigma^2 \mathbf{I}\): Это предположение приводит к вероятностной модели PCA.

• \(\Psi = \mathrm{diag}(\psi_1, \psi_2, \dots, \psi_n)\): Эта модель называется FactorAnalysis, классическая статистическая модель. Матрицу W иногда называют “матрицей факторной нагрузки”.

Обе модели, по сути, оценивают гауссиану с ковариационной матрицей низкого ранга. Поскольку обе модели являются вероятностными, они могут быть интегрированы в более сложные модели, например, в анализ смесей факторов (Mixture of Factor Analysers). Если предполагаются негауссовские приоритеты на латентные переменные, то получаются совсем другие модели (например, FastICA).

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

Основное преимущество факторного анализа перед PCA заключается в том, что он может моделировать дисперсию в каждом направлении входного пространства независимо (гетероскедастический шум):

Это позволяет лучше выбирать модели, чем вероятностный PCA в присутствии гетероскедастического шума:

За факторным анализом часто следует вращение факторов (с параметром rotation), обычно для улучшения интерпретируемости. Например, вращение Varimax максимизирует сумму дисперсий квадратичных нагрузок, т.е. имеет тенденцию к получению более разреженных факторов, на которые влияют лишь несколько признаков в каждом (“простая структура”). См., например, первый пример ниже.

Примеры:

• Factor Analysis (with rotation) to visualize patterns

• Model selection with Probabilistic PCA and Factor Analysis (FA)

2.5.6. Независимый компонентный анализ (Independent component analysis - ICA)

Анализ независимых компонент разделяет многомерный сигнал на аддитивные подкомпоненты, которые максимально независимы. Он реализован в scikit-learn с помощью алгоритма Fast ICA. Обычно ICA используется не для снижения размерности, а для разделения наложенных сигналов. Поскольку модель ICA не включает шумовой член, для корректности модели необходимо применить “отбеливание” (whitening). Это можно сделать внутренне с помощью аргумента whiten или вручную, используя один из вариантов PCA.

Классически используется для разделения смешанных сигналов (проблема, известная как слепое разделение источников), как в примере ниже:

ICA также может использоваться как еще одно нелинейное разложение, которое находит компоненты с некоторой разреженностью:

Примеры:

• Blind source separation using FastICA

• FastICA on 2D point clouds

• Faces dataset decompositions

2.5.7. Факторизация неотрицательных матриц (Non-negative matrix factorization - NMF или NNMF)

2.5.7.1. NMF с нормой Фробениуса

NMF [1] - альтернативный подход к декомпозиции, предполагающий, что данные и компоненты неотрицательны. NMF может быть подключен вместо PCA или его вариантов, в случаях, когда матрица данных не содержит отрицательных значений.

Находит разложение выборки \(X\) на две матрицы \(W\) и \(H\) из неотрицательных элементов, оптимизируя расстояние \(d\) между \(X\) и произведением матриц \(WH\). Наиболее широко используемой функцией расстояния является квадратичная норма Фробениуса, которая является очевидным расширением евклидовой нормы на матрицы:

\[d_{\mathrm{Fro}}(X, Y) = \frac{1}{2} ||X - Y||_{\mathrm{Fro}}^2 = \frac{1}{2} \sum_{i,j} (X_{ij} - {Y}_{ij})^2\]

В отличие от PCA, представление вектора получается аддитивным способом, путем наложения компонент, без вычитания. Такие аддитивные модели эффективны для представления изображений и текста.

В [Hoyer, 2004] [2] было замечено, что при тщательном ограничении NMF может создавать представление набора данных на основе частей, что приводит к интерпретируемым моделям. В следующем примере показаны 16 разреженных компонент, найденных с помощью NMF из изображений в наборе данных Olivetti faces, в сравнении с собственными значениями PCA.

Атрибут init определяет применяемый метод инициализации, который оказывает большое влияние на производительность метода. NMF реализует метод Nonnegative Double Singular Value Decomposition (NNDSVD).

NNDSVD [4] основан на двух процессах SVD, один из которых аппроксимирует матрицу данных, а другой аппроксимирует положительные сечения результирующих частичных коэффициентов SVD, используя алгебраическое свойство матриц единичного ранга.

Базовый алгоритм NNDSVD лучше подходит для разреженной факторизации. Его варианты NNDSVDa (в котором все нули устанавливаются равными среднему значению всех элементов данных) и NNDSVDar (в котором нули устанавливаются на случайные возмущения, меньшие, чем среднее значение данных, деленное на 100) рекомендуются в плотном случае.

Обратите внимание, что алгоритм Multiplicative Update (‘mu’) не может обновлять нули, присутствующие при инициализации, поэтому он приводит к худшим результатам при использовании совместно с базовым алгоритмом NNDSVD, который вводит много нулей; в этом случае следует предпочесть NNDSVDa или NNDSVDar.

NMF можно также инициализировать правильно масштабированными случайными неотрицательными матрицами, задав init="random". Для контроля воспроизводимости в random_state можно также передать целочисленное значение (seed) или RandomState.

В NMF к функции потерь могут быть добавлены L1 и L2 регуляризации модели. L2 использует норму Фробениуса, а L1 - поэлементное нармирование. Как и в ElasticNet, мы управляем комбинацией L1 и L2 с помощью параметра l1_ratio (\(\rho\)), а интенсивностью регуляризации с помощью параметров alpha_W и alpha_H (\(\alpha_W\) и \(\alpha_H\)). Регуляризация масштабируются по количеству выборок (\(n\_samples\)) для H и количеству признаков (\(n\_features\)) для W, чтобы их влияние было сбалансировано по отношению друг к другу и к члену подгонки данных, насколько это возможно, независимо от размера обучающего набора. Тогда члены имеют вид:

\[(\alpha_W \rho ||W||_1 + \frac{\alpha_W(1-\rho)}{2} ||W||_{\mathrm{Fro}} ^ 2) * n\_features + (\alpha_H \rho ||H||_1 + \frac{\alpha_H(1-\rho)}{2} ||H||_{\mathrm{Fro}} ^ 2) * n\_samples\]

а регуляризованная целевая функция имеет вид:

\[d_{\mathrm{Fro}}(X, WH) + (\alpha_W \rho ||W||_1 + \frac{\alpha_W(1-\rho)}{2} ||W||_{\mathrm{Fro}} ^ 2) * n\_features + (\alpha_H \rho ||H||_1 + \frac{\alpha_H(1-\rho)}{2} ||H||_{\mathrm{Fro}} ^ 2) * n\_samples\]

2.5.7.2. NMF с бета-расхождением

Как было описано ранее, наиболее широко используемой функцией расстояния является квадратичная норма Фробениуса, которая является очевидным расширением евклидовой нормы на матрицы:

\[d_{\mathrm{Fro}}(X, Y) = \frac{1}{2} ||X - Y||_{Fro}^2 = \frac{1}{2} \sum_{i,j} (X_{ij} - {Y}_{ij})^2\]

В NMF могут использоваться и другие функции расстояния, например, (обобщенная) дивергенция Кульбака-Лейблера (KL), также называемая I-дивергенцией:

\[d_{KL}(X, Y) = \sum_{i,j} (X_{ij} \log(\frac{X_{ij}}{Y_{ij}}) - X_{ij} + Y_{ij})\]

Или дивергенция Итакура-Сайто (IS):

\[d_{IS}(X, Y) = \sum_{i,j} (\frac{X_{ij}}{Y_{ij}} - \log(\frac{X_{ij}}{Y_{ij}}) - 1)\]

Эти три расстояния являются частными случаями семейства бета-дивергенций, с \(\beta = 2, 1, 0\) соответственно [6]. Бета-дивергенция определяется :

\[d_{\beta}(X, Y) = \sum_{i,j} \frac{1}{\beta(\beta - 1)}(X_{ij}^\beta + (\beta-1)Y_{ij}^\beta - \beta X_{ij} Y_{ij}^{\beta - 1})\]

Заметим, что это определение недействительно, если \(\beta \in (0; 1)\), однако оно может быть непрерывно расширено до определений \(d_{KL}\) и \(d_{IS}\) соответственно.

Алгоритм, реализующие NMF. Click for more details

NMF реализует два алгоритма, использующие координатный спуск (Coordinate Descent - ‘cd’) [5] и мультипликативное обновление (Multiplicative Update - ‘mu’) [6]. Алгоритм ‘mu’ может оптимизировать любое бета-расхождение, включая, конечно, норму Фробениуса (\(\beta=2\)), (обобщенную) дивергенцию Куллбэка-Лейблера (\(\beta=1\)) и дивергенцию Итакуры-Сайто (\(\beta=0\)). Обратите внимание, что для \(\beta \in (1; 2)\) алгоритм ‘mu’ работает значительно быстрее, чем для других значений \(\beta\). Заметим также, что при отрицательном (или 0, т.е. “Итакур-Сайто”) \(\beta\) входная матрица не может содержать нулевых значений.

Алгоритм ‘cd’ может оптимизировать только норму Фробениуса. Из-за невыпуклости NMF различные алгоритмы могут сходиться к разным минимумам даже при оптимизации одной и той же функции расстояния.

NMF лучше всего использовать с методом fit_transform, который возвращает матрицу W. Матрица H хранится в модели в атрибуте components_; метод transform разложит новую матрицу X_new на основе этих сохраненных компонентов:

>>> import numpy as np
>>> X = np.array([[1, 1], [2, 1], [3, 1.2], [4, 1], [5, 0.8], [6, 1]])
>>> from sklearn.decomposition import NMF
>>> model = NMF(n_components=2, init='random', random_state=0)
>>> W = model.fit_transform(X)
>>> H = model.components_
>>> X_new = np.array([[1, 0], [1, 6.1], [1, 0], [1, 4], [3.2, 1], [0, 4]])
>>> W_new = model.transform(X_new)

Примеры:

• Faces dataset decompositions

• Topic extraction with Non-negative Matrix Factorization and Latent Dirichlet Allocation

2.5.7.3. Мини-батчевая факторизация неотрицательной матрицы

MiniBatchNMF [7] реализует более быструю, но менее точную версию неотрицательной матричной факторизации (т.е. NMF), лучше подходящую для больших наборов данных.

По умолчанию MiniBatchNMF разбивает данные на мини-батчи и оптимизирует NMF-модель в режиме онлайн, перебирая мини-батчи в течение заданного количества итераций. Параметр batch_size управляет размером батчей.

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

Модель также реализует partial_fit, который обновляет H, выполняя итерацию только один раз над мини-батчем. Это может быть использовано для онлайн-обучения, когда данные не доступны с самого начала, или когда данные не помещаются в память.

Ссылки:

[1]

“Learning the parts of objects by non-negative matrix factorization” D. Lee, S. Seung, 1999

[2]

“Non-negative Matrix Factorization with Sparseness Constraints” P. Hoyer, 2004

[4]

“SVD based initialization: A head start for nonnegative matrix factorization” C. Boutsidis, E. Gallopoulos, 2008

[5]

“Fast local algorithms for large scale nonnegative matrix and tensor factorizations.” A. Cichocki, A. Phan, 2009

[6] (1,2)

“Algorithms for nonnegative matrix factorization with the beta-divergence” C. Fevotte, J. Idier, 2011

[7]

“Online algorithms for nonnegative matrix factorization with the Itakura-Saito divergence” A. Lefevre, F. Bach, C. Fevotte, 2011

2.5.8. Латентное размещение Дирихле (Latent Dirichlet Allocation - LDA)

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

Графовая модель LDA - это трехуровневая генеративная модель:

Примечание к обозначениям, представленным в графической модели выше, которые можно найти в Hoffman et al. (2013):

• Корпус - это коллекция \(D\) документов.

• Документ - это последовательность \(N\) слов.

• В корпусе есть \(K\) тем.

• “Коробки” представляют собой повторную выборку.

В графической модели каждый узел является случайной переменной и играет определенную роль в генеративном процессе. Заштрихованный узел указывает на наблюдаемую переменную, а незаштрихованный - на скрытую (латентную) переменную. В данном случае слова в корпусе - это единственные данные, которые мы наблюдаем. Латентные переменные определяют случайную смесь тем в корпусе и распределение слов в документах. Цель LDA - использовать наблюдаемые слова для вывода скрытой структуры тем.

Подробности о моделировании текстовых корпусов Click for more details

При моделировании текстовых корпусов модель предполагает следующий генеративный процесс для корпуса с \(D\) документов и \(K\) тем, причем \(K\) соответствует n_components в API:

1. Для каждой темы \(k \in K\), строим \(\beta_k \sim \mathrm{Dirichlet}(\eta)\). Это дает распределение по словам, т.е. вероятность появления слова в теме \(k\). \(\eta\) соответствует topic_word_prior.

2. Для каждого документа \(d \in D\) строим пропорции тем \(\theta_d \sim \mathrm{Dirichlet}(\alpha)\). \(\alpha\) соответствует doc_topic_prior.

3. Для каждого слова \(i\) в документе \(d\):

   1. Формируется заданнная тема \(z_{di} \sim \mathrm{Multinomial} (\theta_d)\).

   2. Формируется наблюдаемое слово \(w_{ij} \sim \mathrm{Multinomial} (\beta_{z_{di}})\).

Для оценки параметров, апостериорное распределение имеет вид:

\[p(z, \theta, \beta |w, \alpha, \eta) = \frac{p(z, \theta, \beta|\alpha, \eta)}{p(w|\alpha, \eta)}\]

Поскольку апостериор является неразрешимой задачей, вариационный байесовский метод использует более простое распределение \(q(z,\theta,\beta | \lambda, \phi, \gamma)\) для его аппроксимации, и эти вариационные параметры \(\lambda\), \(\phi\), \(\gamma\) оптимизируются для максимизации нижней границы доказательности (Evidence Lower Bound - ELBO):

\[\log\: P(w | \alpha, \eta) \geq L(w,\phi,\gamma,\lambda) \overset{\triangle}{=} E_{q}[\log\:p(w,z,\theta,\beta|\alpha,\eta)] - E_{q}[\log\:q(z, \theta, \beta)]\]

Максимизация ELBO эквивалентна минимизации расхождения Куллбэка-Лейблера (KL) между \(q(z,\theta,\beta)\) и истинным последействием \(p(z, \theta, \beta |w, \alpha, \eta)\).

LatentDirichletAllocation реализует онлайн вариационный алгоритм Байеса и поддерживает как онлайн, так и батчевые методы обновления.

В то время как батчевый метод обновляет переменные после каждого полного прохода по данным, онлайн метод обновляет переменные из мини-батчей точек данных.

Примечание

Хотя онлайн метод гарантированно сходится к точке локального оптимума, качество точки оптимума и скорость сходимости могут зависеть от размера мини-батчей и атрибутов, связанных с настройкой скорости обучения.

Когда LatentDirichletAllocation применяется к матрице “документ-термин”, матрица будет разложена на матрицу “тема-термин” и матрицу “документ-топик”. В то время как матрица “тема-термин” хранится в модели как components_, матрица “документ-топик” может быть вычислена из метода transform.

LatentDirichletAllocation также реализует метод partial_fit. Он используется, когда данные могут быть получены последовательно.

Примеры:

• Topic extraction with Non-negative Matrix Factorization and Latent Dirichlet Allocation

Ссылки:

• “Latent Dirichlet Allocation” D. Blei, A. Ng, M. Jordan, 2003

• “Online Learning for Latent Dirichlet Allocation” M. Hoffman, D. Blei, F. Bach, 2010

• “Stochastic Variational Inference” M. Hoffman, D. Blei, C. Wang, J. Paisley, 2013

• “The varimax criterion for analytic rotation in factor analysis” H. F. Kaiser, 1958

См. также Снижение размерности для снижения размерности с помощью анализа компонент соседства (Neighborhood Components Analysis).

См. так же Матричная факторизация из “Учебник по машинному обучению” от yandex