엔트로피

Entropy; 정보 엔트로피

정보의 불확실성 또는 정보량을 수치로 나타낸 값

• 1948년 클로드 섀넌(Claude Shannon)이 정보 이론에서 제시했다.
• 어떤 사건이 일어날지 예측하기 어려울수록, 즉 불확실성이 클수록 엔트로피가 크다.
• 단위는 밑을 2로 하는 로그를 쓸 때 비트(bit)이다.

정의

확률변수 X가 값 x₁, x₂, …, xₙ을 각각 확률 p₁, p₂, …, pₙ으로 가질 때 엔트로피는 다음과 같다.

H(X) = -Σ pᵢ log₂ pᵢ

• 어떤 값이 나올 확률이 1이면(결과가 이미 정해져 있으면) 엔트로피는 0이다.
• 모든 값의 발생 확률이 같을 때, 즉 균등 분포일 때 엔트로피가 최대가 되며 그 값은 log₂ n이다.
• 따라서 한 비트가 가질 수 있는 엔트로피의 최댓값은 1이다. 0과 1이 각각 1/2 확률일 때가 그렇다.

성질

• 엔트로피는 항상 0 이상이다.
• 확률 분포가 한쪽으로 치우칠수록 엔트로피는 작아진다.
• 엔트로피는 그 정보를 표현하는 데 필요한 평균 비트 수의 하한이다. 무손실 압축의 한계를 정한다.

암호에서의 의미

• 암호문은 평문의 통계적 특성이 드러나지 않아야 하므로 암호문의 엔트로피가 높을수록 안전하다. 이상적인 암호문은 무작위 비트열과 구분되지 않는다.
• 키 공간의 엔트로피가 키의 실질적인 강도를 나타낸다. 128비트 키를 쓰더라도 예측 가능한 패스워드에서 키를 만들면 실제 엔트로피는 훨씬 낮다.
• 의사 난수 생성기의 시드는 충분한 엔트로피를 가진 값에서 얻어야 한다. 리눅스는 `/dev/random`, `/dev/urandom`으로 시스템이 수집한 엔트로피를 제공한다.
• 패스워드 엔트로피는 `log₂(사용 가능한 문자 수 ^ 길이)`로 어림한다.

관련 개념

• 결합 엔트로피 : 두 확률변수를 함께 고려한 엔트로피
• 조건부 엔트로피 : 한쪽을 알고 있을 때 남아 있는 불확실성
• 상호 정보량 : 한쪽을 알았을 때 줄어드는 불확실성
• 교차 엔트로피 : 두 확률 분포의 차이를 재는 값. 기계 학습의 손실 함수로 쓴다
• 의사결정 나무의 분할 기준 : 엔트로피가 가장 많이 줄어드는(정보 이득이 큰) 속성으로 분할한다

같이 보기

• 교차 엔트로피
• 의사 난수 생성기
• 암호