28.29 텐서 트레인(Tensor Train) 분해의 정의와 고차 텐서 압축

1. 텐서 트레인 분해의 도입 배경

고차 텐서를 다룰 때 가장 본질적인 난제는 차원의 저주(Curse of Dimensionality)이다. $d$ 차 텐서 $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times \cdots \times n_d}$ 를 명시적으로 저장하면 원소의 수는 $\prod_{k=1}^{d} n_k$ 가 되며, 모든 모드의 크기가 동일하게 $n$ 이라고 가정하면 저장 비용이 $n^d$ 로 지수적으로 증가한다. 앞서 다룬 CP 분해(CANDECOMP/PARAFAC)는 표현이 간결하다는 장점이 있지만 최적 계수(rank)의 결정이 NP-난해(NP-hard)에 속하며, 터커(Tucker) 분해는 핵심 텐서(Core Tensor)의 크기가 여전히 $r^d$ 형태로 차원에 대해 지수적이라는 한계를 가진다. 이러한 두 분해 방식의 약점을 동시에 극복하기 위하여 오셀레데츠(I. V. Oseledets)가 2011년 논문 “Tensor-Train Decomposition”(SIAM Journal on Scientific Computing)에서 체계적으로 정립한 분해 형식이 텐서 트레인(Tensor Train, TT) 분해이다. 동일한 형식은 양자 다체 물리학(Quantum Many-Body Physics)에서 행렬 곱 상태(Matrix Product States, MPS)라는 명칭으로 1990년대부터 사용되어 왔으며, 양 분야의 표현은 본질적으로 동일한 수학적 구조를 공유한다.

2. 형식적 정의

$d$ 차 텐서 $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times \cdots \times n_d}$ 가 텐서 트레인 형식으로 표현된다는 것은, 각 원소가 다음과 같이 일련의 행렬 곱으로 기술되는 것을 의미한다.

$\mathcal{A}(i_1, i_2, \ldots, i_d) = G_1(i_1) \, G_2(i_2) \, \cdots \, G_d(i_d)$

여기서 $G_k(i_k)$ 는 인덱스 $i_k$ 에 의해 결정되는 $r_{k-1} \times r_k$ 크기의 행렬이며, 양 끝단의 경계 조건은 $r_0 = r_d = 1$ 로 고정된다. 따라서 우변의 곱은 $1 \times r_1$ , $r_1 \times r_2$ , …, $r_{d-1} \times 1$ 크기의 행렬들이 차례로 곱해지는 형태이며, 최종 결과는 $1 \times 1$ 행렬, 즉 스칼라로 환원된다. 인덱스 $i_k$ 를 자유롭게 변화시키면 행렬 $G_k(i_k)$ 의 모음은 자연스럽게 3차 텐서 $\mathcal{G}_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}$ 로 재구성되며, 이 3차 텐서들을 텐서 트레인의 코어(TT-core) 또는 캐리지(Carriage)라 부른다.

성분 단위로 서술하면 다음과 같다.

$\mathcal{A}(i_1, i_2, \ldots, i_d) = \sum_{\alpha_0=1}^{r_0} \sum_{\alpha_1=1}^{r_1} \cdots \sum_{\alpha_d=1}^{r_d} \mathcal{G}_1(\alpha_0, i_1, \alpha_1) \, \mathcal{G}_2(\alpha_1, i_2, \alpha_2) \, \cdots \, \mathcal{G}_d(\alpha_{d-1}, i_d, \alpha_d)$

여기서 $\alpha_k$ 는 인접한 두 코어를 연결하는 보조 인덱스이며, 통상 결합 인덱스(Auxiliary Index 또는 Bond Index)라고 한다. 보조 인덱스가 가질 수 있는 최대 크기 $r_k$ 가 곧 해당 결합의 텐서 트레인 계수(TT-rank)이며, 벡터 $(r_0, r_1, \ldots, r_d) = (1, r_1, r_2, \ldots, r_{d-1}, 1)$ 을 텐서 트레인 계수 벡터라 부른다.

3. 텐서 트레인 계수의 수학적 성격

텐서 트레인 계수는 단순히 분해 시 임의로 부여되는 매개변수가 아니라, 원본 텐서의 펼친 행렬(Unfolding Matrix)의 계수로 엄밀히 특징지어진다. $k$ 번째 분리 펼치기(Separation Unfolding) $A_{[k]}$ 를 다음과 같이 정의한다.

$A_{[k]} \big( (i_1, \ldots, i_k), (i_{k+1}, \ldots, i_d) \big) = \mathcal{A}(i_1, i_2, \ldots, i_d)$

즉, 처음 $k$ 개의 모드를 행 인덱스로, 나머지 $d - k$ 개의 모드를 열 인덱스로 묶어 만든 $\big(\prod_{j=1}^{k} n_j\big) \times \big(\prod_{j=k+1}^{d} n_j\big)$ 크기의 행렬이다. 오셀레데츠의 정리에 의하면, 텐서 $\mathcal{A}$ 가 텐서 트레인 형식 $(r_0, r_1, \ldots, r_d)$ 을 가지기 위한 필요충분조건은 모든 $k = 1, 2, \ldots, d-1$ 에 대하여 $\mathrm{rank}(A_{[k]}) \le r_k$ 가 성립하는 것이다. 또한 최소 텐서 트레인 계수(minimal TT-rank)는 정확히 $r_k = \mathrm{rank}(A_{[k]})$ 이다. 이 사실은 텐서 트레인 분해가 행렬의 계수 개념을 자연스러운 방식으로 다차원 텐서에 일반화한 것임을 보여 준다.

4. TT-SVD 알고리즘

오셀레데츠는 위의 특징을 활용하여 임의의 텐서로부터 텐서 트레인 분해를 결정론적으로 구성하는 알고리즘을 제시하였다. 이를 일반적으로 TT-SVD 알고리즘이라 부른다. 절차는 다음과 같이 진행된다.

첫째, 입력 텐서 $\mathcal{A}$ 를 첫 번째 분리 펼치기 $A_{[1]}$ 로 재배열한 뒤, 절단 특이값 분해(Truncated Singular Value Decomposition)를 수행하여 $A_{[1]} \approx U_1 \Sigma_1 V_1^{\top}$ 의 근사를 얻는다. 둘째, $U_1$ 을 코어 $\mathcal{G}_1 \in \mathbb{R}^{1 \times n_1 \times r_1}$ 의 형태로 재형성한다. 셋째, $\Sigma_1 V_1^{\top}$ 를 다음 단계의 입력 행렬로 삼아 새로운 분리 펼치기를 수행하고, 다시 절단 SVD를 적용하여 코어 $\mathcal{G}_2$ 를 추출한다. 이러한 과정을 $d - 1$ 회 반복하면 마지막에 남는 잔여 행렬이 곧 코어 $\mathcal{G}_d$ 가 된다.

이 알고리즘이 가지는 본질적 장점은 준최적 근사 보장(Quasi-Optimality Guarantee)이다. 각 단계에서 절단 SVD에 의하여 발생하는 오차를 $\varepsilon_k$ 라 할 때, 최종 텐서 트레인 근사 $\tilde{\mathcal{A}}$ 의 프로베니우스 노름 오차는 다음 부등식을 만족한다.

$\| \mathcal{A} - \tilde{\mathcal{A}} \|_F \le \sqrt{\sum_{k=1}^{d-1} \varepsilon_k^2}$

따라서 사용자가 사전에 허용 오차 $\varepsilon$ 을 지정하면 각 단계의 절단 임계값을 $\varepsilon / \sqrt{d-1}$ 로 설정함으로써, 동일한 노름 오차 한도 내에서 가장 작은 텐서 트레인 계수에 비해 상수배 이내의 근사를 보장할 수 있다.

5. 고차 텐서 압축의 정량적 효과

텐서 트레인 형식으로 저장되는 매개변수의 총 개수는 모든 코어의 원소 수의 합과 같다. 모든 모드의 크기가 $n$ 이고 모든 결합 계수가 $r$ 로 균일하다고 가정하면, 코어 1개의 크기는 $n r^2$ 이며 총 매개변수 수는 다음과 같다.

$\sum_{k=1}^{d} r_{k-1} \, n_k \, r_k \approx d \, n \, r^2$

이를 원본 저장 비용 $n^d$ 및 터커 분해 비용 $n d r + r^d$ 와 비교하면, 텐서 트레인은 차원 $d$ 에 대해 선형적으로만 증가하는 유일한 형식임을 확인할 수 있다. 즉, 차원 $d$ 가 매우 큰 영역에서도 결합 계수 $r$ 만 적절히 작게 유지된다면 압축률은 사실상 차원에 무관하게 보존된다. 이러한 성질을 차원의 저주의 회피(Breaking the Curse of Dimensionality)라고 부른다.

6. 표준 연산의 텐서 트레인 형식 내 수행

텐서 트레인 형식의 또 다른 중요한 특징은, 텐서를 명시적으로 복원하지 않고도 코어 단위에서 직접 표준 연산을 수행할 수 있다는 점이다. 두 텐서 트레인 텐서의 덧셈, 원소별 곱(Hadamard 곱), 내적(Inner Product), 행렬-벡터 곱셈(텐서 트레인 행렬-텐서 트레인 벡터 곱) 등은 모두 코어들 사이의 국소적 연산으로 표현된다. 예를 들어 두 텐서의 내적은 결합 인덱스에 대한 순차적 축약(Sequential Contraction)으로 $\mathcal{O}(d n r^3)$ 의 비용으로 계산되며, 덧셈 결과의 텐서 트레인 계수는 두 입력 계수의 합으로 표현된다. 다만 덧셈과 곱 연산의 결과는 일반적으로 결합 계수가 증가하므로, 연산 후에는 좌·우 직교화(Left/Right Orthogonalization)와 절단 SVD에 기반한 재근사(TT-Rounding) 절차를 통하여 결합 계수를 다시 줄여야 한다.

7. 인접 분해 형식과의 관계

텐서 트레인 분해는 CP 분해와 터커 분해 사이에서 표현력과 안정성의 균형을 절충적으로 달성한다. CP 분해는 매개변수 수가 $d n r$ 로 가장 작지만, 최적 계수의 결정이 일반적으로 잘 정의되지 않으며 수치적 불안정성이 빈번히 보고된다. 터커 분해는 잘 정의된 다중선형 SVD(Higher-Order SVD, HOSVD)를 통해 안정적으로 계산되지만, 핵심 텐서의 크기가 차원에 대하여 지수적으로 증가하는 단점이 있다. 텐서 트레인 분해는 잘 정의된 펼친 행렬의 계수에 의하여 결합 계수가 결정되며, 동시에 매개변수 수가 차원에 대하여 선형적으로만 증가한다는 점에서 양자의 장점을 모두 취한다. 이러한 구조적 특징은 텐서 네트워크 일반론에서 텐서 트레인을 1차원 사슬(Chain) 형태의 가장 단순한 텐서 네트워크로 분류하게 만드는 근거가 된다.

8. 응용 영역

텐서 트레인 분해는 고차원 편미분방정식의 수치 해법, 다전자계의 양자 상태 표현, 고차원 적분의 효율적 계산, 신경망 가중치 행렬 및 임베딩 행렬의 압축 등 여러 영역에서 활용된다. 노보쿠도프(A. Novikov) 등이 2015년 NeurIPS 논문 “Tensorizing Neural Networks“에서 제안한 텐서 트레인 계층(TT-Layer)은 완전 연결 계층의 가중치 행렬을 텐서화한 뒤 텐서 트레인 형식으로 표현함으로써, 정확도의 큰 손실 없이 매개변수 수를 수십 배에서 수백 배까지 압축하는 결과를 보여 주었다. 또한 칼란트지스(V. Khrulkov) 등의 연구에서는 순환 신경망(RNN)과 임베딩 테이블의 텐서 트레인 압축이 거대 모델의 메모리 사용량을 결정적으로 감소시키는 수단임을 입증하였다. 이러한 응용은 텐서 트레인 분해가 단순한 수학적 형식이 아니라, 고차 텐서를 효율적으로 저장·연산하기 위한 근본적인 표현 도구임을 보여 준다.