22.2. Собственные разложения¶
Собственные значения — одно из самых полезных понятий, с которыми мы встретимся при изучении линейной алгебры, однако новичкам легко недооценить их важность. Ниже мы вводим спектральное разложение и пытаемся объяснить, почему оно так важно.
Предположим, что у нас есть матрица \(A\) со следующими элементами:
Если мы применим \(A\) к любому вектору \(\mathbf{v} = [x, y]^\top\), мы получим вектор \(\mathbf{A}\mathbf{v} = [2x, -y]^\top\). Это имеет интуитивное объяснение: растянем вектор так, чтобы он стал в два раза шире в направлении \(x\), а затем отразим его в направлении \(y\).
Однако есть векторы, для которых направление остаётся неизменным. А именно \([1, 0]^\top\) переходит в \([2, 0]^\top\), а \([0, 1]^\top\) — в \([0, -1]^\top\). Эти векторы по-прежнему лежат на тех же прямых, и единственное изменение заключается в том, что матрица растягивает их в \(2\) и \(-1\) раз соответственно. Такие векторы называются собственными векторами, а множители растяжения — собственными значениями.
В общем случае, если мы можем найти число \(\lambda\) и вектор \(\mathbf{v}\) такие, что
Мы говорим, что \(\mathbf{v}\) — собственный вектор, а \(A\) и \(\lambda\) — собственные значения.
22.2.1. Нахождение собственных значений¶
Давайте разберёмся, как их найти. Вычтя \(\lambda \mathbf{v}\) из обеих частей и вынеся вектор за скобки, мы видим, что приведённое выше выражение эквивалентно:
Чтобы (22.2.3) имело место, мы видим, что \((\mathbf{A} - \lambda \mathbf{I})\) должно сжимать какое-то направление до нуля, следовательно, оно необратимо, а значит, его определитель равен нулю. Таким образом, мы можем найти собственные значения, определив, для каких \(\lambda\) выполняется условие \(\det(\mathbf{A}-\lambda \mathbf{I}) = 0\). Найдя собственные значения, мы можем решить \(\mathbf{A}\mathbf{v} = \lambda \mathbf{v}\), чтобы найти соответствующие собственные векторы.
22.2.1.1. Пример¶
Рассмотрим это на более сложной матрице
Рассмотрим \(\det(\mathbf{A}-\lambda \mathbf{I}) = 0\). Мы видим, что это эквивалентно полиномиальному уравнению \(0 = (2-\lambda)(3-\lambda)-2 = (4-\lambda)(1-\lambda)\). Следовательно, два собственных значения равны \(4\) и \(1\). Чтобы найти соответствующие им векторы, необходимо решить
Мы можем решить эту задачу с помощью векторов \([1, -1]^\top\) и \([1, 2]^\top\) соответственно.
Мы можем проверить это в коде с помощью встроенной numpy.linalg.eig.
%matplotlib inline
import torch
from IPython import display
from d2l import torch as d2l
torch.linalg.eig(torch.tensor([[2, 1], [2, 3]], dtype=torch.float64))
Обратите внимание, что numpy нормирует собственные векторы так,
чтобы их длина была равна единице, тогда как мы брали собственные
векторы произвольной длины. Кроме того, выбор знака является
произвольным. Однако вычисленные векторы параллельны тем, которые мы
нашли вручную, и соответствуют тем же собственным значениям.
22.2.2. Разложение матриц¶
Продолжим предыдущий пример на один шаг дальше. Пусть
Пусть \(\mathbf{A}\) — матрица, столбцы которой являются собственными векторами матрицы. Пусть
— матрица, на диагонали которой расположены соответствующие собственные значения. Тогда определение собственных значений и собственных векторов говорит нам, что ⟦N⟧
Матрица \(W\) обратима, поэтому мы можем умножить обе части справа на \(W^{-1}\), и тогда получим, что
В следующем разделе мы рассмотрим несколько интересных следствий этого, но пока нам достаточно знать, что такая декомпозиция существует, если мы можем найти полный набор линейно независимых собственных векторов (так что \(W\) обратима).
22.2.3. Операции с собственными разложениями¶
Одним из преимуществ собственных разложений (22.2.9) является то, что многие операции, с которыми мы обычно сталкиваемся, можно аккуратно выразить через собственное разложение. В качестве первого примера рассмотрим:
Это означает, что для любой положительной степени матрицы её собственное разложение получается возведением собственных значений в ту же степень. То же самое верно и для отрицательных степеней, поэтому, если нам нужно обратить матрицу, достаточно рассмотреть
или, иными словами, просто инвертировать каждое собственное значение. Это сработает до тех пор, пока каждое собственное значение не равно нулю, поэтому мы видим, что обратимость эквивалентна отсутствию нулевых собственных значений.
Действительно, дополнительные выкладки показывают, что если \(\lambda_1, \ldots, \lambda_n\) — собственные значения матрицы, то определитель этой матрицы равен
или произведению всех собственных значений. Это интуитивно понятно, поскольку любое растяжение, выполняемое \(\mathbf{W}\), \(W^{-1}\) обращает в обратное, так что в итоге остаётся лишь растяжение, осуществляемое умножением на диагональную матрицу \(\boldsymbol{\Sigma}\), которое увеличивает объёмы в произведение диагональных элементов.
Наконец, вспомним, что ранг — это максимальное количество линейно независимых столбцов матрицы. При внимательном рассмотрении собственноразложения можно увидеть, что ранг равен числу ненулевых собственных значений \(\mathbf{A}\).
Примеры можно продолжать, но, надеемся, суть ясна: собственное разложение позволяет упростить многие вычисления линейной алгебры и является фундаментальной операцией, лежащей в основе многих численных алгоритмов и значительной части анализа, проводимого в линейной алгебре.
22.2.4. Собственные разложения симметричных матриц¶
Не всегда возможно найти достаточное количество линейно независимых собственных векторов, чтобы описанный выше процесс работал. Например, матрица
имеет только один собственный вектор, а именно \((1, 0)^\top\). Для работы с такими матрицами требуются более сложные методы, чем те, которые мы можем рассмотреть (например, жорданова нормальная форма или сингулярное разложение). Мы будем часто ограничивать наше внимание матрицами, для которых можно гарантировать существование полного набора собственных векторов.
Наиболее часто встречающимся семейством являются симметричные матрицы, то есть такие матрицы, где \(\mathbf{A} = \mathbf{A}^\top\). В этом случае мы можем выбрать \(W\) в качестве ортогональной матрицы — матрицы, столбцы которой являются единичными векторами, взаимно перпендикулярными друг другу, где \(\mathbf{W}^\top = \mathbf{W}^{-1}\), — и все собственные значения будут действительными. Таким образом, в этом частном случае мы можем записать (22.2.9) как
22.2.5. Теорема о кругах Гершгорина¶
Интуитивно понять собственные значения часто бывает сложно. Если дана произвольная матрица, то без их вычисления мало что можно сказать о том, какими они являются. Однако существует одна теорема, которая позволяет хорошо оценить их, если наибольшие значения находятся на диагонали.
Пусть \(\mathbf{A} = (a_{ij})\) — произвольная квадратная матрица (\(n\times n\)). Определим \(r_i = \sum_{j \neq i} |a_{ij}|\). Пусть \(\mathcal{D}_i\) обозначает круг на комплексной плоскости с центром \(a_{ii}\) и радиусом \(r_i\). Тогда каждое собственное значение \(\mathbf{A}\) принадлежит одному из \(\mathcal{D}_i\).
Это может быть неочевидным, поэтому рассмотрим пример. Пусть задана матрица:
У нас есть \(r_1 = 0.3\), \(r_2 = 0.6\), \(r_3 = 0.8\) и \(r_4 = 0.9\). Матрица симметрична, поэтому все собственные значения вещественны. Это означает, что все собственные значения будут находиться в одном из диапазонов
Численные вычисления показывают, что собственные значения приблизительно равны \(0.99\), \(2.97\), \(4.95\), \(9.08\), и все они находятся в пределах указанных диапазонов.
A = torch.tensor([[1.0, 0.1, 0.1, 0.1],
[0.1, 3.0, 0.2, 0.3],
[0.1, 0.2, 5.0, 0.5],
[0.1, 0.3, 0.5, 9.0]])
v, _ = torch.linalg.eig(A)
v
Таким образом, собственные значения можно аппроксимировать, и эти аппроксимации будут достаточно точными в случае, когда диагональные элементы значительно превышают все остальные.
Это мелочь, но при изучении такой сложной и тонкой темы, как собственное разложение, полезно иметь любое интуитивное понимание, которое мы можем обрести.
22.2.6. Полезное применение: рост итерированных отображений¶
Теперь, когда мы понимаем, что такое собственные векторы, давайте посмотрим, как они помогают глубоко понять проблему, центральную для поведения нейронной сети: правильную инициализацию весов.
22.2.6.1. Собственные векторы как долгосрочное поведение¶
Полное математическое исследование инициализации глубоких нейронных сетей выходит за рамки данного текста, но мы можем рассмотреть упрощённый пример, чтобы понять, как собственные значения помогают разобраться в работе этих моделей. Как известно, нейронные сети работают за счёт чередования слоёв линейных преобразований и нелинейных операций. Для простоты будем считать, что нелинейности отсутствуют, а преобразование представляет собой многократно повторяемую матричную операцию \(A\), так что выход нашей модели равен
При инициализации таких моделей \(A\) принимается за случайную матрицу с элементами, распределёнными по гауссовскому закону, поэтому давайте создадим одну из них. Для определённости начнём с матрицы \(5 \times 5\), имеющей нулевое среднее и дисперсию, равную единице.
torch.manual_seed(42)
k = 5
A = torch.randn(k, k, dtype=torch.float64)
A
22.2.6.2. Поведение на случайных данных¶
Для простоты в нашей учебной модели мы будем считать, что входной вектор данных \(\mathbf{v}_{in}\) представляет собой случайный пятимерный гауссов вектор. Давайте подумаем, чего мы хотим добиться. Для контекста рассмотрим общую задачу машинного обучения, где мы стремимся преобразовать входные данные, такие как изображение, в прогноз, например, в вероятность того, что на изображении изображена кошка. Если многократное применение \(\mathbf{A}\) растягивает случайный вектор, делая его очень длинным, то небольшие изменения во входных данных приведут к значительным изменениям в выходных данных — крошечные модификации входного изображения вызвали бы совершенно разные прогнозы. Это кажется неправильным!
С другой стороны, если \(\mathbf{A}\) сжимает случайные векторы, делая их короче, то после прохождения через множество слоёв вектор по сути сожмётся до нуля, и выход не будет зависеть от входа. Это также явно неверно!
Нам нужно пройти по тонкой грани между ростом и затуханием, чтобы убедиться, что выход зависит от входа, но не слишком сильно!
Давайте посмотрим, что происходит, когда мы многократно умножаем нашу матрицу \(\mathbf{A}\) на случайный входной вектор и отслеживаем норму.
# Calculate the sequence of norms after repeatedly applying `A`
v_in = torch.randn(k, 1, dtype=torch.float64)
norm_list = [torch.norm(v_in).item()]
for i in range(1, 100):
v_in = A @ v_in
norm_list.append(torch.norm(v_in).item())
d2l.plot(torch.arange(0, 100), norm_list, 'Iteration', 'Value')
Норма растёт неконтролируемо! Действительно, если мы рассмотрим список отношений, то увидим закономерность.
# Compute the scaling factor of the norms
norm_ratio_list = []
for i in range(1, 100):
norm_ratio_list.append(norm_list[i]/norm_list[i - 1])
d2l.plot(torch.arange(1, 100), norm_ratio_list, 'Iteration', 'Ratio')
Если посмотреть на последнюю часть приведённого выше вычисления, то
видно, что случайный вектор растягивается с коэффициентом
1.974459321485[...], при этом конечная часть немного смещается, но
коэффициент растяжения остаётся стабильным.
22.2.6.3. Связь с собственными векторами¶
Мы уже видели, что собственные векторы и собственные значения соответствуют тому, насколько растягивается объект, но это касалось конкретных векторов и конкретных растяжений. Давайте посмотрим, что они означают для \(\mathbf{A}\). Здесь есть одно важное замечание: чтобы увидеть их все, нам придётся перейти к комплексным числам. Их можно рассматривать как растяжения и повороты. Измерить коэффициент растяжения можно, взяв норму комплексного числа (квадратный корень из суммы квадратов действительной и мнимой частей). Также отсортируем их.
# Compute the eigenvalues
eigs = torch.linalg.eig(A).eigenvalues.tolist()
norm_eigs = [torch.abs(torch.tensor(x)) for x in eigs]
norm_eigs.sort()
print(f'norms of eigenvalues: {norm_eigs}')
22.2.6.4. Наблюдение¶
Мы наблюдаем нечто немного неожиданное: число, которое мы ранее определили как долгосрочное растяжение нашей матрицы \(\mathbf{A}\), применённой к случайному вектору, в точности (с точностью до тринадцати знаков после запятой!) совпадает с наибольшим собственным значением \(\mathbf{A}\). Это явно не совпадение!
Но если теперь рассмотреть происходящее геометрически, это начинает иметь смысл. Рассмотрим случайный вектор. Этот случайный вектор имеет небольшую компоненту в каждом направлении, в частности, он имеет хотя бы небольшую проекцию в том же направлении, что и собственный вектор \(\mathbf{A}\), соответствующий наибольшему собственному значению. Это настолько важно, что это значение называют главным собственным значением, а соответствующий ему вектор — главным собственным вектором. После применения \(\mathbf{A}\) наш случайный вектор растягивается во всех возможных направлениях, соответствующих всем возможным собственным векторам, но сильнее всего он растягивается именно в направлении, связанном с этим главным собственным вектором. Это означает, что после применения \(A\) наш случайный вектор становится длиннее и его направление всё больше совпадает с направлением главного собственного вектора. После многократного применения матрицы совпадение направления с главным собственным вектором становится всё точнее, пока, по сути, наш случайный вектор не превратится в главный собственный вектор! Действительно, этот алгоритм лежит в основе того, что известно как степенная итерация для нахождения наибольшего собственного значения и собственного вектора матрицы. Подробности см., например, в (Golub and Van Loan, 1996).
22.2.6.5. Исправление нормализации¶
Исходя из предыдущих рассуждений, мы пришли к выводу, что случайный вектор не должен ни растягиваться, ни сжиматься; мы хотим, чтобы случайные векторы сохраняли примерно одинаковый размер на протяжении всего процесса. Для этого мы нормируем нашу матрицу на это главное собственное значение, чтобы наибольшее собственное значение стало равным единице. Давайте посмотрим, что произойдет в этом случае.
# Rescale the matrix `A`
A /= norm_eigs[-1]
# Do the same experiment again
v_in = torch.randn(k, 1, dtype=torch.float64)
norm_list = [torch.norm(v_in).item()]
for i in range(1, 100):
v_in = A @ v_in
norm_list.append(torch.norm(v_in).item())
d2l.plot(torch.arange(0, 100), norm_list, 'Iteration', 'Value')
Мы также можем построить график отношения последовательных норм, как и раньше, и убедиться, что он действительно стабилизируется.
# Also plot the ratio
norm_ratio_list = []
for i in range(1, 100):
norm_ratio_list.append(norm_list[i]/norm_list[i-1])
d2l.plot(torch.arange(1, 100), norm_ratio_list, 'Iteration', 'Ratio')
22.2.7. Обсуждение¶
Теперь мы видим именно то, на что рассчитывали! После нормировки матриц по главному собственному значению мы видим, что случайные данные не взрываются, как раньше, а в конечном итоге стабилизируются на определённом значении. Было бы здорово уметь делать это, исходя из первых принципов, и оказывается, что если мы глубоко погрузимся в математику этого процесса, то увидим, что наибольшее собственное значение большой случайной матрицы с независимыми элементами, имеющими нулевое среднее и единичную дисперсию, в среднем составляет примерно \(\sqrt{n}\), или в нашем случае \(\sqrt{5} \approx 2.2\), благодаря увлекательному факту, известному как круговой закон (Ginibre, 1965). Было показано, что связь между собственными значениями (и связанным с ними объектом, называемым сингулярными значениями) случайных матриц имеет глубокие связи с правильной инициализацией нейронных сетей, как обсуждалось в Pennington et al. (2017) и последующих работах.
22.2.8. Резюме¶
Собственные векторы — это векторы, которые растягиваются матрицей без изменения направления.
Собственные значения — это множитель, на который растягиваются собственные векторы при умножении на матрицу.
Собственное разложение матрицы позволяет свести многие операции к операциям с собственными значениями.
Теорема Жордана о кругах позволяет получить приближённые значения собственных чисел матрицы.
Поведение итерированных степеней матрицы в первую очередь зависит от величины наибольшего собственного значения. Это понимание имеет множество применений в теории инициализации нейронных сетей.
22.2.9. Упражнения¶
Каковы собственные значения и собственные векторы
(22.2.21)¶\[\begin{split}\mathbf{A} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}?\end{split}\]Каковы собственные значения и собственные векторы следующей матрицы, и что в этом примере необычно по сравнению с предыдущим?
(22.2.22)¶\[\begin{split}\mathbf{A} = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}.\end{split}\]Не вычисляя собственные значения, может ли наименьшее собственное значение следующей матрицы быть меньше \(0.5\)? Примечание: эту задачу можно решить в уме.
(22.2.23)¶\[\begin{split}\mathbf{A} = \begin{bmatrix} 3.0 & 0.1 & 0.3 & 1.0 \\ 0.1 & 1.0 & 0.1 & 0.2 \\ 0.3 & 0.1 & 5.0 & 0.0 \\ 1.0 & 0.2 & 0.0 & 1.8 \end{bmatrix}.\end{split}\]