Kernel Methods и RKHS

NTK теория 2018 года показала: бесконечно широкая нейросеть - это kernel machine. Это объяснило generalization paradox Zhang 2017 в новом свете. Google использует kernel methods в production (Gaussian Processes для hyperparameter optimization). SVM - стандарт для malware detection в Microsoft. Понять kernel = понять фундамент как classical ML, так и deep learning теории.

• **Gaussian Processes в Google Vizier:** Bayesian optimization для автоматического выбора hyperparameters в TensorFlow/JAX моделях. Prior = GP с RBF kernel.
• **SVM в malware detection:** Касперский, Microsoft Defender используют SVM с custom kernels на byte n-grams для классификации PE-файлов.
• **NTK и scaling laws:** Chinchilla scaling laws (DeepMind 2022) частично объясняются NTK теорией - предсказания потерь через kernel eigenspectrum.

Kernel trick: бесконечные feature maps без вычислений

**Бесконечно широкая нейросеть обучается как kernel machine.** Neural Tangent Kernel (NTK) теория 2018 года показала: при random initialization нейросеть в infinite-width limit - это kernel regression с фиксированным ядром. Понять kernel methods - значит понять предел нейросетей.

Kernel trick: для алгоритма, использующего только скалярные произведения ⟨φ(x), φ(x')⟩, не нужно явно вычислять φ(x). Достаточно функции k(x, x') = ⟨φ(x), φ(x')⟩. Если φ отображает в бесконечномерное пространство (polynomials всех степеней) - прямое вычисление невозможно. Kernel trick: O(n²) вместо O(n·∞).

**Популярные ядра и их feature maps:** **Polynomial kernel:** k(x,x') = (xᵀx' + c)^d φ(x) = все мономы степени ≤ d **RBF/Gaussian kernel:** k(x,x') = exp(-||x-x'||²/(2σ²)) φ(x) = бесконечномерный вектор (Taylor expansion exp) **Neural Tangent Kernel:** k_NTK(x,x') = E[∇_θf(x,θ)ᵀ·∇_θf(x',θ)] φ(x) = gradient нейросети по параметрам **Условие Mercer:** k - ядро ⟺ k симметрична и положительно полуопределена. ∀x₁,...,xₙ: матрица K, Kᵢⱼ=k(xᵢ,xⱼ), является PSD.

RKHS и representer theorem

**Reproducing Kernel Hilbert Space (RKHS)** - пространство функций H_k с нормой ||f||_k, определяемой ядром k. Ключевое свойство: f(x) = ⟨f, k(·,x)⟩_k для всех f ∈ H_k. Это «воспроизводящее» свойство. Минимизация потерь + ||f||² в H_k имеет точное конечномерное решение.

**Representer Theorem (Kimeldorf-Wahba 1971):** Пусть задача: min_{f ∈ H_k} [Σᵢ L(yᵢ, f(xᵢ)) + λ||f||²_k] Тогда оптимальное решение имеет вид: f*(x) = Σᵢ αᵢ·k(xᵢ, x) Только n функций k(xᵢ, ·) - независимо от размерности H_k! Подставляя в задачу: min_α [L(y, Kα) + λ·αᵀKα] где K - kernel matrix, Kᵢⱼ = k(xᵢ, xⱼ). Для ridge regression: α = (K + λI)⁻¹y Предсказание: f(x_new) = kᵀα = Σᵢ αᵢ·k(xᵢ, x_new)

Gaussian Processes - это Bayesian интерпретация kernel regression. Prior: f ~ GP(0, k). Posterior mean совпадает с kernel ridge regression с α = (K + σ²I)⁻¹y. Posterior variance даёт confidence intervals. Используется в Bayesian optimization (AutoML, hyperparameter tuning).

Neural Tangent Kernel: нейросети как kernel machines

**NTK теорема (Jacot-Gabriel-Hongler, 2018):** при random initialization и infinite width нейросеть обучается gradient descent, и kernel не меняется - это постоянный NTK K_∞(x,x'). В этом режиме нейросеть = kernel regression с NTK. Это объясняет часть double descent и generalization parадокса.

**Neural Tangent Kernel:** K_NTK(x,x') = Σ_l ⟨∇_θl f(x,θ), ∇_θl f(x',θ)⟩ где θl - параметры слоя l. При gradient descent обновление: dθ/dt = -∇_θ L = -Kᵀ(f(X,θ) - y) При infinite width: K_NTK фиксирован (не меняется в процессе обучения)! Это делает динамику линейной ODE с известным решением. **Практическое значение:** - Объясняет lazy training режим (маленький lr, большой width) - NTK kernel плохо аппроксимирует иерархические features - Реальные нейросети работают в feature learning режиме (меняют kernel) - Это разрыв между NTK теорией и практикой

Ключевые идеи

• **Kernel trick:** k(x,x') = ⟨φ(x),φ(x')⟩ - скалярное произведение в feature space без явного φ. RBF kernel: бесконечномерный φ, O(n²) вычисление.
• **Mercer condition:** k - ядро ⟺ матрица Грама K PSD для любых точек. Проверка: все eigenvalues ≥ 0.
• **Representer theorem:** оптимальная f в RKHS = Σᵢ αᵢ·k(xᵢ,·). Только n компонент! α = (K + λI)⁻¹y для kernel ridge regression.
• **NTK:** K_NTK(x,x') = Σ_l ⟨∇_θl f(x), ∇_θl f(x')⟩. При infinite width фиксирован. Нейросеть → kernel regression.
• **Gaussian Processes:** Bayesian интерпретация kernel regression. Posterior mean = KRR. Posterior variance = uncertainty. Применение: Bayesian optimization.

Связанные темы

Kernel methods - мост между классикой и deep learning:

• Generalization парадокс — NTK объясняет, почему overparameterized нейросети обобщают
• Boosting — Предыдущий урок: ансамблевые методы и margin theory

Связанные уроки

• lt-13-deep-generalization — NTK объясняет deep learning через kernel methods
• lt-04-vc-dimension — RKHS с бесконечной размерностью, но finite generalization
• lt-16-boosting — Оба объединяют слабые предсказатели в сильный