Метод на най-малките квадрати

от Уикипедия, свободната енциклопедия

Методът на най-малките квадрати (МНМК) в числения анализ е един от най-разпространените методи за решаване на системи уравнения с повече неизвестни от броя на уравненията. Полученото решение е апроксимация, при която се минимизира сумата от квадратите на грешката, получена за всяко едно уравнение.

Най-разпространеното приложение на метода е в областта на моделирането и по-точно в експерименталния подход (идентификация на системи). От гледна точка на идентификацията търсеният модел зависи от набора входно-изходни наблюдения на поведението на изследваната система (наличните данни), а неизвестните величини са параметрите на модела. Всяко уравнение от системата е описание на връзката на конкретен изход от множеството фактори, участващи в модела. Когато моделът описва статично поведение (изходът не зависи от времето), тогава факторите са входните величини, но когато се моделира динамика, изходът може да зависи както от своята предистория, така и от тази на входните величини. Тогава факторите са изместени във времето входно-изходни наблюдения.

При експерименталното моделиране МНМК се използва за оценка на параметрите на модела, като целта е поведението му да се доближи максимално до това на описвания обект. Това е оптимизационна задача като целевата функция е сума от квадратите на остатъчната грешка – разликата между наблюдавания изход и този на модела.

В зависимост от това дали изходът на модела е линейна функция на параметрите се разграничават:

  • линейни или стандартни МНМК;
  • нелинейни МНМК.

Често в литературата [1][2][3][4]под МНМК се разбира линейният вариант на метода, а когато моделът е нелинеен по параметри в явен вид се записва, че става дума за нелинейните МНМК (например в [5][2]). Когато изходът е линейна функция на параметрите, те може да се изразят само чрез данните и така оценките на параметрите по МНМК да се определят еднократно. От друга страна, когато моделът е нелинеен по параметри, оценките се определят с итеративни методи, като на всяка стъпка оценките се актуализират и така, при определени условия, се приближават към търсените оптимални стойности. Един вариант е на всяка итерация да се приложи МНМК. Това е т.нар. линеен подход за оценяване, при който, въпреки че моделът е нелинеен, той изкуствено се приема за линеен по параметри. Примери за такива методи са методът на разширените НМК, разширеният матричен МНМК и др.[3]. Другият вариант е нелинейният модел да се разглежда именно като нелинеен и да се използват методи за числена оптимизация, които също се реализират като итеративни процедури. Често използван метод за числена оптимизация при решаването на задачата на нелинейните НМК, е Гаус-Нютон[5], при който, за разлика от оригиналния метод на Нютон, вместо Хесиана се използва нейна апроксимация.

Когато разпределението на изхода е Гаусово, оценките по МНМК съвпадат с тези по метода на максималното правдоподобие (МП). С други думи, при такова разпределение на изхода на обекта, максимизирането на функцията на правдоподобие е равносилно на минимизиране на сумата от квадратите на остатъка.[6]

МНМК е създаден от Карл Гаус (1795),[7] но за пръв път е публикуван от Адриен Мари Лежандър.

Линеен модел – червенА линия и данни – сини точки.

По-долу е представена постановката на задачата на МНМК за оценяване параметрите на линеен модел с един изход. Методът е изведен и са анализирани свойствата на оценките. След това е извършено обобщение на МНМК за модел с много изходи. Накрая е засегната задачата на нелинейните най-малки квадрати.

МНМК за линеен модел[редактиране | редактиране на кода]

МНМК за едноизходов модел[редактиране | редактиране на кода]

Моделът, когато е линеен по параметри и е с един изход [3], може да се запише в следния общ вид:

където е скаларният изход (зависимата променлива), е остатъкът, е векторът на регресорите (факторите), е векторът на параметрите. При едноизходови модели броят на регресорите е равен на броя на параметрите (но при многоизходовите модели ).

Целева функция[редактиране | редактиране на кода]

При МНМК се минимизира сумата от квадратите на остатъците. Когато зависимата променлива е една, целевата функция е

Нека се въведат векторите и матрицата , които са

За динамични модели е броят предишни тактове, необходими за формиране на вектора на регресорите в даден момент, а за статични модели (т. е. не се отчита предисторията в поведението на обекта). Тогава може да се използват по-удобните за извежданията записи за модела:

и за целевата функция:

В литературата [8], свързана с идентификацията на системи (в случая изследваната система е обектът, подлежащ на моделиране), често се използва следният запис на целевата функция:

При него отпада остатъкът, който е неизвестен преди оценяването на параметрите, и така зависи явно от търсените параметри и наличните данни, което е стъпка към определянето на оптималните оценки. В горния запис е 2-норма на вектор (квадратен корен на сумата от квадратите на елементите на вектора).

В долните разглеждания целевата функция се представя с по-краткия запис . Тогава критерият, заложен в МНМК, добива вида:

Оценки по МНМК[редактиране | редактиране на кода]

Определянето на вектора на параметрите , при който целевата функция има минимум, се извършва, като първо се представи във вид, удобен за диференциране, после се определи градиентът и накрая се изрази , при която се нулира.

  • Диференциране на скаларна функция по векторен аргумент

Целевата функция зависи от векторен аргумент. Затова в извеждането по-долу се дават някои зависимости, свързани с диференцирането на скаларна функция по векторен аргумент.

Нека са дадени матриците и , както и векторите и . Тогава са в сила съотношенията:

Когато е симетрична, какъвто е случаят в долните разглеждания , то .

  • Извеждане на НМК

Първо се представя във вид, удобен за диференциране:

След диференциране на израза, за градиента на се получава:

Той се приравнява на нула и се определя , т.е.

Така окончателно оценките по НМК , при които сумата от квадратите на остатъка е минимална (или с други думи се нулира), се изчисляват от израза:

МНМК за многоизходов модел, представен с матрица на параметрите[редактиране | редактиране на кода]

Когато моделът е линеен по параметри, а изходът е векторен (т.е. ), тогава описанието на обекта може да се запише в следния общ вид[9] [10] [2]:

където е векторният остатък за -тото наблюдение, е векторът на регресорите, е матрицата на параметрите. При представянето на многоизходовите модели с матрица на параметрите, броят на регресорите не е равен на броя на параметрите (виж регресионен модел).

Целева функция[редактиране | редактиране на кода]

Тук целевата функция е сумата от квадратите на остатъците по всеки изход и за всяко наблюдение, т.е.

Нека се въведат матриците и матрицата , които са

Отново за динамични модели , а за статични .

Ако се използва матрицата на остатъците, то -тият диагонален елемент на е сумата от квадратите на -тия остатък, или . Така за може да се използва по-удобният за извежданията запис:

където е следа на матрица (сумата от диагоналните елементи).

Оценки по МНМК[редактиране | редактиране на кода]

Определянето на матрицата на параметрите , при която целевата функция има минимум, се извършва по същия начин като в предишните разглеждания: първо се представя в удобен за диференциране вид, после се определя градиентната матрица и накрая се изразява , при която се нулира.

  • Диференциране на скаларна функция по матричен аргумент

Аналогът на първата производна на скаларната функция по отношение на матричния аргумент се нарича градиентна матрица (в някои източници се нарича градиент). Елементите на тази матрица са първите частни производни на целевата функция по отношение на параметрите, т.е. -тият елемент е .

Градиентната матрица има вида:

По-долу е описан начинът, по който се определя оптималната матрица като функция на наличните входно-изходни данни.

  • Извеждане на НМК

Представянето на във вид, удобен за диференциране по отношение на , се получава по следния начин:

След диференциране на , градиентната матрица добива вида:

За определяне на оптималните параметри изразът за се приравнява на нула, т.е.

Матрицата , за която се нулира, е

Тя съдържа оценките на параметрите, определени по НМК.

МНМК за многоизходов модел, представен с вектор на параметрите[редактиране | редактиране на кода]

При тази постановка на задачата, моделът е

където векторният изход и остатъкът за текущото наблюдиние са , матрицата на регресорите е , а векторът на параметрите е . При това представяне параметрите са подредени във вектор и поради тази причина извеждането [2] не се отличава от това за едноизходови модели, дадено по-горе. Оптималните оценки по НМК отново се изчисляват от израза:

Тук е важно да се отчете структурата на матрицата и вектора , а именно:

Графична интерпретация[редактиране | редактиране на кода]

За да може графично да се изобразят важните за МНМК пространства, нека моделът да е с един вход и един изход и да е представен като:

Нека също остатъкът да се развие по следния начин:

В двете представяния са въведени матриците и . Матрицата има свойството да проектира мерното пространство във факторното пространство, което е дефинирано от стълбовете на . Наистина лесно се проверява, че , т.е., както се очаква при тази проекция, стълбовете на се проектират в себе си. Матрицата проектира в споменатото пространство като от представянето на модела се вижда, че получената проекция е именно .

На фигурата е представен случай, при който стълбовете на са с размерност , а броят им (броят на факторите) е , т.е. . Двата стълба и на матрицата на данните образуват база в (това е равнината, в която те лежат – факторното пространство ). Тъй като е проекция на в , то лежи в тази равнина. Колкото по-информативна е комбинацията от факторите, толкова равнината ще е по-близка до . В граничния случай, когато факторите съдържат цялата информация за описание на изхода (това означава, че няма остатъчна неопределеност), ще лежи във факторната равнина. На фигурата е вектор, който не лежи в тази равнина, което показва, че той не може изцяло да бъде описан с двата фактора.

Втората матрица има свойството да проектира - мерното пространство в ортогонално пространство на факторното. (Наистина лесно се проверява, че , т.е. проектира стълбовете на в ортогонално за тях пространство и затова тяхната проекция е 0.) От израза се вижда, че проектира в това ортогонално пространство, а получената проекция е остатъкът . Матрицата се използва в събспейс методите [8][11][12][13] за оценяване на параметрите на динамични модели, описани в пространство на състоянието. На фигурата ортогоналното допълнение на факторното (двумерно) пространство е правата (едномерно пространство). Векторът лежи именно на тази права. В такъв случай, колкото по-голямо е нивото на неопределеността в , толкова посоката на този вектор е по-близка до правата . В граничния случай, когато съдържа само неопределеност, а това означава, че факторите са напълно неинформативни, векторът ще лежи на правата .

Източници[редактиране | редактиране на кода]

  1. Elden, L., (2005) Numerical linear algebra and applications in data mining. Preliminary version. Lecture Notes, Department of Mathematics, Linkoping University, Sweden.
  2. а б в г Ефремов, А., (2013) Идентификация на многомерни системи, DAR-RH, ISBN 978-954-9489-34-7
  3. а б в Гарипов, Е., (2004) Идентификация системи Част II. Идентификация чрез дискретни стохастични регресионни модели. ТУ – София, ISBN 954-438-392-1
  4. Матеев, П., (2012) Линеен регресионен модел. Метод на най-малките квадрати. Теорема на Гаус-Марков, София, архив на оригинала от 24 септември 2015, https://web.archive.org/web/20150924071527/http://www.fmi.uni-sofia.bg/lecturers/vois/pmat/Regression.pdf, посетен на 2014-09-04 
  5. а б Eriksson, J. and P.-A.Wedin, (2004) Truncated Gauss-Newton algorithms for ill-conditioned nonlinear least squares problems. In: Optimization Methods and Software, volume 19,  6, pp. 721 – 737
  6. Charnes, A et al. The Equivalence of Generalized Least Squares and Maximum Likelihood Estimates in the Exponential Family // Journal of the American Statistical Association. Taylor and Francis Online, April 2012. DOI:10.1080/01621459.1976.10481508. p. 169 – 171. Посетен на 1 септември 2020. (на английски)
  7. Bretscher, Otto. Linear Algebra With Applications, 3rd ed. Upper Saddle River NJ, Prentice Hall, 1995.
  8. а б Verhaegen, M. and V. Verdult, (2007) Filtering and System Identification. A least Squares Approach. Cambridge University Press, The Edinburgh Building, Cambridge CB2 8RU, UK.
  9. Вучков, И., (1996) Идентификация. ИК Юрапел, София
  10. Dayal, B. S. and J. F. MacGregor, (1997) Multi-output process identification. In: Journal of Process Control, volume 7, № 4, pp. 269 – 282
  11. Verdult, V., (2002) Non-linear System Identification – A State Space Approach. Ph.D. thesis, The Netherlands, 2002
  12. Moor, B. D. and P. V. Overschee, (1995) Trends in Control: a European Perspective. Springer-Verlag London Limited
  13. Jorgensen, S. B. and J. H. Lee, (2002) Recent advances and challenges in process identification. – In: AIChE Symposium Series, ISU 326, pp. 55 – 74. Budapest, Hungary.