벡터 양자화(Vector Quantization) 이론: 스칼라 양자화부터 LBG 알고리즘까지

디지털 신호 처리에서 양자화는 연속적인 값을 이산적인 표현으로 변환하는 과정으로, 모든 디지털 시스템의 근간을 이룹니다. 우리가 가장 흔히 접하는 양자화는 각 샘플을 독립적으로 처리하는 스칼라 양자화(Scalar Quantization)입니다. 그러나 클로드 섀넌(Claude Shannon)이 제시한 정보 이론적 토대 위에서, 신호의 샘플들을 묶어 하나의 벡터로 다루는 벡터 양자화(Vector Quantization, VQ)는 동일한 비트율(Bit Rate)에서 더 낮은 왜곡을 달성할 수 있다는 것이 이론적으로 증명되어 있습니다.

벡터 양자화는 1980년대 음성 부호화에서 본격적으로 활용되기 시작하여 영상 압축, 패턴 인식, 정보 검색 등 다양한 분야로 확장되어 왔습니다. 최근에는 VQ-VAE(Vector Quantized Variational AutoEncoder)와 같이 딥러닝 모델 내부에서 이산 표현을 학습하는 데 활용되며 다시금 주목받고 있습니다. 이러한 흐름 속에서 벡터 양자화의 이론적 기반을 이해하는 것은 고전적인 압축 기법뿐 아니라 최신 생성 모델까지 관통하는 통찰을 제공합니다.

이번 글에서는 벡터 양자화의 이론적 토대를 살펴봅니다. 스칼라 양자화의 한계를 짚어보는 것으로 시작하여, 벡터 양자화의 수학적 정의, 최적 양자화기가 만족해야 할 두 가지 조건, 그리고 실용적인 코드북 설계 알고리즘인 LBG 알고리즘까지 단계적으로 다룹니다.

 

1. 스칼라 양자화에서 벡터 양자화로의 확장

스칼라 양자화는 입력 신호의 각 샘플을 독립적으로 양자화합니다. $L$개의 양자화 레벨을 가진 스칼라 양자화기는 한 샘플당 $\log_2 L$ 비트를 사용하며, 입력 샘플 $x$를 가장 가까운 레벨 $\hat{x}$로 매핑합니다.

그러나 실제 신호의 샘플들은 일반적으로 상관관계(Correlation)를 가집니다. 예를 들어 음성 신호의 인접한 샘플들, 영상의 이웃한 픽셀들은 서로 통계적으로 강한 관련성을 보입니다. 스칼라 양자화는 이러한 상관관계를 활용하지 못하므로 효율의 한계가 존재합니다.

정보 이론의 창시자인 클로드 섀넌의 속도-왜곡 이론(Rate-Distortion Theory)에 따르면, 데이터의 각 차원이 서로 독립적인 특징을 가지더라도 스칼라 단위가 아닌 벡터 단위로 묶어서 양자화할 때 이론적인 압축 한계 성능이 훨씬 높아집니다. 다차원 공간을 활용하면 데이터의 확률 분포 모양을 더욱 유연하게 채울 수 있기 때문입니다. 이는 다음 세 가지 이득(Gain)에 기인합니다.

• 공간 채움 이득(Space-filling Gain): 고차원 공간에서 영역을 효율적으로 채울 수 있는 셀(Cell) 형태가 존재합니다. 1차원에서는 구간만이 유일한 선택이지만, 2차원에서는 육각형(Hexagon)이 정사각형(Square)보다, 3차원 이상에서는 다양한 다면체가 정육면체(Cube)보다 효율적으로 공간을 분할합니다.
• 형태 이득(Shape Gain): 입력의 확률 분포 형태에 맞춰 양자화 셀의 모양을 최적화할 수 있습니다.
• 메모리 이득(Memory Gain): 샘플 간 상관관계를 활용할 수 있습니다. 단, 이 이득은 i.i.d. 신호에서는 발생하지 않습니다.

이러한 이론적 우수성으로 인해, 동일한 비트율에서 벡터 양자화는 스칼라 양자화보다 항상 같거나 낮은 왜곡을 보장합니다.

 

2. 벡터 양자화의 정의

$k$차원 벡터 양자화기 $Q$는 $k$차원 유클리드 공간 $\mathbb{R}^k$를 유한 집합 $\mathcal{C} = \{y_1, y_2, \dots, y_N\}$으로 사상(mapping)하는 함수로 정의됩니다.

$$Q : \mathbb{R}^k \rightarrow \mathcal{C}, \quad \mathcal{C} \subset \mathbb{R}^k$$

여기서 집합 $\mathcal{C}$를 코드북(Codebook)이라 하며, 각 원소 $y_i$를 코드워드(Codeword) 또는 재생 벡터(Reproduction Vector)라고 부릅니다. 코드북의 크기 $N$은 양자화 레벨 수에 해당합니다. 여기서 입력 벡터 $x \in \mathbb{R}^k$를 특정한 코드워드(Codeword) $y_i$로 매핑하는 비선형 양자화 함수 $Q(\cdot)$로 정의할 수 있습니다. 즉, 식으로는 $Q(x) = y_i$ 형태로 표현됩니다.

벡터 양자화기는 두 부분으로 구성됩니다.

• 부호화기(Encoder): 입력 벡터 $x \in \mathbb{R}^k$를 받아 가장 적합한 코드워드의 인덱스 $i \in \{1, 2, \dots, N\}$를 출력합니다.
• 복호화기(Decoder): 인덱스 $i$를 받아 해당 코드워드 $y_i$를 출력합니다.

전송 또는 저장되는 정보는 인덱스 $i$이며, 이를 위해 필요한 비트 수는 $\log_2 N$입니다. 따라서 샘플당 비트율은 다음과 같이 정의됩니다.

$$R = \frac{\log_2 N}{k} \quad \text{(bits/sample)}$$

같은 비트율 $R$에서 차원 $k$가 클수록 코드북 크기 $N = 2^{kR}$이 지수적으로 커지지만, 그만큼 더 정교한 양자화가 가능해집니다.

벡터 양자화기는 또한 입력 공간 $\mathbb{R}^k$를 $N$개의 영역으로 분할하는 것으로 볼 수 있습니다. $i$번째 코드워드에 매핑되는 입력 벡터들의 집합을 $i$번째 분할 영역(Partition Cell) $R_i$라 부릅니다.

$$R_i = \{x \in \mathbb{R}^k : Q(x) = y_i\}$$

이 영역들은 서로 겹치지 않으며($R_i \cap R_j = \emptyset, i \neq j$), 그 합집합이 전체 입력 공간을 이룹니다($\bigcup_i R_i = \mathbb{R}^k$).

 

3. 왜곡 척도

양자화의 품질은 입력 벡터와 출력 벡터 간의 왜곡(Distortion)으로 측정됩니다. 가장 널리 쓰이는 왜곡 척도는 제곱 오차(Squared Error)입니다.

$$d(x, y) = \|x - y\|^2 = \sum_{j=1}^{k} (x_j - y_j)^2$$

전체 양자화기의 평균 왜곡은 입력 벡터의 확률 분포 $p(x)$에 대한 기댓값으로 정의됩니다.

$$D = E[d(X, Q(X))] = \int_{\mathbb{R}^k} d(x, Q(x)) p(x) dx$$

이를 분할 영역으로 나누어 표현하면 다음과 같습니다.

$$D = \sum_{i=1}^{N} \int_{R_i} d(x, y_i) p(x) dx$$

응용에 따라 가중 제곱 오차, 마할라노비스 거리, 지각(Perceptual) 척도 등 다양한 왜곡 척도가 사용됩니다. 그러나 이론 전개와 알고리즘 설계의 명료성을 위해 본 글에서는 제곱 오차를 기준으로 논의를 진행합니다.

벡터 양자화기 설계의 목표는 주어진 코드북 크기 $N$과 입력 분포 $p(x)$에 대해 평균 왜곡 $D$를 최소화하는 것입니다.

 

4. 최적 양자화기의 두 가지 조건

최적의 벡터 양자화기는 코드북 $\mathcal{C}$와 분할 영역 $\{R_i\}$가 서로에 대해 최적이어야 합니다. 이는 두 가지 필요 조건으로 정리됩니다.

4.1 최근접 이웃 조건 (Nearest Neighbor Condition)

코드북 $\mathcal{C}$가 고정되어 있을 때, 평균 왜곡을 최소화하는 분할은 각 입력 벡터를 가장 가까운 코드워드에 할당하는 것입니다.

$$R_i = \{x : d(x, y_i) \leq d(x, y_j), \forall j \neq i\}$$

제곱 오차 척도에서 이 조건이 만드는 분할 영역들을 보로노이 영역(Voronoi Region)이라 부릅니다. 보로노이 영역은 두 코드워드 $y_i, y_j$를 잇는 선분의 수직이등분 초평면(Hyperplane)으로 경계가 정해지는 볼록 다면체(Convex Polytope)입니다.

부호화기는 이 조건을 직접 구현합니다. 즉, 입력 벡터 $x$가 주어지면 모든 코드워드와의 거리를 계산하여 가장 가까운 코드워드의 인덱스를 출력합니다.

$$Q(x) = \arg \min_{y_i \in \mathcal{C}} d(x, y_i)$$

4.2 중심 조건 (Centroid Condition)

분할 영역 $\{R_i\}$가 고정되어 있을 때, 평균 왜곡을 최소화하는 각 코드워드는 해당 분할 영역 내 입력 벡터들의 조건부 기댓값(Conditional Expectation), 즉 중심(Centroid)입니다.

$$y_i = E[X \mid X \in R_i] = \frac{\int_{R_i} x\, p(x)\, dx}{\int_{R_i} p(x)\, dx}$$

이는 표본 평균이 제곱 오차를 최소화한다는 잘 알려진 사실에서 직접 유도됩니다.

실제로는 입력 분포 $p(x)$가 명시적으로 주어지지 않고 학습 데이터(Training Set) $\{x_1, x_2, \dots, x_M\}$만이 제공되는 경우가 일반적입니다. 이때 중심 조건은 표본 평균으로 근사됩니다.

$$y_i = \frac{1}{|R_i|} \sum_{x_m \in R_i} x_m$$

여기서 $|R_i|$는 $R_i$에 속하는 학습 벡터의 개수입니다.

이 두 조건은 서로에 대한 필요 조건일 뿐 충분 조건은 아닙니다. 즉, 두 조건을 동시에 만족하는 양자화기는 국소 최적해(Local Minimum)일 수 있으며, 전역 최적해를 보장하지는 않습니다.

 

5. LBG 알고리즘

위의 두 조건을 교대로 반복 적용하여 양자화기를 설계하는 것이 1980년 Linde, Buzo, Gray가 제안한 LBG 알고리즘입니다. 이는 스칼라 양자화의 Lloyd 알고리즘을 벡터 영역으로 일반화한 것으로, 벡터 양자화의 사실상 표준 설계 기법으로 자리 잡았습니다. 이 알고리즘의 수학적 뼈대는 k-means와 유사하지만, 지역 최적해에 빠질 가능성을 완화하기 위해 스플리팅(Splitting)이라는 고유하고 체계적인 초기화 방식을 사용합니다.

5.1 알고리즘의 진행

학습 데이터 $\mathcal{T} = \{x_1, x_2, \dots, x_M\}$, 목표 코드북 크기 $N$, 수렴 임계값 $\epsilon$이 주어졌을 때 LBG 알고리즘은 다음과 같이 진행됩니다.

1. 초기 코드북 설정: 초기 코드북 $\mathcal{C}^{(0)} = \{y_1^{(0)}, \dots, y_N^{(0)}\}$을 설정합니다.
2. 할당 단계(Nearest Neighbor): 현재 코드북을 기준으로 학습 벡터를 가장 가까운 코드워드에 할당하여 분할 영역 $R_i^{(n)}$을 구성합니다.
3. 갱신 단계(Centroid): 각 분할 영역의 중심을 계산하여 새로운 코드워드 $y_i^{(n+1)}$로 삼습니다.
4. 수렴 판정: 평균 왜곡의 상대 감소율이 $\epsilon$ 이하이면 종료합니다. 그렇지 않으면 단계 2로 돌아갑니다.

$$\frac{D^{(n)} - D^{(n+1)}}{D^{(n)}} < \epsilon$$

각 반복에서 평균 왜곡 $D^{(n)}$은 단조 감소하며, 하한(0)이 존재하므로 알고리즘은 반드시 수렴합니다. 다만 그 수렴점이 전역 최적해라는 보장은 없습니다.

5.2 초기 코드북 설계: 분할법 (Splitting)

초기 코드북을 임의로 여러 개 설정하는 대신, LBG 알고리즘은 전체 데이터 벡터들의 단일 무게중심인 단 1개의 코드워드에서 출발합니다. 이후 이 코드워드에 미세한 섭동(Perturbation) 벡터 $\delta$를 더하고 빼서 두 개의 새로운 코드워드로 분화시킵니다. 수식으로 표현하면 기존의 코드워드 $c$가 $c + \delta$와 $c - \delta$라는 두 개의 초기값으로 쪼개지는 것입니다.

1. 전체 학습 데이터의 중심을 단일 코드워드 $y_1$로 삼습니다 (크기 1 코드북).
2. 각 코드워드를 작은 섭동(Perturbation) $\delta$만큼 분할합니다.
   $$y_i \rightarrow \{y_i + \delta, \, y_i - \delta\}$$
3. 분할된 $2N$개의 코드워드로 LBG 알고리즘을 수행하여 코드북을 갱신합니다.
4. 목표 크기에 도달할 때까지 단계 2와 3을 반복합니다.

이 방법은 직전 단계의 최적해에서 다음 단계를 시작하므로, 무작위 초기화보다 안정적이고 일관된 결과를 제공합니다.

5.3 시각화 자료를 통한 LBG 알고리즘 시뮬레이션

아래 시각화 자료는 LBG 알고리즘의 특징인 1개의 코드워드에서 시작하여 점진적으로 코드워드의 개수를 늘려가는 방식과 $N$개의 코드워드를 무작위로 설정하고 수행하는 방식을 비교할 수 있도록 하였습니다. 설계 방법에서 분할법을 선택하면 LBG 알고리즘을 시뮬레이션할 수 있습니다. 참고로 위젯의 '직접 학습(무작위 초기화)' 모드는 사실상 k-means 알고리즘과 동등하며, 두 방법의 차이는 본질적으로 초기화 전략에 있음을 시각적으로 확인하실 수 있습니다.

LBG 알고리즘 시뮬레이션

데이터 분포 가우시안 혼합 (3개 클러스터) 고리 형태 두 클러스터 균일 분포

설계 방법 분할법 (1 → 2 → 4 → 8) 직접 학습 (무작위 초기화)

코드워드 수 N = 6

 

코드워드 수 N 0

반복 횟수 0

평균 왜곡 D -

데이터 포인트 0

데이터를 생성하고 있습니다...

 

6. 벡터 양자화의 한계

이론적 우수성에도 불구하고 벡터 양자화는 다음과 같은 실용적 어려움을 안고 있습니다.

• 부호화 복잡도: 가장 가까운 코드워드를 찾기 위해 $N$개의 코드워드 전체와의 거리를 계산해야 합니다. 샘플당 비트율을 $R$로 유지하면서 차원 $k$를 늘리면 $N = 2^{kR}$이 지수적으로 증가하므로, 부호화 계산량 역시 지수적으로 증가합니다.
• 저장 공간: 코드북 자체를 부호화기와 복호화기 양쪽에 저장해야 하며, 그 크기는 $N \cdot k$에 비례합니다.
• 학습 데이터 의존성: 코드북은 학습 데이터의 통계 특성을 반영하므로, 학습 데이터와 다른 분포를 가진 입력에 대해서는 성능이 저하될 수 있습니다.
• 차원의 저주: 차원 $k$가 클수록 학습에 필요한 데이터의 양도 기하급수적으로 증가합니다.

이러한 한계를 완화하기 위해 트리 구조 벡터 양자화(Tree-Structured VQ), 다단계 벡터 양자화(Multi-Stage VQ), 격자 벡터 양자화(Lattice VQ), 곱 벡터 양자화(Product VQ) 등 다양한 변형이 제안되어 왔습니다.

 

7. 응용

벡터 양자화는 다양한 분야에서 활용되어 왔으며 지금도 새로운 영역으로 확장되고 있습니다.

• 음성 부호화: CELP(Code-Excited Linear Prediction)에서 LPC 계수와 여기 신호를 벡터 양자화하여 저비트율 음성 압축을 실현합니다.
• 영상 압축: 초기 영상 압축 표준에서 블록 단위 벡터 양자화가 사용되었으며, 현재도 색상 양자화(color quantization) 등에 활용됩니다.
• 특징 표현 및 검색: 컴퓨터 비전에서 SIFT, SURF 등의 특징점을 코드북으로 표현하는 Bag-of-Visual-Words 모델은 영상 검색과 분류의 표준 기법으로 자리 잡았습니다.
• 딥러닝 생성 모델: VQ-VAE는 잠재 표현을 이산 코드북으로 양자화하여 자기회귀 생성 모델(autoregressive generative model)과 결합 가능한 형태로 만듭니다. VQ-VAE 및 그 변형(dVAE 등)은 DALL-E, Jukebox 같은 대규모 생성 모델의 핵심 구성 요소가 되었습니다.
• 신경망 압축: 거대 신경망의 가중치를 벡터 양자화로 압축하여 메모리와 계산량을 줄이는 연구가 활발히 진행되고 있습니다.

 

마치며

이번 글에서는 신호 처리와 데이터 압축의 유서 깊은 이론인 벡터 양자화에 대해 자세히 알아보았습니다. 다차원 공간에서 데이터를 효율적으로 군집화하고 대표값을 찾아내는 이 일련의 수학적 과정은 단순히 파일 용량을 줄이는 수단에 머물지 않습니다. 오히려 데이터가 가진 핵심적인 특성을 추출하고 이산화하여 더 큰 규모의 AI 모델이 정보를 쉽게 이해할 수 있도록 돕는 훌륭한 다리 역할을 하고 있습니다.

본 글에서 다룬 두 가지 최적 조건(최근접 이웃 조건과 중심 조건)과 LBG 알고리즘은 40년이 넘는 시간 동안 이 분야의 토대로 자리해 왔으며, k-means 클러스터링과 VQ-VAE의 코드북 학습에 이르기까지 그 본질은 변하지 않습니다. 도메인이 바뀌어도 변하지 않는 이러한 원리를 이해하는 것은, 새로운 기법이 등장할 때마다 그 본질을 빠르게 파악하고 응용 가능성을 가늠하는 데 큰 도움이 됩니다. 전통적인 디지털 신호 처리 분야에서 하드웨어 코덱 최적화를 위해 연구되던 LBG 알고리즘과 벡터 양자화 이론은, 현재 딥러닝 네트워크 구조 안으로 성공적으로 융합되었습니다. 

 

📖 참고문헌

1. Linde, Y., Buzo, A., & Gray, R. M. (1980).
   An Algorithm for Vector Quantizer Design.
   IEEE Transactions on Communications, 28(1), 84–95. https://doi.org/10.1109/TCOM.1980.1094577
2. Gray, R. M. (1984).
   Vector Quantization.
   IEEE ASSP Magazine, 1(2), 4–29. https://doi.org/10.1109/MASSP.1984.1162229
3. Gersho, A., & Gray, R. M. (1992).
   Vector Quantization and Signal Compression.
   Kluwer Academic Publishers.
4. Lloyd, S. P. (1982).
   Least Squares Quantization in PCM.
   IEEE Transactions on Information Theory, 28(2), 129–137. https://doi.org/10.1109/TIT.1982.1056489
5. Shannon, C. E. (1959).
   Coding Theorems for a Discrete Source with a Fidelity Criterion.
   IRE National Convention Record, 7(4), 142–163.
6. Gersho, A. (1979).
   Asymptotically Optimal Block Quantization.
   IEEE Transactions on Information Theory, 25(4), 373–380. https://doi.org/10.1109/TIT.1979.1056067
7. Schroeder, M. R., & Atal, B. S. (1985).
   Code-Excited Linear Prediction (CELP): High-Quality Speech at Very Low Bit Rates.
   ICASSP 1985, 937–940. https://doi.org/10.1109/ICASSP.1985.1168147
8. van den Oord, A., Vinyals, O., & Kavukcuoglu, K. (2017).
   Neural Discrete Representation Learning.
   NeurIPS 2017. https://arxiv.org/abs/1711.00937