Наименьших квадратов - Least squares

Результат подгонки набора точек данных квадратичной функцией
Коническая подгонка набора точек с использованием аппроксимации наименьших квадратов

Метод наименьших квадратов является стандартным подходом в регрессионном анализе для аппроксимации решения переопределенных систем (систем уравнений, в которых уравнений больше, чем неизвестных) путем минимизации суммы квадратов остатков, полученных в результате каждого отдельного уравнения. .

Самое важное приложение - подгонка данных . Наилучшее соответствие в смысле наименьших квадратов минимизирует сумму квадратов остатков (остаток - это разница между наблюдаемым значением и подобранным значением, предоставленным моделью). Когда проблема имеет существенные неопределенности в независимой переменной ( переменной x ), тогда возникают проблемы с простыми методами регрессии и наименьших квадратов; в таких случаях вместо метода наименьших квадратов можно использовать методологию, необходимую для подбора моделей ошибок в переменных .

Задачи наименьших квадратов делятся на две категории: линейные или обычные наименьшие квадраты и нелинейные наименьшие квадраты , в зависимости от того, являются ли остатки линейными по всем неизвестным. Проблема линейных наименьших квадратов возникает в статистическом регрессионном анализе ; это решение в закрытой форме . Нелинейная задача обычно решается итеративным уточнением; на каждой итерации система аппроксимируется линейной, поэтому расчет керна в обоих случаях одинаков.

Полиномиальный метод наименьших квадратов описывает дисперсию прогноза зависимой переменной как функцию независимой переменной и отклонения от подобранной кривой.

Когда наблюдения происходят из экспоненциального семейства с идентичностью в качестве естественной достаточной статистики и выполняются мягкие условия (например, для нормального, экспоненциального, пуассоновского и биномиального распределений), стандартизованные оценки методом наименьших квадратов и оценки максимального правдоподобия идентичны. Метод наименьших квадратов можно также вывести как метод оценки моментов .

Следующее обсуждение в основном представлено в терминах линейных функций, но использование наименьших квадратов действительно и практично для более общих семейств функций. Кроме того, путем итеративного применения локальной квадратичной аппроксимации вероятности (через информацию Фишера ) метод наименьших квадратов может использоваться для соответствия обобщенной линейной модели .

Метод наименьших квадратов был официально открыт и опубликован Адрианом-Мари Лежандром (1805 г.), хотя обычно его приписывают Карлу Фридриху Гауссу (1795 г.), который внес значительный теоретический прогресс в этот метод и, возможно, ранее использовал его в своей работе. Работа.

История

Основание

Метод наименьших квадратов вырос из области астрономии и геодезии , поскольку ученые и математики стремились найти решения проблем навигации по океанам Земли в эпоху исследований . Точное описание поведения небесных тел было ключом к тому, чтобы корабли могли плавать в открытом море, где моряки больше не могли полагаться на наземные наблюдения для навигации.

Этот метод стал кульминацией нескольких достижений, имевших место в течение восемнадцатого века:

  • Комбинация различных наблюдений как лучшая оценка истинного значения; ошибки уменьшаются с агрегированием, а не увеличиваются, возможно, впервые высказанное Роджером Котсом в 1722 году.
  • Комбинация различных наблюдений, сделанных в одних и тех же условиях, в отличие от простого стремления изо всех сил наблюдать и точно записывать одно наблюдение. Этот подход был известен как метод средних значений. Этот подход, в частности, использовался Тобиасом Майером при изучении либраций Луны в 1750 году и Пьером-Симоном Лапласом в его работе по объяснению различий в движении Юпитера и Сатурна в 1788 году.
  • Комбинация разных наблюдений, сделанных в разных условиях. Этот метод стал известен как метод наименьшего абсолютного отклонения. В частности, это было выполнено Роджером Йозефом Босковичем в его работе о форме Земли в 1757 году и Пьером-Симоном Лапласом для той же задачи в 1799 году.
  • Разработка критерия, который может быть оценен, чтобы определить, когда было достигнуто решение с минимальной ошибкой. Лаплас попытался определить математическую форму плотности вероятности ошибок и определить метод оценки, который минимизирует ошибку оценки. Для этой цели Лаплас использовал симметричное двустороннее экспоненциальное распределение, которое мы теперь называем распределением Лапласа для моделирования распределения ошибок, и использовал сумму абсолютных отклонений как ошибку оценки. Он чувствовал, что это самые простые предположения, которые он мог сделать, и надеялся получить среднее арифметическое как наилучшую оценку. Вместо этого его оценкой была апостериорная медиана.

Метод

Первое четкое и краткое изложение метода наименьших квадратов было опубликовано Лежандром в 1805 году. Этот метод описывается как алгебраическая процедура для подгонки линейных уравнений к данным, и Лежандр демонстрирует новый метод, анализируя те же данные, что и Лаплас, для определения формы Земля. В течение десяти лет после публикации Лежандра метод наименьших квадратов был принят в качестве стандартного инструмента в астрономии и геодезии во Франции, Италии и Пруссии, что представляет собой чрезвычайно быстрое признание научной техники.

В 1809 году Карл Фридрих Гаусс опубликовал свой метод расчета орбит небесных тел. В этой работе он утверждал, что владеет методом наименьших квадратов с 1795 года. Это, естественно, привело к спору о приоритете с Лежандром. Однако, к чести Гаусса, он пошел дальше Лежандра и сумел связать метод наименьших квадратов с принципами вероятности и нормального распределения . Ему удалось завершить программу Лапласа по определению математической формы плотности вероятности для наблюдений, зависящей от конечного числа неизвестных параметров, и определить метод оценки, который минимизирует ошибку оценки. Гаусс показал, что среднее арифметическое действительно является наилучшей оценкой параметра местоположения путем изменения как плотности вероятности, так и метода оценки. Затем он решил проблему, задав вопрос, какую форму должна иметь плотность и какой метод оценки следует использовать, чтобы получить среднее арифметическое значение в качестве оценки параметра местоположения. В этой попытке он изобрел нормальное распределение.

Ранняя демонстрация силы метода Гаусса произошла, когда он использовался для предсказания будущего местоположения недавно открытого астероида Церера . 1 января 1801 года итальянский астроном Джузеппе Пиацци открыл Цереру и смог проследить ее путь в течение 40 дней, прежде чем она затерялась в ярком солнечном свете. Основываясь на этих данных, астрономы хотели определить местоположение Цереры после того, как она появилась из-за Солнца, не решая сложных нелинейных уравнений движения планет Кеплера. Единственные предсказания, которые позволили венгерскому астроному Францу Ксаверу фон Заку переместить Цереру, были предсказаны 24-летним Гауссом с использованием анализа наименьших квадратов.

В 1810 году, после прочтения работы Гаусса, Лаплас, после доказательства центральной предельной теоремы , использовал ее для обоснования большой выборки метода наименьших квадратов и нормального распределения. В 1822 году Гаусс смог заявить, что подход наименьших квадратов к регрессионному анализу является оптимальным в том смысле, что в линейной модели, где ошибки имеют нулевое среднее значение, некоррелированы и имеют равные дисперсии, лучшая линейная несмещенная оценка коэффициенты - это оценка методом наименьших квадратов. Этот результат известен как теорема Гаусса – Маркова .

Идея анализа методом наименьших квадратов была также независимо сформулирована американцем Робертом Адрейном в 1808 году. В следующие два столетия исследователи теории ошибок и статистики нашли множество различных способов применения метода наименьших квадратов.

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

Цель состоит в настройке параметров модельной функции для наилучшего соответствия набору данных. Простой набор данных состоит из n точек (пар данных) , i = 1,…, n , где - независимая переменная, а - зависимая переменная , значение которой определяется путем наблюдения. Модельная функция имеет вид , где в векторе хранятся m настраиваемых параметров . Цель состоит в том, чтобы найти значения параметров для модели, которые "наилучшим образом" соответствуют данным. Подгонка модели к точке данных измеряется ее невязкой , определяемой как разница между наблюдаемым значением зависимой переменной и значением, предсказанным моделью:

Остатки нанесены на соответствующие значения. Случайные колебания около указывают на то, что линейная модель подходит.

Метод наименьших квадратов находит оптимальные значения параметров путем минимизации суммы квадратов остатков , :

Примером модели в двух измерениях является прямая линия. Обозначив точку пересечения по оси Y как и наклон как , модельная функция будет иметь вид . См. Линейный метод наименьших квадратов для получения полностью разработанного примера этой модели.

Точка данных может состоять из нескольких независимых переменных. Например, при подгонке плоскости к набору измерений высоты плоскость является функцией двух независимых переменных , скажем , x и z . В наиболее общем случае в каждой точке данных может быть одна или несколько независимых переменных и одна или несколько зависимых переменных.

Справа - остаточный график, иллюстрирующий случайные колебания , указывающий на то, что линейная модель подходит. является независимой случайной величиной.  

Остатки нанесены на график против соответствующих значений. Параболическая форма колебаний около указывает на то, что параболическая модель подходит.

Если бы остаточные точки имели какую-то форму и не колебались случайным образом, линейная модель не была бы подходящей. Например, если остаточный график имеет параболическую форму, если смотреть справа, параболическая модель будет подходящей для данных. Остатки для параболической модели могут быть рассчитаны с помощью .

Ограничения

Эта формулировка регрессии учитывает только ошибки наблюдений в зависимой переменной (но альтернативная регрессия методом наименьших квадратов может учитывать ошибки в обеих переменных). Есть два довольно разных контекста с разными значениями:

  • Регрессия для предсказания. Здесь модель подбирается для обеспечения правила прогнозирования для применения в аналогичной ситуации, к которой применяются данные, используемые для подгонки. Здесь зависимые переменные, соответствующие такому будущему применению, будут подвержены тем же типам ошибок наблюдения, что и в данных, используемых для подгонки. Следовательно, для таких данных логически целесообразно использовать правило прогнозирования методом наименьших квадратов.
  • Регрессия для подбора «истинных отношений». В стандартном регрессионном анализе, который приводит к аппроксимации методом наименьших квадратов, неявно предполагается, что ошибки в независимой переменной равны нулю или строго контролируются, чтобы ими можно было пренебречь. Когда ошибками в независимой переменной нельзя пренебречь, можно использовать модели ошибки измерения ; такие методы могут привести к оценкам параметров , проверке гипотез и доверительным интервалам, которые учитывают наличие ошибок наблюдения в независимых переменных. Альтернативный подход заключается в подборе модели методом наименьших квадратов ; это можно рассматривать как прагматический подход к уравновешиванию эффектов различных источников ошибок при формулировании целевой функции для использования при подгонке модели.

Решение задачи наименьших квадратов

Минимальный из суммы квадратов определяются путем установки градиента к нулю. Поскольку модель содержит m параметров, существует m градиентных уравнений:

и поскольку градиентные уравнения принимают вид

Уравнения градиента применимы ко всем задачам наименьших квадратов. Каждая конкретная проблема требует определенных выражений для модели и ее частных производных.

Линейный метод наименьших квадратов

Регрессионная модель является линейной, когда модель содержит линейную комбинацию параметров, т. Е.

где функция является функцией от .

Допуская и помещая независимые и зависимые переменные в матрицы и , соответственно, мы можем вычислить наименьшие квадраты следующим образом. Обратите внимание, что это набор всех данных.

Нахождение минимума может быть достигнуто путем установки градиента потерь на ноль и решения для

Наконец, установив градиент потерь на ноль и решив для, мы получим:

Нелинейный метод наименьших квадратов

В некоторых случаях существует решение в замкнутой форме нелинейной задачи наименьших квадратов, но в общем случае его нет. В случае отсутствия решения в закрытой форме используются численные алгоритмы для нахождения значения параметров, которое минимизирует цель. Большинство алгоритмов включают выбор начальных значений параметров. Затем параметры уточняются итеративно, то есть значения получаются методом последовательного приближения:

где верхний индекс k - номер итерации, а вектор приращений называется вектором сдвига. В некоторых обычно используемых алгоритмах на каждой итерации модель может быть линеаризована путем приближения к разложению в ряд Тейлора первого порядка примерно :

Якобиан J является функцией констант, независимой переменной и параметрами, поэтому он изменяется от одной итерации к следующей. Остатки даются как

Чтобы минимизировать сумму квадратов , уравнение градиента устанавливается равным нулю и решается для :

которые при перестановке превращаются в m одновременных линейных уравнений, нормальных уравнений :

Нормальные уравнения записываются в матричных обозначениях как

Это определяющие уравнения алгоритма Гаусса – Ньютона .

Различия между линейным и нелинейным методом наименьших квадратов

  • Модельная функция f в LLSQ (линейный метод наименьших квадратов) представляет собой линейную комбинацию параметров формы . Модель может представлять прямую линию, параболу или любую другую линейную комбинацию функций. В NLLSQ (нелинейный метод наименьших квадратов) параметры отображаются как функции, например, и так далее. Если производные либо постоянны, либо зависят только от значений независимой переменной, модель линейна по параметрам. В противном случае модель будет нелинейной.
  • Требуются начальные значения для параметров, чтобы найти решение проблемы NLLSQ; LLSQ не требует их.
  • Алгоритмы решения для NLLSQ часто требуют, чтобы якобиан мог быть вычислен аналогично LLSQ. Аналитические выражения для частных производных могут быть сложными. Если невозможно получить аналитические выражения, либо частные производные должны быть вычислены с помощью численного приближения, либо должна быть сделана оценка якобиана, часто с помощью конечных разностей .
  • Несходимость (неспособность алгоритма найти минимум) - обычное явление в NLLSQ.
  • LLSQ является глобально вогнутым, поэтому несходимость не является проблемой.
  • Решение NLLSQ обычно является итеративным процессом, который должен быть прекращен, когда выполняется критерий сходимости. Решения LLSQ могут быть вычислены с использованием прямых методов, хотя проблемы с большим количеством параметров обычно решаются итерационными методами, такими как метод Гаусса – Зейделя .
  • В LLSQ решение уникально, но в NLLSQ может быть несколько минимумов в сумме квадратов.
  • При условии, что ошибки не коррелируют с переменными-предикторами, LLSQ дает несмещенные оценки, но даже при этом условии оценки NLLSQ обычно смещены.

Эти различия необходимо учитывать всякий раз, когда ищется решение нелинейной задачи наименьших квадратов.

Пример

Рассмотрим простой пример из физики. Пружина должна подчиняться закону Гука, который гласит, что растяжение пружины y пропорционально приложенной к ней силе F.

составляет модель, где F - независимая переменная. Для того , чтобы оценить постоянную силу , K , мы проводим серию п измерений с различными силами , чтобы произвести набор данных, где у я есть измеренное расширение пружины. Каждое экспериментальное наблюдение будет содержать некоторую ошибку, и поэтому мы можем указать эмпирическую модель для наших наблюдений,

Есть много методов, которые мы можем использовать для оценки неизвестного параметра k . Поскольку n уравнений от m переменных в наших данных представляют собой переопределенную систему с одним неизвестным и n уравнениями, мы оцениваем k, используя метод наименьших квадратов. Минимизируемая сумма квадратов равна

Оценка силовой постоянной k методом наименьших квадратов дается выражением

Мы предполагаем, что приложение силы заставляет пружину расширяться. После получения силовой постоянной с помощью аппроксимации методом наименьших квадратов мы прогнозируем расширение по закону Гука.

Количественная оценка неопределенности

При вычислении методом наименьших квадратов с единичными весами или в линейной регрессии дисперсия j- го параметра, обозначенного , обычно оценивается с помощью

где истинная дисперсия ошибки σ 2 заменяется оценкой, с уменьшенной хи-квадрат статистики , на основе свернутого значения остаточной суммы квадратов (целевой функции), S . Знаменатель n  -  m представляет собой статистические степени свободы ; см. эффективные степени свободы для обобщений. C - ковариационная матрица .

Статистическое тестирование

Если распределение вероятностей параметров известно или выполнено асимптотическое приближение, можно найти доверительные интервалы . Аналогичным образом, статистические тесты остатков могут проводиться, если распределение вероятностей остатков известно или предполагается. Мы можем получить распределение вероятностей любой линейной комбинации зависимых переменных, если распределение вероятностей экспериментальных ошибок известно или предполагается. Сделать вывод легко, если предположить, что ошибки следуют нормальному распределению, следовательно, подразумевая, что оценки параметров и остатки также будут нормально распределены в зависимости от значений независимых переменных.

Для статистической проверки результатов необходимо сделать предположения о природе экспериментальных ошибок. Распространенным предположением является то, что ошибки принадлежат нормальному распределению. Центральная предельная теорема поддерживает идею о том , что это хорошее приближение во многих случаях.

  • Теорема Гаусса – Маркова . В линейной модели, в которой ошибки имеют нулевое математическое ожидание, обусловленное независимыми переменными, некоррелированы и имеют равные дисперсии , наилучшей линейной несмещенной оценкой любой линейной комбинации наблюдений является ее оценка по методу наименьших квадратов. «Наилучшее» означает, что оценки параметров методом наименьших квадратов имеют минимальную дисперсию. Предположение о равной дисперсии действительно, когда все ошибки принадлежат одному и тому же распределению.
  • Если ошибки принадлежат нормальному распределению, оценки наименьших квадратов также являются оценками максимального правдоподобия в линейной модели.

Однако предположим, что ошибки не имеют нормального распределения. В этом случае центральная предельная теорема часто, тем не менее, часто подразумевает, что оценки параметров будут приблизительно нормально распределены, если выборка достаточно велика. По этой причине, учитывая важное свойство, заключающееся в том, что среднее значение ошибки не зависит от независимых переменных, распределение члена ошибки не является важным вопросом в регрессионном анализе. В частности, обычно не важно, следует ли член ошибки нормальному распределению.

Взвешенный метод наименьших квадратов

Эффект "разветвления" гетероскедастичности

Частный случай обобщенных наименьших квадратов, называемый взвешенными наименьшими квадратами, возникает, когда все недиагональные элементы Ω (корреляционная матрица остатков) равны нулю; отклонениях наблюдений (по ковариационная матрица по диагонали) по- прежнему может быть неодинаковой ( гетероскедастичность ). Проще говоря, гетероскедастичность - это когда дисперсия зависит от значения, которое заставляет остаточный график создавать эффект «разветвления» в сторону больших значений, как видно на остаточном графике справа. С другой стороны, гомоскедастичность предполагает, что дисперсия и равна.   

Отношение к основным компонентам

Первый главный компонент о среднем значении набора точек может быть представлен той линией, которая наиболее близко приближается к точкам данных (измеряется квадратом расстояния наибольшего сближения, т. Е. Перпендикулярно линии). Напротив, линейный метод наименьших квадратов пытается минимизировать расстояние только в направлении. Таким образом, хотя оба используют схожую метрику ошибок, линейный метод наименьших квадратов - это метод, который предпочтительно обрабатывает одно измерение данных, в то время как PCA обрабатывает все измерения одинаково.

Отношение к теории измерения

Известный статистик Сара ван де Гир использовала теорию эмпирических процессов и размерность Вапника-Червоненкиса, чтобы доказать, что оценка методом наименьших квадратов может быть интерпретирована как мера на пространстве функций, интегрируемых с квадратом .

Регуляризация

Тихоновская регуляризация

В некоторых контекстах может быть предпочтительнее регуляризованная версия решения методом наименьших квадратов. Регуляризация Тихонова (или регрессия гребня ) добавляет ограничение, которое , L 2 -норма вектора параметров, не превышает заданного значения. Эквивалентно, он может решить неограниченную минимизацию штрафа методом наименьших квадратов с добавленным, где - константа (это лагранжева форма задачи с ограничениями). В байесовском контексте это эквивалентно помещению в вектор параметров априорного значения с нормальным распределением с нулевым средним .

Метод лассо

Альтернатива регуляризованное версия наименьших квадратов Лассо ( не менее абсолютное сжатие и выбор оператора), который использует ограничение , что , то L 1 -норма вектора параметров, не больше , чем заданное значение. (Как и выше, это эквивалентно неограниченной минимизации штрафа по методу наименьших квадратов с добавлением.) В байесовском контексте это эквивалентно помещению априорного распределения Лапласа с нулевым средним на вектор параметров. Проблема оптимизации может быть решена с использованием квадратичного программирования или более общих методов выпуклой оптимизации , а также с помощью конкретных алгоритмов, таких как алгоритм регрессии по наименьшему углу .

Одно из основных различий между лассо и регрессией гребня состоит в том, что при гребневой регрессии по мере увеличения штрафа все параметры уменьшаются, но при этом остаются ненулевыми, в то время как в лассо увеличение штрафа приводит к тому, что все больше и больше параметров будут изменяться. загнал в ноль. Это преимущество лассо перед регрессией гребня, так как приведение параметров к нулю отменяет выбор объектов из регрессии. Таким образом, Lasso автоматически выбирает более релевантные функции и отбрасывает другие, тогда как регрессия Ridge никогда полностью не отбрасывает какие-либо функции. Некоторые методы выбора характеристик разработаны на основе LASSO, в том числе Bolasso, который загружает образцы, и FeaLect, который анализирует коэффициенты регрессии, соответствующие различным значениям, для оценки всех функций.

L 1 -регуляризованная формулировка полезна в некоторых контекстах из-за ее тенденции отдавать предпочтение решениям, в которых большее количество параметров равно нулю, что дает решения, которые зависят от меньшего числа переменных. По этой причине лассо и его варианты являются фундаментальными для области восприятия сжатых данных . Расширением этого подхода является эластичная сетевая регуляризация .

Смотрите также

использованная литература

дальнейшее чтение

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