Геометрический подход
Краткое содержание статьи:
- Постановка задачи
- Геометрия задачи
- Определения и полезные теоремы.
- Решения и нормальное уравнение
- Вывод
Постановка проблемы:
Предположим, нам дан набор точек и мы хотим найти лучшую линию. Один из способов формализации этой проблемы - заметить, что каждая линия определяется двумя коэффициентами M и b, например y = Mx + b, поэтому, чтобы найти линию наилучшего соответствия, достаточно найти эти два коэффициента. В идеальном сценарии (т.е. идеально подходит) наша линия удовлетворяет следующим уравнениям:
Теперь, когда мы имеем дело с системой линейных уравнений, давайте запишем эту систему в матричной записи. Для конкретности просто рассмотрим следующий случай:
Теперь проблема просто сводится к поиску решения системы линейных уравнений. К сожалению, если все наши точки не коллинеарны, у этой системы нет решения. Фактически, легко увидеть, что наша система переопределена, то есть больше строк, чем столбцов. Поэтому вместо идеального решения мы остановимся на приближенном решении, а именно на решении, которое удовлетворяет следующему ограничению:
Другими словами, мы ищем линию, которая минимизирует сумму квадратов остатков от точек до линии. Отсюда и название метод наименьших квадратов!
Геометрия задачи:
Полезно думать об Ax как о линейной комбинации столбцов A.
Мы называем множество (пространство) всех возможных линейных комбинаций формы над пространством столбцов A (обозначается Col (A)). Обратите внимание, что если бы столбец 1 был кратен столбцу 2, столбец (A) был бы просто линией в трехмерном пространстве. Поскольку столбцы матрицы A линейно независимы, Col (A) является плоскостью.
Обратите внимание, что плоскость (синяя) пересекает начало координат. Плоскость представляет все линейные комбинации столбцов A, включая комбинацию, в которой мы не берем ни один столбец, ни второй столбец (например, M = 0, b = 0). Еще одно важное наблюдение заключается в том, что столбцы A не охватывают пространство, в котором они живут. Итак, есть векторы в трехмерном пространстве, которых нет в столбце (A), не каждая точка в трехмерном пространстве находится на синей плоскости! Другими словами, существуют точки y, для которых нет решения уравнения Ax = y. Если столбцы A заполнят 3-места, то мы сможем найти точное решение и не будем нуждаться в приближении наименьших квадратов.
Так в чем же задача с геометрической точки зрения?
Мы ищем точку c в пространстве столбцов A на плоскости, которая является ближайшей к точке Y, а не на плоскости. Поскольку c находится на плоскости, Ax = c разрешимо. Оказывается, что c, которое приводит нас к нашему решению задачи методом наименьших квадратов, является ортогональной проекцией Y на пространство столбцов A.
C - наш лучший выбор на Col (A), потому что Y-C - прямая линия от C до Y, перпендикулярная плоскости. Эта линия минимизирует расстояние от Y до плоскости и, как результат, сводит к минимуму нашу ошибку и соответствует нашему критерию наименьших квадратов. Наше решение x методом наименьших квадратов таково, что Ax является ортогнальной проекцией Y на пространство столбцов A.
Так как же нам найти этот прогноз?
Определения и полезные теоремы:
Пространство столбца A: набор всех линейных комбинаций столбцов A.
Пространство строк A: набор всех линейных комбинаций строк A или набор всех линейных комбинаций столбцов A-транспонирования
Пустое пространство A: набор всех линейных комбинаций столбцов A, равных нулевому вектору.
Левое нулевое пространство A: набор всех линейных комбинаций строк A, равных нулевому вектору, или набор всех линейных комбинаций столбцов A-транспонирования, равных нулевому вектору.
Ортогональное дополнение к пространству A: множество всех векторов, ортогональных всем векторам в A.
Теорема 1: ортогональное дополнение пространства столбцов A - это левое нулевое пространство A
Решения и нормальное уравнение:
Что мы знаем о yProj (проекции y на пространство столбцов A)? Мы знаем, что yProj-y ортогонален пространству столбцов A. Напомним, что yProj-y - это вектор, указывающий от y к yProj, длина этого вектора - это расстояние от yProj до Y и является мерой количества ошибка в нашем приближенном решении. Мы хотим минимизировать эту ошибку, поэтому мы хотим минимизировать расстояние от yProj до y, что мы делаем, заставляя yProj-y быть ортогональным Col (A), перпендикулярно ему. Поскольку yProj-y перпендикулярно Col (A), yProj-y является элементом левого нулевого пространства A по теореме 1, что означает, что A-transpose (yProj-y) = 0. После этого наблюдения немного алгебры приведет вас к нормальному уравнению. Важно отметить, что теперь мы можем решить нормальное уравнение обычным способом с использованием исключения Гаусса.
Вывод:
Мы узнали следующее:
- Проблема подгонки линии к точкам может рассматриваться как нахождение такого x, чтобы расстояние от Ax до y было минимальным.
- X, который решает эту проблему, таков, что Ax лежит в пространстве столбцов A
- В частности, Ax - это ортогональная проекция y на пространство столбцов A
- Свойства ортогональной проекции y на пространство столбцов матрицы A приводят нас к нормальному уравнению
- Мы можем решить задачу наименьших квадратов, используя метод исключения Гаусса для решения нормального уравнения
Спасибо за чтение!
