[ЗАСТАВКА] Сейчас мы с вами рассмотрим один из очень известных методов в анализе данных — это метод главных компонент. Он полезен не только при решении задач регрессии, но и в гораздо более широком числе случаев. Задача ставится так: имеется множество исходных числовых признаков, их n штук, и нам хочется перейти в пространство новых числовых признаков, но желательно сделать так, чтобы их оказалось меньше, но, тем не менее, чтобы новые признаки содержали всю основную информацию о старых. Ну как это требование можно формализовать? Например, так, что старые признаки должны восстанавливаться по новым, то есть, несмотря на то, что новых признаков меньше, но значение старых на всех объектах обучающей выборки, тем не менее, можно восстановить. Можно наложить то или иное ограничение на класс преобразований, с помощью которых старые признаки восстанавливаются по новым. Метод главных компонент — это частный случай, когда мы предполагаем, что это преобразование линейно. Можно и всякие разные обобщения изобретать на эту тему, пользуясь нелинейными преобразованиями, но вот мы сейчас с вами рассматриваем только линейную модель. Итак, мы будем требовать, чтобы старые признаки хорошо восстанавливались по новым, а новые признаки j нам требуется найти, более того, нам так же требуется, совместно с ними, найти и матрицу преобразований, которая восстанавливает старые признаки по новым. То есть получается так, если мы применяем метод наименьших квадратов, мы минимизируем сумму квадратов разностей между значениями старыми признаков fj(xi), то есть берем каждый признак и в каждом объекте, и восстановленное значение — f с крышечкой. Если записывать эту постановку задачи в матричном виде, то ее решать гораздо удобнее. Давайте введем матрицы «объекты-признаки» — старая матрица. Строки — это объекты выборки, столбцы — это признаки. Новая матрица G, строки соответствуют тем же самым объектам, столбцы — это новые признаки. И нам нужна матрица линейного преобразования, перехода от новых признаков к ну не совсем старым, а к восстановленным старым, то есть здесь очень важно отличать матрицу F с крышечкой, которая есть оценка матрицы F, F — это исходная матрица «объекты-признаки», а F с крышечкой — это произведение новой матрицы G на матрицу перехода U транспонированное. И нам хочется построить одновременно и матрицу G, и матрицу U таким образом, что бы их произведение хорошо восстанавливало матрицу F. Получается так, что матрица F имеет размер l на n, и в общем случае она имеет полный ранг, то есть если объектов больше чем признаков, то ранг ее равен n, и мы хотим ее приблизить матрицей, которая есть произведение двух матриц размера l на m и m на n. Вот эта промежуточная размерность m, она может быть существенно меньше, чем n, то есть мы делаем низкоранговое матричное приближение исходной матрицы F. Итак, в матричном виде задача заключается в том, чтобы минимизировать квадрат нормы разности двух матриц — заданная исходная матрица F и произведение двух матриц G и U транспонированное, которые имеют, вот это произведение оно имеет ранг, может быть много меньше, чем ранг матрицы F. Есть теорема, которая решает эту задачу исчерпывающим образом, она гласит следующее, что при техническом предположении, что ранг матрицы F не меньше, чем n, минимум нашего функционала достигается в том случае, когда мы возьмем в качестве столбцов матрицы U собственные векторы матрицы F транспонированное F, соответствующие максимальным собственным значениям λ1, ..., λm. Ну вот поскольку мы берем максимальные собственные значения, они называются главные компоненты, отсюда и название метода — метод главных компонент. И есть масса полезных свойств про вот эти матрицы G и U, которые у нас в итоге получаются. Во-первых, да, U — ортонормированная матрица, матрица G — ортогональная, то есть произведение G транспонированное на G дает диагональную матрицу, а на диагоналях записаны те самые собственные значения λ1, λm. Дальше пункт третий в этой теореме гласит на самом деле следующее, что столбцы матрицы U — это есть собственные векторы матрицы F транспонированное F, а столбцы матрицы G — это собственные векторы матрицы F на F транспонированное. Вот эти вот факты они записаны в такой вот компактной матричной форме. И наконец, очень важный факт, что значение того функционала, который мы минимизируем может быть выражено в виде квадрат нормы матрицы F минус след матрицы Λ. След матрицы Λ — это сумма всех собственных значений λ1, ..., λm. Но квадрат нормы матрицы F, мы знаем это из линейной алгебры, это сумма всех и тех же самых собственных значений, но от 1 до n. Итого получается, что значение нашего функционала, который мы минимизировали, состоит из тех собственных значений, которые мы не взяли в наше разложение, то есть отсюда следует, что мы действительно должны брать в разложение те собственные векторы, которые соответствуют максимальным собственным значениям, нужно для того, чтобы минимизировать этот функционал. Ну а уже по виду этой теоремы и по свойствам матриц U и G можно догадаться, что видимо здесь имеется какая-то внутренняя взаимосвязь глубокая с сингулярным разложением, и да, это действительно так оно и есть. В частном случае, если мы не стремимся понизить размерность нашего матричного представления и мы берем промежуточную размерность m, равную числу столбцов исходной матрицы F, то мы получим, собственно, ноль слагаемых вот в этой сумме, и в итоге норма разности будет в точности равна нулю. Это означает, что представление F с крышечкой равно GU транспонированное оно точное, оно точно равно исходной матрице F, которую мы разлагали, и совпадает с сингулярным разложением. И можно даже написать, что вот эта матрица G она выражается через собственные векторы, которые записаны в столбцах матрицы V. И получается, что линейное преобразование работает в обе стороны — можно умножить матрицу F на U и получить G, а можно G умножить на U транспонированное и получить F. Вот это вот преобразование U оно еще называется декоррелирующим или преобразованием Карунена-Лоэва. Вообще метод главных компонент изобретался в разные времена разными учеными для решения разных задач, которые на первый взгляд казалось, что это новая задача, но потом вот всякий раз оказывалось, что вот такое вот урезанное сингулярное разложение, из которого выкинули минимальные собственные значения с их собственными векторами, вот это вот очень полезная конструкция, которая дает низкоранговое матричное разложение. Вопрос, как выбрать число m, и иногда бывает так, что данные, которые представлены в матрице F, на самом деле лежат не в пространстве размерности n, а в пространстве меньшей размерности, то есть вся наша выборка укладывается в какое-то линейное многообразие, размерность которого меньше, чем размерность пространства. И вот в таком случае очень выгодно использовать метод главных компонент. Если это действительно так, то у метода главных компонент возникает вот такое интересное свойство, что возникает эффективная размерность выборки. Если мы возьмем и упорядочим по убыванию собственные значения матрицы F транспонированное F и посмотрим на получившийся ряд, то в каком-то месте мы обнаружим крутой склон или такой резкий обрыв, который отличает большие собственные значения от маленьких, то есть действительно это будет означать, что была какая-то закономерность, какой-то закон природы, благодаря которому все наши данные образовали в n-мерном пространстве некое линейное подпространство меньшей размерности. Вот таким способом через собственные значения мы можем обнаружить размерность этого пространства, ну а потом, выписав матрицы G и U, найти и само это пространство. Далеко не всегда работает критерий крутого склона, иногда построив такой график собственных значений, мы увидим монотонно убывающую последовательность точек, на которой нет никаких заметных глазу крутых склонов. Это случай, когда, может быть, и не стоит применять метод главных компонент, то есть он хорошо работает именно тогда, когда в данных объективно присутствуют какие-то причины, заставляющие эти данные находиться в пространстве существенно меньшей размерности, и тогда метод главных компонент становится техникой для нахождения этого пространства. Ну давайте посмотрим, как эта техника работает в том случае, когда мы решаем задачу многомерной линейной регрессии методом наименьших квадратов. Итак, мы минимизируем тот самый функционал, который мы уже ввели на позапрошлой лекции. Мы берем матрицу F и пытаемся заменить ее приближенно на произведение двух матриц G и U транспонированное, полагая, что вот, наверное, найдется какая-то меньшая размерность m, меньшее число признаков. Ну сразу можно заметить, что это просто означает решение задачи в пространстве меньшей размерности, в пространстве новых признаков. Какая разница, что искать, вектор α, а потом умножать его на матрицу U транспонированное или сразу искать их произведение — вектор β. Можно решить эту самую новую возникшую задачу в пространстве меньшей размерности и расписать для нее всё решение. Ну и заметить, что спектр матриц G и F в части первых m собственных векторов они совпадают, и поэтому мы получим ровно то же самое решение, которое мы выписывали ранее для вот этой вот самой нашей задачи наименьших квадратов в пространстве пониженной размерности, но теперь мы сможем написать выражение для псевдообратной матрицы, для решения наименьших квадратов α со звездочкой, и в этом решении будут фигурировать только первые m собственных векторов, которые соответствуют максимальным собственным значениям, а весь остальной спектр он просто выкидывается из решения. То есть такое впечатление, что мы снова воспользовались тем же самым сингулярным разложением, но теперь мы взяли не все собственные векторы, а только те, которые соответствовали собственным значениям, максимальным m, первым собственным значениям. Резюмируем. Мы рассмотрели метод главных компонент, который позволяет приближать матрицу ее низкоранговым разложением. По сути, для этого достаточно взять все то же сингулярное разложение матрицы, взять только ее первые m сингулярных чисел, которые имеют максимальные значения, а все остальные отбросить. Этот прием часто применяется в анализе данных не только для решения задачи регрессии, но и для классификации, для сжатия данных, используется он также в обработке изображений. [ЗАСТАВКА]
