[Theory for AI] Линейная алгебра. Ортогонализация Грама-Шмидта
Представим, что у вас есть датасет с двумя переменными, которые почти линейно зависимы (так называемая коллинеарность). При обучении модели на таких данных можно столкнуться с переобучением или плохой обобщаемостью — например, одна из переменных может получить близкий к нулю вес. Как же заставить модель эффективно использовать всю информацию, содержащуюся в признаках? Ответ прост: проведите их ортогонализацию!
Введение
Одним из самых известных алгоритмов ортогонализации является процесс Грама–Шмидта, и именно его мы рассмотрим в этой статье, а также решим несколько задач на эту тему.
Что вообще означает ортогонализация? Это приведение системы векторов к ортогональному виду (обобщённое понятие перпендикулярности в n-мерных пространствах).
Нормировка же приводит каждый вектор к единичной длине (нормированный вектор).
Теперь, зная эти два понятия, можно описать процесс Грама–Шмидта: этот алгоритм приводит систему векторов к ортонормированному виду — то есть каждый вектор нормирован и ортогонален к остальным. Запишем это формально:
Пусть ${\overline{v}_1, \overline{v}_2, ..., \overline{v}_n} \in \mathbb{R}^m$ — линейно независимые векторы.
В результате алгоритма получаем систему ${\overline{u}_1, \overline{u}_2, ..., \overline{u}_n} \in \mathbb{R}^m$, такую что:
Ортогональность:
$$\forall i, j \in \overline{1, n},\ i \neq j: \quad \langle \overline{u}_i, \overline{u}_j \rangle\ =\ 0$$Нормированность:
$$\forall i \in \overline{1, n}: \quad \parallel \overline{u}_i \parallel\ =\ 1$$Порождают то же подпространство:
$$span(\overline{u}_1, ..., \overline{u}_n)\ =\ span(\overline{v}_1, ..., \overline{v}_n)$$
Да, третий пункт не входит в представленное мною определение, но он всегда выполняется: новые векторы лежат в том же пространстве, что и исходные.
Переходим к самому алгоритму:
Пусть
$$\overline{u}_1\ =\ \frac{\overline{v}_1}{\parallel \overline{v}_1 \parallel}$$Для каждого $i = 2, ..., n$:
Вычитаем из $\overline{v}_i$ проекции на все предыдущие $\overline{u}_j$:
$$ \overline{w}_i\ =\ \overline{v}_i\ -\ \sum_{j=1}^{i-1} proj_{\overline{u}_j}(\overline{v}_i) $$ где
$$ proj_{\overline{u}_j}(\overline{v}_i)\ =\ \frac{\langle \overline{v}_i, \overline{u}_j \rangle}{\langle \overline{u}_j, \overline{u}_j \rangle} \overline{u}_j $$Затем нормализуем:
$$ \overline{u}_i\ =\ \frac{\overline{w}_i}{\parallel \overline{w}_i \parallel} $$
Несколько важных замечаний:
- Нормировка в процессе Грама–Шмидта не обязательна. Без неё вы получите просто ортогональную систему.
- При работе с классическими векторами проекцию можно записать в матричном виде:
$$ proj_{\overline{u}}(\overline{v})\ =\ \frac{\overline{u}^T \overline{v}}{\overline{u}^T \overline{u}} \overline{u} $$ - Если в исходной системе есть линейно зависимые векторы, то алгоритм даст нулевой вектор, и его следует исключить, чтобы избежать деления на ноль.
Полезные свойства:
- Произведение норм векторов (до нормировки) равно объёму параллелепипеда, построенного на исходных векторах.
- Матрица перехода от исходной системы к ортогональной — верхнетреугольная.
Зачем всё это?
Во время ортогонализации мы, грубо говоря, “вытаскиваем” из вектора только уникальную информацию. Благодаря этому модель перестаёт “путаться” в признаках, которые на самом деле дублируют друг друга.
Задача
Даны два вектора $\overline{a}_1,\ \overline{a}_2 \in \mathbb{R}^n$. Покажите, что
$$ \overline{u}_1\ =\ \overline{a}_1, $$ $$ \overline{u}_2\ =\ \overline{a}_2\ -\ \frac{\overline{u}_1^T \overline{a}_2}{\overline{u}_1^T \overline{u}_1} \overline{u}_1 $$
образуют ортогональную систему.
Решение:
Вспомним: два вектора ортогональны, если их скалярное произведение равно нулю. Проверим это:
$$ \overline{u}_1^T \overline{u}_2\ =\ \overline{u}_1^T \left( \overline{a}_2\ -\ \frac{\overline{u}_1^T \overline{a}_2}{\overline{u}_1^T \overline{u}_1} \overline{u}_1 \right) $$ $$ =\ \overline{u}_1^T \overline{a}_2\ -\ \frac{\overline{u}_1^T \overline{a}_2}{\overline{u}_1^T \overline{u}_1} \cdot \overline{u}_1^T \overline{u}_1 $$ $$ =\ \overline{u}_1^T \overline{a}_2\ -\ \overline{u}_1^T \overline{a}_2\ =\ 0 $$
Что и требовалось доказать.
Отметим: если $\overline{a}_2\ =\ \alpha \overline{a}_1$, то:
$$ \overline{u}_2\ =\ \alpha \overline{a}_1\ -\ \frac{\alpha \overline{u}_1^T \overline{a}_1}{\overline{u}_1^T \overline{u}_1} \overline{u}_1\ =\ \alpha \overline{u}_1\ -\ \alpha \overline{u}_1\ =\ \overline{0} $$
То есть, если векторы линейно зависимы, второй вектор зануляется.
С точки зрения машинного обучения это означает, что он не содержит уникальной информации. Следовательно, такие признаки следует исключать — они только мешают модели.