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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Результат підгонки сукупності спостережень (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}
тобто випадкові змінні є гомоскедастичними і між ними відсутня будь-яка залежність.

Для такої моделі оцінка \hat \boldsymbol\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