Метод наименьших квадратов
- ToDo статьи:
- http://rextester.com/DPAQ80544 — реальный пример
- картинки: http://rextester.com/DUX29094
- ссылки на литературу
- типографика
- ТеоремаГауссаМаркова
- код на AWK от Г. А.
- статья удовлетворяет слабому критерию Никитенкова и частично — сильному критерию Никитенкова.
В данной статье все вектора по умолчанию являются векторами-столбцами. Внимательно следите за размерностями матриц и векторов по ходу объяснения. Запись многочленов будет обратной, т. е. не 
а 
Содержание
Простейший случай
Общая постановка задачи
Допустим, в рамках некого эксперимента было проведено 
измерений ¹). Каждое измерение представляет собой пару 
где 
— вход, 
— выход (такую пару будем называть «точкой»).
Результаты эксперимента могут быть записаны в таблице, в первом столбце которой будут находиться все значения входов, а во втором — все значения выходов:
![bold x =
left \[
pile {x sub 1 above x sub 2 above vdots above x sub i above vdots above x sub n}
right \] ^ , ~
bold y =
left \[
pile {y sub 1 above y sub 2 above vdots above y sub i above vdots above y sub n}
right \] ^ .](/resources/images/7d6b015dcd1659e9d858f2362cc5f0d40b930119.svg)
Графически можно представить результаты проведённого эксперимента на графике: по оси абсцисс будем откладывать входы, а по оси ординат — выходы. Такой график называется диаграмма рассеяния (scatter diagram, scatter plot, scatter chart).
Почти никогда не встречается ситуаций, при которых все точки будут лежать на одной прямой. Поэтому мы хотим описать экспериментальные данные линейной функцией («подогнать» их к прямой). По рисунку интуитивно очевидно, что синяя линяя лучше описывает полученные экспериментальные данные, чем красная, но без какого-либо чёткого математического критерия, нельзя однозначно сказать, какая из линий: синяя или зелёная — более приемлема для целей анализа и прогнозирования.
Таким образом, наша цель — найти такую линейную функцию (прямую), которая, в некотором смысле, наилучшим образом описывала бы полученные результаты. Такую функцию назовём наилучшей линейной аппроксимацией (НЛА). Значения функции НЛА будем называть оценками или прогнозами и обозначим 
Сама функция будет иметь вид 
Каждому измерению входа будет соответствовать реальное значение и оценка Разницу между реальным значением и оценкой будем называть отклонением или ошибкой прогноза и обозначим 
Таким образом, нам нужна такая линейная функция, для которой общее отклонение реальных экспериментальных значений от оценок было бы наименьшим. При этом общее отклонение не обязательно должно быть измерено как сумма отклонений для всех измерений.
Выбор способа «подгонки»
Существует большое количество способов измерить общее отклонение реальных экспериментальных значений от их оценок. Приведём самые очевидные из них:
- сумма значений отклонений
- сумма абсолютных значений отклонений
- сумма квадратов отклонений
Каждый из этих способов имеет как свои плюсы, так и свои минусы. В каком-то смысле, все они «плохие», поэтому наша задача выбрать наименее «плохой» из них: тот, чьи плюсы перевесят минусы. Для выбора рассмотрим их по отдельности.
Несомненным достоинством первого способа является его чрезвычайная простота. Однако такой способ небезопасен с точки зрения статистических выбросов. Если в наших данных есть два выброса, лежащие по разные стороны от прямой на примерно одном и том же расстоянии, то они погасят друг друга. Если таких выбросов будет много (при малых выборках бывает достаточно и двух), то это может дать нам прямую с неверным угловым коэффициентом 
Казалось бы, недостатки первого способа полностью снимаются вторым. Взятие абсолютного значения (модуля) должно обезопасить нас от проблем с взаимопогашающимися разносторонними выбросами. Однако и у этого способа есть существенные недостатки.
Забегая несколько вперед, скажем, что для получения коэффициентов НЛА мы воспользуемся математическим аппаратом дифференциального исчисления. Модуль же не является всюду дифференцируемой функций. И если это кажется не такой большой проблемой в нашем примере, то когда мы расширим МНК на случай многих независимых переменных, это может сделать вычислительную задачу чрезвычайно трудноразрешимой (а в момент, когда этот метод был открыт и просто практически неразрешимой). Кроме того, неприемлемость данного способа (бо́льшую приемлемость другого) доказал в своё время великий русский математик Андрей Андреевич Марков, чьи работы позволили использовать МНК в статистическом оценивании.
Третий способ, давший имя методу наименьших квадратов, позволяет избежать проблем, связанных с робастностью. Более сильные отклонения вносят бо́льшие вклады, а слабые отклонения нивелируются — взаимного погашения при этом возникнуть не может, т. к. квадрат числа неотрицателен. Вместе с этим, уходит и проблема, связанная с дифференцированием: квадратическая функция является всюду дифференцируемой. Этим, а также и другими причинами (в том числе и причинами, выявленными А. А. Марковым в связи с использованием МНК в статистическом оценивании), был обусловлен выбор способа.
Таким образом мы можем формализовать описанную нами задачу: необходимо найти такие значения коэффициентов 
и 
, при которых функция 
примет наименьшее значение.
Математическая формализация
Необходимое условие минимума (условие первого порядка):
Обратите внимание: условие первого порядка — система дифференциальных уравнений в частных производных размерности два. Точка 
таким образом, — стационарная точка данной системы.
Разделив оба уравнения системы на 
и перенеся отрицательные слагаемые в другие части уравнений, получим систему нормальных уравнений для МНК, из которой разными способами получим коэффициенты 
Далее мы будем получать значения коэффициентов в разных формах записи. Прежде всего, получим самую компактную форму записи, разделив оба уравнения на :
где 
— принятые в математической статистике обозначения средних: среднего арифметического элементов вектора 
среднего арифметического элементов вектора 
среднего значения поэлементого произведения векторов 
среднего квадратичного значения (среднего квадратов) элементов вектора 
соответственно.
Для всех дальнеших рассуждений мы воспользуемся фактом, следующим из первого уравнения 
: наилучшая линейная аппроксимация проходит через центр масс наших экспериментальных данных.
Выразим из этого уравнения коэффициент 
Подставив во второе уравнение системы получим:
В итоге получим коэффициенты:
Приведём вторую форму вывода коэффициентов. Для этого подставим 
во второе уравнение системы нормальных уравнений для МНК:
Откуда финально можем получить решение системы в виде
Данная формула является абсолютно верной, но совершенно не интуитивной. Попробуем привести её к более читаемому и понятному виду, воспользовавшись следующим свойством средних величин:
Аналогично и 
По большому счёту мы просто записали факт того, что сумма величин вариационного ряда (элементов вектора) равна сумме средних этого ряда (вектора). Умножим полученные равенства на 
по отдельности:
Воспользовавшись полученной формулой, преобразуем коэффициент 
В числителе данного выражения стоит в точности КовариацияСлучайныхВеличин?, а в знаменателе — в точности ДисперсияСлучайнойВеличины. Это можно было бы заметить из самой первый записи коэффициентов, но вторая форма гораздо более привычна.
Финально имеем следующее:
![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](/resources/images/afcfd0e10151c0a11b0f0d593c7af2a93a6d6e0a.svg)
Необходимое условие минимума (условие первого порядка), вообще говоря, даёт нам точку, подозрительную на экстремум. Для того, чтобы математически строго доказать, что полученное решение — точка минимума функции 
, исследуем определённость матрицы вторых частных производных (также называемую матрицей Гессе или гессианом). Если матрица вторых частных производных будет положительно определена, то это гарантирует, что найденное решение даст минимум функции . В соответствии с критерием Сильвестра, матрица является положительно определённой, когда все ее угловые миноры положительны.
Достаточное условие максимума (условие второго порядка):
![left \[
matrix {
ccol{
{partial Q} over {partial sup 2 b sub 1}
above
{partial Q} over {partial b sub 2 partial b sub 1}
}
ccol{
{partial Q} over {partial b sub 1 partial b sub 2}
above
{partial Q} over {partial sup 2 b sub 2}
}
}
right \] =
left \[
matrix {
ccol{
2n
above
2 sum from i=1 to n x sub i
}
ccol{
2 sum from i=1 to n x sub i
above
2 sum from i=1 to n x sub i sup 2
}
}
right \] =
2 ~
left \[
matrix {
ccol{
n
above
sum from i=1 to n x sub i
}
ccol{
sum from i=1 to n x sub i
above
sum from i=1 to n x sub i sup 2 ~ .
}
}
right \]](/resources/images/78f9cdba83a83f1156d66ffbc7cc00a9c0772af8.svg)
Напомним, что 
, поэтому можем рассматривать матрицу с вынесенной двойкой: умножение матрицы на положительное число не изменит знака её угловых миноров.
Значение первого углового минора (число наблюдений) будет положительным всегда.
Неотрицательность второго углового минора матрицы вторых частных производных функции следует из неравенство о средних (также называемого неравенством Коши, не путайте с неравенством Коши-Буняковского).
Последнее выражение выполняется как равенство, когда значения, для которых вычисляются средние, равны между собой (попробуйте доказать это самостоятельно). Этот случай не представляет интереса для задач обработки данных методом наименьших квадратов. Можем заключить: второй угловой минор матрицы вторых частных производных функции также положителен.
Матрица вторых частных производных, таким образом, по критерию Сильвестра явлется положительно определённой, что даёт нам основания утверждать, что полученное решение — точка минимума функции .
Множественный случай
Общая постановка задачи
Расширим наш эксперимент: по-прежнему было проведено измерений, но замерялся не один вход, а 
различных входов (выход по-прежнему один).
Результаты эксперимента могут быть компактно записаны с помощью матриц. Входы будут находиться в матрице 
, а выходы — в векторе-столбце 
.
![X =
left \[
matrix {
ccol {x sub 11 above x sub 21 above vdots above x sub i1 above vdots above x sub n1}
ccol {x sub 12 above x sub 22 above vdots above x sub i2 above vdots above x sub n2}
ccol {cdots above cdots above ddots above cdots above ddots above cdots}
ccol {x sub 1j above x sub 2j above vdots above x sub ij above vdots above x sub nj}
ccol {cdots above cdots above ddots above cdots above ddots above cdots}
ccol {x sub 1m above x sub 2m above vdots above x sub im above vdots above x sub nm}
}
right \]
~ , ~
bold y =
left \[
pile {y sub 1 above y sub 2 above vdots above y sub i above vdots above y sub n}
right \]
~ .](/resources/images/764907899f4d7f9d728f74c19832bc48c0a824b5.svg)
По строкам матрицы расположены результаты измерений, по столбцам — значения входов. Например, 
— значение 4-го входа в 3-ем измерении.
Мы по-прежнему хотим «подогнать» наши экспериментальные данные к линейной функции, но, в отличие от предыдущего случая это будет не прямая, а -мерная плоскость (для 
это будет обычная плоскость, для 
— гиперплоскость). Вектор значений линейной функции назовём вектором оценкок и обозначим 
где 
— вектор-столбец коэффициентов линейной функции.
Проиллюстрируем случай следующим примером. Представьте, что в комнате в разных местах на разной высоте висят воздушные шарики. Вы хотите растянуть в этой комнате несгибаемое полотно (из ткани, бумаги, картона) так, чтобы это полотно находилось ближе всего к шарикам. Высота шарика относительно пола будет являться выходом , координаты проекции шарика на пол — входами 
, расстояние от проекции шарика на пол до полотна — оценкой 
, расстояние от шарика до полотна по линии проекции шарика на пол — отклонением 
.
Если мы предполагаем, что в нашей линейной функции имеется свободный член, то значения крайнего левого столбца матрицы будут состоять только из единиц. Соответственно, и будет значением свободного члена.
Разницу между реальным значением и оценкой будем по-прежнему называть отклонением и обозначим 
Сумма квадратов отклонений может быть получена как 
Нам необходимо, найти такой вектор , чтобы сумма квадратов отклонений была минимальна:
Математическая формализация
Вспоминим некоторые базовые свойства операции транспонирования матриц, чтобы корректно раскрыть скобки и провести дифференцирование. Нам потребуются два следующих свойства:
Заметим два нетривиальных факта, в большинстве пособий, учебников и статей по МНК опускаемые как самоочевидные и простые (действительно, зачем объяснять, люди же могут начать понимать и задавать вопросы):
- Второе и третье слагаемое — это один и тот же математический объект с точностью до операции транспонирования:
Мы воспользовались вторым из указанных свойств операции транспонирования матриц для подтверждения этого факта. - Оба этих математических объекта (второе и третье слагаемое) являются скалярами (любой скаляр же по определению — это матрица размерности
). Это нетрудно проверить просто по размерностям векторов и матриц, включаемых в оба этих объекта.
Исходя из этих двух фактов можно смело утверждать, что 
что позволяет упростить выражение 
Как и в случае с парным случаем, мы воспользуемся аппаратом дифференциального исчисления, взяв производную по вектору и приравняв её к нулю:
Покажем, что условие первого порядке даёт нам минимум функции. Для этого докажем, что матрица вторых производных будет положительно определена:
Напомним ещё один факт из линейной алгебры. Если некоторая матрица 
положительно определена, то это в том числе означает, что для любого ненулевого вектора 
подходящей размерности будет выполнятся следующее:
Пусть наша матрица разложима в виде 
тогда она будет положительно определена:
Произведение 
— сумма квадратов значений вектора 
, которая будет неотрицательна всегда, а равно нулю, только если матрица 
— нулевая матрица.
Вернёмся к нашему примеру: 
— умножение на скаляр не изменит определённости матрицы, а в силу рассуждений, приведённых выше, мы можем смело утверждать, что матрица вторых производных положительно определена, значит, найденное нами решение — точка минимума функции 
Список литературы
- Марков, А. А. Исчисление вероятностей, изд. 4 / Андрей Андреевич Марков. — ГИЗ, 1924.
- Марков, А. А. Закон больших чисел и метод наименьших квадратов (1898) Избр. труды / Андрей Андреевич Марков. — Изд. АН СССР, 1951. — C. 233—251.
- Линник, Ю. В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений / Юрий Владимирович Линник. — М. : ФизМатГИЗ, 1962. — C. 10—16. — http://books.e-herit....
- Доугерти, К. Введение в эконометрику / Кристофер Доугерти. — М. : Инфра-М, 1999. — C. 53—58.
- Angrist, J. D. Mostly Harmless Econometrics: An Empiricist's Companion / Joshua D. Angrist, Jörn-Steffen Pischke. — Princeton University Press, 2009. — pp. 21—38. — http://egei.vse.cz/e....
Примечания
¹) В случае, если МНК используется для обработки социально-экономических данных, вместо «измерение» говорят «наблюдение», вместо «опыт» — «статистическое наблюдение».
КатегорияПрикладнаяМатематика | КатегорияМетодНаименьшихКвадратов