Разница между 1.1386
и текущей версией
МетодНаименьшихКвадратов.
@@ -1,22 +1,20 @@
-- Метод наименьших квадратов
+= Метод наименьших квадратов
-----
* ''''''ToDo'''''' статьи:
1 http://rextester.com/DPAQ80544 — реальный пример
1 картинки: http://rextester.com/DUX29094
1 ссылки на литературу
- 1 формулы: типографика + вывод в терминах $$roman D [ bold x , bold y ] , ~ roman D [ bold x ] .$$
+ 1 типографика
1 ТеоремаГауссаМаркова
1 код на AWK от Г. А.
- 1 [[http://economictheoryblog.com/2015/02/19/ols_estimator/ | вывод для множественного случая]]
* статья удовлетворяет слабому критерию Никитенкова и частично — сильному критерию Никитенкова.
----
В данной статье все вектора по умолчанию являются векторами-столбцами. Внимательно следите за размерностями матриц и векторов по ходу объяснения. Запись многочленов будет обратной, т. е. не $$y = b sub 2 x + b sub 1,$$ а $$y = b sub 1 + b sub 2 x .$$
--- Простейший случай
+- Простейший случай
---- Общая постановка задачи
+-- Общая постановка задачи
Допустим, в рамках некого эксперимента было проведено $$n$$ измерений ¹). Каждое измерение представляет собой пару $$(x sub i , y sub i ),$$ где $$x sub i$$ — ''вход'', $$y sub i$$ — ''выход'' (такую пару будем называть «точкой»).
@@ -35,15 +33,15 @@
Графически можно представить результаты проведённого эксперимента на графике: по оси абсцисс будем откладывать входы, а по оси ординат — выходы. Такой график называется ''диаграмма рассеяния'' (''scatter diagram'', ''scatter plot'', ''scatter chart'').
-Почти никогда не встречается ситуаций, при которых все точки будут лежать на одной прямой. Поэтому мы хотим описать экспериментальные данные линейной функцией («подогнать» их к прямой). По рисунку интуитивно очевидно, что синяя линяя лучше описывать полученные экспериментальные данные, но без какого-либо чёткого математического критерия, нельзя однозначно сказать, какая из линий: синяя или зелёная — более приемлема для целей анализа и прогнозирования.
+Почти никогда не встречается ситуаций, при которых все точки будут лежать на одной прямой. Поэтому мы хотим описать экспериментальные данные линейной функцией («подогнать» их к прямой). По рисунку интуитивно очевидно, что синяя линяя лучше описывает полученные экспериментальные данные, чем красная, но без какого-либо чёткого математического критерия, нельзя однозначно сказать, какая из линий: синяя или зелёная — более приемлема для целей анализа и прогнозирования.
----
[[https://pp.vk.me/c627731/v627731792/1878b/5kzYeQ0sh9o.jpg|http://rextester.com/VGWGO78956| 450px]]
----
-Таким образом, наша цель — найти такую линейную функцию (прямую), которая, в некотором смысле, наилучшим образом описывала бы полученные результаты. Такую функцию назовём ''наилучшей линейной аппроксимацией (НЛА)''. Значения функции НЛА будем называть ''оценками'' и обозначим $$y hat sub i .$$ Сама функция будет иметь вид $$y hat sub i = b sub 1 + b sub 2 x sub i.$$
+Таким образом, наша цель — найти такую линейную функцию (прямую), которая, в некотором смысле, наилучшим образом описывала бы полученные результаты. Такую функцию назовём ''наилучшей линейной аппроксимацией (НЛА)''. Значения функции НЛА будем называть ''оценками'' или ''прогнозами'' и обозначим $$y hat sub i .$$ Сама функция будет иметь вид $$y hat sub i = b sub 1 + b sub 2 x sub i .$$
-Каждому измерению входа $$x sub i$$ будет соответствовать реальное значение $$y sub i$$ и оценка $$y hat sub i .$$ Разницу между реальным значением и оценкой будем называть ''отклонением'' и обозначим $$d sub i = y sub i - y hat sub i = y sub i - (b sub 1 + b sub 2 x sub i ) = y sub i - b sub 1 - b sub 2 x sub i.$$
+Каждому измерению входа $$x sub i$$ будет соответствовать реальное значение $$y sub i$$ и оценка $$y hat sub i .$$ Разницу между реальным значением и оценкой будем называть ''отклонением'' или ''ошибкой прогноза'' и обозначим $$d sub i = y sub i - y hat sub i = y sub i - (b sub 1 + b sub 2 x sub i ) = y sub i - b sub 1 - b sub 2 x sub i.$$
----
[[https://pp.vk.me/c627731/v627731792/187bb/2_Gbds1I6ko.jpg| http://rextester.com/PXN34584 | 450px]]
@@ -51,7 +49,7 @@
Таким образом, нам нужна такая линейная функция, для которой общее отклонение реальных экспериментальных значений от оценок было бы наименьшим. При этом общее отклонение не обязательно должно быть измерено как сумма отклонений для всех измерений.
---- Выбор способа «подгонки»
+-- Выбор способа «подгонки»
Существует большое количество способов измерить общее отклонение реальных экспериментальных значений от их оценок. Приведём самые очевидные из них:
@@ -69,9 +67,9 @@
Третий способ, давший имя методу наименьших квадратов, позволяет избежать проблем, связанных с робастностью. Более сильные отклонения вносят бо́льшие вклады, а слабые отклонения нивелируются — взаимного погашения при этом возникнуть не может, т. к. квадрат числа неотрицателен. Вместе с этим, уходит и проблема, связанная с дифференцированием: квадратическая функция является всюду дифференцируемой. Этим, а также и другими причинами (в том числе и причинами, выявленными А. А. Марковым в связи с использованием МНК в статистическом оценивании), был обусловлен выбор способа.
-Таким образом мы можем формализовать описанную нами задачу: необходимо наити такие значения коэффициентов $$b sub 1$$ и $$b sub 2$$, при которых функция $$Q = sum from i=1 to n d sub i sup 2$$ примет наименьшее значение.
+Таким образом мы можем формализовать описанную нами задачу: необходимо найти такие значения коэффициентов $$b sub 1$$ и $$b sub 2$$, при которых функция $$Q = sum from i=1 to n d sub i sup 2$$ примет наименьшее значение.
---- Математическая формализация
+-- Математическая формализация
%EQ
roman argmin from {b sub 1 , ~ b sub 2} ~ Q =
@@ -82,80 +80,204 @@
Необходимое условие минимума (условие первого порядка):
%EQ
-lpile {
- left {
- lpile {
- {partial Q} over {partial b sub 1} = 0 ~ , above
- {partial Q} over {partial b sub 2} = 0
- }
- right nothing
- ~ \(ti ~
- left {
+left {
+ lpile {
+ {partial Q} over {partial b sub 1} = 0 ~ , above
+ {partial Q} over {partial b sub 2} = 0
+ }
+right nothing
+~ \(ti ~
+left {
lpile {
{partial sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) sup 2} over {partial b sub 1}
= 0 ~ , above
{partial sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) sup 2} over {partial b sub 2}
= 0
}
- right nothing
- ~ \(ti ~
- left {
- lpile {
- {-2} sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) = 0 ~ , above
- {-2} sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) x sub i = 0 .
- }
- right nothing
-}
+right nothing
+~ \(ti ~
+left {
+ lpile {
+ {-2} sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) = 0 ~ , above
+ {-2} sum from i=1 to n (y sub i - b sub 1 - b sub 2 x sub i ) x sub i = 0 .
+ }
+right nothing
%EN
Обратите внимание: условие первого порядка — система дифференциальных уравнений в частных производных размерности два. Точка $$left ( b sub 1 , b sub 2 right ) ,$$ таким образом, — стационарная точка данной системы.
-Разделив оба уравнения системы на $$-2$$ и немного преобразовав получим финальную систему, из которой разными способами будет получать коэффициенты:
+Разделив оба уравнения системы на $$-2$$ и перенеся отрицательные слагаемые в другие части уравнений, получим ''систему нормальных уравнений для МНК'', из которой разными способами получим коэффициенты $$b sub 1 , b sub 2 :$$
%EQ
-lpile {
- left {
- lpile {
- sum from i=1 to n y sub i =
- b sub 1 n + b sub 2 sum from i=1 to n x sub i ~, above
- sum from i=1 to n x sub i y sub i =
- b sub 1 sum from i=1 to n x sub i + b sub 2 sum from i=1 to n x sub i sup 2 .
- }
- right nothing
-}
+left {
+ lpile {
+ sum from i=1 to n y sub i =
+ b sub 1 n + b sub 2 sum from i=1 to n x sub i ~ , above
+ sum from i=1 to n x sub i y sub i =
+ b sub 1 sum from i=1 to n x sub i + b sub 2 sum from i=1 to n x sub i sup 2 .
+ }
+right nothing
%EN
-Для получения коэффициентов в разных формах записи нам потребуется одно общее замечание, следующее из первого уравнения системы: линия наилучшей линейной аппроксимации проходит через центр масс нашего набора данных. Покажем это разделив первое уравнение на $$n$$ и используя принятые в математической статистике обозначения: $$y bar = b sub 1 + b sub 2 x bar ,$$ где $$x bar = size -2 {{sum from i=1 to n x sub i} over n}$$ — среднее (выборочное) вектора $$bold x$$, а $$y bar = size -2 {{sum from i=1 to n y sub i} over n}$$ — среднее (выборочное) вектора $$bold y .$$
-
-Разделив второе уравнение системы на $$n$$ и введя два дополнительных специфичных для математической статистики $$xy bar = size -2 {{sum from i=1 to n x sub i y sub i} over n} ~ , ~~ {x sup size -2 2} bar = size -2 {{sum from i=1 to n x sub i sup 2} over n} :$$
+Далее мы будем получать значения коэффициентов в разных формах записи. Прежде всего, получим самую компактную форму записи, разделив оба уравнения на $$n$$ :
%EQ
left {
lpile {
+ size -2 {{sum from i=1 to n y sub i} over n} =
+ b sub 1 + b sub 2 size -2 {{sum from i=1 to n x sub i} over n} ~ , above
+ size -2 {{sum from i=1 to n x sub i y sub i} over n} =
+ b sub 1 size -2 {{sum from i=1 to n x sub i} over n} +
+ b sub 2 size -2 {{sum from i=1 to n x sub i sup 2} over n}
+ }
+right nothing
+~ \(ti ~
+left {
+ lpile {
y bar = b sub 1 + b sub 2 x bar ~ , above
- xy bar = b sub 1 x bar + b sub 2 {x sup size -2 2} bar
+ xy bar = b sub 1 x bar + b sub 2 {x sup size -2 2} bar ,
}
right nothing
%EN
-Выразив из первого уравнения
-$$b sub 1 = y bar - b sub 2 x bar$$
-и подставив во второе получим
-$$b sub 2 = {xy bar - x bar y bar} over {{x sup size -2 2} bar - {x bar} sup size -1 2}$$
+где $$x bar = size -2 {{sum from i=1 to n x sub i} over n} ~ , y bar = size -2 {{sum from i=1 to n y sub i} over n} ~ , xy = size -2 {{sum from i=1 to n x sub i y sub i} over n} ~ , {x sup size -2 2} bar = size -2 {{sum from i=1 to n x sub i sup 2} over n} $$ — принятые в математической статистике обозначения средних: среднего арифметического элементов вектора $$bold x ,$$ среднего арифметического элементов вектора $$bold y ,$$ среднего значения поэлементого произведения векторов $$bold x , bold y ,$$ среднего квадратичного значения (среднего квадратов) элементов вектора $$bold x$$ соответственно.
+
+Для всех дальнеших рассуждений мы воспользуемся фактом, следующим из первого уравнения $$y bar = b sub 1 + b sub 2 x bar$$ : наилучшая линейная аппроксимация проходит через центр масс наших экспериментальных данных.
+
+----
+[[https://pp.vk.me/c627731/v627731792/18796/Pu7ucv0LNx0.jpg|http://rextester.com/UFPG93288|450px]]
+----
+
+Выразим из этого уравнения коэффициент $$b sub 1 = y bar - b sub 2 x bar .$$ Подставив во второе уравнение системы получим:
+
+%EQ
+lpile {
+ xy bar = b sub 1 x bar + b sub 2 {x sup size -2 2} bar ~ , above
+ xy bar = ( y bar - b sub 2 x bar ) x bar + b sub 2 {x sup size -2 2} bar ~ , above
+ xy bar = x bar y bar - b sub 2 {x bar} sup size -1 2 + b sub 2 {x sup size -2 2} bar ~ , above
+ b sub 2 ({x sup size -2 2} bar - {x bar} sup size -1 2 ) = xy bar - x bar y bar ~ , above
+ b sub 2 = {xy bar - x bar y bar} over {{x sup size -2 2} bar - {x bar} sup size -1 2}
+}
+%EN
В итоге получим коэффициенты:
%EQ
left {
lpile {
- b sub 1 = y bar - k x bar ~ , above
- b sub 2 = {xy bar - x bar y bar} over {{x sup size -2 2} bar - {x bar} sup size -1 2}
+ b sub 1 = y bar - b sub 2 x bar ~ , above
+ b sub 2 =
+ size -2 {
+ {xy bar - x bar y bar} over
+ {{x sup size -2 2} bar - {x bar} sup size -1 2}
+ } .
}
right nothing
%EN
-----
-[[https://pp.vk.me/c627731/v627731792/18796/Pu7ucv0LNx0.jpg|http://rextester.com/UFPG93288|450px]]
-----
+Приведём вторую форму вывода коэффициентов. Для этого подставим $$b sub 1 = y bar - b sub 2 x bar$$ во второе уравнение системы нормальных уравнений для МНК:
+
+%EQ
+lpile {
+ sum from i=1 to n x sub i y sub i =
+ b sub 1 sum from i=1 to n x sub i + b sub 2 sum from i=1 to n x sub i sup 2 ~ , above
+ sum from i=1 to n x sub i y sub i =
+ ( y bar - b sub 2 x bar ) sum from i=1 to n x sub i +
+ b sub 2 sum from i=1 to n x sub i sup 2 ~ , above
+ sum from i=1 to n x sub i y sub i =
+ y bar sum from i=1 to n x sub i -
+ b sub 2 x bar sum from i=1 to n x sub i +
+ b sub 2 sum from i=1 to n x sub i sup 2 ~ , above
+ sum from i=1 to n x sub i y sub i - sum from i=1 to n x sub i y bar =
+ b sub 2 left ( sum from i=1 to n x sub i sup 2 - sum from i=1 to n x sub i x bar right ) ~ , above
+ sum from i=1 to n x sub i (y sub i - y bar ) =
+ b sub 2 sum from i=1 to n x sub i (x sub i - x bar ) .
+}
+%EN
+
+Откуда финально можем получить решение системы в виде
+%EQ
+left {
+ lpile {
+ b sub 1 = y bar - b sub 2 x bar ~ , above
+ b sub 2 =
+ size -2 {
+ {sum from i=1 to n x sub i (y sub i - y bar )} over
+ {sum from i=1 to n x sub i (x sub i - x bar )}
+ } .
+ }
+right nothing
+%EN
+
+Данная формула является абсолютно верной, но совершенно не интуитивной. Попробуем привести её к более читаемому и понятному виду, воспользовавшись следующим свойством средних величин:
+
+%EQ
+lpile {
+ x bar = size -2 {sum from i=1 to n x sub i} over n ~ , above
+ n x bar = sum from i=1 to n x sub i ~ , above
+ sum from i=1 to n x bar = sum from i=1 to n x sub i ~ , above
+ sum from i=1 to n (x sub i - x bar ) = 0 .
+}
+%EN
+
+Аналогично и $$sum from i=1 to n (y sub i - y bar ) = 0 .$$
+
+По большому счёту мы просто записали факт того, что сумма величин вариационного ряда (элементов вектора) равна сумме средних этого ряда (вектора). Умножим полученные равенства на $$x bar$$ по отдельности:
+
+%EQ
+lpile {
+ x bar sum from i=1 to n (x sub i - x bar ) = 0 ~ , above
+ sum from i=1 to n x bar (x sub i - x bar ) = 0
+}
+%EN
+
+%EQ
+lpile {
+ x bar sum from i=1 to n (y sub i - y bar ) = 0 ~ , above
+ sum from i=1 to n x bar (y sub i - y bar ) = 0
+}
+%EN
+
+Воспользовавшись полученной формулой, преобразуем коэффициент $$b sub 2 :$$
+
+%EQ
+b sub 2 =
+size -2 {
+ {sum from i=1 to n x sub i (y sub i - y bar )} over
+ {sum from i=1 to n x sub i (x sub i - x bar )}
+} =
+size -2 {
+ {sum from i=1 to n x sub i (y sub i - y bar ) - 0} over
+ {sum from i=1 to n x sub i (x sub i - x bar ) - 0}
+}
+=
+size -2 {
+ {sum from i=1 to n x sub i (y sub i - y bar ) - sum from i=1 to n x bar (y sub i - y bar )} over
+ {sum from i=1 to n x sub i (x sub i - x bar ) - sum from i=1 to n x bar (x sub i - x bar )}
+} =
+size -2 {
+ {sum from i=1 to n (x sub i - x bar ) (y sub i - y bar )} over
+ {sum from i=1 to n (x sub i - x bar ) sup 2}
+}
+%EN
+
+В числителе данного выражения стоит в точности КовариацияСлучайныхВеличин, а в знаменателе — в точности ДисперсияСлучайнойВеличины. Это можно было бы заметить из самой первый записи коэффициентов, но вторая форма гораздо более привычна.
+
+Финально имеем следующее:
+
+%EQ
+left {
+ lpile {
+ b sub 1 = y bar - b sub 2 x bar ~ , above
+ b sub 2 =
+ {xy bar - x bar y bar} over {{x sup size -2 2} bar - {x bar} sup size -1 2} =
+ size -2 {
+ {sum from i=1 to n (x sub i - x bar ) (y sub i - y bar )} over
+ {sum from i=1 to n (x sub i - x bar ) sup 2}
+ } =
+ size -2 {{roman Cov [ bold x, bold y ]} over {roman D [ bold x ]}}
+ }
+right nothing
+%EN
Необходимое условие минимума (условие первого порядка), вообще говоря, даёт нам точку, подозрительную на экстремум. Для того, чтобы математически строго доказать, что полученное решение — точка минимума функции $$Q$$, исследуем определённость матрицы вторых частных производных (также называемую матрицей Гессе или гессианом). Если матрица вторых частных производных будет положительно определена, то это гарантирует, что найденное решение даст минимум функции $$Q$$. В соответствии с критерием Сильвестра, матрица является положительно определённой, когда все ее угловые миноры положительны.
@@ -201,10 +323,10 @@
ccol{
sum from i=1 to n x sub i
above
- sum from i=1 to n x sub i sup 2
+ sum from i=1 to n x sub i sup 2 ~ .
}
}
-right ] ~ .
+right ]
%EN
Напомним, что $$roman det ( alpha A) = alpha roman det (A)$$, поэтому можем рассматривать матрицу с вынесенной двойкой: умножение матрицы на положительное число не изменит знака её угловых миноров.
@@ -256,9 +378,9 @@
Матрица вторых частных производных, таким образом, по критерию Сильвестра явлется положительно определённой, что даёт нам основания утверждать, что полученное решение — точка минимума функции $$Q$$.
--- Множественный случай
+- Множественный случай
---- Общая постановка задачи
+-- Общая постановка задачи
Расширим наш эксперимент: по-прежнему было проведено $$n$$ измерений, но замерялся не один вход, а $$m$$ различных входов (выход по-прежнему один).
@@ -296,7 +418,7 @@
Сумма квадратов отклонений может быть получена как $$Q = bold d sup roman T bold d.$$ Нам необходимо, найти такой вектор $$bold b$$, чтобы сумма квадратов отклонений была минимальна:
---- Математическая формализация
+-- Математическая формализация
%EQ
roman argmin from bold b ~ Q =
@@ -327,15 +449,45 @@
%EQ
lpile {
- {partial Q} over {partial bold b} =
- {partial ( bold y sup roman T bold y - 2 bold b sup roman T X sup roman T bold y + bold b sup roman T X sup roman T X bold b )} over {partial bold b} =
+ size -2 {{partial Q} over {partial bold b}} =
+ size -2 {{partial ( bold y sup roman T bold y - 2 bold b sup roman T X sup roman T bold y +
+ bold b sup roman T X sup roman T X bold b )} over {partial bold b}} =
-2 X sup roman T bold y + 2 X sup roman T X bold b = 0 ~ , above
- X sup roman T X bold b = X sup roman T bold y ~ , above
- bold b = (X sup roman T X) sup -1 X sup roman T bold y
+ X sup roman T X bold b = X sup roman T bold y ~ , above
+ bold b = (X sup roman T X) sup -1 X sup roman T bold y
}
%EN
--- Список литературы
+Покажем, что условие первого порядке даёт нам минимум функции. Для этого докажем, что матрица вторых производных будет положительно определена:
+
+%EQ
+size -2 {{partial Q} over {partial sup 2 bold b}} =
+size -2 {{partial} over {partial bold b} cdot {partial Q} over {partial bold b}} =
+size -2 {{partial left ( -2 X sup roman T bold y + 2 X sup roman T X bold b right ) }
+over {partial bold b}} =
+2 X sup roman T X
+%EN
+
+Напомним ещё один факт из линейной алгебры. Если некоторая матрица $$A$$ положительно определена, то это в том числе означает, что для любого ненулевого вектора $$bold z$$ подходящей размерности будет выполнятся следующее:
+
+%EQ
+bold z sup roman T A bold z > 0 ~ .
+%EN
+
+Пусть наша матрица разложима в виде $$A = B sup roman T B ~ ,$$ тогда она будет положительно определена:
+
+%EQ
+bold z sup roman T A bold z =
+bold z sup roman T B sup roman T B bold z =
+(B bold z) sup roman T B bold z =
+bold u sup roman T bold u.
+%EN
+
+Произведение $$bold u sup roman T bold u$$ — сумма квадратов значений вектора $$u$$, которая будет неотрицательна всегда, а равно нулю, только если матрица $$B$$ — нулевая матрица.
+
+Вернёмся к нашему примеру: $$size -2 {{partial Q} over {partial sup 2 bold b}} = 2 X sup roman T X$$ — умножение на скаляр не изменит определённости матрицы, а в силу рассуждений, приведённых выше, мы можем смело утверждать, что матрица вторых производных положительно определена, значит, найденное нами решение — точка минимума функции $$Q .$$
+
+- Список литературы
%R(
@@ -373,17 +525,9 @@
%P 21-38
%U http://egei.vse.cz/english/wp-content/uploads/2012/08/mostly+harmeless+econometrics.pdf
-%A Атрашкевич Андрей Анатольевич
-%A Ситкарев Григорий Александрович
-%T Занимательная эконометрика для дошкольников
-%I Издательство Лаборатории прикладной математики и программирования
-%D 2015
-%C Сыктывкар
-%P 65
-
%R)
--- Примечания
+- Примечания
¹) В случае, если МНК используется для обработки социально-экономических данных, вместо «измерение» говорят «наблюдение», вместо «опыт» — «статистическое наблюдение».