Как уменьшить количество измерений и извлечь из этого пользу

Сначала я хотел честно и подробно написать о методах снижения размерности данных — PCA, ICA, NMF, вывалить кучу формул и сказать, какую же важную роль играет SVD во всем этом зоопарке. Потом понял, что получится текст, похожий на вырезки из опусов от Mathgen, поэтому количество формул свел к минимуму, но самое любимое — код и картинки — оставил в полном объеме.

Еще думал написать об автоэнкодерах. В R же, как известно, беда с нейросетевыми библиотеками: либо медленные, либо глючные, либо примитивные. Это и понятно, ведь без полноценной поддержки GPU (и в этом огромный минус R по сравнению с Python) работа со сколь-нибудь сложными нейронными сетями — и в особенности с Deep Learning — практически бессмысленна (хотя есть подающий надежды развивающийся проект MXNet ). Интересен также относительно свежий фреймворк h2o, авторов которого консультирует небезызвестный Trevor Hastie, а Cisco, eBay и PayPal даже используют его для создания своих планов по порабощению человечества. Фреймворк написан на Java (да-да, и очень любит оперативную память). К сожалению, он тоже не поддерживает работу с GPU, т.к. имеет несколько иную целевую аудиторию, но зато отлично масштабируется и предоставляет интерфейс к R и Python (хотя любители мазохизма могут воспользоваться и висящем по дефолту на localhost:54321 web-интерфейсом).

Так вот, если уж возник вопрос о количестве измерений в наборе данных, то это значит, что их, ну, скажем так, довольно много, из-за чего применение алгоритмов машинного обучения становится не совсем удобным. А иногда часть данных — всего лишь информационный шум, бесполезный мусор. Поэтому лишние измерения желательно убрать, вытащив из них по возможности все самое ценное. Кстати, может возникнуть и обратная задача — добавить еще измерений, а попросту — больше интересных и полезных фич. Выделенные компоненты могут быть полезны и для целей визуализации (t-SNE на это, например, и ориентирован). Алгоритмы декомпозиции интересны и сами по себе в качестве машинных методов обучения без учителя, что, согласитесь, иногда может и вовсе привести к решению первичной задачи.

В принципе, для сокращения размерности данных с той или иной эффективностью можно приспособить большинство методов машинного обучения — этим, собственно, они и занимаются, отображая одни многомерные пространства в другие. Например, результаты работы PCA и K-means в некотором смысле эквивалентны. Но обычно хочется сокращать размерность данных без особой возни с поиском параметров модели. Самым важным среди таких методов, конечно же, является SVD. «Почему SVD, а не PCA?» — спросите вы. Потому что SVD, во-первых, само по себе является отдельной важной методикой при анализе данных, а полученные в результате разложения матрицы имеют вполне осмысленную интерпретацию с точки зрения машинного обучения; во-вторых, его можно использовать для PCA и с некоторыми оговорками для NMF (как и других методов факторизации матриц); в-третьих, SVD можно приспособить для улучшения результатов работы ICA. Кроме того, у SVD нет таких неудобных свойств, как, например, применимость только к квадратным (разложения LU, Schur) или квадратным симметричным положительно определенным матрицам (Cholesky), или только к матрицам, элементы которых неотрицательны (NMF). Естественно, за универсальность приходится платить — сингулярное разложение довольно медленное; поэтому, когда матрицы слишком большие, применяют рандомизированные алгоритмы.

Суть SVD проста — любая матрица (вещественная или комплексная) представляется в виде произведения трех матриц: X=UΣV * , где U — унитарная матрица порядка m; Σ — матрица размера m x n, на главной диагонали которой лежат неотрицательные числа, называющиеся сингулярными (элементы вне главной диагонали равны нулю — такие матрицы иногда называют прямоугольными диагональными матрицами); V * — эрмитово-сопряжённая к V матрица порядка n. m столбцов матрицы U и n столбцов матрицы V называются соответственно левыми и правыми сингулярными векторами матрицы X. Для задачи редукции количества измерений именно матрица Σ, элементы которой, будучи возведенными во вторую степень, можно интерпретировать как дисперсию, которую «вкладывает» в общее дело каждая компонента, причем в убывающем порядке: σ1 ≥ σ2 ≥… ≥ σnoise. Поэтому-то при выборе количества компонент при SVD (как и при PCA, между прочим) ориентируются именно на сумму дисперсий, которую дают учитываемые компоненты. В R операцию сингулярной декомпозиции выполняет функция svd(), которая возвращает список из трех элементов: вектора d c сингулярными значениями, матриц u и v.

Что будет, если из исходного изображения вычесть средние значения каждого столбца, разделить полученную матрицу на корень квадратный из количества столбцов в исходной матрице, а потом выполнить сингулярное разложение? Оказывается, что столбцы матрицы V в полученном разложении в точности будут соответствовать главным компонентам, которые получаются при PCA (к слову, в R для PCA можно использовать функцию prcomp() )

Таким образом, при выполнении сингулярного разложения нормализованной исходной матрицы не составляет труда выделить главные компоненты. Это и есть один из способов их вычисления; второй же основывается непосредственно на поиске собственных векторов ковариационной матрицы XX T .

Вернемся к вопросу выбора количества главных компонент. Капитанское правило такое: чем больше компонент, тем больше дисперсии они описывают. Andrew Ng, например, советует ориентироваться на >90% дисперсии. Другие исследователи утверждают, что это число может быть и 50%. Даже придуман так называемый параллельный анализ Хорна, который основывается на симуляции Монте-Карло. В R для этого и пакет есть. Совсем простой подход — использовать scree plot: на графике надо искать «локоть» и отбрасывать все компоненты, которые формируют пологую часть этого «локтя». На рисунке ниже, я бы сказал, надо учитывать 6 компонент:

В общем, как вы видите. вопрос неплохо проработан. Также бытует мнение, что PCA применим только для нормально распределенных данных, но Wiki с этим не согласна, и SVD/PCA можно использовать с данными любого распределения, но, конечно, не всегда результативно (что выясняется эмпирически).

Еще одно интересное разложение — это факторизация неотрицательных матриц, которая, как следует из названия, применяется для разложения неотрицательных матриц на неотрицательные матрицы: X=WH. В целом, такая задача не имеет точного решения (в отличие от SVD), и для ёё вычисления используют численные алгоритмы. Задачу можно сформулировать в терминах квадратичного программирования — и в этом смысле она будет близка к SVM. В проблеме же сокращения размерности пространства важным является вот что: если матрица Х имеет размерность m x n, то соответственно матрицы W и H имеют размерности m x k и k x n, и, выбирая k намного меньше самих m и n, можно значительно урезать эту самую исходную размерность. NMF любят применят для анализа текстовых данных, там, где неотрицательные матрицы хорошо согласуются с самой природой данных, но в целом спектр применения методики не уступает PCA. Разложение первой картинки в R дает такой результат:

Какое отношение имеет ICA к задаче уменьшения размерности данных? Попробуем представить данные — вне зависимости от их природы — как смесь компонент, тогда можно будет разделить эту смесь на то количество «сигналов», которое нам подходит. Особого критерия, как в случае с PCA, по выбору количества компонент нет — оно подбирается экспериментально.

Последний подопытный в этом обзоре — автоэнкодеры, которые представляют собой особый класс нейронных сетей, настроенных таким образом, чтобы отклик на выходе автокодировщика был максимально близок к входному сигналу. Со всей мощью и гибкостью нейронных сетей мы одновременно получаем и массу проблем, связанных с поиском оптимальных параметров: количества скрытых слоев и нейронов в них, функции активации (sigmoid, tanh, ReLu,), алгоритма обучения и его параметров, способов регуляризации (L1, L2, dropout). Если обучать автоэнкодер на зашумленных данных с тем, чтобы сеть восстанавливала их, то получается denoising autoencoder . Предварительно настроенные автокодировщики также можно «стыковать» в виде каскадов для предобучения глубоких сетей без учителя.

В самом простом представлении автоэнкодер можно смоделировать как многослойный перцептрон, в котором количество нейронов в выходном слое равно количеству входов. Из рисунка ниже понятно, что, выбирая промежуточный скрытый слой малой размерности, мы тем самым «сжимаем» исходные данные.

Вышеозначенный автоэнкодер несложно превратить в denoising autoencoder. Так как такому автокодировщику на вход надо подавать искаженные образы, перед первым скрытым слоем достаточно разместить dropout слой. Благодаря ему с некоторой вероятностью нейроны будут находиться в «выключенном» состоянии, что а) будет вносить искажения в обрабатываемый образ; б) будет служить своеобразной регуляризацией при обучении. Еще одно интересное применение автоэнкодера — определение аномалий в данных по ошибке реконструкции образов. В целом, если подавать на вход автоэнкодера данные не из обучающей выборки, то, понятно, ошибка реконструкции каждого образа из новой выборки будет выше таковой из тренировочной выборки, но более-менее одного порядка. При наличии аномалий эта ошибка будет в десятки, а то и сотни раз больше.