혼동하기 쉬운 점과 요약

토론 1. 오류를 줄이려면 레이트를 0으로 낮출 수밖에 없나

뒤집힘 확률 0.1인 선으로 사진 파일을 보낸다. 오류율을 100만 분의 1보다 낮추려면 레이트를 얼마까지 낮춰야 하는가?

뒤집힘 확률 0.1인 선으로 사진 파일을 보내요. 비트 오류율을 100만 분의 1 아래로 낮추고 싶어요. 레이트를 얼마까지 낮춰야 할까요?

반복 코드로 계산해 볼게요. 다섯 번이면 0.0086, 열한 번이면 0.0003, 열다섯 번이면 0.00003이에요. 스물한 번도 1.4 × 10^(−6)이라 모자라고, 스물세 번에서 4.7 × 10^(−7)로 처음 100만 분의 1 아래가 돼요. 레이트가 1/23 = 0.043이니 원래보다 스무 배 넘게 느려요.

오류율을 10억 분의 1로 낮추면요?

반복을 더 늘려야 하니까 레이트는 더 낮아지죠. 오류율을 0으로 보내려면 레이트도 0으로 가는 것 같아요. 덜 틀리는 대가가 느려지는 거니까요.

무작위 코드 실험은 레이트 1/4로 고정했는데도 블록이 길어질수록 오류율이 내려갔잖아. 반복 코드는 블록 길이와 레이트가 묶여 있어서 그런 거 아냐?

아, 반복 코드는 n을 늘리는 게 곧 레이트를 1/n로 낮추는 거라서 그렇게 보였구나. 레이트를 고정하고 블록만 길게 할 수 있는 코드에서는 둘이 따로 움직이고.

그래요. 채널 코딩 정리는 용량 0.531보다 작은 레이트라면, 예를 들어 0.5에서도 블록을 길게 해 오류율을 원하는 만큼 낮추는 코드가 있다고 말해요. 반복 코드가 보여 준 맞바꿈은 반복 코드 자신의 한계예요.

그럼 레이트 0.043까지 내릴 필요가 없고, 0.5 근처에서 긴 코드를 쓰면 되는 거네요. 와이파이가 느려지지 않으면서 오류를 고치는 것도 그래서고요.

토론 2. 용량보다 조금 빠르면 오류도 조금만 늘까

용량이 0.531인 채널에 레이트 0.55로 보낸다. 용량을 3.5%만 넘었으니 오류율도 조금만 늘까?

용량 0.531인 채널에 레이트 0.55로 보내기로 했어요. 용량을 3.5%만 넘었는데, 블록을 아주 길게 하면 오류율은 어떻게 될까요?

조금 넘었으니까 오류율도 조금이겠죠. 용량 아래에서 0에 가까웠으니 0.55면 0.01쯤?

파노 부등식에서 나온 경계 1 − C/R에 넣어 볼까요?

1 − 0.531/0.55 = 0.035예요. 어, 적어도 3.5%는 틀려요. 그리고 이건 하한이니까 실제로는 더 클 수 있고요.

하한이 0.035면 「조금」이긴 한데, 용량 아래에서는 0으로 보낼 수 있던 것과는 다르네. 레이트를 0.53에서 0.55로 올리는 순간 0으로 가던 게 0으로 안 가게 되는 거야.

그리고 블록을 길게 할수록 어떻게 되는지는 무작위 코드 실험에서 봤죠.

레이트 3/4는 블록이 길수록 오류율이 올라갔어요. 용량을 넘으면 긴 블록이 도와주기는커녕 블록 전체가 틀릴 확률이 1로 가요. 조금 넘으면 조금 나빠진다고 한 게 틀렸네요.

용량은 보내는 속도의 문턱이에요. 아래에서는 블록이 길수록 좋아지고, 위에서는 길수록 나빠져요. 그래서 실제 통신은 선의 노이즈를 재서 용량보다 조금 낮은 레이트를 골라요.

토론 3. 압축으로 덜어 낸 중복을 다시 붙이면 헛일인가

체크포인트를 압축해 크기를 절반으로 줄인 뒤, 보내기 전에 오류 정정 코드로 덧붙인다. 압축으로 덜어 낸 중복을 다시 붙이는 셈이니 처음부터 압축하지 않는 편이 나은가?

체크포인트를 압축해 크기를 절반으로 줄이고, 보내기 전에 오류 정정 코드로 덧붙인다고 해 봐요. 압축은 중복을 덜어 내고 오류 정정은 중복을 붙이는데, 헛일일까요?

음, 헛일 같아요. 원래 파일에도 중복이 많았으니까, 그 중복으로 오류를 고치면 되잖아요. 영어 글은 철자 하나가 틀려도 사람이 알아보니까요.

원래 파일에서 비트 하나가 뒤집혔을 때, 그 중복으로 어느 비트가 틀렸는지 찾을 수 있을까요?

글이면 사람이 문맥으로 찾겠지만… 가중치 파일은 숫자들이라 어느 비트가 틀렸는지 알 방법이 없어요. 중복이 있어도 오류를 고치기 좋게 놓인 중복은 아니네요.

원천의 중복은 원천이 정한 모양이고, 채널의 노이즈랑은 상관없으니까. 해밍 코드는 「비트 하나가 틀리면 신드롬이 틀린 자리 번호를 가리킨다」가 되게 일부러 놓은 중복이고.

섀넌의 정리 둘을 함께 보면, 원천을 엔트로피 근처까지 줄인 다음 채널에 맞는 코드를 붙여도 손해가 없어요. 원천의 비트가 엔트로피만큼, 채널은 기호마다 용량만큼이니, 엔트로피가 용량 아래면 둘을 따로 설계해도 틀리지 않게 보낼 수 있죠.

아, 중복의 양이 아니라 놓인 모양이 문제였네요. 덜어 내는 중복과 붙이는 중복은 하는 일이 달라서, 둘을 차례로 하는 게 헛일이 아니에요.

혼동하기 쉬운 점

혼동하기 쉬운 생각	나온 문제	바로잡는 법
엔트로피보다 조금 적게 쓰면 조금만 틀린다고 봄	2	길게 묶으면 엔트로피보다 적게 쓰는 한 되살리지 못할 확률이 1로 간다
가장 그럴듯한 수열이 전형적인 수열이라고 봄	1	하나의 확률이 가장 큰 수열(모두 0)은 개수가 하나뿐이라 확률 합이 작다. 개수 × 확률로 본다
맞힌 비율로 채널(답하는 사람)의 쓸모를 잼	4, 6	늘 반대로 답하면 뒤집어 읽으면 된다. 정보는 1 − h(ε)로 재고, ε = 0.5가 0이다
망가진 비율이 같으면 용량도 같다고 봄	5	망가진 자리를 아는 지워짐 채널은 1 − 지워짐, 모르는 이진 대칭 채널은 1 − h(ε)로 훨씬 작다
오류율을 0으로 하려면 레이트도 0으로 가야 한다고 봄	토론 1	반복 코드의 한계일 뿐이다. 용량 아래 레이트에서 블록을 길게 하면 오류율을 0에 가깝게 할 수 있다
해밍(7,4)가 두 비트 오류도 알아챈다고 봄	8	신드롬은 한 비트 오류를 가정하고 자리를 가리켜, 두 비트 오류를 엉뚱한 자리로 「고친다」
사본을 여러 벌 두는 것이 가장 안전하다고 봄	9	패리티 조각을 여럿 둔 코드가 덜 저장하고도 같거나 더 안전하다
용량을 조금 넘으면 오류도 조금만 는다고 봄	토론 2	용량 위에서는 오류율이 1 − C/R 이상이고, 블록이 길수록 나빠진다
파노 하한이 실제 오류율과 크게 다르면 틀렸다고 봄	11	틀리는 방향이 몰리면 느슨해질 뿐이다. 실제로 헷갈리는 클래스 수로 다시 본다
파노 상한을 넘는 점수는 무조건 불가능하다고 봄	12	분류기가 입력만 본다는 가정이 깨졌는지(시험 자료가 학습에 섞임), 시험 라벨의 노이즈가 다른지 본다
크로스 엔트로피 손실을 파노 부등식의 H(Y∣X) 자리에 넣음	ML에서(파노)	손실은 남은 불확실성의 위쪽 경계라, 넣으면 하한이 아니게 된다
압축 뒤에 오류 정정 비트를 붙이는 것을 헛일로 봄	토론 3	원천의 중복은 오류 자리를 가리키게 놓여 있지 않다. 줄인 뒤 채널에 맞게 덧붙여도 손해가 없다

요약

이 장에서 한 일을 정리해 보자. 기호마다 같은 비율로 서로 상관없이 나오는 원천의 긴 수열은, 하나하나의 확률이 거의 2^(−nH)로 같은 전형 집합에 확률이 거의 다 모이고, 그 개수는 2^(nH)쯤이다. 그래서 전형 집합에 번호를 붙이면 기호 하나에 H비트에 다가가고(앞면 확률 0.1인 동전에서 길이 10의 0.900비트가 10만에서 0.476비트로), 그보다 적게 쓰면 길이가 길어질수록 되살리지 못할 확률이 1로 간다. 이 두 방향이 원천 코딩 정리다.

노이즈가 비트를 뒤집는 선에서 기호 하나로 건너가는 정보는 상호정보량이고, 입력 분포를 골라 얻는 그 최댓값이 채널 용량이다. 뒤집힘 확률 ε인 이진 대칭 채널은 반반으로 보낼 때 C = 1 − h(ε)이고, 섀넌의 예에서는 1초에 990이 아니라 919비트였다. 채널 코딩 정리에 따르면 레이트가 용량보다 작은 한 블록을 길게 해 오류율을 0에 가깝게 할 수 있고, 반복 코드처럼 레이트를 0으로 보낼 필요가 없다. 해밍(7,4) 코드는 확인 비트 셋으로 한 비트 오류를 고치고, 신드롬이 틀린 자리 번호를 이진수로 가리킨다. 파노 부등식은 입력을 보고도 남는 불확실성에서 어떤 분류기나 디코더도 넘을 수 없는 오류율의 하한을 주고, 레이트가 용량을 넘으면 오류율이 1 − C/R 아래로 내려가지 못한다는 것도 여기서 나온다.

flowchart LR
  S["원천<br/>기호마다 엔트로피 H"] -- "원천 코딩 정리<br/>기호당 H비트로 줄임" --> E["줄인 비트열"]
  E -- "채널 코딩 정리<br/>레이트 R < C 인 코드" --> CH["노이즈 채널<br/>용량 C = max I(X;Y)"]
  CH -- "가장 가까운 코드로 읽기" --> D["되살린 비트열"]
  CH -. "R > C 이면<br/>파노 부등식: 오류율 ≥ 1 − C/R" .-> D

정리 연습문제

물음. 앞면 확률 0.1인 동전을 길이 1000으로 던진 수열을, 엔트로피(기호당 0.469비트)보다 적은 기호당 0.3비트로 무손실 압축하려 한다. 맞는 말은?

[ ] 조금 모자라니 열에 한두 번쯤 틀린다 〔틀림: 길게 묶을수록 엔트로피보다 적게 쓰면 되살리지 못할 확률이 1로 간다. 길이 1000이면 맞게 되살릴 확률이 1000만 분의 1쯤이다.〕
[x] 길이가 길수록 거의 늘 되살리지 못한다 〔맞음: 번호 2^300개가 덮는 확률은 많아야 2^300 × 2^(−0.469×1000)쯤으로 지수만큼 작다.〕
[ ] 산술 코딩을 쓰면 된다 〔틀림: 산술 코딩도 원천 코딩 정리의 하한 위에 있다.〕

물음. 뒤집힘 확률 0.9인 이진 대칭 채널의 용량은?

[ ] 0.1비트. 열에 하나만 맞으니까 〔틀림: 늘 같은 방향으로 틀리면 받은 비트를 뒤집어 읽으면 된다.〕
[x] 0.531비트. 뒤집힘 0.1인 채널과 같다 〔맞음: 1 − h(0.9) = 1 − h(0.1) = 0.531.〕
[ ] 0비트. 대부분 틀리니까 〔틀림: 용량이 0인 것은 받은 비트가 보낸 비트와 상관없는 ε = 0.5일 때다.〕

물음. 용량 0.531인 채널로 오류율을 아주 낮게 보내고 싶다. 맞는 말은?

[ ] 반복을 늘려 레이트를 0 가까이 낮추는 수밖에 없다 〔틀림: 반복 코드의 한계다. 용량 아래 레이트에서는 블록을 길게 해 오류율을 원하는 만큼 낮추는 코드가 있다.〕
[x] 레이트 0.5로 고정하고 블록을 길게 하는 코드로 오류율을 원하는 만큼 낮출 수 있다 〔맞음: 채널 코딩 정리. 0.5는 용량 0.531보다 작다.〕
[ ] 레이트 0.6이라도 블록을 충분히 길게 하면 된다 〔틀림: 용량을 넘는 레이트에서는 오류율이 1 − 0.531/0.6 = 0.115 아래로 내려가지 못한다.〕

물음. 10 클래스 자료에서 입력을 보고도 남는 라벨의 불확실성이 1비트다. 맞는 말은?

[x] 어떤 분류기도 13.5%보다 덜 틀릴 수 없다 〔맞음: h(P_e) + P_e·log₂ 9 = 1을 풀면 P_e = 0.135.〕
[ ] 남은 불확실성이 1비트이니 두 번에 한 번은 틀린다 〔틀림: 그것은 두 후보 사이에서 고르게 헷갈릴 때다. 클래스가 열이면 틀린 경우를 적는 비트가 커서 하한이 0.135로 내려간다.〕
[ ] 정확도 86.5%를 내는 분류기가 늘 있다 〔틀림: 파노 부등식은 하한만 준다. 하한에 닿으려면 틀릴 때 나머지 아홉에 고르게 틀려야 한다.〕

막힌 곳

이 장의 두 정리는 원천과 채널을 미리 안다고 했다. 원천 코딩 정리의 H는 참 분포의 엔트로피이고, 채널 코딩 정리의 C는 노이즈의 확률을 알아야 셀 수 있다. 동전이나 날씨처럼 기호마다 같은 비율로 서로 상관없이 나오는 원천이면 비율 하나만 알면 됐다. 그런데 사진처럼 칸 수천 개의 값이 서로 얽혀 있는 자료라면, 원천의 분포를 무엇으로 적어야 할까? 동전을 길게 던진 수열에서는 확률이 전형 집합이라는 좁은 곳에 몰려 있었는데, 그럴듯한 사진도 칸 수천 개가 만드는 넓은 공간 안에서 좁은 곳에 모여 있을까? 모여 있다면 그곳은 어떤 모양이고, 그 모양을 알면 사진 한 장에 적어야 할 숫자는 얼마나 줄어들까?