섀넌의 엔트로피 공식.내 혼란을 도와주세요

Question

엔트로피 공식에 대한 나의 이해는 일부 데이터를 표현하는 데 필요한 최소 비트 수를 계산하는 데 사용된다는 것입니다.정의할 때 일반적으로 다르게 표현되지만, 이전의 이해는 지금까지 내가 의존한 것입니다.

내 문제는 다음과 같습니다.100 '1' 다음에 100 '0' = 200비트의 시퀀스가 ​​있다고 가정합니다.알파벳은 {0,1}이고 엔트로피 베이스는 2입니다.기호 "0"의 확률은 0.5이고 "1"은 0.5입니다.따라서 엔트로피는 1비트를 나타내기 위해 1또는 1비트입니다.

그러나 출력할 비트 수 뒤에 비트가 오는 100/1/100/0과 같은 형식으로 실행 길이 인코딩할 수 있습니다.데이터보다 작은 표현이 있는 것 같습니다.특히 100을 훨씬 더 큰 숫자로 늘리면 더욱 그렇습니다.

나는 다음을 사용하고 있습니다 : http://en.wikipedia.org/wiki/Information_entropy 현재 참고로.내가 어디서 잘못됐나요?기호에 할당된 확률인가요?나는 그것이 틀렸다고 생각하지 않습니다.아니면 압축과 엔트로피 사이의 연결을 잘못 이해한 걸까요?다른 건 없나요?

감사해요.

편집하다

내 후속 답변 중 일부는 다음과 같습니다.정보 내용을 알아내기 위해 메시지의 특정 인스턴스에 엔트로피 공식을 적용하시겠습니까?"aaab" 메시지를 받아 엔트로피가 ~0.811이라고 말하는 것이 유효할까요?그렇다면 엔트로피 공식을 사용하여 1과 0이 n번 반복되는 경우 1...10...0의 엔트로피는 무엇입니까?답은 1인가요?

예, 입력 기호의 무작위 변수를 생성하고 메시지를 기반으로 확률 질량 함수를 추측하고 있다는 것을 이해합니다.내가 확인하려는 것은 엔트로피 공식이 메시지의 기호 위치를 고려하지 않는다는 것입니다.

Answer 1

아니면 압축과 엔트로피 사이의 연결을 잘못 이해한 걸까요?

당신은 꽤 가깝습니다. 그러나 이 마지막 질문은 실수가 있었던 곳입니다.원래 표현보다 작은 형태로 무언가를 압축할 수 있다면 원래 표현에 최소한 어느 정도 중복성이 있다는 뜻입니다. 메시지의 각 비트는 실제로 단 1비트의 정보도 전달하지 못했습니다.

중복 데이터는 메시지의 정보 내용에 기여하지 않으므로 엔트로피도 증가하지 않습니다.예를 들어 "0" 값만 반환하는 "무작위 비트 생성기"를 상상해 보세요.이것은 전혀 정보를 전달하지 않습니다!(실제로는 다음과 같은 내용을 전달합니다. 한정되지 않은 왜냐하면 한 종류의 기호로만 구성된 이진 메시지는 엔트로피 공식에서 0으로 나누어야 하기 때문입니다.)

대조적으로, 많은 수의 무작위 동전 던지기를 시뮬레이션했다면 이 메시지의 크기를 크게 줄이는 것은 매우 어려울 것입니다.각 비트는 1비트의 엔트로피에 가깝게 기여합니다.

데이터를 압축하면 해당 중복성이 추출됩니다.그 대가로 이 데이터를 압축하고 압축 해제하는 방법을 아는 체계를 고안해야 하므로 일회성 엔트로피 가격을 지불합니다.그 자체에는 약간의 정보가 필요합니다.

그러나 출력할 비트 수 뒤에 비트가 오는 100/1/100/0과 같은 형식으로 실행 길이 인코딩할 수 있습니다.데이터보다 작은 표현이 있는 것 같습니다.특히 100을 훨씬 더 큰 숫자로 늘리면 더욱 그렇습니다.

요약하자면, 다음과 같은 계획을 세울 수 있다는 사실입니다. 데이터 인코딩 보다 작은 원본 데이터 중요한 것을 말해줍니다.즉, 다음과 같이 말합니다. 원본 데이터에는 정보가 거의 포함되어 있지 않습니다..

---

추가 읽기

몇 가지 예를 통해 임의의 숫자 시퀀스에 대한 엔트로피를 계산하는 방법을 포함하여 이에 대한 보다 철저한 처리를 확인하십시오. 이 짧은 백서.

Answer 2

보세요 콜모고로프 복잡성

정보 손실 없이 문자열을 압축할 수 있는 최소 비트 수입니다.이는 보편적인 Turing 기계에 의해 제공되는 고정되었지만 보편적인 압축 해제 체계와 관련하여 정의됩니다.

그리고 특별한 경우에는 알파벳 {0,1}로 제한하지 마십시오.예를 들어 {0...0, 1...1}(000개와 100개)을 사용합니다.

Answer 3

이 예에서는 인코딩이 작동하지만 똑같이 유효한 경우를 생각해 볼 수도 있습니다.010101010101...1 / 0 / 1 / 1 / ...로 인코딩됩니다.

엔트로피는 병리학적 예뿐만 아니라 주어진 알파벳으로 구성할 수 있는 모든 가능한 메시지에 걸쳐 측정됩니다!

Answer 4

John Feminella의 말이 맞았지만 할 말이 더 많은 것 같습니다.

섀넌 엔트로피는 확률을 기반으로 하며 확률은 항상 보는 사람의 눈에 달려 있습니다.

1과 0의 가능성이 동일하다고 말씀하셨습니다(0.5).그렇다면 100개의 1 뒤에 100개의 0이 오는 문자열의 확률은 0.5^200이며, 예상대로 -log(base 2)는 200비트입니다.그러나 해당 문자열의 엔트로피(Shannon 용어로)는 정보 내용에 확률을 곱한 값, 즉 200 * 0.5^200이지만 여전히 매우 작은 숫자입니다.

문자열을 압축하기 위해 실행 길이 코딩을 수행하는 경우 이 문자열의 경우 길이가 작아지지만 전체 2^200 문자열에 대한 평균을 계산하면 제대로 작동하지 않기 때문에 이는 중요합니다.운이 좋다면 평균적으로 약 200 정도가 될 것입니다. 그러나 그 이하도 아닙니다.

반면에 원래 문자열을 보고 그것이 너무 인상적이어서 그것을 생성한 사람이 누구든 그와 유사한 것을 더 많이 생성할 가능성이 높다고 말하면 실제로 그 확률이 ​​0.5^200보다 크다고 말하는 것이므로 다른 문자열을 만드는 것입니다. 문자열 생성기의 원래 확률 구조, 즉 엔트로피가 200비트보다 낮다는 가정.

개인적으로 저는 이 주제가 정말 흥미롭다고 생각합니다. 특히 Kolmogorov(알고리즘) 정보를 살펴볼 때 더욱 그렇습니다.이 경우 문자열의 정보 내용을 해당 문자열을 생성할 수 있는 가장 작은 프로그램의 길이로 정의합니다.이는 소프트웨어 엔지니어링 및 언어 설계에 대한 모든 종류의 통찰력으로 이어집니다.

도움이 되었기를 바랍니다. 질문해 주셔서 감사합니다.