Розділ 10
МНК і машинне навчання
Лінійна регресія — «hello world» машинного навчання, і це той самий МНК. Але ML додає три речі, яких класична геодезія довго не потребувала: навчання кроками, коли формула недоступна; штраф за складність; стійкість до брудних даних. У цьому розділі — усі три.
10.1. Навіщо ще щось, якщо є формула?
- Нормальні рівняння для мільйона параметрів — це матриця мільйон на мільйон. Її не вмістити в пам'ять, не кажучи вже про розв'язання.
- Перенавчання з розділу 7 нікуди не зникло: гнучка модель підлаштовується під шум.
- Один промах псує весь МНК-розв'язок (розділи 8–9), а в реальних даних промахи трапляються завжди.
10.2. Градієнтний спуск: кулька котиться всерйоз
Замість того щоб розв'язувати $\nabla S = 0$ одразу, можна йти до мінімуму кроками проти градієнта:
$$\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \eta\,\nabla\,\mathrm{MSE}(\boldsymbol\theta_t),\qquad \nabla\,\mathrm{MSE} = -\frac{2}{n}A^\mathsf{T}(\mathbf y - A\boldsymbol\theta).$$Кожен крок потребує лише множення на матрицю, без розв'язання системи. Параметр $\eta$ — крок навчання (learning rate). А якщо градієнт рахувати не по всіх даних, а по одному випадковому прикладу чи невеликій пачці, отримаємо стохастичний градієнтний спуск (SGD), на якому навчаються всі сучасні нейромережі.
- Крок навчання — головний параметр. За малого $\eta$ спуск повільний, біля межі $2/L$ кулька перестрибує дно туди-сюди, а трохи далі за межею розлітається на нескінченність. Спробуйте $\eta = 1{,}05\cdot 2/L$.
- Форма чаші вирішує швидкість. Зніміть «стандартизувати x»: долина витягується, і навіть найкращий крок потребує сотень ітерацій (розділ 3). Звідси універсальна порада ML: нормалізуйте ознаки.
- SGD шумить, бо кожен крок бачить одну точку, але кожен крок у 40 разів дешевший. На мільйонах прикладів це в мільйон разів дешевше. Шум біля дна прибирають, поступово зменшуючи крок.
- Кнопка ⚡ — нормальні рівняння: одразу на дно. Для лінійної регресії з тисячами ознак це найкращий вибір (розділ 6). Градієнтні методи потрібні, коли формули немає (нейромережі) або вона задорога.
10.3. Ridge: штраф за великі параметри
Пам'ятаєте многочлен, що дико розгойдувався в розділі 7, і коефіцієнти, що «розхитувалися» в розділі 6? Спільна риса: величезні параметри протилежних знаків. Гребенева регресія (ridge, регуляризація Тихонова) додає до суми квадратів штраф за їхню величину:
$$\min_{\boldsymbol\theta}\ \Bigl(|\mathbf y - A\boldsymbol\theta|^2 + \lambda\,|\boldsymbol\theta|^2\Bigr)\quad\Longrightarrow\quad \bigl(A^\mathsf{T}A + \lambda I\bigr)\,\hat{\boldsymbol\theta} = A^\mathsf{T}\mathbf y.$$Нормальні рівняння майже ті самі, лише до діагоналі додано $\lambda$. Геодезист упізнає тут старий прийом: псевдовиміри. Штраф $\lambda\theta_j^2$ — це те саме, що додати до системи «уявний вимір» $\theta_j = 0$ з вагою $\lambda$. Саме так рахує інтерактив: звичайним МНК з кількома додатковими рядками.
- Малий λ — майже звичайний МНК: крива проходить біля кожної точки, коефіцієнти величезні, помилка на нових даних велика.
- Середній λ приборкує коефіцієнти на кілька порядків. Крива стає гладкою, а помилка на нових даних мінімальна, хоча параметрів так само 10. Регуляризація — альтернатива зменшенню степеня.
- Великий λ «придушує» все, і модель вироджується майже в сталу. Це знову недонавчання. Найкраще λ шукають перевіркою на окремих даних або крос-валідацією.
Та сама ідея вже траплялася нам тричі. Доданок $\lambda I$ був у методі Левенберга — Марквардта (розділ 8). Обрізання малих сингулярних чисел (розділ 6) — «жорстка» версія того самого, а ridge — «м'яка». А в розділі 9 ridge виявився оцінкою максимальної апостеріорної ймовірності за гауссового апріорного припущення про параметри.
10.4. Промахи: Губер, L1, RANSAC і тест Баарди
МНК чутливий до промахів, бо квадрат «штрафує» велику нев'язку непропорційно сильно: промах тягне пряму до себе з силою, пропорційною своїй нев'язці. Є два підходи. Можна зменшити вплив великих нев'язок (стійкі функції втрат). А можна знайти й виключити промахи.
- Функція Губера: квадрат для малих нев'язок ($|r| \le \delta$) і модуль для великих. Промах усе ще впливає, але з обмеженою силою. Рахують ітеративно перезваженим МНК (IRLS): кожна ітерація — звичайний зважений МНК, де точки з великими нев'язками отримують вагу $\delta/|r|$.
- L1 (сума модулів) з розділу 2: вага $1/|r|$ у тому самому IRLS.
- RANSAC (Фішлер і Боллес, 1981): беремо навмання мінімальний набір точок (для прямої — дві), проводимо пряму, рахуємо, скільки точок з нею згодні (в межах порогу $t$). Повторюємо багато разів, обираємо найбільший «консенсус» і рахуємо МНК лише за ним. Стандарт у комп'ютерному зорі й обробці хмар точок лазерного сканування.
- Тест Баарди (data snooping, 1968) — класика геодезії. Кожну нев'язку МНК нормують на її очікувану похибку з урахуванням важеля (розділ 5): $w_i = v_i / (\sigma\sqrt{1 - h_{ii}})$. Для доброго виміру $w_i$ має стандартний нормальний розподіл, тож $|w_i| > 3{,}29$ трапляється лише з імовірністю 0,1%. Найгірший вимір виключають, розв'язок перераховують, тест повторюють.
- Промах «розмазується». Натисніть «Тест Баарди». На першому кроці порогу 3,29 перевищує більше точок, ніж справжніх промахів: МНК перекосило пряму, і постраждали чесні сусіди. Тому виключають по одному, найгірший, і перераховують. Після двох кроків підозрілих не лишається.
- Промах з великим важелем найнебезпечніший: крайня точка тягне МНК-пряму найсильніше (розділ 5), а її власна нев'язка через це виходить скромною. Тут RANSAC і L1 впораються краще за Губера з великим δ.
- Без промахів усі чотири методи згодні, і найточніший з них МНК (розділ 9). За стійкість платять трохи меншою точністю на чистих даних.
10.5. Карта відповідностей: МНК ↔ ML
| Геодезія / МНК | Машинне навчання | Розділ |
|---|---|---|
| надлишкові виміри, $n > k$ | навчальна вибірка, прикладів більше за параметри | 1 |
| критерій якості $\sum r_i^2$ | функція втрат MSE | 2 |
| поверхня $S(a, b)$, еліпси | ландшафт функції втрат | 3 |
| нормальні рівняння | normal equation, закрита форма | 4 |
| проєкція, $R^2$ | передбачення як проєкція, метрика $R^2$ | 5 |
| QR, SVD, обумовленість | всередині lstsq і LinearRegression, масштабування ознак | 6 |
| базисні функції | ознаки, feature engineering, перенавчання | 7 |
| ваги, Гаусс — Ньютон | sample_weight, нелінійні моделі, $J^\mathsf{T}\mathbf r$ і backprop | 8 |
| максимальна правдоподібність, $\sigma^2(A^\mathsf{T}A)^{-1}$ | втрати як −log правдоподібності, невизначеність | 9 |
| ітераційне зрівнювання | градієнтний спуск, SGD | 10 |
| псевдовиміри, апріорні дані | ridge-регуляризація, MAP | 10 |
| пошук промахів, стійке зрівнювання | стійкі втрати (Huber), RANSAC, очищення даних | 10 |
10.6. Що обрати на практиці
scikit-learn
LinearRegression— звичайний МНК (усередині SVD). Для невеликих і середніх задач без промахів.Ridge,RidgeCV— ridge;CV-версія сама підбирає λ крос-валідацією.Lasso— штраф $\lambda\sum|\theta_j|$ замість квадратів: частину коефіцієнтів робить рівно нульовими, тобто сама обирає ознаки.SGDRegressor— стохастичний спуск для дуже великих даних, що не влазять у пам'ять.HuberRegressor,RANSACRegressor,TheilSenRegressor— стійкі до промахів.-
І завжди:
StandardScalerперед навчанням (розділи 3, 6, 10),train_test_splitабо крос-валідація для перевірки (розділ 7).
🔍 Хочете більше подробиць? Збіжність спуску, Adam, ridge через SVD, LASSO, точка зламу, надійність за Баардою
Швидкість градієнтного спуску
Для квадратичної функції з гессіаном, власні числа якого від $\mu$ до $L$, спуск з оптимальним постійним кроком зменшує відстань до мінімуму щонайменше в $\frac{\kappa - 1}{\kappa + 1}$ разів за крок, де $\kappa = L/\mu$ — те саме число обумовленості з розділів 3 і 6. За $\kappa = 1000$ це 0,998, тобто потрібні тисячі кроків. Імпульс (momentum, метод Нестерова) і спряжені градієнти покращують залежність до $\sqrt\kappa$. Алгоритм Adam, стандарт для нейромереж, поєднує імпульс з окремим кроком для кожного параметра. Це грубе наближення до стандартизації, яку ви вмикали галочкою.
Крок SGD має зменшуватися
Зі сталим кроком SGD вічно тремтить навколо мінімуму: шум градієнта не зникає. Щоб збігтися, крок зменшують так, щоб $\sum \eta_t = \infty$, але $\sum \eta_t^2 < \infty$ (умови Роббінса — Монро, 1951), наприклад $\eta_t \propto 1/t$. На практиці використовують розклади кроку (learning rate schedules) і усереднення параметрів.
Ridge мовою SVD
Якщо $A = U\Sigma V^\mathsf{T}$, то розв'язок ridge — $\hat{\boldsymbol\theta} = \sum_i \frac{\sigma_i}{\sigma_i^2 + \lambda}\,(\mathbf u_i^\mathsf{T}\mathbf y)\,\mathbf v_i$. Порівняйте з розділом 6: там було $1/\sigma_i$. Для великих $\sigma_i$ нічого не змінюється, а малі $\sigma_i$, які підсилювали шум, тепер «м'яко» гасяться множником $\sigma_i^2/(\sigma_i^2 + \lambda)$. Сума цих множників — ефективна кількість параметрів моделі.
Чому LASSO обнуляє коефіцієнти
Мінімізувати суму квадратів за обмеження $|\boldsymbol\theta|_1 \le c$ означає шукати, де еліпси рівня $S$ (розділ 3) уперше торкаються ромба L1 (розділ 2). Ромб має гострі кути на осях, і дотик найчастіше припадає саме на кут, де частина координат нульова. Коло L2 (ridge) кутів не має, тож коефіцієнти зменшуються, але не обнуляються.
Точка зламу
Найменша частка промахів, яка може зсунути оцінку як завгодно далеко, — точка зламу (breakdown point). У МНК і середнього вона дорівнює 0: одного промаху досить. У медіани — 50%. У Губера — теж 0 з погляду теорії (промах з великим важелем усе одно шкодить), хоча на практиці він значно стійкіший за МНК. RANSAC і методи на кшталт найменшої медіани квадратів (LMedS) витримують до 50%.
Надійність мережі за Баардою
Баарда поставив і обернене питання: який найменший промах тест гарантовано помітить (minimal detectable bias)? Відповідь залежить від $1 - h_{ii}$, частки виміру, що «потрапляє» в нев'язку. Якщо вимір майже нічим не контролюється ($h_{ii} \approx 1$, як у точки з великим важелем), промах у ньому може бути величезним і все одно непомітним. Геодезисти проєктують мережі так, щоб кожен вимір мав достатній контроль. Це повертає нас до надлишкових вимірів з розділу 1. Стійкі методи зрівнювання в геодезії теж є: «данський метод» Крарупа й Кубіка (1980-ті) — це по суті той самий IRLS.
10.7. Код
Python: градієнтний спуск з різними кроками, SGD, ridge, Губер (IRLS), RANSAC і покроковий тест Баарди. JavaScript: ті самі стійкі методи на прямій з двома промахами й перевірка межі стійкості кроку градієнтного спуску.
10.8. Перевірте себе
Найбільше власне число гессіана функції втрат $L = 10$. Яка межа кроку $\eta$, за якої спуск ще не розбігається?
Модель $y = \theta x$ без вільного члена, $\sum xy = 10$, $\sum x^2 = 10$. Яке $\hat\theta$ дає ridge з $\lambda = 10$?
Поріг Губера $\delta = 1$. Яку вагу в IRLS отримає точка з нев'язкою $r = 3$? (десятковим дробом)
Половина точок — промахи. Скільки спроб RANSAC (пар точок) потрібно, щоб з імовірністю 99% хоча б раз витягти пару без промахів? (ціле число)
Ми пройшли шлях від трьох вимірів рулеткою до градієнтного спуску, регуляризації й стійких методів. В останньому розділі зберемо все в шпаргалку, розв'яжемо кілька задач наскрізно й подивимося, куди рухатися далі: фільтр Калмана (МНК, що оновлюється з кожним новим виміром) і bundle adjustment (МНК на мільйонах невідомих).