Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




27.01.2021


27.01.2021


27.01.2021


27.01.2021


27.01.2021





Яндекс.Метрика





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

08.03.2021

В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.

Аппроксимация данных методом наименьших полных квадратов в общем виде эквивалентна лучшей по норме Фробениуса малоранговой аппрокимации матрицы данных.

Линейная модель

Основы

В методе наименьших квадратов моделирования данных минимизируется функция потерь S,

S = r T W r , {displaystyle S=mathbf {r^{T}Wr} ,}

где r — вектор отклонений, а W — весовая матрица. В линейном методе наименьших квадратов модель содержит уравнения, которые линейны от параметров в векторе β {displaystyle {oldsymbol {eta }}} , так что отклонения вычисляются по формуле

r = y − X β . {displaystyle mathbf {r=y-X{oldsymbol {eta }}} .}

Имеется m наблюдений в векторе y и n параметров в β при m>n. X является m×n матрицей, элементы которой либо константы, либо функции от независимых переменных x. Весовая матрица W, в идеале, является обратной к дисперсионно-ковариационной матрице M y {displaystyle mathbf {M} _{y}} наблюдений y. Предполагается, что независимые переменные ошибок не имеют. Параметры оценки находятся путём приравнивания градиента нулю, что приводит к уравнению

X T W X β = X T W y {displaystyle mathbf {X^{T}WX{oldsymbol {eta }}=X^{T}Wy} }

Возможность ошибок наблюдений для всех переменных

Предположим теперь, что как x, так и y наблюдаются с ошибками с дисперсионно-ковариационными матрицами M x {displaystyle mathbf {M} _{x}} и M y {displaystyle mathbf {M} _{y}} соответственно. В этом случае функция потерь записывается как

S = r x T M x − 1 r x + r y T M y − 1 r y {displaystyle S=mathbf {r_{x}^{T}M_{x}^{-1}r_{x}+r_{y}^{T}M_{y}^{-1}r_{y}} } ,

где r x {displaystyle mathbf {r} _{x}} и r y {displaystyle mathbf {r} _{y}} являются отклонениями для x и y соответственно. Ясно, что эти отклонения не могут быть независимыми и между ними должна быть какая-то связь. Если записать функцию как f ( r x , r y , β ) {displaystyle mathbf {f(r_{x},r_{y},{oldsymbol {eta }})} } , ограничения выражаются m условиями.

F = Δ y − ∂ f ∂ r x r x − ∂ f ∂ r y r y − X Δ β = 0 {displaystyle mathbf {F=Delta y-{frac {partial f}{partial r_{x}}}r_{x}-{frac {partial f}{partial r_{y}}}r_{y}-XDelta {oldsymbol {eta }}=0} }

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

X T M − 1 X Δ β = X T M − 1 Δ y , {displaystyle mathbf {X^{T}M^{-1}XDelta {oldsymbol {eta }}=X^{T}M^{-1}Delta y} ,}

или, альтернативно, X T M − 1 X β = X T M − 1 y {displaystyle mathbf {X^{T}M^{-1}X{oldsymbol {eta }}=X^{T}M^{-1}y} }

Здесь M — дисперсионно-ковариационная матрица, относящаяся как к независимым, так и зависимым переменным.

M = K x M x K x T + K y M y K y T ;   K x = − ∂ f ∂ r x ,   K y = − ∂ f ∂ r y {displaystyle mathbf {M=K_{x}M_{x}K_{x}^{T}+K_{y}M_{y}K_{y}^{T}; K_{x}=-{frac {partial f}{partial r_{x}}}, K_{y}=-{frac {partial f}{partial r_{y}}}} }

Пример

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

f ( x i , β ) = α + β x i {displaystyle f(x_{i},eta )=alpha +eta x_{i}!}

И в этом случае

M i i = σ y , i 2 + β 2 σ x , i 2 {displaystyle M_{ii}=sigma _{y,i}^{2}+eta ^{2}sigma _{x,i}^{2}}

что показывает, как дисперсия в i-ой точке определяется дисперсией независимых и зависимых переменных, а также моделью, используемой для согласования данных. Выражение можно обобщить, если заметить, что параметр β {displaystyle eta } является наклоном прямой.

M i i = σ y , i 2 + ( d y d x ) i 2 σ x , i 2 {displaystyle M_{ii}=sigma _{y,i}^{2}+left({frac {dy}{dx}} ight)_{i}^{2}sigma _{x,i}^{2}}

Выражение такого вида используется для аппроксимации данные титрования pH, когда малые ошибки в x дают большие ошибки y в случае большого наклона.

С алгебраической точки зрения

Прежде всего следует заметить, что задача МНПК в общем случае решения не имеет, что было показано ещё в 1980. Рассмотрим простой случай, где единственное решение существует без каких-либо предположений.

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

X B ≈ Y {displaystyle XBapprox Y}

относительно B, где X — матрица m-на-n, а Y — матрица m-на-k

То есть мы пытаемся найти матрицу B, минимизирующую матрицы ошибок R и F для X и Y соответственно. То есть

a r g m i n R , F ‖ [ R F ] ‖ F , ( X + R ) B = Y + F {displaystyle mathrm {argmin} _{R,F}|[R;F]|_{F},qquad (X+R)B=Y+F} ,

где [ R F ] {displaystyle [R;F]} — расширенная матрица с R и F рядом и ‖ ⋅ ‖ F {displaystyle |cdot |_{F}} является нормой матрицы, квадратным корнем из суммы квадратов всех элементов матриц, что эквивалентно квадратному корню из суммы квадратов длин строк или столбцов матрицы.

Это можно переписать как

[ ( X + R ) ( Y + F ) ] [ B − E k ] = 0. {displaystyle [(X+R);(Y+F)]{egin{bmatrix}B-E_{k}end{bmatrix}}=0.}

Где E k {displaystyle E_{k}} является k × k {displaystyle k imes k} единичной матрицей. Целью является нахождение матрицы [ R F ] {displaystyle [R;F]} , которая уменьшает ранг [ X Y ] {displaystyle [X;Y]} на k. Определим [ U ] [ Σ ] [ V ] ∗ {displaystyle [U][Sigma ][V]*} как сингулярное разложение расширенной матрицы [ X Y ] {displaystyle [X;Y]} .

[ X Y ] = [ U X U Y ] [ Σ X 0 0 Σ Y ] [ V X X V X Y V Y X V Y Y ] ∗ = [ U X U Y ] [ Σ X 0 0 Σ Y ] [ V X X ∗ V Y X ∗ V X Y ∗ V Y Y ∗ ] {displaystyle [X;Y]=[U_{X};U_{Y}]{egin{bmatrix}Sigma _{X}&0&Sigma _{Y}end{bmatrix}}{egin{bmatrix}V_{XX}&V_{XY}V_{YX}&V_{YY}end{bmatrix}}^{*}=[U_{X};U_{Y}]{egin{bmatrix}Sigma _{X}&0&Sigma _{Y}end{bmatrix}}{egin{bmatrix}V_{XX}^{*}&V_{YX}^{*}V_{XY}^{*}&V_{YY}^{*}end{bmatrix}}} ,

где V разбита на блоки, соответствующие формам матриц X и Y.

Если использовать теорему Экарта-Янга, аппроксимация, минимизирующая норму ошибки, это такая аппроксимация, что матрицы U {displaystyle U} и V {displaystyle V} не меняются, в то время как k {displaystyle k} наименьших сингулярных значений заменяются нулями. То есть мы хотим

[ ( X + R ) ( Y + F ) ] = [ U X U Y ] [ Σ X 0 0 0 k × k ] [ V X X V X Y V Y X V Y Y ] ∗ {displaystyle [(X+R);(Y+F)]=[U_{X};U_{Y}]{egin{bmatrix}Sigma _{X}&0&0_{k imes k}end{bmatrix}}{egin{bmatrix}V_{XX}&V_{XY}V_{YX}&V_{YY}end{bmatrix}}^{*}}

так что, ввиду линейности,

[ R F ] = − [ U X U Y ] [ 0 n × n 0 0 Σ Y ] [ V X X V X Y V Y X V Y Y ] ∗ . {displaystyle [R;F]=-[U_{X};U_{Y}]{egin{bmatrix}0_{n imes n}&0&Sigma _{Y}end{bmatrix}}{egin{bmatrix}V_{XX}&V_{XY}V_{YX}&V_{YY}end{bmatrix}}^{*}.}

Мы можем удалить блоки из матриц U и Σ, упростив выражение до

[ R F ] = − U Y Σ Y [ V X Y V Y Y ] ∗ = − [ X Y ] [ V X Y V Y Y ] [ V X Y V Y Y ] ∗ . {displaystyle [R;F]=-U_{Y}Sigma _{Y}{egin{bmatrix}V_{XY}V_{YY}end{bmatrix}}^{*}=-[X;Y]{egin{bmatrix}V_{XY}V_{YY}end{bmatrix}}{egin{bmatrix}V_{XY}V_{YY}end{bmatrix}}^{*}.}

Это даёт R и F, таки что

[ ( X + R ) ( Y + F ) ] [ V X Y V Y Y ] = 0. {displaystyle [(X+R);(Y+F)]{egin{bmatrix}V_{XY}V_{YY}end{bmatrix}}=0.}

Теперь, если V Y Y {displaystyle V_{YY}} не вырождена, что не всегда верно (заметим, что поведение МНПК в случае вырожденности V Y Y {displaystyle V_{YY}} не вполне понятно), мы можем умножить справа обе части на − V Y Y − 1 {displaystyle -V_{YY}^{-1}} , чтобы привести нижний блок правой матрицы к отрицательной единичной матрице, что даёт

[ ( X + R ) ( Y + F ) ] [ − V X Y V Y Y − 1 − V Y Y V Y Y − 1 ] = [ ( X + R ) ( Y + F ) ] [ B − E k ] = 0 , {displaystyle [(X+R);(Y+F)]{egin{bmatrix}-V_{XY}V_{YY}^{-1}-V_{YY}V_{YY}^{-1}end{bmatrix}}=[(X+R);(Y+F)]{egin{bmatrix}B-E_{k}end{bmatrix}}=0,}

а тогда

B = − V X Y V Y Y − 1 . {displaystyle B=-V_{XY}V_{YY}^{-1}.}

Имплементация в системе GNU Octave:

function B = tls(X,Y) [m n] = size(X); % n является шириной матрицы X (X[m x n]) Z = [X Y]; % Z является расширением X на Y. [U S V] = svd(Z,0); % находим [[Сингулярное разложение|SVD]] матрицы Z. VXY = V(1:n,1+n:end); % Берём блок матрицы V, состоящий из первых n строк и n+1 последних столбцов VYY = V(1+n:end,1+n:end); % Берём нижний правы блок матрицы V. B = -VXY/VYY; end

Метод решения задачи, описанный выше и требующий, чтобы матрица V Y Y {displaystyle V_{YY}} не была вырожденной, может быть слегка расширен так называемым классическим МНПК алгоритмом.

Вычисление

Стандартная имплементация классического алгоритма МНПК доступна на Netlib, см. также статьи. Все современные имплементации, базирующиеся, например, на использовании обычного метода наименьших квадратов, аппроксимируют матрицу B {displaystyle B} (которая в литературе обозначается как X {displaystyle X} ), как это делают Ван Хуффель и Вандевалле. Стоит заметить, однако, что полученная матрица B {displaystyle B} во многих случаях не является решением МНПК.

Нелинейная модель

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

J T M − 1 J Δ β = J T M − 1 Δ y . {displaystyle mathbf {J^{T}M^{-1}JDelta {oldsymbol {eta }}=J^{T}M^{-1}Delta y} .}

Геометрическая интерпретация

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

Масштабно-инвариантные методы

Серьёзная трудность появляется, если переменные не измеряются в тех же самых единицах. Сначала рассмотрим измерение расстояния между точками данных и кривой — какова будет единица измерения для расстояния? Если мы будем измерять расстояние на основе теоремы Пифагора, ясно, что нам придётся складывать единицы, измеряемые в различных единицах, что приводит к бессмысленным результатам. Если мы заменим масштаб одной из переменных, например, будем измерять в граммах, а не килограммах, мы получим другие результаты (другую кривую). Чтобы избежать этой проблемы несоизмеримости, иногда предлагается переводить их в безразмерные величины — это можно назвать нормализацией или стандартизацией. Существуют, однако, различные пути сделать это, приводящие к неэквивалентным моделям. Один из подходов — нормализовать с помощью известной (или оценочной) точности измерения, минимизируя тем самым расстояние Махаланобиса до точек на линии и обеспечивая решение с максимальным правдоподобием. Неизвестные точности измерения могут быть найдены с помощью дисперсионного анализа.

Кратко, метод наименьших полных квадратов не имеет свойства инвариантности по единицам измерения, т.е. он не является масштабно инвариантным. Для полноценности модели мы требуем, чтобы это свойство выполнялось. Дальнейшее продвижение вперёд, это понимание, что отклонения (расстояния), измеряемые в других единицах, могут быть скомбинированы, если используется умножение, а не сложение. Рассмотрим аппроксимацию прямой, для каждой точки данных произведение горизонтального и вертикального отклонений равно удвоенной площади треугольника, образованного отрезками отклонений и аппроксимирующей прямой. Мы выбираем прямую, минимизирующую сумму этих площадей. Нобелевский лауреат Пол Самуэльсон доказал в 1942, что в двумерном случае эта прямая выражается исключительно в терминах отношений квадратических отклонений и корреляции коэффициентов, которые (1) удовлетворяют уравнению, если наблюдения находятся на прямой линии; (2) обнаруживают масштабную инвариантность, (3) обнаруживают инвариантность при обмене переменных. Эта прямая переоткрывалась в различных дисциплинах и известна как стандартизованная главная ось, приведённая главная ось, функциональная зависимость средних геометрических, регрессия наименьших квадратов, диагональная регрессия и прямая наименьших площадей. Тофаллис расширил этот подход для работы с несколькими переменными.