압축과 예측의 수학적 동치가 적용되기 전에 고정되어야 하는 조건, 모델 비용, 표현의 연산 계약을 살펴본다.
지난 몇 주 동안 Hacker News에서 같은 주장을 반복해서 접했다. 압축은 예측이다라는 주장이다. 최근 논의는 양방향에서 이 주제에 접근했다. 3Blue1Brown의 두 영상, 엔트로피 다시 만들기와 그런데 교차 엔트로피란 무엇일까?는 소스 부호화의 한계에서 엔트로피와 교차 엔트로피를 유도한다. ngrok 글은 산술 부호화와 언어 모델을 통해 같은 수학을 따라간다. Salvatore Sanfilippo는 예측과 압축 사이의 결과적 동일시를 어디까지 받아들여야 하는지 묻는다.
이 설명들은 한 사실에서 만난다. 확률 모델은 가능한 모든 이어짐에 조건부 확률을 할당하고, 엔트로피 부호화기는 관측된 이어짐에 할당된 확률을 비트로 변환한다. 수열 $x_{1 : n}$ 및 모델 $Q$에 대해, 결과적인 이상적 페이로드 길이는
이며, 부호화 절차가 도입하는 오버헤드는 제외한다. 우변의 양은 모델의 누적 로그 손실이기도 하다. 이 설정에서는 로그 손실 아래에서 예측을 개선하는 것과 부호화된 페이로드를 줄이는 것이 같은 최적화 문제다.
이 대응의 바탕 자체는 새롭지 않다. 그 토대는 고전 정보 이론에 속한다. Shannon은 확률을 최적 부호 길이와 연결했고, 적응형 통계 압축기는 현대 언어 모델보다 훨씬 이전부터 조건부 추정을 부호로 바꾸었으며, 학습과 압축의 관계는 최소 설명 길이, 정보 이론과 추론에 대한 MacKay의 논의, Hutter Prize 같은 작업을 통해 발전해 왔다. 최근 언어 모델 결과는 이 오래된 대응을 새로운 규모에서 구현한 것일 뿐이다.
나는 지난 몇 년간 압축, 정보 이론, 압축 자료 구조를 연구해 왔고 내 견해를 보태고 싶다. 나는 이 동치에 동의한다. 내가 관심을 두는 것은 그것이 어디에서 시작하고 어디에서 끝나는가다. 이는 합의된 모델 아래에서 데이터를 부호화하는 비용을 설명하지만, 압축 문제는 그 모델을 적용하기 전부터 시작하며 가장 짧은 비트열이 만들어졌다고 해서 언제나 끝나는 것도 아니다. 부호화기와 복호화기는 어떤 종류의 객체를 표현하는지, 어떤 대안이 여전히 가능한지, 확률 모델을 어떻게 이용 가능하게 하는지, 복호화기가 그 표현으로 무엇을 할 수 있어야 하는지에 합의해야 한다.
이 글 전체에서 별도 언급이 없으면 _압축_은 무손실 압축을 뜻한다. 그 범위 안에서도 순차 모델을 도입하기 전에 압축을 정의할 수 있다. 허용되는 객체의 유한한 집합은 다음 기호를 식별하지 않고도 계수 하한을 제공한다. 고정 부호나 데이터 의존적 부호는 나중에 확률적으로 해석할 수 있고, 직렬화된 객체 위의 분포는 다음 기호 조건부 확률들로 분해할 수 있다. 하지만 그런 재해석이 객체 집합을 선택해 주거나, 복호화기에 없는 정보의 비용을 지불하거나, 임의 접근 같은 연산을 강제하지는 않는다.
따라서 질문은 예측과 압축을 수학적으로 동등하게 만들 수 있는가가 아니다. 가능하다. 질문은 그 동치가 적용되기 전에 무엇을 고정해야 하는지, 완전한 표현 중 어느 부분을 그 비트 수가 측정하는지, 그리고 그 측정 밖에 무엇이 남는지다.
수준에 관한 메모. 이 글은 다소 기술적이다. 학부 수준 수학과 기초적인 증명식 논증에 익숙하다고 가정하지만, 정보 이론의 사전 배경은 실제로 필요하지 않으며 있으면 도움이 될 수 있다.
목차 열기
ngrok 글은 축소화와 이른바 “진정한” 압축을 구분하며 시작한다. 축소화기는 주석, 공백, 그리고 실행에 영향을 주지 않는 소스 파일의 다른 부분을 제거한다. 결과 프로그램은 더 짧지만 원래 소스 파일은 그것으로부터 복원할 수 없다.
이 연산이 무손실인지는 표현이 무엇을 보존해야 하는지에 달려 있다. 객체가 원래 소스 바이트 수열이라면 축소화는 손실적이다. 객체가 프로그램의 동작이고 복호화기가 동작상 동등한 어떤 프로그램이든 돌려줄 수 있다면, 의미 보존 축소화기는 그 다른 계약에 대해서는 무손실이다. 변환은 바뀌지 않았다. 표현되는 객체가 바뀌었다.
이 구분은 모든 확률 모델보다 앞선다. 객체가 얼마나 그럴듯한지를 묻기 전에, 부호화기와 복호화기는 무엇이 그 객체로 간주되는지 그리고 언제 두 복호화 출력이 동등한 것으로 간주되는지 합의해야 한다. 그래야만 설명의 길이가 의미를 갖는다.
개별 객체 $x$가 고정되면, 가장 허용적인 효과적 설명은 그것을 생성하는 프로그램이다. 보편 기계 $U$를 선택한 뒤 이진 문자열 $x$의 Kolmogorov 복잡도는
K_{U} \left(\right. x \left.\right) = min \left{\right. \mid p \mid : U \left(\right. p \left.\right) = x \left.\right}이다. 따라서 $K_{U} \left(\right. x \left.\right)$는 $x$를 출력하는 가장 짧은 프로그램의 길이다. 알고리즘적으로 표현할 수 있는 모든 규칙성은 이 설명을 줄일 수 있다. 10억 개의 0으로 이루어진 문자열은 긴 리터럴 표현을 갖지만 10억 개의 0을 출력하는 짧은 프로그램을 갖는다. 이 정의는 문자열이 소스에서 표본 추출되었을 것을 요구하지 않으며, 한 기호를 그 앞 기호들로부터 예측할 것도 요구하지 않는다.
기계 $U$는 설명 언어의 일부다. 다른 보편 기계를 선택하면 이용 가능한 프로그램이 달라지고 따라서 복잡도의 정확한 값도 달라진다. 불변성 정리는 이 의존성을 제한한다. 두 고정된 보편 기계 $U$와 $V$에 대해 다음을 만족하는 상수 $c_{U , V}$가 존재한다.
이는 모든 문자열 $x$에 대해 성립한다. 상수는 두 기계에는 의존할 수 있지만 $x$에는 의존하지 않는다. 이는 한 설명 언어를 다른 언어에서 모의하는 데 필요한 고정 프로그램을 설명한다. 따라서 기계 선택은 프로그램을 생성하고 해석하는 사람들이 공유하는 설명 언어의 일부다. 이는 반복될 주제의 첫 사례다. 객체의 길이는 그 설명 바깥에서 이미 고정된 정보에 대해서만 의미가 있다.
Kolmogorov 복잡도는 개별 객체의 효과적 설명에 한계를 제공하지만 일반 압축 알고리즘을 제공하지는 않는다. 함수 $K_{U}$는 계산 가능하지 않다. 어떤 절차도 모든 문자열에 대해 가장 짧은 프로그램의 길이를 결정할 수 없으며, 그 프로그램을 구성하는 것은 더욱 불가능하다. 실용 압축기는 고려할 의사와 능력이 있는 설명을 제한해야 한다.
그러한 제한 중 하나는 객체가 유한 집합 $\mathcal{F}$에 속한다는 것이다. $\mathcal{F}$가 고정되면 무손실 표현은 그 집합의 모든 원소를 다른 모든 원소와 구별해야 한다. 고정 길이 부호화를 생각하자.
C : \mathcal{F} \rightarrow \left{\right. 0 , 1 \left.\right}^{ℓ}무손실 복호화는 $C$가 단사일 것을 요구한다. 길이 $ℓ$인 이진 문자열은 $2^{ℓ}$개뿐이므로, 단사성은
을 함의하고, 따라서
이다.
여기서부터의 논증도 같은 원리를 계속 적용한다. 가능한 객체 집합과 복호화기에 공유된 정보가 고정되면, Kraft–McMillan 부등식은 유일 복호 가능 부호의 길이를 확률 가중치와 연결한다. 순차화된 객체에 대해 연쇄 법칙을 적용하면 모델의 누적 로그 손실은 산술 부호화의 이상적 페이로드 길이가 된다. 반대로 유일 복호 가능 부호의 길이는 정규화 후 확률 분포를 유도하며, 그 분포는 다음 기호 조건부 확률로 분해될 수 있다.
그러나 실제 압축에서는 모델도 비용을 가진다. 모델이 파일 형식에 고정되어 있거나 미리 공유되었다면 개별 메시지의 조건부 길이에 그 전체 크기를 부과해서는 안 된다. 반면 오프라인으로 맞춘 모델이 복호화기에 없다면 표, 매개변수 또는 가중치의 설명이 데이터에 동반되어야 한다. 사전순차 부호화에서는 부호화기와 복호화기가 같은 초기 상태에서 시작하여 각 기호 뒤에 같은 갱신을 수행하므로 최종 매개변수를 전송할 필요가 없다. 대신 초기화, 갱신 규칙, 학습 절차, 수치 규약, 그에 영향을 주는 무작위성은 공유되거나 기술되어야 한다.
또한 가장 짧은 비트열이 언제나 가장 좋은 표현은 아니다. 비트 패킹된 벡터는 각 값에 고정 폭을 할당하므로 빈도 차이를 이용하지 못할 수 있지만, 인덱스에서 위치를 직접 계산해 vector[i]에 상수 시간으로 접근할 수 있다. 일반적인 산술 부호화 스트림에서는 위치의 복호화 상태가 이전 기호들과 문맥에 의존하므로, 해당 위치를 얻으려면 처음부터 또는 저장된 검사점부터 복호화해야 한다. 검사점은 접근을 빠르게 하지만 공간을 차지한다. 따라서 목표는 단순한 비트열 최소화가 아니라 필요한 연산을 만족하는 표현의 공간과 시간 사이의 절충이 된다.
그렇다면 압축은 예측인가? 부호화 문제가 고정된 뒤라면, 정확한 의미에서 그렇다. 이 동치는 합의된 모델 아래에서 부호화된 페이로드의 이상적 길이에 관한 것이다.
이 단서는 중요하다. 다음 기호 예측기가 존재하기 전에도 설명 길이 문제를 제기할 수 있기 때문이다. Kolmogorov 복잡도는 개별 문자열에 대해 그렇게 하며, 계수 하한은 유한한 객체 집합에 대해 그렇게 한다.
부호화기와 복호화기는 합의된 객체 집합, 직렬화, 전송되는 정보와 공유 정보의 경계, 그리고 복호화 계약을 필요로 한다. 이 선택들 중 어느 것도 다음 기호 예측만으로 결정되지 않는다.
그 선택이 이루어진 뒤에는 부호 길이 수준에서 동치가 정확하다. 순차 확률 모델은 로그 손실을 통해 이상적 페이로드 길이를 할당한다. 반대로 고정된 객체 집합 위의 모든 유일 복호 가능 부호는 분포를 유도한다. 객체를 직렬화한 뒤에는 그 분포를 다시 다음 기호 조건부 확률들로 분해할 수 있다.
그러나 이것이 바로 _압축은 예측이다_라는 구호의 한계이기도 하다. 표현을 확률적으로 재구성한다고 해서 왜 그 객체들이 선택되었는지, 모델을 전송해야 하는지, 어떤 연산을 지원하는지는 설명되지 않는다. 로그 손실이 더 낮은 모델도 매개변수를 포함하면 더 큰 완전 파일을 만들 수 있다. 경험적 엔트로피가 0이어도 복호화기에 수열을 재구성하는 데 필요한 모델이 없을 수 있다.
따라서 압축은 부호화 문제가 고정된 뒤에 그리고 유도된 부호 길이가 측정하는 수준에서만 예측이다. 공유된 순차 모델에 대해 누적 로그 손실은 부호화 오버헤드를 제외한 이상적 페이로드 길이를 제공한다. 그것은 무엇을 표현해야 하는지, 복호화기가 이미 무엇을 아는지, 또는 표현이 복호화기에게 무엇을 가능하게 해야 하는지를 정의하지 않는다.
