율–왜곡 이론(Rate–distortion theory)

원천 부호화 정리⁠(source coding theorem)⁠는 원래대로 정확히 되살려야 하는 무손실 압축⁠(lossless compression)⁠의 한계였습니다. 그런데 소리의 세기나 화소의 밝기 같은 실수⁠(real number)⁠ 값은 무손실로는 아예 적을 수 없습니다. 실수 하나를 정확히 적는 데는 비트가 끝없이 들기 때문입니다. 그렇다면 오차를 얼마만큼 받아들일 때 몇 비트가 필요할까요? 섀넌은 1948년 논문의 끝에서 이 물음의 밑그림을 그렸고, 1959년 논문 「충실도 기준이 있는 이산 원천의 부호화 정리」에서 율–왜곡 함수⁠(rate–distortion function)⁠ $R(D)$를 정식으로 다뤘습니다. 표본들이 서로 독립⁠(independence)⁠이고 같은 분포를 따를 때, 평균⁠(mean)⁠ 왜곡이 D를 넘지 않게 되살리려면 표본 하나에 적어도 $R(D)$비트가 필요하고, 표본을 길게 묶어 부호화하면 그보다 조금만 더 써서 평균 왜곡을 D에 얼마든지 가깝게 할 수 있습니다. $R(D)$는 원래 값과 되살린 값이 공유해야 하는 상호 정보량⁠(mutual information)⁠의 최솟값으로 정의되고, 그 값이 정말 필요한 비트 수와 같다는 것이 섀넌의 정리입니다.

정규분포 $N(0, \sigma^2)$를 따르는 표본을 평균 제곱 오차(틀린 정도를 제곱해 평균한 값)로 잴 때 답은 간단합니다. $R(D) = \tfrac12 \log_2 (\sigma^2 / D)$, 거꾸로 쓰면 $D(R) = \sigma^2\, 2^{-2R}$입니다. 비트 하나를 더 쓸 때마다 오차가 4분의 1로 줄고, 신호 대 잡음비⁠(signal-to-noise ratio)⁠로는 $10 \log_{10} 4 \approx 6.02$ dB씩 좋아집니다. 분산이 같은 원천 가운데 정규분포가 가장 압축하기 어렵습니다. 분산이 정해졌을 때 엔트로피⁠(entropy)⁠가 가장 큰 분포이기 때문입니다(최대 엔트로피 원리⁠, principle of maximum entropy⁠).

가장 단순한 손실 압축⁠(lossy compression)⁠은 표본 하나마다 R비트, 곧 $2^R$개의 대표값 가운데 가장 가까운 것 하나를 골라 그 번호를 적는 스칼라 양자화입니다. $\sigma = 1$로 두고, R = 비트(대표값 개), 양자화기⁠(quantizer)⁠는 입니다. 흰검은 점을 끌어 표본을 옮겨 보세요.

균일 양자화기는 대표값을 같은 간격으로 놓고 간격만 가장 좋게 고른 것입니다. 드문 꼬리에 대표값을 낭비하고, 흔한 가운데는 성기게 덮습니다. 벨 연구소의 스튜어트 로이드(1957년 사내 보고서, 1982년 출판)와 조엘 맥스(1960)는 가장 좋은 양자화기가 두 조건을 만족해야 함을 보였습니다. 칸의 경계는 이웃한 두 대표값의 한가운데이고(표본을 가장 가까운 대표값으로 보내므로, 칸은 1차원 보로노이 칸입니다), 대표값은 자기 칸에 떨어지는 표본의 평균, 곧 무게중심입니다. 두 조건을 번갈아 맞추는 것이 로이드 알고리즘⁠(Lloyd's algorithm)⁠이고, 분포 대신 데이터 점에 쓰면 그대로 k-평균 군집입니다. 점을 한 대표값에 딱 잘라 배정하는 대신 확률⁠(probability)⁠로 나눠 배정하면, 정규분포들이 섞인 모형에 대한 EM 알고리즘⁠(algorithm)⁠이 됩니다. 두 조건은 최적이기 위한 필요조건⁠(necessary condition)⁠이라 일반적으로는 국소 최적에 멈출 수도 있지만, 정규분포처럼 밀도의 로그가 오목한 분포에서는 답이 하나뿐이라 그 답에 닿습니다. 로이드–맥스로 바꾸면 대표값이 가운데로 모이고, R이 3 이상에서 균일 양자화기와의 차가 벌어집니다.

그래도 섀넌 한계와는 틈이 남습니다. R이 커지면 로이드–맥스 양자화기⁠(Lloyd–Max quantizer)⁠의 오차는 $\tfrac{\sqrt3\,\pi}{2}\,\sigma^2\, 2^{-2R}$에 다가가, 한계보다 약 4.35 dB 모자랍니다. 대표값의 번호를 고정 길이로 적는 대신 흔한 칸의 번호에 짧은 부호를 주면(허프만 부호⁠(Huffman coding)⁠, 산술 부호화⁠(arithmetic coding)⁠) 비트 수가 번호의 엔트로피 $H(\hat X)$로 줄어듭니다. 이때는 오히려 촘촘한 균일 칸이 거의 가장 좋고, 청록 곡선처럼 한계와의 차가 $10 \log_{10} (\pi e / 6) \approx 1.53$ dB(비트로는 약 0.254비트)로 일정해집니다. 비트가 넉넉한 영역에서 이 마지막 1.53 dB는 표본을 하나씩 따로 양자화⁠(quantization)⁠하는 한 없앨 수 없습니다. 표본 여러 개를 한 벡터⁠(vector)⁠로 묶어 고차원 공간을 칸으로 나누는 벡터 양자화⁠(vector quantization)⁠는 차원을 키울수록 이 틈을 좁혀, 극한⁠(limit)⁠에서 닫습니다. 1차원의 칸은 선분일 수밖에 없지만, 차원이 높아지면 공에 점점 가까운 모양의 칸으로 공간을 빈틈없이 채울 수 있어 같은 부피에서 평균 제곱 오차가 작아지기 때문입니다. 무손실 압축에서 기호를 길게 묶을수록 엔트로피에 다가가던 것과 같은 이야기입니다.

실제 신호는 표본끼리 닮아 있습니다. 서로 독립인 정규 성분 여러 개에 비트를 나눠 줄 때의 답은 거꾸로 물 채우기입니다. 모든 성분의 오차를 같은 수위 θ에 맞추되, 분산이 θ보다 작은 성분에는 비트를 하나도 주지 않고 통째로 버립니다: $D_i = \min(\theta, \sigma_i^2)$, $R = \sum_i \tfrac12 \log_2 (\sigma_i^2 / D_i)$. 이산 코사인 변환⁠(discrete cosine transform)⁠은 이웃 화소의 닮음을 풀어, 분산이 큰 몇 개의 낮은 진동수⁠(frequency)⁠ 계수와 분산이 작은 많은 높은 진동수 계수로 나눕니다. JPEG은 앞의 것에 비트를 몰아주고 뒤의 것은 거칠게 양자화하거나 0으로 버립니다. MP3와 AAC는 여기에 사람 귀의 가림 효과(큰 소리 바로 곁의 작은 소리는 들리지 않는 현상)를 왜곡의 잣대로 넣어, 들리지 않는 오차에는 비트를 쓰지 않습니다.

이어지는 곳. 율–왜곡 함수는 통로 용량⁠(channel capacity)⁠과 짝을 이룹니다. 표본 하나마다 용량⁠(capacity)⁠이 C인 통로를 한 번 쓸 수 있을 때 정규 원천을 보내며 얻을 수 있는 가장 작은 오차는 $\sigma^2 2^{-2C}$이고, 길게 묶어 보내는 극한에서는 압축과 전송을 따로 가장 잘 하는 것이 합쳐서 가장 잘 하는 것과 같습니다(섀넌의 분리 정리⁠(source–channel separation theorem)⁠). 오차 $2^{-2R}$과 섀넌–하틀리 정리⁠(Shannon–Hartley theorem)⁠의 $\tfrac12 \log_2(1 + \text{SNR})$은 같은 로그의 두 얼굴입니다. 소리를 디지털로 만드는 가장 기본적인 방법인 PCM(펄스 부호 변조⁠, pulse-code modulation⁠)은 표본화 정리⁠(sampling theorem)⁠에 따라 표본을 뽑은 뒤 각 표본을 이렇게 양자화합니다. 정규분포를 따르는 상관된 성분을 먼저 서로 독립인 축으로 돌리는 최선의 변환은 주성분 분석⁠(principal component analysis)⁠이고, 이웃끼리 강하게 닮은 신호에서 DCT는 그 빠른 근사입니다. 큰 언어 모델⁠(language model)⁠의 가중치⁠(weight)⁠를 8비트나 4비트 정수⁠(integer)⁠로 줄이는 양자화도, 적은 비트를 출력이 덜 망가지는 쪽으로 나누는 이 저울질의 한 예입니다(언어 모델의 발전사).