Розділ 3

Мінімум помилки: чаша

Критерій обрано: сума квадратів $S(a, b)$. Тепер подивимося на нього як на поверхню. Виявиться, що це чаша з одним-єдиним дном, і саме її форма пояснює, чому МНК такий надійний.

3.1. Два простори: дані й параметри

Проблема Треба знайти пару чисел $(a, b)$, для якої $S(a, b) = \sum (y_i - a - b\,x_i)^2$ найменша. У розділі 2 ми робили це перебором або кнопкою. Але як влаштована ця функція? Чи може в неї бути кілька «ям»? Чи не пропустимо ми справжній мінімум?

Ключ до відповіді — подивитися на задачу з іншого боку. Досі ми малювали простір даних: осі $x$ і $y$, точки, пряма. Пряма $y = a + bx$ повністю задається двома числами: $a$ — висота, на якій вона перетинає вісь $y$, і $b$ — нахил. Знаючи ці два числа, пряму можна намалювати, і навпаки: з намальованої прямої їх можна зчитати. Отже, замість того щоб малювати пряму, можна просто записати пару чисел $(a;\ b)$.

А пару чисел зручно позначити точкою на звичайній площині: по горизонталі відкладаємо $a$, по вертикалі $b$. Так само місто на карті задане двома числами, довготою й широтою, і ми ставимо на карті крапку, а не малюємо саме місто. Пряма $y = 1 + 0{,}5x$ стає точкою $(1;\ 0{,}5)$, пряма $y = 3 - 0{,}5x$ — точкою $(3;\ -0{,}5)$. Цю другу площину, з осями $a$ і $b$, називають простором параметрів.

Помітили? Усі чотири прямі проходять через точку $(2;\ 2)$, а всі чотири точки лежать на одній прямій. Це не збіг. Умова «пряма проходить через точку даних $(2;\ 2)$» означає $a + 2b = 2$, а це рівняння прямої в просторі параметрів. Отже, кожна точка даних — це пряма в просторі параметрів: усі пари $(a;\ b)$, для яких пряма проходить через цю точку. Коли точок даних кілька, ці прямі зазвичай не мають спільної точки (надлишкові виміри з розділу 1), і МНК шукає в просторі параметрів місце, що найменше «суперечить» їм усім.

Одна точка в просторі параметрів — це ціла пряма в просторі даних.
Прямі з однаковим нахилом лежать на одній горизонталі простору параметрів, а всі горизонтальні прямі ($b = 0$) — на осі $a$.
У кожній точці простору параметрів можна порахувати число $S(a, b)$. Отримуємо «рельєф» над площиною $(a, b)$.
Знайти найкращу пряму означає знайти найнижчу точку цього рельєфу.

3.2. Карта помилки

Праворуч — «топографічна карта» функції $S(a, b)$: кожна лінія з'єднує точки з однаковим значенням $S$, як горизонталі на карті місцевості. Що темніше, то нижче. Хрестик — дно.

Центрувати $x$

Погравшись із картою, зверніть увагу на кілька речей.

Лінії рівня — еліпси, вкладені один в одного навколо єдиного центру. Жодних інших «ям» на карті немає, хоч куди подивитися.
Кожен переріз — парабола. Зафіксуйте $b$ і рухайтеся лише вздовж $a$: $S$ змінюється як парабола (лівий графік під картою). Те саме вздовж $b$. На дні вершини обох парабол збігаються з поточною точкою: нахил в обох напрямках дорівнює нулю.
Еліпси нахилені. Параметри $a$ і $b$ «зчеплені»: якщо збільшити нахил $b$, найкраще $a$ зменшується. Пряма ніби обертається навколо центру ваги точок. Про це — у 3.5.
Рухаючи точки даних, ви змінюєте всю чашу: вона зсувається, повертається, стає ширшою чи вужчою. Але лишається чашею з одним дном.

3.3. Чаша в об'ємі

Та сама функція, намальована як поверхня над площиною $(a, b)$. Висота — значення $S$. Помаранчева точка — поточні параметри з карти вище, зелена — дно.

Математики називають таку поверхню еліптичним параболоїдом. Вертикальні перерізи — параболи, горизонтальні — еліпси з карти. Кулька, покладена будь-де на схил, скотиться в одне й те саме місце.

3.4. Чому дно лише одне

Розкрийте дужки в $S(a, b) = \sum (y_i - a - b\,x_i)^2$ і зберіть подібні доданки. Вийде многочлен другого степеня від $a$ і $b$:

$$S(a, b) = n\,a^2 + 2\Bigl(\sum x_i\Bigr) a b + \Bigl(\sum x_i^2\Bigr) b^2 - 2\Bigl(\sum y_i\Bigr) a - 2\Bigl(\sum x_i y_i\Bigr) b + \sum y_i^2.$$

Для трьох точок з розділу 1 це $S = 3a^2 + 12ab + 14b^2 - 10a - 22b + 9$. Формулу для ваших даних показано внизу інтерактиву.

Із цього запису випливає все, що ми бачили.

Перерізи — параболи гілками вгору. При фіксованому $b$ функція має вигляд $n\,a^2 + \ldots$, а $n > 0$. При фіксованому $a$ маємо $(\sum x_i^2)\,b^2 + \ldots$, і коефіцієнт теж додатний.
Уся поверхня — чаша, а не сідло, якщо не всі $x_i$ однакові. (Умову перевіримо в «подробицях».) У чаші може бути лише одне дно.
Усе про чашу визначають п'ять чисел: $n$, $\sum x_i$, $\sum x_i^2$, $\sum y_i$, $\sum x_i y_i$. Хоч у вас мільйон точок, для пошуку мінімуму достатньо цих сум. Це важливо для програмування: дані можна обробляти потоком, не тримаючи в пам'яті.

Для порівняння: поверхня $\sum |r_i|$ з розділу 2 складається з пласких граней, як дорогоцінний камінь. У неї гострі ребра, похідна на них не існує, а дно може бути цілою пласкою гранню. Гладка чаша суми квадратів — саме те, що дозволить у розділі 4 знайти мінімум формулою.

3.5. Форма чаші: круглі й витягнуті

Натисніть у інтерактиві «точки далеко від нуля». Чаша перетворилася на довгу вузьку долину: еліпси витягнулися в тонкі нахилені смуги. Чому так?

Параметр $a$ — висота прямої в точці $x = 0$. Коли всі дані зібрані біля $x \approx 5$, ця точка далеко за межами даних. Невелика зміна нахилу $b$ сильно змінює $a$, а пряма в області даних майже не рухається. Параметри стають сильно залежними, і на карті це видно як вузька нахилена долина.

Тепер увімкніть «Центрувати $x$». Замість $y = a + b\,x$ запишемо ту саму пряму як $y = c + b\,(x - \bar x)$, де $\bar x$ — середнє значення $x$. Тепер $c$ — це висота прямої в центрі даних. Прямі ті самі, але еліпси на карті стали рівними, з осями вздовж $c$ і $b$. Параметри «розчепилися»: найкраще $c$ не залежить від $b$.

Для точного розв'язку форма чаші байдужа: дно все одно одне. Але вона стає критичною, коли мінімум шукають кроками. Натисніть «Покотити кульку» спершу без центрування, а потім з ним. У вузькій долині кулька петляє від схилу до схилу й ледве повзе вздовж дна. У круглій чаші вона доходить за кілька кроків.

3.6. Ландшафт функції втрат

Зв'язок з ML

Карта й чаша в цьому розділі — найважливіша картинка машинного навчання. Там її називають ландшафтом функції втрат (loss landscape).

Простір параметрів (parameter space, weight space): кожна точка — окрема модель. У нас він двовимірний, у нейромережі — мільйони або мільярди вимірів. Але ідея та сама.
Навчання — це рух по ландшафту вниз. Кнопка «Покотити кульку» робить саме це: з поточної точки крок у напрямку найшвидшого спуску, потім ще крок. Це градієнтний спуск (gradient descent), основний алгоритм навчання нейромереж. Докладно розберемо його в розділі 10.
Масштабування ознак. Те, що ви зробили галочкою «Центрувати $x$», у ML називається feature centering. Разом з діленням на стандартне відхилення це standardization. Порада «нормалізуйте ознаки перед навчанням» — це саме про те, щоб перетворити вузьку долину на круглу чашу, де градієнтний спуск швидко збігається.
Опуклість. Для лінійної регресії з MSE ландшафт завжди чаша з одним дном (кажуть, опукла задача). Будь-який спуск прийде до того самого глобального мінімуму. Ландшафт нейромережі зовсім інший: безліч ям, сідел і плато. Там немає ні формули, ні гарантії. МНК — той рідкісний щасливий випадок, коли все розв'язується точно.

🔍 Хочете більше подробиць? Квадратична форма, додатна визначеність, власні числа, число обумовленості

Матричний запис чаші

Позначимо $\boldsymbol\theta = (a, b)^\mathsf{T}$. Функцію з 3.4 можна записати компактно:

$$S(\boldsymbol\theta) = \boldsymbol\theta^\mathsf{T} M \boldsymbol\theta - 2\,\boldsymbol\theta^\mathsf{T}\mathbf v + c, \qquad M = \begin{pmatrix} n & \sum x_i \\ \sum x_i & \sum x_i^2 \end{pmatrix},\quad \mathbf v = \begin{pmatrix} \sum y_i \\ \sum x_i y_i \end{pmatrix},\quad c = \sum y_i^2.$$

Якщо згадати матрицю $A$ з розділу 1 (рядки $(1, x_i)$), то $M = A^\mathsf{T}A$ і $\mathbf v = A^\mathsf{T}\mathbf y$. Ці два вирази — головні герої розділів 4–6.

Виділення повного квадрата

Якщо $\boldsymbol\theta^*$ — дно чаші, то для будь-якої точки

$$S(\boldsymbol\theta) = S(\boldsymbol\theta^*) + (\boldsymbol\theta - \boldsymbol\theta^*)^\mathsf{T} M\, (\boldsymbol\theta - \boldsymbol\theta^*).$$

Це двовимірний аналог тотожності $\sum(x - l_i)^2 = n(x - \bar l)^2 + \text{const}$ з розділу 2. Форма чаші (еліпси) залежить лише від $M$, тобто лише від $x_i$. Значення $y_i$ визначають тільки те, де дно і наскільки воно високо.

Коли це справді чаша: додатна визначеність

Чаша з одним дном вийде, якщо $\boldsymbol\delta^\mathsf{T} M \boldsymbol\delta > 0$ для будь-якого ненульового $\boldsymbol\delta$ (матриця додатно визначена). Для симетричної матриці $2\times2$ достатньо, щоб $M_{11} > 0$ і $\det M > 0$. Перше очевидно ($n > 0$), а друге —

$$\det M = n\sum x_i^2 - \Bigl(\sum x_i\Bigr)^2 = n \sum (x_i - \bar x)^2 \;\ge\; 0,$$

причому рівність можлива лише тоді, коли всі $x_i$ однакові. Тоді чаша вироджується в жолоб: пряму через вертикальний стовпчик точок провести однозначно неможливо. (Спробуйте в інтерактиві поставити всі точки на одну вертикаль.)

Звідки ще $M = A^\mathsf{T}A$ гарантує невід'ємність: $\boldsymbol\delta^\mathsf{T}A^\mathsf{T}A\boldsymbol\delta = \|A\boldsymbol\delta\|^2 \ge 0$. Нуль буває, лише коли стовпці $A$ лінійно залежні. У розділі 5 це стане ключовим аргументом.

Еліпси, власні числа й число обумовленості

Осі еліпсів $\boldsymbol\delta^\mathsf{T} M\boldsymbol\delta = \text{const}$ напрямлені вздовж власних векторів $M$, а їхні довжини обернено пропорційні $\sqrt{\lambda_1}$ і $\sqrt{\lambda_2}$ (власним числам). Відношення осей $\sqrt{\lambda_1/\lambda_2}$ показує, наскільки витягнута долина. Величину $\kappa = \lambda_1/\lambda_2$ називають числом обумовленості матриці $M$.

Дані	$M$	$\kappa$
3 точки, без центрування	$\begin{pmatrix}3 & 6\\ 6 & 14\end{pmatrix}$	≈ 46
3 точки, центровані	$\begin{pmatrix}3 & 0\\ 0 & 2\end{pmatrix}$	1,5
точки біля $x \approx 5$, без центрування	$\begin{pmatrix}4 & 19\\ 19 & 91{,}5\end{pmatrix}$	≈ 1800
ті самі, центровані	$\begin{pmatrix}4 & 0\\ 0 & 1{,}25\end{pmatrix}$	3,2

Після центрування $\sum (x_i - \bar x) = 0$, тож позадіагональні елементи $M$ зникають і еліпси стають осьовими. Велике $\kappa$ шкодить двічі. По-перше, градієнтний спуск сповільнюється: за один крок похибка вздовж пологого напрямку зменшується лише в $(1 - \text{const}/\kappa)$ разів. По-друге, як ми побачимо в розділі 6, чисельні формули втрачають точність. Тому програми МНК і бібліотеки ML так часто центрують і масштабують дані.

3.7. Код

Python-версія рахує $S$ на сітці й малює лінії рівня та поверхню (потрібні numpy і matplotlib). JavaScript-версія виводить ту саму «карту» символами: що темніший символ, то вища помилка. Запустіть її та знайдіть нахилений еліпс.

3.8. Перевірте себе

Усі питання — для трьох точок $(1;1)$, $(2;2)$, $(3;2)$, для яких $S = 3a^2 + 12ab + 14b^2 - 10a - 22b + 9$.

Чому дорівнює $S(0, 1)$?

Яке найменше значення $S$? (Можна десятковим дробом.)

На скільки зросте $S$, якщо з дна зсунутися на 1 вздовж $a$ (тобто $a = \tfrac23 + 1$, $b = \tfrac12$)?

Чому дорівнює коефіцієнт при $b^2$, якщо його порахувати через $x_i$?

Далі: знайти дно формулою

На дні чаші обидва перерізи мають вершину, тобто нахил уздовж $a$ і вздовж $b$ дорівнює нулю. Мовою математичного аналізу: $\partial S/\partial a = 0$ і $\partial S/\partial b = 0$. Оскільки $S$ — многочлен другого степеня, ці похідні лінійні, і ми отримуємо звичайну систему з двох лінійних рівнянь. Вона має назву нормальні рівняння, і в розділі 4 ми виведемо та розв'яжемо її.