Линейная алгебра: сложные вопросы интервью

На собеседовании в DeepMind спросили: почему для нейросетей SVD, а не EVD - если оба разлагают матрицу? Правильный ответ занял 4 минуты и потребовал знания численной устойчивости, применимости к прямоугольным матрицам и связи с condition number. Этот урок - 10 таких вопросов уровня senior ML.

• DeepMind, Google Brain: SVD vs EVD, condition number, LoRA - реальные вопросы 2023-2024
• OpenAI: почему attention O(n²) и как Flash Attention это решает - системный вопрос
• Meta AI: PCA vs LDA, когда что использовать - вопрос на понимание, не формулы
• Anthropic: связь между рангом матрицы весов и обобщающей способностью модели
• Quant finance: число обусловленности ковариационной матрицы в портфельной оптимизации

SVD vs EVD: численная устойчивость и применимость

EVD: $A = V\Lambda V^{-1}$ - только для квадратных матриц, $V$ может быть плохо обусловленным. SVD: $A = U\Sigma V^\top$ - для любых матриц, $U$ и $V$ всегда унитарны (число обусловленности = 1). Вычисление собственных значений через $A^\top A$ удваивает число обусловленности: $\kappa(A^\top A) = \kappa(A)^2$ - катастрофическая потеря точности для плохо обусловленных матриц.

**Почему SVD для нейросетей, не EVD**: веса $W \in \mathbb{R}^{m \times n}$ - прямоугольные ($m \neq n$). EVD неприменим. SVD даёт $\sigma_1$ (spectral norm) через power iteration за 1-2 шага. Для PCA: $X^\top X$ - матрица ковариации. Прямой SVD матрицы данных $X$ численно устойчивее и точнее чем EVD матрицы $X^\top X$.

Ранг, проекции и PCA vs LDA: торговые вопросы senior-уровня

Проектор на подпространство $\text{col}(A)$: $P = A(A^\top A)^{-1}A^\top$ (если $A$ полного ранга). Свойства: $P^2 = P$ (идемпотентность), $P^\top = P$ (симметричность). Ортогональный дополняющий проектор: $P_\perp = I - P$. Ранг матрицы = размерность пространства столбцов = число ненулевых сингулярных значений.

**PCA vs LDA**: оба снижают размерность, но PCA максимизирует дисперсию (unsupervised), LDA максимизирует разделимость классов (supervised). LDA: $\max_w \frac{w^\top S_B w}{w^\top S_W w}$ - обобщённая задача на собственные значения $S_B w = \lambda S_W w$. Решается через $S_W^{-1} S_B$ (если $S_W$ обратима). LDA даёт не более $C-1$ компонент ($C$ - число классов).

Упражнения

1. Почему в ML-задачах предпочитают SVD, а не EVD (разложение по собственным значениям)? — EVD: только для квадратных матриц; SVD: для любых m x n матриц - это фундаментальное различие; Матрица данных X в ML почти всегда прямоугольная (n samples x d features), EVD неприменима напрямую; EVD через A^T A требует квадратирования матрицы: kappa(A^T A) = kappa(A)^2 - удвоение потери точности; SVD вычисляет сингулярные значения напрямую, без квадратирования: численно в 2x стабильнее; PCA через SVD (scipy) vs через eigenvectors(X^T X) (устаревший способ) - поэтому sklearn использует SVD
2. Матрица A имеет condition number kappa = 10^8. Можно ли решить Ax = b через LU-разложение на float64? Что делать? — float64 имеет ~15-16 значимых десятичных цифр; kappa = 10^8 означает потерю 8 цифр; Оставшихся 7-8 цифр может хватить, но результат ненадёжен: малое изменение b дёт большое изменение x; Квантованная ошибка: если b имеет ошибку eps, то x имеет ошибку eps * kappa; Решение: SVD с порогом tau = eps_machine * sigma_max; сингулярные значения < tau обнуляются; Это псевдообращение (pinv): numpy.linalg.pinv делает именно это по умолчанию
3. Обратимая матрица W и численно нестабильная - это одно и то же? — Нет - это принципиально разные понятия; W = diag(1, 1e-15) обратима математически: det(W) = 1e-15 != 0; Численно: при нахождении W^{-1} b второй компонент умножается на 1e15 - усиление ошибки; kappa(W) = 1/1e-15 = 1e15 >> 1/eps_machine (~1e16): решение теряет все значащие цифры; Вывод: invertible != stable; для численной работы нужно kappa << 1/eps_machine

Упражнения

1. Почему LoRA использует rank r = 4-16 для GPT-3, а не r = 1 или r = 100? — r = 1: слишком мало свободы - все обновления в одном направлении, качество страдает; r = d: то же самое что полный fine-tuning - никакой экономии; Оптимальный r = intrinsic rank задачи: эмпирически 4-16 для большинства NLP задач; Проверка: обучить с r=1, 2, 4, 8, 16; смотреть validation loss plateau - это и есть intrinsic rank; Исключение: задачи с доменным сдвигом (code->math) требуют большего r, иногда 64-128
2. Матрица весов W ∈ R^{1000x1000} имеет rank 5. Сколько памяти нужно для хранения? Как это использовать? — Полная матрица: 1000 x 1000 = 1M параметров; Rank-5 хранение: 2 x (1000 x 5) + 5 = 10005 параметров -> сжатие в 100x; Умножение W @ x = U @ (S @ (V^T @ x)): три матвека вместо matmul: O(1000x5) вместо O(1000^2); Это basis of tensor decomposition: Tucker, TT разложения для 4D весов Conv слоёв; Проверка на практике: np.linalg.matrix_rank(W) < threshold -> применять SVD-сжатие

Упражнения

1. В чём принципиальное линейно-алгебраическое различие между PCA и LDA? — PCA: eigenvectors(X^T X) или SVD(X) - максимизирует дисперсию; unsupervised, нет меток; LDA: решает обобщённую задачу EVD: S_W^{-1} S_B v = lambda v, где S_W - within-class scatter, S_B - between-class; LDA максимизирует отношение межклассовой к внутриклассовой дисперсии (Fisher criterion); PCA может выбрать компоненты, не разделяющие классы; LDA гарантированно ищет разделяющие; Ограничение LDA: не более C-1 компонент (C = число классов) vs PCA: до d компонент
2. Почему определитель det(W) плохо подходит для ML задач, несмотря на то что он характеризует обратимость? — det(0.1 * I_{1000}) = 0.1^{1000} ~ 10^{-1000} - underflow в float64 (min ~= 5e-324); det зависит от масштаба: det(2A) = 2^n * det(A) - не инвариантен к нормировке данных; det = 0 только для точно вырожденных матриц; численно det ~ eps не говорит ничего конкретного; Лучше: matrix_rank(A) для вырожденности, kappa(A) для численной устойчивости; Исключение: det нужен в normalizing flows (log |det J| для change of variables)

Упражнения

1. Почему attention в трансформерах имеет сложность O(seq^2 * d), и как Flash Attention обходит ограничение по памяти? — Матрица S = QK^T имеет форму (seq, seq) - занимает O(seq^2) память (для seq=32K это 4 GB); Стандартный attention материализует S в HBM (глобальная память GPU) - узкое место по bandwidth; Flash Attention: блочное вычисление tiles в SRAM (быстрая память); softmax считается онлайн с rescaling; Online softmax: поддерживает running max и running sum; можно не хранить всю строку S; Результат: O(seq^2 * d) FLOPS (то же), но O(seq * d) по памяти - 5-10x ускорение на практике
2. Randomized SVD в sklearn использует O(m*n*k) вместо O(m*n*min(m,n)) для полного SVD. За счёт чего? — Randomized SVD (Halko et al. 2011): умножение Y = A * Omega ∈ R^{m x k} проецирует в k-мерное подпространство; Johnson-Lindenstrauss: случайная проекция сохраняет расстояния с вероятностью; k = O(log n / eps^2); QR(Y) = Q даёт ортобазис для range(A); затем B = Q^T A (k x n); SVD(B) - дешёвый этап; Полная сложность: O(m*n*k) - линейно по k вместо min(m,n); sklearn.utils.extmath.randomized_svd использует это для TruncatedSVD и PCA на разреженных матрицах

Упражнения

1. Ковариационная матрица Sigma всегда PSD (positive semi-definite). Почему - и что это означает для ML? — v^T Sigma v = E[(v^T(x-mu))^2] >= 0 - это дисперсия проекции на v, всегда неотрицательная; Значит все eigenvalues Sigma >= 0: PSD по определению через квадратичную форму; Численно: из-за ошибок округления Sigma может иметь tiny negative eigenvalues (~-1e-15); Фикс: Sigma = Sigma + eps * I (nugget regularization) или nearest_PSD через eigenvalue clipping; Cholesky требует строго PD: Sigma + eps*I гарантирует это; используется в Gaussian Processes

10 ключевых тезисов финального урока

• SVD > EVD в ML: работает с прямоугольными матрицами, не квадрирует condition number
• kappa(A) = sigma_max / sigma_min; при kappa >> 1/eps_machine решение теряет значимые цифры
• Invertible != stable: det(W) != 0 не гарантирует численную безопасность
• LoRA rank r = intrinsic dim задачи: эмпирически 4-16 для NLP; больше при доменном сдвиге
• det(A) - плохая мера в ML: underflow при n > 100, масштабозависимый; лучше rank и kappa
• PCA: EVD(X^T X) - unsupervised, max variance; LDA: S_W^{-1} S_B - supervised, max class separation
• Attention O(seq^2) память; Flash Attention: online softmax в SRAM tiles, O(seq*d) память
• Randomized SVD: проекция A*Omega на k-мерное подпространство; O(mnk) вместо O(mn*min(m,n))
• Ковариационная матрица PSD по построению; nearest_psd через eigenvalue clipping для Cholesky
• Сильный ответ на интервью - это trade-offs, а не формула; знание когда метод ломается

Весь курс за одним взглядом

Финальный урок замыкает курс. Каждый вопрос выше опирается на темы из предыдущих уроков.

• SVD разложение — Основа блока 1 (SVD vs EVD) и блока 2 (LoRA, randomized SVD)
• Спектральная теория графов — Блок про PageRank и GCN напрямую связан с eigenvectors Laplacian
• Линейная алгебра в глубоком обучении — Блок про attention и LoRA - прямое продолжение урока 34

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

• stat-09-regression