벡터 양자화

통계 수치해석 소프트웨어 마지막 수정: 2026-08-13 04:27:41

1. 개요[편집]

벡터 양자화(vector quantization, VQ)는 $k$ 차원 벡터 공간 전체를 유한 개의 대표 벡터 집합(코드북)으로 대신하는 손실 압축이다. 입력 벡터 $\mathbf{x} \in \mathbb{R}^k$ 가 들어오면 코드북 $\mathcal{C} = \{\mathbf{c}_1,\dots,\mathbf{c}_K\}$ 중 가장 가까운 것을 골라 그 인덱스만 저장·전송하고, 복원할 때는 인덱스로 코드워드를 꺼내 온다. 즉 데이터를 보내는 게 아니라 “몇 번 서랍”을 보낸다.

Q(\mathbf{x}) = \mathbf{c}_{i^*}, \qquad i^* = \arg\min_{i} \lVert \mathbf{x}-\mathbf{c}_i \rVert^2

수치·통계 쪽 사람에게는 k-평균 군집화와 같은 물건으로 보일 것이고, 실제로 같은 물건이다(아래 절 참고). 다른 것은 목적이다. 군집화는 “데이터에 어떤 구조가 있나”를 묻고, 벡터 양자화는 “몇 비트를 쓸 때 왜곡을 얼마나 줄일 수 있나”를 묻는다. 질문이 다르니 따라오는 이론(율-왜곡)과 공학(탐색 구조)이 다르다.

2. 보로노이 구역과 왜곡[편집]

인코더가 하는 일은 공간을 조각내는 것이다. 코드워드 $\mathbf{c}_i$ 로 부호화되는 입력들의 집합

R_i = \{\mathbf{x} : \lVert \mathbf{x}-\mathbf{c}_i\rVert \le \lVert\mathbf{x}-\mathbf{c}_j\rVert \ \forall j\}

을 부호화 구역이라 하고, 유클리드 거리를 쓰면 이것이 정확히 코드워드들의 보로노이 다이어그램이다. 경계는 항상 초평면 조각이고 각 구역은 볼록 다면체다. 성능 지표는 평균 왜곡

D = \mathbb{E}\big[\lVert \mathbf{X}-Q(\mathbf{X})\rVert^2\big] = \sum_{i=1}^{K}\int_{R_i} \lVert \mathbf{x}-\mathbf{c}_i\rVert^2 p(\mathbf{x})\, d\mathbf{x}

이고, 비용 지표는 비트율이다. 코드워드가 $K$ 개면 인덱스 하나에 $\log_2 K$ 비트, 벡터 차원이 $k$ 이므로 표본당

R = \frac{\log_2 K}{k} \quad [\text{bit/dimension}]

가 된다. 여기서 VQ 설계의 근본 긴장이 다 보인다. $K$ 를 키우면 $D$ 는 줄지만 $R$ 은 $\log_2 K$ 로만 늘고, 대신 탐색 비용은 $K = 2^{Rk}$ 로 지수적으로 폭발한다. 이론이 좋아지는 방향과 계산이 감당되는 방향이 정반대라는 것이 이 분야의 모든 트릭이 존재하는 이유다.

3. 로이드 조건 — 최적 양자기의 두 가지 필요조건[편집]

$D$ 를 최소화하는 양자기가 만족해야 하는 두 조건이 있다. 인코더와 디코더를 번갈아 고정하고 미분하면 바로 나온다.

최근접 조건(nearest neighbor condition). 코드북을 고정하면, 최적 분할은 보로노이 분할이다. 각 점을 가장 가까운 코드워드에 보내는 것보다 왜곡이 작을 수는 없다.
중심 조건(centroid condition). 분할을 고정하면, 각 구역의 최적 코드워드는 그 구역의 조건부 기댓값 $\mathbf{c}_i = \mathbb{E}[\mathbf{X} \mid \mathbf{X}\in R_i]$ 이다.

제곱오차의 최소점이 평균이라는 사실 그대로다. 왜곡 척도를 바꾸면 이 갱신식도 같이 바뀐다 — $\ell_1$ 왜곡이면 성분별 중앙값, 이토쿠라-사이토 왜곡이면 또 다른 형태가 나온다. 목적함수가 갱신식을 결정한다.

중요한 것은 이 둘이 필요조건일 뿐 충분조건이 아니라는 점이다. 둘 다 만족하는 코드북(고정점)은 무수히 많고, 그중 전역 최적은 하나다. 최적 VQ 설계는 k-평균 군집화와 마찬가지로 NP-난해이며, 실무는 좋은 고정점을 찾는 휴리스틱으로 산다.

4. LBG 알고리즘[편집]

두 조건을 번갈아 강제하는 반복이 LBG 알고리즘(Linde–Buzo–Gray, 1980)이며, 일반화 로이드 알고리즘(GLA)이라고도 부른다.

초기 코드북을 잡는다.
부호화 단계 — 학습 벡터를 전부 최근접 코드워드에 배정한다(최근접 조건).
갱신 단계 — 각 코드워드를 배정받은 벡터들의 평균으로 옮긴다(중심 조건).
왜곡 감소율이 문턱 아래로 떨어질 때까지 반복.

두 단계 모두 $D$ 를 증가시키지 않으므로 왜곡은 단조 감소하고 반복은 반드시 멈춘다. 원논문의 진짜 기여는 여기에 두 가지가 더 붙어 있다는 점이다. 하나는 왜곡 척도가 제곱거리가 아니어도 되는 일반적 틀로 정리한 것(그래서 이름이 “generalized”), 다른 하나는 초기화다.

분할 초기화(splitting). 코드워드 1개로 시작한다(= 전체 평균). 각 코드워드를 $\mathbf{c} \pm \boldsymbol{\varepsilon}$ 로 미세하게 쪼개 2개로 만들고 수렴시킨다. 다시 쪼개 4개, 8개, … $K$ 개까지 간다. $K$ 가 2의 거듭제곱일 때 딱 떨어지고, 각 단계의 해가 다음 단계의 좋은 출발점이라 무작위 초기화보다 훨씬 안정적이다. k-평균 군집화의 k-means++가 나오기 전까지 이쪽이 사실상 표준 초기화였고, 지금도 계층 구조가 필요한 곳(트리 구조 VQ)에서는 분할 쪽이 유리하다.

빈 구역(empty cell) 처리는 구현 필수 항목이다. 아무 벡터도 배정받지 못한 코드워드는 그대로 두면 영원히 죽어 있으므로, 왜곡이 가장 큰 구역을 찾아 그 안에서 쪼개 재활용한다. 신경망 시대에 코드북 붕괴라는 이름으로 같은 문제가 다시 등장한다.

5. 왜 스칼라가 아니라 벡터인가[편집]

성분마다 따로 양자화(스칼라 양자화)하면 구현이 훨씬 쉬운데 왜 굳이 벡터로 묶을까. 이득의 출처가 셋이다.

이득	출처	상관 없는 독립 성분에서도?
공간 채움(granular)	다차원에서 더 둥근 셀을 쓸 수 있음	있음
모양(shape)	주변분포 모양에 셀 크기를 맞춤	있음
기억(memory)	성분 간 통계적 종속 활용	없음

핵심은 성분들이 완전히 독립이어도 벡터 양자화가 이긴다는 것이다. 스칼라 양자기를 $k$ 개 쓰면 셀이 초입방체가 되는데, 초입방체는 같은 부피에서 관성모멘트가 최적이 아니다. 고해상도 극한에서 이 공간 채움 이득의 상한은

10\log_{10}\frac{2\pi e}{12} \approx 1.53\ \text{dB}

로, 비트율로 환산하면 표본당 약 0.2546 비트다. 커 보이지 않지만 이건 차원을 무한히 키웠을 때의 값이고, 섀넌의 율-왜곡 한계에 실제로 도달하려면 차원이 커진 벡터 양자기가 필요하다는 이론적 사실과 짝을 이룬다. 반대로 말하면, 스칼라 양자화에 좋은 엔트로피 부호화(허프만 부호화 등)를 붙이는 것만으로도 이 1.53 dB 안쪽까지는 따라올 수 있다는 뜻이기도 하다 — 실무에서 JPEG류가 스칼라 양자화로 버티는 이유다.¹

6. 고해상도 이론 — 왜곡은 비트율에 어떻게 붙나[편집]

$K$ 를 충분히 크게 잡아 셀이 작아지면 각 셀 안에서 밀도 $p(\mathbf{x})$ 가 거의 상수라고 볼 수 있고, 그러면 왜곡을 닫힌 형태로 근사할 수 있다. 자도르(Zador)의 고해상도 공식은

D \;\approx\; C_k \, 2^{-2R} \left[\int p(\mathbf{x})^{\frac{k}{k+2}}\, d\mathbf{x}\right]^{\frac{k+2}{k}}

꼴이며, 여기서 $C_k$ 는 차원에만 의존하는 상수다. 세 가지가 한눈에 읽힌다.

$2^{-2R}$ — 비트당 6 dB. 표본당 1비트를 더 쓸 때마다 왜곡이 4배(= 6.02 dB) 줄어든다. 양자화 세계의 국룰이며, 스칼라 양자화든 벡터 양자화든 기울기는 같다. 차이는 절편에서만 난다.
밀도 항. 지수 $k/(k+2)$ 짜리 적분이 “이 분포가 얼마나 퍼져 있는가”를 재고, 이것이 모양 이득의 정체다. 분산이 같아도 첨도가 크면(뾰족하면) 왜곡이 작다.
$C_k$ — 셀 모양 값. 최적 셀 모양이 무엇인가는 사실 미해결이다. 거쇼 추측은 고해상도 극한에서 최적 분할이 어떤 고정된 다면체 하나로 공간을 타일링하는 형태라고 말하며, $k=1$ (구간)과 $k=2$ (정육각형)에서는 증명되어 있지만 일반 차원에서는 여전히 추측이다.

기준선은 율-왜곡 이론이 주는 하한이다. 분산 $\sigma^2$ 인 가우시안 원천의 이론적 하한이

D(R) = \sigma^2 2^{-2R}

이고, 어떤 압축기도 이보다 잘할 수 없다. 스칼라 양자기는 이 하한에서 1.53 dB 위에 붙고, 벡터 양자기는 차원 $k$ 를 키우며 그 간격을 조금씩 메운다 — 다만 $k$ 를 키운 만큼 코드북이 $2^{Rk}$ 로 커지므로 이론적 최적성과 계산 가능성이 정확히 반대로 움직인다. 이 절과 다음 절이 벡터 양자화라는 분야의 전부라고 해도 과언이 아니다.

7. 지수 폭발을 우회하는 구조들[편집]

전수 탐색 VQ는 $K = 2^{Rk}$ 번의 거리 계산이 필요하다. 표본당 1비트, 차원 64면 코드워드가 $2^{64}$ 개다. 실무 VQ의 역사는 이 벽을 우회한 역사다.

트리 구조 VQ. 분할 초기화를 그대로 탐색 구조로 쓴다. 이진 트리를 따라 내려가며 매 단계 두 자식 중 가까운 쪽만 고르면 탐색이 $O(\log K)$ . 대신 탐욕적 선택이라 전수 탐색보다 왜곡이 크다.
격자 VQ(lattice VQ). 코드북을 데이터에서 배우지 않고 규칙적인 격자( $D_4$ , $E_8$ , 리치 격자 등)로 못 박는다. 최근접 코드워드를 반올림 몇 번으로 닫힌 형태로 찾을 수 있어 탐색이 사실상 공짜. 대신 데이터 분포에 적응하지 못한다.
곱 양자화(product quantization, PQ). $D$ 차원 벡터를 $m$ 개의 부분 벡터로 자르고 각 부분마다 작은 코드북( $K_s = 256$ 이 국룰)을 둔다. 유효 코드워드 수는 $K_s^{m}$ 인데 학습·저장은 $m K_s$ 개면 된다. 벡터 하나가 $m$ 바이트로 줄어드는 셈. 검색할 때는 질의를 양자화하지 않고 비대칭 거리 계산을 쓴다 — 질의와 각 부분 코드워드의 거리를 $m \times K_s$ 표에 미리 채워 두고, 후보 벡터마다 표에서 $m$ 번 조회해 더하면 거리 근사가 나온다. 곱셈이 아니라 룩업 $m$ 번이라, 10억 개 벡터 규모의 최근접 이웃 탐색이 메모리 안에서 돌아가게 만든 결정적 기법이다.²
잔차 양자화(residual/multi-stage VQ). 1단 코드북으로 근사한 뒤 잔차 $\mathbf{x}-\mathbf{c}^{(1)}$ 를 2단 코드북으로 다시 양자화하고, 그 잔차를 또 3단으로… 단을 $L$ 개 쌓으면 유효 코드워드가 $K^{L}$ 인데 저장은 $LK$ . 각 단이 앞 단의 오차를 갚는 구조라 점진적 전송(coarse-to-fine)이 공짜로 따라온다. 요즘 신경 오디오 코덱이 잔차 VQ를 쓰는 이유가 이 성질이다.

곱 양자화는 “공간을 쪼갠다”, 잔차 양자화는 “정밀도를 쌓는다”로 요약된다. 둘을 섞은 변형(최적화 곱 양자화, 가법 양자화)도 많다.

8. k-평균과 정확히 같은 알고리즘이다[편집]

여기서 이름을 정리하고 가자. LBG 알고리즘 = 로이드 알고리즘 = k-평균 알고리즘이다. 부호화 단계는 k-평균의 배정 단계, 갱신 단계는 중심 갱신, 목적함수는 군집내 제곱합(관성). 완전히 같은 반복이며 k-평균 군집화 문서의 논의(수렴성, 초기화 민감성, 지역 최적, 보로노이-CVT 대응)가 전부 그대로 적용된다.

역사적으로 로이드는 1957년 벨연구소 내부 보고서에서 스칼라 양자기 설계 문제로 이 반복을 유도했고(정식 출판은 1982년), 린데-부조-그레이가 1980년에 벡터·일반 왜곡 척도로 확장했으며, 같은 시기 통계 쪽에서는 맥퀸의 “k-means”라는 이름이 정착해 있었다. 같은 알고리즘이 세 커뮤니티에서 세 번 발견되고 세 이름을 가진 사례. 실무적 차이는 강조점뿐이다.

	k-평균 군집화	벡터 양자화
목적	데이터 구조 발견	비트율 대비 왜곡 최소화
$K$ 선택	엘보·실루엣·갭 통계	비트 예산이 정해 줌( $K=2^{Rk}$ )
관심	군집 해석	인코딩·디코딩 속도, 코드북 저장
전형적 $K$	수~수십	256~65536

$K$ 를 사람이 고민해서 정해야 하는 군집화와 달리, VQ에서는 “이 오디오 프레임에 24비트 쓸 수 있다”가 $K = 2^{24}$ 를 결정해 준다. 이 바닥에서 $K$ 선택이 논쟁거리가 아닌 이유다.

9. 설계할 때 실제로 정해야 하는 것들[편집]

논문이 아니라 코드를 짜는 입장에서 결정 사항은 다음 다섯 개로 압축된다.

차원 $k$ 를 어떻게 자를 것인가. 상관이 큰 성분끼리 한 벡터에 묶어야 기억 이득이 나온다. 시계열이면 인접 프레임, 이미지면 인접 블록, 임베딩이면 그냥 연속 구간(곱 양자화의 기본값)이다. 잘 모르겠으면 주성분 분석으로 회전시켜 분산이 비슷한 덩어리끼리 묶는 것이 무난하며, 실제로 곱 양자화의 성능이 성분 순서에 의외로 민감하다는 것이 알려져 있다.
왜곡 척도. 유클리드가 기본이지만 지각적으로 중요한 축에 가중치를 주는 경우가 흔하다. 가중 유클리드는 중심 조건이 여전히 가중평균이라 구현이 쉽고, 브레그만 발산 계열도 중심 조건이 그대로 산술평균으로 유지되는 좋은 성질이 있다. 이걸 벗어나면 갱신 단계가 최적화 문제로 승격된다.
정규화. 축마다 단위가 다르면 거리가 큰 축에 독점된다. k-평균 군집화와 같은 함정이고 처방도 같다. 방향만 중요한 임베딩이면 노름을 떼어 따로 스칼라 양자화하는 편이 낫다.
학습 데이터 양. 코드워드 하나당 학습 벡터가 최소 수십 개는 있어야 중심이 안정된다. 경험칙으로 $K$ 의 수십 배가 필요하고, 그보다 적으면 코드북이 학습 집합에 과적합해 실제 데이터에서 왜곡이 튄다.
인코딩 비용을 어디서 낼 것인가. 인코딩은 최근접 탐색( $O(K)$ ), 디코딩은 배열 조회( $O(1)$ )로 철저히 비대칭이다. 한 번 압축해 여러 번 푸는 용도(방송, 검색 인덱스)에는 최적이고, 실시간 양방향에는 구조적 VQ가 필수다.

10. 어디에 쓰이나[편집]

음성 코덱. VQ의 고전적 주무대. 선형예측 계수를 선스펙트럼쌍으로 바꿔 곱/분할 VQ로 압축하는 것이 CELP 계열 코덱의 심장이고, 여기서 곱 양자화·잔차 양자화 기법이 다 다듬어졌다.
색 양자화. 트루컬러 이미지를 256색 팔레트로 줄이는 것이 RGB 3차원 공간의 VQ다. GIF 인코더가 하던 일이 정확히 이것.
대규모 최근접 이웃 탐색. 임베딩 검색 인프라의 실질 표준이 “역인덱스로 후보를 좁히고 곱 양자화로 거리를 근사”하는 조합이다. 정확도를 조금 내주고 메모리를 한두 자릿수 줄인다.
신경망 잠재변수의 이산화. 인코더 출력을 코드북 최근접 벡터로 스냅해 이산 잠재 표현을 만드는 VQ-VAE 계열. 인덱스가 정수라서 그 위에 자기회귀 사전분포(트랜스포머)를 얹을 수 있다는 것이 결정적 장점 — 이미지·오디오 생성 모형이 “토큰 시퀀스 예측”으로 환원되는 통로가 여기다. 자세한 내용은 변분 오토인코더 문서 참고.
모델 압축. 가중치 행렬을 부분 벡터로 잘라 코드북으로 대체하는 것도 VQ다. 지식 증류가 “작은 모형을 새로 가르치기”라면 이쪽은 “같은 모형의 파라미터를 서랍 번호로 바꾸기”.

11. 신경망 시대의 벡터 양자화[편집]

VQ-VAE(2017)가 되살린 문제의식은 옛 VQ와 사실 같다. 코드북 갱신을 중심 조건 대신 경사하강으로 하려니 $\arg\min$ 에서 미분이 끊기는데, 처방이 직통 추정량(straight-through) — 순전파는 스냅한 코드워드를 쓰고 역전파는 그 기울기를 인코더 출력에 그대로 복사한다. 코드북 자체는 별도 손실로 학습하거나 지수이동평균 갱신을 쓰는데, 후자는 미니배치판 중심 조건 그 자체다. 즉 신경망 안에서 LBG의 갱신 단계를 미니배치 버전으로 돌리고 있는 것.

그리고 옛 문제가 새 이름으로 돌아온다.

코드북 붕괴. 코드워드 대부분이 한 번도 선택되지 않고 소수만 쓰인다. LBG의 빈 구역 문제와 완전히 같으며, 처방도 비슷하다 — 죽은 코드워드를 배치 안의 실제 벡터로 재초기화하거나(random restart), 왜곡이 큰 코드워드를 쪼갠다.³
초기화 민감성. k-평균으로 코드북을 초기화하면 학습이 눈에 띄게 안정된다. 40년 전 결론이 그대로 재확인된 것.
이산 표본추출. 확률적으로 코드워드를 뽑아야 하는 변형에서는 검벨-소프트맥스 완화가 등장한다(검벨 분포 참고).

40년 된 신호처리 기법이 딥러닝 논문의 핵심 부품으로 재등장하는 흔치 않은 사례이고, 그래서 요즘 VQ 구현을 디버깅하다 보면 결국 1980년 논문의 조언대로 하게 된다.⁴

12. 관련 문서[편집]

벡터 양자화는 1980년대에 “차세대 이미지 압축”으로 대대적으로 밀렸다가 JPEG(스칼라 양자화 + 엔트로피 부호화)에 완패한 전력이 있다. 이론적 우위 1.53 dB를 얻자고 디코더 쪽에 코드북을 통째로 실어야 하고 인코딩이 느렸으니, 표준화 싸움에서 이길 수가 없었다. 기술이 이론적으로 우월해도 배포 비용이 이긴다는 교과서적 사례. ↩
곱 양자화의 부분 코드북 크기가 거의 항상 256인 이유는 우아한 이론이 아니라 인덱스 하나가 1바이트로 딱 떨어지기 때문이다. 이 바닥 상수의 절반쯤은 이런 식으로 정해진다. ↩
코드북 붕괴를 처음 겪으면 “잠재 공간이 붕괴했다”며 손실함수를 뜯어고치게 되는데, 사용 중인 코드워드 개수를 찍어 보면 512개 중 7개만 살아 있는 경우가 흔하다. 죽은 코드워드를 배치에서 다시 심는 세 줄짜리 처방으로 끝나는 일에 며칠을 쓰는 것이 통과의례. ↩
그 패배한 기술이 40년 뒤 “이산 토큰이 필요한” 생성 모형에서 되살아난 것은, 이번엔 코드북을 실어 보내는 비용이 문제가 아니었기 때문이다. 모형 가중치가 수십 GB인 마당에 코드북 몇 MB는 반올림 오차다. ↩