Ridge
Jak działa
Do funkcji straty najmniejszych kwadratów dodaje się człon kary α·Σwⱼ². Optymalizacja tego celu prowadzi do zmodyfikowanych równań normalnych, których rozwiązanie zamknięte to ŵ = (XᵀX + αI)⁻¹Xᵀy. Dodanie αI „podnosi grzbiet” (stąd nazwa) na diagonali macierzy XᵀX, gwarantując jej odwracalność i lepsze uwarunkowanie. Parametr α steruje kompromisem: dla α→0 estymator dąży do OLS, dla dużego α współczynniki są silnie kurczone w kierunku zera. Cechy powinny być wystandaryzowane, bo kara zależy od skali; wyrazu wolnego (intercept) zwykle się nie karze. Optymalne α dobiera się walidacją krzyżową (np. RidgeCV, uogólniona walidacja krzyżowa GCV).
Rozwiązany problem
Zwykła metoda najmniejszych kwadratów (OLS) daje estymatory o dużej wariancji, gdy cechy są silnie skorelowane (współliniowość) lub gdy macierz XᵀX jest bliska osobliwości bądź nieodwracalna (np. gdy liczba cech przekracza liczbę obserwacji). Prowadzi to do niestabilnych, przeuczonych modeli. Ridge rozwiązuje ten problem przez regularyzację L2, która stabilizuje odwracanie macierzy i ogranicza przeuczenie.
Komponenty
Parametryczny predyktor liniowy ŷ = Xw, którego współczynniki są estymowane z regularyzacją.
Człon regularyzacyjny karzący kwadrat normy euklidesowej współczynników, kurczący je w kierunku zera.
Oficjalna
Rozwiązanie zmodyfikowanych równań normalnych ŵ = (XᵀX + αI)⁻¹Xᵀy.
Oficjalna
Implementacja
Kara L2 zależy od skali cech; bez standaryzacji cechy o dużych wartościach są słabiej regularyzowane.
Włączenie interceptu do kary wprowadza błąd zależny od przesunięcia celu.
Zbyt małe α nie ogranicza przeuczenia, zbyt duże powoduje niedouczenie.
Ewolucja
Andriej Tichonow formułuje metodę regularyzacji problemów źle postawionych — matematyczny odpowiednik Ridge.
Dwa artykuły w Technometrics wprowadzają regresję grzbietową w statystyce i jej zastosowania do problemów nieortogonalnych.
Robert Tibshirani wprowadza Lasso, dające rozwiązania rzadkie — kontrast dla proporcjonalnego kurczenia Ridge.
Zou i Hastie łączą kary L1 i L2, godząc rzadkość Lasso ze stabilnością Ridge.
Hiperparametry (konfigurowalne osie)
Nieujemny współczynnik kary L2; kontroluje kompromis obciążenie–wariancja. α→0 zbliża do OLS, duże α silnie kurczy współczynniki.
Algorytm rozwiązania: dekompozycja SVD/Cholesky, lsqr, sparse_cg, sag/saga, lbfgs.
Ridge nie jest niezmiennicza względem skali cech; standaryzacja jest zwykle konieczna dla sensownej regularyzacji.
Czy dopasować i (zwykle) nie karać wyrazu wolnego.
Złożoność obliczeniowa
Złożoność czasowa: O(n · d²). Złożoność przestrzenna: O(d²).
Wąskie gardło obliczeniowe
Głównym kosztem jest rozwiązanie układu równań normalnych z regularyzowaną macierzą d×d.
Paradygmat wykonania
Wszystkie współczynniki są aktywne w każdej predykcji; brak routingu czy warunkowej aktywacji.
Równoległość
Operacje gęstej algebry liniowej (mnożenie macierzy, faktoryzacja, iloczyn skalarny przy predykcji) dobrze się zrównoleglają w bibliotekach BLAS/LAPACK.
Wymagania sprzętowe
Algorytm oparty na podstawowej algebrze liniowej działa na dowolnym sprzęcie.
Dla małych i średnich zbiorów CPU z BLAS/AVX jest w pełni wystarczające.
GPU przyspiesza operacje macierzowe przy bardzo dużych danych.