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

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

(Различия между версиями)

Версия 10:00, 1 июня 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://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»

Категории: Регрессионный анализ | Энциклопедия анализа данных

@@ Строка 6: / Строка 6: @@
 Эта ошибка есть расстояние от вектора&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>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>.

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

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

Версия 10:00, 1 июня 2008

Содержание

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

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

Смотри также

Литература

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

Просмотры

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

Навигация

Поиск

Инструменты