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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Смотри также)
(Литература)
Строка 72: Строка 72:
* Стренг Г. Линейная алгебра и ее применения. М.: Мир. 1980.
* Стренг Г. Линейная алгебра и ее применения. М.: Мир. 1980.
* Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир. 1998.
* Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир. 1998.
 +
* Стрижов В. В. Методы индуктивного порождения регрессионных моделей. М.: ВЦ РАН. 2008. 55 с. [[Media:strijov08ln.pdf|Брошюра, PDF]].
== Внешние ссылки ==
== Внешние ссылки ==

Версия 14:26, 24 октября 2008

Метод наименьших квадратов — метод нахождения оптимальных параметров линейной регрессии, таких, что невязка регрессионных остатков минимальна. Метод заключается в минимизации евклидова расстояния \|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

Личные инструменты