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

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (08:43, 18 декабря 2012) (править) (отменить)
м (→Пример построения линейной регрессии)
 
(19 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Метод наименьших квадратов'''&nbsp;&#151; метод нахождения оптимальных параметров [[регрессионный анализ|линейной регрессии]], таких, что [[регрессионный анализ|невязка]] [[анализ регрессионных остатков|регрессионных остатков]] минимальна. Метод заключается в минимизации евклидова расстояния <tex>\|A\mathbf{w}-\mathbf{y}\|</tex> между двумя векторами.
+
'''Метод наименьших квадратов'''&nbsp;&#151; метод нахождения оптимальных параметров [[регрессионный анализ|линейной регрессии]], таких, что сумма квадратов ошибок ([[анализ регрессионных остатков|регрессионных остатков]]) минимальна. Метод заключается в минимизации евклидова расстояния <tex>\|A\mathbf{w}-\mathbf{y}\|</tex> между двумя векторами — вектором восстановленных значений зависимой переменной и вектором фактических значений зависимой переменной.
== Постановка задачи ==
== Постановка задачи ==
-
Задача метода наименьших квадратов состоит выборе вектора <tex>\mathbf{w}</tex>, минимизирующего ошибку (длину [[регрессионный анализ|вектора невязки]]) <tex>S=\|A\mathbf{w}-\mathbf{y}\|^2</tex>.
+
Задача метода наименьших квадратов состоит в выборе вектора <tex>\mathbf{w}</tex>, минимизирующего ошибку <tex>S=\|A\mathbf{w}-\mathbf{y}\|^2</tex>.
Эта ошибка есть расстояние от вектора&nbsp;<tex>\mathbf{y}</tex> до вектора&nbsp;<tex>A\mathbf{w}</tex>.
Эта ошибка есть расстояние от вектора&nbsp;<tex>\mathbf{y}</tex> до вектора&nbsp;<tex>A\mathbf{w}</tex>.
Вектор&nbsp;<tex>A\mathbf{w}</tex> лежит в простанстве столбцов матрицы&nbsp;<tex>A</tex>,
Вектор&nbsp;<tex>A\mathbf{w}</tex> лежит в простанстве столбцов матрицы&nbsp;<tex>A</tex>,
-
так как&nbsp;<tex>A\mathbf{w}</tex> есть линейная комбинация столбцов этой матрицы коэффициентами&nbsp;<tex>w_1,...,w_N</tex>.
+
так как&nbsp;<tex>A\mathbf{w}</tex> есть линейная комбинация столбцов этой матрицы с коэффициентами&nbsp;<tex>w_1,...,w_N</tex>.
Отыскание решения&nbsp;<tex>\mathbf{w}</tex> по методу наименьших квадратов эквивалентно задаче отыскания такой точки&nbsp;<tex>\mathbf{p}=A\mathbf{w}</tex>,
Отыскание решения&nbsp;<tex>\mathbf{w}</tex> по методу наименьших квадратов эквивалентно задаче отыскания такой точки&nbsp;<tex>\mathbf{p}=A\mathbf{w}</tex>,
которая лежит ближе всего к&nbsp;<tex>\mathbf{y}</tex> и находится при этом в пространстве столбцов матрицы&nbsp;<tex>A</tex>.
которая лежит ближе всего к&nbsp;<tex>\mathbf{y}</tex> и находится при этом в пространстве столбцов матрицы&nbsp;<tex>A</tex>.
Таким образом, вектор&nbsp;<tex>\mathbf{p}</tex> должен быть проекцией&nbsp;<tex>\mathbf{y}</tex> на пространство столбцов и вектор невязки&nbsp;<tex>A\mathbf{w}-\mathbf{y}</tex>
Таким образом, вектор&nbsp;<tex>\mathbf{p}</tex> должен быть проекцией&nbsp;<tex>\mathbf{y}</tex> на пространство столбцов и вектор невязки&nbsp;<tex>A\mathbf{w}-\mathbf{y}</tex>
-
должен быть ортогонелен этому пространству. Ортогональность состоит в том, что каждый вектор в пространстве столбцов
+
должен быть ортогонален этому пространству. Ортогональность состоит в том, что каждый вектор в пространстве столбцов
есть линейная комбинация столбцов с некоторыми коэффициентами&nbsp;<tex>v_1,...,v_N</tex>, то есть это вектор&nbsp;<tex>A\mathbf{v}</tex>.
есть линейная комбинация столбцов с некоторыми коэффициентами&nbsp;<tex>v_1,...,v_N</tex>, то есть это вектор&nbsp;<tex>A\mathbf{v}</tex>.
Для всех&nbsp;<tex>v</tex> в пространстве <tex>A\mathbf{v}</tex>, эти векторы должны быть перпендикулярны невязке&nbsp;<tex>A{\mathbf{w}}-\mathbf{y}</tex>:
Для всех&nbsp;<tex>v</tex> в пространстве <tex>A\mathbf{v}</tex>, эти векторы должны быть перпендикулярны невязке&nbsp;<tex>A{\mathbf{w}}-\mathbf{y}</tex>:
<center><tex>(A\mathbf{v})^T(A{\mathbf{w}}-\mathbf{y})=\mathbf{v}^T(A^TA{\mathbf{w}}-A^T\mathbf{y})=0.</tex></center>
<center><tex>(A\mathbf{v})^T(A{\mathbf{w}}-\mathbf{y})=\mathbf{v}^T(A^TA{\mathbf{w}}-A^T\mathbf{y})=0.</tex></center>
-
Так как это равентсво должно быть справедливо для произвольного вектора&nbsp;<tex>\mathbf{v}</tex>, то
+
Так как это равенство должно быть справедливо для произвольного вектора&nbsp;<tex>\mathbf{v}</tex>, то
<center><tex>A^TA{\mathbf{w}}-A^T\mathbf{y}=0.</tex></center>
<center><tex>A^TA{\mathbf{w}}-A^T\mathbf{y}=0.</tex></center>
Решение по методу наименьших квадратов несовместной системы <tex>A\mathbf{w}=\mathbf{y}</tex>,
Решение по методу наименьших квадратов несовместной системы <tex>A\mathbf{w}=\mathbf{y}</tex>,
Строка 29: Строка 29:
Обратное также верно: матрица, обладающая этими двумя свойствами есть матрица проектирования на свое пространство столбцов.
Обратное также верно: матрица, обладающая этими двумя свойствами есть матрица проектирования на свое пространство столбцов.
-
== Пример постоения линейной регрессии ==
+
== Пример построения линейной регрессии ==
Задана выборка&nbsp;&#151; таблица
Задана выборка&nbsp;&#151; таблица
Строка 42: Строка 42:
<center><tex>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). </tex></center>
<center><tex>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). </tex></center>
-
Задан критерий качества модели: функця ошибки
+
Задан критерий качества модели: функция ошибки
<center><tex> S=\sum_{i=1}^M(f(\mathbf{w},x_i)-y_i)^2=\|A\mathbf{w}-\mathbf{y}\|^2\longrightarrow\min. </tex></center>
<center><tex> S=\sum_{i=1}^M(f(\mathbf{w},x_i)-y_i)^2=\|A\mathbf{w}-\mathbf{y}\|^2\longrightarrow\min. </tex></center>
Здесь вектор&nbsp;<tex>\mathbf{y}=\langle y_1,\ldots,y_M\rangle</tex>. Требуется найти такие параметры&nbsp;<tex>\mathbf{w}</tex>, которые бы доставляли
Здесь вектор&nbsp;<tex>\mathbf{y}=\langle y_1,\ldots,y_M\rangle</tex>. Требуется найти такие параметры&nbsp;<tex>\mathbf{w}</tex>, которые бы доставляли
Строка 55: Строка 55:
по&nbsp;<tex>\mathbf{w}</tex> составляют
по&nbsp;<tex>\mathbf{w}</tex> составляют
<center><tex> \frac{\partial S}{\partial\mathbf{w}}=-2A^T\mathbf{y}+2A^TA\mathbf{w}=0. </tex></center>
<center><tex> \frac{\partial S}{\partial\mathbf{w}}=-2A^T\mathbf{y}+2A^TA\mathbf{w}=0. </tex></center>
-
Это выражение также называется нормальным уравнением. Решение
+
Это выражение совпадает с нормальным уравнением. Решение
этой задачи должно удовлетворять системе линейных уравнений
этой задачи должно удовлетворять системе линейных уравнений
<center><tex> A^TA\mathbf{w}=A^T\mathbf{y}, </tex></center> то есть, <center><tex> \mathbf{w}=(A^TA)^{-1}(A^T\mathbf{y}). </tex></center>
<center><tex> A^TA\mathbf{w}=A^T\mathbf{y}, </tex></center> то есть, <center><tex> \mathbf{w}=(A^TA)^{-1}(A^T\mathbf{y}). </tex></center>
Строка 64: Строка 64:
== Смотри также ==
== Смотри также ==
 +
* [[Линейная регрессия (пример)]]
 +
* [[Нелинейная регрессия]] и метод наименьших квадратов
* [[Регрессионный анализ]]
* [[Регрессионный анализ]]
* [[Анализ регрессионных остатков]]
* [[Анализ регрессионных остатков]]
Строка 71: Строка 73:
* Стренг&nbsp;Г. Линейная алгебра и ее применения. М.:&nbsp;Мир.&nbsp;1980.
* Стренг&nbsp;Г. Линейная алгебра и ее применения. М.:&nbsp;Мир.&nbsp;1980.
* Каханер&nbsp;Д., Моулер&nbsp;К., Нэш&nbsp;С. Численные методы и программное обеспечение. М.:&nbsp;Мир.&nbsp;1998.
* Каханер&nbsp;Д., Моулер&nbsp;К., Нэш&nbsp;С. Численные методы и программное обеспечение. М.:&nbsp;Мир.&nbsp;1998.
 +
* Стрижов В. В. Методы индуктивного порождения регрессионных моделей. М.: ВЦ РАН. 2008. 55&nbsp;с. [[Media:strijov08ln.pdf|Брошюра, PDF]].
== Внешние ссылки ==
== Внешние ссылки ==
-
Wikipedia.org, Least squares http://en.wikipedia.org/wiki/Least_squares
+
[http://en.wikipedia.org/wiki/Least_squares Wikipedia.org, Least squares]
[[Категория:Регрессионный анализ]]
[[Категория:Регрессионный анализ]]
 +
[[Категория:Энциклопедия анализа данных]]
 +
[[Категория:Популярные и обзорные статьи]]

Текущая версия

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