[МУЗЫКА] В этом видео мы разберем, как работает метод PCA, или метод главных компонент, или Principal component analysis. Начнем с постановки задачи. Представьте, что у нас имеется m векторов xi и они из пространства Rn. И мы хотим спроецировать их на такие вложенные друг в друга многообразия, чтобы квадрат расстояний от наших точек до этих многообразий был минимален. Что же это за многообразия? Давайте начнем с нульмерного, L0 — это просто какая-то точка, a0 — это просто какой-то вектор. И мы хотим найти такой, что все остальные к нему как можно ближе по сумме квадратов расстояний. Дальше ищем L1, в которой вложен L0, и L1 уже будет являться линией, это наша точка a0 плюс с каким-то вещественным коэффициентом мы ходим вдоль вектора a1, то есть это, грубо говоря, такая линия, которая идет вдоль a1 и смещенная на a0. Если продолжать эту цепочку, то, например, L2 будет уже плоскостью, то есть это такая плоскость, которая проходит через нашу линию L1, но, имея еще один вектор a2, она уже может целую плоскость замести. Вот мы и рассмотрели, как эти вложенные многообразия устроены. И вот мы хотим их искать до какого-то значения k, что является гиперпараметром. Здесь есть некоторое ограничение: чтобы это все имело смысл, мы хотим, чтобы a0 был просто каким-то вектором в том же пространстве, что и наши иксы, а система векторов a1, ..., ak была ортонормированной. То есть все эти векторы друг другу ортогональны и по норме равны единичке. Тогда весь этот метод будет иметь смысл. Давайте посмотрим на примере, как нам эти расстояния от наших точек xi до нашего многообразия считать. До нульмерного многообразия L0, до точки расстояние считать довольно просто. Если мы возьмем минимум вот этого среднеквадратичного расстояния от наших точек до a0, то мы все с вами знаем, что оптимум этой задачи находится ровно в центре масс, то есть мы можем просто взять и усреднить все наши векторы xi, и это будет оптимальным a0, оптимальной точкой, расстояние квадратов до которой минимально. Давайте посмотрим, как это устроено в чуть более сложном случае. Давайте попробуем расписать, как выглядит расстояние от наших точек xi до многообразия L1, которое уже является линией. Чтобы задать линию нам нужно два вектора — a0 и a1, a0 задает смещение, а a1 задает нормированный вектор, вдоль которого мы можем эту линию проводить. И пусть у нас есть точка xi из R2, и мы хотим найти расстояние от этой точки до нашей линии. То есть мы хотим как бы опустить перпендикулярно нашу линию и посмотреть, какой он будет длины. Чтобы это провернуть, давайте сначала построим вектор, который будет xi − a0 — это синий вектор на картинке. Теперь этот синий вектор можно спроецировать на наш вектор a1. Для этого мы воспользуемся скалярным произведением. Так как вектор a1 нормированный, он по норме равен единичке, то мы как бы вдоль этого вектора ровно идем на проекцию синего вектора на нашу эту ось. И мы получаем зеленый вектор, который является проекцией синего вектора. И в этом зеленом векторе в записи используются два вектора, которые в скобочках. Это так мы будем обозначать скалярное произведение. Скалярное произведение — это просто поэлементно перемножили координаты двух векторов и сложили все эти произведения. Что делать дальше? Дальше вы можете заметить, что перпендикуляр, который мы хотим найти, он здесь серым пунктиром нарисован, на самом деле он является разностью двух векторов. Он является разностью синего вектора и зеленого. Собственно поэтому все эти векторы теперь нам известны, и оптимум нашей задачи оптимизационной — это будет a1, а оптимизационная задача — это просто нужно найти норму разности двух векторов синего и зеленого. И эта норма — это ровно наше расстояние до нашей линии L1. И теперь, чтобы найти следующую компоненту в нашем методе, мы решаем вот эту оптимизационную задачу при условии, что вектор a1, который мы ищем, он должен быть нормированным, то есть он по норме должен давать единичку. Ну и последний случай, самый сложный из рассмотренных: давайте посмотрим, как искать расстояние от точки xi до целой плоскости. Плоскость задается уже тремя векторами: a0 задает смещение, а a1 и a2, они нормированные и ортонормированные даже, то есть они ортогональны друг другу. И у нас есть вот эта вот плоскость. И давайте возьмем точку тоже в трехмерном пространстве, и xi — оно уже из R3 на этой картинке. Что нам теперь нужно сделать? Давайте так же, как и с линией мы делали, построим сначала вот этот синий вектор, который является разностью нашего xi и a0, то есть вот это смещение уберем. Теперь этот синий вектор, его можно на плоскость спроецировать, но прежде давайте найдем проекцию этого вектора на наши оси a1 и a2. Это соответственно зеленый вектор и фиолетовый. Теперь, если вы достроите эту картинку таким мысленным параллелепипедом, у которого в основании наш зеленый и фиолетовый вектор, которые ортогональные друг другу, то можете заметить, что проекцию, которую мы ищем, она на самом деле будет являться суммой этих двух векторов. Вот эта наша проекция синего вектора на плоскость — это ровно оранжевый вектор, который не что иное, как сумма зеленого и фиолетового. Это можете проверить дома сами, здесь нужно достроить все до параллелепипеда, и тогда это станет очевидным. И оказывается теперь, что наше расстояние, которое здесь обозначено пунктиром между синим вектором и оранжевым, это, опять же, просто разность этих двух векторов. Ну точнее, норма разности, мы же ищем квадрат расстояния. И тогда наша задача оптимизации для поиска a2 выглядит следующим образом: нам нужно посчитать разность синего вектора и оранжевого, посчитать норму в квадрате и эту сумму минимизировать при условии, что a2 должно быть по норме единичка, то есть это тоже должен быть нормированный вектор. Собственно, мы с вами рассмотрели, как можно найти расстояние до линии и до плоскости и, конечно же, до одной точки, но это совсем тривиальный случай, там решение прямо сразу известно — это просто среднеарифметическое всех координат, точнее, всех точек, которые у нас есть. Можно продолжать эту цепочку рассуждений, просто это уже не визуализируешь так просто, потому что следующее — это уже четырехмерное пространство, не понятно, как его рисовать. Но можете мне поверить, что эта формула обобщается, и k-тая компонента ak — это решение вот такой задачи оптимизации. Этот вектор должен быть по норме единичным, и мы ищем разность нашего синего вектора xi − a0 и суммы проекций до всех осей вот этой нашей гиперплоскости. Собственно, мы научились искать расстояние от любой точки xi до многообразия любой размерности: размерности 0, 1, 2, и это даже обобщается на размерность k. В следующем видео мы посмотрим, как из этого собрать наш алгоритм. [МУЗЫКА]
