Это третья часть моей серии заметок по CS M146.
СПС: мотивация
Иногда мы хотим уменьшить размерность данных. Может быть, потому, что функций слишком много, или, может быть, мы хотим сократить их до двух, чтобы мы могли их визуализировать. Мы хотим сопоставить исходный набор данных 𝑋 из 𝑑 пространственных объектов в 𝑘 пространственных объектов.
PCA: формулировка проблемы
Мы можем думать о проблеме как о поиске матрицы линейного преобразования 𝑃, которая преобразует 𝑋 в 𝑍.
Откуда мы знаем, что преобразование 𝑃, которое мы выбрали, хорошее? Мы выберем 𝑃 так, чтобы дисперсия 𝑍 была максимальной. Почему? Рассмотрим случай, когда 𝑘 равно 1.
Интуитивно кажется, что лучше проецировать точки данных на линию слева. Если мы выберем линию справа, нам будет трудно различить точки данных, потому что они очень близки друг к другу. Другими словами, разница небольшая. Поэтому мы хотим, чтобы дисперсия была как можно больше.
Сначала мы начнем с того, когда 𝑘 равно 1 (т. е. уменьшение размерности до 1). Тогда мы будем думать об общем случае.
Это то же самое, что сказать
Есть одна вещь, которую нам нужно сделать с алгоритмом PCA, а именно центрировать точки данных 𝑋. Другими словами, вычтите каждую точку данных из ее среднего значения.
Почему мы это делаем? Мы увидим, что это облегчит математику позже. С этого момента всякий раз, когда мы видим 𝑋, мы будем считать, что он уже отцентрирован.
Итак, еще раз, наша цель — максимизировать дисперсию прогнозируемых точек данных 𝑍.
Напомним, что формула дисперсии выглядит следующим образом:
Обратите внимание, поскольку 𝑋 уже находится в центре, 𝑍 также находится в центре. Другими словами, среднее значение 𝑍 равно нулю. Следовательно, дисперсия 𝑍 — это просто усредненная сумма квадратов.
Мы можем заменить 𝑥 и 𝑤 обратно.
Мы можем векторизовать выражение.
Пусть 𝐶 будет 𝑋ᵀ𝑋/N. 𝐶 называется ковариационной матрицей. Тогда наша цель
Но так как на 𝑤 нет ограничений, 𝑤 будет расти до бесконечности. Нам нужно ограничение на 𝑤. Напомним, что 𝑤 — это просто вектор нормали к линии проекции. Таким образом, мы можем установить длину 𝑤 равной 1 без ограничения общности.
Мы уже знаем, как решать задачу условной оптимизации из предыдущей части — правильно, мы используем лагурангиан.
Наша цель заключается в следующем.
Взятие производной по λ только возвращает нам ограничение. Но, взяв его по отношению к 𝑤, мы получим кое-что интересное.
Это говорит о том, что 𝑤 является одним из собственных векторов 𝐶. Но какой собственный вектор? Мы можем подключить результат обратно к цели.
Оказывается, дисперсия равна λ. Поскольку мы максимизируем λ, нам нужен собственный вектор с наибольшим собственным значением.
Когда 𝑘 равно 2, вот наша цель.
Мы просто добавляем дисперсию второго столбца 𝑍 к нашей оптимизации. Если мы просто решим эту задачу оптимизации, 𝑤₂ будет таким же, как 𝑤₁, и, следовательно, как 𝑧₂ и 𝑧₁. Но это плохо. Это похоже на уменьшение размеров до ℝ², но проецирование точек данных на линию, а не на плоскость. А поскольку нам не нужна избыточность во втором собственном векторе, первый собственный вектор должен быть перпендикулярен первому.
Другими словами, второй собственный вектор соответствует второму по величине собственному значению. В общем, когда мы хотим уменьшить размеры до 𝑘, 𝑃
где собственные векторы отсортированы так, что соответствующие собственные значения находятся в порядке убывания.
