Метод найменших квадратів

Метод найменших квадратів — метод знаходження наближеного розв'язку надлишково-визначеної системи. Часто застосовується в регресійному аналізі. На практиці найчастіше використовується лінійний метод найменших квадратів, що використовується у випадку системи лінійних рівнянь. Зокрема важливим застосуванням у цьому випадку є оцінка параметрів у лінійній регресії, що широко застосовується у математичній статистиці і економетриці.

Результат підгонки сукупності спостережень $(x_i, y_i)$ (червоним) квадратичною функцією $y=\beta_1+\beta_2x+\beta_3x^2\,$ (синім). У лінійних найменших квадратах функція не повинна бути лінійною у своєму аргументі $x,$ а лише щодо своїх параметрів $\beta_j,$ які треба визначити для отримання найкращого результату

Мотиваційний приклад

Графік точок даних (червоним), лінія найменших квадратів (синім) і відстані (зеленим)

У висліді досліду, отримали чотири $(x, y)$ точки даних: $(1, 6),$ $(2, 5),$ $(3, 7)$ і $(4, 10)$ (позначені червоним). Ми хочемо знайти лінію $y=\beta_1+\beta_2 x$, яка найкраще підходить для цих точок. Інакше кажучи, ми хотіли б знайти числа $\beta_1$ і $\beta_2$, які приблизно розв'язують надвизначену лінійну систему

$\begin{alignat}{3} \beta_1 + 1\beta_2 &&\; = \;&& 6 & \\ \beta_1 + 2\beta_2 &&\; = \;&& 5 & \\ \beta_1 + 3\beta_2 &&\; = \;&& 7 & \\ \beta_1 + 4\beta_2 &&\; = \;&& 10 & \\ \end{alignat}$

чотирьох рівнянь з двома невідомими в деякому найкращому сенсі.

Підхід найменших квадратів розв'язання цієї проблеми полягає у спробі зробити якомога меншою суму квадратів похибок між правою і лівою сторонами цієї системи, тобто необхідно знайти мінімум функції

$\begin{align}S(\beta_1, \beta_2) =& \left[6-(\beta_1+1\beta_2)\right]^2 +\left[5-(\beta_1+2\beta_2) \right]^2 \\ &+\left[7-(\beta_1 + 3\beta_2)\right]^2 +\left[10-(\beta_1 + 4\beta_2)\right]^2.\end{align}$

Мінімум визначають через обчислення часткової похідної від $S(\beta_1, \beta_2)$ щодо $\beta_1$ і $\beta_2$ і прирівнюванням їх до нуля

$\frac{\partial S}{\partial \beta_1}=0=8\beta_1 + 20\beta_2 -56$

$\frac{\partial S}{\partial \beta_2}=0=20\beta_1 + 60\beta_2 -154.$

Це приводить нас до системи з двох рівнянь і двох невідомих, які звуться нормальними рівняннями. Якщо розв'язати, ми отримуємо

$\beta_1=3.5$

$\beta_2=1.4$

І рівняння $y=3.5+1.4x$ є рівнянням лінії, яка підходить найбільше. Мінімальна сума квадратів похибок є $S(3.5, 1.4)=1.1^2+(-1.3)^2+(-0.7)^2+0.9^2=4.2.$

Використання квадратичної моделі

Важливо, у методі лінійних найменших квадратів ми не обмежені використанням лінії як моделі як у попередньому прикладі. Наприклад, ми могли вибрати обмежену квадратичну модель $y=\beta_1 x^2$. Ця модель все ще лінійна в сенсі параметру $\beta_1$, отже ми все ще можемо здійснювати той самий аналіз, будуючи систему рівнянь з точок даних:

$\begin{alignat}{2} 6 &&\; = \beta_1 (1)^2 \\ 5 &&\; = \beta_1 (2)^2 \\ 7 &&\; = \beta_1 (3)^2 \\ 10 &&\; = \beta_1 (4)^2 \\ \end{alignat}$

Часткові похідні щодо параметрів (цього разу лише одного) знов обчислені і прирівняні до 0:

$\frac{\partial S}{\partial \beta_1} = 0 = 708 \beta_1 - 498$

і розв'язані

$\beta_1 = .703,$

що призводить до вислідної найпідхожої моделі $y = .703 x^2$

Лінійний випадок

Одна незалежна змінна

Нехай маємо лінійну регресію зі скалярною змінною x:

$y = x\beta_1 + \beta_0,$

а також вибірку початкових даних $(y_i, x_i)$ розміру M. Тоді

$\beta_0 = \frac{1}{M} \sum_i y_i - \frac{\beta_1}{M}\sum_i x_i, \beta_1 = \frac{M\sum_i x_iy_i - \sum_i x_i\sum_i y_i}{M\sum_i x_i^2 - (\sum_i x_i)^2}$

Множинна регресія (випадок багатьох незалежних змінних)

Для надлишково-визначеної системи m лінійних рівнянь з n невідомими $\beta_j, \quad (m > n) :$

$\sum_{j=1}^n X_{ij}\beta_j = y_i, \quad i=\overline{1,m}, \quad j=\overline{1,n}$

чи в матричній формі запису:

$X \boldsymbol \beta = \mathbf y,$

зазвичай не існує точного розв'язку, і потрібно знайти такі β, які мінімізують наступну норму:

$\underset{\boldsymbol\beta} {\operatorname{arg\,min}} \, \sum_{i=1}^{m}\left|y_i - \sum_{j=1}^{n} X_{ij}\beta_j\right|^2 = \underset{\boldsymbol\beta} {\operatorname{arg\,min}} \, \big\|\mathbf y - X \boldsymbol\beta \big\|^2.$

Такий розв'язок завжди існує і він є єдиним:

$\hat \boldsymbol\beta = (X^ \top X )^{-1}X^ \top \mathbf y$

хоч дана формула не є ефективною через необхідність знаходити обернену матрицю.

Виведення формули

Значення $S = \sum_{i=1}^{m}\left|y_i - \sum_{j=1}^{n} X_{ij}\beta_j\right|^2$ досягає мінімуму в точці в якій похідна по кожному параметру рівна нулю. Обчислюючи ці похідні одержимо:

$\frac{\partial S}{\partial \beta_j}=2\sum_i r_i\frac{\partial r_i}{\partial \beta_j}=0 \ (j=1,2,\dots, n)$

де використано позначення $r_i= y_i - \sum_{j=1}^{n} X_{ij}\beta_j.$

Також виконуються рівності:

$\frac{\partial r_i}{\partial \beta_j}=-X_{ij}.$

Підставляючи вирази для залишків і їх похідних одержимо рівність:

$\frac{\partial S}{\partial \beta_j}=-2\sum_{i=1}^{m}X_{ij} \left( y_i-\sum_{k=1}^{n} X_{ik}\beta_k \right)=0.$

Дану рівність можна звести до вигляду:

$\sum_{i=1}^{m}\sum_{k=1}^{n} X_{ij}X_{ik}\hat \beta_k=\sum_{i=1}^{m} X_{ij}y_i\ (j=1,2,\dots, n)\,$

або в матричній формі:

$(\mathbf X^\top \mathbf X) \hat \boldsymbol \beta = \mathbf X^\top \mathbf y .$

Числові методи для обчислення розв'язку

Якщо матриця $\ X^\top X$ є невиродженою та додатноозначеною, тобто має повний ранг, тоді система може бути розв'язана за допомогою розкладу Холецького $X^\top X=R^\top R$, де $R$ — верхня трикутна матриця.

$R^\top R \hat \boldsymbol \beta = X^\top \mathbf y.$

Розв'язок отримаємо в два кроки:

1. Отримаємо $\mathbf z$ з рівняння $R^\top \mathbf z = X^\top \mathbf y,$
2. Підставимо і отримаємо $\hat \boldsymbol \beta$ з $R \hat \boldsymbol \beta= \mathbf z.$

В обох випадках використовуються властивості трикутної матриці.

Статистичні властивості

Одним із найважливіших застосувань лінійного МНК є оцінка параметрів лінійної регресії. Для заданого набору даних $\{y_i,\, x_{i1}, \ldots, x_{ip}\}_{i=1}^n$ будується модель:

$y_i =\beta_0 \beta_1 x_{i1} + \cdots + \beta_p x_{ip} + \varepsilon_i = x'_i\beta + \varepsilon_i, \qquad i = 1, \ldots, n,$

або в матричній формі:

$y = X\beta + \varepsilon, \,$

де:

$y = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}, \quad X = \begin{pmatrix} x'_1 \\ x'_2 \\ \vdots \\ x'_n \end{pmatrix} = \begin{pmatrix} x_{11} & \cdots & x_{1p} \\ x_{21} & \cdots & x_{2p} \\ \vdots & \ddots & \vdots \\ x_{n1} & \cdots & x_{np} \end{pmatrix}, \quad \beta = \begin{pmatrix} \beta_1 \\ \vdots \\ \beta_p \end{pmatrix}, \quad \varepsilon = \begin{pmatrix} \varepsilon_1 \\ \varepsilon_2 \\ \vdots \\ \varepsilon_n \end{pmatrix}.$

В цих формулах $\beta$ — вектор параметрів, які оцінюються, наприклад, за допомогою методу найменших квадратів, а $\varepsilon$ — вектор випадкових змінних.

У класичній моделі множинної лінійної регресії приймаються такі умови:

• $y_i = \beta_0 \beta_1 x_{i1} + \cdots + \beta_p x_{ip} + \varepsilon_i = x'_i\beta + \varepsilon_i, \qquad i = 1, \ldots, n,$
• $\operatorname{E}[\,\varepsilon_i] = 0.$
• $\operatorname{E}[\,\varepsilon_i \varepsilon_j] = \begin{cases}\sigma^2 & i = j \\ 0 & i \neq j \end{cases}$

тобто випадкові змінні є гомоскедастичними і між ними відсутня будь-яка залежність.

• Ранг матриці X рівний p + 1, тобто між пояснюючими змінними відсутня лінійна залежність.

Для такої моделі оцінка $\hat \boldsymbol\beta$ одержана методом найменших квадратів володіє властивостями:

• Незміщеність. Оцінка $\hat \boldsymbol\beta$ є незміщеною, тобто $\operatorname{E}[\, \hat\beta \,| X \,] = \beta.$ Справді:

$\operatorname{E}[\,\hat\beta] = \operatorname{E}\Big[(X'X)^{-1}X'(X\beta+\varepsilon)\Big] = \beta + \operatorname{E}\Big[(X'X)^{-1}X'\varepsilon\Big] = \beta + \Big[(X'X)^{-1}X'\varepsilon\Big]\operatorname{E}(\varepsilon) =\beta$

• Коваріаційна матриця оцінки $\hat \boldsymbol\beta$ рівна:

$\operatorname{Var}[\, \hat\beta \,] = \sigma^2(X'X)^{-1}.$

Це випливає з того, що $\operatorname{Var}[\, Y \,] = \operatorname{Var}[\, \varepsilon \,]$ і

$\operatorname{E}[\,\hat\beta] = \operatorname{Var}[\, (X^ \top X )^{-1}X^ \top Y \,]= (X^ \top X )^{-1}X^ \top \operatorname{Var}[\, Y \,] X (X^ \top X )^{-1} =$

$= \sigma^2(X'X)^{-1} (X^ \top X )^{-1}(X^ \top X ) = \sigma^2(X'X)^{-1}$

• Ефективність. Згідно з теоремою Гауса — Маркова оцінка, що одержана МНК, є найкращою лінійною незміщеною оцінкою.
• Змістовність. При доволі слабких обмеженнях на матрицю X метод найменших квадратів є змістовним, тобто при збільшенні розміру вибірки, оцінка за імовірністю прямує до точного значення параметру. Однією з достатніх умов є наприклад прямування найменшого власного значення матриці $(X^ \top X )$ до безмежності при збільшенні розміру вибірки.
• Якщо додатково припустити нормальність змінних $\varepsilon,$ то оцінка МНК має розподіл:

$\hat\beta\ \sim\ \mathcal{N}\big(\beta,\ \sigma^2(X'X)^{-1}\big)$

В математичному моделюванні

Нехай ми маємо вибірку початкових даних $f(x_i)=y_i\ i=\overline{1..n}$. Функція $f$ — невідома.

Якщо ми знаємо приблизний вигляд функції $f(x)$, то задамо її у вигляді функціоналу $F(x_i,a_0,\ldots,a_m) \approx y_i$, де $a_0,\ldots , a_m$ — невідомі константи.

Нам потрібно мінімізувати відмінності між $F$ та $f$. Для цього беруть за міру суму квадратів різниць значень цих функцій у всіх точках $x_i$ і її мінімізують (тому метод так і називається):

$I(a_0,\ldots,a_m) = \sum_{i=0}^n (y_i - F(x_i, a_0, \ldots, a_m))^2 \to \min$

Коефіцієнти $a_j$ в яких така міра мінімальна знаходять з системи:

$\begin{cases} \displaystyle \frac{\delta I(a_0,\ldots,a_m)}{\delta a_0} = 0 \\ \ldots \\ \displaystyle \frac{\delta I(a_0,\ldots,a_m)}{\delta a_m} = 0 \end{cases}$

Джерела

• Лоусон Ч., Хенсон Р. Численное решение задач методом наименьших квадратов. — М.: Наука, 1986.
• Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-е изд., испр. — Т. 2: Айвазян С А. Основы эконометрики. — М.: ЮНИТИ- ДАНА, 2001. - 432 с. ISBN 5-238-00305-6
• Björck, Åke (1996). Numerical methods for least squares problems. Philadelphia: SIAM. ISBN 0-89871-360-9.
• Greene, William H. (2002). Econometric analysis (5th ed.). New Jersey: Prentice Hall