엔트로피의 재발견 | 압축은 지능이다 파트 1

비디오: 엔트로피의 재발견 | 압축은 지능이다 파트 1
채널: 3Blue1Brown
길이: 32분 19초
출처: 자막 (수동, 영문)
스크립트:
[criblate.com에서 자막 수정을 제출하세요]
텍스트를 이진수 (binary)로 인코딩할 때, 가능한 한 적은 데이터를 사용하는 것이 좋은 경우가 많습니다.
그래서 여러분은 자연스럽게 다음과 같은 의문을 가질 수 있습니다. 텍스트를 얼마나 효율적으로 압축할 수 있는지에 대한 어떤 근본적인 한계가 존재할까요?
ASCII를 사용하는 기본 인코딩은 상당히 비효율적입니다.
각 문자는 8개의 전체 비트 (bits)로 표현됩니다.
더 흔한 문자를 더 짧은 비트 문자열과 연관시키는 약간의 영리함을 적용하면, 이를 문자당 평균 약 4비트까지 낮출 수 있으며, 긴 텍스트 시퀀스 사이의 패턴을 활용하는 그보다 훨씬 더 똑똑한 방법들을 사용하면 훨씬 더 나은 결과를 얻을 수 있습니다.
하지만 다시 말해, 그 한계는 무엇일까요?
여러분 중 많은 분이 이에 대한 추정치를 들어보셨을 것이라 생각합니다.
영상 마지막에 하나를 공유하겠지만, 단일한 수치적 답변보다 훨씬 더 흥미로운 점은 이 질문에 어떻게 접근하느냐 하는 것입니다.
이 질문은 정보 이론 (information theory)을 시작한 Claude Shannon의 영향력 있는 연구와 함께 적어도 1940년대로 거슬러 올라갑니다.
매우 흥미로운 점은, 그가 이러한 질문에 답하기 위해 개발한 수학이 현대 머신러닝 (machine learning)에 놀라울 정도로 유용하게 쓰이고 있다는 사실입니다.
오늘날의 두드러진 사례를 들자면, 대규모 언어 모델 (large language models)이 학습될 때, 그 사전 학습 (pre-training) 단계는 보통 다음 토큰 예측 (next token prediction), 구체적으로는 교차 엔트로피 손실 (cross-entropy loss)이라고 불리는 것을 사용하는 과정으로 설명됩니다.
이 교차 엔트로피 (cross-entropy)라는 용어는 정보 이론에 뿌리를 두고 있습니다.
하지만 또한 흥미로운 점은, 정보 이론의 결론 중 하나가 예측 (prediction)과 압축 (compression)은 수학적으로 동일하다는 것입니다.
그것들은 동전의 양면과 같습니다.
이는 사전 학습 목표 (pre-training objective)를 단순히 다음 토큰을 예측하는 것 자체가 아니라, 대신 가능한 한 가장 효율적인 텍스트 압축기를 만드는 것으로 사고의 틀을 완전히 재구성할 수 있음을 의미합니다.

나중에 이것이 정확히 어떻게 작동하는지 설명하겠지만, 그렇게 하고 나면 이 교차 엔트로피 (cross-entropy)라는 개념이 실제로 무엇인지, 그리고 왜 그것을 사용하는지에 대해 더 명확한 통찰을 얻을 수 있을 것이라고 생각합니다.

또한, 여러분은 어떨지 모르겠지만 적어도 저에게는, 지능을 추구하는 과정에서 압축 (compression)을 근본적인 목표로 사용하는 것에는 매우 흥미로운 무언가가 있습니다. 실제로 어떤 이들은 압축이 곧 지능이라고 말하기까지 합니다.

물론 앞서 언급했듯이, 지능은 매우 모호하고 정의하기 어려운 용어이기 때문에 이를 엄격하게 판단하기는 어려운 주장입니다. 더 안전한 주장은 압축의 수학적 이론이 인공지능 (artificial intelligence)과 기묘할 정도로 관련이 있다는 것입니다. 그럼에도 불구하고, 이 간결한 문구는 생각할 거리를 던져줍니다. 그래서 이 영상은 이 주장이 실제로 무엇을 의미하는지 평가하기 위한 수학적 기초를 다지는 것을 목표로 하는 3부작 영상 중 첫 번째입니다.

앞으로 약 30분 동안, 당신과 저는 압축의 한계를 이해하는 데 집중할 것이며, 여러분이 샤논의 무손실 코딩 정리 (Shannon's noiseless coding theorem) 뒤에 숨겨진 핵심 아이디어를 스스로 재발견한 것처럼 느끼게 할 수 있을지 확인해 볼 것입니다. 이를 위해서는 몇 가지 핵심 정의, 즉 정보 (information)와 엔트로피 (entropy)의 정의를 재발견하는 과정이 포함됩니다.

정의를 '발견해야 할 것'으로 묘사하는 것이 조금 이상하게 들릴 수도 있겠지만, 훌륭한 정의는 종종 어떤 종류의 통찰이 남긴 잔여물인 경우가 많습니다. 사실, 이 두 가지 특정 용어는 여러분에게 공식을 제시한다는 의미에서 정의하기가 그리 어렵지는 않지만, 너무 일찍 정의를 내려버리면 좋은 이야기의 흐름을 망칠 수 있습니다. 언어 압축의 한계에 대해 질문함으로써 여러분이 어떻게 필연적으로 이 개념들에 이끌리게 되는지 지켜보는 것이 훨씬 더 재미있을 것입니다.

그리고 제가 여기서 여러분이 주목하기를 바라는 점은, 우리가 어떤 지능의 개념과 반드시 연관되지 않고서는 이 질문에 진정으로 답할 수 없다는 것, 혹은 적어도 샤논 (Shannon)조차도 답할 수 없었다는 사실입니다. 우리는 경이로울 정도로 복잡한 언어를 모델링하는 단계로 나아갈 것이지만, 우리의 재발견 과정을 위해 필요한 동일한 핵심 아이디어들을 포함하고 있는 더 단순한 예시로 워밍업을 하는 것이 도움이 될 것입니다.

우리가 멀리 떨어진 달로 보낸 로봇이 있다고 상상해 봅시다. 이 로봇의 임무는 표면을 돌아다니며 데이터를 수집하는 것입니다. 이곳 지구에서 우리는 로봇이 어떻게 움직여야 하는지에 대한 지침을 보내는데, 이 지침은 네 가지 매우 단순한 가능성으로 제한됩니다. 위, 아래, 왼쪽, 또는 오른쪽으로 이동하는 것이며, 각 이동은 고정된 보폭을 가집니다. 여기서 미묘한 차이는 이 지침들이 균등하게 분포(uniformly distributed)되어 있지 않다는 점입니다. 우리가 보내는 것의 절반은 위쪽이고, 4분의 1은 아래쪽, 8분의 1은 왼쪽, 나머지 8분의 1은 오른쪽입니다. 약간 인위적인 설정이며 단순한 예시를 의도한 것이지만, 이러한 단순함의 정신에 따라 우리는 모든 지침이 독립적(independent)이라고 가정할 것입니다. 지침들은 이전의 문맥(context)과 상관없이 이 분포로부터 샘플링(sampled)됩니다. 멀리 떨어진 이 로봇에게 데이터를 보낼 때, 우리는 이를 1과 0으로 이루어진 비트 스트림(stream of bits) 형태로 보내는데, 이 방식은 매우 느리고 비용이 많이 듭니다. 따라서 자연스러운 질문이자 오늘 여러분을 위한 워밍업 퍼즐은, 이 지침들을 비트 스트림으로 인코딩(encode)할 수 있는 가장 효율적인 방법이 무엇인지 묻는 것입니다. 여기서 우리는 각자 답을 시도하는 세 명의 학생을 상상해 볼 수 있습니다. 한 명은 직설적이고, 한 명은 영리하며, 한 명은 매우 이론적입니다. 직설적인 학생은 즉시 손을 들고 말합니다. "음, 이 네 가지 지침 각각에 대해 그냥 2비트(bits)를 사용하면 됩니다. 아마도 00은 위, 01은 아래, 10은 왼쪽, 11은 오른쪽을 인코딩하겠죠." 수신 측에서 이 방식은 로봇이 디코딩(decode)하기 매우 쉽게 만듭니다. 로봇은 단순히 비트 스트림을 2개씩 묶음으로 나누고, 각 묶음을 적절한 지침으로 변환하기만 하면 됩니다. 이때 영리한 학생이 지적합니다. "음, 그 방식은 위쪽이 왼쪽이나 오른쪽보다 훨씬 더 자주 나타난다는 사실을 전혀 활용하지 못하고 있어요." 그들은 각 지침에 대해 서로 다른 수의 비트를 사용하는 방법을 제안합니다.

잠시 후에 설명하겠지만, 서로 다른 지침에 서로 다른 비트 수를 할당하게 되는 순간, 로봇이 그것을 어떻게 디코딩(decode)해야 할지 알 수 있을지는 분명 자명한 문제가 아닙니다. 결국 로봇은 어디에서 경계선을 그어야 할지를 어떻게든 알아내야 하기 때문입니다. 매우 영리한 두 번째 학생은 이 점을 충분히 고려했지만, 제가 모든 것을 펼쳐서 보여드리는 것이 설명하기에 가장 쉬울 것 같습니다.

그들이 제안하는 방식은 단일 비트 0을 '위(up)'로 나타내고, 두 비트 10을 '아래(down)'로 나타내며, 110을 '왼쪽(left)', 111을 '오른쪽(right)'으로 사용하는 것입니다. 간단한 가중 합(weighted sum)을 통해 이 방식이 요구하는 지침당 평균 비트 수를 계산할 수 있습니다. 절반의 경우에는 단 1비트만 사용되고, 4분의 1의 경우에는 2비트가 필요하며, 나머지 경우에는 3비트가 필요합니다. 이 모든 것을 가중 합으로 더하면 지침당 1.75비트가 나오는데, 이는 지침당 일괄적으로 2비트를 사용하는 더 단순한(naive) 방식보다 확실히 더 낫습니다. 두 번째 학생은 마지막 두 지침에 더 많은 비트를 할당하고 있지만, 이 지침들은 훨씬 덜 빈번하게 발생하기 때문에, 가장 흔한 지침에 단 1비트만 사용함으로써 그 손실을 충분히 메우고도 남습니다.

그리고 이러한 효율성은 경험적으로도 증명될 수 있습니다. 여기 있는 것은 해당 분포에서 샘플링된 지침 세트입니다. 많은 '위'가 있고, '아래'는 그 절반 정도이며, '왼쪽'과 '오른쪽'은 그보다 더 적다는 것을 알 수 있을 것입니다. 이 인코딩(encoding)을 따라 각 심볼을 적절한 비트 문자열(bit string)로 변환하면, 결과로 나오는 비트 시퀀스는 실제로 단순한 방식이 내놓은 결과보다 더 짧습니다.

하지만 여러분 중 몇몇은 이렇게 묻고 계실 것 같군요. 로봇이 이것을 어떻게 디코딩하는지 어떻게 알 수 있나요? 경계선을 긋는 방식에 모호함이 없다고 확신할 수 있나요? 인코딩(encodings) 용어로 말하자면, 지침을 인코딩하는 데 사용되는 이 네 가지 비트 문자열 각각을 코드워드(code word)라고 부릅니다. 이제 단계를 밟아 나가면서, 영리한 학생이 자신의 코드워드들이 서로 충돌하지 않도록 하기 위해 어떤 규칙을 따랐는지 여러분이 직접 찾아낼 수 있는지 확인해 보시기 바랍니다.

그리고 실제로, 여러분은 그저 로봇의 관점에서 예시 비트 스트림 (bit stream)을 바라보고 차근차근 생각해보면 됩니다.

로봇이 받는 첫 번째 비트가 1이라고 가정해 봅시다. 지금까지는 이것이 마지막 세 가지 명령 중 하나인 아래(down), 왼쪽(left), 또는 오른쪽(right) 중 무엇을 인코딩(encoding)하고 있는지 알 수 없습니다.

만약 그 뒤에 0이 온다면, 그것은 오직 '아래'일 수밖에 없습니다. 다른 가능성은 없습니다. 따라서 로봇은 그것을 하나의 완전한 명령으로 등록할 수 있습니다.

그다음부터 다시 시작해서, 만약 뒤따르는 비트가 0이라면, 다른 가능성이 없으므로 그것은 반드시 '위(up)'를 인코딩하고 있는 것이어야 합니다. 0으로 시작하는 다른 것은 없기 때문입니다.

그 후, 만약 1을 본다면, 이는 아직 모호한 상태입니다. 마지막 세 가지 코드워드 (code word) 중 어떤 것의 접두사 (prefix)일 수 있기 때문입니다.

만약 다음 비트가 또 다른 1이라면, 여전히 모호하며 마지막 두 개의 접두사 상태로 남습니다. 하지만 그 뒤에 0이 따라온다면, 이 세 비트는 반드시 '왼쪽'을 인코딩하고 있었음이 명확해집니다.

요약하자면, 로봇이 해야 할 일은 완전한 코드워드를 형성하는 순간까지 다음 비트 시퀀스 (sequence)를 읽어 들이는 것이며, 그 시점에 로봇은 이를 하나의 완전한 명령으로 등록할 수 있습니다.

한 걸음 물러나 생각해 보면, 이 모든 것이 작동하기 위한 핵심 제약 조건은 어떤 코드워드도 다른 코드워드의 접두사가 될 수 없다는 것입니다.

예를 들어, 만약 여러분이 '100'이라는 코드워드를 가진 다섯 번째 명령을 도입하려고 한다고 가정해 봅시다. 이는 충돌을 일으킬 것입니다. 왜냐하면 '10'을 읽은 후, 이것이 '아래'를 의미하는 것인지, 아니면 이 새로운 다섯 번째 명령의 시작인지 명확하지 않기 때문입니다.

이러한 종류의 충돌을 피할 때, 이와 같은 인코딩 (encoding) 방식은 특별한 이름을 갖게 됩니다. 업계에서는 이를 접두사-free 코드 (prefix-free code)라고 부르며, 혼란스럽게도 동의어처럼 쓰이긴 하지만 실제로는 접두사 코드 (prefix code)라는 이름으로 더 흔히 알려져 있습니다.

그리고 가능한 모든 이진 문자열 (binary string)을 나타내는 특정 도표를 사용하면, 접두사-free 코드를 선택하는 과정을 시각화하는 아주 멋진 방법이 있습니다. 이 도표는 제가 잠시 후 엔트로피 (entropy)를 보여드리고자 하는 방식과도 매우 유용한 유사점을 가지고 있습니다.

잠시 멈춰서 가만히 들여다본다면 무슨 일이 일어나고 있는지 꽤 직관적으로 이해할 수 있겠지만, 중요한 특징들을 짚어드리겠습니다. 각 층은 주어진 길이의 모든 비트 문자열 (bit string)을 보여주며, 0으로 시작하는 모든 것은 이 도표의 왼쪽 절반에 위치하고, 1로 시작하는 모든 것은 도표의 오른쪽 절반에 위치한다는 것을 알 수 있습니다. 그리고 이러한 동일한 아이디어가 위로 올라갈수록 재귀적 (recursively)으로 계속됩니다. 따라서 00으로 시작하는 모든 것은 도표의 이 4분의 1 영역 위에 있고, 01로 시작하는 모든 것은 도표의 이 4분의 1 영역 위에 있는 식입니다. 특히 핵심적인 속성은 이 도표의 모든 이진 문자열 (binary string)이 그 위에 위치한 모든 것의 접두사 (prefix)라는 점입니다. 따라서 우리의 영리한 학생이 '위로 (up)'라는 명령어를 나타내기 위해 단일 비트 0을 할당하기로 선택했을 때, 그들은 사실상 가능한 모든 코드 단어 (code words) 공간의 절반을 소비한 셈입니다. 왜냐냐하면 이 접두사-자유 (prefix-free) 속성에 따라 0으로 시작하는 모든 것이 이제 금지되었기 때문입니다. 마찬가지로, '아래로 (down)'에 0 하나를 할당하는 것은 이 공간의 또 다른 4분의 1을 차지하며, 나머지 두 명령어는 각각 공간의 8분의 1씩을 차지합니다. 남는 것이 아무것도 없다는 것을 바로 확인할 수 있습니다. 그리고 이 시점에서, 이 비율들이 각 명령어가 나타날 확률과 정확히 일치한다는 점을 고려하면, 여러분의 머릿속에서 어떤 종이 울리는 듯한 느낌이 들 것이라고 추측합니다. 사실, 데이터 크기와 확률 사이의 이러한 관계를 느끼는 그 짜릿한 감각이 바로 정보 이론 (information theory)의 기초가 되는 통찰입니다. 이 즐거운 정렬을 보고 있으면, 영리한 학생의 해결책이 단순히 더 나은 수준이 아니라, 어쩌면 어떤 면에서는 완벽할지도 모른다는 생각이 들 수도 있습니다. 하지만 현재로서는 그것이 다소 대담한 주장처럼 느껴집니다. 명령어의 매우 긴 시퀀스 (sequences)를 사용하여 무언가 화려한 처리를 함으로써, 명령어당 평균 비트 수를 이보다 훨씬 더 낮게 만들 수 있는 초정밀의 영리한 방법이 존재하지 않는다고 어떻게 확신할 수 있을까요?

이것은 세 번째 학생인 '구름 위의 머리 (Head in the Clouds)'로 우리를 인도합니다.
이 학생은 실제로 구현할 수 있는 구체적인 코드에 대해서는 별로 생각하지 않았습니다.
대신 완벽하고 최적으로 효율적인 코드가 어떤 속성을 가져야 하는지를 고민해 왔습니다.
이 학생은 매우 영리한 아이디어를 가지고 있는데, 바로 무작위 노이즈 (random noise)는 압축할 수 없어야 하며, 따라서 완벽한 압축 알고리즘 (compression algorithm)은 무작위 노이즈와 구별할 수 없는 비트스트림 (bitstream)을 생성해야 한다고 주장하는 것입니다.
흥미로운 점은, 이것이 다소 단순하게 들릴지라도 실제로 Shannon 엔트로피 (Shannon entropy)라는 개념을 재발명하게 만들 수 있다는 것입니다.
여기서 제가 무작위 노이즈라고 말할 때의 의미는, 각 비트가 50%의 확률로 1 또는 0이며, 모든 비트가 서로 독립적으로 작동한다는 뜻입니다.
우리의 두 번째 학생이 로봇을 위해 만든 인코딩 (encoding)이 진정으로 이 규칙을 따르고 있다는 것을 보여주는 것은 어렵지 않습니다.
생각해 보면, 메시지가 '위로 (up)'라는 명령어로 시작할 확률이 50%이므로, 그 첫 번째 비트가 0일 확률은 50%이며, 그 외