Линейные уравнения и ранг матрицы
От задачи о курицах и кроликах до обучения моделей ИИ — системы линейных уравнений повсюду. «Ранг» матрицы говорит нам, сколько действительно полезной информации содержится в системе.
Любую систему линейных уравнений можно записать в виде Ax = b
A — матрица коэффициентов (m уравнений, n неизвестных), x — вектор неизвестных, а b — вектор констант.
Например, задача о курицах и кроликах: \( \begin{cases} x+y=10 \\ 2x+4y=28 \end{cases} \), записанная в матричной форме:
\[ \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 10 \\ 28 \end{bmatrix} \]Ранг: количество независимых фрагментов информации
Ранг = количество действительно "независимых" строк (или столбцов) в матрице.
Если уравнение можно получить, умножив другие уравнения на коэффициенты, оно избыточно — оно не добавляет новой информации.
Ранг определяет варианты решений системы уравнений:
Полный ранг
Единственное решение
Нет избыточности среди уравнений
Неполный ранг
Бесконечно много решений
Есть избыточные уравнения
Противоречивая
Нет решения
Уравнения противоречат друг другу
Пример из реальной жизни
Задача о курах и кроликах: полный ранг, единственное решение
10 голов + 28 ног → 6 кур, 4 кролика. Два уравнения дают две независимые порции информации — ровно столько, сколько нужно, чтобы найти два неизвестных.
Избыточная информация: недостаточный ранг, бесконечно много решений
Уравнение 1: x + y = 5. Уравнение 2: 2x + 2y = 10 (это просто уравнение 1, умноженное на 2).
На самом деле эти два уравнения — это одна порция информации: существует бесконечно много пар (x, y), удовлетворяющих условию.
Математическое определение
Определение ранга
| Условие | Случаи решения |
|---|---|
| rank(A) = rank([A|b]) = n | Единственное решение |
| rank(A) = rank([A|b]) < n | Бесконечно много решений |
| rank(A) < rank([A|b]) | Нет решения |
Здесь [A|b] — расширенная матрица, полученная приписыванием b справа к A.
Практическое занятие по Python
Пример
# Курицы и кролики в одной клетке: полный ранг
A = np.array([[1,1],[2,4]])
b = np.array([10,28])
x = np.linalg.solve(A, b)
print("Решение:", x, "→ Курица=6, Кролик=4")
print("Ранг:", np.linalg.matrix_rank(A)) # 2 (полный ранг)
# Избыточное уравнение
A_red = np.array([[1,2],[2,4]]) # Строка 2 = 2 × Строка 1
print("\n"Ранг избыточной матрицы:", np.linalg.matrix_rank(A_red)) # 1
# Ранг случайной большой матрицы
big = np.random.randn(100, 50)
print("Ранг случайной матрицы 100×50:", np.linalg.matrix_rank(big)) # 50
解: [6. 4.] → 鸡=6, 兔=4 秩: 2(满秩) 冗余矩阵的秩: 1 100×50 随机矩阵的秩: 50
Сценарии применения в ИИ
Тонкая настройка LoRA = предположение о низком ранге
Основное предположение LoRA (Low-Rank Adaptation) состоит в том, что обновление тонкой настройки \Delta W предобученных весов имеет низкий ранг. Следовательно, полное обновление \Delta W = AB можно аппроксимировать произведением двух небольших матриц A (d×r) и B (r×d), где r << d.
Например, для 12288-мерной матрицы весов GPT-3 достаточно r = 8 или 16 — ранг падает с 12288 до 8, сокращая число параметров более чем в тысячу раз. Здесь используется понятие «ранга» для параметроэффективной тонкой настройки.
Обнаружение коллинеарности признаков
Если ранг матрицы данных намного меньше числа столбцов → среди признаков наблюдается высокая коллинеарность (мультиколлинеарность) → X^TX в линейной регрессии необратима или близка к вырожденной → требуется регуляризация (Ridge/Lasso) или снижение размерности (PCA). В реальных ML-проектах это проявляется как чрезмерно большое число обусловленности матрицы признаков.
Матричное пополнение в рекомендательных системах
Матрица оценок «пользователь–элемент» обычно содержит лишь несколько оценок (разреженная), но предполагается, что она порождена структурой низкого ранга (похожие пользователи имеют похожие вкусы). Матричное пополнение использует ограничения на ранг, чтобы восстановить пропущенные оценки по известным. Это основная идея алгоритма-победителя конкурса Netflix Prize.
Другие расширения