7B 모델에 LoRA 어댑터를 붙이려는 팀이 있습니다. 어댑터 두 행렬을 0과 작은 난수로 시작하는 대신, PiSSA 방식으로 사전학습 가중치의 상위 특잇값 방향에서 시작하기로 했습니다. 가중치 를 로 쪼개 앞쪽을 어댑터로 넘기고 뒤쪽 잔차를 얼린다는 계획입니다. 계수는 이고, 한 층의 MLP down_proj 가중치는 입니다. 어댑터를 붙일 행렬이 층마다 일곱 개, 층이 서른둘이라 224번의 분해가 필요합니다. 첫 시도로 torch.linalg.svd 를 그대로 불렀더니 행렬 하나마다 4096개의 특잇값과 특이벡터를 전부 계산합니다. 정작 쓰는 것은 그중 16개입니다. 한편 PEFT 라이브러리 문서는 init_lora_weights 에 pissa_niter_4 처럼 숫자를 붙이면 전체 SVD 대신 빠른 SVD로 초기화하고, 그 숫자가 부분공간 반복(subspace iteration)의 횟수라고 적어 둡니다.
리뷰에서 질문이 셋 나옵니다. 첫째, 전체 분해 대신 무작위로 몇 번 곱한 결과를 쓰면 얼마나 빨라지고 얼마나 틀리나요. 둘째, 「4번 반복」의 4는 어디서 나온 수이고 0이면 무엇이 무너지나요. 셋째, 무작위로 줄인 행렬이 원래 행렬의 스펙트럼을 지킨다는 보장은 무엇에 기대나요. 이 글은 그 셋에 답합니다. 큰 행렬을 작은 무작위 행렬로 줄이는 스케치를 정의하고, 줄인 행렬이 원래 열공간을 보존한다는 것을 행렬 집중부등식으로 보장한 뒤, 그 위에 무작위 SVD를 세웁니다. 「중급 16번 · 저계수 근사와 에카르트-영: LoRA의 r을 스펙트럼으로 고르기」가 세운 최적 저계수 근사를 수십억 파라미터 위에서 실제로 계산하는 절차가 목표입니다.
연산량
전체 SVD
「중급 15번 · 특잇값 분해: 모든 행렬을 회전-늘림-회전으로 쪼개고 랭크를 읽기」에서 행렬은 언제나 로 쪼개졌습니다. 와 의 열은 정규직교이고 의 대각에 특잇값 이 내림차순으로 놓입니다. 그 분해를 계산하는 표준 절차는 골럽–카한 방식입니다. 행렬을 직교 변환으로 양쪽에서 깎아 이중대각 행렬로 만든 뒤 그 작은 문제를 반복으로 풉니다. 깎는 단계가 행렬 전체를 번 훑으므로 연산량이 에 비례합니다.
상수까지 적으면 일 때 얇은 와 를 함께 구하는 비용이 대략 번의 부동소수점 연산입니다. down_proj 는 전치해서 , 으로 넣으면 되고, 그 값이 입니다. 모델 전체의 224개 행렬을 다 더하면 입니다. 게다가 이중대각화는 행렬-벡터 곱 위주라 GPU가 가장 잘하는 큰 행렬곱으로 바뀌지 않습니다. 같은 연산 수라도 실제 시간은 행렬곱보다 훨씬 깁니다.
상위 k개
필요한 것이 상위 개뿐이라면 이 비용의 대부분은 버려집니다. 중급 16번의 에카르트–영 정리는 계수 인 행렬 가운데 에 가장 가까운 것이 , 곧 상위 개의 특잇값과 특이벡터만 남긴 행렬이라고 말했습니다. 그 오차는 행렬이 단위 벡터를 가장 길게 늘리는 배수, 곧 가장 큰 특잇값인 스펙트럼 노름으로 재면 이고, 성분 제곱합의 제곱근인 프로베니우스 노름으로 재면 입니다. 나머지 4080개의 특이벡터는 이 최적해를 적는 데 한 번도 쓰이지 않습니다.
개의 방향만 찾는 데 드는 최소 비용은 행렬을 몇 번 읽는 것입니다. 에 행렬을 곱하면 번의 연산이 들고, 이 보다 조금 큰 수라면 이것이 전체 분해와 견줄 단위가 됩니다. 상수를 다 빼고 세면 둘의 비는
이고, down_proj 에서 로 두면 배입니다. 뒤에서 만들 알고리즘은 이 행렬곱을 번 하는데, 상수를 넣어 세면 에서도 행렬 하나에 이라 전체 분해의 109분의 1이고, 모델 전체로는 입니다. 문제는 그렇게 적게 읽고도 상위 개를 정확히 잡을 수 있느냐는 것입니다.
스케치
큰 행렬 를 작은 행렬 와 곱해 크기를 줄인 결과를 의 스케치라 부르고, 를 스케치 행렬이라 부릅니다. 왼쪽에서 곱하는 는 행의 수를, 오른쪽에서 곱하는 는 열의 수를 줄입니다. 「중급 66번 · 랜덤 사영과 존슨–린덴스트라우스 보조정리」의 랜덤 사영이 바로 왼쪽 스케치였습니다. 점 개를 차원으로 사영해도 모든 쌍의 거리가 배 안에 남았습니다.
이 글에서 스케치가 지켜야 할 것은 점 몇 개의 거리가 아니라 행렬의 스펙트럼입니다. 그것은 무한히 많은 벡터에 대한 약속이라 존슨–린덴스트라우스를 점마다 쓰고 합집합 한계로 묶는 방식으로는 바로 나오지 않습니다. 무작위 행렬의 고윳값이 기댓값 근처에 모인다는, 한 단계 위의 집중이 필요합니다.
행렬 집중부등식
스칼라 베른슈타인
출발점은 스칼라 부등식 하나입니다. 독립인 실수 확률변수 가 평균이 0이고 이며 분산의 합이 이면
입니다. 베른슈타인 부등식이라 부르고, 「고급 8번 · 집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가」에서 증명합니다. 읽는 법만 짚습니다. 가 작으면 분모의 가 이겨 꼬리가 정규분포처럼 로 줄고, 가 크면 이 이겨 지수분포처럼 로 줄어듭니다. 지난 글의 아주마–회프딩 부등식이 차분의 범위만 썼다면, 이것은 분산까지 써서 더 날카롭습니다.
행렬 베른슈타인
이제 를 대칭 행렬로 바꿉니다. 독립이고 , 이라 합시다. 여기서 는 앞의 스펙트럼 노름이고, 대칭 행렬에서는 절댓값이 가장 큰 고윳값과 같습니다. 분산 자리에는 행렬 의 스펙트럼 노름을 둡니다. 그러면 행렬 베른슈타인 부등식은
입니다. 스칼라 식과 비교하면 절댓값이 스펙트럼 노름으로, 분산이 행렬 분산의 노름으로 바뀌었고, 앞에 차원 가 하나 붙었습니다. 이렇게 독립인 무작위 행렬의 합이 기댓값 근처에 모인다는 부등식들을 통틀어 행렬 집중부등식이라 부르고, 아래의 체르노프 판과 함께 이 글의 모든 보장이 여기에 기댑니다. 기댓값으로 적으면
입니다. 직사각 행렬 이면 를 로 바꾸고 를 와 중 큰 값으로 둡니다.
증명은 이 글의 몫이 아닙니다. 줄기만 적으면, 스칼라 증명의 지수 모멘트 를 대각합 로 바꾸고, 행렬끼리는 라 막히는 자리를 리브의 오목성 정리로 넘깁니다. 대각합이 고윳값 개를 더하므로 그 대가가 앞의 입니다. 차원이 지수 안이 아니라 밖에 붙는다는 점이 중요합니다. 꼬리 확률을 로 맞추려면 만 더 치르면 됩니다.
행렬 체르노프
양의 준정부호 행렬의 합에는 더 쓰기 쉬운 형태가 있습니다. 독립인 행렬 이 이고, 기댓값의 합의 가장 작은 고윳값을 , 가장 큰 것을 라 합시다. 행렬 체르노프 부등식은 에서
입니다. 동전 던지기의 체르노프 부등식에서 「앞면 수」 자리에 고윳값이 들어간 꼴입니다. 비율 이 핵심입니다. 합에 든 항 하나가 기댓값 전체에 견줘 얼마나 큰가를 재는 수이고, 그 비가 보다 충분히 크면 극단 고윳값이 둘 다 기댓값의 배 안에 묶입니다.
무작위 특징의 개수
행렬 베른슈타인의 사용법을 하나 봅니다. 길이 인 시퀀스의 커널 행렬 를, 무작위로 뽑은 특징 벡터 의 바깥곱 평균으로 근사한다고 합시다. Performer가 소프트맥스 어텐션을 근사하는 방식이 이 꼴입니다. 이고 라 하면 개로 만든 근사는 입니다.
오차를 , 로 적으면 평균이 0인 독립 대칭 행렬의 합입니다. 이니 이고, 이라 입니다. 상대 오차 를 넣고 꼬리를 이하로 누르면
를 얻습니다. , , , 이면 약 29,000개입니다. 이 식에서 읽을 것은 숫자보다 모양입니다. 시퀀스 길이는 로그로만 들어오고, 비용을 정하는 것은 특징 하나의 크기와 행렬 전체 크기의 비 입니다. 행렬 체르노프의 과 같은 역할을 하는 수입니다.
부분공간 임베딩
정의
행렬 () 의 열공간을 지키는 스케치를 정의합니다. 행렬 가 모든 에서
를 만족하면 의 열공간에 대한 -부분공간 임베딩이라 부릅니다. 열공간의 벡터 는 무한히 많지만 모두 차원 부분공간 안에 있으므로, 이 조건은 행렬 하나의 고윳값 조건으로 바뀝니다. 열공간의 정규직교 기저를 () 로 잡으면 , 이고, 조건은
과 같습니다. 곧 의 특잇값이 모두 안에 있다는 말입니다. 존슨–린덴스트라우스가 점 집합의 거리를 지켰다면 이것은 부분공간 위의 모든 거리를 지킵니다. 그래서 최소제곱 를 로 바꿔 풀어도 잔차가 배 안에 남습니다. 의 열공간에 임베딩을 걸면 되기 때문입니다.
레버리지 점수
가장 단순한 스케치는 행을 몇 개 뽑는 것입니다. 그런데 행마다 중요도가 다릅니다. 의 번째 행의 길이 제곱 을 번째 행의 레버리지 점수라 부릅니다. 합이 이고 각각은 0과 1 사이입니다. 점수가 1에 가까운 행은 그 행 없이는 열공간의 한 방향이 사라지는 행입니다. 그래서 레버리지 점수는 를 어떻게 잡든 열공간 하나로 정해지는 양이고, 그 행을 빼면 열공간이 얼마나 무너지는가를 잽니다.
행 를 확률 로 번 독립으로 뽑아 로 늘려 쌓은 것을 라 하면
입니다. 각 는 계수 1인 양의 준정부호 행렬이고 이며, 기댓값의 합은 라 입니다. 행렬 체르노프 두 줄을 합치면 실패 확률이 이하이고, 이를 로 누르는 표본 수는
입니다. 행을 고르게 뽑으면 이라 가 되고, 필요한 가 에 비례합니다. 레버리지 점수가 고르면 라 손해가 없지만, 한 행에 몰려 있으면 에 가까워져 표본을 거의 다 뽑아야 합니다. 이 비율 를 열공간의 결맞음이라 부릅니다.
오블리비어스 스케치
레버리지 점수를 정확히 구하려면 가 있어야 하고, 를 구하는 일이 처음 풀려던 문제입니다. 그래서 실무의 스케치는 를 보지 않고 분포를 정합니다. 와 무관한 분포에서 를 뽑아 고정된 마다 높은 확률로 임베딩이 되는 것을 오블리비어스 스케치라 부릅니다. 데이터가 들어오기 전에 를 정해 둘 수 있고, 스트림으로 들어오는 행렬에도 쓸 수 있다는 뜻입니다.
대표는 성분이 독립 인 가우스 행렬입니다. 회전 불변이라 는 와 무관하게 가우스 행렬과 같은 분포이고, 그 특잇값은 대략 사이에 놓입니다. 이면 충분하고, 결맞음이 아예 문제가 되지 않습니다. 대가는 비용입니다. 를 만드는 데 번의 곱이 들어, 줄이기 전보다 오히려 비싸질 수 있습니다.
카운트 스케치와 SRHT
곱셈을 줄인 오블리비어스 스케치가 둘 있습니다. 카운트 스케치는 열마다 무작위로 고른 한 행에만 을 둔 행렬입니다. 원래 행 를 무작위 칸 에 무작위 부호 를 붙여 더해 넣는 것이고, 를 만드는 비용이 의 0 아닌 성분 수와 같습니다. 대신 칸끼리 부딪히는 일을 막으려면 개의 칸이 필요합니다.
SRHT는 결맞음을 먼저 없애고 나서 고르게 뽑는 스케치입니다. 정식 이름은 부분표본 무작위 아다마르 변환이고, 로 적습니다. 는 대각에 무작위 부호를 둔 행렬, 는 성분이 인 정규화 아다마르 행렬, 은 개의 행을 고르게 뽑는 행렬입니다. 는 직교 변환이라 열공간의 기하를 바꾸지 않으면서 레버리지 점수를 고르게 폅니다. 높은 확률로 가 되고, 그다음의 고른 추출에 위의 체르노프 계산이 그대로 섭니다. 를 곱하는 일은 고속 푸리에 변환과 같은 나비 구조로 번에 끝납니다.
결맞음이 큰 행렬로 넷을 견줍니다. 행렬의 위쪽 스무 행에 큰 값을 얹어 레버리지 점수의 최댓값을 0.996으로 만들었습니다. 평균 의 200배입니다.
import numpy as np
rng = np.random.default_rng(1)
n, d, s = 4096, 20, 400
X = rng.standard_normal((n, d))
X[:d] += 1000 * np.eye(d) # 위쪽 스무 줄에 무게가 몰린 행렬
U, _ = np.linalg.qr(X) # 열공간의 정규직교 기저
lev = (U ** 2).sum(axis=1) # 레버리지 점수, 합은 d
print(f"max leverage {lev.max():.3f} (평균 {d / n:.4f})")
def fwht(A): # 정규화한 아다마르 변환, n log n
A = A.copy(); h = 1
while h < len(A):
a = A.reshape(-1, 2, h, A.shape[1])
a[:, 0], a[:, 1] = a[:, 0] + a[:, 1], a[:, 0] - a[:, 1]
h *= 2
return A / np.sqrt(len(A))
def sv(SU):
x = np.linalg.svd(SU, compute_uv=False)
return f"[{x.min():.3f}, {x.max():.3f}]"
G = rng.standard_normal((s, n)) / np.sqrt(s)
print("gaussian ", sv(G @ U))
rows = rng.integers(0, s, n); signs = rng.choice([-1.0, 1.0], n)
CU = np.zeros((s, d)); np.add.at(CU, rows, signs[:, None] * U)
print("count sketch", sv(CU))
HDU = fwht(signs[:, None] * U)
print(f"max leverage after HD {(HDU ** 2).sum(axis=1).max():.4f}")
pick = rng.choice(n, s, replace=False)
print("SRHT ", sv(np.sqrt(n / s) * HDU[pick]))
print("uniform rows", sv(np.sqrt(n / s) * U[pick]))
# max leverage 0.996 (평균 0.0049)
# gaussian [0.804, 1.186]
# count sketch [0.981, 1.022]
# max leverage after HD 0.0055
# SRHT [0.757, 1.217]
# uniform rows [0.054, 3.194]
가우스와 SRHT는 근처에 섭니다. 고른 행 추출은 스무 개의 무거운 행 가운데 몇 개만 건져 가장 작은 특잇값이 0.054로 꺼졌습니다. 그 방향의 길이를 거의 잃은 것입니다. 같은 고른 추출이 를 거친 뒤에는 멀쩡한데, 레버리지의 최댓값이 0.996에서 0.0055로 내려왔기 때문입니다. 로 세면 4080에서 22.5로, 과 거의 같아졌습니다. , 로 체르노프 식에 넣으면 필요한 표본 수가 을 넘는 40만에서 2,200으로 내려옵니다. 실제로는 400개로 충분했으니 상수는 넉넉하고, 식이 맞히는 것은 결맞음에 비례한다는 모양입니다. 카운트 스케치가 유난히 좋은 것은 무거운 스무 행이 거의 다른 칸에 떨어진 덕입니다.
무작위 SVD
레인지 파인더
이제 오른쪽 스케치로 돌아갑니다. 목표는 행렬 의 열공간에서 큰 특잇값 쪽의 차원을 담는 정규직교 행렬 () 를 찾는 것입니다. 찾고 나면 이고, 오차 가 에 가까울수록 좋습니다. 이 일을 하는 절차를 레인지 파인더라 부르고, 무작위 판은 두 줄입니다.
여기서 는 가우스 행렬이고 입니다. 의 각 열은 의 열공간에서 뽑은 무작위 벡터이고, 특잇값 분해로 적으면 입니다. 계수 가 모두 같은 분포의 가우스이니 큰 의 방향이 더 많이 섞입니다. 그런 벡터 개가 생성하는 공간은 위쪽 개 방향을 거의 다 품습니다. 여분 를 과표본이라 부르고, 보통 5에서 20 사이를 씁니다. 정확히 개만 뽑으면 무작위 벡터 하나가 어떤 방향과 거의 수직일 확률이 무시할 수 없지만, 몇 개를 더 뽑으면 그 확률이 지수적으로 사라집니다.
알고리즘
를 얻은 뒤에는 작은 행렬로 결정적인 분해를 합니다. 무작위 SVD의 전체 절차는 다섯 걸음입니다.
- 가우스 행렬 를 뽑습니다.
- 를 계산합니다. 연산 입니다.
- 를 QR 분해해 를 얻습니다. 연산 입니다.
- 를 계산합니다. 행렬이고 연산 입니다.
- 를 분해하고 로 되돌립니다. 연산 입니다.
마지막 걸음이 성립하는 것은 이고, 의 열이 다시 정규직교이기 때문입니다. 근사 의 특잇값 분해를 정확히 얻은 셈이고, 거기서 상위 개를 잘라 냅니다. 전체 분해가 하던 일 가운데 의 크기에 비례하는 부분은 걸음 2와 4의 행렬곱 둘로 줄었고, 분해 자체는 의 작은 행렬 위에서만 일어납니다.
오차 상계
헬코–마티손–트롭은 가우스 와 에서 다음을 보였습니다.
첫 줄의 오른쪽에서 는 에카르트–영의 최적 오차입니다. 무작위 레인지 파인더는 최적의 배 안에 들고, , 이면 그 배수가 1.438입니다. 를 키우면 1로 다가갑니다. 둘째 줄은 사정이 다릅니다. 첫 항은 최적값 의 상수배이지만, 둘째 항에는 꼬리 전체의 프로베니우스 노름이 들어 있습니다. 스펙트럼이 빨리 줄면 그 항이 과 비슷해 문제가 없고, 천천히 줄면 꼬리의 합이 보다 몇 배 커져 상계가 느슨해집니다. 다음 절의 거듭제곱 반복이 이 둘째 항을 겨냥합니다.
오차 상계에 차원 과 이 하나도 없다는 점을 짚어 둡니다. 행렬이 4096행이든 400만 행이든 보장은 , , 그리고 스펙트럼의 모양으로만 정해집니다. 큰 행렬을 줄여도 스펙트럼의 위쪽이 남는 이유가 이 식입니다.
증명 개요
의 특잇값 분해를 위쪽 개와 나머지로 가릅니다. 이고, 스케치도 같은 좌표로 (), 로 나눕니다. 증명은 두 단계입니다.
첫 단계는 확률이 없는 부등식입니다. 이 행 계수가 꽉 차 있으면, 곧 오른쪽 역 가 있으면
입니다. 여기서 는 의 열공간으로의 사영입니다. 줄기는 이렇습니다. 의 열공간이 의 열공간 안에 있으므로 그쪽으로 사영한 오차가 더 큽니다. 그런데 의 윗블록이 그대로라, 위쪽 방향은 정확히 잡히고 아래 블록 만큼만 옆으로 샙니다. 그 샘이 오차에 더해지는 몫이 둘째 항입니다. 이 부등식은 어떤 에도 섭니다.
둘째 단계에서 가우스의 성질을 씁니다. 가 직교라 과 는 서로 독립인 가우스 행렬입니다. 독립인 가우스 와 고정 행렬 에서 이고, 가우스의 유사역행렬은 입니다. 앞의 것은 성분별 분산을 더한 것이고, 뒤의 것은 역위샤트 분포의 평균에서 나옵니다. 프로베니우스 판의 첫 단계 부등식에 을 고정한 채 로 먼저 평균을 내면
이고, 젠센 부등식으로 제곱근을 씌우면 첫 줄의 상계입니다. 스펙트럼 노름 판은 같은 줄기에서 를 쓰면 나옵니다. 이면 가 발산한다는 것이 과표본이 필요한 이유의 정확한 형태입니다. 정사각 가우스 행렬은 특잇값이 0 가까이 내려가는 일이 너무 잦습니다.
거듭제곱 반복
느린 감쇠
사전학습 가중치의 스펙트럼은 대개 천천히 줄어듭니다. 위쪽 몇 개가 크고 그 아래로 긴 꼬리가 이어집니다. 실험용으로 행렬을 이 되게 만들어 봅니다. down_proj 의 가로세로를 반씩 줄인 크기입니다. 에서 인데 꼬리의 프로베니우스 노름은 으로 아홉 배입니다. 스펙트럼 상계의 둘째 항이 첫째 항을 네 배 넘게 압도하고, 상계 전체가 의 10.7배가 됩니다.
실제로 돌려 보면 상계만큼 나쁘지는 않지만 느린 감쇠의 값은 분명히 치릅니다. 과표본 16의 무작위 SVD로 얻은 계수 16 근사의 스펙트럼 오차가 최적의 1.815배이고, 16번째 특잇값은 40%나 작게 나옵니다. 이유는 레인지 파인더의 설명 그대로입니다. 무작위 벡터 에서 의 몫은 에 비례하고, 그 아래 2000개 방향이 각각 0.24에서 0.02 사이의 몫으로 섞여 들어옵니다. 하나하나는 작아도 합치면 위쪽 방향을 가립니다.
거듭제곱 보정
처방은 스펙트럼을 날카롭게 만든 행렬로 스케치하는 것입니다.
를 쓰면 는 와 같은 특이벡터를 갖고 특잇값만 로 바뀝니다. 비 가 제곱으로 줄어드니 꼬리가 위쪽을 가리는 힘이 빠르게 사라집니다. 이 절차를 거듭제곱 반복이라 부릅니다. 「중급 13번 · 행렬 거듭제곱과 거듭제곱법: 스펙트럼 반지름이 정하는 것」의 거듭제곱법이 벡터 하나를 로 거듭 곱해 가장 큰 고유벡터를 찾았다면, 이것은 벡터 개짜리 블록을 거듭 곱해 위쪽 차원 부분공간을 찾는 판이라 부분공간 반복이라고도 부릅니다. PEFT 문서가 말하는 부분공간 반복이 이것이고 pissa_niter_4 는 입니다.
보장도 그대로 올라갑니다. 앞의 상계를 에 쓰고 「」를 이으면
입니다. 대괄호 안의 꼬리 합은 의 합이라 빨리 줄고, 바깥의 제곱이 남은 상수배를 1 쪽으로 끌어당깁니다. 대가는 행렬곱이 번 늘어나는 것이고, 앞의 연산량 계산에서 가 그것입니다.
그림의 오른쪽이 한 번의 반복으로 거의 다 해결된다는 것을 보여 줍니다. 에서 스펙트럼 오차가 최적의 1.004배로 내려오고, 그다음부터는 특잇값 자체의 정확도가 한 자리씩 오릅니다. 16번째 특잇값의 상대 오차가 에서 , , , 입니다. PiSSA처럼 특이벡터를 초기값으로 쓰는 일이라면 근사 오차가 최적에 닿은 이나 2로도 충분하고, 4는 넉넉한 쪽의 선택입니다.
재직교화
를 식 그대로 계산하면 안 됩니다. 곱할 때마다 각 방향의 크기가 배로 늘어, 면 위쪽 방향과 16번째 방향의 크기 비가 이 됩니다. 꼬리 쪽 방향과는 더 벌어집니다. 배정밀도의 유효 숫자가 16자리 남짓이라 작은 방향의 정보가 반올림에 묻히고, 열들이 사실상 같은 벡터로 무너집니다.
그래서 곱할 때마다 QR로 다시 정규직교화합니다.
정확한 산술에서는 열공간이 같으므로 결과가 바뀌지 않고, 유한 정밀도에서는 매번 크기를 1로 되돌려 작은 방향을 지킵니다. QR 한 번은 이라 행렬곱 에 견줘 배로 작습니다. 정밀도를 반으로 낮춘 bf16 가중치라면 이 걱정이 훨씬 커지므로, 분해는 fp32로 올려서 합니다.
나이스트룀 근사와 CUR
나이스트룀 근사
대칭 양의 준정부호 행렬 () 에는 스케치를 한쪽에만 곱해도 되는 근사가 있습니다. 스케치 와 작은 행렬 로
를 두는 것을 나이스트룀 근사라 부릅니다. 를 열 선택 행렬로 잡으면 는 의 열 몇 개이고 는 그 열과 행이 만나는 작은 블록입니다. 커널 행렬이라면 원소 개만 계산하면 되고 나머지 개는 보지도 않습니다.
이 근사는 언제나 아래에서 다가갑니다. 로 적으면 이고, 는 의 열공간으로의 사영이라 입니다. 고른 열을 앞으로 모아 로 쓰면 오차가 정확히 이고, 이 블록을 에 대한 슈어 보수라 부릅니다. 가우스 과정에서 고른 점들을 관측한 뒤 남은 점들의 조건부 공분산과 같은 식입니다. 무작위 SVD와의 관계도 이 꼴에서 보입니다. 를 가우스로 잡으면 나이스트룀 근사는 에 레인지 파인더를 건 것과 같고, 오차 상계도 앞 절의 식을 따라갑니다.
어텐션 근사
길이 의 어텐션 행렬 는 원소라 긴 문맥에서 비용을 지배합니다. 효율 어텐션 셋이 이 절의 도구로 그것을 줄입니다. Linformer는 키와 값을 시퀀스 길이 방향으로 행렬로 사영해 어텐션을 계산합니다. 왼쪽 스케치 그 자체이고, 논문의 근사 보장 절이 존슨–린덴스트라우스로 어텐션 행렬이 저계수에 가깝다는 것을 보입니다. Performer는 소프트맥스 커널을 양수 무작위 특징의 바깥곱 평균으로 바꿉니다. 앞의 무작위 특징의 개수 계산이 그 근사 오차를 재는 틀입니다. Nyströmformer는 쿼리와 키의 구간 평균으로 표지점 몇 개를 잡아 나이스트룀 꼴 로 어텐션을 적습니다. 소프트맥스 행렬은 대칭이 아니라 위의 양의 준정부호 보장이 그대로 서지는 않고, 그래서 세 조각을 따로 소프트맥스로 만듭니다.
셋은 무엇을 줄이느냐가 다릅니다. Linformer는 길이 방향을 섞어 줄이고, Performer는 커널을 무작위 특징으로 펴고, Nyströmformer는 실제 위치 몇 개를 고릅니다. 세 논문의 근사 오차 절을 읽을 때 물어야 할 것은 같습니다. 어느 노름으로 재는지, 상수에 무엇이 숨어 있는지, 그리고 이 절의 나 결맞음 같은 비율이 실제 어텐션에서 얼마인지입니다.
CUR 분해
일반 직사각 행렬에서 실제 열과 행을 고르는 판이 CUR 분해입니다. 의 열 개로 를, 행 개로 을 만들고 가운데를
로 둡니다. 와 이 각각 의 열공간과 의 행공간으로의 사영이라 이고, 이것은 고른 열공간과 행공간 안에서 가장 좋은 근사입니다. 특잇값 분해의 특이벡터는 모든 열을 섞은 추상적 방향이지만 와 은 데이터에 실제로 있는 열과 행이라 해석할 수 있고, 희소 행렬이면 희소성이 그대로 남습니다.
어느 열을 고르느냐가 품질을 정하고, 여기서도 답은 레버리지 점수입니다. 위쪽 개 오른쪽 특이벡터 의 행 길이 제곱에 비례하는 확률로 열을 개 뽑고 같은 식으로 행을 뽑으면, 높은 확률로 입니다. 체르노프 계산이 부분공간 임베딩에서 한 일과 같은 일을 합니다. 레버리지 점수는 다시 를 요구하므로 실무에서는 무작위 SVD로 어림한 에서 점수를 읽습니다.
다시 PiSSA 초기화로
절차
첫머리의 세 질문에 답합니다. 첫째, down_proj 하나의 상위 16개를 과표본 16, 반복 4번으로 구하면 큰 행렬에 닿는 연산이 행렬곱 열 번이고, 전체 분해의 에 견줘 입니다. 오차는 헬코–마티손–트롭의 상계가 묶고, 그 상계에는 행렬의 크기가 없습니다. 둘째, 4는 사전학습 가중치의 스펙트럼이 천천히 줄기 때문에 필요한 거듭제곱 반복의 수입니다. 0이면 꼬리 수천 개 방향이 위쪽 방향을 가려 16번째 특잇값이 40% 틀립니다. 셋째, 무작위 스케치가 열공간을 지킨다는 보장은 행렬 집중부등식에 기대고, 그 부등식은 스칼라 집중을 스펙트럼 노름으로 올리면서 차원의 로그만 더 치릅니다.
수십억 파라미터 모델 전체에 쓰는 절차는 이렇게 정리됩니다.
- 행렬마다 시드를 정해 를 그 자리에서 만듭니다. 저장할 필요가 없습니다.
- 가중치를 fp32로 올리고, 메모리가 모자라면 열 블록마다 로 쌓습니다. 큰 행렬을 한 번 훑는 일입니다.
- 반복마다 와 를 블록으로 계산하고 QR로 다시 정규직교화합니다. 반복 한 번이 행렬을 두 번 훑습니다.
- 를 계산해 의 작은 분해를 하고, , , 을 잘라 어댑터 두 행렬 와 으로 나눕니다.
- 잔차 를 원래 정밀도로 되돌려 얼립니다.
행렬을 훑는 횟수는 번이고, 이 수가 GPU 메모리에 다 안 올라가는 행렬에서 비용을 정합니다. LoRA-XS처럼 위쪽 특이벡터를 얼리고 그 사이의 행렬만 학습하는 방법도 같은 절차의 4단계까지를 그대로 씁니다.
코드로 확인하기
down_proj 의 가로세로를 반씩 줄인 행렬에 느린 스펙트럼 을 심고, 전체 분해와 반복 수가 다른 무작위 SVD를 견줍니다. 특이벡터를 알고 만든 행렬이라 오차를 정확히 잴 수 있습니다.
import time
import numpy as np
rng = np.random.default_rng(0)
m, n, k, p = 2048, 5504, 16, 16 # 4096×11008 의 가로세로를 반씩
sig = np.arange(1, m + 1) ** -0.5 # 천천히 줄어드는 스펙트럼
U0, _ = np.linalg.qr(rng.standard_normal((m, m)))
V0, _ = np.linalg.qr(rng.standard_normal((n, m)))
W = (U0 * sig) @ V0.T # W = U diag(σ) Vᵀ
def rsvd(A, k, p, q, rng):
Y = A @ rng.standard_normal((A.shape[1], k + p)) # 스케치 Y = AΩ
Q, _ = np.linalg.qr(Y)
for _ in range(q): # 거듭제곱 반복, 매번 다시 직교화
Q, _ = np.linalg.qr(A.T @ Q)
Q, _ = np.linalg.qr(A @ Q)
B = Q.T @ A # (k+p)×n 의 작은 행렬
Ub, s, Vt = np.linalg.svd(B, full_matrices=False)
return Q @ Ub[:, :k], s[:k], Vt[:k], Q
t = time.perf_counter(); s_full = np.linalg.svd(W, compute_uv=True)[1]
print(f"full SVD {time.perf_counter() - t:5.2f} s")
tail = np.sqrt((sig[k:] ** 2).sum())
print(f"sigma_k+1 = {sig[k]:.4f}, tail_F = {tail:.4f}")
rsvd(W, k, p, 0, rng) # 첫 호출의 준비 시간을 빼려고 한 번 돌린다
for q in [0, 1, 2, 4]:
t = time.perf_counter(); Uk, sk, Vk, Q = rsvd(W, k, p, q, rng); dt = time.perf_counter() - t
E = U0 * sig - (Uk * sk) @ (Vk @ V0) # (W - W_k) V0, 노름은 그대로다
e2 = np.linalg.norm(E, 2) / sig[k] # 1 이 에카르트–영의 최적
R = U0 * sig - Q @ (Q.T @ (U0 * sig)) # (I - QQᵀ)W, 레인지 파인더의 오차
rF = np.linalg.norm(R) / tail # HMT 상계 1.438
rel = np.abs(sk - sig[:k]) / sig[:k]
print(f"q={q} {dt:5.2f} s range_F {rF:.3f} rank_k {e2:.3f} "
f"s1 {rel[0]:.0e} s16 {rel[-1]:.0e}")
# full SVD 6.79 s
# sigma_k+1 = 0.2425, tail_F = 2.1958
# q=0 0.04 s range_F 1.106 rank_k 1.815 s1 8e-02 s16 4e-01
# q=1 0.07 s range_F 0.946 rank_k 1.004 s1 2e-05 s16 4e-02
# q=2 0.11 s range_F 0.934 rank_k 1.001 s1 2e-08 s16 7e-03
# q=4 0.16 s range_F 0.930 rank_k 1.000 s1 1e-14 s16 7e-04
전체 분해가 6.79초, 반복 네 번의 무작위 SVD가 0.16초로 42배 차이입니다. 앞의 연산 수 식으로 이 크기를 세면 대 로 54배이니, 시간 비가 연산 비를 거의 따라갑니다. 시간은 기계마다 다르고 실행마다 조금씩 흔들립니다. range_F 는 레인지 파인더의 프로베니우스 오차를 꼬리 노름으로 나눈 값으로, 에서도 1.106이라 상계 1.438 안에 듭니다. 에서 1보다 작은 것은 가 32차원이라 16번째 너머의 방향까지 일부 담기 때문입니다. rank_k 는 잘라 낸 계수 16 근사의 스펙트럼 오차를 최적 로 나눈 값이고, 반복 한 번에 1.815에서 1.004로 내려와 에카르트–영의 최적에 닿습니다. 실제 down_proj 에서는 연산 비가 109배로 더 벌어지고, GPU 위에서는 이중대각화가 행렬곱만큼 빨라지지 않으므로 시간 차가 그보다 커지기 쉽습니다.
연습
가중치에서 , 의 무작위 SVD가 큰 행렬에 쓰는 연산과 전체 분해의 연산 () 을 비교해 몇 배 차이인지 구하세요.
전치해서 , 로 두면 전체 분해는 입니다. 무작위 SVD는 행렬곱 번에 한 번이 이라 입니다. 비는 약 174배입니다.열이 개인 정규직교 기저에서 레버리지 점수로 행을 뽑습니다. 행렬 체르노프로 의 고윳값이 안에 들 확률을 0.99 이상으로 만드는 표본 수의 하한을 구하세요.
, 을 에 넣으면 라 입니다.무작위 레인지 파인더에서 일 때 프로베니우스 상계의 배수를 과표본 에서 구하고, 배수를 1.1 이하로 만드는 가장 작은 를 구하세요.
입니다. 이어야 하므로 , 곧 입니다.특잇값이 인 행렬에서 을 찾습니다. 거듭제곱 반복을 번 하면 비 이 무엇으로 바뀌는지 적고, 그 비를 0.1 이하로 만드는 가장 작은 를 구하세요.
비가 이 됩니다. 이어야 하므로 , 곧 입니다. 확인으로 이면 , 면 입니다. 간격이 이렇게 좁으면 거듭제곱보다 과표본을 늘리는 편이 쌉니다.에서 첫째와 셋째 열을 골라 나이스트룀 근사 를 구하고, 오차 가 슈어 보수와 같은지 확인하세요.
는 열 과 이고 라 입니다. 오차는 가운데 원소 하나가 1인 행렬입니다. 슈어 보수는 로 같고, 양수라 오차가 양의 준정부호입니다.
이 글이 세운 것은 한 문장으로 모입니다. 무작위로 줄인 행렬은 원래 행렬의 크기를 잊어도 스펙트럼의 위쪽을 기억하고, 그 기억이 얼마나 정확한지는 차원이 아니라 비율이 정합니다. 체르노프의 , 무작위 특징의 , 레버리지 점수의 결맞음, 그리고 거듭제곱 반복이 다듬는 가 모두 그 비율입니다. 다음 글 「고급 7번 · 란초스로 헤세 스펙트럼을 재고 랜덤 행렬로 잡음을 걷어 내기」는 블록 하나를 거듭 곱하던 이 글의 반복을 크릴로프 부분공간 전체를 쓰는 란초스 반복으로 넓혀, 행렬을 만들지 않고 헤세-벡터 곱만으로 스펙트럼 밀도를 그립니다. 그리고 그렇게 얻은 스펙트럼에서 무엇이 신호이고 무엇이 잡음인지를, 무작위 행렬의 특잇값이 따르는 마르첸코–파스투르 분포를 기준선으로 가립니다. 이 글의 가우스 스케치가 사이에 특잇값을 모았던 것이 바로 그 분포의 양 끝입니다.
읽어주셔서 감사합니다. 😊

