28.27 CP 분해(CANDECOMP/PARAFAC Decomposition)의 구조와 원리

CP 분해는 CANDECOMP(Canonical Decomposition)과 PARAFAC(Parallel Factor Analysis)이 동일한 수학적 모델을 독립적으로 제안한 뒤 통합된 명칭이다. CP 분해의 기본 아이디어는 고차 텐서를 유한 개의 랭크-1 텐서의 합으로 표현하는 것으로, 행렬의 특이값 분해를 자연스럽게 일반화한다. CP 분해는 파라미터 수가 차수에 대해 선형적으로 증가한다는 효율성과, 특정 조건 하에서 유일한 분해를 보장한다는 수학적 우수성 때문에 신호 처리, 화학 계량학, 심리 측정 등에서 고전적으로 사용되어 왔다.

1. 랭크-1 텐서와 CP 분해의 정의

n차 텐서 \mathcal{X} \in \mathbb{R}^{d_1 \times d_2 \times \cdots \times d_n}이 다음 형태로 표현되면 랭크-1 텐서라 한다.

\mathcal{X} = \mathbf{a}^{(1)} \otimes \mathbf{a}^{(2)} \otimes \cdots \otimes \mathbf{a}^{(n)}

즉, \mathcal{X}_{i_1 i_2 \cdots i_n} = a^{(1)}_{i_1} a^{(2)}_{i_2} \cdots a^{(n)}_{i_n}이다. CP 분해는 임의의 텐서 \mathcal{T}를 R개의 랭크-1 텐서의 합으로 근사하는 모델이다.

\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r\, \mathbf{a}_r^{(1)} \otimes \mathbf{a}_r^{(2)} \otimes \cdots \otimes \mathbf{a}_r^{(n)}

여기서 R은 분해 랭크, \lambda_r \in \mathbb{R}은 가중치 계수, \mathbf{a}_r^{(k)} \in \mathbb{R}^{d_k}는 각 모드의 성분 벡터이다. 성분 벡터들을 모아 인자 행렬 A^{(k)} = [\mathbf{a}_1^{(k)}\ \mathbf{a}_2^{(k)}\ \cdots\ \mathbf{a}_R^{(k)}] \in \mathbb{R}^{d_k \times R}로 구성하면, CP 분해는 다음과 같은 성분별 형태로 기술된다.

\mathcal{T}_{i_1 i_2 \cdots i_n} \approx \sum_{r=1}^{R} \lambda_r\, A^{(1)}_{i_1 r}\, A^{(2)}_{i_2 r}\, \cdots\, A^{(n)}_{i_n r}

2. 파라미터 수와 압축 효율

CP 분해의 총 파라미터 수는 R \sum_{k=1}^{n} d_k + R이며, 각 d_k \approx d라고 가정하면 O(nRd)의 복잡도를 가진다. 반면 원본 텐서의 원소 수는 O(d^n)이므로, R \ll d^{n-1}인 경우 압축률은 매우 높다. 예를 들어 d = 100, n = 5인 텐서의 원소 수는 10^{10}이지만, R = 10인 CP 분해의 파라미터 수는 약 5 \cdot 10 \cdot 100 = 5000으로, 압축률은 약 2 \cdot 10^6배에 달한다.

3. 텐서 랭크의 정의

텐서의 CP 랭크(혹은 텐서 랭크)는 텐서 \mathcal{T}를 정확히 표현하는 데 필요한 최소의 랭크-1 항의 수로 정의된다.

\mathrm{rank}(\mathcal{T}) = \min\left\{ R : \mathcal{T} = \sum_{r=1}^{R} \mathbf{a}_r^{(1)} \otimes \cdots \otimes \mathbf{a}_r^{(n)}\right\}

행렬의 랭크와 달리 고차 텐서의 랭크는 NP-난해 문제로 알려져 있으며, 일반적으로 정확한 값을 계산하는 것은 매우 어렵다. 또한 실수체 \mathbb{R}에서의 랭크가 복소수체 \mathbb{C}에서의 랭크와 다를 수 있으며, 경계 랭크(border rank)와 통상 랭크가 일치하지 않는 병리적 현상이 존재한다.

4. 최적화와 교대 최소 제곱법(ALS)

CP 분해의 파라미터를 구하기 위한 표준 알고리즘은 교대 최소 제곱법(Alternating Least Squares, ALS)이다. 목적 함수는 프로베니우스 노름 기반의 재구성 오차이다.

\min_{A^{(1)}, \ldots, A^{(n)}}\ \left\lVert \mathcal{T} - \sum_{r=1}^{R} \mathbf{a}_r^{(1)} \otimes \cdots \otimes \mathbf{a}_r^{(n)} \right\rVert_F^2

ALS는 한 번에 하나의 인자 행렬만을 갱신하며, 나머지 모든 인자 행렬을 고정한 상태에서 해당 최적화 문제가 선형 최소 제곱 문제로 환원된다는 점을 이용한다. 모드-k 전개(mode-k unfolding) \mathbf{T}_{(k)}를 이용하면 갱신 규칙은 다음과 같이 표현된다.

A^{(k)} \leftarrow \mathbf{T}_{(k)}\, \left(A^{(n)} \odot \cdots \odot A^{(k+1)} \odot A^{(k-1)} \odot \cdots \odot A^{(1)}\right)\, \left(\Gamma\right)^{-1}

여기서 \odot는 카트리-라오(Khatri-Rao) 곱이며, \Gamma는 해당 카트리-라오 곱에 해당하는 그램 행렬이다. ALS는 각 단계에서 목적 함수가 단조 감소함이 보장되지만, 전역 최적해 수렴은 보장되지 않는다.

5. 유일성과 Kruskal 조건

CP 분해의 특징적인 성질은 특정 조건 하에서 분해가 본질적으로 유일하다는 것이다. 인자 행렬 A^{(k)}의 Kruskal 랭크 k_{A^{(k)}}는 임의의 k개 열이 선형 독립이 되는 최대 k의 값으로 정의된다. 3차 텐서의 CP 분해는 다음 Kruskal 조건을 만족하면 열 순서와 스케일링을 제외하고 유일하다.

k_{A^{(1)}} + k_{A^{(2)}} + k_{A^{(3)}} \geq 2R + 2

이 유일성 성질은 행렬의 SVD가 직교성 제약 없이는 유일하지 않은 것과 대비되며, CP 분해가 잠재 요인 분석(latent factor analysis)에서 선호되는 핵심 이유이다.

6. 딥러닝에서의 응용

CP 분해는 합성곱 신경망의 4차 커널 텐서 \mathcal{K} \in \mathbb{R}^{C_{\text{out}} \times C_{\text{in}} \times K_h \times K_w}를 압축하는 데 사용된다. 이를 랭크 R의 CP 분해로 근사하면 다음과 같은 형태가 된다.

\mathcal{K}_{o,c,h,w} \approx \sum_{r=1}^{R} U_{or}\, V_{cr}\, P_{hr}\, Q_{wr}

이는 원래의 단일 합성곱 연산을 1 \times 1, 깊이별(depthwise), 그리고 방향별 합성곱의 연쇄로 분해하는 것과 동등하며, 파라미터 수와 FLOPs를 동시에 크게 감소시킨다. 또한 순환 신경망의 가중치, 임베딩 테이블, 그리고 트랜스포머의 일부 가중치 역시 CP 분해 기반으로 압축될 수 있다. CP 분해는 단순한 구조와 이론적 엄밀성을 동시에 갖춘 가장 고전적이면서도 강력한 텐서 분해 방법이다.