Principal Component Analysis

Как выглядит задача машинного обучения в реальной жизни? Сели, подумали, выбрали какие-то фичи, засунули их в алгоритм, получили результат. Чем больше фич выбрали, тем, вроде как, лучше. Пример: пытаемся описать модель плавного подъема воздушного шарика; иногда он подлетает на воздушном потоке, иногда его качает немного в стороны. Для самой простой модели нам всего лишь надо знать среднюю скорость, а для этого нужна одна камера, которая сделает несколько снимков сбоку. По снимкам мы посчитаем среднюю скорость. А теперь предположим: мы застряли в облаке, парим рядом с шариком не знаем, где земля, и поэтому не знаем где находится “сбоку”. Поэтому ставим камеры как-нибудь, побольше и со всех сторон. Вопрос, как теперь из этого вычленить реальное нужное нам измерение y, чтобы посчитать в итоге скорость?

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

Если выражать математически, есть sample выраженный через $m$ -мерный вектор наблюдений $x$. В нашем пример один sample - это набор фотографий в определенный момент времени, а $x$ - все измерения, снятые с этих фотографий. $X$ - это матрица всех наших наблюдений.

Теперь надо вспомнить немного линейной алгебры. Каждый вектор можно представить как линейную комбинацию некоторых базисных векторов. В 2мерном пространстве самый простой базис - это (1,0); (0,1). PCA - это способ преобразовать наш простой базис в другой, являющийся линейной комбинацией оригинального. То есть мы линейно преобразуем наши исходные данные:

Здесь $P$ - матрица преобразования, которую нам и предстоит найти. Для этого надо формально определить, что значит “представить данные наилучшим образом”.

Шум (Noise)

Картинка с одной из камер.

Camera 1

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

Лишние данные (Redundancy)

Ясно, что мы наснимали сильно больше фоток, чем нужно. Более того, скорее всего одни картинки выражаются простым линейным преобразованием из других. Например, поставили одну камеру на метр выше второй. Тогда координаты с этой камеры линейно выражаются ($coord_1 = coord_2 + 1$). И на самом деле мы эти фотографии можем просто выкинуть, они не несут нам никакой информации. Хочется от таких измерений избавится совсем.

Ковариационная матрица

Мера линейной зависимости между переменными - covariance. Мера разброса значений переменной - variance. Ковариационная матрица содержит как раз все эти меры и считается как:

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

Теперь, если вернуться к нашим целям и идельному представлению Y, то мы хотим получить ковариационную матрицу $C_Y$, для которой

  1. Все ковариации равны 0.
  2. Все строки отсортированы по значимости согласно значению variance. Таким образом, мы в любой момент сможем взять, например, лучшие 10 измерений, а остальные выкинуть как ненужные.

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

Любую матрицу можно представить как разложение в собственных векторах и диаганальной матрицы $A = EDE^T$. Тогда, взяв за $P = E^T$, где $E^T$ матрица собственных векторов $C_X$ получим:

Учитывая, что $P$ - ортогональная матрица $P^T = P^{-1}$, получаем, что $C_Y = D$. $P$ - ортогональная матрица, так как $C_X$ - симметричная и вещественная матрица. Для таких матриц всегда существует ортономированный базис из собственных векторов и разложение через ортогональную матрицу $P$.

То есть мы нашли нужные вектора разложения, которые оказались собственными векторами матрицы $C_X$. Первый собственный вектор - это первый компонент. По этому направлению дисперсия максимальна.

Допущения

Следущие допущения нужны для того, чтобы применить PCA

  1. Линейность. Если один аттрибут выражается через другой нелинейно, PCA не поможет. Поможет, например, предварительная замена аттрибутов, чтобы избавится от нелинейности.
  2. Полагаем, что нас интересуют больше всего направления, в которых variance максимален. Это не всегда правда.

Rodion's blog

put it on the cloud and kill it with fire
Tags
Connect