gzip이 언어 모델(Language Model)이 될 수 있을까?

얼마 전 저는 신경망(Neural Network) 없이 언어 모델링(Language Modeling)을 하는 것에 대해 글을 쓴 적이 있습니다. 당시 저는 가중치(Weights)도, 학습(Training)도 없이 오직 개수만 세는 무제한 n-gram 모델을 사용하여 셰익스피어(Shakespeare)를 생성했습니다. 운 좋게도 저는 **압축-예측 등가성 (compression–prediction equivalence)**을 언급한 'Language Modeling is Compression'이라는 논문을 접하게 되었습니다.

모든 예측 모델(Prediction Model)은 본질적으로 압축기(Compressor)이며, 모든 압축 알고리즘(Compression Algorithm)은 예측 모델이다.

이것은 자연스러운 질문으로 이어졌습니다: gzip이 언어 모델링을 할 수 있을까?

1신경망도 없고, 학습된 파라미터(Learned Parameters)도 없고, 아무것도 없습니다. 그저 여러분의 운영체제(Operating System)에 포함되어 있는 압축기일 뿐입니다. 코퍼스(Corpus)로 모델을 준비시키고(Prime), 일반적인 텍스트 프롬프트(Prompt)를 주면, 이 모델은 가장 잘 압축되는 바이트 시퀀스(Byte Sequences)를 탐색함으로써 프롬프트를 이어 나갑니다. 아주 작은 셰익스피어 데이터로 준비시킨 후 얻은 편집되지 않은 실제 출력 결과는 다음과 같습니다:

gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200

MENENIUS:
'Though all at once canq
MARCIUS:
...

결과를 보니, 어느 정도는 가능해 보입니다. 완전히 일관성 있는 텍스트는 아니지만, 텍스트에 대해 분명히 무언가를 알고 있습니다. 제가 gzip이 알고 있을 것이라고 예상했던 것보다 훨씬 더 많이 말이죠.2 그렇다면 압축기가 어떻게 이것을 생성할 수 있는 걸까요?

압축은 예측이다 (Compression is prediction)

압축기가 무엇을 하는지 생각해 보십시오. 압축기는

DEFLATE를 사용하며, 이는 32 KiB 슬라이딩 윈도우 (sliding window) 내의 최근 텍스트와 일치하는 항목을 찾아 다음 바이트들을 압축합니다. 만약 이어지는 내용이 윈도우에 이미 있는 내용을 반영한다면, DEFLATE는 이를 리터럴 바이트 (literal bytes) 대신 저렴한 백 레퍼런스 (back-reference)로 인코딩합니다. 즉:

gzip이 "예측한" 이어지는 내용은, 윈도우에 이미 있는 텍스트를 반영하기 때문에 거의 압축되지 않는 수준으로 줄어듭니다.

이를 통해 우리는 점수 (score)를 얻을 수 있습니다. 만약 어떤 컨텍스트 (context)가 있고 후보 이어지는 내용이 얼마나 좋은지 알고 싶다면, 저는 단순히 다음을 측정합니다:

$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$
압축된 길이가 작을수록, 해당 후보는 더 많이 "예측된" 것입니다. 모델을 준비시키기 위해, 저는 gzip의 윈도우에 코퍼스 (corpus)를 포함시킵니다. 코퍼스와 유사해 보이는 모든 이어지는 내용은 작게 압축되고, 그렇지 않은 모든 이어지는 내용은 크게 압축됩니다.

빔 서치 (beam search)를 통한 생성#

점수를 매기는 것과 생성하는 것은 별개의 문제입니다. 가장 압축이 잘 되는 단일 다음 바이트를 선택하는 단순한 접근 방식은 심각하게 실패하며, 그 이유는 미묘합니다. gzip은 오직 정수 형태의 바이트 길이만을 제공하기 때문입니다 (소수점 불가). 바이트 하나를 추가해도 압축 길이가 전혀 변하지 않는 경우가 많으므로, 많은 후보가 동점 처리가 되어 신호가 양자화 노이즈 (quantization noise) 속에 묻혀버립니다.

해결책은 확정하기 전에 전체 구간을 미리 "내다보는" 것입니다. gzipt는 바이트 시퀀스에 대해 빔 서치 (beam search)를 실행합니다. 각 단계에서 현재 컨텍스트는 다음과 같습니다:

코퍼스 윈도우 + (프롬프트 + 생성된 바이트)의 최근 끝부분

그 다음 gzipt는 가능한 다음 바이트들을 시도합니다. 각 후보 이어지는 내용은 context + candidate를 압축하여 압축 결과가 몇 바이트를 차지하는지 확인함으로써 점수가 매겨집니다.

루프는 다음과 같습니다:

프롬프트 (Prompt). 사용자의 프롬프트를 이어갈 초기 텍스트로 시작합니다. 시작 토큰 (start token)은 없으며, 프롬프트 바이트는 gzip이 보는 컨텍스트의 일부일 뿐입니다.
컨텍스트 (Context). gzip에게 코퍼스 윈도우와 프롬프트/생성된 텍스트의 최근 끝부분을 보여줍니다.
탐색 (Search). beam_width를 유지하며

가장 압축률이 높은 부분적 연속(partial continuations)들을 찾습니다. 코퍼스(corpus)에 등장하는 모든 바이트를 사용하여 각 연속을 확장하고, 압축 길이(compressed length)로 모든 후보의 점수를 매긴 뒤, 가장 우수한 beam_width만큼만 남기고 가지치기(prune)합니다. 이 과정을 horizon 바이트만큼 반복합니다. 확정 (Commit). 가장 압축률이 높은 전체 구간을 선택하여(만약 temperature가 양수라면 최종 후보들 중에서 샘플링) 뒤에 붙이고, 루프를 다시 시작합니다.

중요한 세부 사항 중 하나는 생성된 출력의 마지막 꼬리 바이트(tail bytes)들만 점수 산정 컨텍스트(scoring context)에 유지된다는 점입니다. DEFLATE는 멀리 떨어진 매치보다 가까운 매치를 더 저렴하게 코딩하므로, 만약 gzip이 전체 이력을 볼 수 있다면 가장 저렴한 방법은 방금 내뱉은 텍스트를 반복적으로 복사하는 verbatim 루프(verbatim loops)에 빠지는 것이 될 것입니다.

위의 애니메이션에서 디코딩(decoding) 및 점수 산정 과정을 볼 수 있으며, 이는 상단에 표시된 것과 동일한 재생 영상입니다. 이 전체 과정은 순수 표준 라이브러리 Python(zlib만 사용)으로 작성된 하나의 파일입니다. 직접 실행해보고 싶다면 GitHub에서 코드를 확인할 수 있습니다.

논문에서는 이를 시도했으나 결과적으로 성능이 좋지 않았습니다. 빔 서치 (beam search)를 추가하는 것이 생성 품질을 크게 향상시켰으며 (저자들이 언급한 아이디어), 이에 대해서는 아래에서 논의합니다. ↩︎

코드는 실제로 gzip 프로세스를 생성하는 대신 zlib을 사용하지만, GziPT라는 이름이 너무 좋았습니다. 내부적으로는 둘 다 동일한 DEFLATE 알고리즘을 사용하는 것으로 알고 있습니다. ↩︎