Розділ 2
Що означає «найкращий» розв'язок?
Точного розв'язку немає — це ми з'ясували в розділі 1. Щоб обрати з нескінченної кількості прямих одну, потрібне одне число, яке каже, наскільки пряма погана. Від того, як його порахувати, залежить відповідь.
2.1. Від трьох нев'язок — до одного числа
Ось чотири природні ідеї. Кожна з них колись пропонувалася всерйоз.
| Ідея | Формула | Людською мовою |
|---|---|---|
| Сума нев'язок | $\left|\sum r_i\right|$ | «у середньому пряма не завищує й не занижує» |
| Сума модулів (L1) | $\sum |r_i|$ | «загальна відстань по вертикалі від точок до прямої» |
| Мінімакс (L∞) | $\max |r_i|$ | «найгірша точка має бути якомога ближче» |
| Сума квадратів (L2) | $\sum r_i^2$ | «сумарна площа квадратів нев'язок» |
Метод найменших квадратів — це просто вибір останнього рядка: серед усіх прямих шукаємо ту, для якої
$$S(a, b) = \sum_{i=1}^{n} \bigl(y_i - a - b\,x_i\bigr)^2 \;\longrightarrow\; \min.$$Звідси й назва: найменша сума квадратів. Але чому не інші рядки? Порівняймо їх наживо.
2.2. Чотири кандидати на одному графіку
Що варто помітити:
- Сума нев'язок не годиться. Натисніть «Обертати навколо центру ваги»: пряма крутиться, а сума лишається нулем. Точки, що вище за пряму, «компенсують» точки нижче, навіть якщо всі вони далеко. Критерій, який має нескінченно багато «найкращих» розв'язків, нічого не обирає.
- Три інші критерії дають три різні прямі. Для трьох точок з розділу 1 усі вони мають однаковий нахил $b = 0{,}5$, але різний зсув: L1 дає $a = 0{,}5$, мінімакс дає $a = 0{,}75$, сума квадратів дає $a = \tfrac23$. Поняття «найкращий» не існує саме по собі, воно завжди «найкращий за певним критерієм».
- Промах по-різному впливає на кожен критерій. Увімкніть «6 точок з промахом» і оптимальні прямі. Пряма L1 не зрушила взагалі: вона просто «пожертвувала» поганою точкою. Мінімакс зсунуло найбільше, майже на одиницю вниз, бо він дбає саме про найгіршу точку. Сума квадратів посередині: промах тягне пряму до себе й помітно зменшує її нахил, бо його великий квадрат дорого коштує.
2.3. Одне невідоме: середнє, медіана, середина розмаху
Повернімося до найпростішої задачі з розділу 1: три виміри довжини, одне невідоме $x$. Нев'язки тут $v_i = x - l_i$, і кожен критерій стає функцією однієї змінної. Її можна просто намалювати.
Тут ховається кілька важливих речей.
- Кожен критерій має «свою» відповідь. Сума квадратів мінімальна в середньому арифметичному, сума модулів — у медіані (середньому за порядком вимірі), максимум — у середині розмаху. Інтуїтивне середнє з розділу 1 виявилося методом найменших квадратів.
- Тільки парабола гладка. Крива $\sum v_i^2$ — це парабола, і її нахил змінюється плавно: від'ємний ліворуч, нуль у мінімумі, додатний праворуч. Дві інші криві — ламані. Їхній нахил стрибає (подивіться в таблиці: у $\sum|v_i|$ він набуває лише цілих значень), і в точці мінімуму похідної взагалі немає.
- Мінімум L1 буває неоднозначним. Додайте четвертий вимір: дно ламаної $\sum|v_i|$ стає горизонтальним відрізком, і будь-яка точка між 10,02 і 10,04 однаково «найкраща». Парабола такого не допускає: у неї мінімум завжди один.
- Промах. Замініть 9,98 на 10,20. Медіана зсунулася з 10,02 до 10,05, середнє — на 7 см, середина розмаху — майже на 10 см. Робастність (стійкість до промахів) — сильна сторона L1, і до неї ми повернемося в розділі 10.
2.4. Повертаємося до нівелірного ходу
У розділі 1 нівелірний хід не замкнувся на 7 мм, і ми бачили кілька способів «розкидати» нев'язку. Тепер у нас є інструмент, щоб їх порівняти. Виправлення $v_1, \dots, v_4$ мусять у сумі дати $-7$ мм, щоб хід замкнувся. Три з них задайте самі, четверте визначиться з цієї умови.
Результат показовий. Сума модулів не розрізняє варіанти «порівну» та «все на один хід»: для обох вона дорівнює 7. Сума квадратів розрізняє і однозначно обирає рівний розподіл по −1,75 мм. Він найкращий, якщо ми однаково довіряємо всім ходам.
А варіант «пропорційно довжині», який на практиці вважають правильним, за сумою квадратів трохи гірший (13,48 проти 12,25). Суперечності тут немає: ми ще не врахували, що довгий хід вимірюється гірше за короткий. Коли в розділі 8 додамо ваги вимірів, зважена сума квадратів дасть саме розподіл пропорційно довжині.
2.5. Чому саме квадрати
Ось причини, з яких сума квадратів стала стандартом і в геодезії, і в машинному навчанні.
- Знаки не заважають. Квадрат, як і модуль, робить кожен доданок невід'ємним, тож нев'язки не компенсують одна одну.
- Гладкість, а отже, формула. $S(a, b)$ — многочлен другого степеня від $a$ і $b$. Його похідні — лінійні функції. Прирівнявши їх до нуля, отримуємо систему лінійних рівнянь, яку розв'язує будь-який комп'ютер (і людина з олівцем). Для L1 і L∞ такої формули немає: потрібні ітераційні алгоритми лінійного програмування. Саме цей аргумент — «легко обчислити, легко запрограмувати» — вирішив справу у XIX столітті й досі важливий. Далі розділи 3–6 цілком про нього.
- Єдиність. Графік $S(a, b)$ — «чаша» з одним дном (розділ 3). Відповідь не залежить від того, звідки почати пошук, і неоднозначності, як у L1, не буває.
- Великі помилки штрафуються сильніше. Одна нев'язка 2 коштує 4, а дві нев'язки по 1 разом коштують 2. Квадрати «розмазують» помилку по всіх вимірах, замість того щоб звалювати її на один. Це ми бачили в нівелірному ході. Зворотний бік — чутливість до промахів.
- Статистика. Якщо похибки вимірів мають нормальний (гауссів) розподіл, мінімізація суми квадратів дає найбільш правдоподібну оцінку. Це найглибша причина, і їй присвячено розділ 9.
- Геометрія. $\sqrt{\sum r_i^2}$ — це звичайна евклідова відстань (теорема Піфагора в $n$-вимірному просторі). Тож МНК шукає найближчу точку в звичному сенсі, а розв'язок має вигляд ортогональної проєкції (розділ 5).
Першим цю задачу поставив геодезист. У 1757 році Руджер Бошкович, обробляючи виміри дуг меридіана, щоб визначити форму Землі, запропонував критерій, близький до L1: сума нев'язок дорівнює нулю, а сума їхніх модулів мінімальна. Метод найменших квадратів уперше опублікував Адрієн-Марі Лежандр у 1805 році, у додатку до праці про орбіти комет. Карл Фрідріх Гаусс у 1809 році заявив, що користувався методом з 1795-го. Саме так він у 1801 році за кількома спостереженнями розрахував орбіту щойно відкритої й загубленої карликової планети Церера, і астрономи знайшли її там, де він передбачив.
2.6. Функції втрат у машинному навчанні
Те, що ми називали «критерієм якості», у машинному навчанні називають функцією втрат (loss function). Навчити модель означає знайти параметри, за яких втрати мінімальні. Усі наші кандидати мають стандартні ML-назви:
| Тут | У ML | Де використовують |
|---|---|---|
| $\sum r_i^2$ | MSE, mean squared error: $\frac1n\sum r_i^2$ (і RMSE — корінь із неї) | стандарт для регресії, основа лінійної регресії й нейромереж для регресійних задач |
| $\sum |r_i|$ | MAE, mean absolute error | коли в даних бувають викиди; прогноз медіани |
| $\max |r_i|$ | max error, мінімакс | рідко; там, де важлива гарантія для найгіршого випадку |
| гібрид L2 і L1 | Huber loss | квадрати для малих нев'язок, модулі для великих (розділ 10) |
Множник $\frac1n$ у MSE нічого не змінює: мінімум $S$ і мінімум $S/n$ досягаються в тій самій точці. Він лише робить число незалежним від розміру вибірки.
Вибір функції втрат — таке саме рішення моделювальника, як вибір моделі. Ви щойно бачили, що від нього залежить відповідь. І в ML MSE обирають найчастіше з тих самих причин: вона гладка (зручні градієнти), для лінійних моделей має розв'язок у формулі й має ймовірнісне пояснення.
А код нижче показує найпримітивніший спосіб «навчання»: перебрати всі пари $(a, b)$ на сітці й узяти найкращу. Для двох параметрів це працює. Для мільйона параметрів нейромережі — ні, і тому потрібні або формули (розділи 3–6), або градієнтний спуск (розділ 10).
🔍 Хочете більше подробиць? Норми, доведення для середнього й медіани, лінійне програмування
Три критерії — три норми вектора нев'язок
Зберемо нев'язки у вектор $\mathbf r = (r_1, \dots, r_n)$. Тоді три критерії — це три способи виміряти його «довжину»:
$$\|\mathbf r\|_1 = \sum |r_i|, \qquad \|\mathbf r\|_2 = \sqrt{\sum r_i^2}, \qquad \|\mathbf r\|_\infty = \max |r_i|.$$Мінімізувати $\|\mathbf r\|_2$ і $\|\mathbf r\|_2^2 = S$ — те саме, бо корінь — зростаюча функція. Квадрат беруть, щоб позбутися кореня й отримати многочлен. Нижче — «одиничні кола» цих норм для $n = 2$: усі вектори довжини 1. Кутасті фігури L1 і L∞ — геометрична причина зламів на графіках вище.
Чому мінімум суми квадратів — середнє
Для одного невідомого $S(x) = \sum_{i=1}^n (x - l_i)^2$. Похідна:
$$S'(x) = 2\sum_{i=1}^n (x - l_i) = 2\Bigl(n x - \sum l_i\Bigr) = 0 \quad\Longrightarrow\quad x = \frac1n \sum l_i = \bar l.$$Друга похідна $S''(x) = 2n > 0$, отже це мінімум. Без похідних те саме видно з тотожності
$$\sum (x - l_i)^2 = n\,(x - \bar l)^2 + \sum (l_i - \bar l)^2.$$Другий доданок від $x$ не залежить, а перший мінімальний (нульовий) при $x = \bar l$. Зверніть увагу на схему: похідна → лінійне рівняння → формула. У розділі 4 вона повториться для прямої, тільки рівнянь буде два.
Чому мінімум суми модулів — медіана
Функція $\sum |x - l_i|$ лінійна між сусідніми вимірами. Її нахил дорівнює (кількість вимірів лівіше від $x$) мінус (кількість правіше), бо кожен доданок $|x - l_i|$ має нахил $+1$ праворуч від $l_i$ і $-1$ ліворуч. Нахил змінює знак там, де ліворуч і праворуч однаково вимірів, тобто в медіані. Для парного $n$ нахил дорівнює нулю на цілому відрізку між двома середніми вимірами, звідси неєдиність.
Аналогічно $\max|x - l_i|$ визначається лише двома крайніми вимірами, і мінімум лежить точно посередині між ними.
Чому сума нев'язок дорівнює нулю для будь-якої прямої через центр ваги
$$\sum_{i=1}^n \bigl(y_i - a - b\,x_i\bigr) = n\,\bigl(\bar y - a - b\,\bar x\bigr).$$Вираз дорівнює нулю, щойно $\bar y = a + b\,\bar x$, тобто пряма проходить через точку $(\bar x;\,\bar y)$, яка б не була $b$. Цікаво, що пряма МНК теж завжди проходить через центр ваги. Це побачимо в розділі 4.
Як усе-таки розв'язують L1 і L∞
Обидві задачі зводяться до лінійного програмування. Наприклад, для L1 вводять допоміжні змінні $t_i \ge |r_i|$:
$$\min \sum t_i \quad\text{за умов}\quad -t_i \le y_i - a - b\,x_i \le t_i.$$Це стандартна задача з лінійною цільовою функцією й лінійними нерівностями, для неї є симплекс-метод і методи внутрішньої точки. Розв'язується надійно, але це ітераційний алгоритм, а не формула. Альтернатива — ітеративно перезважений МНК (IRLS): L1 розв'язують як послідовність зважених задач найменших квадратів. МНК виявляється «цеглинкою» навіть для інших критеріїв (розділ 10).
Вертикальні чи перпендикулярні відстані?
Ми міряємо нев'язку по вертикалі, тобто вважаємо, що $x_i$ відомі точно, а помиляється лише $y_i$. Якщо похибки є в обох координатах, природніше мінімізувати перпендикулярні відстані. Це вже інша задача, повна МНК (total least squares). Вона розв'язується через SVD, про яке піде мова в розділі 6.
2.7. Код
Обчислюємо чотири критерії для прямих з розділу 1, а потім «навчаємо» пряму перебором по сітці для кожного критерію. JavaScript-варіант перебирає близько 120 000 пар $(a, b)$ прямо у вашому браузері.
Одне невідоме: середнє, медіана й середина розмаху, зокрема для даних з промахом.
2.8. Перевірте себе
Виміри: 3, 5, 10. Яку оцінку дає метод найменших квадратів?
Ті самі виміри 3, 5, 10. Яку оцінку дає мінімізація суми модулів?
А мінімакс (мінімізація найбільшого відхилення)?
Нев'язки прямої: $+1$, $-1$, $+2$. Чому дорівнює $S = \sum r_i^2$?
Критерій обрано: $S(a, b) = \sum (y_i - a - b\,x_i)^2$. У цьому розділі ми знаходили мінімум кнопкою або перебором. Але як він виглядає і чому він один? У розділі 3 намалюємо $S(a, b)$ як поверхню над площиною параметрів — це «чаша», і пряма МНК відповідає її дну. У машинному навчанні ту саму картинку називають ландшафтом функції втрат.