5 Уменьшение размерности описания данных - метод главных компонент (1162173)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Конспект лекции«Уменьшение размерности описания данных: метод главных компонент»по курсу «Математические основы теории прогнозирования» 2011Проблема анализа многомерных данныхПри решении различных задач распознавания предполагается, что в наличии имеетсянекоторая выборка объектов, и для каждого объекта вычислен один и тот же наборпризнаков. На практике объекты могут быть представлены сложными многомерными данными,например, изображениями, набором кривых, текстом, ДНК-микрочипами и т.д. (см.

рис. 1).Поэтому возникает задача извлечения из входных многомерных данных набора признаков,информативных с точки зрения дальнейшего решения задачи распознавания.Рис. 1: Примеры многомерных данных.Любые многомерные данные всегда можно представить в виде вектора чисел. В случаеизображений достаточно развернуть матрицу пикселей в вектор. Для текстов можно вычислитьколичество раз, которое встречается каждое слово в тексте, и сформировать вектор чисел,длина которого определяется общим числом слов в словаре. Подобные вектора чисел имеют, какправило, большую длину, а содержащиеся в них признаки, как правило, малоинформативны.Поэтому рассматривается задача сокращения размерности описания данных с целью полученияотносительно компактного множества информативных признаков.Рассмотрим задачу классификации изображений рукописных цифр MNIST1 .

Здесь имеетсянекоторое количество черно-белых изображений, на каждом из которых представлена однацифра (см. рис. 2). Задача состоит в автоматическом определении цифры для входногоизображения (задача классификации на 10 классов).Для того, чтобы применить методы распознавания в данной задаче, необходимопредварительно выбрать пространство признаков, характеризующее изображения цифр. Впростейшей случае в качестве признаков можно взять исходные интенсивности пикселовизображения.

Тогда для изображения размера 28 × 28 получаем 784 признака. Такой способ1Исходные данные можно скачать по адресу http://yann.lecun.com/exdb/mnist/1Рис. 2: Примеры изображений рукописных цифр из базы данных MNIST.формирования признакового пространства обладает рядом существенных недостатков. Вопервых, получается большое количество признаков. Например, для относительно небольшихизображений размера 300 × 200 получается 60000 признаков. Большое количество признаковприводит к высоким временным затратам на обработку данных, большим объемам памяти,требуемой для хранения информации, а также к необходимости сбора большого числапрецедентов для уверенного восстановления скрытых зависимостей в существенно многомерномпространстве.

Другим серьезным недостатком полученного признакового пространстваявляется тот факт, что близкие в пространстве признаков объекты не соответствуют одним итем же классам (см. рис. 3a). Выполнение гипотезы компактности является одним из основныхтребований для большинства методов распознавания. Методы уменьшения размерности вданных позволяют получать представление выборок в маломерных пространствах, обладающихрядом хороших свойств. В частности, для изображений рукописных цифр метод главныхкомпонент позволяет получить существенно более качественное признаковое пространство (см.рис.

3b).1’1’’2’’3’0.92’1’’2’’3’00.8-20.7Feature 3430.6-40.5-60.40.3-80.2-100.1000.20.40.6Feature 3420.8-1215(a)0-5(b)Рис. 3: Проекция выборки изображений цифр ’1’, ’2’ и ’3’ на два признака, соответствующихинтенсивностям пикселов (a) и на два признака, полученных с помощью метода главныхкомпонент (b).DПусть имеется некоторая выборка объектов X = {xn }Nn=1 , xn ∈ R . Задача уменьшенияразмерности состоит в получении представления этой выборки в пространстве меньшей2dразмерности T = {tn }Nn=1 , tn ∈ R .

Здесь d ≪ D, но в частных случаях d может и совпадать сD. Уменьшение размерности в описании данных может преследовать множество целей:• Сокращение вычислительных затрат при обработке данных;• Борьба с переобучением. Чем меньше количество признаков, тем меньше требуетсяобъектов для уверенного восстановления скрытых зависимостей в данных и тем вышекачество восстановления подобных зависимостей;• Сжатие данных для более эффективного хранения информации. В этом случае помимопреобразования X → T требуется иметь возможность осуществлять также обратноепреобразование T → X;• Визуализация данных.

Проектирование выборки на двух-/трехмерное пространствопозволяет графически представить выборку;• Извлечение новых признаков. Новые признаки, полученные в результате преобразованияX → T , могут оказывать значимый вклад при последующем решении задачраспознавания (например, как метод главных компонент в случае рис.

3b);• и др.Заметим, что описанные далее методы уменьшения размерности относятся к классу методовобучения без учителя, т.е. в качестве исходной информации выступает только признаковоеописание объектов X. В частности, в задаче классификации рукописных цифр результат,показанный на рис.

3b, был получен без использования информации о цифрах (метках класса).Метод главных компонентМетод главных компонент (разложение Карунена-Лоева, principal component analysis, PCA)является простейшим методом уменьшения размерности в данных. Идея метода заключаетсяв поиске в исходном пространстве гиперплоскости заданной размерности с последующимпроектированием выборки на данную гиперплоскость. При этом выбирается та гиперплоскость,ошибка проектирования данных на которую является минимальной в смысле суммы квадратовотклонений.Пусть D = 2, d = 1, т.е.

задача состоит в проектировании двухмерных данных на прямую.Предположим далее, что прямая проходит через начало координат, а ее направление задаетсяединичным вектором u, ∥u∥ = 1 (см. рис. 4a). Тогда величина проекции вектора x на этупрямую составляет ∥xpr ∥ = uT x, а сам вектор проекции определяется как xpr = ∥xpr ∥u.

Потеореме Пифагора квадрат ошибки проектирования вычисляется как∥xerr ∥2 = ∥x∥2 − ∥xpr ∥2 = xT x − uT xxT u.Таким образом, критерий средней ошибки проектирования выборки X на прямую,задаваемую единичным вектором u, может быть записан как[]NNN∑∑111 ∑ TJ=(x xn − uT xn xTn u) =xT xn − u Txn xTn u.N n=1 nN n=1 nN n=13Признак 2x^errx^xx^ prxerrxxprmuu00Признак 1(a)(b)Рис. 4: Проекция объекта x на прямую, задаваемую направляющим вектором u и векторомсдвига µ.∑Обозначим через S матрицу (1/N ) n xn xTn . Минимизация критерия J по u эквивалентнаследующей задаче условной максимизации:uT Su → max,(1)uuT u = 1.Записывая функцию Лагранжа L(u, λ) и приравнивая к нулю все ее производные, получимнеобходимое условие экстремума:L(u, λ) = uT Su + λ(1 − uT u),∇u L(u, λ) = 2Su − 2λu = 0,∂L(u, λ) = 1 − uT u = 0,∂λ⇒ Su = λu,(2)⇒ uT u = 1.(3)Условие (2) означает, что оптимальный вектор u является собственным вектором матрицыS, отвечающим некоторому собственному значению λ.

Заметим, что собственный вектор всегдаопределен с точностью до нормы, поэтому условию (3) всегда можно удовлетворить.Условия (2),(3) являются необходимыми условиями экстремума. Для того, чтобы найтиточку глобального условного максимума критерия (1), подставим условие (2) в критерий (1):J = uT Su = λuT u = λ.Таким образом, оптимальный вектор u является собственным вектором матрицы S,отвечающим ее максимальному собственному значению λmax .Теперь рассмотрим случай, когда прямая не проходит через начало координат (см.рис.

4b). Вектор сдвига прямой µ относительно начала координат всегда можно выбратьперпендикулярно прямой, т.е. µT u = 0. Задача поиска прямой с минимальной ошибкойпроектирования может быть сведена к рассмотренной выше задаче путем перехода от объектов4xn к объектам x̂n = xn − µ:N1 ∑J=((xn − µ)T (xn − µ) − uT (xn − µ)(xn − µ)T u) =N n=1[]NNN∑∑1 ∑ T11(x xn − 2µT xn + µT µ − uT xn xTn u) =xT xn − 2µTxn + µT µ − uT Su.N n=1 nN n=1 nN n=1Приравнивая к нулю градиент J по µ, получаем:][NN1 ∑1 ∑∇µ J = −2xn + 2µ = 0 ⇒ µopt =xn .N n=1N n=1После того, как µ и u найдены, осталось спроектировать выборку X на найденную прямую:tn = uT (xn − µ).(4)Сами объекты выборки в исходном пространстве после проектирования можно вычислитьследующим образом:xn,pr = tn u + µ.(5)Теперь пусть d является произвольным.

Следовательно, нам требуется найти вектор сдвигаµ и направляющие векторы гиперплоскости u1 , . . . , ud такие, чтобы ошибка проектированиявыборки на эту гиперплоскость была бы минимальна. Рассуждая аналогично случаю d = 1,легко показать, чтоN1 ∑µ=xn ,N n=1Sui = λi ui , i = 1, . . . , d,λ1 ≥ λ2 ≥ . . . λD .(6)Таким образом, оптимальные ui являются собственными векторами матрицы S, отвечающиеее d наибольшим собственным значениям. Обозначим через U матрицу [u1 , . . . , ud ]. Тогдаредукция X при проектировании на оптимальную гиперплоскость вычисляется какtn = (xn − µ)T U,а сами точки проекции определяются какxn,pr = tTn U + µ.Метод главных компонент через критерий максимизации разброса вданныхНаряду с критерием минимизации ошибки проектирования можно рассмотретьальтернативный критерий поиска гиперплоскости, связанный с максимизацией разбросаспроектированных точек выборки. Рассмотрим снова простейшую ситуацию D = 2, d = 1.Обозначим через ti случайную величину, соответствующую значению i-ого признака55.53524.5413.5302.5−121.5−210.51234−3−35(a)−2−10123(b)Рис.

5: Пример применения метода главных компонент. На рис. a показана исходная выборкав двухмерном пространстве вместе с направлениеми, определяемыми собственными векторамивыборочной матрицы ковариации. На рис. b показан переход к некоррелированным признакам.в редуцированном пространстве Rd . Характеристикой разброса данных в одномерномпространстве является∑ выборочная дисперсия. Предположим, что наша выборка являетсяцентрированной, т.е.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций