2.5. Разложение сигналов на компоненты (задачи факторизации матриц)

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

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

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

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

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

Примеры

• Анализ главных компонент (PCA) на наборе данных ирисов
• Сравнение двумерных проекций набора данных ирисов с помощью LDA и PCA
• Выбор модели с помощью вероятностного PCA и факторного анализа (FA)

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

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

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

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

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

Примеры

• Инкрементальный 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 (значение по умолчанию).

Примеры

• Пример распознавания лиц с использованием собственных лиц и SVM
• Разложения набора данных лиц

Литература

• Алгоритм 4.3 в статье «Поиск структуры с помощью случайности: стохастические алгоритмы для построения приближенных разложений матриц» Halko и др., 2009
• «Реализация рандомизированного алгоритма анализа главных компонент» A. Szlam и др., 2014

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

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

Мини-пакетный разреженный PCA (MiniBatchSparsePCA) — это более быстрый, но менее точный вариант SparsePCA. Повышение скорости достигается за счет итераций по небольшим фрагментам набора признаков в течение заданного числа итераций.

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

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

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

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

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

Примеры

• Разложения набора данных лиц

Литература

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

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

Примеры

• Ядерный PCA
• Удаление шума с изображений с помощью ядерного PCA

Литература

2.5.2.2. Выбор решателя для ядерного PCA

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

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

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

• Ортогональный жадный алгоритм выбора соответствий (ортогональный жадный алгоритм выбора соответствий (OMP))
• Регрессия с наименьшим углом (регрессия с наименьшим углом)
• Lasso, вычисляемый с помощью регрессии с наименьшим углом
• Lasso с использованием покоординатного спуска (Lasso)
• Пороговая обработка

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

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

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

Примеры

• Разреженное кодирование с заранее вычисленным словарём

2.5.4.2. Обучение словаря общего назначения

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

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

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

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

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

Ссылки

• «Онлайн-обучение словаря для разреженного кодирования» J. Mairal, F. Bach, J. Ponce, G. Sapiro, 2009

2.5.4.3. Обучение словаря на мини-пакетах

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

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

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

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

Примеры

• Удаление шума с изображения с помощью обучения словаря

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

NMF [1] — альтернативный подход к разложению, предполагающий, что данные и компоненты неотрицательны. NMF можно использовать вместо PCA или его вариантов в тех случаях, когда матрица данных не содержит отрицательных значений. Метод находит разложение выборок \(X\) на две матрицы \(W\) и \(H\) с неотрицательными элементами, оптимизируя расстояние \(d\) между \(X\) и матричным произведением \(WH\). Наиболее широко используется квадрат нормы Фробениуса, являющийся очевидным расширением евклидовой нормы на матрицы:

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

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

Атрибут init задаёт используемый метод инициализации, который сильно влияет на производительность метода. NMF реализует метод двойного сингулярного разложения для неотрицательных матриц. NNDSVD [4] основан на двух процедурах SVD: одна аппроксимирует матрицу данных, а другая — положительные части полученных частичных множителей SVD, используя алгебраическое свойство матриц ранга 1. Базовый алгоритм NNDSVD лучше подходит для разреженной факторизации. Для плотных данных рекомендуются его варианты NNDSVDa (в котором все нули заменяются средним значением всех элементов данных) и NNDSVDar (в котором нули заменяются случайными возмущениями, меньшими среднего значения данных, делённого на 100).

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

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

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

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

2.5.7.2. NMF с бета-дивергенцией

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

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

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

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

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

Для 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)

Примеры

• Разложения набора данных лиц
• Извлечение тем с помощью неотрицательной матричной факторизации и латентного размещения Дирихле

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

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

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

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

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

Литература