Розділ 1
Коли рівнянь більше, ніж невідомих
Суперечлива система рівнянь — не помилка в умові задачі, а нормальний результат будь-яких вимірювань. Тому питання «як знайти розв'язок?» доведеться замінити іншим: «як знайти найкращий компроміс?»
1.1. Три виміри однієї довжини
Невідоме тут одне — довжина $x$. А рівнянь три, по одному на кожен вимір:
$$x = 10{,}02, \qquad x = 10{,}05, \qquad x = 9{,}98.$$Формально ця система не має розв'язку: одне число не може дорівнювати водночас трьом різним. Але ніхто не скаже «задача не має відповіді». Інтуїтивно всі беруть середнє арифметичне — 10,017 м. Чому саме середнє, а не, скажімо, середній за величиною з трьох вимірів (медіану)? Поки що це лише відчуття. У розділі 3 ми побачимо, що середнє — це і є розв'язок методом найменших квадратів для цієї задачі.
Зверніть увагу: якщо «повірити» одному виміру, його рівняння виконається точно, але два інших розійдуться з ним на десятки міліметрів. Жоден вибір не задовольняє всі три рівняння одразу. Кожна оцінка — це компроміс, і виміри з ним не згодні по-різному.
1.2. Геодезія: звідки береться нев'язка
Геодезисти стикаються з цією ситуацією щодня й давно дали їй назву. Два класичні приклади.
Кути трикутника
Теодолітом виміряли всі три кути трикутника: $\alpha = 62^\circ 14' 20''$, $\beta = 51^\circ 27' 48''$, $\gamma = 66^\circ 17' 58''$. Їхня сума мала б дорівнювати рівно $180^\circ$, а виходить
$$\alpha + \beta + \gamma = 180^\circ 00' 06''.$$Зайві $6''$ — це нев'язка (англ. misclosure): на скільки виміри порушують умову, яка мусить виконуватися точно. Для форми трикутника достатньо двох кутів, третій вимір — надлишковий. Саме завдяки йому ми взагалі бачимо, що виміри неточні.
Замкнений нівелірний хід
Нівеліром вимірюють перевищення $h$ — на скільки одна точка вища за іншу. Вийшли з репера Rp (точки з відомою висотою 100,000 м), пройшли через пункти A, B, C і повернулися назад. Повернулися в ту саму точку, тож сума всіх перевищень мусить дорівнювати нулю. Але ні:
Усі три способи виправлення «замикають» хід: сума стає нулем, висота Rp знову 100,000 м. Але висоти пунктів A, B, C у кожному варіанті різні. Способів розподілити 7 мм — нескінченно багато: чотири поправки пов'язані лише однією умовою (їхня сума має дорівнювати −7 мм), тож три з них можна обрати довільно, а четверта визначиться сама. Щоб обрати один, потрібен принцип, а не смак. Його ми й шукатимемо в наступних розділах.
1.3. Пряма через три точки
Кожна точка $(x_i;\,y_i)$ вимагає, щоб пряма пройшла через неї: $a + b\,x_i = y_i$. Отже, маємо два невідомих ($a$ та $b$) і три рівняння:
$$ \begin{cases} a + 1\cdot b = 1\\ a + 2\cdot b = 2\\ a + 3\cdot b = 2 \end{cases} \qquad\Longleftrightarrow\qquad \underbrace{\begin{pmatrix}1 & 1\\ 1 & 2\\ 1 & 3\end{pmatrix}}_{A} \underbrace{\begin{pmatrix}a\\ b\end{pmatrix}}_{\boldsymbol\theta} = \underbrace{\begin{pmatrix}1\\ 2\\ 2\end{pmatrix}}_{\mathbf y}. $$Матричний запис $A\boldsymbol\theta = \mathbf y$ поки що просто компактна форма тієї самої системи. Але запам'ятайте його: з розділу 5 він стане головним інструментом, і точно такий самий запис ви побачите в будь-якому підручнику з машинного навчання.
Будь-які два рівняння з трьох мають єдиний розв'язок, адже через дві точки завжди проходить пряма. Але кожна пара дає свою пряму:
| Беремо рівняння | Розв'язок | Пряма | Що з «зайвою» точкою |
|---|---|---|---|
| 1 і 2 | $a = 0,\ b = 1$ | $y = x$ | точка 3 нижче на 1 |
| 2 і 3 | $a = 2,\ b = 0$ | $y = 2$ | точка 1 нижче на 1 |
| 1 і 3 | $a = 0{,}5,\ b = 0{,}5$ | $y = 0{,}5 + 0{,}5x$ | точка 2 вище на 0,5 |
Спробуйте самі.
Що варто помітити, граючись із графіком:
- Три нулі одночасно не виходять. Коли підганяєте пряму під одну точку, «тікає» інша. Це не ваша незграбність: для цих трьох точок такої прямої просто не існує.
- Обрати пару рівнянь — нечесно. Кожна кнопка «1 + 2», «2 + 3», «1 + 3» дає пряму, яка ідеально задовольняє два виміри і повністю ігнорує третій. А чим третій гірший?
- Суперечність створюють дані, а не метод. Перетягніть точки так, щоб вони стали на одну пряму (наприклад, точку 3 у $(3;\,3)$). Система одразу стає сумісною, і з'являється точний розв'язок.
Забігаючи наперед: найкраща в певному сенсі пряма для точок $(1;1),\,(2;2),\,(3;2)$ — це $y = \tfrac{2}{3} + \tfrac12 x$. Вона не збігається з жодною з трьох «парних» прямих і не проходить точно через жодну точку. Чому саме вона і в якому сенсі «найкраща», з'ясуємо в розділах 2–4. Спробуйте виставити $a \approx 0{,}67$, $b = 0{,}5$ і подивіться на нев'язки.
Ще одне спостереження. На графіку навмисно немає жодного числа, яке б казало «ця пряма краща за ту». Ви бачите три окремі нев'язки, але як звести їх до однієї оцінки? Скласти? Узяти найбільшу? А що робити зі знаками? Це питання розділу 2.
1.4. Навіщо взагалі міряти «зайве»?
Може, простіше міряти рівно стільки, скільки невідомих? Тоді система завжди матиме розв'язок і жодних суперечностей не буде. Практики ніколи так не роблять, і на те є дві причини.
- Контроль. Без надлишкових вимірів помилку неможливо навіть помітити. Один вимір дає одне число, і нам лишається тільки йому вірити. Два виміри показують, що щось не так. Три й більше дозволяють знайти, який вимір хибний.
- Точність. Випадкові похибки бувають і плюсові, і мінусові. Коли вимірів багато, вони частково гасять одна одну, і результат стає стабільнішим.
Звідси стандартна геодезична практика: кути вимірюють кількома прийомами, нівелірні ходи замикають, у мережах міряють більше сторін і кутів, ніж потрібно для побудови. Ціна цього — суперечливі системи рівнянь, з якими доводиться щось робити.
Уважно подивіться, що стається з гістограмою, коли ввімкнено промах: середнє зсувається. Одна груба помилка псує результат, навіть коли вимірів багато. Цей недолік середнього (і самого МНК) ми детально розберемо в розділі 10.
1.5. Те саме мовою машинного навчання
Задача «провести пряму через точки» — це лінійна регресія, найперша модель у будь-якому курсі машинного навчання. Слова інші, суть та сама:
| Геодезія / МНК | Машинне навчання |
|---|---|
| виміри $(x_i, y_i)$ | навчальна вибірка, training set (рядки датасету) |
| невідомі $a,\ b$ | параметри моделі: зсув $w_0$ (bias) і вага $w_1$ (weight) |
| рівняння $a + b\,x_i = y_i$ | передбачення моделі на $i$-му прикладі: $\hat y_i = w_0 + w_1 x_i$ |
| матриця $A$ | матриця ознак $X$ (design matrix) зі стовпцем одиниць |
| нев'язка $r_i$ | помилка передбачення, residual |
| надлишкові виміри, $n > k$ | прикладів більше, ніж параметрів — звичайний стан справ |
| ручне підбирання $a$, $b$ повзунками | навчання моделі (training) |
У ML «рівнянь» зазвичай не три, а тисячі чи мільйони, і система завжди несумісна. Ніхто не очікує, що модель пройде точно через усі точки даних. Навпаки, якщо параметрів стільки ж, скільки прикладів, модель може «завчити» кожну точку. Це вже не успіх, а перенавчання (overfitting), і ми побачимо його наживо в розділі 7.
А повзунки $a$ і $b$ — це «навчання вручну». Далі ми зробимо дві речі, які робить кожна бібліотека ML: сформулюємо, що саме мінімізувати (функцію втрат, розділ 2), і знайдемо мінімум автоматично — формулою (розділи 3–6) або градієнтним спуском (розділ 10).
🔍 Хочете більше подробиць? Сумісність систем, ранги, геометрія, ступені свободи
Коли система має розв'язок: теорема Кронекера–Капеллі
Система $A\boldsymbol\theta = \mathbf y$ сумісна тоді й лише тоді, коли ранг матриці $A$ дорівнює рангу розширеної матриці $[A\,|\,\mathbf y]$ (до $A$ дописано стовпець правих частин). Змістовно: стовпець $\mathbf y$ не додає нічого «нового», він уже виражається через стовпці $A$.
Для прямої через три точки $A$ має розмір $3\times 2$, і її ранг дорівнює 2, якщо не всі $x_i$ однакові. Розширена матриця квадратна, $3\times3$. Її ранг дорівнює 3, якщо $\det[A\,|\,\mathbf y] \ne 0$, і це відбувається рівно тоді, коли точки не лежать на одній прямій. Нижче — рахунок для точок з інтерактиву 1.3. Посуньте там точки і поверніться сюди.
Чому з реальними даними система майже напевно несумісна
Умова «три точки на одній прямій» — це одне рівняння $\det[A\,|\,\mathbf y] = 0$ на координати. Якщо до кожного $y_i$ додається випадковий неперервний шум, то ймовірність потрапити точно на цю поверхню дорівнює нулю (кажуть, що множина сумісних даних має міру нуль). Тож несумісність — не невдача конкретного експерименту, а гарантований наслідок шуму. Уявіть, що кидаєте голку на аркуш: ймовірність влучити точно в намальовану лінію дорівнює нулю.
Перший погляд на геометрію
Запишімо систему «по стовпцях»:
$$a\begin{pmatrix}1\\1\\1\end{pmatrix} + b\begin{pmatrix}1\\2\\3\end{pmatrix} = \begin{pmatrix}1\\2\\2\end{pmatrix}.$$Ліва частина за всіх можливих $a, b$ — це всі лінійні комбінації двох векторів у тривимірному просторі, тобто площина, що проходить через початок координат. Система сумісна, якщо вектор $\mathbf y$ лежить у цій площині. Шум «виштовхує» $\mathbf y$ з площини, і тоді природне питання: яка точка площини найближча до $\mathbf y$? Відповідь — ортогональна проєкція. Це і є МНК, і в розділі 5 ми покажемо це в тривимірній сцені.
Геодезична термінологія: необхідні й надлишкові виміри
Позначимо $n$ — кількість вимірів (рівнянь), $k$ — кількість необхідних вимірів, тобто мінімум, що однозначно визначає невідомі. Різниця
$$r = n - k$$— кількість надлишкових вимірів, або ступенів свободи. Саме $r$ показує, скільки незалежних перевірок (умов на кшталт «сума кутів = 180°») можна скласти.
| Задача | $n$ | $k$ | $r$ |
|---|---|---|---|
| Три виміри однієї довжини | 3 | 1 | 2 |
| Три кути трикутника | 3 | 2 | 1 |
| Замкнений нівелірний хід (3 невідомі висоти) | 4 | 3 | 1 |
| Пряма через три точки | 3 | 2 | 1 |
| Лінійна регресія: 1000 прикладів, 10 ознак + зсув | 1000 | 11 | 989 |
Ступені свободи ще повернуться: у розділі 9 від $r$ залежатиме оцінка точності результату (знаменник $n - k$ у формулі дисперсії, той самий, що в ML-статистиці регресії).
Які бувають похибки
- Випадкові — непередбачувані за знаком і величиною, дрібні, їх багато. Саме з ними працює МНК.
- Систематичні — однакові за знаком: розтягнута рулетка, неправильно відкалібрований прилад. Надлишковими вимірами тим самим приладом їх не виявити.
- Грубі (промахи) — описка, не та точка, збій датчика. МНК до них дуже чутливий, це показав інтерактив 1.4. Стійкі методи — у розділі 10.
1.6. Код
Перший фрагмент — «повірити» кожному виміру по черзі й подивитися на відхилення решти. JavaScript-варіант можна запустити прямо тут.
Другий — пряма через три точки: складаємо матрицю $A$, перевіряємо сумісність за рангами і розв'язуємо систему для кожної пари рівнянь.
Якщо передати ці самі три точки в sklearn.linear_model.LinearRegression().fit(x.reshape(-1, 1), y),
бібліотека без жодних скарг на несумісність поверне intercept_ ≈ 0.667 і coef_ = [0.5].
Це та сама пряма $y = \tfrac23 + \tfrac12 x$. Усередині бібліотеки — метод найменших квадратів, і до кінця
підручника ви знатимете, як саме він працює.
1.7. Перевірте себе
Відрізок виміряли 5 разів. Скільки надлишкових вимірів $r$?
Пряму $y = a + b\,x$ проводять через 10 точок. Скільки надлишкових рівнянь?
Параболу $y = a + b\,x + c\,x^2$ підбирають за 7 точками. Скільки надлишкових рівнянь?
Параболу $y = a + b\,x + c\,x^2$ підбирають за трьома точками з інтерактиву 1.3. Скільки буде надлишкових рівнянь?
Точного розв'язку немає, отже потрібен критерій якості: одне число, яке каже, наскільки пряма погана. Сума нев'язок? Сума модулів? Найбільша нев'язка? Сума квадратів? Кожен варіант веде до свого методу, а в ML — до своєї функції втрат. У розділі 2 ми порівняємо їх наживо і зрозуміємо, чому квадрати виграють.