Информатика и искусственный интеллект: учебник для 10–11 классов

В прошлом уроке про матрицы мы видели: у симметричной матрицы есть ортогональные собственные направления. Сейчас окажется, что именно они отвечают на важнейший вопрос анализа данных — вдоль каких осей облако точек разбросано сильнее всего. Так рождается метод главных компонент: не магия, а прямое следствие ортогональности и множителей Лагранжа.

Проекция на единичный вектор

Пусть у нас $n$ объектов, у каждого — вектор признаков $x_i$ . Спроецируем их на единичное направление $u$ : проекция $i$ -го объекта равна числу $z_i=x_i^\top u$ . Насколько «широко» точки разъезжаются вдоль этой оси, измеряет выборочная дисперсия проекций. Если данные центрированы (среднее вычтено), она равна

\frac1n\sum_i z_i^2=u^\top\!\left(\frac1n X_c^\top X_c\right)\!u=u^\top S u, \qquad S=\frac1n X_c^\top X_c.

Здесь $S$ — ковариационная матрица. Первая главная компонента — это направление, вдоль которого разброс максимален:

u_1=\arg\max_{\lVert u\rVert=1} u^\top S u.

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

Слева облако центрированных ирисов по длине и ширине лепестка, красная ось первой компоненты вдоль вытянутого облака. Справа кривая дисперсии проекции от угла оси: она поднимается к максимуму 3,66 около 23 градусов и падает почти до нуля перпендикулярно — Рис. 38.1. Дисперсия проекции зависит от направления
Каждому углу оси проекции отвечает своя дисперсия $u^\top S u$ . Максимум $3{,}66$ достигается вдоль вытянутой оси облака — это и есть первая главная компонента.

УпражнениеДиагональная ковариация

Ковариация двух признаков диагональна: $S=\left(\begin{smallmatrix}9&0\\0&1\end{smallmatrix}\right)$ . Куда смотрит первая компонента, чему равны собственные значения и какую долю общей дисперсии удерживает первая ось?

Показать ответ

Матрица уже диагональна, поэтому оси координат и есть собственные векторы: $u_1=(1,0)$ с $\lambda_1=9$ и $u_2=(0,1)$ с $\lambda_2=1$ . Первая компонента смотрит вдоль первого признака (у него разброс больше). Доля дисперсии первой оси — $9/(9+1)=0{,}9$ , то есть $90\%$ .

Центрировать обязательно

Вычитание среднего — не формальность. Без него первая ось может просто указывать из начала координат к далёкому облаку, описывая его положение, а не внутренний разброс.

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

От Лагранжа к собственному вектору

Откуда берётся оптимальное направление? Это задача на условный экстремум: максимизировать $u^\top S u$ при ограничении $u^\top u=1$ . Составим лагранжиан

\mathcal L(u,\lambda)=u^\top S u-\lambda\,(u^\top u-1).

Приравняв производную к нулю, получаем $2Su-2\lambda u=0$ , то есть

S u=\lambda u.

Оптимальное направление — собственный вектор ковариационной матрицы, а само $\lambda$ равно дисперсии проекции вдоль него. Максимум достигается на собственном векторе с наибольшим собственным значением.

Если снять ограничение $u^\top u=1$ и разрешить вектору любую длину, та же задача записывается одной дробью

R(u)=\frac{u^\top S u}{u^\top u},

которую называют отношением Рэлея. Растяжение вектора не меняет её значения, так что максимум по всем ненулевым $u$ и максимум по единичным — это одно и то же число $\lambda_1$ . Отношение Рэлея — рабочий инструмент численной линейной алгебры: через него оценивают собственные значения, не находя собственных векторов точно.

УпражнениеПочему именно старший вектор

Разложим единичный вектор $u$ по ортонормированному базису собственных векторов $S$ : $u=\sum_j c_j v_j$ , где $\sum_j c_j^2=1$ . Чему равно $u^\top S u$ в этих координатах и почему максимум достигается на векторе со старшим собственным значением?

Показать ответ

Так как $Sv_j=\lambda_j v_j$ и векторы ортонормированы, $u^\top S u=\sum_j \lambda_j c_j^2$ — это среднее взвешенное собственных значений с весами $c_j^2\ge0$ , сумма которых равна $1$ . Среднее не превосходит наибольшего слагаемого: $u^\top S u\le\lambda_{\max}$ , причём равенство достигается, когда весь вес приходится на старший вектор ( $c$ равен $1$ на нём). Значит, максимум — это $\lambda_{\max}$ вдоль $v_{\max}$ .

Как эти векторы находят на самом деле

Уравнение $Su=\lambda u$ выглядит так, будто ответ можно выписать формулой. Для матрицы $4\times4$ это ещё правда: характеристический многочлен четвёртой степени решается в радикалах. Начиная с пятого порядка формулы нет — и не будет, это теорема Абеля. А ковариационные матрицы в машинном обучении бывают тысячного порядка. Значит, собственные направления не вычисляют, а итерируют.

Простейший способ напрашивается сам. Возьмите произвольный вектор, умножьте на $S$ , нормируйте, повторите:

u_{k+1}=\frac{S u_k}{\lVert S u_k\rVert}.

Разложим старт по собственному базису: $u_0=\sum_j c_j v_j$ . Каждое умножение на $S$ множит $j$ -е слагаемое на $\lambda_j$ , поэтому после $k$ шагов доля $j$ -й компоненты относительно первой равна $(\lambda_j/\lambda_1)^k\,c_j/c_1$ . Всё, кроме старшего направления, гаснет геометрически, и скорость задаёт отношение соседних собственных значений.

Слева логарифмический график: угол между итерацией степенного метода и первой главной осью падает с 90 градусов до машинной точности за семь шагов, рядом пунктирная прямая теоретической скорости отношения собственных значений; справа норма внедиагональной части матрицы при QR-итерациях падает от единиц до машинного нуля к четырнадцатому шагу — Рис. 38.4. Собственные направления итерируют, а не решают формулой
Обе панели считаны на настоящей ковариации всех четырёх измерений ириса. Слева: старт взят почти вдоль самого слабого направления, и всё равно через семь умножений на $S$ угол до первой главной оси падает до машинной точности. Пунктир — теоретическая скорость $(\lambda_2/\lambda_1)^k$ при $\lambda_2/\lambda_1=0{,}0574$ ; реальная кривая идёт даже круче, потому что у старта была ничтожная примесь первого направления. Справа: QR-итерации $A_{k+1}=R_kQ_k$ гасят внедиагональную часть к четырнадцатому шагу, и на диагонали проступают все собственные значения сразу: $4{,}228$ , $0{,}243$ , $0{,}078$ , …

Степенной метод даёт одно направление — старшее. Чтобы получить весь набор, применяют QR-алгоритм: матрицу раскладывают на ортогональную и треугольную части, $A_k=Q_kR_k$ , и перемножают их в обратном порядке, $A_{k+1}=R_kQ_k$ . Каждый такой шаг — преобразование подобия, поэтому собственные значения не меняются, а внедиагональная часть тает. Для симметричной матрицы предел диагонален, и на диагонали стоят ровно те $\lambda_j$ , которые нам нужны.

УпражнениеКогда итерации буксуют

Скорость степенного метода задаёт $(\lambda_2/\lambda_1)^k$ . Что произойдёт, если два старших собственных значения совпадают, $\lambda_1=\lambda_2$ ? Что это значит геометрически?

Показать ответ

Отношение равно единице, и множитель $(\lambda_2/\lambda_1)^k=1$ ничего не гасит: метод не сходится к отдельному вектору. И правильно делает — сходиться не к чему. При $\lambda_1=\lambda_2$ дисперсия одинакова во всех направлениях плоскости, натянутой на $v_1$ и $v_2$ : любая пара ортогональных осей в этой плоскости одинаково хороша, «первой компоненты» просто не существует. Итерации сойдутся к какому-то вектору из этой плоскости — к какому именно, решит случайный старт. Это не дефект алгоритма, а честный ответ: вопрос был задан некорректно.

Собственные векторы ковариации ортогональны

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

Облако ирисов трёх видов с эллипсом рассеяния. Красная длинная стрелка — первая компонента с собственным значением 3,66, фиолетовая короткая перпендикулярная стрелка — вторая компонента с собственным значением 0,04; оси строго перпендикулярны — Рис. 38.2. Главные оси — ортогональные собственные векторы ковариации
Эллипс рассеяния и две его оси. Длинная — первая компонента ( $\lambda_1=3{,}66$ ), короткая перпендикулярная — вторая ( $\lambda_2=0{,}04$ ). Длины полуосей равны $\sqrt{\lambda}$ .

УпражнениеЗнак компоненты

Если $u_1$ — первая главная компонента, то и $-u_1$ ей является. Почему знак собственного вектора не определён, и меняется ли от этого дисперсия проекции или качество восстановления?

Показать ответ

Из $Su=\lambda u$ следует $S(-u)=\lambda(-u)$ : противоположный вектор — тоже собственный с тем же $\lambda$ . Он задаёт ту же прямую, только «в другую сторону». Дисперсия проекции $u^\top S u=(-u)^\top S(-u)$ не меняется, и восстановление $\hat X=ZV^\top$ тоже: знак кода $Z$ и знак компоненты сокращаются. Поэтому у «собственной цифры» или eigenface знак сам по себе не несёт смысла.

Русская линия здесь ведёт к самому понятию ортогональности в статистике. П. Л. Чебышёв и его школа развили теорию ортогональных многочленов и метод наименьших квадратов, где взаимно перпендикулярные направления позволяют раскладывать величину на независимые вклады. Главные компоненты — это ровно такой ортогональный базис, только построенный по разбросу самих данных.

Следующие компоненты и SVD

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

X_c=U\Sigma V^\top.

Столбцы $V$ — это и есть главные компоненты, а собственные значения ковариации связаны с сингулярными числами: $\lambda_j=\sigma_j^2/n$ . Такой путь численно устойчивее, потому что не требует возводить данные в квадрат при построении $S$ .

Спектр и объяснённая дисперсия

Как понять, сколько компонент оставить? Собственные значения, выстроенные по убыванию, образуют спектр (scree plot): первые несколько велики, дальше — быстрый спад. Накопленная доля объяснённой дисперсии

R_m=\frac{\lambda_1+\dots+\lambda_m}{\lambda_1+\dots+\lambda_d}

говорит, какую долю разброса удерживают первые $m$ осей. На реальных рукописных цифрах $8\times8$ уже $13$ компонент из $64$ удерживают $80\%$ дисперсии.

Слева спектр собственных значений цифр в логарифмической шкале круто падает, синяя накопленная дисперсия растёт до 100 процентов и достигает 80 процентов при 13 компонентах. Справа реконструкция цифры четыре по 2, 8, 16 и 40 компонентам, от размытой к чёткой — Рис. 38.3. Спектр компонент и реконструкция цифры
Слева: спектр (красный) круто падает, накопленная дисперсия (синяя) достигает $80\%$ уже при $13$ компонентах. Справа: цифра, восстановленная по $m$ компонентам, от размытой к чёткой.

УпражнениеДисперсия из сингулярных чисел

Центрированная матрица данных имеет сингулярные числа $s=(6,3,2,1)$ , число объектов $n=10$ . Чему равны собственные значения ковариации и какую долю дисперсии удержат первые две компоненты?

Показать ответ

Собственные значения ковариации связаны с сингулярными: $\lambda_j=s_j^2/(n-1)$ , то есть пропорциональны $s_j^2=(36,9,4,1)$ с общим множителем $1/9$ . Доля дисперсии не зависит от множителя: $R_2=(36+9)/(36+9+4+1)=45/50=0{,}9$ . Первые две компоненты удерживают $90\%$ разброса.

КстатиПервые «собственные цифры»

Главные направления цифр можно вернуть в форму картинки — получаются «собственные цифры». Любая цифра приближается их взвешенной суммой; это прямой аналог знаменитых eigenfaces для лиц.

Сжатие и реконструкция

Оставив первые $m$ компонент $V_m$ , строим код $Z=X_c V_m$ и восстановление $\hat X=Z V_m^\top+\mu$ . Средняя квадратичная ошибка восстановления равна сумме отброшенных собственных значений $\lambda_{m+1}+\dots+\lambda_d$ . Это в точности то, что делал линейный автокодировщик: оба ищут наилучшее линейное подпространство под квадратичную ошибку — и находят одно и то же.

Масштаб меняет вопрос

У PCA есть важная тонкость. Если один признак измеряется тысячами (цена в рублях), а другой единицами (масса в килограммах), большая численная дисперсия цены перетянет первую компоненту на себя. PCA по ковариации сохраняет физический масштаб исходных единиц; PCA по корреляции сначала делит каждый признак на его стандартное отклонение и отвечает уже на другой вопрос — о совместных изменениях безразмерных признаков.

ОсторожноМасштаб решает

Один и тот же набор. По ковариации первая ось идёт за крупномасштабным признаком (вертикальная игла). По корреляции признаки уравнены, и ось определяется их связью. Ни один вариант не «правильный» автоматически — выбор по смыслу.

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

PCA — это гипотеза, а не подпись

Красивую ось легко переоценить. Двумерная проекция честно показывает линейную картину, но перекрытие точек не доказывает отсутствия структуры — она может лежать в третьей компоненте или быть нелинейной. PCA чувствительна к выбросам: один испорченный объект с большим отклонением способен повернуть первую ось к артефакту, потому что квадрат расстояния даёт далёкой точке огромный вес. И направление наибольшей дисперсии не обязано быть лучшим для классификации: полезный сигнал порой живёт в оси малого разброса.

Поэтому все средние и масштабы оценивают только по обучающей части, как требует честное разбиение, а тест преобразуют сохранёнными числами. Подпись «первая компонента означает освещение» — это проверяемая гипотеза: её подтверждают спектральным зазором, примерами крайних проекций и повтором на другой части данных, а не одной красивой картинкой.

Коротко о главных компонентах

Дисперсия проекции равна $u^\top S u$ , и её максимум по направлению — это собственный вектор ковариации с наибольшим собственным значением. Компоненты ортогональны, потому что ковариация симметрична; их удобно считать сингулярным разложением. Спектр и накопленная дисперсия подсказывают число осей, а сумма отброшенных собственных значений равна ошибке восстановления — той же, что минимизирует линейный автокодировщик. Но PCA чувствительна к масштабу и выбросам, и её интерпретацию всегда проверяют. Следующий шаг — от линейных осей к нелинейным методам понижения размерности.

Задачи

4баллов

Для четырёх наблюдений $x_1=(2,0)$ , $x_2=(-2,0)$ , $x_3=(0,1)$ , $x_4=(0,-1)$ найдите среднее и выборочную ковариационную матрицу $S=\frac1{n-1}\sum_i(x_i-\bar x)(x_i-\bar x)^\top$ с делителем $n-1=3$ . Вычислите собственные значения по убыванию, единичные главные оси и долю дисперсии первой компоненты $\lambda_1/(\lambda_1+\lambda_2)$ . Проверьте, что след $S$ равен сумме покомпонентных выборочных дисперсий.

5баллов

Пусть $S\in\mathbb R^{d\times d}$ — вещественная симметричная неотрицательно определённая матрица. Методом множителя Лагранжа для $\max u^\top S u$ при $u^\top u=1$ выведите условие $Su=\lambda u$ . Разложите произвольный единичный $u$ по ортонормированному собственному базису и докажите оценку $u^\top S u\le\lambda_{\max}$ . Опишите всё множество максимумов при кратном $\lambda_{\max}$ и объясните, почему для произвольной несимметричной матрицы вывод неверен.

4баллов

Центрированная матрица данных $X_c\in\mathbb R^{20\times4}$ имеет сингулярные числа $s=(10,4,2,1)$ . Ковариация определена как $S=X_c^\top X_c/(n-1)=X_c^\top X_c/19$ . Найдите четыре собственных значения $S$ и накопленную долю дисперсии для $m=1,2,3$ . После PCA с двумя компонентами вычислите среднюю по объектам квадратную ошибку восстановления $\lVert X_c-X_2\rVert_F^2/20$ и остаточную выборочную дисперсию $(s_3^2+s_4^2)/19$ ; объясните разницу знаменателей.

6баллов

На реальных цифрах sklearn.datasets.load_digits (пиксели делить на $16$ , центрировать по среднему обучающей части) сравните PCA через svd_solver="full" для кодов $m\in\{2,8,16,40,64\}$ . Разбейте на train/test по индексам без пересечения. Для каждого $m$ сообщите долю объяснённой дисперсии на train и среднюю квадратичную ошибку восстановления на test, проверив, что $80\%$ дисперсии достигается около $13$ компонент. Отдельно постройте первые шесть главных направлений как изображения $8\times8$ и опишите, какие штрихи они кодируют.

5баллов

Даны два признака с корреляцией $\rho$ и дисперсиями $\sigma_1^2,\sigma_2^2$ , так что $S=\left(\begin{smallmatrix}\sigma_1^2&\rho\sigma_1\sigma_2\\ \rho\sigma_1\sigma_2&\sigma_2^2\end{smallmatrix}\right)$ . Выведите собственные значения в замкнутом виде и покажите, что при $\sigma_1=\sigma_2$ главные оси идут под $45^\circ$ независимо от $\rho\ne0$ . Объясните, как меняется угол первой оси, если $\sigma_2$ становится во много раз больше $\sigma_1$ , и свяжите это с выбором PCA по ковариации против PCA по корреляции.

5баллов

Сгенерируйте признаки $x_1=z+e_1$ , $x_2=100\,(z+e_2)$ со скрытым $z\sim N(0,1)$ и малым шумом $e_i\sim N(0,0{,}1^2)$ . Сравните PCA по ковариации и PCA по корреляции: для каждого варианта найдите loadings первой компоненты и долю объяснённой дисперсии. Объясните, почему по ковариации первая ось почти совпадает с $x_2$ , а по корреляции — с диагональю, и какой критерий ошибки фактически оптимизирует каждый вариант.

6баллов

На цифрах load_digits оцените устойчивость PCA к выбросам и к составу выборки. Сначала испортите один объект, прибавив к нему яркую константу, и сравните первую компоненту с исходной через угол между направлениями. Затем на $50$ bootstrap-подвыборках объектов пересчитайте PCA и измерьте углы ведущих компонент; покажите, что при близких $\lambda_m\approx\lambda_{m+1}$ отдельные оси сильно поворачиваются, хотя $m$ -мерное подпространство остаётся устойчивым. Сформулируйте, какую оговорку требует подпись к конкретной «собственной цифре».