Линейная алгебра
Процесс Грама-Шмидта: фабрика ортогональных базисов
Ортогональный базис - это система координат без корреляций. В ортогональном базисе проекция на подпространство становится простой суммой, а численные вычисления теряют точность намного медленнее. Gram-Schmidt строит такой базис из любого набора векторов - именно это происходит внутри QR-разложения.
- QR-разложение: модифицированный Gram-Schmidt - численно стабильная версия для production
- Нейросети: ортогональная инициализация весов - снижает затухание/взрывные градиенты
- Биоинформатика: ортогонализация факторов в факторном анализе геномных данных
- Signal processing: базис Фурье - ортогональный; DFT проецирует сигнал на синусоиды
- Численные методы: предобусловливание Крылов-методов через ортогонализацию
Процесс Грама-Шмидта: алгоритм
**numpy.linalg.qr - одна из самых вызываемых функций в научном Python.** За ней стоит одна идея: взять произвольные векторы и сделать их строго перпендикулярными, не меняя то пространство, которое они натягивают. Эта идея - процесс Грама-Шмидта - появилась в 1880-х, но прямо сейчас работает внутри `torch.nn.init.orthogonal_` при инициализации нейросетей, в QR-итерационном методе нахождения собственных значений и в ZCA-whitening для декорреляции признаков.
**О чём этот урок на самом деле**: не просто алгоритм на бумаге, а способ думать об ортогональности как инструменте. После урока станет понятно, почему ортогональные матрицы так любят в ML - и как из "кривых" векторов получить идеальный базис за один проход.
Зачем вообще нужна ортогональность
Ортогональный базис - это когда все базисные векторы попарно перпендикулярны: **e_i · e_j = 0** при i ≠ j. Если ещё и длины единичные - называется ортонормированным. Почему это ценно?
| Операция | Произвольный базис | Ортонормированный базис |
|---|---|---|
| Найти координаты вектора v | Решить систему уравнений | Просто dot product: cᵢ = v · eᵢ |
| Вычислить норму | Через матрицу Грама | ||v||² = c₁² + c₂² + ... (Пифагор) |
| Обратная матрица | Алгоритм Гаусса-Жордана | Q⁻¹ = Qᵀ (просто транспонировать!) |
| Число обусловленности | Может быть огромным | κ(Q) = 1 (идеально устойчива) |
**Ключевой факт**: для ортогональной матрицы Q выполняется Q⁻¹ = Qᵀ. Транспонирование - бесплатная операция. Поэтому в численном ML всё, что можно, стараются выражать через ортогональные матрицы.
Идея метода: вычитать лишнее
Возьмём два вектора v₁ и v₂, которые не перпендикулярны. Хочется получить из них пару e₁, e₂ такую, что e₁ · e₂ = 0. Идея проста: оставить v₁ как есть, а из v₂ **вычесть его проекцию на v₁**. Что останется - будет перпендикулярно v₁.
ПРОЕКЦИЯ вектора v на направление u: proj_u(v) = (v · u / u · u) · u Это часть v, смотрящая в сторону u. ВЫЧИТАНИЕ проекции: u₂ = v₂ - proj_u₁(v₂) Получаем вектор, перпендикулярный u₁. ПРОВЕРКА: u₁ · u₂ = u₁ · (v₂ - proj_u₁(v₂)) = u₁ · v₂ - u₁ · (v₂·u₁/u₁·u₁)·u₁ = u₁ · v₂ - (v₂·u₁) · 1 = 0 ✓
Алгоритм Грама-Шмидта: шаг за шагом
Для n векторов v₁, ..., vₙ алгоритм строит ортонормированный набор e₁, ..., eₙ, покрывающий то же подпространство. Каждый следующий вектор очищается от всех проекций на уже построенные:
ШАГ 1: u₁ = v₁ ШАГ k (k = 2, 3, ..., n): uₖ = vₖ - sum_{j=1}^{k-1} proj_{u_j}(vₖ) где proj_{u_j}(vₖ) = (vₖ · uⱼ) / (uⱼ · uⱼ) · uⱼ НОРМИРОВАНИЕ: eₖ = uₖ / ||uₖ|| РЕЗУЛЬТАТ: e₁, ..., eₙ - ортонормированный базис eᵢ · eⱼ = 0 при i ≠ j ||eᵢ|| = 1
Числовой пример в R³
Возьмём три вектора и построим из них ортонормированный базис:
ИСХОДНЫЕ ВЕКТОРЫ: v₁ = (1, 1, 0) v₂ = (1, 0, 1) v₃ = (0, 1, 1) ШАГ 1: u₁ = v₁ = (1, 1, 0) e₁ = u₁ / ||u₁|| = (1, 1, 0) / √2 = (0.707, 0.707, 0) ШАГ 2: proj_{u₁}(v₂) = (v₂ · u₁)/(u₁ · u₁) · u₁ = (1·1 + 0·1 + 1·0) / (1+1+0) · (1,1,0) = 1/2 · (1, 1, 0) = (0.5, 0.5, 0) u₂ = v₂ - proj = (1,0,1) - (0.5, 0.5, 0) = (0.5, -0.5, 1) e₂ = u₂/||u₂|| = (0.5,-0.5,1)/√1.5 = (0.408, -0.408, 0.816) ШАГ 3: proj_{u₁}(v₃) = (0·1+1·1+1·0)/2 · (1,1,0) = (0.5, 0.5, 0) proj_{u₂}(v₃) = (0·0.5+1·(-0.5)+1·1)/1.5 · (0.5,-0.5,1) = 0.5/1.5 · (0.5,-0.5,1) = (0.167, -0.167, 0.333) u₃ = (0,1,1) - (0.5,0.5,0) - (0.167,-0.167,0.333) = (-0.667, 0.667, 0.667) e₃ = u₃/||u₃|| = (-0.577, 0.577, 0.577) ПРОВЕРКА: e₁·e₂ = 0.707·0.408 + 0.707·(-0.408) + 0·0.816 = 0 ✓
Какова основная идея процесса Грама-Шмидта?
Алгоритм: u_k = v_k - sum_{j<k} (v_k · q_j) q_j, затем q_k = u_k / ‖u_k‖. Каждый q_k ортогонален всем предыдущим по построению. Это даёт ортонормированный базис того же подпространства, что натянуто на v_1,...,v_n.
Численная устойчивость и модифицированный алгоритм
Численная нестабильность - и модифицированный алгоритм
Классический Грам-Шмидт математически верен, но на практике накапливает **ошибки округления**: при большом числе векторов результирующие векторы перестают быть строго перпендикулярными. Модифицированная версия - та же математика, другой порядок операций - решает проблему.
Если входные векторы почти линейно зависимы - оба алгоритма дают плохие результаты. В таких случаях используют **отражения Хаусхолдера** (именно они стоят за `numpy.linalg.qr` в продакшне). Хаусхолдер и модифицированный Грам-Шмидт дают одну и ту же матрицу Q, но Хаусхолдер устойчивее при плохо обусловленных системах.
Связь с QR-разложением
Процесс Грама-Шмидта - это и есть QR-разложение. Матрица Q содержит ортонормированные векторы e₁, ..., eₙ. Матрица R содержит коэффициенты проекций - то есть "координаты" исходных векторов в новом базисе:
Q - матрица с ортонормированными столбцами (Q^T Q = I) R - верхнетреугольная матрица коэффициентов R_{ij} = <v_j, e_i> (проекция j-го вектора на i-й базисный) ПРИМЕР: [v₁ | v₂ | v₃] = [e₁ | e₂ | e₃] · R [<v₁,e₁> <v₂,e₁> <v₃,e₁>] R = [ 0 <v₂,e₂> <v₃,e₂>] [ 0 0 <v₃,e₃>] R - верхнетреугольная, потому что каждый eₖ ортогонален ко всем предыдущим vⱼ (j < k) - их проекции уже вычтены.
Чем модифицированный Грам-Шмидт лучше классического?
Классический Грам-Шмидт вычитает все проекции из v_k одновременно; ошибки округления накапливаются и q_k теряют ортогональность. Модифицированный вычитает проекцию на q_j из текущего остатка сразу же, что даёт значительно лучшую численную устойчивость на близких к зависимым векторах.
Применения: QR, инициализация, ZCA-whitening
ML-применение №1: ортогональная инициализация нейросетей
При инициализации весов нейросети случайными числами возникает проблема: при глубоких сетях сигнал либо взрывается (gradient explosion), либо гаснет (vanishing gradient). **Ортогональная инициализация** - один из лучших способов её избежать: матрица весов инициализируется как случайная ортогональная матрица.
**Почему это работает**: у ортогональной матрицы W все сингулярные значения равны 1. Это значит, что при прямом проходе ||W·x|| = ||x|| - норма сигнала не меняется. Gradient vanishing / explosion возникает именно от многократного масштабирования сигнала, и ортогональность его устраняет.
ML-применение №2: QR-итерация для собственных значений
Один из самых быстрых численных методов нахождения всех собственных значений матрицы - **QR-алгоритм** - буквально многократно применяет QR-разложение. Он лежит в основе `numpy.linalg.eig`, LAPACK, MATLAB и почти всех научных вычислений с матрицами.
ИДЕЯ: последовательность матриц Aₖ сходится к верхнетреугольной, на диагонали которой - собственные значения. АЛГОРИТМ: A₀ = A для k = 0, 1, 2, ... Aₖ = Qₖ · Rₖ (QR-разложение) A_{k+1} = Rₖ · Qₖ (ПЕРЕСТАВИТЬ Q и R местами!) Схождение: A₀ → A₁ → A₂ → ... → верхнетреугольная На диагонали: λ₁, λ₂, ..., λₙ ПОЧЕМУ РАБОТАЕТ: умножение на Qₖ справа и слева - ортогональное подобие (А = Q·R → R·Q = Q^T·A·Q), поэтому собственные значения не меняются, но матрица постепенно "треугольнеет".
ML-применение №3: ZCA-whitening через ортогональный базис
В обработке изображений и нормализации признаков широко применяется **ZCA whitening** (Zero-phase Component Analysis). Он декоррелирует пиксели / признаки и используется как предобработка перед PCA, ICA, а в Computer Vision - для улучшения обучаемости CNN. Суть - найти ортогональный базис, выровнять дисперсии, вернуться обратно.
**Ортогональный базис - главный инструмент ZCA**: матрица eigenvectors содержит ортонормированные направления максимальной дисперсии. Это ровно то, что строит Грам-Шмидт - только здесь его применяет `np.linalg.eigh` автоматически.
Gram-Schmidt в дикой природе
**Где Грам-Шмидт и QR работают прямо сейчас** - **Инициализация нейросетей**: torch.nn.init.orthogonal_. Предотвращает vanishing/exploding gradients в глубоких сетях (RNN, ResNet) - **Численные методы собственных значений**: QR-итерация - основа numpy.linalg.eig, LAPACK. PCA, спектральная кластеризация, PageRank - всё через собственные значения - **QR-разложение для систем**: numpy.linalg.qr → устойчивое решение Ax = b. Численно устойчивее LU при плохо обусловленных матрицах - **ZCA whitening / декорреляция**: Предобработка перед PCA, ICA, CNN. Natural image statistics whitening для улучшения обучаемости моделей - **Ортогональные полиномы**: Базис Лежандра, Чебышёва, Эрмита. Гауссова квадратура, spectral methods в решении дифференциальных уравнений - **Позиционные эмбеддинги (Transformer)**: Rotary Position Embedding (RoPE). Ортогональные вращения в RoPE - в LLaMA, GPT-4 и большинстве современных LLM
Что унести из урока
- **Грам-Шмидт** = итеративно вычитать проекции: uₖ = vₖ - Σ proj_{u_j}(vₖ)
- **Ортонормированный базис** даёт Q⁻¹ = Qᵀ, κ(Q) = 1 - идеальная численная устойчивость
- **QR-разложение** - это Грам-Шмидт в матричной форме: A = Q·R, где Q ортогональна, R верхнетреугольна
- **numpy.linalg.qr** использует Хаусхолдера, не Грам-Шмидта - устойчивее при плохо обусловленных матрицах
- **Ортогональная инициализация** (torch.nn.init.orthogonal_) предотвращает vanishing gradients в глубоких сетях
- **QR-итерация** = многократное QR-разложение - основа численного нахождения собственных значений
- **ZCA whitening** = ортогональный базис + нормализация дисперсии - предобработка для PCA и CV
Связи
Грам-Шмидт - точка пересечения геометрии, численных методов и ML
- Скалярное произведение — Формула проекции основана на dot product - без него нет Грама-Шмидта
- Собственные векторы и диагонализация — QR-итерация - основной числовой метод нахождения собственных значений
- SVD (сингулярное разложение) — SVD обобщает QR на прямоугольные матрицы; pinv строится через SVD
- Обратная матрица — Для ортогональных матриц Q⁻¹ = Qᵀ - самый дешёвый случай обращения