Метод наименьших квадратов

Материал из MachineLearning.

Перейти к: навигация, поиск

Метод наименьших квадратов — метод нахождения оптимальных параметров линейной регрессии, таких, что сумма квадратов ошибок (регрессионных остатков) минимальна. Метод заключается в минимизации евклидова расстояния \|A\mathbf{w}-\mathbf{y}\| между двумя векторами — вектором восстановленных значений зависимой переменной и вектором фактических значений зависимой переменной.

Содержание

Постановка задачи

Задача метода наименьших квадратов состоит в выборе вектора \mathbf{w}, минимизирующего ошибку S=\|A\mathbf{w}-\mathbf{y}\|^2. Эта ошибка есть расстояние от вектора \mathbf{y} до вектора A\mathbf{w}. Вектор A\mathbf{w} лежит в простанстве столбцов матрицы A, так как A\mathbf{w} есть линейная комбинация столбцов этой матрицы с коэффициентами w_1,...,w_N. Отыскание решения \mathbf{w} по методу наименьших квадратов эквивалентно задаче отыскания такой точки \mathbf{p}=A\mathbf{w}, которая лежит ближе всего к \mathbf{y} и находится при этом в пространстве столбцов матрицы A. Таким образом, вектор \mathbf{p} должен быть проекцией \mathbf{y} на пространство столбцов и вектор невязки A\mathbf{w}-\mathbf{y} должен быть ортогонален этому пространству. Ортогональность состоит в том, что каждый вектор в пространстве столбцов есть линейная комбинация столбцов с некоторыми коэффициентами v_1,...,v_N, то есть это вектор A\mathbf{v}. Для всех v в пространстве A\mathbf{v}, эти векторы должны быть перпендикулярны невязке A{\mathbf{w}}-\mathbf{y}:

(A\mathbf{v})^T(A{\mathbf{w}}-\mathbf{y})=\mathbf{v}^T(A^TA{\mathbf{w}}-A^T\mathbf{y})=0.

Так как это равенство должно быть справедливо для произвольного вектора \mathbf{v}, то

A^TA{\mathbf{w}}-A^T\mathbf{y}=0.

Решение по методу наименьших квадратов несовместной системы A\mathbf{w}=\mathbf{y}, состоящей из M уравнений с N неизвестными, есть уравнение

A^TA\mathbf{w}=A^T\mathbf{y},

которое называется нормальным уравнением. Если столбцы матрицы A линейно независимы, то матрица A^TA обратима и единственное решение

\mathbf{w}=(A^TA)^{-1}A^T\mathbf{y}.

Проекция вектора \mathbf{y} на пространство столбцов матрицы имеет вид

\mathbf{p}=A{\mathbf{w}}=A(A^TA)^{-1}A^T\mathbf{y}=P\mathbf{y}.

Матрица P=A(A^TA)^{-1}A^T называется матрицей проектирования вектора \mathbf{y} на пространство столбцов матрицы A. Эта матрица имеет два основных свойства: она идемпотентна, P^2=P, и симметрична, P^T=P. Обратное также верно: матрица, обладающая этими двумя свойствами есть матрица проектирования на свое пространство столбцов.

Пример построения линейной регрессии

Задана выборка — таблица

D=\left(\begin{array}{cc} x_1 & y_1 \\ x_2 & y_2 \\ \dots & \dots \\ x_M & y_M \\ \end{array}\right).

Задана регрессионная модель — квадратичный полином

f = w_3x^2+w_2x+w_1 =\sum_{j=1}^3w_jx^{j-1}.

Назначенная модель является линейной. Для нахождения оптимального значения вектора параметров \mathbf{w}=\langle{w_1,...,w_3}\rangle^T выполняется следующая подстановка:

x^0_i{\mapsto}a_{i1},   x^1_i{\mapsto}a_{i2},  x^2_i{\mapsto}a_{i3}.

Тогда матрица A значений подстановок свободной переменной x_i будет иметь вид

A= \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ \cdots & \cdots & \cdots \\ a_{M 1} & a_{M 2} & a_{M 3} \\ \end{array} \right).

Задан критерий качества модели: функция ошибки

S=\sum_{i=1}^M(f(\mathbf{w},x_i)-y_i)^2=\|A\mathbf{w}-\mathbf{y}\|^2\longrightarrow\min.

Здесь вектор \mathbf{y}=\langle y_1,\ldots,y_M\rangle. Требуется найти такие параметры \mathbf{w}, которые бы доставляли минимум этому функционалу,

\mathbf{w}=\arg\min\limits_{\mathbf{w}\in\R^3}(S).

Требуется найти такие параметры \mathbf{w}, которые доставляют минимум S — норме вектора невязок A\mathbf{w}-\mathbf{y}.

\begin{array}{l} S = \|A\mathbf{w}-\mathbf{y}\|^2=(A\mathbf{w}-\mathbf{y})^T(A\mathbf{w}-\mathbf{y})= \\ =\mathbf{y}^T\mathbf{y}-\mathbf{y}^TA\mathbf{w}-\mathbf{w}^TA^T\mathbf{y}+\mathbf{w}^TA^TA\mathbf{w}= \\ =\mathbf{y}^T\mathbf{y}-2\mathbf{y}^TA\mathbf{w}+\mathbf{w}^TA^TA\mathbf{w}. \end{array}

Для того, чтобы найти минимум функции невязки, требуется приравнять ее производные к нулю. Производные данной функции по \mathbf{w} составляют

\frac{\partial S}{\partial\mathbf{w}}=-2A^T\mathbf{y}+2A^TA\mathbf{w}=0.

Это выражение совпадает с нормальным уравнением. Решение этой задачи должно удовлетворять системе линейных уравнений

A^TA\mathbf{w}=A^T\mathbf{y},
то есть,
\mathbf{w}=(A^TA)^{-1}(A^T\mathbf{y}).

После получения весов можно построить график найденной функции.

При обращении матрицы (A^TA)^{-1} предполагается, что эта матрица невырождена и не плохо обусловлена. О том, как работать с плохо обусловленными матрицами см. в статье Сингулярное разложение.

Смотри также

Литература

  • Стренг Г. Линейная алгебра и ее применения. М.: Мир. 1980.
  • Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир. 1998.
  • Стрижов В. В. Методы индуктивного порождения регрессионных моделей. М.: ВЦ РАН. 2008. 55 с. Брошюра, PDF.

Внешние ссылки

Wikipedia.org, Least squares

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2»