이 단원 목차
확률에서 실제 이진 부호로
자기정보 −log₂p는 이상적인 길이와 연결되지만, 실제 부호는 이진 문자열입니다. 부호집 0은 네 기호에 0,10,110,111을 배정하고 길이는 1,2,3,3입니다. 부호집 1은 00,01,10,11로 모두 길이 2입니다. 어느 단어도 다른 단어의 접두사가 아니므로 둘 다 순차 복호화할 수 있습니다.
여덟 관측의 비트 수 세기
관측 개수가 (4,2,1,1)이면 부호집 0의 데이터 길이는 4×1+2×2+1×3+1×3=14 bits입니다. 부호집 1은 8×2=16 bits입니다. 경험 엔트로피는 1.75 bits/기호이고 첫 부호의 평균 길이도 1.75입니다. 이 경우 길이가 −log₂ 빈도와 맞는 특별한 예제입니다.
다른 빈도에서는 같지 않을 수 있습니다. 균등 개수 (2,2,2,2)에서는 첫 부호의 데이터가 18 bits, 고정 길이 부호가 16 bits입니다. 모든 부호집이 모든 분포에 최적인 것은 아닙니다. 알려진 유한 정보원의 최적 접두 평균 길이에 대한 엔트로피 경계와 현재 선택한 고정 부호집의 길이를 구분하세요.
수신자에게 모형도 알려주기
어떤 부호집을 썼는지 알리는 헤더를 포함합니다. 부호집 0의 헤더는 10, 부호집 1은 0으로 이 헤더들도 접두 부호입니다. 따라서 기본 데이터의 두 부분 총 길이는 2+14=16 bits와 1+16=17 bits입니다. 여기서는 관측 수 N이 알려져 있어 종료를 알리는 별도 길이는 비교에서 제외합니다.
이것은 사전에 정한 두 유효 부호집 사이의 작은 MDL 예제입니다. 연속 모수를 학습하거나 정교한 universal coding을 구현한 것은 아닙니다. 부호집 자체를 데이터로 설계한다면 그 설명 비용도 별도로 정해야 합니다.
짧아 보이지만 무효인 부호
부호집 2는 0,01,10,11입니다. 0이 01의 접두사이고 Kraft 합은 1.25입니다. 실제 문자열 010을 0|10 또는 01|0으로 읽을 수 있어 모호합니다. 화면은 원시 평균 길이를 보여주되 유효한 총 길이는 —로 표시하고 MDL 후보에서 제외합니다. 접두사가 아니라는 사실만으로 모든 일반 부호의 복호화 가능성을 판정하는 것은 아니지만, 이 목록은 직접적인 모호성도 갖습니다.
파랑은 두 유효 후보의 데이터 비트 수, 주황은 헤더를 포함한 총 길이입니다. 표는 현재 선택한 기호 부호를 보여줍니다. 반복 횟수를 늘리면 데이터 비용은 비례하지만 고정 헤더 비용은 그대로입니다.
확인 문제와 해설
- 균등 개수의 더 짧은 두 부분 코드는? 총 17 bits인 고정 길이 후보입니다.
- invalid 후보가 짧으면 선택해도 되나요? 아니요. 유효한 복호화 규칙이 먼저입니다.
- 결정적 경험 빈도이면 이 고정 부호가 0 bits/기호인가요? 아니요. 네 기호 부호집을 유지한 예제입니다.
추가 읽기: Grünwald, A Tutorial Introduction to the Minimum Description Length Principle.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.