27.20 행렬 곱셈(Matrix Multiplication)의 정의와 연산 규칙

1. 행렬 곱셈의 정의

$A \in \mathbb{R}^{m \times p}$ 와 $B \in \mathbb{R}^{p \times n}$ 의 곱 $C = AB \in \mathbb{R}^{m \times n}$ 은 다음과 같이 정의된다.

$c_{ij} = \sum_{k=1}^{p} a_{ik} b_{kj}, \quad 1 \leq i \leq m, \; 1 \leq j \leq n$

즉 $C$ 의 $(i, j)$ -성분은 $A$ 의 $i$ 번째 행벡터와 $B$ 의 $j$ 번째 열벡터의 내적이다. 곱셈이 정의되려면 $A$ 의 열 수와 $B$ 의 행 수가 동일하여야 한다. 결과 행렬의 크기는 $A$ 의 행 수와 $B$ 의 열 수로 결정된다.

$\underbrace{A}_{m \times p} \cdot \underbrace{B}_{p \times n} = \underbrace{C}_{m \times n}$

2. 행렬 곱셈의 네 가지 해석

행렬 곱셈은 네 가지 동등한 관점에서 해석할 수 있다.

해석 1: 내적 관점. $C$ 의 각 성분은 $A$ 의 행과 $B$ 의 열의 내적이다.

$c_{ij} = \mathbf{a}_i^\top \mathbf{b}_j$

여기서 $\mathbf{a}_i^\top$ 는 $A$ 의 $i$ 번째 행벡터, $\mathbf{b}_j$ 는 $B$ 의 $j$ 번째 열벡터이다.

해석 2: 열 관점. $C$ 의 각 열은 $A$ 의 열벡터들의 선형 결합이다. $B = [\mathbf{b}_1 \; \cdots \; \mathbf{b}_n]$ 이면

$AB = [A\mathbf{b}_1 \; A\mathbf{b}_2 \; \cdots \; A\mathbf{b}_n]$

각 $A\mathbf{b}_j = \sum_{k=1}^p b_{kj}\mathbf{a}_k$ 는 $A$ 의 열벡터 $\mathbf{a}_1, \ldots, \mathbf{a}_p$ 의 $\mathbf{b}_j$ 성분에 의한 선형 결합이다. 따라서 $C$ 의 열 공간은 $A$ 의 열 공간의 부분 공간이다.

해석 3: 행 관점. $C$ 의 각 행은 $B$ 의 행벡터들의 선형 결합이다.

$AB = \begin{pmatrix} \mathbf{a}_1^\top B \\ \mathbf{a}_2^\top B \\ \vdots \\ \mathbf{a}_m^\top B \end{pmatrix}$

해석 4: 외적 합(outer product sum) 관점. 행렬 곱을 순위-1 행렬의 합으로 분해한다.

$AB = \sum_{k=1}^{p} \mathbf{a}_k \mathbf{b}_k^\top$

여기서 $\mathbf{a}_k$ 는 $A$ 의 $k$ 번째 열, $\mathbf{b}_k^\top$ 는 $B$ 의 $k$ 번째 행이다. 각 $\mathbf{a}_k\mathbf{b}_k^\top$ 는 $m \times n$ 순위-1 행렬(rank-1 matrix)이며, $AB$ 는 이들의 합이다. 이 해석은 저순위 행렬 분해(low-rank matrix factorization)의 기초가 된다.

3. 행렬 곱셈의 연산 규칙

행렬 곱셈은 다음 성질들을 만족한다. 크기가 적합한 행렬 $A, B, C$ 와 스칼라 $\alpha$ 에 대하여,

결합법칙: $(AB)C = A(BC)$
좌분배법칙: $A(B + C) = AB + AC$
우분배법칙: $(A + B)C = AC + BC$
스칼라 호환: $\alpha(AB) = (\alpha A)B = A(\alpha B)$
단위 행렬: $I_m A = A I_n = A$ ( $A \in \mathbb{R}^{m \times n}$ )
전치: $(AB)^\top = B^\top A^\top$

교환법칙은 일반적으로 성립하지 않는다. $AB \neq BA$ 인 경우가 대부분이며, 심지어 $AB$ 가 정의되더라도 $BA$ 가 정의되지 않을 수 있다. $A \in \mathbb{R}^{m \times p}$ , $B \in \mathbb{R}^{p \times n}$ 에서 $m \neq n$ 이면 $BA$ 의 크기 조건이 맞지 않는다.

교환법칙이 성립하는 특수한 경우로는 대각 행렬끼리의 곱, $A$ 와 $A$ 의 거듭제곱, $A$ 와 $I$ 등이 있다.

4. 행렬-벡터 곱

행렬-벡터 곱은 행렬 곱셈의 특수한 경우로, $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{x} \in \mathbb{R}^n$ 에 대하여 $\mathbf{y} = A\mathbf{x} \in \mathbb{R}^m$ 이다.

$y_i = \sum_{j=1}^{n} a_{ij} x_j = \mathbf{a}_i^\top \mathbf{x}$

열 관점에서는 $A\mathbf{x} = x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \cdots + x_n\mathbf{a}_n$ 으로, $A$ 의 열벡터들의 선형 결합으로 해석된다. 이 해석에 의하면, $A\mathbf{x}$ 의 가능한 모든 값의 집합은 $A$ 의 열 공간 $\text{Col}(A)$ 이다.

5. 계산 복잡도

$A \in \mathbb{R}^{m \times p}$ 와 $B \in \mathbb{R}^{p \times n}$ 의 곱을 정의에 따라 계산하면, 각 성분에 $p$ 번의 곱셈과 $(p-1)$ 번의 덧셈이 필요하고, 성분이 $mn$ 개이므로 총 연산 횟수는 $O(mnp)$ 이다.

정사각 행렬의 경우 ( $m = n = p$ ) 나이브 알고리즘의 복잡도는 $O(n^3)$ 이다. 스트라센 알고리즘(Strassen algorithm)은 분할 정복(divide and conquer)을 이용하여 $O(n^{2.807})$ 으로 개선하였으며, 현재 이론적 최선의 알고리즘은 $O(n^{2.3729})$ 이다.

실무에서 GPU 위의 행렬 곱셈은 고도로 최적화된 BLAS(Basic Linear Algebra Subprograms) 라이브러리를 통하여 수행된다. 타일링(tiling), 메모리 계층 구조 활용, 텐서 코어(tensor core) 등의 하드웨어 최적화가 적용되어, 이론적 복잡도와는 별개로 극도로 높은 처리량(throughput)을 달성한다.

6. 행렬 곱셈의 결합법칙과 계산 순서

결합법칙 $(AB)C = A(BC)$ 에 의하여 세 행렬의 곱은 어떤 순서로 계산하여도 결과가 동일하지만, 계산 비용은 다를 수 있다. $A \in \mathbb{R}^{m \times p}$ , $B \in \mathbb{R}^{p \times q}$ , $C \in \mathbb{R}^{q \times n}$ 일 때,

$(AB)C$ : $O(mpq) + O(mqn) = O(mq(p + n))$
$A(BC)$ : $O(pqn) + O(mpn) = O(pn(q + m))$

$m, p, q, n$ 의 상대적 크기에 따라 최적의 곱셈 순서가 달라진다. 이 문제는 행렬 체인 곱셈(matrix chain multiplication) 문제로 알려져 있으며, 동적 프로그래밍으로 최적 순서를 $O(k^3)$ ( $k$ 는 행렬 수)에 결정할 수 있다.

7. 딥러닝에서의 행렬 곱셈

완전 연결층: 단일 완전 연결층의 순전파는 행렬 곱셈과 덧셈이다.

$Z = XW^\top + \mathbf{1}\mathbf{b}^\top$

$X \in \mathbb{R}^{N \times d}$ (배치 데이터), $W \in \mathbb{R}^{m \times d}$ (가중치), $\mathbf{b} \in \mathbb{R}^m$ (편향). 배치 처리에 의하여 $N$ 개의 데이터에 대한 연산이 하나의 행렬 곱셈으로 수행된다.

어텐션 메커니즘: 트랜스포머의 자기 어텐션은 세 번의 행렬 곱셈으로 구성된다.

$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^\top}{\sqrt{d_k}}\right)V$

$Q, K \in \mathbb{R}^{n \times d_k}$ , $V \in \mathbb{R}^{n \times d_v}$ . $QK^\top \in \mathbb{R}^{n \times n}$ 의 계산에 $O(n^2 d_k)$ 연산이 필요하며, 시퀀스 길이 $n$ 이 클 때 이것이 계산 병목이 된다.

합성곱의 행렬 곱 변환: 합성곱(convolution) 연산은 im2col 변환을 통하여 행렬 곱셈으로 변환되어 수행된다. 입력 패치(patch)를 행렬의 열로 펼치면, 합성곱 필터와의 연산이 행렬 곱셈이 된다. 이를 통하여 고도로 최적화된 행렬 곱셈 라이브러리를 활용할 수 있다.

역전파에서의 행렬 곱셈: 역전파 과정에서 경사도는 전치 행렬과의 곱으로 전파된다. 순전파에서 $\mathbf{y} = W\mathbf{x}$ 이면, 역전파에서 $\frac{\partial\mathcal{L}}{\partial\mathbf{x}} = W^\top\frac{\partial\mathcal{L}}{\partial\mathbf{y}}$ 이고 $\frac{\partial\mathcal{L}}{\partial W} = \frac{\partial\mathcal{L}}{\partial\mathbf{y}}\mathbf{x}^\top$ 이다. 전자는 행렬-벡터 곱이고 후자는 외적(outer product)으로서, 모두 행렬 곱셈의 특수한 경우이다.

혼합 정밀도(mixed precision) 행렬 곱셈: 현대 GPU의 텐서 코어는 FP16 또는 BF16 정밀도의 행렬 곱셈을 FP32 대비 2~8배 빠르게 수행한다. 순전파와 역전파의 행렬 곱셈을 낮은 정밀도로 수행하고, 가중치 갱신만 FP32로 유지하는 혼합 정밀도 학습(mixed precision training)은 학습 속도를 크게 향상시키면서도 모델 품질을 유지할 수 있다.