Fano 부등식과 분류 오류 경계

남은 불확실성과 분류 오류

M개의 라벨 중 X를 관측 Y로 추정하는 디코더 X̂=g(Y)를 생각합니다. 오류 사건 E=1{X̂≠X}의 확률을 Pₑ라고 합니다. Fano 부등식은 관측 후 남은 조건부 엔트로피를 그 디코더의 오류율로 상계합니다. 오류는 관측뿐 아니라 디코더 선택에도 의존합니다.

오류 여부를 먼저 알리는 논증

Y와 X를 알면 오류 여부도 정해집니다. 조건부 연쇄법칙으로 H(X|Y)=H(E|Y)+H(X|E,Y)를 얻습니다. 첫 항은 h₂(Pₑ) 이하입니다. 오류가 없으면 X는 디코더 출력으로 결정되고, 오류가 있으면 남은 후보는 최대 M−1개이므로 둘째 항은 Pₑ log₂(M−1) 이하입니다. 이 두 상한을 더하면 Fano를 얻습니다.

등호를 이루는 대칭 예제

실습은 균등한 X와 P(Y=X)=1−ε, 다른 각 라벨에 ε/(M−1)을 주는 채널을 사용합니다. 선택한 디코더는 Y를 그대로 반환합니다. 이 대칭 구조에서는 남은 잘못된 라벨이 균등해 날카로운 상계가 등호가 됩니다.

M=4,ε=.3이면 H(X|Y)=h₂(.3)+.3 log₂3≈1.35678 bits이고 I(X;Y)=2−H(X|Y)≈.64322 bits입니다. 표는 X=0일 때의 조건부 행 한 개를 보여줍니다. 나머지 행은 대칭으로 얻을 수 있습니다.

간단하지만 느슨한 오류 하한

h₂(Pₑ)≤1, log₂(M−1)≤log₂M을 사용하면 다음 더 느슨한 하한을 얻습니다. 균등 X에서는 H(X|Y)=log₂M−I(X;Y)로도 쓸 수 있습니다.

M=4이고 독립 출력 ε=.75이면 실제 최적 오류는 .75이지만 이 하한은 .5입니다. 경계가 정확한 오류율을 알려주는 것은 아닙니다. 그래프의 파랑은 이 대칭 모형의 조건부 엔트로피와 날카로운 Fano 식이고 주황은 1+ε log₂M의 느슨한 상계입니다.

100% 오류가 정보 0을 뜻하지 않는다

M=2,ε=1이면 Y는 항상 X와 반대입니다. 그대로 반환하는 디코더 오류는 1이지만 뒤집는 MAP 디코더 오류는 0이고 상호정보량은 1 bit입니다. 선택한 디코더와 최적 디코더를 구분하세요. 이 예제의 MAP 오류는 min(ε,1−ε/(M−1))입니다. 일반 자료에서 상호정보량 하나가 모든 디코더의 오류를 결정하지 않습니다.

확인 문제와 해설

1. Fano에서 오류가 났을 때 후보 수는 최대? M−1개입니다.
2. 이 대칭 예제의 등호가 모든 모형에서도 등호인가요? 아니요. 일반식은 상계입니다.
3. 느슨한 오류 하한이 음수면? 0과의 최댓값을 사용합니다.

추가 읽기: MIT 6.441, Information Theory — lecture notes by Polyanskiy and Wu.