📚 지식 노트

정보량: 놀라움을 비트로 재기

1948년 클로드 섀넌은 "정보"를 뜻과 상관없이 재는 방법을 내놓았다. 핵심 발상은 정보 = 놀라움이다. 해가 동쪽에서 떴다는 소식은 거의 아무것도 알려 주지 않고, 드문 일이 일어났다는 소식은 많은 것을 알려 준다. 그래서 확률 p인 사건이 일어났을 때 얻는 정보량을 −log₂p로 정의한다. 단위는 비트다.

로그를 쓰는 이유는 독립인 두 사건의 정보량이 더해지기를 바라서다. 확률은 곱해지고(p × q), 로그는 곱을 합으로 바꾼다. 공정한 동전의 앞면은 −log₂(1/2) = 1비트, 즉 예/아니오 질문 하나의 답이다. 동전 10번이 모두 앞면이면 확률이 1/1024라 10비트이고, 이는 동전 한 번의 정보 1비트를 열 번 모은 것과 같다. 확실한 사건(p = 1)은 0비트다.

로그의 밑이 단위를 정한다. 밑이 2면 비트(섀넌), 자연로그 ln이면 내트(nat), 밑이 10이면 하틀리다. 1내트 = 1/ln 2 ≈ 1.443비트로, 식은 같고 상수배만 다르다. 자연로그로 계산한 머신러닝 손실은 내트 단위이므로, 이 노트의 비트 값과 견줄 때는 ln 2로 나눠 맞춘다.

엔트로피: 평균 놀라움

사건 하나가 아니라 정보원 전체를 보면, 다음에 나올 기호가 평균적으로 얼마나 놀라운지를 물을 수 있다. 이것이 엔트로피 H = Σ −pᵢ log₂pᵢ다. 각 결과의 정보량을 그 확률로 가중 평균한 값이고, "결과를 알기 전의 불확실성"이라고 읽어도 된다.

• 공정한 동전: 1비트. 두 결과가 똑같이 그럴듯해 불확실성이 가장 크다.
• 공정한 주사위: log₂6 ≈ 2.58비트. 결과가 n개로 고르면 엔트로피는 log₂n이고, 이것이 n개 결과에서 낼 수 있는 최댓값이다.
• 앞면이 90%인 동전: 약 0.47비트. 대부분 앞면이라 결과를 들어도 덜 놀랍다. 다음 절에서 보듯 이런 동전 던지기 결과는 압축하면 던질 때마다 1비트보다 훨씬 적게 적을 수 있다.

결합·조건부 엔트로피와 상호 정보량

변수가 둘이면 관계를 잴 수 있다. X를 "오늘 비가 오는가", Y를 "우산을 들고 나왔는가"라고 하자. 결합 엔트로피 H(X,Y)는 둘을 한꺼번에 알 때의 불확실성이다. 조건부 엔트로피 H(X|Y)는 Y를 이미 알 때 X에 남는 불확실성이다. 우산을 든 사람을 보면 비가 왔을 가능성이 높으니, H(X|Y)는 H(X)보다 작다.

그 차이 I(X;Y) = H(X) − H(X|Y)가 상호 정보량이다. Y를 보고 X에 대해 알게 된 양이다. 식을 바꾸면 H(Y) − H(Y|X)와도 같아 대칭이고, 둘이 독립이면 0이다. 상관 계수와 달리 직선 관계가 아니어도 잡아내서, 특징 선택이나 의사 결정 나무의 정보 이득 같은 데 쓴다. 아래 벤 그림의 넓이 관계(H(X,Y) = H(X) + H(Y|X) 등)가 그대로 성립한다.

소스 부호화 정리: 평균 부호 길이 ≥ H

엔트로피가 중요한 이유는 섀넌이 이것이 압축의 한계임을 증명했기 때문이다. 기호마다 0과 1로 된 부호를 붙여 이어 쓰되 다시 풀 수 있어야 한다면, 기호당 평균 부호 길이는 엔트로피 H보다 짧을 수 없다(소스 부호화 정리). 반대로 기호를 충분히 길게 묶어 부호화하면 평균 길이를 H에 원하는 만큼 가깝게 만들 수 있다. 엔트로피는 "이 정보원을 적는 데 정말로 필요한 비트 수"다.

직관은 이렇다. 자주 나오는 기호에는 짧은 부호를, 드문 기호에는 긴 부호를 주면 평균이 준다. 확률 p인 기호에 길이 −log₂p를 주는 것이 이상적인데, 부호 길이는 정수여야 하니 정확히 맞추지 못하는 만큼 손해를 본다. 아래는 ABRACADABRA(11글자, 5종류)의 예다.

허프만 부호

데이비드 허프만은 1952년 논문에서 주어진 빈도에 대해 기호마다 부호를 따로 붙이는 방식 가운데 평균 길이가 가장 짧은 부호를 만드는 방법을 보였다. 방법은 단순하다. 기호마다 빈도를 무게로 가진 마디를 만들고, 가장 가벼운 두 마디를 합쳐 무게를 더한 새 마디로 바꾸기를 마디가 하나 남을 때까지 되풀이한다. 다 만든 나무에서 뿌리부터 왼쪽은 0, 오른쪽은 1로 읽으면 부호다.

글자가 나무의 잎에만 있으므로 어떤 부호도 다른 부호의 앞부분이 되지 않는다(접두 부호). 그래서 0과 1을 구분 기호 없이 이어 붙여도 앞에서부터 하나씩 떼어 읽을 수 있다. 허프만 부호는 DEFLATE(ZIP·gzip·PNG)와 JPEG 같은 형식의 마지막 단계에 쓰인다. 한계도 있다. 기호마다 적어도 1비트를 써야 해서, 한 기호가 압도적으로 흔하면(앞면 90% 동전처럼) 엔트로피에서 멀어진다. 이 틈을 메우는 것이 다음 절의 산술 부호다.

산술 부호와 사전 기반 압축(LZ77)

산술 부호는 기호마다 부호를 붙이지 않고 메시지 전체를 0과 1 사이의 수 하나로 적는다. [0, 1) 구간을 기호 확률만큼 나누고, 메시지의 첫 기호에 해당하는 조각을 고르고, 그 조각을 다시 같은 비율로 나누기를 되풀이한다. 마지막 구간의 폭은 각 기호 확률의 곱이므로, 그 구간 안의 수 하나를 가리키는 데 필요한 비트 수가 메시지의 정보량에 가깝다. 기호당 정수 비트라는 허프만의 제약이 없어, 확률이 치우친 정보원에서도 엔트로피에 거의 붙는다.

지금까지는 기호의 확률을 안다고 가정했다. 실제 파일은 확률을 미리 모르고, 같은 낱말이나 패턴이 되풀이되는 구조가 있다. 야코브 지브와 아브라함 렘펠의 LZ77은 이미 지나간 글을 사전으로 삼는다. 앞으로 읽을 글이 최근 창(window) 안 어딘가와 같으면, 글자 대신 "몇 칸 앞에서 몇 글자 복사"라는 짝을 적는다. 확률 표가 없어도 되풀이가 많으면 저절로 줄어든다. DEFLATE는 LZ77로 되풀이를 걷어 낸 뒤 남은 토큰을 허프만 부호로 한 번 더 줄이며, 창 크기는 32K 바이트다.

압축의 한계: 무작위 데이터는 줄지 않는다

"어떤 파일이든 조금씩이라도 줄이는 압축기"는 있을 수 없다. 세어 보면 바로 나온다. 길이 n 비트인 파일은 2ⁿ개인데, 그보다 짧은 파일(빈 파일 포함)은 1 + 2 + … + 2ⁿ⁻¹ = 2ⁿ − 1개뿐이다. 무손실 압축은 서로 다른 입력을 서로 다른 출력으로 보내야 하니, 비둘기집 원리에 따라 적어도 하나는 줄지 않는다. 1바이트(8비트)만 해도 256개를 255개 자리에 넣어야 한다.

압축은 데이터에 치우침이나 되풀이(낮은 엔트로피)가 있을 때만 이긴다. 이미 압축한 파일, 암호문, 좋은 난수는 엔트로피가 거의 최대라 다시 압축해도 줄지 않고 머리글만큼 오히려 늘어난다. 그래서 압축은 암호화보다 먼저 해야 한다. 거꾸로 암호문이 잘 압축된다면 암호가 약하다는 신호다. 좋은 암호가 출력을 무작위처럼 보이게 하는 원리는 암호학 노트에 있다.

헷갈리기 쉬운 세 낱말을 갈라 두자. 압축은 군더더기를 걷어 길이를 줄이고, 부호화(인코딩)는 같은 정보를 다른 기호로 바꿔 적을 뿐이며, 암호화는 열쇠 없이는 읽지 못하게 한다. Base64는 부호화다. 3바이트(24비트)를 6비트씩 네 글자로 적으므로 길이가 4/3배로 오히려 늘고, 표준 문서 RFC 4648도 기밀성을 전혀 주지 않는다고 밝힌다. 바이너리를 글자만 다니는 통로(이메일, JSON, URL)에 실으려는 것이지, 비밀번호를 Base64로 바꿔 두는 것은 숨긴 것이 아니다.

통신 채널과 잡음

섀넌의 논문 후반부는 보내는 쪽과 받는 쪽 사이의 채널을 다룬다. 전선, 전파, 광섬유, 디스크 표면 모두 채널이고, 모두 잡음이 있다. 열잡음, 간섭, 긁힘 때문에 보낸 것과 받은 것이 다를 수 있다. 가장 단순한 모형인 이진 대칭 채널은 비트마다 독립적으로 확률 p로 뒤집는다.

섀넌은 통신을 두 단계로 나눴다. 먼저 정보원의 군더더기를 걷어 내고(소스 부호화, 앞 절의 압축), 그다음 채널 잡음에 맞서도록 계획된 군더더기를 다시 붙인다(채널 부호화, 뒤 절의 오류 정정). 무턱대고 반복하는 것은 비싸다. 비트를 세 번 보내 다수결을 하면 p = 0.1에서 오류율이 0.028로 줄지만 전송량이 세 배가 된다. 섀넌의 놀라운 결과는, 이 채널이 전송 한 번에 실어 나를 수 있는 정보가 1 − H(p) = 0.53비트이고, 이보다 낮은 속도라면 오류율을 0에 가깝게 만드는 부호가 존재한다는 것이다.

섀넌 채널 용량: C = B log₂(1 + SNR)

전파나 전선처럼 연속 신호를 쓰는 채널이라면 용량은 두 가지로 정해진다. 쓸 수 있는 주파수 폭인 대역폭 B(Hz)와, 신호 세기를 잡음 세기로 나눈 신호 대 잡음비(SNR)다. 백색 가우스 잡음이 낀 채널의 용량은 C = B log₂(1 + SNR) 비트/초다(섀넌–하틀리 정리). 여기서 SNR은 dB가 아닌 선형 비다. 30 dB는 1000배이므로, 대역폭 3 kHz 전화선이라면 상한은 약 29,902 비트/초다.

식에서 두 가지를 읽을 수 있다. 대역폭은 용량에 정비례하지만 SNR은 로그 안에 있다. 신호를 두 배로 세게 해도 용량은 조금만 늘고, 대역폭을 두 배로 넓히면 두 배가 된다. 그래서 무선 통신은 더 넓은 주파수 대역(5G의 밀리미터파, 와이파이의 넓은 채널)과 여러 안테나로 공간을 나눠 쓰는 MIMO에 매달린다. 대역폭 20 MHz라면 SNR 0 dB에서 20 Mbit/s, 20 dB에서 133 Mbit/s, 30 dB에서 199 Mbit/s가 상한이다. 변조와 다중 안테나 이야기는 무선 통신 노트, 대역폭과 샘플링은 신호 처리 노트에 있다.

오류 검출: 패리티, 체크섬, CRC

고칠 수는 없어도 "틀렸다"는 것만 알면 다시 보내 달라고 할 수 있다. 가장 싼 방법이 패리티 비트다. 1의 개수가 짝수가 되도록 비트 하나를 덧붙이면 비트 하나가 뒤집힌 오류를 잡는다. 두 개가 뒤집히면 다시 짝수가 되어 놓친다.

인터넷 체크섬은 IP·TCP·UDP 머리글에 쓰인다. 데이터를 16비트 낱말로 잘라 1의 보수 덧셈(넘친 자리는 맨 아래로 다시 더함)으로 모두 더하고, 그 합을 뒤집어 적는다. 받는 쪽이 체크섬까지 함께 더하면 모든 비트가 1이 나와야 한다. 계산이 아주 싸지만 낱말 순서가 바뀐 오류는 못 잡는다.

CRC(순환 중복 검사)는 비트열을 GF(2) 위의 다항식으로 보고, 정해 둔 생성 다항식으로 나눈 나머지를 덧붙인다. GF(2)에서 덧셈과 뺄셈은 모두 XOR이라 나눗셈은 "맨 앞 1에 생성 다항식을 맞대고 XOR"의 반복이다. 받는 쪽이 같은 다항식으로 나눠 나머지가 0이 아니면 오류다. 하드웨어로 아주 빠르게 계산되고, 생성 다항식 길이보다 짧은 연속 오류(버스트)는 모두 잡는다. 이더넷 프레임과 ZIP 파일이 CRC-32를 쓴다.

이 셋은 모두 우연한 오류를 잡는 장치다. 데이터를 일부러 고치는 사람은 체크섬이나 CRC도 다시 계산해 붙이면 그만이라 고의 변조는 막지 못한다. 변조를 막아야 하면 열쇠가 있어야 계산되는 메시지 인증 코드(MAC)나 전자 서명을 쓴다(Wikipedia의 CRC 데이터 무결성 절, 암호학 노트).

오류 정정: 해밍 거리와 해밍(7,4)

고치려면 오류가 어디서 났는지 알아야 한다. 두 비트열의 해밍 거리는 서로 다른 자리의 수다. 쓸 수 있는 부호어끼리의 최소 거리가 d면, d − 1개까지의 오류는 다른 부호어로 착각할 수 없으니 검출할 수 있고, ⌊(d − 1)/2⌋개까지는 가장 가까운 부호어로 되돌려 고칠 수 있다. 오류 정정 부호를 설계한다는 것은 부호어들을 서로 멀리 떨어뜨려 놓는 일이다.

리처드 해밍은 1950년에 해밍 부호를 내놓았다. 해밍(7,4)는 데이터 4비트에 패리티 3비트를 붙여 7비트로 보낸다. 부호어끼리 최소 거리가 3이라 한 비트 오류를 고친다. 비결은 배치다. 자리 번호를 이진수로 쓰고, 패리티를 1·2·4번 자리에 두어 p1은 번호에 1이 있는 자리, p2는 2가 있는 자리, p4는 4가 있는 자리를 검사하게 한다. 그러면 실패한 검사들을 이진수로 읽은 값(증후군)이 곧 틀린 자리 번호다.

해밍 부호는 지금도 서버용 ECC 메모리에 쓰인다(한 비트를 더 붙여 두 비트 오류를 검출까지 하는 SECDED 꼴). 다만 해밍(7,4)는 7비트에 4비트만 실어 효율이 57%이고 두 비트 오류에는 엉뚱한 자리를 "고친다". 더 센 잡음, 한꺼번에 몰려오는 오류에는 아래의 부호들이 쓰인다. 메모리 쪽 이야기는 RAM 노트에 있다.

리드–솔로몬: QR 코드와 CD

1960년 MIT 링컨 연구소의 어빙 리드와 구스타브 솔로몬이 만든 리드–솔로몬(RS) 부호는 비트가 아니라 기호(보통 8비트 바이트) 단위로 일한다. 데이터 기호 k개를 다항식의 계수로 보고, 그 다항식을 n개 점에서 계산한 값을 보낸다는 발상이다. 점이 몇 개 망가져도 남은 점으로 다항식을 되살릴 수 있다. 패리티 기호를 2t개 붙이면 위치를 모르는 기호 오류 t개까지 고친다.

기호 단위라는 점이 긁힘과 얼룩에 강하다. 연속된 비트 수십 개가 망가져도 바이트 몇 개의 오류로만 셈된다. CD는 RS 부호 두 겹 사이에 데이터를 뒤섞는 인터리빙을 넣은 CIRC를 써서, 대량 생산된 소비자 제품에 강한 오류 정정을 처음 넣은 예로 꼽힌다. QR 코드도 RS 부호를 덧붙여 일부가 가려지거나 더러워져도 읽힌다. 오류 정정 등급을 고를 수 있는데, 가장 많이 쓰는 M 등급은 약 15%, Q 등급은 약 25%의 코드어를 복원한다. DVD도 더 큰 블록으로 같은 구성을 쓴다.

LDPC와 폴라 부호: 5G

섀넌은 용량에 다가가는 부호가 "있다"고 증명했을 뿐 만드는 법은 알려 주지 않았다. 반세기 가까이 실용 부호는 용량에서 꽤 떨어져 있었다. 이 간극을 거의 메운 것이 LDPC(저밀도 패리티 검사) 부호다. 해밍 부호처럼 "이 비트들의 합은 짝수"라는 검사를 쓰되, 검사 수천 개가 저마다 몇 개의 비트만 보게 한다(검사 행렬이 거의 0이라 저밀도). 복호기는 검사 마디와 비트 마디가 "내가 보기에 너는 0일 확률이 이만큼"이라는 믿음을 선을 따라 주고받기를 되풀이한다(믿음 전파). 이 과정이 용량에 아주 가까이서도 잘 수렴한다.

폴라 부호는 에르달 아르칸이 내놓은 부호로, 채널을 여러 번 합치고 나누면 일부는 거의 완벽한 채널이, 나머지는 거의 쓸모없는 채널이 된다는 "채널 양극화"를 이용한다. 좋은 채널에만 데이터를 싣고 나쁜 채널에는 미리 정한 값을 넣는다. 부호 길이를 늘리면 용량에 닿는다는 것이 증명되어 있다. 3GPP는 2016년 11월 5G NR에서 eMBB의 제어 채널에 폴라 부호를, 데이터 채널에 LDPC를 쓰기로 정했다. 짧은 제어 메시지와 긴 데이터에 각자 강한 부호를 고른 셈이다.

정보 이론과 AI: 교차 엔트로피와 KL

분류 모델을 훈련할 때 가장 흔한 손실 함수가 교차 엔트로피 H(p, q) = Σ −p log q다. 정답 분포 p를 모델이 낸 분포 q로 부호화할 때의 평균 부호 길이로 읽을 수 있다. 정답이 한 칸(원-핫)이면 정답 칸에 모델이 준 확률의 −log만 남는다. 정답에 확신할수록 손실이 0에 가깝고, 틀린 쪽에 확신하면 손실이 크게 뛴다. 교차 엔트로피에서 p 자체의 엔트로피를 뺀 것이 KL 발산 D(p‖q)로, "q로 부호화해서 더 쓴 비트"다. 0 이상이고 p = q일 때만 0이지만, 순서를 바꾸면 값이 달라져 거리는 아니다.

언어 모델의 손실도 다음 토큰에 대한 교차 엔트로피이고, 흔히 보는 퍼플렉서티는 그 값을 지수로 되돌린 것이다. 따라서 언어 모델을 잘 훈련하는 일은 글을 잘 압축하는 일과 같은 문제다. 소프트맥스와의 결합, 기울기 모양, 수치 안정성은 AI를 위한 수학 노트에서 다룬다.

핵심 자료

신호와 샘플링은 신호 처리 노트, 실제 무선 링크는 무선 통신 노트, 암호와 난수는 암호학 노트에 있다.