수학

MATH / 고급 6번

스케치와 행렬 집중부등식: 큰 행렬을 줄여도 스펙트럼이 남는 이유

행렬 베른슈타인·체르노프 부등식으로 무작위 스케치가 열공간을 보존하는 조건을 세우고, 레인지 파인더와 무작위 SVD의 알고리즘·오차 상계·거듭제곱 보정을 유도합니다. 4096×11008 가중치의 상위 16개 특잇값을 전체 분해의 백분의 일 연산으로 구해 PiSSA 초기화에 씁니다.

PALDYN Team56 MIN READ

7B 모델에 LoRA 어댑터를 붙이려는 팀이 있습니다. 어댑터 두 행렬을 0과 작은 난수로 시작하는 대신, PiSSA 방식으로 사전학습 가중치의 상위 특잇값 방향에서 시작하기로 했습니다. 가중치 WW 를 W=UrSrVr⊤+WresW = U_r S_r V_r^\top + W_{\mathrm{res}} 로 쪼개 앞쪽을 어댑터로 넘기고 뒤쪽 잔차를 얼린다는 계획입니다. 계수는 r=16r = 16 이고, 한 층의 MLP down_proj 가중치는 4096×110084096 \times 11008 입니다. 어댑터를 붙일 행렬이 층마다 일곱 개, 층이 서른둘이라 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번 · 특잇값 분해: 모든 행렬을 회전-늘림-회전으로 쪼개고 랭크를 읽기」에서 m×nm \times n 행렬은 언제나 W=UΣV⊤W = U \Sigma V^\top 로 쪼개졌습니다. UU 와 VV 의 열은 정규직교이고 Σ\Sigma 의 대각에 특잇값 σ1≥σ2≥⋯≥0\sigma_1 \ge \sigma_2 \ge \cdots \ge 0 이 내림차순으로 놓입니다. 그 분해를 계산하는 표준 절차는 골럽–카한 방식입니다. 행렬을 직교 변환으로 양쪽에서 깎아 이중대각 행렬로 만든 뒤 그 작은 문제를 반복으로 풉니다. 깎는 단계가 행렬 전체를 min⁡(m,n)\min(m, n) 번 훑으므로 연산량이 mn⋅min⁡(m,n)mn \cdot \min(m, n) 에 비례합니다.

상수까지 적으면 m≥nm \ge n 일 때 얇은 UU 와 VV 를 함께 구하는 비용이 대략 14mn2+8n314mn^2 + 8n^3 번의 부동소수점 연산입니다. down_proj 는 전치해서 m=11008m = 11008, n=4096n = 4096 으로 넣으면 되고, 그 값이 3.14×10123.14 \times 10^{12} 입니다. 모델 전체의 224개 행렬을 다 더하면 4.9×10144.9 \times 10^{14} 입니다. 게다가 이중대각화는 행렬-벡터 곱 위주라 GPU가 가장 잘하는 큰 행렬곱으로 바뀌지 않습니다. 같은 연산 수라도 실제 시간은 행렬곱보다 훨씬 깁니다.

상위 k개

필요한 것이 상위 kk 개뿐이라면 이 비용의 대부분은 버려집니다. 중급 16번의 에카르트–영 정리는 계수 kk 인 행렬 가운데 WW 에 가장 가까운 것이 Wk=UkΣkVk⊤W_k = U_k \Sigma_k V_k^\top, 곧 상위 kk 개의 특잇값과 특이벡터만 남긴 행렬이라고 말했습니다. 그 오차는 행렬이 단위 벡터를 가장 길게 늘리는 배수, 곧 가장 큰 특잇값인 스펙트럼 노름으로 재면 σk+1\sigma_{k+1} 이고, 성분 제곱합의 제곱근인 프로베니우스 노름으로 재면 (∑j>kσj2)1/2\bigl(\sum_{j > k} \sigma_j^2\bigr)^{1/2} 입니다. 나머지 4080개의 특이벡터는 이 최적해를 적는 데 한 번도 쓰이지 않습니다.

kk 개의 방향만 찾는 데 드는 최소 비용은 행렬을 몇 번 읽는 것입니다. WW 에 n×ℓn \times \ell 행렬을 곱하면 2mnℓ2mn\ell 번의 연산이 들고, ℓ\ell 이 kk 보다 조금 큰 수라면 이것이 전체 분해와 견줄 단위가 됩니다. 상수를 다 빼고 세면 둘의 비는

mn⋅min⁡(m,n)mnℓ=min⁡(m,n)ℓ\frac{mn \cdot \min(m, n)}{mn \ell} = \frac{\min(m, n)}{\ell}

이고, down_proj 에서 ℓ=32\ell = 32 로 두면 4096/32=1284096 / 32 = 128 배입니다. 뒤에서 만들 알고리즘은 이 행렬곱을 2q+22q + 2 번 하는데, 상수를 넣어 세면 q=4q = 4 에서도 행렬 하나에 2.9×10102.9 \times 10^{10} 이라 전체 분해의 109분의 1이고, 모델 전체로는 4.1×10124.1 \times 10^{12} 입니다. 문제는 그렇게 적게 읽고도 상위 kk 개를 정확히 잡을 수 있느냐는 것입니다.

스케치

큰 행렬 AA 를 작은 행렬 SS 와 곱해 크기를 줄인 결과를 AA 의 스케치라 부르고, SS 를 스케치 행렬이라 부릅니다. 왼쪽에서 곱하는 SASA 는 행의 수를, 오른쪽에서 곱하는 AΩA\Omega 는 열의 수를 줄입니다. 「중급 66번 · 랜덤 사영과 존슨–린덴스트라우스 보조정리」의 랜덤 사영이 바로 왼쪽 스케치였습니다. 점 NN 개를 s=O(log⁡N/ε2)s = O(\log N / \varepsilon^2) 차원으로 사영해도 모든 쌍의 거리가 1±ε1 \pm \varepsilon 배 안에 남았습니다.

이 글에서 스케치가 지켜야 할 것은 점 몇 개의 거리가 아니라 행렬의 스펙트럼입니다. 그것은 무한히 많은 벡터에 대한 약속이라 존슨–린덴스트라우스를 점마다 쓰고 합집합 한계로 묶는 방식으로는 바로 나오지 않습니다. 무작위 행렬의 고윳값이 기댓값 근처에 모인다는, 한 단계 위의 집중이 필요합니다.

행렬 집중부등식

스칼라 베른슈타인

출발점은 스칼라 부등식 하나입니다. 독립인 실수 확률변수 X1,…,XsX_1, \dots, X_s 가 평균이 0이고 ∣Xk∣≤L\lvert X_k \rvert \le L 이며 분산의 합이 v=∑kE[Xk2]v = \sum_k \mathbb{E}[X_k^2] 이면

P(∣∑kXk∣≥t)≤2exp⁡ ⁣(−t2/2v+Lt/3)P\Bigl( \Bigl\lvert \sum_k X_k \Bigr\rvert \ge t \Bigr) \le 2 \exp\!\left( \frac{-t^2/2}{v + Lt/3} \right)

입니다. 베른슈타인 부등식이라 부르고, 「고급 8번 · 집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가」에서 증명합니다. 읽는 법만 짚습니다. tt 가 작으면 분모의 vv 가 이겨 꼬리가 정규분포처럼 e−t2/2ve^{-t^2/2v} 로 줄고, tt 가 크면 Lt/3Lt/3 이 이겨 지수분포처럼 e−3t/2Le^{-3t/2L} 로 줄어듭니다. 지난 글의 아주마–회프딩 부등식이 차분의 범위만 썼다면, 이것은 분산까지 써서 더 날카롭습니다.

행렬 베른슈타인

이제 XkX_k 를 d×dd \times d 대칭 행렬로 바꿉니다. 독립이고 EXk=0\mathbb{E} X_k = 0, ∥Xk∥≤L\lVert X_k \rVert \le L 이라 합시다. 여기서 ∥⋅∥\lVert \cdot \rVert 는 앞의 스펙트럼 노름이고, 대칭 행렬에서는 절댓값이 가장 큰 고윳값과 같습니다. 분산 자리에는 행렬 ∑kE[Xk2]\sum_k \mathbb{E}[X_k^2] 의 스펙트럼 노름을 둡니다. 그러면 행렬 베른슈타인 부등식은

P(∥∑kXk∥≥t)≤2dexp⁡ ⁣(−t2/2v+Lt/3),v=∥∑kE[Xk2]∥P\Bigl( \Bigl\lVert \sum_k X_k \Bigr\rVert \ge t \Bigr) \le 2d \exp\!\left( \frac{-t^2/2}{v + Lt/3} \right), \qquad v = \Bigl\lVert \sum_k \mathbb{E}[X_k^2] \Bigr\rVert

입니다. 스칼라 식과 비교하면 절댓값이 스펙트럼 노름으로, 분산이 행렬 분산의 노름으로 바뀌었고, 앞에 차원 dd 가 하나 붙었습니다. 이렇게 독립인 무작위 행렬의 합이 기댓값 근처에 모인다는 부등식들을 통틀어 행렬 집중부등식이라 부르고, 아래의 체르노프 판과 함께 이 글의 모든 보장이 여기에 기댑니다. 기댓값으로 적으면

E∥∑kXk∥≤2vlog⁡(2d)+L3log⁡(2d)\mathbb{E} \Bigl\lVert \sum_k X_k \Bigr\rVert \le \sqrt{2v \log(2d)} + \frac{L}{3} \log(2d)

입니다. 직사각 행렬 d1×d2d_1 \times d_2 이면 2d2d 를 d1+d2d_1 + d_2 로 바꾸고 vv 를 ∥∑E[XkXk⊤]∥\lVert \sum \mathbb{E}[X_k X_k^\top] \rVert 와 ∥∑E[Xk⊤Xk]∥\lVert \sum \mathbb{E}[X_k^\top X_k] \rVert 중 큰 값으로 둡니다.

증명은 이 글의 몫이 아닙니다. 줄기만 적으면, 스칼라 증명의 지수 모멘트 Eeθ∑Xk\mathbb{E} e^{\theta \sum X_k} 를 대각합 tr E eθ∑Xk\mathrm{tr}\, \mathbb{E}\, e^{\theta \sum X_k} 로 바꾸고, 행렬끼리는 eA+B≠eAeBe^{A+B} \ne e^A e^B 라 막히는 자리를 리브의 오목성 정리로 넘깁니다. 대각합이 고윳값 dd 개를 더하므로 그 대가가 앞의 dd 입니다. 차원이 지수 안이 아니라 밖에 붙는다는 점이 중요합니다. 꼬리 확률을 η\eta 로 맞추려면 log⁡(2d/η)\log(2d/\eta) 만 더 치르면 됩니다.

행렬 체르노프

양의 준정부호 행렬의 합에는 더 쓰기 쉬운 형태가 있습니다. 독립인 d×dd \times d 행렬 Xk⪰0X_k \succeq 0 이 λmax⁡(Xk)≤L\lambda_{\max}(X_k) \le L 이고, 기댓값의 합의 가장 작은 고윳값을 μmin⁡=λmin⁡(∑kEXk)\mu_{\min} = \lambda_{\min}\bigl(\sum_k \mathbb{E} X_k\bigr), 가장 큰 것을 μmax⁡\mu_{\max} 라 합시다. 행렬 체르노프 부등식은 0≤δ≤10 \le \delta \le 1 에서

P(λmin⁡(∑kXk)≤(1−δ)μmin⁡)≤dexp⁡ ⁣(−δ2μmin⁡2L)P(λmax⁡(∑kXk)≥(1+δ)μmax⁡)≤dexp⁡ ⁣(−δ2μmax⁡3L)\begin{aligned} P\Bigl( \lambda_{\min}\Bigl(\sum_k X_k\Bigr) \le (1 - \delta)\mu_{\min} \Bigr) &\le d \exp\!\left( -\frac{\delta^2 \mu_{\min}}{2L} \right) \\ P\Bigl( \lambda_{\max}\Bigl(\sum_k X_k\Bigr) \ge (1 + \delta)\mu_{\max} \Bigr) &\le d \exp\!\left( -\frac{\delta^2 \mu_{\max}}{3L} \right) \end{aligned}

입니다. 동전 던지기의 체르노프 부등식에서 「앞면 수」 자리에 고윳값이 들어간 꼴입니다. 비율 μ/L\mu / L 이 핵심입니다. 합에 든 항 하나가 기댓값 전체에 견줘 얼마나 큰가를 재는 수이고, 그 비가 log⁡d\log d 보다 충분히 크면 극단 고윳값이 둘 다 기댓값의 1±δ1 \pm \delta 배 안에 묶입니다.

무작위 특징의 개수

행렬 베른슈타인의 사용법을 하나 봅니다. 길이 nn 인 시퀀스의 커널 행렬 KK 를, 무작위로 뽑은 특징 벡터 z∈Rnz \in \mathbb{R}^n 의 바깥곱 평균으로 근사한다고 합시다. Performer가 소프트맥스 어텐션을 근사하는 방식이 이 꼴입니다. E[zz⊤]=K\mathbb{E}[z z^\top] = K 이고 ∥z∥2≤B\lVert z \rVert^2 \le B 라 하면 mm 개로 만든 근사는 K^=1m∑kzkzk⊤\hat K = \frac{1}{m} \sum_k z_k z_k^\top 입니다.

오차를 K^−K=∑kXk\hat K - K = \sum_k X_k, Xk=(zkzk⊤−K)/mX_k = (z_k z_k^\top - K)/m 로 적으면 평균이 0인 독립 대칭 행렬의 합입니다. ∥K∥≤E∥z∥2≤B\lVert K \rVert \le \mathbb{E} \lVert z \rVert^2 \le B 이니 ∥Xk∥≤2B/m\lVert X_k \rVert \le 2B/m 이고, (zz⊤)2=∥z∥2zz⊤⪯Bzz⊤(z z^\top)^2 = \lVert z \rVert^2 z z^\top \preceq B z z^\top 이라 v≤B∥K∥/mv \le B \lVert K \rVert / m 입니다. 상대 오차 t=ε∥K∥t = \varepsilon \lVert K \rVert 를 넣고 꼬리를 η\eta 이하로 누르면

m≥2B∥K∥⋅1+2ε/3ε2⋅log⁡2nηm \ge \frac{2B}{\lVert K \rVert} \cdot \frac{1 + 2\varepsilon/3}{\varepsilon^2} \cdot \log \frac{2n}{\eta}

를 얻습니다. B/∥K∥=10B / \lVert K \rVert = 10, ε=0.1\varepsilon = 0.1, η=0.01\eta = 0.01, n=4096n = 4096 이면 약 29,000개입니다. 이 식에서 읽을 것은 숫자보다 모양입니다. 시퀀스 길이는 로그로만 들어오고, 비용을 정하는 것은 특징 하나의 크기와 행렬 전체 크기의 비 B/∥K∥B / \lVert K \rVert 입니다. 행렬 체르노프의 μ/L\mu / L 과 같은 역할을 하는 수입니다.

부분공간 임베딩

정의

n×dn \times d 행렬 AA (n≫dn \gg d) 의 열공간을 지키는 스케치를 정의합니다. s×ns \times n 행렬 SS 가 모든 x∈Rdx \in \mathbb{R}^d 에서

(1−ε)∥Ax∥2≤∥SAx∥2≤(1+ε)∥Ax∥2(1 - \varepsilon) \lVert A x \rVert^2 \le \lVert S A x \rVert^2 \le (1 + \varepsilon) \lVert A x \rVert^2

를 만족하면 AA 의 열공간에 대한 ε\varepsilon-부분공간 임베딩이라 부릅니다. 열공간의 벡터 y=Axy = Ax 는 무한히 많지만 모두 dd 차원 부분공간 안에 있으므로, 이 조건은 행렬 하나의 고윳값 조건으로 바뀝니다. 열공간의 정규직교 기저를 UU (n×dn \times d) 로 잡으면 y=Uzy = Uz, ∥y∥=∥z∥\lVert y \rVert = \lVert z \rVert 이고, 조건은

∥U⊤S⊤SU−Id∥≤ε\lVert U^\top S^\top S U - I_d \rVert \le \varepsilon

과 같습니다. 곧 SUSU 의 특잇값이 모두 [1−ε,1+ε][\sqrt{1 - \varepsilon}, \sqrt{1 + \varepsilon}] 안에 있다는 말입니다. 존슨–린덴스트라우스가 점 집합의 거리를 지켰다면 이것은 부분공간 위의 모든 거리를 지킵니다. 그래서 최소제곱 min⁡x∥Ax−b∥\min_x \lVert Ax - b \rVert 를 min⁡x∥S(Ax−b)∥\min_x \lVert S(Ax - b) \rVert 로 바꿔 풀어도 잔차가 1+O(ε)1 + O(\varepsilon) 배 안에 남습니다. [A,b][A, b] 의 열공간에 임베딩을 걸면 되기 때문입니다.

레버리지 점수

가장 단순한 스케치는 행을 몇 개 뽑는 것입니다. 그런데 행마다 중요도가 다릅니다. UU 의 ii 번째 행의 길이 제곱 ℓi=∥ui∥2\ell_i = \lVert u_i \rVert^2 을 ii 번째 행의 레버리지 점수라 부릅니다. 합이 ∥U∥F2=d\lVert U \rVert_F^2 = d 이고 각각은 0과 1 사이입니다. 점수가 1에 가까운 행은 그 행 없이는 열공간의 한 방향이 사라지는 행입니다. 그래서 레버리지 점수는 UU 를 어떻게 잡든 열공간 하나로 정해지는 양이고, 그 행을 빼면 열공간이 얼마나 무너지는가를 잽니다.

행 ii 를 확률 pi=ℓi/dp_i = \ell_i / d 로 ss 번 독립으로 뽑아 1/spi1/\sqrt{s p_i} 로 늘려 쌓은 것을 SUSU 라 하면

U⊤S⊤SU=∑k=1sXk,Xk=uikuik⊤s pikU^\top S^\top S U = \sum_{k=1}^{s} X_k, \qquad X_k = \frac{u_{i_k} u_{i_k}^\top}{s \, p_{i_k}}

입니다. 각 XkX_k 는 계수 1인 양의 준정부호 행렬이고 λmax⁡(Xk)=ℓi/(spi)=d/s\lambda_{\max}(X_k) = \ell_i / (s p_i) = d / s 이며, 기댓값의 합은 ∑iuiui⊤=Id\sum_i u_i u_i^\top = I_d 라 μmin⁡=μmax⁡=1\mu_{\min} = \mu_{\max} = 1 입니다. 행렬 체르노프 두 줄을 합치면 실패 확률이 2dexp⁡(−δ2s/3d)2d \exp(-\delta^2 s / 3d) 이하이고, 이를 η\eta 로 누르는 표본 수는

s≥3dδ2log⁡2dηs \ge \frac{3d}{\delta^2} \log \frac{2d}{\eta}

입니다. 행을 고르게 뽑으면 pi=1/np_i = 1/n 이라 L=nmax⁡iℓi/sL = n \max_i \ell_i / s 가 되고, 필요한 ss 가 nmax⁡iℓin \max_i \ell_i 에 비례합니다. 레버리지 점수가 고르면 nmax⁡iℓi≈dn \max_i \ell_i \approx d 라 손해가 없지만, 한 행에 몰려 있으면 nn 에 가까워져 표본을 거의 다 뽑아야 합니다. 이 비율 nmax⁡iℓi/dn \max_i \ell_i / d 를 열공간의 결맞음이라 부릅니다.

오블리비어스 스케치

레버리지 점수를 정확히 구하려면 UU 가 있어야 하고, UU 를 구하는 일이 처음 풀려던 문제입니다. 그래서 실무의 스케치는 AA 를 보지 않고 분포를 정합니다. AA 와 무관한 분포에서 SS 를 뽑아 고정된 AA 마다 높은 확률로 임베딩이 되는 것을 오블리비어스 스케치라 부릅니다. 데이터가 들어오기 전에 SS 를 정해 둘 수 있고, 스트림으로 들어오는 행렬에도 쓸 수 있다는 뜻입니다.

대표는 성분이 독립 N(0,1/s)\mathcal{N}(0, 1/s) 인 가우스 행렬입니다. 회전 불변이라 SUSU 는 UU 와 무관하게 s×ds \times d 가우스 행렬과 같은 분포이고, 그 특잇값은 대략 1±d/s1 \pm \sqrt{d/s} 사이에 놓입니다. s=O((d+log⁡(1/η))/ε2)s = O\bigl((d + \log(1/\eta))/\varepsilon^2\bigr) 이면 충분하고, 결맞음이 아예 문제가 되지 않습니다. 대가는 비용입니다. SASA 를 만드는 데 s⋅n⋅ds \cdot n \cdot d 번의 곱이 들어, 줄이기 전보다 오히려 비싸질 수 있습니다.

카운트 스케치와 SRHT

곱셈을 줄인 오블리비어스 스케치가 둘 있습니다. 카운트 스케치는 열마다 무작위로 고른 한 행에만 ±1\pm 1 을 둔 s×ns \times n 행렬입니다. 원래 행 ii 를 무작위 칸 h(i)h(i) 에 무작위 부호 g(i)g(i) 를 붙여 더해 넣는 것이고, SASA 를 만드는 비용이 AA 의 0 아닌 성분 수와 같습니다. 대신 칸끼리 부딪히는 일을 막으려면 s=O(d2/ε2)s = O(d^2 / \varepsilon^2) 개의 칸이 필요합니다.

SRHT는 결맞음을 먼저 없애고 나서 고르게 뽑는 스케치입니다. 정식 이름은 부분표본 무작위 아다마르 변환이고, S=n/s RHDS = \sqrt{n/s}\, R H D 로 적습니다. DD 는 대각에 무작위 부호를 둔 행렬, HH 는 성분이 ±1/n\pm 1/\sqrt{n} 인 정규화 아다마르 행렬, RR 은 ss 개의 행을 고르게 뽑는 행렬입니다. HDHD 는 직교 변환이라 열공간의 기하를 바꾸지 않으면서 레버리지 점수를 고르게 폅니다. 높은 확률로 max⁡iℓi=O((d+log⁡n)/n)\max_i \ell_i = O\bigl((d + \log n)/n\bigr) 가 되고, 그다음의 고른 추출에 위의 체르노프 계산이 그대로 섭니다. HH 를 곱하는 일은 고속 푸리에 변환과 같은 나비 구조로 nlog⁡nn \log n 번에 끝납니다.

네 스케치의 특잇값 구간. 위쪽 스무 행에 레버리지가 몰린 4096×20 기저 U 를 400행으로 줄였을 때 SU 의 특잇값이 가우스 [0.804, 1.186], 카운트 스케치 [0.981, 1.022], SRHT [0.757, 1.217] 로 1 근처의 1 ± √(d/s) 띠 안팎에 모이고, 고른 행 추출만 [0.054, 3.194] 로 크게 벗어난다

결맞음이 큰 행렬로 넷을 견줍니다. 4096×204096 \times 20 행렬의 위쪽 스무 행에 큰 값을 얹어 레버리지 점수의 최댓값을 0.996으로 만들었습니다. 평균 d/n=0.0049d/n = 0.0049 의 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는 1±d/s=[0.776,1.224]1 \pm \sqrt{d/s} = [0.776, 1.224] 근처에 섭니다. 고른 행 추출은 스무 개의 무거운 행 가운데 몇 개만 건져 가장 작은 특잇값이 0.054로 꺼졌습니다. 그 방향의 길이를 거의 잃은 것입니다. 같은 고른 추출이 HDHD 를 거친 뒤에는 멀쩡한데, 레버리지의 최댓값이 0.996에서 0.0055로 내려왔기 때문입니다. nmax⁡iℓin \max_i \ell_i 로 세면 4080에서 22.5로, d=20d = 20 과 거의 같아졌습니다. δ=0.5\delta = 0.5, η=0.01\eta = 0.01 로 체르노프 식에 넣으면 필요한 표본 수가 nn 을 넘는 40만에서 2,200으로 내려옵니다. 실제로는 400개로 충분했으니 상수는 넉넉하고, 식이 맞히는 것은 결맞음에 비례한다는 모양입니다. 카운트 스케치가 유난히 좋은 것은 무거운 스무 행이 거의 다른 칸에 떨어진 덕입니다.

무작위 SVD

레인지 파인더

이제 오른쪽 스케치로 돌아갑니다. 목표는 m×nm \times n 행렬 AA 의 열공간에서 큰 특잇값 쪽의 kk 차원을 담는 정규직교 행렬 QQ (m×ℓm \times \ell) 를 찾는 것입니다. 찾고 나면 A≈QQ⊤AA \approx Q Q^\top A 이고, 오차 ∥(I−QQ⊤)A∥\lVert (I - QQ^\top) A \rVert 가 σk+1\sigma_{k+1} 에 가까울수록 좋습니다. 이 일을 하는 절차를 레인지 파인더라 부르고, 무작위 판은 두 줄입니다.

Y=AΩ,Q=qr(Y)Y = A\Omega, \qquad Q = \mathrm{qr}(Y)

여기서 Ω\Omega 는 n×ℓn \times \ell 가우스 행렬이고 ℓ=k+p\ell = k + p 입니다. AΩA\Omega 의 각 열은 AA 의 열공간에서 뽑은 무작위 벡터이고, 특잇값 분해로 적으면 Aω=∑jσj(vj⊤ω)ujA\omega = \sum_j \sigma_j (v_j^\top \omega) u_j 입니다. 계수 vj⊤ωv_j^\top \omega 가 모두 같은 분포의 가우스이니 큰 σj\sigma_j 의 방향이 더 많이 섞입니다. 그런 벡터 ℓ\ell 개가 생성하는 공간은 위쪽 kk 개 방향을 거의 다 품습니다. 여분 pp 를 과표본이라 부르고, 보통 5에서 20 사이를 씁니다. 정확히 kk 개만 뽑으면 무작위 벡터 하나가 어떤 방향과 거의 수직일 확률이 무시할 수 없지만, 몇 개를 더 뽑으면 그 확률이 지수적으로 사라집니다.

알고리즘

QQ 를 얻은 뒤에는 작은 행렬로 결정적인 분해를 합니다. 무작위 SVD의 전체 절차는 다섯 걸음입니다.

  1. 가우스 행렬 Ω∈Rn×ℓ\Omega \in \mathbb{R}^{n \times \ell} 를 뽑습니다.
  2. Y=AΩY = A\Omega 를 계산합니다. 연산 2mnℓ2mn\ell 입니다.
  3. YY 를 QR 분해해 QQ 를 얻습니다. 연산 O(mℓ2)O(m\ell^2) 입니다.
  4. B=Q⊤AB = Q^\top A 를 계산합니다. ℓ×n\ell \times n 행렬이고 연산 2mnℓ2mn\ell 입니다.
  5. B=U~ΣV⊤B = \tilde U \Sigma V^\top 를 분해하고 U=QU~U = Q \tilde U 로 되돌립니다. 연산 O(nℓ2)O(n\ell^2) 입니다.

마지막 걸음이 성립하는 것은 QQ⊤A=QB=(QU~)ΣV⊤QQ^\top A = Q B = (Q \tilde U) \Sigma V^\top 이고, QU~Q \tilde U 의 열이 다시 정규직교이기 때문입니다. 근사 QQ⊤AQQ^\top A 의 특잇값 분해를 정확히 얻은 셈이고, 거기서 상위 kk 개를 잘라 냅니다. 전체 분해가 하던 일 가운데 AA 의 크기에 비례하는 부분은 걸음 2와 4의 행렬곱 둘로 줄었고, 분해 자체는 ℓ×n\ell \times n 의 작은 행렬 위에서만 일어납니다.

무작위 SVD의 다섯 걸음. 4096×11008 의 W 에 11008×32 가우스 Ω 를 곱해 4096×32 의 Y 를 얻고, QR 로 Q 를 만든 뒤 B = QᵀW 는 32×11008 이다. B 의 작은 SVD 에서 U = QŨ 를 되돌려 상위 16 개를 자른다. 큰 행렬에 닿는 것은 두 번의 행렬곱뿐이다

오차 상계

헬코–마티손–트롭은 가우스 Ω\Omega 와 p≥2p \ge 2 에서 다음을 보였습니다.

E∥(I−QQ⊤)A∥F≤(1+kp−1)1/2(∑j>kσj2)1/2E∥(I−QQ⊤)A∥≤(1+kp−1)σk+1+ek+pp(∑j>kσj2)1/2\begin{aligned} \mathbb{E} \lVert (I - QQ^\top) A \rVert_F &\le \Bigl( 1 + \frac{k}{p - 1} \Bigr)^{1/2} \Bigl( \sum_{j > k} \sigma_j^2 \Bigr)^{1/2} \\ \mathbb{E} \lVert (I - QQ^\top) A \rVert &\le \Bigl( 1 + \sqrt{\frac{k}{p - 1}} \Bigr) \sigma_{k+1} + \frac{e \sqrt{k + p}}{p} \Bigl( \sum_{j > k} \sigma_j^2 \Bigr)^{1/2} \end{aligned}

첫 줄의 오른쪽에서 (∑j>kσj2)1/2\bigl(\sum_{j > k} \sigma_j^2\bigr)^{1/2} 는 에카르트–영의 최적 오차입니다. 무작위 레인지 파인더는 최적의 1+k/(p−1)\sqrt{1 + k/(p-1)} 배 안에 들고, k=16k = 16, p=16p = 16 이면 그 배수가 1.438입니다. pp 를 키우면 1로 다가갑니다. 둘째 줄은 사정이 다릅니다. 첫 항은 최적값 σk+1\sigma_{k+1} 의 상수배이지만, 둘째 항에는 꼬리 전체의 프로베니우스 노름이 들어 있습니다. 스펙트럼이 빨리 줄면 그 항이 σk+1\sigma_{k+1} 과 비슷해 문제가 없고, 천천히 줄면 꼬리의 합이 σk+1\sigma_{k+1} 보다 몇 배 커져 상계가 느슨해집니다. 다음 절의 거듭제곱 반복이 이 둘째 항을 겨냥합니다.

오차 상계에 차원 mm 과 nn 이 하나도 없다는 점을 짚어 둡니다. 행렬이 4096행이든 400만 행이든 보장은 kk, pp, 그리고 스펙트럼의 모양으로만 정해집니다. 큰 행렬을 줄여도 스펙트럼의 위쪽이 남는 이유가 이 식입니다.

증명 개요

AA 의 특잇값 분해를 위쪽 kk 개와 나머지로 가릅니다. A=U[Σ1Σ2][V1⊤V2⊤]A = U \begin{bmatrix} \Sigma_1 & \\ & \Sigma_2 \end{bmatrix} \begin{bmatrix} V_1^\top \\ V_2^\top \end{bmatrix} 이고, 스케치도 같은 좌표로 Ω1=V1⊤Ω\Omega_1 = V_1^\top \Omega (k×ℓk \times \ell), Ω2=V2⊤Ω\Omega_2 = V_2^\top \Omega 로 나눕니다. 증명은 두 단계입니다.

첫 단계는 확률이 없는 부등식입니다. Ω1\Omega_1 이 행 계수가 꽉 차 있으면, 곧 오른쪽 역 Ω1†\Omega_1^\dagger 가 있으면

∥(I−PY)A∥2≤∥Σ2∥2+∥Σ2Ω2Ω1†∥2\lVert (I - P_Y) A \rVert^2 \le \lVert \Sigma_2 \rVert^2 + \lVert \Sigma_2 \Omega_2 \Omega_1^\dagger \rVert^2

입니다. 여기서 PY=QQ⊤P_Y = QQ^\top 는 YY 의 열공간으로의 사영입니다. 줄기는 이렇습니다. YΩ1†Y \Omega_1^\dagger 의 열공간이 YY 의 열공간 안에 있으므로 그쪽으로 사영한 오차가 더 큽니다. 그런데 YΩ1†=U[Σ1Σ2Ω2Ω1†]Y \Omega_1^\dagger = U \begin{bmatrix} \Sigma_1 \\ \Sigma_2 \Omega_2 \Omega_1^\dagger \end{bmatrix} 의 윗블록이 Σ1\Sigma_1 그대로라, 위쪽 kk 방향은 정확히 잡히고 아래 블록 Σ2Ω2Ω1†\Sigma_2 \Omega_2 \Omega_1^\dagger 만큼만 옆으로 샙니다. 그 샘이 오차에 더해지는 몫이 둘째 항입니다. 이 부등식은 어떤 Ω\Omega 에도 섭니다.

둘째 단계에서 가우스의 성질을 씁니다. VV 가 직교라 Ω1\Omega_1 과 Ω2\Omega_2 는 서로 독립인 가우스 행렬입니다. 독립인 가우스 GG 와 고정 행렬 S,TS, T 에서 E∥SGT∥F2=∥S∥F2∥T∥F2\mathbb{E}\lVert S G T \rVert_F^2 = \lVert S \rVert_F^2 \lVert T \rVert_F^2 이고, k×(k+p)k \times (k + p) 가우스의 유사역행렬은 E∥Ω1†∥F2=k/(p−1)\mathbb{E}\lVert \Omega_1^\dagger \rVert_F^2 = k / (p - 1) 입니다. 앞의 것은 성분별 분산을 더한 것이고, 뒤의 것은 역위샤트 분포의 평균에서 나옵니다. 프로베니우스 판의 첫 단계 부등식에 Ω1\Omega_1 을 고정한 채 Ω2\Omega_2 로 먼저 평균을 내면

E∥(I−PY)A∥F2≤∥Σ2∥F2+∥Σ2∥F2 E∥Ω1†∥F2=(1+kp−1)∥Σ2∥F2\mathbb{E}\lVert (I - P_Y) A \rVert_F^2 \le \lVert \Sigma_2 \rVert_F^2 + \lVert \Sigma_2 \rVert_F^2 \, \mathbb{E}\lVert \Omega_1^\dagger \rVert_F^2 = \Bigl( 1 + \frac{k}{p - 1} \Bigr) \lVert \Sigma_2 \rVert_F^2

이고, 젠센 부등식으로 제곱근을 씌우면 첫 줄의 상계입니다. 스펙트럼 노름 판은 같은 줄기에서 E∥SGT∥≤∥S∥∥T∥F+∥S∥F∥T∥\mathbb{E}\lVert S G T \rVert \le \lVert S \rVert \lVert T \rVert_F + \lVert S \rVert_F \lVert T \rVert 를 쓰면 나옵니다. p=0p = 0 이면 E∥Ω1†∥F2\mathbb{E}\lVert \Omega_1^\dagger \rVert_F^2 가 발산한다는 것이 과표본이 필요한 이유의 정확한 형태입니다. 정사각 가우스 행렬은 특잇값이 0 가까이 내려가는 일이 너무 잦습니다.

거듭제곱 반복

느린 감쇠

사전학습 가중치의 스펙트럼은 대개 천천히 줄어듭니다. 위쪽 몇 개가 크고 그 아래로 긴 꼬리가 이어집니다. 실험용으로 2048×55042048 \times 5504 행렬을 σj=j−1/2\sigma_j = j^{-1/2} 이 되게 만들어 봅니다. down_proj 의 가로세로를 반씩 줄인 크기입니다. k=16k = 16 에서 σ17=0.2425\sigma_{17} = 0.2425 인데 꼬리의 프로베니우스 노름은 (∑j>16j−1)1/2=2.196\bigl(\sum_{j > 16} j^{-1}\bigr)^{1/2} = 2.196 으로 아홉 배입니다. 스펙트럼 상계의 둘째 항이 첫째 항을 네 배 넘게 압도하고, 상계 전체가 σ17\sigma_{17} 의 10.7배가 됩니다.

실제로 돌려 보면 상계만큼 나쁘지는 않지만 느린 감쇠의 값은 분명히 치릅니다. 과표본 16의 무작위 SVD로 얻은 계수 16 근사의 스펙트럼 오차가 최적의 1.815배이고, 16번째 특잇값은 40%나 작게 나옵니다. 이유는 레인지 파인더의 설명 그대로입니다. 무작위 벡터 AωA\omega 에서 u16u_{16} 의 몫은 σ16=0.25\sigma_{16} = 0.25 에 비례하고, 그 아래 2000개 방향이 각각 0.24에서 0.02 사이의 몫으로 섞여 들어옵니다. 하나하나는 작아도 합치면 위쪽 방향을 가립니다.

거듭제곱 보정

처방은 스펙트럼을 날카롭게 만든 행렬로 스케치하는 것입니다.

Y=(AA⊤)qAΩY = (A A^\top)^q A \Omega

를 쓰면 (AA⊤)qA(AA^\top)^q A 는 AA 와 같은 특이벡터를 갖고 특잇값만 σj2q+1\sigma_j^{2q+1} 로 바뀝니다. 비 σk+1/σk\sigma_{k+1}/\sigma_k 가 2q+12q+1 제곱으로 줄어드니 꼬리가 위쪽을 가리는 힘이 빠르게 사라집니다. 이 절차를 거듭제곱 반복이라 부릅니다. 「중급 13번 · 행렬 거듭제곱과 거듭제곱법: 스펙트럼 반지름이 정하는 것」의 거듭제곱법이 벡터 하나를 AA 로 거듭 곱해 가장 큰 고유벡터를 찾았다면, 이것은 벡터 ℓ\ell 개짜리 블록을 거듭 곱해 위쪽 ℓ\ell 차원 부분공간을 찾는 판이라 부분공간 반복이라고도 부릅니다. PEFT 문서가 말하는 부분공간 반복이 이것이고 pissa_niter_4 는 q=4q = 4 입니다.

보장도 그대로 올라갑니다. 앞의 상계를 (AA⊤)qA(AA^\top)^q A 에 쓰고 「∥(I−P)A∥2q+1≤∥(I−P)(AA⊤)qA∥\lVert (I - P)A \rVert^{2q+1} \le \lVert (I - P)(AA^\top)^q A \rVert」를 이으면

E∥(I−PY)A∥≤[(1+kp−1)σk+12q+1+ek+pp(∑j>kσj2(2q+1))1/2]1/(2q+1)\mathbb{E} \lVert (I - P_Y) A \rVert \le \Bigl[ \Bigl( 1 + \sqrt{\tfrac{k}{p - 1}} \Bigr) \sigma_{k+1}^{2q+1} + \tfrac{e\sqrt{k + p}}{p} \Bigl( \sum_{j > k} \sigma_j^{2(2q+1)} \Bigr)^{1/2} \Bigr]^{1/(2q+1)}

입니다. 대괄호 안의 꼬리 합은 σj2q+1\sigma_j^{2q+1} 의 합이라 빨리 줄고, 바깥의 1/(2q+1)1/(2q+1) 제곱이 남은 상수배를 1 쪽으로 끌어당깁니다. 대가는 행렬곱이 2q2q 번 늘어나는 것이고, 앞의 연산량 계산에서 2q+22q + 2 가 그것입니다.

왼쪽은 σⱼ = j^(−1/2) 스펙트럼을 σ₁ 로 나눠 로그 눈금에 그린 것으로, q = 0, 1, 2 에서 σⱼ^(2q+1) 이 차례로 가팔라지고 j = 17 의 값이 0.243, 0.0143, 0.00084 로 떨어진다. 오른쪽은 같은 2048×5504 행렬에서 계수 16 근사의 스펙트럼 오차를 최적 σ₁₇ 로 나눈 값이 q = 0 에서 1.815, q = 1 에서 1.004, q = 2 에서 1.001 이다

그림의 오른쪽이 한 번의 반복으로 거의 다 해결된다는 것을 보여 줍니다. q=1q = 1 에서 스펙트럼 오차가 최적의 1.004배로 내려오고, 그다음부터는 특잇값 자체의 정확도가 한 자리씩 오릅니다. 16번째 특잇값의 상대 오차가 q=0,1,2,4q = 0, 1, 2, 4 에서 4×10−14 \times 10^{-1}, 4×10−24 \times 10^{-2}, 7×10−37 \times 10^{-3}, 7×10−47 \times 10^{-4} 입니다. PiSSA처럼 특이벡터를 초기값으로 쓰는 일이라면 근사 오차가 최적에 닿은 q=1q = 1 이나 2로도 충분하고, 4는 넉넉한 쪽의 선택입니다.

재직교화

(AA⊤)qAΩ(AA^\top)^q A\Omega 를 식 그대로 계산하면 안 됩니다. 곱할 때마다 각 방향의 크기가 σj2\sigma_j^2 배로 늘어, q=4q = 4 면 위쪽 방향과 16번째 방향의 크기 비가 (σ1/σ16)9=49≈2.6×105(\sigma_1/\sigma_{16})^9 = 4^9 \approx 2.6 \times 10^5 이 됩니다. 꼬리 쪽 방향과는 더 벌어집니다. 배정밀도의 유효 숫자가 16자리 남짓이라 작은 방향의 정보가 반올림에 묻히고, 열들이 사실상 같은 벡터로 무너집니다.

그래서 곱할 때마다 QR로 다시 정규직교화합니다.

Q0=qr(AΩ),Q~i=qr(A⊤Qi−1),Qi=qr(AQ~i)Q_0 = \mathrm{qr}(A\Omega), \qquad \tilde Q_i = \mathrm{qr}(A^\top Q_{i-1}), \qquad Q_i = \mathrm{qr}(A \tilde Q_i)

정확한 산술에서는 열공간이 같으므로 결과가 바뀌지 않고, 유한 정밀도에서는 매번 크기를 1로 되돌려 작은 방향을 지킵니다. QR 한 번은 O(mℓ2)O(m\ell^2) 이라 행렬곱 2mnℓ2mn\ell 에 견줘 ℓ/n\ell/n 배로 작습니다. 정밀도를 반으로 낮춘 bf16 가중치라면 이 걱정이 훨씬 커지므로, 분해는 fp32로 올려서 합니다.

나이스트룀 근사와 CUR

나이스트룀 근사

대칭 양의 준정부호 행렬 KK (n×nn \times n) 에는 스케치를 한쪽에만 곱해도 되는 근사가 있습니다. 스케치 C=KΩC = K\Omega 와 작은 행렬 W=Ω⊤KΩW = \Omega^\top K \Omega 로

K^=C W† C⊤\hat K = C \, W^{\dagger} \, C^\top

를 두는 것을 나이스트룀 근사라 부릅니다. Ω\Omega 를 열 선택 행렬로 잡으면 CC 는 KK 의 열 몇 개이고 WW 는 그 열과 행이 만나는 작은 블록입니다. 커널 행렬이라면 원소 nℓn\ell 개만 계산하면 되고 나머지 n2n^2 개는 보지도 않습니다.

이 근사는 언제나 아래에서 다가갑니다. K=G⊤GK = G^\top G 로 적으면 K^=G⊤PG\hat K = G^\top P G 이고, PP 는 GΩG\Omega 의 열공간으로의 사영이라 K−K^=G⊤(I−P)G⪰0K - \hat K = G^\top (I - P) G \succeq 0 입니다. 고른 열을 앞으로 모아 K=[WK21⊤K21K22]K = \begin{bmatrix} W & K_{21}^\top \\ K_{21} & K_{22} \end{bmatrix} 로 쓰면 오차가 정확히 K22−K21W−1K21⊤K_{22} - K_{21} W^{-1} K_{21}^\top 이고, 이 블록을 WW 에 대한 슈어 보수라 부릅니다. 가우스 과정에서 고른 점들을 관측한 뒤 남은 점들의 조건부 공분산과 같은 식입니다. 무작위 SVD와의 관계도 이 꼴에서 보입니다. Ω\Omega 를 가우스로 잡으면 나이스트룀 근사는 GG 에 레인지 파인더를 건 것과 같고, 오차 상계도 앞 절의 식을 따라갑니다.

어텐션 근사

길이 nn 의 어텐션 행렬 softmax(QK⊤/d)\mathrm{softmax}(QK^\top/\sqrt{d}) 는 n2n^2 원소라 긴 문맥에서 비용을 지배합니다. 효율 어텐션 셋이 이 절의 도구로 그것을 줄입니다. Linformer는 키와 값을 시퀀스 길이 방향으로 k×nk \times n 행렬로 사영해 n×kn \times k 어텐션을 계산합니다. 왼쪽 스케치 그 자체이고, 논문의 근사 보장 절이 존슨–린덴스트라우스로 어텐션 행렬이 저계수에 가깝다는 것을 보입니다. Performer는 소프트맥스 커널을 양수 무작위 특징의 바깥곱 평균으로 바꿉니다. 앞의 무작위 특징의 개수 계산이 그 근사 오차를 재는 틀입니다. Nyströmformer는 쿼리와 키의 구간 평균으로 표지점 몇 개를 잡아 나이스트룀 꼴 F~A~+B~\tilde F \tilde A^{+} \tilde B 로 어텐션을 적습니다. 소프트맥스 행렬은 대칭이 아니라 위의 양의 준정부호 보장이 그대로 서지는 않고, 그래서 세 조각을 따로 소프트맥스로 만듭니다.

셋은 무엇을 줄이느냐가 다릅니다. Linformer는 길이 방향을 섞어 줄이고, Performer는 커널을 무작위 특징으로 펴고, Nyströmformer는 실제 위치 몇 개를 고릅니다. 세 논문의 근사 오차 절을 읽을 때 물어야 할 것은 같습니다. 어느 노름으로 재는지, 상수에 무엇이 숨어 있는지, 그리고 이 절의 B/∥K∥B/\lVert K \rVert 나 결맞음 같은 비율이 실제 어텐션에서 얼마인지입니다.

CUR 분해

일반 직사각 행렬에서 실제 열과 행을 고르는 판이 CUR 분해입니다. AA 의 열 cc 개로 CC 를, 행 rr 개로 RR 을 만들고 가운데를

A≈CUR,U=C†AR†A \approx C U R, \qquad U = C^\dagger A R^\dagger

로 둡니다. CC†CC^\dagger 와 R†RR^\dagger R 이 각각 CC 의 열공간과 RR 의 행공간으로의 사영이라 CUR=(CC†)A(R†R)CUR = (CC^\dagger) A (R^\dagger R) 이고, 이것은 고른 열공간과 행공간 안에서 가장 좋은 근사입니다. 특잇값 분해의 특이벡터는 모든 열을 섞은 추상적 방향이지만 CC 와 RR 은 데이터에 실제로 있는 열과 행이라 해석할 수 있고, 희소 행렬이면 희소성이 그대로 남습니다.

어느 열을 고르느냐가 품질을 정하고, 여기서도 답은 레버리지 점수입니다. 위쪽 kk 개 오른쪽 특이벡터 VkV_k 의 행 길이 제곱에 비례하는 확률로 열을 O(klog⁡k/ε2)O(k \log k / \varepsilon^2) 개 뽑고 같은 식으로 행을 뽑으면, 높은 확률로 ∥A−CUR∥F≤(1+ε)∥A−Ak∥F\lVert A - CUR \rVert_F \le (1 + \varepsilon) \lVert A - A_k \rVert_F 입니다. 체르노프 계산이 부분공간 임베딩에서 한 일과 같은 일을 합니다. 레버리지 점수는 다시 VkV_k 를 요구하므로 실무에서는 무작위 SVD로 어림한 VkV_k 에서 점수를 읽습니다.

두 근사의 모양. 왼쪽은 대칭 K 에서 열 몇 개 C 와 그 교차 블록 W 를 골라 K̂ = C W⁺ Cᵀ 로 근사하고, 오차가 남은 블록의 슈어 보수 K₂₂ − K₂₁ W⁻¹ K₂₁ᵀ 이다. 오른쪽은 직사각 A 에서 열 C 와 행 R 을 골라 가운데 U = C⁺ A R⁺ 를 끼운 CUR 이다

다시 PiSSA 초기화로

절차

첫머리의 세 질문에 답합니다. 첫째, down_proj 하나의 상위 16개를 과표본 16, 반복 4번으로 구하면 큰 행렬에 닿는 연산이 행렬곱 열 번이고, 전체 분해의 3.14×10123.14 \times 10^{12} 에 견줘 2.9×10102.9 \times 10^{10} 입니다. 오차는 헬코–마티손–트롭의 상계가 묶고, 그 상계에는 행렬의 크기가 없습니다. 둘째, 4는 사전학습 가중치의 스펙트럼이 천천히 줄기 때문에 필요한 거듭제곱 반복의 수입니다. 0이면 꼬리 수천 개 방향이 위쪽 방향을 가려 16번째 특잇값이 40% 틀립니다. 셋째, 무작위 스케치가 열공간을 지킨다는 보장은 행렬 집중부등식에 기대고, 그 부등식은 스칼라 집중을 스펙트럼 노름으로 올리면서 차원의 로그만 더 치릅니다.

수십억 파라미터 모델 전체에 쓰는 절차는 이렇게 정리됩니다.

  1. 행렬마다 시드를 정해 Ω\Omega 를 그 자리에서 만듭니다. 저장할 필요가 없습니다.
  2. 가중치를 fp32로 올리고, 메모리가 모자라면 열 블록마다 Y+=W:,JΩJY \mathrel{+}= W_{:, J} \Omega_J 로 쌓습니다. 큰 행렬을 한 번 훑는 일입니다.
  3. 반복마다 W⊤QW^\top Q 와 WQWQ 를 블록으로 계산하고 QR로 다시 정규직교화합니다. 반복 한 번이 행렬을 두 번 훑습니다.
  4. B=Q⊤WB = Q^\top W 를 계산해 32×1100832 \times 11008 의 작은 분해를 하고, U16U_{16}, Σ16\Sigma_{16}, V16V_{16} 을 잘라 어댑터 두 행렬 U16Σ161/2U_{16}\Sigma_{16}^{1/2} 와 Σ161/2V16⊤\Sigma_{16}^{1/2} V_{16}^\top 으로 나눕니다.
  5. 잔차 W−U16Σ16V16⊤W - U_{16}\Sigma_{16}V_{16}^\top 를 원래 정밀도로 되돌려 얼립니다.

행렬을 훑는 횟수는 2q+22q + 2 번이고, 이 수가 GPU 메모리에 다 안 올라가는 행렬에서 비용을 정합니다. LoRA-XS처럼 위쪽 특이벡터를 얼리고 그 사이의 r×rr \times r 행렬만 학습하는 방법도 같은 절차의 4단계까지를 그대로 씁니다.

코드로 확인하기

down_proj 의 가로세로를 반씩 줄인 2048×55042048 \times 5504 행렬에 느린 스펙트럼 σj=j−1/2\sigma_j = j^{-1/2} 을 심고, 전체 분해와 반복 수가 다른 무작위 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배 차이입니다. 앞의 연산 수 식으로 이 크기를 세면 3.9×10113.9 \times 10^{11} 대 7.2×1097.2 \times 10^{9} 로 54배이니, 시간 비가 연산 비를 거의 따라갑니다. 시간은 기계마다 다르고 실행마다 조금씩 흔들립니다. range_F 는 레인지 파인더의 프로베니우스 오차를 꼬리 노름으로 나눈 값으로, q=0q = 0 에서도 1.106이라 상계 1.438 안에 듭니다. q≥1q \ge 1 에서 1보다 작은 것은 QQ 가 32차원이라 16번째 너머의 방향까지 일부 담기 때문입니다. rank_k 는 잘라 낸 계수 16 근사의 스펙트럼 오차를 최적 σ17\sigma_{17} 로 나눈 값이고, 반복 한 번에 1.815에서 1.004로 내려와 에카르트–영의 최적에 닿습니다. 실제 down_proj 에서는 연산 비가 109배로 더 벌어지고, GPU 위에서는 이중대각화가 행렬곱만큼 빨라지지 않으므로 시간 차가 그보다 커지기 쉽습니다.

연습

  1. 8192×286728192 \times 28672 가중치에서 ℓ=64\ell = 64, q=2q = 2 의 무작위 SVD가 큰 행렬에 쓰는 연산과 전체 분해의 연산 14mn2+8n314mn^2 + 8n^3 (m≥nm \ge n) 을 비교해 몇 배 차이인지 구하세요.
    전치해서 m=28672m = 28672, n=8192n = 8192 로 두면 전체 분해는 14⋅28672⋅81922+8⋅81923=3.13×101314 \cdot 28672 \cdot 8192^2 + 8 \cdot 8192^3 = 3.13 \times 10^{13} 입니다. 무작위 SVD는 행렬곱 2q+2=62q + 2 = 6 번에 한 번이 2⋅28672⋅8192⋅642 \cdot 28672 \cdot 8192 \cdot 64 이라 1.80×10111.80 \times 10^{11} 입니다. 비는 약 174배입니다.
  2. 열이 d=50d = 50 개인 정규직교 기저에서 레버리지 점수로 행을 뽑습니다. 행렬 체르노프로 U⊤S⊤SUU^\top S^\top S U 의 고윳값이 [0.5,1.5][0.5, 1.5] 안에 들 확률을 0.99 이상으로 만드는 표본 수의 하한을 구하세요.
    δ=0.5\delta = 0.5, η=0.01\eta = 0.01 을 s≥(3d/δ2)log⁡(2d/η)s \ge (3d/\delta^2)\log(2d/\eta) 에 넣으면 600log⁡104=5526.2600 \log 10^4 = 5526.2 라 s≥5527s \ge 5527 입니다.
  3. 무작위 레인지 파인더에서 k=10k = 10 일 때 프로베니우스 상계의 배수를 과표본 p=5p = 5 에서 구하고, 배수를 1.1 이하로 만드는 가장 작은 pp 를 구하세요.
    1+10/4=3.5=1.871\sqrt{1 + 10/4} = \sqrt{3.5} = 1.871 입니다. 1+10/(p−1)≤1.211 + 10/(p - 1) \le 1.21 이어야 하므로 p−1≥47.6p - 1 \ge 47.6, 곧 p=49p = 49 입니다.
  4. 특잇값이 σj=1/j\sigma_j = 1/j 인 행렬에서 k=10k = 10 을 찾습니다. 거듭제곱 반복을 qq 번 하면 비 σ11/σ10\sigma_{11}/\sigma_{10} 이 무엇으로 바뀌는지 적고, 그 비를 0.1 이하로 만드는 가장 작은 qq 를 구하세요.
    비가 (10/11)2q+1(10/11)^{2q+1} 이 됩니다. (2q+1)log⁡1.1≥log⁡10(2q + 1)\log 1.1 \ge \log 10 이어야 하므로 2q+1≥24.162q + 1 \ge 24.16, 곧 q=12q = 12 입니다. 확인으로 q=11q = 11 이면 (10/11)23=0.112(10/11)^{23} = 0.112, q=12q = 12 면 (10/11)25=0.092(10/11)^{25} = 0.092 입니다. 간격이 이렇게 좁으면 거듭제곱보다 과표본을 늘리는 편이 쌉니다.
  5. K=[210121012]K = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix} 에서 첫째와 셋째 열을 골라 나이스트룀 근사 K^\hat K 를 구하고, 오차 K−K^K - \hat K 가 슈어 보수와 같은지 확인하세요.
    CC 는 열 (2,1,0)(2, 1, 0) 과 (0,1,2)(0, 1, 2) 이고 W=2IW = 2I 라 K^=12CC⊤=[210111012]\hat K = \tfrac{1}{2} C C^\top = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix} 입니다. 오차는 가운데 원소 하나가 1인 행렬입니다. 슈어 보수는 2−(1,1)W−1(1,1)⊤=2−1=12 - (1, 1) W^{-1} (1, 1)^\top = 2 - 1 = 1 로 같고, 양수라 오차가 양의 준정부호입니다.

이 글이 세운 것은 한 문장으로 모입니다. 무작위로 줄인 행렬은 원래 행렬의 크기를 잊어도 스펙트럼의 위쪽을 기억하고, 그 기억이 얼마나 정확한지는 차원이 아니라 비율이 정합니다. 체르노프의 μ/L\mu/L, 무작위 특징의 B/∥K∥B/\lVert K \rVert, 레버리지 점수의 결맞음, 그리고 거듭제곱 반복이 다듬는 σk+1/σk\sigma_{k+1}/\sigma_k 가 모두 그 비율입니다. 다음 글 「고급 7번 · 란초스로 헤세 스펙트럼을 재고 랜덤 행렬로 잡음을 걷어 내기」는 블록 하나를 거듭 곱하던 이 글의 반복을 크릴로프 부분공간 전체를 쓰는 란초스 반복으로 넓혀, 행렬을 만들지 않고 헤세-벡터 곱만으로 스펙트럼 밀도를 그립니다. 그리고 그렇게 얻은 스펙트럼에서 무엇이 신호이고 무엇이 잡음인지를, 무작위 행렬의 특잇값이 따르는 마르첸코–파스투르 분포를 기준선으로 가립니다. 이 글의 가우스 스케치가 1±d/s1 \pm \sqrt{d/s} 사이에 특잇값을 모았던 것이 바로 그 분포의 양 끝입니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN