손실 지형을 들여다보는 팀이 있습니다. 학습률을 얼마까지 올려도 되는지, 지금 지점이 날카로운 골짜기인지 넓은 분지인지를 알고 싶어서 손실의 헤세 행렬, 곧 파라미터 둘씩 짝지은 2차 편미분을 모은 행렬의 고윳값을 보려 합니다. 파라미터가 1억 개면 헤세 행렬은 1억 × 1억이라 만들 수조차 없습니다. 자동미분이 내주는 것은 벡터 하나를 넣으면 를 돌려주는 함수뿐입니다. 팀은 이 함수를 40번쯤 불러 맨 위 고윳값과 스펙트럼 전체의 모양을 그립니다. 그림에는 0 근처에 넓게 퍼진 덩어리가 하나 있고, 그 오른쪽에 떨어진 점이 몇 개 서 있습니다. 논문들이 「벌크와 이상치」라 부르는 모양입니다.
리뷰에서 질문이 셋 나옵니다. 첫째, 함수를 40번 불러서 어떻게 1억 개 고윳값의 모양을 안다는 말인가요. 둘째, 같은 계산을 150번으로 늘렸더니 맨 위 고윳값이 일곱 번 겹쳐 찍혔는데, 정말 일곱 겹인가요. 셋째, 덩어리 오른쪽에 떨어진 점 가운데 어느 것이 데이터가 심은 구조이고 어느 것이 유한한 표본의 잡음인가요. 이 글은 셋에 답합니다. 앞의 두 질문은 크릴로프 부분공간과 란초스 반복이, 마지막 질문은 랜덤 행렬 이론이 맡습니다. 중급 13번 · 「행렬 거듭제곱과 거듭제곱법: 스펙트럼 반지름이 정하는 것」의 거듭제곱법과 중급 15번 · 「특잇값 분해: 모든 행렬을 회전-늘림-회전으로 쪼개고 랭크를 읽기」의 특잇값 분포 그림에 「무엇이 잡음인가」라는 기준선을 긋는 것이 후반부의 일입니다.
크릴로프 부분공간
다항식의 공간
지난 글의 범위 찾기는 무작위 행렬 를 한꺼번에 곱해 의 열공간으로 의 위쪽 특잇값 방향을 잡았고, 거듭제곱을 몇 번 끼워 넣어 그 정확도를 올렸습니다. 이번에는 벡터 하나로 시작해 행렬을 거듭 곱하면서 생긴 벡터를 하나도 버리지 않습니다. 행렬 와 시작 벡터 에 대해
를 차 크릴로프 부분공간이라 부릅니다. 이 공간의 원소는 정확히 꼴의 벡터, 곧 차수가 이하인 다항식 를 행렬에 넣어 에 곱한 것들입니다. 이 한 줄이 이 글 전반부의 열쇠입니다. 크릴로프 부분공간 위에서 무언가를 가장 잘 고르는 문제는 언제나 「가장 좋은 다항식을 고르는 문제」로 바뀝니다.
거듭제곱법과 견주면 차이가 분명합니다. 거듭제곱법은 번 곱한 뒤 마지막 벡터 하나만 씁니다. 다항식으로 말하면 로 미리 정해 둔 것입니다. 크릴로프 방법은 같은 행렬-벡터 곱 번으로 얻은 벡터를 전부 남겨 두고, 그 공간 안에서 목적에 맞는 다항식을 고릅니다. 같은 비용으로 고를 수 있는 다항식의 폭이 넓으니 결과가 더 좋을 수밖에 없고, 그 차이가 얼마인지는 아래 리츠 값과 켤레경사법에서 숫자로 나옵니다.
부분공간의 차원은 와 함께 늘다가 어딘가에서 멈춥니다. 가 대칭이고 고유분해가 라 하면 입니다. 가 성분을 가진 서로 다른 고윳값이 개면 다항식은 그 개 점에서의 값으로만 구별되므로, 차원은 에서 멈춥니다. 시작 벡터를 무작위로 잡으면 모든 고유방향에 성분이 있으니 멈추는 자리는 서로 다른 고윳값의 수입니다. 이론상 그 자리에 닿으면 크릴로프 방법은 정확한 답을 냅니다. 실무에서는 그 훨씬 전, 가 수십일 때 멈추고 근사를 읽습니다.
아르놀디 반복
를 그대로 기저로 쓰면 수치적으로 엉망이 됩니다. 거듭제곱법이 보여 주듯 이 벡터들은 모두 맨 위 고유방향으로 쏠려 서로 거의 평행해지기 때문입니다. 그래서 하나를 만들 때마다 앞의 것들과 직교화해 정규직교 기저 를 쌓습니다. 이것이 아르놀디 반복입니다.
절차는 그람–슈미트를 한 걸음씩 미루는 것입니다. 로 시작해, 번째 걸음에서 를 계산하고 앞의 모든 성분 을 빼낸 뒤 남은 벡터의 길이를 로, 정규화한 것을 로 둡니다. 는 안에 있으므로 이렇게 얻은 는 의 정규직교 기저입니다. 계수를 모으면
라는 관계가 나옵니다. 는 를 열로 쌓은 행렬, 는 를 모은 행렬이고 는 번째 표준 기저입니다. 가 까지밖에 성분을 갖지 않으므로 는 주대각선 바로 아래 한 줄까지만 값이 있는 상헤센베르크 행렬입니다. 양변 왼쪽에 를 곱하면 , 곧 는 를 크릴로프 부분공간에 사영해 그 기저로 적은 작은 행렬입니다.
란초스 삼중대각화
헤세 행렬은 대칭입니다. 그러면 도 대칭이고, 상헤센베르크이면서 대칭인 행렬은 주대각선과 그 위아래 한 줄씩만 값을 갖는 삼중대각 행렬입니다. 대각 성분을 , 위아래 성분을 로 적어 라 부릅니다. 아르놀디 관계의 번째 열을 읽으면
이라는 삼항 점화식이 됩니다. 새 벡터를 만들 때 앞의 벡터 전부가 아니라 바로 앞 둘만 빼면 된다는 뜻이고, 이렇게 대칭 행렬에 맞춰 줄인 아르놀디 반복을 란초스 반복이라 부릅니다. 한 걸음의 비용은 행렬-벡터 곱 한 번과 길이 벡터 연산 몇 번이고, 기억해야 할 것은 벡터 셋뿐입니다.
란초스 반복이 하는 일을 한 문장으로 적으면, 거대한 대칭 행렬 를 크릴로프 부분공간에 사영해 삼중대각 행렬 로 줄이는 것입니다. 이면 는 숫자 79개짜리 행렬이고, 고윳값은 노트북에서 순식간에 나옵니다. 헤세 행렬은 한 번도 만들지 않았고 를 40번 불렀을 뿐입니다. 첫째 질문의 앞부분, 「40번 불러서 무엇을 아는가」의 답이 이 작은 행렬 안에 들어 있습니다. 남은 것은 이 작은 행렬의 고윳값이 원래 행렬에 대해 무엇을 말해 주느냐입니다.
리츠 값
레일리–리츠 사영
의 고윳값 를 리츠 값이라 부르고, 의 고유벡터 를 원래 공간으로 되돌린 를 리츠 벡터라 부릅니다. 부분공간 안에서 의 고유쌍을 가장 잘 흉내 내는 짝을 고르는 이 절차를 레일리–리츠 사영이라 합니다. 리츠 값이 원래 고윳값의 근사가 되는 이유는 레일리 몫에 있습니다. 레일리 몫 의 최댓값은 이고 최솟값은 이라는 것이 중급 12번 · 「고윳값과 고유벡터: 방향이 변하지 않는 축」의 변분 성질이었습니다. 부분공간 안의 로 제한하면 이므로
입니다. 맨 위 리츠 값은 원래 맨 위 고윳값을 아래에서 다가가고, 부분공간이 커질수록 최댓값을 잡는 범위가 넓어지니 에 대해 줄어들지 않습니다. 맨 아래도 같은 논리로 위에서 다가갑니다. 안쪽 리츠 값에 대해서는 쿠란트–피셔의 최소최대 원리가 같은 일을 해, 번째 리츠 값이 를 넘지 않는다는 끼워 넣기 부등식이 섭니다.
극단 고윳값의 수렴
리츠 값이 원래 고윳값에 얼마나 빨리 다가가는지는 다항식으로 읽습니다. 은 안에서 레일리 몫을 최대로 하는 값이고, 그 공간의 원소는 이므로
입니다. 이 몫을 에 가깝게 만들려면 에서는 크고 나머지 고윳값이 사는 구간 에서는 작은 다항식을 고르면 됩니다. 로 정의되는 차 다항식을 체비쇼프 다항식이라 부르는데, 에서는 절댓값이 1을 넘지 않으면서 구간 밖에서는 같은 차수의 어떤 다항식보다 빨리 자랍니다. 구간 를 로 옮긴 체비쇼프 다항식을 넣어 계산하면 오차가 대략 로 줄어듭니다. 여기서 는 상대 간격 에 대해 꼴이라, 간격이 작아도 에 비례하는 속도로 줄어듭니다. 거듭제곱법의 비율 은 간격에 비례해서만 1에서 멀어지므로, 간격이 좁을수록 차이가 벌어집니다. 이 추정을 카니엘–페이지 이론이라 부르고, 여기서는 줄기만 적습니다.
같은 그림이 안쪽 고윳값이 느린 이유도 말해 줍니다. 구간 한가운데의 고윳값 하나를 골라 키우려면 다항식이 그 점에서만 크고 양옆의 이웃 고윳값에서는 작아야 하는데, 이웃이 빽빽하면 그런 다항식은 차수가 매우 높아야 합니다. 극단에 떨어져 있는 고윳값은 한쪽에만 이웃이 있고 그것도 멀리 있으니 낮은 차수로 충분합니다. 리츠 값이 스펙트럼의 끝에서부터 차례로 잡히는 이유가 이것입니다.
아래 그림은 400 × 400 대각 행렬로 이를 확인한 것입니다. 고윳값 397개를 에 고르게 뿌리고 벌크 밖에 1.6, 2.2, 3.0을 하나씩 둔 뒤, 무작위 벡터로 시작한 란초스의 리츠 값을 걸음마다 찍었습니다. 3.0은 5걸음에 2.996, 6걸음에 2.9999로 잡히고, 2.2는 6걸음에 2.1989, 1.6은 10걸음에 1.598입니다. 반면 벌크 안의 리츠 값은 20걸음이 지나도 개별 고윳값을 잡지 못하고 구간을 고르게 채울 뿐입니다. 맨 아래 리츠 값은 20걸음에 0.0056까지 내려와 참값 0.0027에 다가가는 중입니다. 벌크의 아래 끝도 극단이라 같은 방식으로 수렴합니다.
이 성질이 헤세 행렬 분석의 출발점입니다. 학습률의 안정 조건을 정하는 맨 위 고윳값, 그리고 벌크에서 떨어져 선 이상치 몇 개는 정확히 「극단에 떨어져 있는 고윳값」이라 란초스 수십 걸음이면 소수 넷째 자리까지 잡힙니다. 벌크 안의 고윳값 하나하나는 영영 못 잡지만, 아래 절에서 보듯 벌크의 모양, 곧 밀도는 따로 읽어 낼 수 있습니다.
유령 고윳값
정확한 산술에서 란초스 벡터 는 서로 직교합니다. 삼항 점화식이 앞의 둘만 빼는데도 나머지와 직교하는 것은 행렬이 대칭이라는 대수적 사실 덕분입니다. 부동소수점에서는 이 보장이 깨집니다. 반올림 오차가 조금씩 섞여 들어오는데, 리츠 값 하나가 고윳값에 수렴하는 순간 그 고유방향 성분이 다시 자라나기 시작합니다. 페이지가 1970년대에 밝힌 구조로, 직교성은 무작위로 무너지지 않고 수렴한 리츠 벡터의 방향으로 무너집니다. 그러면 반복은 이미 찾은 고윳값을 처음 보는 것처럼 다시 찾아내고, 에 같은 값이 둘, 셋 겹쳐 찍힙니다. 실제로는 한 겹인 고윳값이 여러 겹으로 보이는 이 복사본을 유령 고윳값이라 부릅니다.
위의 대각 행렬에서 다른 시작 벡터로 재 보면 이렇습니다. 표의 「3.0의 복사본」은 의 고윳값 가운데 3.0에서 안에 드는 것의 개수이고, 「직교성 손실」은 입니다.
| 걸음 수 | 3.0의 복사본 | 2.2의 복사본 | 직교성 손실 | 재직교화 시 복사본 |
|---|---|---|---|---|
| 20 | 1 | 1 | 0.0018 | 1 |
| 40 | 2 | 2 | 0.63 | 1 |
| 60 | 3 | 3 | 0.70 | 1 |
| 80 | 4 | 3 | 0.80 | 1 |
| 100 | 6 | 4 | 0.80 | 1 |
| 120 | 7 | 5 | 0.80 | 1 |
20걸음에서 이미 직교성이 만큼 새고, 40걸음이면 3.0과 2.2가 두 겹이 됩니다. 걸음이 늘수록 극단 고윳값부터 복사본이 쌓입니다. 둘째 질문의 답이 이 표에 있습니다. 150걸음에서 맨 위 고윳값이 일곱 번 찍힌 것은 일곱 겹이라서가 아니라 직교성이 무너져서입니다. 리츠 값 자체는 틀리지 않았다는 점이 함정을 더 교묘하게 만듭니다. 값은 정확한데 개수가 틀립니다.
처방은 재직교화, 곧 새 벡터를 만들 때마다 앞의 전부의 성분을 다시 빼는 것입니다. 표의 오른쪽 열처럼 복사본이 사라지고 직교성 손실은 에 머뭅니다. 한 번으로는 반올림 때문에 모자라 두 번 빼는 것이 관례입니다. 대가는 저장과 계산입니다. 벡터 개를 모두 들고 있어야 하고 걸음마다 의 일이 더 듭니다. 가 수십에서 백 남짓인 스펙트럼 분석에서는 행렬-벡터 곱 한 번, 곧 역전파 한 번보다 싼 일이라 대개 그냥 씁니다. 직교성이 일정 수준을 넘을 때만 수렴한 방향을 골라 빼는 선택적 재직교화도 있습니다.
켤레경사법
부분공간 위의 최적해
대칭 양정치 행렬 로 연립방정식 를 푸는 일은 2차 함수 를 최소화하는 일과 같습니다. 기울기가 이기 때문입니다. 뉴턴법의 한 걸음 , 가우스–뉴턴, K-FAC의 전처리 모두 결국 이런 연립방정식이고, 중급 51번 · 「뉴턴법과 2차 방법: 왜 안 쓰는가, 요즘은 무엇을 근사하는가」가 「헤세 행렬을 만들지 않고 근사로 푼다」고 넘어간 자리의 안쪽이 여기입니다.
켤레경사법은 에서 시작해 번째 걸음에서
를 내놓는 방법입니다. 는 가 정하는 노름이고, 는 참해입니다. 이므로 이것은 크릴로프 부분공간 위에서 를 정확히 최소화한 점입니다. 같은 부분공간 위에서 란초스는 고윳값을, 켤레경사법은 연립방정식의 해를 고르는 셈이고, 실제로 켤레경사법의 계수를 모으면 란초스의 가 그대로 나옵니다.
놀라운 점은 이 최적해를 앞의 걸음 하나만 기억하는 짧은 점화식으로 얻는다는 것입니다. 탐색 방향 들이 을 만족하도록, 곧 서로 -켤레가 되도록 고르면 각 방향을 따라 한 번씩 정확히 선 탐색한 결과가 부분공간 전체에서의 최적해가 됩니다. 새 방향을 만들 때 바로 앞 방향의 성분만 빼면 나머지와도 저절로 켤레가 되는 것은 란초스의 삼항 점화식과 같은 대칭성 덕분입니다. 경사하강법이 지난 걸음을 잊고 매번 기울기만 보는 것과 달리, 켤레경사법은 지금까지 탐색한 부분공간 전체에서 이미 최적이라 같은 방향으로 되돌아가는 낭비가 없습니다.
수렴률
오차를 다항식으로 쓰면 수렴률이 나옵니다. 이고 이므로 는 꼴이고, 는 차수 이하이면서 인 다항식입니다. 켤레경사법은 그런 다항식 가운데 -노름 오차를 최소로 하는 것을 고르므로
입니다. 고윳값 자리에서만 작으면 되는 것을 구간 전체로 넓혀 위로 눌렀습니다. 오른쪽의 최소최대 문제는 답이 알려져 있고, 리츠 값의 수렴에서 쓴 체비쇼프 다항식이 다시 그 답입니다. 구간 를 로 옮기고 로 맞춘 것이 최적이고, 계산을 마치면 조건수 으로
를 얻습니다. 최적 보폭의 경사하강법은 매 걸음 배씩만 줄어듭니다. 오차를 배로 줄이는 데 드는 걸음 수로 바꾸면 경사하강법은 대략 , 켤레경사법은 입니다. 조건수가 로 바뀌는 것, 중급 45번 · 「테일러 2차 근사와 헤세 행렬: 곡률, 안장점, 조건수」에서 본 조건수의 벌칙이 제곱근으로 줄어드는 것이 크릴로프 방법의 대표적인 이득입니다.
인 1000차원 대각 행렬에서 실제로 돌려 보았습니다. 고윳값은 1과 1000 사이에 로그 눈금으로 고르게 뿌렸습니다. 상대 오차 에 켤레경사법은 109걸음에 닿고, 상한이 주는 걸음 수는 120입니다. 경사하강법은 150걸음 뒤에도 오차가 0.54에 머물고, 같은 까지 가려면 상한 계산으로 약 3,450걸음이 필요합니다.
실제 곡선이 상한보다 조금 아래에 있는 것은 상한이 고윳값 자리가 아니라 구간 전체를 보기 때문입니다. 고윳값이 몇 개의 무리로 뭉쳐 있으면 켤레경사법은 무리마다 다항식의 근 하나를 박아 넣어 훨씬 빨리 끝납니다. 이상치 몇 개와 좁은 벌크로 이뤄진 헤세 스펙트럼은 이 점에서 켤레경사법에 유리한 모양입니다. 이상치 개는 걸음 개로 지우고, 남은 걸음은 벌크의 좁은 조건수로 수렴합니다.
CG-Steihaug
헤세 행렬이 양정치라는 가정은 신경망의 손실에서 흔히 깨집니다. 안장점 근처에서는 음수 고윳값이 있고, 그러면 가 아래로 끝없이 내려가 연립방정식의 해가 최소점이 아닙니다. 그래서 2차 방법은 걸음의 길이를 묶어 둡니다. 현재 지점에서 반지름 의 공 안에서만 2차 근사를 믿고
를 푸는 것이 신뢰영역 방법이고, 공의 반지름은 근사가 실제 손실을 얼마나 잘 예측했는지에 따라 걸음마다 늘리고 줄입니다.
이 하위 문제를 헤세-벡터 곱만으로 푸는 것이 CG-Steihaug입니다. 0에서 출발해 켤레경사법을 그대로 돌리다가 두 경우에 멈춥니다. 탐색 방향 에서 곡률 가 0 이하로 나오면 그 방향으로는 손실이 끝없이 내려가니 그 방향을 따라 공의 경계까지 갑니다. 다음 반복점이 공 밖으로 나가면 경계에서 멈춥니다. 켤레경사법의 반복점은 길이가 단조롭게 늘어나므로 경계를 한 번 넘으면 다시 돌아오지 않고, 그래서 이 멈춤이 정당합니다. 음의 곡률 방향을 만나는 순간을 「실패」가 아니라 「안장점을 벗어날 방향을 찾았다」로 읽는다는 점이 이 방법의 묘미이고, 헤세-벡터 곱 기반의 2차 최적화기 대부분이 안쪽에 이 반복을 품고 있습니다.
행렬 없는 스펙트럼 추정
헤세-벡터 곱
여기까지 쓴 연산은 하나뿐이었습니다. 벡터 를 받아 를 돌려주는 것입니다. 헤세 행렬이 자리에 들어가면 그것이 헤세-벡터 곱이고, 행렬 없이 계산할 수 있습니다. 기울기 를 방향 로 미분하면
입니다. 오른쪽 식은 스칼라 를 한 번 더 미분하라는 뜻이고, 자동미분으로는 역전파 한 번에 순전파 방향 미분을 얹은 정도, 대략 기울기 계산 두 번의 비용이 듭니다. 펄머터의 방법이라 부르는 이 계산 덕분에 파라미터가 개인 모델에서 헤세-벡터 곱 하나는 메모리와 기울기 두어 번의 시간이면 됩니다. 행렬 전체는 개 숫자라, 1억 파라미터에서는 4경 바이트가 넘습니다.
글의 계산을 손에 쥘 크기로 줄인 장면을 하나 세워 끝까지 씁니다. 파라미터가 개인 로지스틱 회귀를 표본 개로 학습합니다. 손실은 이고 헤세 행렬은
이라 헤세-벡터 곱은 으로, 행렬을 만들지 않고 행렬-벡터 곱 두 번에 끝납니다. 입력 는 표준정규 잡음에, 서로 직교하는 네 방향을 따라 분산 4, 1.5, 0.5, 0.3짜리 신호를 더해 만들었습니다. 초기화 지점 에서는 모든 이라 , 곧 입력의 표본 공분산을 4로 나눈 것입니다. 이 장면을 고른 이유는 후반부에서 드러납니다. 헤세 스펙트럼이 정확히 표본 공분산의 스펙트럼이 되므로, 랜덤 행렬 이론의 예측을 그대로 대 볼 수 있습니다.
Hutchinson 추정량
스펙트럼에 관한 가장 간단한 요약은 대각합, 곧 고윳값의 합입니다. 헤세 행렬의 대각합은 평균 곡률이고, 일반화와 평탄함을 연결하는 논문들이 자주 씁니다. 행렬 없이 대각합을 재는 방법은 무작위 벡터의 이차형식입니다. 성분이 서로 독립이고 평균 0, 분산 1인 무작위 벡터 를 잡으면 이므로
입니다. 를 개 뽑아 를 평균하는 것이 Hutchinson 추정량입니다. 헤세-벡터 곱 번이 비용의 전부입니다.
이 추정량의 분산은 직접 계산할 수 있습니다. 의 분산을 성분의 4차 적률로 풀면, 성분이 을 반반으로 갖는 라데마허 벡터에서는 이 늘 성립해 대각 항이 상수가 되고
이 남습니다. 표준정규 벡터에서는 대각 항도 흔들려 입니다. 라데마허가 언제나 같거나 낫고, 대각 성분이 큰 행렬일수록 차이가 큽니다. 위 장면의 헤세 행렬에서 대각합은 251.5, , 대각 성분 제곱합은 63.3이라 벡터 하나의 표준편차가 라데마허로 8.09, 정규로 13.9입니다. 2,000번씩 뽑아 잰 표준편차 8.03과 14.1이 계산과 맞습니다. 벡터 10개면 표준편차가 이라 상대 오차 1% 안팎입니다. 이 값이 표본 하나가 기댓값에서 얼마나 벗어나는지를 확률로 묶는 일반적인 도구는 다음 단원이 세웁니다.
확률적 란초스 구적
대각합은 고윳값의 합 하나이고, 우리가 원하는 것은 고윳값의 분포 전체입니다. 대칭 행렬의 고윳값 에 질량 씩을 놓은 분포
를 스펙트럼 밀도라 부릅니다. 함수 를 이 분포로 평균하면 이므로, 스펙트럼 밀도를 아는 것은 모든 에 대해 를 아는 것과 같습니다. 그리고 는 Hutchinson 추정량으로 입니다. 남은 문제는 행렬 함수의 이차형식 를 행렬 없이 계산하는 것입니다.
를 고유벡터로 풀면 , 입니다. 고윳값 자리에 무게 를 놓은 분포 위의 적분이라는 뜻입니다. 여기서 란초스가 다시 나옵니다. 로 시작한 란초스를 걸음 돌려 로 고유분해하면, 리츠 값 를 마디로 하고 의 고유벡터 첫 성분의 제곱 를 무게로 하는 규칙이 차수 이하의 모든 다항식 에서 그 적분을 정확히 맞힙니다. 마디와 무게를 골라 적분을 유한한 합으로 바꾸는 규칙 가운데 이렇게 차수를 최대로 맞히는 것을 가우스 구적이라 부르고, 란초스의 가 정확히 그 가우스 구적의 마디와 무게를 준다는 것이 골럽과 웰시의 관찰입니다.
둘을 합친 절차가 확률적 란초스 구적입니다.
- 라데마허 벡터 을 뽑습니다.
- 벡터마다 재직교화를 붙인 란초스를 걸음 돌려 를 얻습니다.
- 를 고유분해해 리츠 값 과 무게 을 모읍니다.
- 스펙트럼 밀도를 로 근사하고, 그림으로 그릴 때는 델타 대신 폭이 좁은 가우스 핵을 씁니다.
위 장면에서 , 으로 돌리면 헤세-벡터 곱 400번입니다. 이렇게 얻은 에서 벌크 바깥에 놓인 무게를 배하면 1.82로, 벌크 밖 고윳값이 두 개쯤이라고 말해 줍니다. 대각합 추정 250.85는 참값 251.49와 맞습니다. 사실 에 대해서는 이 절차가 Hutchinson 추정량과 정확히 같은 값을 냅니다. 이기 때문입니다. 재직교화를 빼먹으면 유령 고윳값이 여기서도 나타나는데, 복사본들이 원래 무게를 나눠 갖는 경향이 있어 밀도의 모양은 대체로 살아남고 「몇 개인가」를 세는 일만 틀립니다. 이상치의 개수가 관심사라면 재직교화는 선택이 아닙니다.
랜덤 행렬의 기준선
위그너 반원 법칙
이제 셋째 질문, 「무엇이 잡음인가」로 넘어갑니다. 잡음만으로 된 행렬의 스펙트럼이 어떻게 생겼는지 알아야 그 위에 얹힌 신호를 가릴 수 있습니다. 행렬의 고윳값에 질량을 고르게 놓은 분포, 곧 위의 를 랜덤 행렬 이론에서는 경험적 스펙트럼 분포라 부릅니다. 행렬이 무작위이므로 이 분포도 무작위인데, 크기가 커지면 하나의 결정된 분포로 모인다는 것이 이 이론의 첫 정리들입니다.
가장 단순한 경우는 대칭 잡음 행렬입니다. 대칭 행렬의 위쪽 성분이 서로 독립이고 평균 0, 분산 이면, 에서 경험적 스펙트럼 분포가
로 모입니다. 그래프가 반원이라 위그너 반원 법칙이라 부릅니다. 성분 하나하나의 분포가 정규든 이든 상관없이 같은 반원이 나온다는 것이 핵심입니다. 증명의 줄기는 적률입니다. 를 성분의 곱으로 풀어 세면, 극한에서 살아남는 항이 나무 모양의 경로뿐이고 그 개수가 카탈랑 수라 반원 분포의 적률과 같아집니다. 성분의 세부 분포는 작은 항으로 사라집니다.
반원은 잡음의 크기를 정합니다. 성분 분산이 인 잡음 행렬의 고윳값은 를 넘지 않습니다. 정확히는 맨 위 고윳값도 로 모입니다. 이 잡음 위에 크기 의 계수 1 신호 를 얹으면, 일 때만 고윳값 하나가 로 튀어나오고 그보다 약하면 반원의 끝 에 붙어 버립니다. 같은 일이 다음 절의 공분산에서 더 중요한 모양으로 일어나므로, 거기서 자세히 봅니다.
마르첸코–파스투르 분포
헤세 행렬, 공분산, 가중치의 특잇값은 대칭 잡음 행렬보다 꼴을 닮았습니다. 가 이고 성분이 독립, 평균 0, 분산 이면 표본 공분산 의 기댓값은 라 모든 고윳값이 이어야 할 것 같습니다. 실제로는 그렇지 않습니다. 비율 을 고정하고 둘 다 키우면 경험적 스펙트럼 분포가
로 모이고, 이것을 마르첸코–파스투르 분포라 부릅니다. 이면 의 계수가 을 넘지 못하므로 0에 질량 가 더 붙습니다. 표본이 차원보다 몇 배 많아도 공분산의 고윳값이 한 점에 모이지 않고 구간 에 퍼진다는 것, 이 퍼짐이 순수하게 유한한 표본에서 온다는 것이 이 분포가 하는 말입니다. 잡음만으로 이루어진 이 덩어리를 벌크라 부릅니다.
종횡비와 지지구간
벌크의 폭을 정하는 것은 하나의 수, 의 종횡비 입니다. 차원을 표본 수로 나눈 이 비가 작으면 구간이 근처로 좁아지고, 1에 가까워지면 0부터 까지 넓게 퍼집니다. 아래 그림이 에서 세 종횡비의 밀도입니다. 이면 , 이면 , 이면 입니다. 표본이 차원의 열 배여도 가장 큰 고윳값이 참값의 1.73배로 나온다는 뜻이라, 공분산의 위쪽 고윳값을 「이 방향에 분산이 몰려 있다」로 바로 읽으면 안 됩니다.
특잇값으로 옮기면 기억하기 쉬운 꼴이 됩니다. 의 특잇값은 고윳값의 제곱근이므로 , 곧
입니다. 성분 분산이 인 잡음 행렬의 특잇값은 두 변 길이의 제곱근을 더하고 뺀 사이에 놓입니다. 신경망 가중치를 분산 로 초기화하는 규칙은 이 식의 두 항을 어림해 층을 지날 때 신호 크기가 1 근처에 머물게 하려는 것이고, 초기화 직후의 가중치 행렬이 바로 이 분포를 따릅니다.
위 장면에 대 봅니다. 이고 잡음 분산이 1이며 헤세 행렬이 표본 공분산의 4분의 1이므로, 신호가 없었다면 헤세 고윳값은 에 퍼졌을 것입니다. 실제로 계산한 맨 아래 고윳값은 0.0210이라 왼쪽 끝과 맞습니다. 그리고 0.7286 오른쪽에 떨어진 고윳값이 두 개 있습니다. 그것이 신호인지는 아직 말할 수 없습니다. 벌크의 끝은 극한의 값이고 유한한 행렬에서는 끝 근처가 조금 흔들리기 때문입니다. 무엇이 벌크에서 떨어질 자격이 있는지를 정하는 것이 다음 절입니다.
스파이크와 무거운 꼬리
BBP 상전이
신호를 가장 단순하게 모형화합니다. 모집단 공분산이 , 곧 잡음 분산 1 위에 단위벡터 방향으로만 분산 가 더 얹힌 경우입니다. 이것을 스파이크 모형이라 부르고, 몇 개의 방향에 구조가 있고 나머지는 잡음인 데이터의 가장 작은 모형입니다. 표본 공분산의 맨 위 고윳값은 근처에 서야 할 것 같지만, 실제로는 종횡비에 따라 날카롭게 갈립니다. 을 고정한 극한에서
입니다. 문턱 를 넘는 신호는 벌크 오른쪽 끝 밖으로 고윳값 하나를 밀어내고, 문턱 아래의 신호는 아무리 실재해도 벌크 끝에 흡수되어 보이지 않습니다. 바이크, 벤 아루스, 페셰가 2005년에 밝힌 이 갈림을 BBP 상전이라 부릅니다. 문턱을 넘은 뒤에도 튀어나온 고윳값은 가 아니라 만큼 부풀어 있습니다. 잡음이 신호 방향으로 분산을 조금 보태기 때문입니다.
그림의 점은 , 에서 마다 네 번 뽑아 평균한 값입니다. 까지는 맨 위 고윳값이 2.89 근처, 곧 벌크 끝 2.91에서 움직이지 않습니다. 에서 3.355로 이론값 3.333과, 에서 4.625로 이론값 4.667과 맞습니다. 문턱 바로 위 에서는 이론값 2.925가 벌크 끝 2.914와 거의 같아 유한한 행렬에서는 구별되지 않습니다. 상전이는 극한에서 날카롭고 유한한 크기에서는 문턱 근처가 흐려집니다.
고유벡터의 겹침
고윳값이 튀어나왔다고 해서 그 고유벡터가 신호 방향을 정확히 가리키는 것은 아닙니다. 표본 공분산의 맨 위 고유벡터 와 참 방향 의 겹침도 같은 문턱에서 갈립니다.
문턱 아래에서는 고유벡터가 무작위 방향과 다름없고, 문턱 위에서도 겹침은 1보다 작습니다. 위 그림 오른쪽에서 일 때 겹침은 이론 0.583, 실측 0.587이고, 에서도 0.84에 머뭅니다. 고윳값이 벌크에서 분명히 떨어져 있어도 그 방향의 16%는 잡음이라는 뜻입니다. 이상치의 고유벡터로 「모델이 어떤 방향을 배웠는가」를 해석하려 할 때 이 값이 얼마나 믿을지를 정합니다.
이제 장면으로 돌아가 셋째 질문에 답할 수 있습니다. 숨긴 신호의 세기는 4, 1.5, 0.5, 0.3이고 문턱은 입니다. 앞의 둘만 문턱을 넘으므로 이상치는 정확히 두 개여야 하고, 그 자리는 헤세 행렬이 공분산의 4분의 1이니 과 입니다. 란초스가 잡은 값은 1.436과 0.810이고, 셋째 고윳값 0.718은 벌크 끝 0.729 안쪽에 있습니다. 신호 0.5와 0.3은 데이터에 분명히 있는데도 헤세 스펙트럼에서는 잡음과 구별되지 않습니다. 확률적 란초스 구적이 벌크 밖 무게로 센 1.82도 이 「둘」을 가리킵니다. 표본을 늘려 를 줄이면 문턱이 내려가 셋째 신호가 드러날 수 있습니다. 이상치의 개수는 데이터의 성질이면서 동시에 표본 크기의 성질입니다.
실제 신경망의 헤세 스펙트럼에서 고르바니와 파피안이 보고한 「벌크와 이상치」 구조가 이 장면의 큰 판입니다. 파피안은 분류 문제의 헤세 행렬에서 이상치의 수가 클래스 수와 맞물리고 그 방향이 클래스 평균의 구조에서 온다는 것을 보였습니다. 이 장면처럼 초기화 지점이 아니라 학습 중의 지점에서는 가 표본마다 달라 벌크가 정확한 마르첸코–파스투르 모양에서 벗어나므로, 기준선은 정확한 예측이 아니라 「이 정도 퍼짐은 잡음만으로도 생긴다」는 눈금으로 씁니다.
무거운 꼬리 스펙트럼
학습된 가중치 행렬의 특잇값 분포는 초기화 때의 마르첸코–파스투르 모양에서 어떻게 달라질까요. 마틴과 마호니는 잘 학습된 큰 모델의 층마다 의 경험적 스펙트럼 분포를 그려, 벌크 끝 너머로 이상치 몇 개가 아니라 거듭제곱 꼴로 늘어진 꼬리 가 서는 경우가 많다고 보고했습니다. 꼬리가 거듭제곱으로 줄어들어 큰 값이 드물지 않게 나오는 이런 분포를 무거운 꼬리 분포라 부르고, 그 지수 가 작을수록 꼬리가 무겁습니다. 그들은 이 지수를 층마다 재서 모델 품질의 진단으로 쓰는데, 보고된 잘 학습된 층의 지수는 대략 2에서 6 사이입니다.
지수는 맨 위 고윳값 개로 재는 힐 추정량 으로 어림합니다. 위쪽 고윳값들이 서로 비슷하면 로그 비가 작아 가 크고, 차례로 크게 벌어지면 가 작습니다. 이것을 장난감 크기에서 재 보았습니다. 입력 200, 은닉 400인 2층 tanh 신경망을, 은닉 50개짜리 교사 신경망이 낸 값으로 SGD 3,000걸음 학습했습니다. 교사의 첫 층 행 크기는 로 줄어들게 두어 세기가 고르지 않은 신호를 심었습니다. 첫 층 은 400 × 200이고 성분 분산 으로 초기화했으므로 특잇값의 벌크 끝은 입니다.
| 걸음 | 학습 손실 | 맨 위 특잇값 | 끝 밖의 수 | (위 10개) |
|---|---|---|---|---|
| 0 | 23.22 | 2.378 | 0 | 11.68 |
| 100 | 3.096 | 3.988 | 1 | 6.46 |
| 300 | 1.305 | 3.609 | 4 | 7.09 |
| 1000 | 0.0091 | 3.316 | 11 | 8.44 |
| 3000 | 0.0000 | 3.314 | 11 | 8.44 |
초기화 때는 맨 위 특잇값 2.378이 이론 끝 2.414 안에 있고 막대가 곡선과 겹칩니다. 학습이 끝나면 벌크의 몸통은 거의 그대로인 채 끝 너머로 열한 개가 나가고, 그 가운데 하나는 3.31로 멀리 떨어진 스파이크, 나머지는 2.4에서 2.75 사이로 끝을 넘어 이어진 짧은 꼬리입니다. 교사가 심은 세기 고른 신호 가운데 문턱을 넘은 것들이 차례로 벌크 밖에 선 모양입니다. 는 11.7에서 8.4로 내려가 꼬리가 무거워지는 방향으로 움직였습니다.
이 장난감에서 정직하게 읽을 수 있는 것은 거기까지입니다. 첫째, 8.4는 큰 모델에서 보고되는 범위보다 한참 크고, 그래프도 거듭제곱 꼬리라기보다 「벌크와 스파이크 몇 개」입니다. 작은 신경망과 짧은 학습으로는 그 국면까지 가지 않습니다. 둘째, 가 100걸음에서 6.46까지 내려갔다가 다시 오른 것은 꼬리가 무거워졌다가 가벼워졌기 때문이 아닙니다. 학습 초반에 가장 센 교사 방향 하나가 먼저 크게 자라 맨 위 특잇값이 3.99까지 솟았고, 위 10개 가운데 하나만 멀리 떨어져 있으면 로그 비의 합이 커져 가 작아집니다. 스파이크 하나와 긴 꼬리를 같은 숫자로 섞는 추정량이라, 지수 하나만 보지 말고 분포 그림을 마르첸코–파스투르 곡선과 겹쳐 함께 봐야 합니다. 이 그림이 중급 15번의 특잇값 그림에 그어 주는 기준선입니다. 곡선 안쪽은 잡음만으로도 생기는 퍼짐이고, 바깥으로 떨어진 것이 학습이 실은 구조입니다.
다시 헤세 스펙트럼으로
코드로 확인하기
첫머리의 세 질문을 장면 하나에서 한꺼번에 확인합니다. 헤세 행렬은 검산하는 마지막 줄에서만 만듭니다.
import numpy as np
rng = np.random.default_rng(0)
n, d = 2000, 1000 # 표본 2000, 파라미터 1000 → γ = d/n = 0.5
theta = np.array([4.0, 1.5, 0.5, 0.3]) # 입력에 숨긴 네 방향의 신호 세기
U = np.linalg.qr(rng.standard_normal((d, 4)))[0]
X = rng.standard_normal((n, d)) + (rng.standard_normal((n, 4)) * np.sqrt(theta)) @ U.T
def hvp(w, v): # 헤세 행렬을 만들지 않고 Hv 만 계산한다
s = 1 / (1 + np.exp(-X @ w))
return X.T @ (s * (1 - s) * (X @ v)) / n
def lanczos(mv, v, k, reorth=True):
Q = np.zeros((len(v), k + 1)); a = np.zeros(k); b = np.zeros(k)
Q[:, 0] = v / np.linalg.norm(v)
for j in range(k):
r = mv(Q[:, j]); a[j] = Q[:, j] @ r
r -= a[j] * Q[:, j] + (b[j - 1] * Q[:, j - 1] if j else 0)
if reorth: # 완전 재직교화(두 번)
for _ in range(2): r -= Q[:, :j + 1] @ (Q[:, :j + 1].T @ r)
b[j] = np.linalg.norm(r); Q[:, j + 1] = r / b[j]
return np.diag(a) + np.diag(b[:-1], 1) + np.diag(b[:-1], -1)
w0 = np.zeros(d) # 초기화 지점: s(1-s) = 1/4 로 일정하다
mv = lambda v: hvp(w0, v)
print(np.round(np.linalg.eigvalsh(lanczos(mv, rng.standard_normal(d), 40))[::-1][:4], 4))
# [1.4359 0.8103 0.7184 0.7127] ← 란초스 40걸음의 위쪽 리츠 값
g = d / n
edge = (1 + np.sqrt(g)) ** 2 / 4 # 마르첸코–파스투르 벌크의 오른쪽 끝 (× 1/4)
bbp = np.where(theta > np.sqrt(g), (1 + theta) * (1 + g / theta) / 4, edge)
print(round(edge, 4), np.round(bbp, 4))
# 0.7286 [1.4062 0.8333 0.7286 0.7286] ← 앞의 둘만 문턱을 넘는다
nodes, weights = [], [] # 확률적 란초스 구적: 벡터 10개 × 40걸음
for _ in range(10):
th, S = np.linalg.eigh(lanczos(mv, rng.choice([-1.0, 1.0], d), 40))
nodes.append(th); weights.append(S[0] ** 2 / 10)
nodes, weights = np.concatenate(nodes), np.concatenate(weights)
print(round(d * weights[nodes > 1.02 * edge].sum(), 2)) # 벌크 밖 고윳값의 수
# 1.82
print(round(d * (nodes * weights).sum(), 2), round((X ** 2).sum() / n / 4, 2)) # tr H 추정, 참값
# 250.85 251.49
th = np.linalg.eigvalsh(lanczos(mv, rng.standard_normal(d), 150, reorth=False))
print(np.sum(np.abs(th - th.max()) < 1e-6), np.round(th[::-1][:4], 4)) # 재직교화 없이 150걸음
# 7 [1.4359 1.4359 1.4359 1.4359] ← 유령 고윳값
ev = np.linalg.eigvalsh(X.T @ X / n / 4) # 검산용으로만 행렬을 만든다
print(np.round(ev[::-1][:4], 4), round(ev[0], 4), round((1 - np.sqrt(g)) ** 2 / 4, 4))
# [1.4359 0.8103 0.7184 0.7128] 0.021 0.0214
첫째 질문의 답은 첫 줄과 마지막 줄의 대조입니다. 헤세-벡터 곱 40번으로 얻은 위쪽 리츠 값 넷이 행렬을 통째로 고유분해한 값과 소수 넷째 자리까지 같고, 넷째 값만 0.7127과 0.7128로 마지막 자리가 다릅니다. 극단에 떨어진 고윳값부터 잡히고 벌크 끝으로 들어갈수록 느려진다는 리츠 값의 성질 그대로입니다. 스펙트럼 전체의 모양은 확률적 란초스 구적이 400번의 곱으로 그립니다. 벌크 밖 무게가 1.82, 대각합이 250.85로 참값 251.49와 맞습니다.
둘째 질문의 답은 재직교화를 끈 줄입니다. 150걸음을 돌리면 맨 위 고윳값 1.4359가 일곱 번 찍힙니다. 값은 정확하고 개수만 틀렸습니다. 실제 행렬에서 그 고윳값은 한 겹입니다. 셋째 질문의 답은 둘째 줄입니다. 종횡비 0.5가 정하는 벌크 끝 0.7286 위로 나갈 자격이 있는 것은 세기 4와 1.5인 신호뿐이고, BBP가 예측한 1.406과 0.833 자리에 란초스가 1.436과 0.810을 잡았습니다. 세기 0.5와 0.3인 신호는 데이터에 있는데도 문턱 아래라 벌크에 묻혔습니다. 실측이 예측에서 2~3% 어긋난 것은 행렬이 유한하기 때문이고, 벌크 끝 바로 안쪽 0.718과 0.713이 끝 0.729에 바싹 붙어 있는 것도 같은 이유입니다.
연습
대각 행렬 과 에 대해, 를 키울 때 크릴로프 부분공간 의 차원이 얼마에서 멈추는지와, 그 걸음에서 란초스가 내는 리츠 값을 구하세요.
가 성분을 가진 서로 다른 고윳값이 2, 5, 7 셋이므로 차원은 3에서 멈춥니다. 고윳값 2의 두 방향은 에서 늘 같은 계수 를 받아 하나로 묶입니다. 3걸음에서 는 를 그 3차원 불변 부분공간에 사영한 것이라 리츠 값은 정확히 2, 5, 7입니다.조건수가 인 대칭 양정치 연립방정식에서, 켤레경사법의 상한 이 아래로 내려가는 최소 걸음 수와, 최적 보폭 경사하강법의 비율 이 아래로 내려가는 최소 걸음 수를 구하세요.
켤레경사법은 비율이 이라 , 곧 99걸음입니다. 경사하강법은 비율이 이라 , 곧 1,843걸음입니다. 약 19배 차이로, 의 크기와 맞습니다.대칭 행렬 의 대각합을 Hutchinson 추정량 한 번으로 잴 때, 라데마허 벡터와 표준정규 벡터 각각에서 의 분산을 구하세요. 라데마허 쪽은 네 가지 를 직접 늘어놓아 확인하세요.
라데마허는 입니다. 직접 보면 라 인 두 경우에 7, 인 두 경우에 3이고, 평균 5에서 각각 2씩 떨어져 분산 4입니다. 표준정규는 입니다.차원 , 표본 이고 잡음 분산이 1인 표본 공분산에서, 신호 세기 인 스파이크 하나가 있을 때 맨 위 고윳값과 고유벡터 겹침 의 극한을 구하세요. 세기가 라면 어떻게 되나요.
, 문턱 입니다. 는 문턱을 넘으므로 고윳값은 , 겹침은 입니다. 는 문턱 아래라 고윳값은 벌크 끝 에 붙고 겹침은 0으로 갑니다.성분 분산이 인 대칭 잡음 행렬에 를 더했습니다(). 이 클 때 와 각각에서 맨 위 고윳값은 어디로 가나요.
반원의 끝은 이고 문턱은 입니다. 이면 로 튀어나옵니다. 이면 문턱 아래라 반원 끝 2에 붙습니다. 으로 뽑아 보면 각각 2.512와 2.001이 나옵니다.
크릴로프 부분공간은 행렬-벡터 곱만 허락된 세계에서 가장 넓게 고르는 방법이었습니다. 란초스는 그 공간 위에서 극단 고윳값을 먼저 잡고 가우스 구적으로 스펙트럼 밀도를 그리며, 켤레경사법은 같은 공간 위에서 연립방정식을 풀어 조건수의 벌칙을 제곱근으로 줄입니다. 재직교화를 빼면 값은 맞고 개수가 틀립니다. 그렇게 얻은 스펙트럼은 마르첸코–파스투르 벌크와 BBP 문턱에 대어 읽습니다. 벌크 안은 표본이 유한해서 생기는 퍼짐이고, 문턱을 넘어 떨어진 것만 데이터가 심은 구조이며, 문턱 아래의 신호는 실재해도 스펙트럼으로는 보이지 않습니다. 이것으로 「대규모 선형대수」 단원 A2를 닫습니다. 지난 글의 스케치와 이 글의 크릴로프 방법은 둘 다 「표본 몇 개로 큰 행렬을 읽는다」는 일이었고, 그 표본이 얼마나 믿을 만한지는 Hutchinson 분산처럼 한 번씩 직접 계산했습니다. 다음 글 「고급 8번 · 집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가」는 A3 「확률 부등식과 일반화」 단원을 열며, 그 계산을 회프딩·번스타인 부등식이라는 일반적인 도구로 바꿉니다.
읽어주셔서 감사합니다. 😊

