Первый алгоритм из семейства dimensionality reduction: PCA (+ SVD)

Тут будет идея алгоритма, а м*тан в случае чего можно найти в этой статье: https://arxiv.org/pdf/1404.1100.pdf.

Представим, что у нас есть друг, претендующий на нобелевскую премию. У него случилась ситуация: его во время коронавируса зачем-то задержали во Франции и совсем не дают выехать. Ему нужна ваша помощь: нужно провести какой-то непонятный физический эксперимент и можно получить вообще все измерения со всех приборов его огромной лаборатории. Понятное дело, что в такой ситуации куча измерений скореллирована между собой, а ещё есть информативные и неинформативные методы измерения и вообще ужас. Нам выделили лабораторию с 6ти утра до 8ми, а друг напился и спит во Франции, при этом сообщить нам, какие конкретно приборы его интересуют, он забыл, но данные весят настолько дофига, что все их выгрузить в облако мы не можем, а надо как-то отобрать нужные. Как это сделать?

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

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

Для многомерных случайных векторов положение центра облачка -- матожидание проекции на оси (что понятно), а вот форму облачка описать просто матожиданиями проекций нельзя: даже в двумере случайные величины от нуля до единицы, распределённые по синусу и косинусу имеют одинаковые дисперсии, только вот формы совершенно разные. Для описания этих самых форм облака от случайных векторов нужна ковариационная матрица, т.е. матрица, где элемент (i, j) -- корреляция соответствующих признаков в матрице, а формулка её записывается как cov(X_i, X_j) = E(X_i * X_j) - E(X_i) * E(X_j), где E -- м*тожидание. Допустим, мы хотим для упрощения жизни сдвинуть СО так, чтобы центр облачка приходился на центр СО, тогда эта штука дюже упростится: cov(X_i, X_j) = E(X_i * X_j). Понятно, что если мы рассмотрим ковариацию элемента с самим собой, выйдет просто дисперсия этого признака. Таким образом, матрица ковариации это просто обобщение дисперсии для многомерных случайных величин, просто описывая форму случайной величины.

Посчитаем эту самую матрицу ковариацию. Довольно весело заметить, что если мы повернём базис так, чтобы на облачко можно было натянуть выпуклую оболочку (тут я представляю эллипс-кита, одним махом сжирающего своего близнеца из маленьких рыбёшек -- измерений), то ВНЕЗАПНО получится, что матрица ковариации стала диагональной. Вообще-то эта штука выводится из отношения Рэлея для ковариационных матриц, но мы же тут идею рассказываем, правильно? Получается, что направление максимальной дисперсии в какой-то проекции ВСЕГДА совпадёт с собственным вектором с максимальным собственным значением (которое просто из определения матрицы ковариации равно величине дисперсии). Это довольно просто себе вообразить: наш трёхмерный кит-эллипс должен растянуться так, чтобы сожрать всех рыб, но растягиваться слишком сильно ему невыгодно: пока он будет растягиваться, рыбы почуют неладное и разбегутся в стороны, поэтому времени у бедолаги немного. Кит умён, поэтому он поворачивается в воде и растягивается в длину так, чтобы гарантированно съесть всех рыб с максимальной дисперсией, в высоту так, чтобы сожрать всех рыб со второй по величине дисперсией, в ширину -- с третьей дисперсией по величине. А собственные вектора тогда будут его длиной, шириной и высотой. Проще это посмотреть на картинке.

Теперь подумаем о том, что мы хотим нарисовать кита (можно ещё и рыбок в довесок). Как нарисовать этого кита на двумерном листочке, чтобы утратить меньше всего информации и чтобы всем было понятно, якобы это кит? Есть шанс, что если мы нарисуем его в базисе из собственных векторов с первыми двумя по величине дисперсиями (длина и высота), мы потеряем меньше информации. Зная его ширину, мы сможем с потерей не больше 10% домножить матрицу на собственный вектор и получить примерное распределение точек. Для опытных смешариков: если пользоваться не матрицей ковариации, а SVD-разложением, потеря будет чуть больше, но зато эту штуку вычислять сильно проще.

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

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

Вот таким способом мы можем понять, что какие-то данные линейно зависят друг от друга и переслать другу файл в несколько раз (на практике в несколько десятков раз) меньшего объёма. Вин.

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