Алгебра
Алгебра на собеседовании
На ML-интервью в Google, Meta, Apple звучат вопросы: 'Объясните PCA через SVD', 'Почему LoRA работает?', 'Что такое Якобиан нейросети?'. Это не теория ради теории - это язык, на котором думают исследователи и старшие инженеры. Этот урок - данный финальный прогон перед loop.
- **Google Brain/DeepMind:** типичный вопрос - 'Выведите gradient descent через Якобиан и объясните почему Adam быстрее SGD через обусловленность матрицы Гессиана'
- **Meta AI Research:** 'Как LoRA уменьшает число параметров? Почему rank-4 работает для матриц 4096×4096?' - проверяет понимание low-rank аппроксимации через SVD
- **Apple ML:** 'Реализуйте PCA без sklearn' - стандартный coding вопрос, проверяющий знание thin SVD, центрирования данных и интерпретации главных компонент
Предварительные знания
Ранг, обратимость и системы уравнений
Google использует SVD-разложение матриц 100M×100M для PageRank - ранг матрицы непосредственно ограничивает качество поиска. Классические вопросы на собеседовании: чему равен rank(AB)? Когда обратима матрица? Что такое ранг произведения? Ключевые факты: rank(AB) ≤ min(rank A, rank B); матрица обратима тогда и только тогда, когда det ≠ 0, все λᵢ ≠ 0, rank = n, нулевое пространство просто.
**Теорема о ранге-дефекте (rank-nullity):** rank(A) + nullity(A) = n для A ∈ ℝ^{m×n}. Следствие: если rank(A) < n, то Ax = 0 имеет ненулевое решение, и система Ax = b либо несовместна, либо имеет бесконечно много решений.
На собеседовании: 'матрица обратима' - это 5 эквивалентных условий одновременно: det ≠ 0, все λᵢ ≠ 0, столбцы линейно независимы, rank = n, Ax = 0 только при x = 0. Знание всех связей показывает глубину понимания.
Матрицы A ∈ ℝ^{5×3} и B ∈ ℝ^{3×5}. Чему равен rank(AB)?
Собственные значения: быстрое рассуждение
Типичные вопросы на FAANG-интервью: чему равна сумма и произведение собственных значений? Как изменятся λ при сдвиге A → A + cI? Каков максимум xᵀAx при ‖x‖=1? Ответы: tr(A) = Σλᵢ; det(A) = Πλᵢ; λᵢ(A+cI) = λᵢ(A) + c; max xᵀAx = λ_max.
**Регуляризация Тихонова:** добавление λI к матрице (A + λI) увеличивает все собственные значения на λ, делая матрицу обратимой и улучшая число обусловленности. В ML - это ridge regression (L2-регуляризация): (AᵀA + λI)x = Aᵀb.
Симметричная матрица A имеет собственные значения 1, 4, 9. Чему равен max‖x‖₌₁ xᵀAx?
ML-вопросы: PCA, SVD и градиенты
Топовые ML-вопросы: объясните PCA через SVD, как SVD используется в рекомендательных системах, почему gradient - линейное отображение, как Якобиан связан с chain rule? Эти вопросы проверяют связь между линейной алгеброй и глубоким обучением.
**PCA vs SVD:** sklearn.PCA внутри использует randomized SVD (алгоритм Halko-Martinsson-Tropp) вместо полного SVD, так как он работает за O(mnk) вместо O(mn·min(m,n)). Для k ≪ min(m,n) это даёт 10-100× ускорение на больших матрицах данных.
PCA для матрицы данных X (n×d, центрированной) - что такое главные компоненты?
Быстрое рассуждение о форматах матриц
На интервью часто задают вопросы о форматах: 'Какой shape у Якобиана?', 'Что такое тонкий SVD?', 'Как изменится сложность если добавить батч?'. Умение мгновенно рассуждать о размерностях - ключевой навык.
| Вопрос | Быстрый ответ |
|---|---|
| rank(AᵀA) = ? | rank(A) - AᵀA и A имеют одинаковый ранг |
| Якобиан f: ℝⁿ → ℝᵐ? | Матрица (m×n): J[i,j] = ∂fᵢ/∂xⱼ |
| Thin SVD для A(m×n), m>n? | U(m×n), Σ(n×n), Vᵀ(n×n) |
| λ(AᵀA) = ? | σᵢ²(A) - квадраты сингулярных значений |
| Когда AᵀA обратима? | Когда rank(A) = n (полный столбцовый ранг) |
| Число обусловленности? | κ = σ_max/σ_min; κ >> 1 → нестабильность |
Стратегия для вопросов о собственных значениях/ранге: сначала проверь симметрию (если A симметрична - используй eigh, не eig), потом знак собственных значений (PSD, indefinite?), затем связь с SVD через σᵢ = √λᵢ(AᵀA). Три шага - 80% вопросов.
Для A ∈ ℝ^{m×n} (m > n, полный ранг), чему равны собственные значения AᵀA?
Ключевые идеи
- **Ранг и обратимость:** rank(AB) ≤ min(rank A, rank B); A обратима ↔ det≠0 ↔ все λᵢ≠0 ↔ rank=n; rank-nullity: rank + nullity = n
- **Трюки с собственными значениями:** tr(A)=Σλᵢ, det(A)=Πλᵢ; λ(A+cI)=λ(A)+c; max xᵀAx при ‖x‖=1 равен λ_max (число Рэлея)
- **PCA через SVD:** главные компоненты = правые сингулярные векторы V; λᵢ(XᵀX) = σᵢ²(X); PCA via SVD устойчивее чем через ковариационную матрицу
- **Быстрые facts:** Якобиан f:ℝⁿ→ℝᵐ имеет shape (m,n); thin SVD для A(m×n): U(m×n); λᵢ(AᵀA)=σᵢ²(A); κ=σ_max/σ_min
Связанные темы
Этот урок синтезирует весь курс линейной алгебры:
- SVD — PCA, псевдообратная, LoRA-понимание SVD критично для 80% ML-вопросов на интервью
- Собственные значения и векторы — Характеристический полином, степенная итерация, PageRank-фундамент вопросов об оптимизации
- Линейная алгебра в ML и Graphics — Практические применения (attention, einsum, MVP)-контекст для ML-вопросов
Вопросы для размышления
- На интервью звучит вопрос: 'PCA через SVD и PCA через eigendecomposition ковариационной матрицы дают одинаковый результат. В чём числовое различие?' Как бы прозвучал ответ?
- Вопрос: 'Нейросеть f: ℝⁿ → ℝᵐ с весами θ. Что такое Якобиан ∂f/∂x и ∂f/∂θ? Как они связаны с chain rule при backprop?'
- LoRA ограничивает обновление весов матрицами rank r. Как бы объяснили интервьюеру: почему для задачи файнтюнинга LLM на специфической задаче rank 4-16 достаточен, хотя размер матриц 4096×4096?