Метод главных компонент (PCA)

Что делает метод главных компонент

Здравствуйте и вновь добро пожаловать на занятия по теме «Глубокое обучение без учителя на языке Python».

В этой лекции мы поговорим о методе главных компонент (PCA). Его описание можно разделить на две части. Первая – это описание того, что он делает и для чего применяется, а вторая – это математическое обоснование метода.

Итак, что же делает метод главных компонент?

Прежде всего отметим, что это линейное преобразование. Предположим, что мы умножаем вектор на скалярную величину. В этом случае он никогда не изменит своё направление, лишь свою длину. Конечно, мы можем умножить вектор на -1, и тогда вектор изменит своё направление на противоположное, но произвольно вращать его нельзя.

Если же мы умножаем вектор на матрицу, он может изменять своё направление и вращаться произвольным способом. Вот именно это и делается в метод главных компонент – мы берём матрицу данных X, имеющую размерность NxD, и умножаем её на матрицу преобразования Q, имеющую размерность DxD, в результате чего получаем матрицу преобразованных данных Z, также имеющую размерность NxD:

Z=XQ.

Если же мы захотим преобразовать отдельный вектор x в соответствующий отдельный вектор z, то умножение приобретает вид

Z=Qx.

Изменение порядка умножения связано с тем, что матрица данных X в данном случае представляет собой вектор-строку размерностью 1xD, тогда как мы, говоря об отдельных векторах, имеем в виду вектор-столбец размерностью Dx1.

Что интересно в методе главных компонент – так это вопрос выбора матрицы Q. Заметьте, что поскольку мы рассматриваем обучение без учителя, то у нас есть X, но нет Y, то есть нет целевых переменных.

Другой точка зрения на то, что происходит при умножении на матрицу, состоит в том, что мы поворачиваем не сам вектор, а систему координат, в которой находится этот вектор. Какой именно точкой зрения на данную операцию мы будем пользоваться, будет зависеть от решаемой задачи.

Одна из сфер применения метода главных компонент – уменьшение размерности. Когда мы рассматриваем базу данных MNIST, состоящую из изображений размером 28×28 или, другими словами, векторов размерностью 784, мы имеем дело с большим количеством размерностей, наглядно отобразить которые мы определённо не можем. Заметьте, что 28×28 – это очень маленькое изображение, в наше время большинство изображений куда больше. Следовательно, нам нужны или вычислительные мощности для обработки данных с миллионными размерностями, или мы должны уменьшить их размерность с помощью каких-либо приёмов, вроде метода главных компонент. Разумеется, мы не можем произвольно уменьшить размерность нашего X – нам необходимо не только уменьшить размеры данных, но и сохранить при этом как можно больше информации о них. Так, если мы хотим уменьшить размерность от 784 до 2, чтобы можно было графически отобразить данные, то в этих двух размерностях должно быть заключено как можно больше информации о нашем X.

Как же измерить эту информацию? В обычном методе главных компонент и во многих других традиционных статистических методах для этого используется дисперсия, поскольку если что-либо изменяется в большей степени, то оно несёт и больше информации. Для лучшего понимания представьте себе противоположную ситуацию, когда некоторая переменная жёстко определена. Тогда у неё нет дисперсии, а измерение этой переменной не даёт нам никакой новой информации, ведь мы уже и так знаем, чему она должна быть равна. Таким образом, нам нужно, чтобы в преобразованных данных Z первый столбец нёс наибольшее количество информации, второй столбец – вторую по объёму информацию и так далее. Иначе говоря, два столбца с наибольшей информацией должны быть первыми двумя столбцами Z.

Другая сфера применения метода главных компонент – декорреляция. Легко понять, что наличие корреляции означает, что некоторые данные являются избыточными, поскольку мы можем, например, предсказать значения одного столбца по значениям второго (например, с помощью линейной регрессии). Рассматривая подвижную систему координат, мы можем так её повернуть, что данные станут декоррелированными. Тут вновь возникает вопрос: как найти нужное значение Q для вращения, чтобы получить необходимое преобразование данных?

Получив информацию о наших данных, отсортированную в порядке убывания по каждой размерности, мы можем взять первые две размерности и создать диаграмму рассеяния, что даст нам представление о распределении точек данных и позволит наглядно отобразить данные с большими размерностями.

И последняя сфера применения метода главных компонент, которую мы обсудим, – это предварительная подготовка данных и устранение переобученности. Легко понять, что наши данные часто бывают замусорены шумом. Обычно предполагается, что шум весьма мал сравнительно с собственно данными. Тогда и дисперсия шума будет мала, а сам шум попадёт в последние столбцы наших преобразованных данных Z и будет отброшен. Затем эти новые данные мы можем обработать с помощью методов машинного обучения с учителем, например логистической регрессии. На самом деле мы это уже делали в предыдущем курсе. Избавляясь от шума, мы предотвращаем переобученность модели, получая гарантию, что шум не попадёт в нашу модель. Как вы увидите, концепция предварительного обучения без учителя всплывёт снова, когда мы будем изучать автокодировщики и ограниченные машины Больцмана.

И ещё один взгляд на метод главных компонент состоит в том, чтобы рассматривать преобразованную переменную Z в качестве ряда скрытых переменных, лежащих в основе данных X. Тогда логично предположить, что они не коррелируют, поскольку являются лишь независимыми скрытыми причинами. Логично также предположить, что некоторые данные из X будут коррелировать, поскольку они представляют собой лишь результаты измерения данных, которые, в свою очередь, создаются комбинацией скрытых причин. При использовании метода главных компонент предполагается, что данные являются линейной комбинацией этих скрытых причин. На самом деле в методе главных компонент линейность распространяется в обе стороны: скрытую переменную Z можно рассматривать как линейную комбинацию наблюдаемой переменной X, и наоборот, наблюдаемые данные X являются линейной комбинацией скрытых переменных Z:

Z=XQ,

X=ZQ^{-1}.

Напомню, что впервые мы встретились с понятием скрытых переменных в курсе, посвящённому кластеризации и гауссовым смесям распределений, поскольку в этих моделях предполагалось, что величина и размер кластера являлись скрытыми переменными.

Описание метода главных компонент

Вот и математическое обоснование метода главных компонент. Многие выкладки при этом могут вначале показаться необоснованными, но вы увидите, как они в конце концов сочетаются и в результате приводят ко всем тем свойствам, о которых говорилось в предыдущей лекции.

Итак, первый этап – вычисление ковариации X. Напомним определение ковариации:

\sum_x(i,j)=E[(X_i-\mu_i)(X_j-\mu_j)].

При этом если i = j, то мы получаем обычную дисперсию.

Таким образом, мы получаем матрицу размерностью DxD. С технической точки зрения нельзя просто вычитать средние значения, как в формуле, поскольку величины имеют разные размерности, но сейчас предположим, что мы выровняли размерности.

Далее, как вы знаете, матрица размерностью DxD имеет D собственных значений и D собственных векторов. Если вы не знаете, что такое собственные значения и собственные векторы, я дам короткое пояснение. Не забывайте, что в общем случае умножение на матрицу изменяет направление вектора или, другими словами, вращает его. Собственные векторы матрицы – это специальные векторы, которые не вращаются при умножении на матрицу, а лишь изменяют свою длину. Это изменение длины и называется собственным значением.

Следовательно, мы сможем связать ковариационную матрицу с её собственным вектором и собственным значением, используя формулу

Av=\lambda v,

где λ – собственное значение, v – собственный вектор.

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

Итак, отыскав эти D собственных значений, – что с ними делать дальше? Тут опять будет пропуск в выкладках, просто скажем, что нам нужно разместить собственные значения в убывающем порядке, что значит, что и соответствующие собственные векторы будут размещены в таком же порядке:

Метод главных компонент (PCA)

Справившись с этим, мы можем подставить их в матрицу размерностью DxD:

Метод главных компонент (PCA)

Метод главных компонент (PCA)

Таким образом, собственные значения войдут в диагональную матрицу размерностью DxD, (эту матрицу мы обозначим через Λ), а собственные векторы выстроятся друг напротив друга в матрице, которую мы обозначим через V.

На примере двухмерного случая можно легко убедиться, что

\sum_{x} V=V \Lambda,

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

Ещё одно замечание. Матрица V является ортонормальной. Это значит, что любой собственный вектор, умноженный на самого себя, равен 1, а любой собственный вектор, умноженный на любой другой собственный вектор, равен 0. Это утверждение можно доказать следующим образом. Рассмотрим \lambda_j v_{i}^{T} v_j. при i\neq j. Тогда

\lambda_j v^{T}_{i} v_j=v^{T}_{i} (\lambda_j v_j)=v^{T}_{i} \sum_{x} v_j=(\sum_{X}^{T} v_i)^{T} v_j.

Но мы знаем, что ΣX симметрично, следовательно,

(\sum_{X}^{T} v_i)^{T} v_j=(\lambda_i v_i)^{T} v_j=\lambda_i v_{i}^{T} v_j.

Поскольку это может быть истинным лишь если v^{T}_{i} v_j=0.

И, наконец, последний этап. Рассмотрим преобразованные данные Z. Как вы помните, мы до сих пор не знаем, чему равно Q. Но давайте найдём решение через его ковариацию. Обратите внимание, как мы можем выразить ковариацию Z через ковариацию X:

Метод главных компонент (PCA)

Теперь давайте посмотрим, что будет, если мы предположим, что Q = V. Получится, что ковариация Z равна Λ, которая является диагональной матрицей собственных значений:

\sum_Z=V^T \sum_X V=V^T V\Lambda =\Lambda.

Что это всё значит?

Поскольку все элементы Λ, не лежащие на диагонали, равны 0, это значит, любая размерность i не коррелирует ни с какой другой размерностью j. А это, в свою очередь, означает, что в преобразованных данных корреляция отсутствует. Таким образом, выбрав Q = V, мы декоррелировали Z.

Далее, поскольку в Λ собственные значения отсортированы в порядке убывания, это значит, что первая размерность Z имеет наибольшую дисперсию, вторая размерность Z имеет вторую по величине дисперсию и так далее. Чтобы было понятнее, отметим, что:

\sigma^{2}_{I}=\sum_Z(i,j)=\lambda_i.

Визуализация базы MNIST и нахождение оптимального числа главных компонент

Чтобы загрузить базу MNIST, нужно перейти по адресу https://www.kaggle.com/c/digit-recognizer. Чтобы загрузить код этого занятия, перейдите по адресу https://github.com/lazyprogrammer/machine_learning_examples и найдите папку unsupervised_class2. Нужный файл называется pca.py.

Но для начала хочу обратить ваше внимание на файл util.py. Мы будем постоянно использовать его на протяжении всего курса, поскольку он содержит ряд полезных функций вроде получения данных из Kaggle[1]. Так, мы используем функцию getKaggleMNIST. Она загружает данные из csv-файла, перемешивает их и разбивает на учебный и проверочный наборы:

def getKaggleMNIST():

    # MNIST data:

    # column 0 is labels

    # column 1-785 is data, with values 0 .. 255

    # total size of CSV: (42000, 1, 28, 28)

    train = pd.read_csv(‘../large_files/train.csv’).values.astype(np.float32)

    train = shuffle(train)

    Xtrain = train[:-1000,1:] / 255

    Ytrain = train[:-1000,0].astype(np.int32)

    Xtest  = train[-1000:,1:] / 255

    Ytest  = train[-1000:,0].astype(np.int32)

    return Xtrain, Ytrain, Xtest, Ytest

Теперь переходим к файлу pca.py. Первым делом импортируем, кроме обычных библиотек, функцию PCA из библиотеки sklearn, и функцию getKaggleMNIST из файла util.py:

import numpy as np

import matplotlib.pyplot as plt

from sklearn.decomposition import PCA

from util import getKaggleMNIST

В функции main первым этапом является простая загрузка данных:

def main():

    Xtrain, Ytrain, Xtest, Ytest = getKaggleMNIST()

На втором этапе мы создаём объект типа PCA:

pca = PCA()

Третий этап состоит в том, чтобы поместить данные в Xtrain и получить преобразованные данные в переменной reduced:

reduced = pca.fit_transform(Xtrain)

Следующий этап – графическое отображение всего этого на диаграмме. Делается это следующим образом. Мы берём первый столбец уже редуцированных данных и размещаем их по оси x, а потом берём второй столбец и размещаем его по оси y. При этом установим цвета для Ytrain. Ytrain является всего лишь метками, поэтому получится, что все нули будут одного цвета, все единицы – другого и так далее:

    plt.scatter(reduced[:,0], reduced[:,1], s=100, c=Ytrain, alpha=0.5)

    plt.show()

Далее мы рисуем график дисперсий, являющихся собственными значениями, которые мы рассматривали на предыдущей лекции:

    plt.plot(pca.explained_variance_ratio_)

    plt.show()

И последний этап – накопительное отображение собственных значений, что покажет нам общую дисперсию при выборе определённого количества главных компонент:

    cumulative = []

    last = 0

    for v in pca.explained_variance_ratio_:

        cumulative.append(last + v)

        last = cumulative[-1]

    plt.plot(cumulative)

    plt.show()

if __name__ == ‘__main__’:

main()

Итак, запустим файл.

Метод главных компонент (PCA)

Вначале мы видим распределение данных базы MNIST, спроецированных на два измерения. Как вы можете убедиться, мы получили довольно неплохое разделение, хотя это всего лишь линейный алгоритм. Заметьте тёмно-синюю область в одной части, синюю – в другой, голубую – в третьей и оранжевую внизу. Недостатком тут является то, что всё сгруппировано в одно облако.

Далее мы видим график дисперсии. Как вы можете видеть, большая часть весовых коэффициентов стремится к левой части.

Метод главных компонент (PCA)

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

Метод главных компонент (PCA)

[1] Не забывайте также, что файл train.csv должен быть в папке large_files рядом с папкой unsupervised_class2.

Целевая функция метода главных компонент

Один неочевидный момент при описании метода главных компонент состоит в том, что она фактически минимизирует целевую функцию, причём целевой функцией является именно то, о чём вы и подумали, – квадрат ошибки восстановления данных. Чтобы пояснить это, придётся обратиться к паре вещей, которые могут оказаться для вас чем-то новым.

Рассмотрим полное Q, при котором, конечно же, ошибка восстановления стремится к нулю. Предположим при этом, что мы преобразуем X в Z, а затем обратно в X. В этом случае мы  умножаем Z на величину, обратную Q:

X восстановленное=XQQ^{-1}.

Мы знаем, что по определению обратной величины Q, умноженное на величину, обратную Q, равно I – единичной матрице:

Q^{-1}Q=QQ^{-1}=I.

Но мы также знаем, что Q ортонормированно, а значит, и

Q^{T}Q=I.

Это значит, что

Q^{T}=Q^{-1}.

Таким образом, мы всегда можем вернуть X, умножив Z на транспонированное Q вместо обратной Q величины:

X восстановленное=XQQ^{T}.

Пусть теперь QK – первые K собственных векторов ковариации X, что значит, что это матрица размерностью DxK. X имеет размерность NxD, а Z – размерность NxK. Таким образом, это просто преобразованные данные с уменьшенной размерностью. Поскольку теперь рассматривается не полное Q, у нас будет ненулевая ошибка восстановления. Восстановить данные при этом мы можем с помощью умножения на транспонированное QK:

X восстановленное=XQ_kQ^{T}_{K}.

В другой форме мы это можем записать так:

J=\sum_n |x(n)-Q_kQ^{T}_{K} x (n)|^{2}=|X-XQkQ^{T}_{K}|_F ^{2},

где вертикальные чёрточки с F в конце – так называемая норма Фробениуса. Она является матричным аналогом евклидовой формы. Стоит иметь в виду эту особенность целевой функции метода главных компонент, поскольку мы ещё столкнёмся с ней позже.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: