[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
1. 개요
정보 엔트로피(information entropy)란 정보이론에서 확률변수의 불확실성(uncertainty)을 정량화하는 척도이다.확률변수의 불확실성을 정량화하는 방법, 즉 엔트로피를 정의하는 방법은 활용 방법과 그 의의에 따라 다양하지만, 가장 널리 사용되는 엔트로피는 섀넌 엔트로피(Shannon entropy)이다. 섀넌 엔트로피는 한 메시지에 들어갈 수 있는 정보량[1]의 비트 수로 해석될 수 있다. 정보 이론의 창시자인 수학자 클로드 섀넌이 1948년 창안하였고, 컴퓨터과학, 암호학, 데이터 압축 등에서 사용되는 개념이다.
2. 정의
2.1. 정보 측도
일단 정보를 정량화하기 위해서는 정보가 무엇인지 직관적인 이해가 필요하다. 다음 예를 통해 그 의미가 무엇인지 생각해보자.문장 1: 해는 동쪽에서 뜬다.
문장 2: 내일 엔비디아 주식 가격이 오른다.
위 예에서 "문장 1"은 너무 당연한 소리이므로 누군가에게 이 문장을 알려준다해도 그 사람이 실질적으로 알게되는 추가 정보는 없다. 반면 "문장 2"의 경우, 어떠한 주식이 오르고 내릴 확률은 효율적 시장 가설이 맞다면 (퍼블릭하게 알려진 정보 외에는 아는 게 없다고 가정할 때) 거의 50% 이므로 "문장 2"가 참이라면 엄청나게 유용한 정보될 것이다. 즉, 어떤 랜덤 변수가 확정적으로 어떤 값을 가지면 (즉, deterministic 하다면), 그 랜덤 변수가 realize되었을 때 얻게 되는 정보량은 0이고, 변수가 완전 랜덤할수록 그 랜덤 변수가 realize되었을 때 얻게 되는 정보량은 많다고 볼 수 있다.이러한 직관을 가지고 어떠한 확률 변수 [math(X)]에 대해 각 사건(outcomes)에 대한 정보량은 대충 다음과 같아야 한다:
[math(\displaystyle X = \begin{cases} x_1 &\text{with probability }p_1 \\
x_2 &\text{with probability }p_2 \\
\vdots \\
x_n &\text{with probability }p_n
일 때, [math(i)]번째 사건 [math(x_i)]이 일어났을 때 얻게되는 정보량은 확률 [math(p_i)]가 클수록 작아지고 작을수록 커야할 것이다. 이를 테면 [math(1/p_i - 1)]나 [math(\log(1/p_i))]로 정보량을 세팅하면 [math(p_i=1)]일 때 0 (당연한 걸 알려줬을 때 얻는 정보는 0), [math(p_i=0)]일 때 [math(\infty)](전혀 예상치도 못한 것을 알려줬을 때 얻는 정보는 무한대)이 되어서 위 직관과 합치된다. x_2 &\text{with probability }p_2 \\
\vdots \\
x_n &\text{with probability }p_n
\end{cases})]
하지만 여러 수학적인 편의성을 위해 후술할 다양한 종류의 정보 측도들이 개발되었다. 정보 측도로써 가져야할 특징들을 생각해보면 다음과 같다.
| 정보 측도 (Information Measure) 정보 측도 [math(I)]는 다음을 만족하는 측도이다.
이 외에 수학적인 편의성을 위해 다음을 만족하여야 한다.
[math(\displaystyle I(X) = I(p_1, \ldots, p_n))] [math(\displaystyle I(X, Y) = I(X) + I(Y) \qquad \text{ if } X \perp\!\!\!\perp Y)] |
이러한 조건을 만족시키는 정보 측도들은 다음과 같다.
2.2. 섀넌 엔트로피
위의 정보 측도 정의에서 두 독립 확률 변수 [math(X, Y)]에 대해 [math(\displaystyle I(X, Y) = I(X) + I(Y))] 만족 시키기 좋은 가장 간단한 form은 [math(\log(1/p_i))]형태임을 짐작할 수 있을 것이다.[2]실제로 섀넌은 이산 확률 변수 [math(X)]의 엔트로피 [math( H(X))]를 다음과 같이 정의하였다.[3]
[math(p(x))]는 [math(X)]의 확률 질량 함수이며, [math(\mathcal{X})]는 확률 변수 [math(X)]가 취할 수 있는 값들의 집합이다. 여기서 완전 랜덤한 1 bit (50%확률로 1, 나머지 확률로 0)의 정보량을 1로 unit을 맞추기 위해 [math(log)]는 밑이 2인 로그를 사용한다.[4]
섀넌 엔트로피 [math(H(X))]는 다음과 같은 성질을 가진다.
- [math(X)]의 섀넌 엔트로피 [math( H(X))]는 [math(-\log p(X))]의 기댓값이다. 즉, [math( \mathbb{E} [-\log p(X) ] = H(X))]이다.[5]
- 임의의 [math(X)]에 대해 [math( H(X) \geq 0)]이다.[6]
- 임의의 [math(X)]에 대해 [math( H(X) \leq \log |\mathcal{X}|)]이다. 즉 [math(\mathcal{X})]에 대해 최대 엔트로피를 갖는 확률 분포는 균등 분포(Uniform distribution)이다.[7]
- 일반적으로 로그의 밑을 2로 사용하며, 이때의 섀넌 엔트로피의 단위는 비트이다.
2.3. 레니 엔트로피
레니 엔트로피(Rényi entropy)는 섀넌 엔트로피, 충돌 엔트로피(collision entropy), 최소 엔트로피(min-entropy) 등 다양한 정보 엔트로피의 척도를 일반화한 것이다.이산 확률 변수 [math(X)]의 레니 엔트로피 [math( H_{\alpha}(X))]는 다음과 같이 정의된다.
[math(p(x))]는 [math(X)]의 확률 질량 함수이며, [math(\mathcal{X})]는 확률 변수 [math(X)]가 취할 수 있는 값들의 집합이다.
또한 특수한 경우의 레니 엔트로피를 다음과 같은 극한으로 정의한다.
- (최대 엔트로피) [math(H_{0}(X) = \displaystyle \lim_{\alpha \to 0}{H_{\alpha}(X)} = \log_{2}{|\mathcal{X}|})]
- (섀넌 엔트로피) [math(H_{1}(X) = \displaystyle \lim_{\alpha \to 1}{H_{\alpha}(X)} = H(X))]
- (최소 엔트로피) [math(H_{\infty}(X) = \displaystyle \lim_{\alpha \to \infty}{H_{\alpha}(X)} = -\log_{2} \left( \max_{x \in \mathcal{X}}{p(x)} \right) )]
섀넌 엔트로피는 레니 엔트로피의 [math(\alpha \to 1)]인 특수한 경우이다. 로피탈의 정리를 사용하면 레니 엔트로피의 [math(\alpha \to 1)]의 극한이 섀넌 엔트로피가 됨을 쉽게 보일 수 있다.
2.4. 미분 엔트로피
[math(X)]가 연속 확률 변수인 경우의 섀넌 엔트로피 [math( h(X))]는 특별히 미분 엔트로피(differential entropy)라 하며, 다음과 같이 정의된다.[math(f(x))]는 [math(X)]의 확률 밀도 함수이며, [math(S)]는 이 확률 변수의 지지 집합(support)이다.
이산 확률 변수는 균등 분포일 때 최대 섀넌 엔트로피를 갖는 반면, 연속 확률 변수의 경우 동일한 [math(S)]에 대해 미분 엔트로피의 최대를 제공하는 분포는 정규 분포가 된다.
3. 개념
예를 들어 a부터 z까지의 알파벳 100글자가 적혀 있는 텍스트 파일이 있다고 하자. 이 파일은 100바이트 = 800비트의 크기를 가질 것이다. 그러나 이 파일은 26가지 글자만을 담을 수 있는 제약이 있으므로, 실제로 가질 수 있는 상태는 최대 [math(26^{100})]가지이다. 따라서 이 파일의 엔트로피는 [math(\log_2 26^{100} = )] 약 470 비트가 된다. 즉, 영어 알파벳 1글자의 엔트로피는 글자당 약 4.7비트이다. 대소문자 구별까지 고려할 경우 글자당 약 5.7비트가 된다.만약 이 파일이 문법에 맞는 영어 문장만을 담고 있다면, 파일의 엔트로피는 더 줄어들게 된다. 랜덤하게 적혀 있는 영어 글자는 말이 되는 문장보다는 말이 안 되는 문장이 훨씬 많기 때문이다. 영어 문장의 엔트로피는 한글자당 1.1 비트 정도로 알려져 있다. 엔트로피 계산은 통계적인 방법에 따라 차이가 난다. 연구 방법에 따라 0.6 비트에서 1.5 비트까지 다양하다.
엔트로피는 이론상 어떤 정보를 나타낼 수 있는 최소한의 비트 수를 의미하기 때문에, 무손실 압축 포맷의 용량은 그 정보의 엔트로피 값보다 작아질 수 없다. 손실 압축 포맷의 경우는 정보가 일부 유실되므로, 엔트로피보다 작은 크기로 줄어들 수 있다.
한글의 경우 한국어에서의 각 자모가 처음으로 등장할 확률 및 마르코프 방법을 이용하면 더 많이 최적화가 가능하다.
4. 물리학에서의 적용
일각의 물리학자들은 이것을 모든 것의 이론의 후보로 꼽기도 한다. 만일 모든 것을 설명할 수 있는 이론 P가 있다고 하자. 이 P가 성립하는 근거는 무엇인가? 우리가 물리법칙에 대해 어떤 이론을 만들든 간에 더 근본적인 이론은 항상 존재해야만 한다.[9] 따라서 모든 것을 설명하는 만물 이론이 정말로 있다면, 그 이론은 아마도 아무런 근거 없이 성립해야 한다. 즉, 모든 자연현상은 본질적으로 엔트로피가 증가하는 확률론적 이유로 일어날 뿐 그 이상의 근본적인 이유는 없다.결과적으로, 여타 물리법칙들은 정보 엔트로피가 증가하는 방향으로 일어나며, 열역학 제2법칙이야말로 이 우주의 근본 법칙이고, 이를 살펴보는 과정에서 마치 전혀 다른 물리법칙들이 존재하는 것처럼 보일 뿐이라는 것이 이들의 주장이다. 아직 검증을 거치고 있지만, 중력을 시공간 정보 엔트로피의 증가로 설명하는 엔트로피 중력(Entropic gravity) 이론이 제안되어 있다.
4.1. 열역학적 엔트로피와의 관계
클로드 섀넌이 정보통신 이론을 창안할 당시, 정보량의 크기를 나타낼 수 있는 공식을 찾고 있었다. 그러던 중 확률 이론을 도입하여 공식을 만들어내는데, 그렇게 공식을 만들고 보니 열역학적 엔트로피와 동일한 모양이었다.- 열역학적 엔트로피(깁스 엔트로피): [math( S= - k_B \sum p_i \ln p_i )]
- 정보 엔트로피(섀넌 엔트로피): [math( \displaystyle H(X) = - \sum_{i=1}^{n} p(x_i) \log_b p(x_i) )]
이러한 유사성에 착안한 섀넌은 자신의 공식에 엔트로피라는 이름을 붙이게 된다. 그런데 이 유사성이 공식에만 그치지 않는다는 것이 나중에 발견되었다. 정보 엔트로피는 어떤 확률변수가 나타낼 수 있는 상태의 총합으로 정의할 수 있고, 열역학적 엔트로피는 분자들의 배열이 나타낼 수 있는 상태의 총합에 로그함수를 취한 것으로 정의할 수 있다. 즉, 열역학적 엔트로피는 정보 엔트로피의 한 형태이다. 1 J K-1=13.06175ZB(=11.06373ZiB)에 해당하지만 그렇게 자주 쓰는 표현은 아니다.[10]
맥스웰의 악마 역설은 정보 엔트로피의 개념이 알려지면서 풀렸다. 맥스웰의 악마가 분자를 분류하려면 그 분자의 정보를 알아야 한다. 따라서 도깨비가 물리법칙을 따르는 존재라면 분자에 대한 정보를 저장할 물리적인 시스템을 포함해야 한다. 그리고 이 시스템은 최소 자신이 저장하는 정보만큼의 엔트로피를 가지게 된다(정보 저장을 축전기에 저장된 전하량으로 하든 전자의 스핀으로 하든 상관 없다). 따라서 분자의 분류를 위해 수집하는 정보의 엔트로피가 총엔트로피에 포함되어 결과적으로 시스템 전체의 엔트로피는 증가한다.
5. 여담
- 2018학년도 대학수학능력시험 국어 영역에 나왔다.
[1] 정보를 물리량으로 본 것.[2] 두 사건이 독립일 때 사건 [math(X=x, Y=y)]가 일어날 확률은 [math(P(X=x,Y=y)=P(X=x) P(Y=y))]이므로 총 정보량은 [math(I(X=x, Y=y)=\log\frac{1}{P(X=x, Y=y)}=\log\frac{1}{P(X=x)P(Y=y)} = I(X=x) + I(Y=y))].[3] The Khinchin Axioms for Entropy의 조건에 다 맞는 정보 측도는 섀넌 엔트로피 밖에 없다는 것을 증명할 수 있다.[4] 실제로 위 식에 대입해보면 밑이 2인 로그를 사용해야지 1이 나오는 것을 알 수 있다.[5] 확률 변수 [math(X)]가 어떠한 값을 취하는지는 중요하지 않다. 엔트로피를 구할 때는 확률 변수가 어떠한 각각의 값을 취할 확률, 즉 확률 질량 함수의 치역만 고려하면 된다.[6] [math(p(x))]는 항상 [math(0)]과 [math(1)] 사이의 값이며, 따라서 [math(-\log p(x))]은 음이 아닌 실수값을 갖게 되므로 그 기댓값은 반드시 [math(0)]보다 크거나 같다.[7] 균등 분포일 때 섀넌 엔트로피는 [math(\log |\mathcal{X}|)]이므로 이 경우 부등식의 등호가 성립한다.[8] 정의역 내에서 [math(y=-x \log x )]가 오목함수이므로 이들의 합인 섀넌 엔트로피 역시 오목성을 만족한다.[9] 예를 들어 중력의 경우, 뉴턴의 만유인력 법칙이든 아인슈타인의 상대성 이론이든 각각 왜 물체가 다른 물체를 끌어당기는지, 왜 질량이 주변의 시공간을 왜곡시키는지는 설명하지 못한다. 이는 물리학의 한계라기 보다는 인간 논리의 한계이다. ‘왜?’라는 질문을 끊임없이 반복하면 언젠가는 한계에 부딪히기 때문이다.[10] 양자역학에서 J(줄)보다 많이 쓰는 eV(전자볼트)단위로는 1 eV K-1가 약 2092.7 바이트에 해당한다. 1kg=8.98755×1016J라고 잘 쓰지 않는 것과 같은 맥락이다.