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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Метод наименьших квадратов'''~--- метод нахождения оптимальных параметров [[регрессионный анализ|лин...)
Строка 1: Строка 1:
-
'''Метод наименьших квадратов'''~--- метод нахождения оптимальных параметров [[регрессионный анализ|линейной регрессии]], таких, что [[регрессионный анализ|невязка]] [[анализ регрессионных остатков|регрессионных остатков]] минимальна. Метод заключается в минимизации евклидова расстояния <tex>\|A\mathbf{w}-\mathbf{y}\| между двумя векторами.
+
'''Метод наименьших квадратов'''&nbsp;&#151; метод нахождения оптимальных параметров [[регрессионный анализ|линейной регрессии]], таких, что [[регрессионный анализ|невязка]] [[анализ регрессионных остатков|регрессионных остатков]] минимальна. Метод заключается в минимизации евклидова расстояния <tex>\|A\mathbf{w}-\mathbf{y}\|</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>A\mathbf{w}</tex> лежит в простанстве столбцов матрицы&nbsp;<tex>A</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{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>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>:
 +
<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>, то
 +
<center><tex>A^TA{\mathbf{w}}-A^T\mathbf{y}=0.</tex></center>
 +
Решение по методу наименьших квадратов несовместной системы <tex>A\mathbf{w}=\mathbf{y}</tex>,
 +
состоящей из&nbsp;<tex>M</tex> уравнений с <tex>N</tex> неизвестными, есть уравнение
 +
<center><tex>A^TA\mathbf{w}=A^T\mathbf{y},</tex></center>
 +
которое называется <i>нормальным уравнением</i>.
 +
Если столбцы матрицы&nbsp;<tex>A</tex> линейно независимы, то матрица&nbsp;<tex>A^TA</tex> обратима
 +
и единственное решение
 +
<center><tex>\mathbf{w}=(A^TA)^{-1}A^T\mathbf{y}.</tex></center>
 +
Проекция вектора&nbsp;<tex>\mathbf{y}</tex> на пространство столбцов матрицы имеет вид
 +
<center><tex>\mathbf{p}=A{\mathbf{w}}=A(A^TA)^{-1}A^T\mathbf{y}=P\mathbf{y}.</tex></center>
 +
Матрица&nbsp;<tex>P=A(A^TA)^{-1}A^T</tex> называется матрицей проектирования вектора&nbsp;<tex>\mathbf{y}</tex> на пространство столбцов матрицы&nbsp;<tex>A</tex>.
 +
Эта матрица имеет два основных свойства: она идемпотентна, <tex>P^2=P</tex>, и симметрична, <tex>P^T=P</tex>.
 +
Обратное также верно: матрица, обладающая этими двумя свойствами есть матрица проектирования на свое пространство столбцов.
 +
 
 +
== Пример постоения линейной регрессии ==
 +
 
 +
Задана выборка&nbsp;&#151; таблица
 +
<center><tex>D=\left(\begin{array}{cc} x_1 & y_1 \\ x_2 & y_2 \\ \dots & \dots \\ x_M & y_M \\ \end{array}\right).</tex></center>
 +
Задана регрессионная модель&nbsp;&#151; квадратичный полином
 +
<center><tex> f = w_3x^2+w_2x+w_1 =\sum_{j=1}^3w_jx^{j-1}.</tex></center>
 +
Назначенная модель является линейной. Для нахождения оптимального
 +
значения вектора параметров&nbsp;<tex>\mathbf{w}=\langle{w_1,...,w_3}\rangle^T</tex> выполняется следующая подстановка:
 +
<center><tex>x^0_i{\mapsto}a_{i1},</tex>&nbsp;&nbsp; <tex>x^1_i{\mapsto}a_{i2},</tex>&nbsp;&nbsp;<tex>x^2_i{\mapsto}a_{i3}.</tex></center>
 +
Тогда матрица&nbsp;<tex>A</tex> значений подстановок свободной переменной&nbsp;<tex>x_i</tex>
 +
будет иметь вид
 +
<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>
 +
Здесь вектор&nbsp;<tex>\mathbf{y}=\langle y_1,\ldots,y_M\rangle</tex>. Требуется найти такие параметры&nbsp;<tex>\mathbf{w}</tex>, которые бы доставляли
 +
минимум этому функционалу,
 +
<center><tex> \mathbf{w}=\arg\min\limits_{\mathbf{w}\in\R^3}(S).</tex></center>
 +
 
 +
Требуется найти такие параметры&nbsp;<tex>\mathbf{w}</tex>, которые доставляют минимум&nbsp;<tex>S</tex>&nbsp;&#151; норме вектора
 +
невязок&nbsp;<tex>A\mathbf{w}-\mathbf{y}</tex>.
 +
<center><tex> \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} </tex></center>
 +
Для того, чтобы найти минимум функции невязки, требуется
 +
приравнять ее производные к нулю. Производные данной функции
 +
по&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> A^TA\mathbf{w}=A^T\mathbf{y}, </tex></center> то есть, <center><tex> \mathbf{w}=(A^TA)^{-1}(A^T\mathbf{y}). </tex></center>
 +
После получения весов можно построить график найденной функции.
 +
 
 +
При обращении матрицы&nbsp;<tex>(A^TA)^{-1}</tex> предполагается, что эта
 +
матрица невырождена и не плохо обусловлена. О том, как работать с плохо обусловленными матрицами см. в статье [[Сингулярное разложение]].
 +
 
 +
== Смотри также ==
 +
* [[Регрессионный анализ]]
 +
* [[Анализ регрессионных остатков]]
 +
* [[Сингулярное разложение]]
 +
 
 +
== Литература ==
 +
* Стренг&nbsp;Г. Линейная алгебра и ее применения. М.:&nbsp;Мир.&nbsp;1980.
 +
* Каханер&nbsp;Д., Моулер&nbsp;К., Нэш&nbsp;С. Численные методы и программное обеспечение. М.:&nbsp;Мир.&nbsp;1998.
 +
 
 +
== Внешние ссылки ==
 +
Wikipedia.org, Least squares http://en.wikipedia.org/wiki/Least_squares
 +
 
 +
[[Категория:Регрессионный анализ]]

Версия 12:01, 16 марта 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.

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

Wikipedia.org, Least squares http://en.wikipedia.org/wiki/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»
Личные инструменты