Инструменты сайта


§

Вспомогательная страница к разделу СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ МАТРИЦЫ.


Сингулярное разложение матрицы в применении к задаче классификации

Сделаем сначала набросок идеи в применении к задаче распознавания изображения.

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

Требуется установить сходство новой $ 101 $-й фотографии

 или  или

с имеющейся коллекцией (выборкой). Пусть каждая фотография оцифрована и представляет собой квадратную матрица порядка $ 100 $ с элементами — вещественными числами из интервала $ [0,1] $. Векторизуем каждую такую матрицу, т.е. «вытянем» ее в одну строку1), представив ее вектором из пространства $ \mathbb R^{10\, 000} $. Обозначим такие векторы $ f_1,\dots, f_{100} $. Тестовую же фотографию, также векторизованную, будем обозначать $ \color{Red} f $.

Если бы все компоненты векторов были «равноправны» (пространство изображений изотропно), то расстояние между векторами $ f_j $ и $ \color{Red}{\widetilde f} $ можно было бы посчитать в стандартной евклидовой метрике: $$ f_j=(f_{j,1},f_{j,2},\dots,f_{j,10000}),\ {\color{Red}{f}}=({\color{Red}{f}}_1,{\color{Red}{f}}_2,\dots, {\color{Red}{f}}_{10000} ) \quad \Rightarrow \quad \|f_j- {\color{Red}{f}} \|=\sqrt{ \sum_{\ell=1}^{10000} (f_{j,\ell}- {\color{Red}{f}}_{\ell} )^2} \, . $$

Однако пространство не является изотропным и одни координаты — или их линейные комбинации могут оказаться более важными — с точки зрения влияния на сходство/различие фотографий, нежели другие (даже если первые меньше вторых по абсолютной величине). Вопрос стоит о смене базиса в пространстве $ \mathbb R^{10\, 000} $, т.е. к построении линейно независимой системы векторов $ \{ \mathfrak X_1,\dots, \mathfrak X_{10000} \} $ таких, что самыми существенными для распознавания вектора $ \color{Red}{\widetilde f} $ координатами в этом базисе $$ {\color{Red}{f}}= \alpha_1 \mathfrak X_1 + \alpha_2 \mathfrak X_2 + \dots + \alpha_{10000} \mathfrak X_{10000} $$ были его первые в небольшом количестве, т.е., скажем числа $ \alpha_1,\alpha_2,\dots, \alpha_5 $.

Как подобрать такой чудесный базис? Первое пожелание — чисто техническое: попробовать подобрать его ортонормированным: $$ \mathfrak X_j \cdot \mathfrak X_k^{\top}= \left\{ \begin{array}{rcc} 1 & npu & j=k; \\ 0 & npu & j\ne k_{}. \\ \end{array} \right. $$ Для такого базиса координаты $ \{\alpha_{\ell}\}_{\ell=1}^{10000} $ вектора $ \color{Red}{\widetilde f} $ (величина проекции $ \color{Red}{\widetilde f} $ на направление $ \mathfrak X_{\ell} $) вычисляютcя особенно просто: $$ \alpha_{\ell}= \color{Red}{\widetilde f} \cdot {\mathfrak X}_{\ell}^{\top} \, . $$ Выберем этот базис с помощью сингулярного разложения матрицы $ F $, составленной из строк $ f_1,\dots, f_{100} $: $$ F=\left[\begin{array}{l} f_1 \\ f_2 \\ \vdots \\ f_{100} \end{array} \right]_{100 \times 10000} \, . $$ Пусть это сингулярное разложение имеет вид $$ F=U \cdot \Sigma \cdot V^{\top} $$ при матрицах $ U \in \mathbb R^{100\times 100}, V \in \mathbb R^{10000\times 10000} $ — ортогональных и матрице $$ \Sigma = \left( \begin{array}{cccc|cc} \sigma_1 & & & & \\ & \sigma_2 & & &\mathbb O_{100 \times (10000-100)}\\ & &\ddots& & \\ & & & \sigma_{100} & \end{array} \right)_{100\times 10000} $$ — имеющей на диагонали сингулярные числа матрицы $ F $, упорядоченные по убыванию $ \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_{100} $. В качестве искомого базиса возьмем строки матрицы $ V^{\top} $, или, что то же, набор транспонированных столбцов матрицы $ V $: $$ \left\{\mathfrak X_{\ell}=V_{[\ell]}^{\top} \right\}_{\ell=1}^{10000} \, . $$ Они образуют ортонормированный базис пространства. Более того, первые сто строк $ \left\{V_{[\ell]}^{\top} \right\}_{\ell=1}^{100} $ образуют базис линейной оболочки системы строк $ f_1,\dots, f_{100} $. Любая строка $ f_j $ однозначно определяется набором своих проекций на направления, заданные векторами $ \left\{V_{[\ell]}^{\top} \right\}_{\ell=1}^{100} $: $$ f_j=\beta_{j1} V_{[1]}^{\top}+ \beta_{j,2} V_{[2]}^{\top}+\dots +\beta_{j,100} V_{[100]}^{\top} \quad npu \quad \beta_{jk}= f_j \cdot V_{[k]} \, . $$

Посмотрим теперь на решение примера $ 6 $ ЗДЕСЬ. Из точного равенства сингулярного разложения $$ F=U \cdot \Sigma \cdot V^{\top} = \sigma_1 U_{[1]} V_{[1]}^{\top}+ \sigma_2 U_{[2]} V_{[2]}^{\top} + \dots + \sigma_{100} U_{[100]} V_{[100]}^{\top} $$ можно попробовать сделать приближенное, оставив из суммы ста слагаемых только небольшое количество первых, соответствующих максимальным сингулярным числам. Оказывается, что такое приближение может достаточно хорошо приближать исходную матрицу $ F $, а следовательно, и любую ее строку. Иными словами, мы переходим от строк $ f_j $ к их приближениям $ \widetilde f_j $, задаваемым, например, пятью слагаемыми $$ \widetilde f_j = \gamma_{j1} V_{[1]}^{\top}+ \gamma_{j2} V_{[2]}^{\top} + \gamma_{j3} V_{[3]}^{\top}+ \gamma_{j4} V_{[4]}^{\top}+ \gamma_{j5} V_{[5]}^{\top} \quad npu \quad \gamma_{jk}= f_j \cdot V_{[k]} \, . $$ И проверить, слишком ли сильно отличается $ \widetilde f_j $ от исходного $ f_j $, узнаваемо ли лицо? Проверка осуществляется, например, несколькими независимыми экспертами. Если их заключение отрицательно, то следует увеличить число слагаемых в формуле, и так дойти до положительного результата.

Если теперь каждую строку $ V_{[k]}^{\top} $ преобразовать в матрицу порядка $ 100 $ в ходе процедуры, обратной изначальной процедуре векторизации, и перевести полученную числовую матрицу на язык пикселей, то получим некоторое изображение — оно называется Eigenface. По смыслу это понятие соответствует понятию собственного вектора (Eigenvector) матрицы. Однако перевод по аналогии на русский язык как «собственное лицо» — звучит несколько двусмысленно. И мы будем пользоваться только этим немецко-английским словом.

Имея в распоряжении этот усеченный базис из Eigenfaces, мы можем, фактически любую фотографию из нашей коллекции представить в виде набора координат, т.е. вектора проекций: $$ \Gamma_j = (\gamma_{j1}, \gamma_{j2}, \gamma_{j3}, \gamma_{j4}, \gamma_{j5}) \in \mathbb R^5 \, . $$ Более того, и тестовое изображение $ \color{Red} f $ тоже можно представить аналогичным приближением $$ {\color{Red}{f}} \approx {\color{Red}{\widetilde f}} = \tau_1 V_{[1]}^{\top}+ \tau_{2} V_{[2]}^{\top} + \tau_{3} V_{[3]}^{\top}+ \tau_{4} V_{[4]}^{\top}+ \tau_{5} V_{[5]}^{\top} \quad npu \quad \tau_{k}= {\color{Red}{f}} \cdot V_{[k]} \, , $$ т.е. снова вектором $$ \mathrm{T} = (\tau_{1}, \tau_{2}, \tau_{3}, \tau_{4}, \tau_{5}) \in \mathbb R^5 \, . $$ И можно попытаться оценить близость $ {\color{Red}{f}} $ к изображению $ f_j $ через расстояние между векторами $ \Gamma_j $ и $ \mathrm{T} $.

Тем самым, введение нового базиса пространства $ \mathbb R^{10000} $, состоящего из набора Eigenfaces, взятых в порядке убыванию соответствующих сингулярных чисел матрицы $ F $, позволяет понизить размерность пространстве, в котором решается задача типа «близко-далеко».

Один вычислительный аспект алгоритма требует пояснения. Каждый Eigenfacе-вектор $ V_{[k]}^{\top} $ содержит $ 10000 $ компонент; при этом $ V_{[k]} $ является собственным вектором матрицы $ F^{\top} F $; порядок последней тоже равен $ 10000 $. Как практически найти собственный вектор матрицы такой размерности? Даже приближенные методы — типа степенного, изложенного ЗДЕСЬ — трудно оцениваемы на точность приближения для матриц таких порядков.

Отложим ответ на этот вопрос до конца настоящего раздела. А пока что попробуем разобраться во внутреннем смысле матрицы $ F \cdot F^{\top} $. Дело в том, что эта матрица связана со статистическими свойствами нашей выборки.

Ковариационная матрица

Обобщим предыдущие рассуждения. Пусть имеется $ m $ фотографий, каждая из которых векторизована в строку из $ n $ чисел. В дальнейшем будем для определенности считать $ m\le n $ (хотя это не всегда существенно).

Поcле векторизации фотографий, произведем еще и центрирование получившейся системы строк. Последнее заключается в вычитании из каждой строки $ f_j $ усредненного значения, вычисленного по всей коллекции: $$ f_j- \overline{f}, \quad npu \quad \overline{f}=\frac{1}{m} \sum_{\ell=1}^{m} f_j \, . $$ Чтобы не вводить новых обозначений будем считать векторы $ \{ f_j \} $ уже центрированными. Таким образом, сумма всех строк матрица $ F $ будет нулевой строкой (и, следовательно, ранг матрицы $ F $ заведомо меньше $ m $).

Рассмотрим $ j $-ю компоненту векторизованной фотографии как случайную величину. $ m $ фотографий задают выборку из $ m $ значений для этой величины: $ f_{j1},f_{j2},\dots,f_{jm} $; записываем эту выборку в виде столбца $ F_{[j]} $. После центрирования, математическое ожидание этой величины становится равным $ 0_{} $. Если бы все компоненты были бы статистически независимы, то наши фотографии представляли бы собой совершенно хаотический набор точек. Однако, в постановке нашей задачи предполагается, что фотографии соответствуют реальному «распознаваемому» большинством людей объекту, а не хаосу.

А это значит, что для двух фотографий (анфас) одного человека некоторой подпоследовательности компонент, отвечающих за изображение левого глаза, будет отвечать расположенная в другом месте того же вектора подпоследовательность, отвечающая за очень изображение правого глаза. И поскольку два изображения глаз не очень сильно различаются, то и соответствующие подпоследовательности тоже не должны сильно различаться. Подпоследовательности, отвечающей за изображение носа, где-то будет соответствовать подпоследовательность, отвечающая за изображение правого уха. Эта взаимосвязь случайных величин называется корреляцией2). Ковариацией между двумя выборками $ F_{[j]} $ и $ F_{[k]} $ (столбцами матрицы $ F $) называется число $$ \operatorname{Cov} ( F_{[j]}, F_{[k]})= \frac{1}{m} \sum_{\ell=1}^m f_{j\ell} f_{k\ell} $$ или, что то же, $$ \operatorname{Cov} ( F_{[j]}, F_{[k]})=\frac{1}{m} \langle F_{[j]}, F_{[k]} \rangle = \frac{1}{m} F_{[j]}^{\top} F_{[k]} \, , $$ где $ \langle , \rangle $ означает скалярное произведение столбцов $ F_{[j]} $ и $ F_{[k]} $, заданное стандартным способом. При $ j=k $ число $ \operatorname{Cov} ( F_{[j]}, F_{[j]}) $ называется дисперсией случайной величины и обозначается в статистике $ \sigma^2_j $. Дисперсия определяет меру разброса случайной величины относительно ее среднего значения, которое в нашем случае равно $ 0_{} $. За что отвечает ковариация двух различных столбцов? Величина $$ \mathbf r_{jk}=\frac{\operatorname{Cov} ( F_{[j]}, F_{[k]})}{ \sqrt{\operatorname{Cov} ( F_{[j]}, F_{[j]}) \operatorname{Cov} ( F_{[k]}, F_{[k]})}} = \frac{\operatorname{Cov} ( F_{[j]}, F_{[k]})}{\sigma_j \sigma_k} $$ называется коэффициентом корреляции Пирсона. Ее геометрическая интерпретация очевидна: это косинус угла между векторами $ F_{[j]} $ и $ F_{[k]} $: $$ =\frac{ \langle F_{[j]}, F_{[k]} \rangle }{\|F_{[j]}\| \cdot \|F_{[k]}\|} \, . $$ Фактически, $ \mathbf r_{jk} $ совпадает с косинусным расстоянием между векторами, с тем только отличием, что косинусное расстояние формально определяется только для векторов с неотрицательными компонентами, т.е. его величина находится в пределах интервала $ [0,1] $. Коэффициент же корреляции может принимать значения из интервала $ [-1,1] $. Если $ \mathbf r_{jk}=\pm 1 $, то векторы $ F_{[j]} $ и $ F_{[k]} $ коллинеарны, т.е. один вектор линейно зависит от другого. Увеличению какой-то координаты одного из них соответствует пропорциональное увеличение (или уменьшение) соответствующей координаты другого.

Квадратная матрица порядка $ n $, составленная из ковариаций между столбцами матрицы $ F $ $$ S= \left[\operatorname{Cov} ( F_{[j]}, F_{[k]})\right]_{j,k=1}^n = \frac{1}{m} F^{\top} F $$ называется выборочной ковариационной матрицей признаков (случайных величин). Матрица $ S $ всегда является положительно полуопределенной, а при $ \det S \ne 0 $ — положительно определенной. Ее собственные числа все неотрицательны. Будем обозначать их $ \lambda_1^2,\lambda_2^2,\dots, \lambda_n^2 $.

Рассмотрим для простоты классический пример с двумя случайными величинами: $ n=2 $.

П

Пример [Гальтон].

В каждой семье, имеющей взрослых детей, замерим рост родителей и рост взрослых детей. Именно это проделал Ф.Гальтон во последней четверти XIX века. Результаты его измерений по $ 205 $ семьям и $ m= 898 $ детям можно найти ЗДЕСЬ. Целью исследования было установление зависимости между усредненным ростом обоих родителей и ростом их детей. Если изобразить полученные данные в виде точек $ \{ C_j=(x_j,y_j)\}_{j=1}^n $ плоскости, то получим следующую диаграмму рассеяния:

Здесь размеры указаны в дюймах ($ 1 $ дюйм $ \approx 2.54 $ см). Гальтон заметил, что диаграмма раccеяния («облако» точек) имеет выраженную эллиптическую структуру3): за исключением отдельных «выбросов» можно это облако хорошо аппроксимировать плоской фигурой с границей в виде некоторого эллипса. Центр этого эллипса очевиден из «здравого смысла» — это центроид системы точек $$ C=(\overline{x},\overline{y}) \quad npu \quad \overline{x} =\frac{1}{m} \sum_{i=1}^m x_i,\ \overline{y} =\frac{1}{m} \sum_{i=1}^n y_i $$ т.е. центр определяется средними значениями наших случайных величин. Главные оси этого эллипса Гальтон сумел определить экспериментально, а вот К.Пирсон сумел подвести под эксперимент строгую математику. Решая задачу поиска прямой минимизирующей сумму квадратов расстояний до нее от множества точек плоскости, он пришел к выводу ( см. ЗДЕСЬ), что эта прямая проходит через центроид, а ее направляющий вектор коллинеарен тому собственному вектору матрицы ковариаций $ S $, который соответствует ее наибольшему собственному числу. Это экстремальное свойство собственного вектора можно переформулировать в терминах максимизации суммы квадратов (ортогональных) проекций того же множества точек на произвольную прямую плоскости.

Изображенный на рисунке эллипс рассеяния4) содержит внутри себя $ 782 $ точки диаграммы рассеяния, т.е. $ \approx 87 $ % их общего числа. Как он был получен? Если центрировать экспериментальные данные, то уравнение эллипса: $$ [x,y] S^{-1} \left[\begin{array}{c} x \\ y \end{array} \right] = 4 \, . $$ Для примера Гальтона имеем: $$ C \approx (69.222006, 66.760690), \ S = \left(\begin{array}{ll} 3.300561 & 2.116288 \\ 2.116288 & 12.823009 \end{array} \right) \ , $$ и уравнение эллипса рассеяния: $$ 0.338835\,x^2-0.111841\,xy+0.087214\, y^2-39.443018\,x-3.903031\,y+1491.446950=0 \, . $$ Но нас больше интересуют направляющие векторы главных осей эллипса. Из аналитической геометрии известно, что они совпадают с собственными векторами матрицы $ S^{-1} $, которые, в свою очередь, совпадают с собственными векторами матрицы $ S $. Собственные числа и собственные векторы матрицы $ S $: $$ \lambda_1^2 \approx 11918.39309,\ \mathfrak X_1 \approx \left[0.175075,0.824925 \right]^{\top} , \lambda_2^2 \approx 2560.572830 ,\ \mathfrak X_2 \approx \left[0.824925,-0.175075 \right]^{\top} $$ и большая (малая) ось эллипса направлена вдоль вектора $ \mathfrak X_1 $ ( $ \mathfrak X_2 $ ), соответствующего $ \lambda_1^2 $ ( $ \lambda_2^2 $), т.е. наибольшему (наименьшему) собственному числу ковариационной матрицы. Длины осей пропорциональны $ \lambda_1 $ и $ \lambda_2 $.

В общем же случае $ n $ центрированных случайных величин (и при условии вероятности равной $ 1/m $), $ n $-мерный эллипсоид рассеяния задается уравнением $$ X^{\top} S^{-1} X = n+2 \quad npu \quad X^{\top}=(x_1,x_2,\dots,x_n) . $$ Константа в правой части выбирается из особых соображений, о которых сейчас рассказывать не буду. Нас больше интересует, что для достаточно широкого класса случайных процессов этот эллипсоид5) адекватно описывает диаграмму рассеяния. Его главные оси коллинеарны собственным векторам ковариационной матрицы (и, напомню, они взаимно ортогональны), а длины осей пропорциональны собственным числам. Наибольшая ось показывает направление максимального разброса точек диаграммы рассеяния, наименьшая — минимального. В терминах статистики, этот результат можно переформулировать следующим образом. Двумерная случайная величина, заданная выборкой точек $ \{(x_j,y_j)\} $, при проецировании на прямые, проходящие через центроид, и с направляющими векторами, определяемыми собственными векторами матрицы ковариаций $ S $ порождают выборки случайных величин, с экстремальными значениями дисперсий из всех возможных проекций на прямые, проходящие через центроид. В частности, проецирование на прямую, задаваемую собственным вектором, принадлежащим максимальному (минимальному) собственному числу, задает случайную величину с максимальной (минимальной) дисперсией. Кроме того, все эти новые случайные величины имеют попарные ковариации равными нулю, поскольку собственные векторы симметричной матрицы попарно ортогональны. Следовательно матрица ковариаций этих случайных величин является диагональной.

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

Последняя фраза предыдущего пункта представляет собой статистическую интерпретацию известного из алгебры экстремального свойства собственных чисел симметричной матрицы. Мы пытаемся найти новый базис пространства $ \mathbb R^n $, в котором матрица $ S $ (симметричная) имела бы диагональный вид. Известно, что такой базис можно построить, причем базис ортогональный. Иными словами, существует ортогональная матрица $ P \in \mathbb R^{n\times n} $, что $$ S=P \left( \begin{array}{cccc} \lambda_1^2 & & & \mathbb O \\ & \lambda_2^2 & & \\ && \ddots & \\ \mathbb O&& & \lambda_n^2 \end{array} \right)P^{\top} \ , $$ где $ \lambda_1^2,\lambda_2^2,\dots,\lambda_n^2 $ — собственные числа матрицы $ S $, а столбцы матрицы $$ P=\left[P_{[1]}\mid P_{[2]} \mid \dots \mid P_{[n]} \right] $$ — соответствующие им собственные векторы. По сути, такое представление симметричной и положительно определенной матрицы является частным случаем сингулярного разложения. Перепишем его в терминах столбцов матрицы: $$ S=\sum_{j=1}^n \lambda_j^2 P_{[j]}P_{[j]}^{\top} $$ Векторы-столбцы $ \{ P_{[j]} \}_{j=1}^n $ или одноранговые симметричные матрицы $ \{ P_{[j]}P_{[j]}^{\top} \}_{j=1}^n $ называются главными компонентами для матрицы $ S $. Договоримся всегда в дальнейшем нумеровать эти компоненты в порядке убывания (невозрастания) собственных чисел: $$ \lambda_1^2 \ge \lambda_2^2 \ge \dots \ge \lambda_n^2 \, . $$ В приведенном выше примере Гальтона собственные числа матрицы ковариаций $ \lambda_1^2 \approx 11918.39309 $ и $ \lambda_2^2 \approx 2560.572830 $ не слишком сильно различались по величине, коэффициент сжатия эллипса рассеивания $ \lambda_2/\lambda_1 \approx 0.5 $. А что произойдет если этот коэффициент станет близким нулю? Эллипс становится все более сплюснутым к большой оси, т.е. фактически, к отрезку прямой. Тогда можно предположить, что реальный процесс, описываемый нашими статистическими данными, на самом деле, описывается некоторым линейным законом, т.е. прямой. Наличие отклонений точек от этой гипотетической прямой (т.е. эллипсовидность диаграммы рассеяния) является следствием зашумленности данных ошибками измерений.

Whenever we may suppose that variation is due to errors of observation or measurment, — i.e., is not organic, but there exists a unique functional relation between the true values of variables, — then, assuming it is of the first degree, we may determine the best values of the constants in the manner given above [1].

Для общего случая $ n $-мерного случайногого процесса, описываемого выборкой с матрицей ковариации $ S $, предположим, что ее спектр, упорядоченный по невозрастанию, можно разбить на две подпоследовательности: числа $ \lambda_1^2,\dots,\lambda_k^2 $ существенно больше $ \lambda_{k+1}^2,\dots,\lambda_n^2 $. Тогда в полной сумме представления матрицы $ S $ посредством ее главных компонент можно попытаться пренебречь малыми слагаемыми, т.е. рассмотреть матрицу $$ S_k = \sum_{j=1}^k \lambda_j^2 P_{[j]}P_{[j]}^{\top} $$ как приближение матрицы $ S $. Заметим, что матрица $ S_k $ имеет симметрична и имеет ранг $ k $. Ошибка приближения $ \|S-S_k \| $ может быть оценена посредством вычисления следа матрицы $$ \|S-S_k \|= \sqrt{\operatorname{Sp} (S-S_k)^2}\, . $$ Что происходит при таком приближении матрицы с $ n $-мерным эллипсоидом рассеяния? Он проецируется на гиперплоскость, проходящую через центроид, с направляющими векторами, совпадающими с первыми $ k $ компонентами. Почему именно на эту гиперплоскость? Во-первых, потому что из всех гиперплоскостей такой размерности общая ошибка приближения (сумма квадратов отклонений точек от гиперплоскости) будет минимальной. Во-вторях, размеры проекции будут максимально возможными. Образно говоря, тень, отбрасываемая эллипсоидом на такую гиперплоскость наиболее адекватно отражает истинные размеры этого эллипсоида!

В этом и заключается первая принципиальная сущность метода главных компонент: отбросить малое, оставив существенное. Особенно хорошо, если этого существенного не так много, т.е. $ k \ll n $. Вторая же особенность метода состоит в том, что, как правило, удается избежать вычисления всего спектра матрицы $ S $, т.е. обойти весьма дорогостоящую процедуру вычисления ее характеристического полинома. Это можно сделать, хотя бы, в рамках степенного метода решения частичной проблемы собственных чисел: см. ЗДЕСЬ.

Классификация

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

Тем не менее, возникает желание использовать идею метода главных компонент и для этого случая.

Гипотеза состоит в том, что наибольший разброс данные будут имет в направлениях, «соединяющих» центры групп, а значит, проекции на старшие главные компоненты обеспечат наилучшую «точку зрения» на данные, когда группы видны на наибольших расстояниях и не закрывают одна другую. [2].

Коллекция фотографий $ 10 $ человек состоит из $ 100 $ фотографий (по $ 10 $ фотографий каждого человека). Для $ 80 $ фотографий классифицированы (достоверно известно кто на них изображен), $ 20 $ – нет. Фотографии — черно-белые, оцифрованные, размерами $ 112 \times 92 $ пикселей. Значения пикселей — от $ 0 $ (абсолютно черный) до $ 255 $ (абсолютно белый). Требуется построить классификатор фотографий, который позволит нам распознать оставшиеся $ 20 $ фотографий.

С этой целью мы делим коллекцию $ 80 $ классифицированных фотографий на две части: $ 60 $ фотографий относим к обучающей выборке,

$ 20 $ – к тестовой:

Для этих последних временно «забываем» их классы. Настраиваемый классификатор должен — на основе обучающей выборки — выдавать значения класса для каждой фотографии тестовой выборки. Качество классификатора будем оценивать формулой $$ A=\frac{1}{20} \sum_{k=1}^{20} I \{y_{test}[k]=a(X_{test}[k]) \} \ ; $$ здесь

  • $ I $ — индикаторная функция, принимающая значение $ 1 $ если выражение внутри $ \{ . \} $ истинно, и $ 0 $ в противном случае;
  • $ \{X_{test}[1],X_{test}[2],\dots, X_{test}[20]\} $ — фотографии тестовой выборки;
  • $ \{y_{test}[1],y_{test}[2],\dots, y_{test}[20]\} $ — классы фотографий тестовой выборки;
  • $ a $ — настраиваемый классификатор.

Чем ближе значение $ A $ окажется к $ 1 $, тем точнее классификатор: предсказанные им значения классов чаще совпадают с их истинными значениями.6)

Рассмотрим теперь сингулярное разложение матрицы $ F $: $$ F=V \Sigma W^{\top} \, . $$ Матрица $ W^{\top}\in \mathbb R^{80\times 10304} $ представляет собой набор своих строк, т.е. транспонированных столбцов матрицы $ W=[ W_{[1]},\dots, W_{[80]} ] $. Если из каждой такой строки сделать фотографию, то получим изображения, первые $ 30 $ которых приведены ниже:

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

Теперь будем «усекать» набор масок и смотреть как это повлияет на «узнаваемость» фотографии.

Посмотрим как будут изображения трех случайных лиц из нашей коллекции при аппроксимации с помощью аппроксимации сингулярного разложения с $ 1 , 2 , \dots , 9 $ слагаемыми. Левое изображение в каждом ряду — фотография тестовой выборки.

Вычислительные аспекты

Источники

[1]. Pearson K. On lines and planes of closest fit to systems of points in space. Phil. Mag. 1901. V.2, pp. 559-572 pearson1901.pdf

[2]. Александров В.В., Алексеев А.И., Горский Н.Д. Анализ данных на ЭВМ. М.: Финансы и статистика, 1990

[3]. Лагутин М.Б. Наглядная математическая статистика. М.Бином. 2007

1)
Строго говоря, операция векторизации матрицы формально определяется как «вытягивание» этой матрицы в столбец, но в настоящем пункте нам более удобно строчное представление вектора.
2)
Оно не обязательно означает причинно-следственную связь между событиями, описываемыми случайными величинами.
3)
На самом деле, Гальтон заметил нечто большее, но я сейчас несколько опримитивлю его выводы.
4)
concentration ellipse (англ.)
5)
Начиная с этого места, под эллипсоидом (или эллипсом на плоскости) будем понимать не только квадратичное многообразие (коническое сечение), но и тело (фигуру), им ограниченное.
6)
Настраивать классификатор предполагается по-честному, т.е. не учитывать в его вычислительном алгоритме знание классов фотографий тестовой выборки!
algebra2/svd/faces.txt · Последние изменения: 2023/05/08 21:11 — au