[БЕЗ_ЗВУКА] В
прошлом видео вы узнали, как формулируется задача метода главных компонент,
а теперь давайте разберемся, как ее решать.
Как вы знаете,
одна из постановок метода главных компонент — это максимизация дисперсии.
Есть некоторое облако точек, где каждая точка — это объект выборки,
и нужно найти такие оси, при проецировании на которые
мы сохраним как можно больше дисперсии исходной выборки.
Чем больше дисперсии мы сохраним,
тем больше информации останется после понижения размерности.
Формально задача максимизации дисперсии после проецирования записывается вот так.
В первой строке записана собственно дисперсия после проецирования
— она выражается через направление wi, а поскольку мы хотим оставить как можно
больше информации, дисперсию нужно максимизировать.
Также мы вводим органичение, что матрица весов W должна быть
ортогональной — это нужно, чтобы решение было единственным.
В методе главных компонент есть один нюанс: выражение,
через которое мы записали дисперсию, будет означать именно дисперсию выборки только в
том случае, если матрица объекты-признаки центрирована,
то есть если среднее каждого признака равно нулю.
Поэтому будем считать, что, собственно, выборка центрирована,
что мы уже вычли среднее из каждого столбца в матрице объекты-признаки.
Итак, чтобы разобраться, как устроено решение этой задачи,
давайте попробуем сначала разобраться с простым частным случаем — случаем, когда
мы хотим найти ровно одну компоненту, на которую будем проецировать всю выборку,
и хотим выбрать ее так, чтобы дисперсия после проецирования была максимальной.
Задача будет выглядеть вот так.
Вектор весов, который характеризует направление — это w1,
и он умножается на матрицу X транспонированное,
это умножается на матрицу X и снова на вектор весов w1.
Это мы хотим максимизировать.
Ограничение же вырождается в то,
что L2 норма этого вектора весов должна равняться единице.
Итак, как вы знаете, чтобы решать такие задачи условной оптимизации,
нужно выписать их лагранжиан.
Лагранжиан будет выглядеть вот так.
Это собственно критерий,
который мы максимизируем минус λ умножить на ограничение.
λ умножить на w1 транспонированное на w1 минус единица.
Далее этот лагранжиан нужно продифференцировать по тому,
что мы хотим найти, то есть по w1.
Если воспользоваться формулами матричного дифференцирования,
можно получить вот такую формулу.
Если там ее немного преобразовать, перенести одно слагаемое в правую
часть и поделить на 2, то мы получим вот такое уравнение.
X транспонированное на X умножить на w1 равняется λ на w1.
Давайте обратим внимание, что что говорит это уравнение?
Оно говорит, что вектор w1 является собственным вектором матрицы X
транспонированное на X, поскольку при умножении матрицы на этот вектор,
мы получаем этот же вектор, умноженный на некоторое число λ, и число λ является
собственным значением, соответствующим этому собственному вектору.
Если мы подставим полученное нами условие в функционал задачи, то обнаружим,
что дисперсия выборки после проецирования будет равна как раз λ, то есть будет равна
собственному значению, соответствующему собственному вектору, который мы выбрали.
Таким образом, поскольку мы хотим максимизировать дисперсию,
нам нужно выбирать максимальное собственное значение и собственный вектор,
который соответствует этому максимальному собственному значению.
Итак, мы получаем, что первая компонента в методе главных компонент — это
собственный вектор матрицы X транспонированное на X,
который соответствует максимальному собственному значению этой матрицы.
Кстати, обратите внимание,
что X транспонированное на X — это матрица ковариации, то есть именно та матрица,
которая характеризует дисперсию нашей выборки.
Неудивительно, что именно через ее характеристики выражается решение метода
главных компонент.
Визуально это выглядит вот так: есть облако точек, и мы выбираем именно то
направление, при проецировании на которое мы сохраним как можно больше дисперсии.
И, собственно, это направление будет как раз равно первому собственному вектору
матрицы ковариации.
Если мы продолжим наши выкладки и будем искать оптимальное второе направление,
третье и так далее, то обнаружим, что, например,
w2 — второе направление в методе главных компонент —
соответствует собственному вектору матрицы X транспонированное на X,
соответствующему второму по величине собственному значению, и так далее.
Кстати, отсюда же можно получить, что через собственные значения можно
выразить долю дисперсии, которую мы сохранили.
Дисперсия всей исходной выборки — это сумма всех собственных значений матрицы X
транспонированное на X, то есть сумма от 1 до D; дисперсия выборки после
проецирования на d главных компонент — это сумма максимальных d собственных значений.
Таким образом, с помощью вот такой дроби можно понять, какую долю дисперсии
мы сохранили, спроецировав нашу выборку на главные компоненты.
При решении задачи метода главных компонент очень пригождается сингулярное
разложение, про которое вы уже слушали в первом курсе.
Напомню, сингулярное разложение матрицы X представляет эту матрицу в виде
произведения трех других матриц: U умножить на D умножить
на V транспонированное.
При этом U и V — это ортогональные матрицы, а D — диагональная матрица.
Столбцы матрицы U — это собственные векторы матрицы X на X транспонированное,
столбцы матрицы V — это собственные векторы матрицы X транспонированное на X,
а на диагонали матрицы D стоят собственные значения этих обоих матриц, которые,
оказывается, совпадают.
Кстати, эти собственные значения матриц X транспонированное
на X и X на X транспонированное называются сингулярными числами.
Итак, мы приходим к следующему алгоритму для решения задачи метода главных
компонент.
Мы находим сингулярное разложение матрицы X, формируем матрицу
весов W из собственных векторов, из столбцов матрицы V, соответствующих
максимальным сингулярным числам, и после этого можем делать преобразования.
Чтобы спроецировать объекты, записанные в матрицу X на наши главные компоненты,
мы просто умножаем матрицу X на W и получаем матрицу Z, которая является
матрицей объекты-признаки для нового сокращенного признакового описания.
Итак, мы с вами разобрались, как решать задачу метода главных компонент.
Чтобы ее решить, нужно найти собственные векторы матрицы ковариации X
транспонированное на X и выбрать те из них,
которые соответствуют максимальным собственным значениям.
Именно проецирование на эти векторы будет позволять сохранить как можно больше
дисперсию.
Также мы выяснили, что через собственные значения этой матрицы можно выяснить,
какую именно долю дисперсии мы сохранили при таком понижении размерности.
