Домашнее задание#
1. Базовая задача МНК.#
Теоретический вопрос 1.
Пусть дана выборка точек \(y_i\). Решите аналитически задачу МНК, моделируя данные постоянной величиной \(\check{y}\), что отвечает минимизации функции потерь
Теоретический вопрос 2.
Покажите, что прямая, построенная по методу МНК, всегда проходит через точку \((\bar{x}, \bar{y})\), где \(\bar{x}\) и \(\bar{y}\) - выборочные средние. Обобщите на случай многомерной регрессии.
Практическое задание.
Для четырех выборок из квартета Энскомба вычислите выборочные дисперсии \(x\) и \(y\) координат, а также коэффициент линейной корреляции Пирсона. Изобразите выборки на графиках. Данные можно получить в системе јuруter с помощью библиотеки seaborn, вызвав метод load_dataset('anscombe') .
2. Централизация признаков и МНК.*#
Покажите, что следующие две процедуры приводят к одинаковому результату:
В матрице объект-признак \(X\) из каждого столбца вычитается среднее по столбцу (централизация признаков). После этого вычисляется \(\left(X^T X\right)^{-1}\).
К матрице \(X\) дописывается в конец столбец, состоящий из одних единиц. Вычисляется \(\left(X^T X\right)^{-1}\) и в получившейся матрице вычеркивается последний столбец и последняя строка.
Также проверьте это практически для случайно сгенерированных матриц.
3. Геометрический смысл псевдообратной матрицы.#
На лекции обсуждалось, что метод наименьших квадратов - это способ поставить задачу о решении переопределенной системы \(X w=y\), которая имеет явный ответ, выражающийся через левую псевдообратную матрицу для \(X\). Для недоопределенной системы \(X w=y\) (имеющей бесконечно много решений, объектов меньше, чем признаков) можно поставить задачу о поиске решения с минимальной \(l_2\)-нормой весов \(\|w\|^2=w^T w\). Решите такую задачу и покажите, что ответ выражается через правую псевдообратную матрицу для \(X\). Считайте, что прямоугольная матрица \(X\) имеет полный ранг (максимально возможный).
4. Матрица объект-признак.#
Теоретический вопрос 1.
Пусть \(X\) - матрица объект-признак (размерность \(l \times F\) ), для которой сингулярное разложение имеет вид \(X=\) \(V \sqrt{\Lambda} U^T\). После понижения размерности данных с помощью метода главных компонент, в диагональной матрице \(\Lambda=\operatorname{diag}\left\{\lambda_1 \geq \cdots \geq \lambda_F\right\}\) оставляются только \(\tilde{F}\) наибольших сингулярных чисел: \(\tilde{\Lambda}=\operatorname{diag}\left\{\lambda_1 \geq \cdots \geq \lambda_{\tilde{F}}\right\}\). При этом данные, как правило, можно восстановить только с некоторой ошибкой: \(\tilde{X}=V \sqrt{\tilde{\Lambda}} U^T \neq X\). Покажите, что норма Фроббениуса ошибки выражается через сумму по оставшимся сингулярным числам:
Теоретический вопрос 2.
Покажите, что сингулярный вектор матрицы \(X\), отвечающий наибольшему сингулярному числу, является решением задачи
где подразумевается матричное умножение \(X\) на \(\boldsymbol{u}\).
Практическое задание.
Сгенерируйте случайную симметричную матрицу \(A\) размера \(3 \times 3\). Сгенерируйте \(N\) элементов из нормального распределения \(P \propto e^{-\boldsymbol{x}^T A \boldsymbol{x}}\) (получится матрица объект-признак \(X\) размерности \(N \times 3\) ). Визуализируйте полученное облако точек (для построения интерактивных трехмерных графиков можно воспользоваться пакетом ipyml в системе jupyter). Примените к матрице \(X\) метод главных компонент, визуализируйте сингулярные вектора вместе с облаком точек, а также двумерные проекции элементов выборки на плоскости, задаваемые сингулярными векторами.
5. Геометрический смысл сингулярного разложения.#
Теоретический вопрос 1.
Пусть дан набор точек на плоскости \(\left(x_i, y_i\right)\), для которых выборочные средние \(x_i\) и \(y_i\) равны нулю. Покажите, что сингулярный вектор для матрицы объект-признак, отвечающий наибольшему сингулярному числу, задает прямую \(a\) (проходящую через начало координат), которая является решением следующей задачи оптимизации:
где distance \(\left[\left(x_i, y_i\right) ; a\right]\) - расстояние от точки \(\left(x_i, y_i\right)\) до прямой \(a\) (равное длине перпендикуляра). Обратите внимание, что такая задача отличается от задачи МНК, в которой расстояние от точки до аппроксимирующей прямой вычисляется не по перпендикуляру, а вдоль оси \(y\), отвечающей целевой переменной.
Теоретический вопрос 2.
Пусть дан набор из \(N\) точек в трехмерном пространстве \(X_{i \alpha}, i \in\{1, \ldots, N\}, \alpha \in\{1,2,3\}\). Покажите, что задача нахождения сингулярных чисел матрицы \(X\) эквивалентна нахождению главных моментов инерции твердого тела, составленного из набора точечных масс, расположенных в точках \(\left(X_{i 1}, X_{i 2}, X_{i 3}\right)\) (можно представлять себе, что точечные массы соединены между собой невесомыми и абсолютно жесткими стержнями).
Практическое задание.
Пусть в SVD-разложении можно пренебречь следующими малыми сингулярными значениями: \(\varepsilon>\sigma_{r+1} \geq \sigma_{r+2} \geq \cdots \geq \sigma_n\). \(\left(\varepsilon=10^{-8}\right)\). Тогда \(x_{T S V D}=\sum_{i=1}^r \sigma_i^{-1} v_i\left(u_i^T b\right)(*)\). Параметр \(\varepsilon\) определяет версию усеченного SVD (TSVD). Решение TSVD (* ) широко используется в качестве упорядоченного решения задачи. Однако решение (*) не является достаточно точным. Это может быть указано следующим образом.
Пусть матрицы левого и правого сингулярных векторов TSVD обозначены как \(U_{T S V D}=\left[u_1, \ldots, u_r\right]\) и \(V_{T S V D}=\left[v_1, \ldots, v_r\right]\), а их ортогональное дополнение \(\widetilde{U_{a d d}}=\left[\widetilde{u_{r+1}}, \ldots, \widetilde{u_n}\right]\) и \(\widetilde{V_{a d d}}=\) \(\left[\widetilde{v_{r+1}}, \ldots, \widetilde{v_n}\right]\). Тогда решение системы будет выглядеть следующим образом:
Вектор \(z_2\) находится: \(\mathrm{C}_2=b_2\), где \(C={\widetilde{U_{a d d}}}^T A \widetilde{V_{a d d}}, \quad b_2=\) \({\widetilde{U_{a d d}}}^T b\).
Рассмотрим в качестве примера СЛАУ с матрицей Гильберта, компоненты которой задаются формулой \(H_{i, j}=\frac{1}{i+j-1}, i, j=\overline{1, n}\). Она относится к числу плохо обусловленных матриц. Характерная особенность этой матрицы в том, что при возрастании еe порядка минимальные собственные числа (сингулярные числа) очень быстро стремятся к нулю.
Решите систему обычным стандартным методом (из библиотеки numpy) и этим методом. Оцените невязку.
\(H_n x_n=b_n\), где \(b_n=\{1,0,0,0,0,0,0,0\}\) для \(\mathrm{n}=8\), \(b_n=\{1,0,0,0,0,0,0,0,0,0\}\) для \(\mathrm{n}=10\).
Число обусловленности для матрицы \(\mathrm{H}_8\) равно \(3.387 \cdot 10^{10}\), а для \(\mathrm{H}_{10}\) равно \(3.535 \cdot 10^{13}\).
6*. Преобразование Прокруста.#
Цель задания - максимально хорошо «подогнать» одну фигуру под другую трансляцией плоскости и поворотом.
Координаты точек даны в файле signatureData.csv
Пусть \(\mathbf{X}_{1}\) и \(\mathbf{X}_{2}-n \times 2\) матрицы, содержащие \(n \ x, y\)-координат точек первой и второй фигур соответственно. Задача сводится к минимизации «прокрустова расстояния» между фигурами
где \(\|\mathbf{X}\|_{F}=\operatorname{tr}\left(\mathbf{X}^{T} \mathbf{X}\right)-\) норма Фробениуса,
\(\mathbf{R}-2 \times 2\) ортогональная матрица поворота,
\(\vec{\mu}\) - двумерный вектор трансляции в плоскости,
\(\mathbf{1}\) - столбец из \(n\) единиц.
Пусть \(\bar{x}_{1}, \bar{x}_{2}-\) двумерные векторы, содержащие среднее по каждому из двух столбцов матриц \(\mathbf{X}_{1}\) и \(\mathbf{X}_{2} .\) Центрируем \(\mathbf{X}_{1}\) и \(\mathbf{X}_{2}\) , то есть вычтем из них среднее по столбцам, и используем SVD:
Тогда решение поставленной задачи даётся формулами:
Используя эти формулы, напишите программу, которая подгоняет одну фигуру под другую и визуализирует результат. Постройте три частных примера - когда фигуры одинаковые, когда они отличаются незначительно и когда они отличаются сильно, чтобы показать результаты работы вашей программы.
Результаты должны выглядеть примерно так:
Докажите эти формулы и примение для данных из файла.
План доказательства:
Расписать целевую функцию, пользуясь инвариантностью следа при циклических перестановках матриц и ортогональностью матрицы поворота
Формально продифференцировать получившееся выражение по \(\vec{\mu}^{T}\), при этом считая нетранспонированный вектор \(\vec{\mu}\) константой (то есть независимой переменной). Приравняв получившееся выражение к нулю, получить первое из равенств.
Единственное слагаемое, содержащее неизвестную \(\mathbf{R}\) в целевой функции, должно иметь вид \(\operatorname{tr}\left(\mathbf{S}^{T} \mathbf{R} .\right) ,\ \mathbf{S} \equiv \overline{\mathbf{X}}_{1}^{T} \overline{\mathbf{X}}_{2}\). Представить матрицу вращений в виде \(\mathbf{R}=\left(\begin{array}{c}\cos \theta & -\sin\theta \\ \sin \theta & \cos \theta \end{array} \right) .\) a \(\mathbf{S}=\) \(\left(\begin{array}{ll}s_{11} & s_{12} \\ s_{21} & s_{22}\end{array}\right)\), продифференцировать получившееся выражение по \(\theta\) и приравнять его к нулю.
Убедиться проверкой, что последнее равенство эквивалентно матричному уравнению \(\mathbf{S}^{T} \mathbf{R}\) = \(\mathbf{R}^{T} \mathbf{S}\). Пользуясь этим равенством и условием ортогональности \(\mathbf{R}\), получить второе равенство.
Дополнение.
Если вам интересно подумать над философским смыслом данного преобразования, рекомендуем почитать основополагающую книгу Винера «Кибернетика, или управление и связь в животном и машине», в особенности главу 6 «Гештальт и универсалии».
Кроме того, преобразование Прокруста и схожие с ним являются отдельной темой исследований в вычислительной математике и имеют много практических применений.