Численные методы
Численные методы на собеседовании
На system design в Meta: «Как посчитать обратную матрицу 10000x10000 эффективно?» Большинство кандидатов отвечают numpy.linalg.inv(). Правильный ответ: никогда не инвертировать явно - это O(n³) и численно нестабильно. Использовать Cholesky + solve. Такие вопросы проверяют numerical literacy уровня «production ML engineer».
- **Google:** катастрофическое сокращение в распределённом SGD - причина расхождений при data parallelism. Kahan summation в gradient accumulation.
- **Meta:** Число обусловленности матрицы эмбеддингов влияет на скорость сходимости. Poorly conditioned - добавить L2 или использовать LAMB optimizer.
- **NVIDIA:** недетерминированность CUDA из-за нарушения ассоциативности fp - причина, почему reproducibility в DL требует специальных мер.
IEEE 754: ловушки для senior-инженера
На system design в Meta: «Как посчитать обратную матрицу 10000x10000 эффективно?» Неправильный ответ: numpy.linalg.inv(). Правильный: никогда не инвертировать явно - использовать Cholesky decomposition и numpy.linalg.solve(). Такие вопросы проверяют, знает ли кандидат numerical analysis на уровне «работало в production».
**Катастрофическое сокращение** (catastrophic cancellation) - потеря значимых бит при вычитании близких чисел. Пример: a=1.000001, b=1.000000. Разность 1e-6. В fp32 оба числа имеют по 7 значащих цифр, но их разность имеет только 1 - остальные биты отданы под совпадающую часть.
**Machine epsilon:** наименьшее ε > 0 такое, что 1.0 + ε != 1.0 в данном формате. - fp32: ε ≈ 1.19 × 10⁻⁷ - fp64: ε ≈ 2.22 × 10⁻¹⁶ Правило IEEE 754: ассоциативность НЕ соблюдается. (a + b) + c ≠ a + (b + c) в общем случае. Именно поэтому результаты параллельных вычислений на GPU недетерминированы - порядок сложения разный.
Классическая ошибка на интервью: «Сравни два float на равенство через ==». Правильно: abs(a - b) < eps * max(abs(a), abs(b), 1.0). Формула из numpy.isclose: |a-b| <= atol + rtol * |b|.
Функция вычисляет дисперсию по формуле Var = E[X²] - E[X]². При каких данных это даёт неверный результат?
При x ≈ 10⁶ и σ≈1: E[X²]≈10¹² и E[X]²≈10¹². Разность двух близких больших чисел теряет значимые биты. Исправление: алгоритм Велфорда - вычисляет дисперсию онлайн без катастрофической отмены.
Число обусловленности: когда матрица «плохая»
**κ(A) = ||A|| · ||A⁻¹|| = σ_max / σ_min.** Это отношение наибольшего к наименьшему сингулярному значению. Смысл: при κ(A) = 10⁶ и fp64 (16 значащих цифр) решение Ax=b достоверно только до 10 цифр. При κ(A) = 10¹⁶ - система численно сингулярна.
Ridge regression (L2 регуляризация) - это не просто «предотвращение переобучения». Добавление λI к матрице Грама XᵀX гарантирует κ(XᵀX + λI) ≤ κ(XᵀX). При λ=1e-4 почти сингулярная матрица становится корректно обусловленной.
**Прямые vs итерационные solvers:** - Прямые (LU, Cholesky): O(n³), точное решение за один проход. Для n < 10000. - Итерационные (CG, GMRES): O(k·nnz) за k итераций, nnz - ненулевых элементов. Для разреженных систем n > 10000. - Conjugate Gradient для SPD матриц: сходится за k ≤ n итераций, на практике k ≪ n если κ мало. Используется в Google PageRank, physics simulators, FEM.
Нужно решить Ax=b: A - симметричная положительно-определённая матрица 5000×5000 с 99% нулей. Какой solver выбрать?
CG требует только матрично-векторных умножений O(nnz) за итерацию. Для СПД матриц сходится за O(√κ) итераций. LU на разреженной матрице создаёт fill-in, уничтожая разреженность.
NaN/Inf в продакшне: диагностика за 5 минут
Тренировка GPT-подобной модели падает с NaN на шаге 50000. Отладка занимает 2 дня или 20 минут - зависит от систематического подхода. Большинство NaN/Inf в DL имеют одну из пяти причин: overflow в softmax, log(0) в cross-entropy, деление на ноль в layer norm, gradient explosion, или Inf веса после Adam с неправильным lr.
| Симптом | Причина | Лечение |
|---|---|---|
| NaN на первом шаге | Слишком большой lr или неинициализированные веса | lr warmup, проверить инициализацию |
| NaN после N шагов | Gradient explosion или fp16 overflow | clip_grad_norm_(max=1.0) + GradScaler |
| Inf в loss | log(0) или softmax overflow | label smoothing, numerical stable cross-entropy |
| NaN только на GPU | Недетерминированные CUDA ops + bad conditioning | torch.use_deterministic_algorithms(True) для дебага |
| Loss = 0 внезапно | Gradient underflow в fp16 (denormals) | Включить GradScaler, перейти на bf16 |
Тренировка трансформера упала с NaN на шаге 80000. Каков первый шаг диагностики?
NaN распространяется через граф. Нужно найти источник: логировать grad norms для каждого слоя. Если NaN в градиентах раньше потери - проблема в backward. Если в loss - в forward (attention overflow, log(0) и т.д.).
Ключевые идеи
- **Catastrophic cancellation:** a-b при близких a,b теряет значимые биты. Двухпроходный алгоритм Уэлфорда для дисперсии, Kahan summation для больших сумм.
- **Machine epsilon fp64 = 2.22e-16:** ассоциативность не соблюдается, float == float через == - ошибка, использовать isclose.
- **κ(A) = σ_max/σ_min:** при κ=10^k решение Ax=b теряет k значимых цифр. Ridge (λI) улучшает κ.
- **Cholesky для SPD:** быстрее LU, численно стабильнее явного inv(). Для разреженных матриц - CG итерационный.
- **NaN диагностика:** register_forward_hook для per-layer detection. Порядок: lr -> инициализация -> gradient explosion -> fp16 overflow.
Связанные темы
Интервью вопросы по численным методам:
- Численные методы в ML — L-BFGS, рандомизированный SVD, смешанная точность - предыдущий урок с реализациями
- Метод Монте-Карло — Стохастические численные методы - следующий урок: MCMC, importance sampling