Information theory is a branch of applied mathematics, electrical engineering, bioinformatics, and computer science involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and communicating data.


A key measure of information is entropy, which is usually expressed by the average number of bits needed to store or communicate one symbol in a message. Entropy quantifies the uncertainty involved in predicting the value of a random variable. For example, specifying the outcome of a fair coin flip (two equally likely outcomes) provides less information (lower entropy) than specifying the outcome from a roll of a die (six equally likely outcomes).


Information theory is based on probability theory and statistics. The most important quantities of information are entropy, the information in a random variable, and mutual information, the amount of information in common between two random variables. The former quantity indicates how easily message data can be compressed while the latter can be used to find the communication rate across a channel.

The choice of logarithmic base in the following formula determines the unit of information entropy that is used. The most common unit of information is the bit, based on the binary logarithm. Other units include the nat, which is based on the natural logarithm, and the hartley, which is based on the common logarithm.


정보이론은 통신방식의 발달과 더불어 발전하였다. Ralph Hartley는 1928년에 k종류의 부호를 n개 늘어놓음으로써 이루어지는 계열의 하나가 가지는 정보량은 배합의 수 kn종의 대수(對數)인 k = n log k에 의해서 가장 합리적으로 표시됨을 밝혔다. 이것이 정보량에서의 엔트로피(entropy)의 개념이다.


정보이론을 가장 완전하게 체계적으로 확립한 사람은 벨 연구소의 Claude E. Shannon이다. 섀넌은 정보를 확률과정으로서 파악, 정보량을 확률과정론에 도입하여 넓은 의미에서 정의하고, 잡음에 의한 영향을 고려하였으며, 정보량으로서의 엔트로피라든가 정보로(情報路)의 통신용량의 개념 등 많은 새로운 개념을 도입하였다.


앞면과 뒷면이 나올 확률이 같은 동전을 던졌을 경우의 정보의 양, 즉 엔트로피를 생각해 보자. 이는 H,T 두가지의 경우만을 나타내므로 엔트로피는 1이다. 다시 생각하면 우리에게 1비트만 주어진다면 동전 던지기시행의 결과값을 나타낼 수 있다는 것이다. 한편 공정하지 않는 동전의 경우에는 특정면이 나올 확률이 상대적으로 더 높기 때문에 엔트로피는 1보다 작아진다. 우리가 예측해서 맞출 수 있는 확률이 더 높아졌기 때문에 정보의 양, 즉 엔트로피는 더 작아진 것이다. (동전던지기의 경우에는 앞,뒤면이 나올 확률이 1/2로 같은 동전이 엔트로피가 가장 크다.) 그러면 여기서 정보 엔트로피를 불확실성(uncertainity)과 같은 개념이라고 인식할 수 있다. 불확실성이 높아질수록 정보의 양은 더 많아지고 엔트로피는 더 커진다.


Entropy

The entropy, H, of a discrete random variable X is a measure of the amount of uncertainty associated with the value of X.

Suppose one transmits 1000 bits (0s and 1s). If these bits are known ahead of transmission (to be a certain value with absolute probability), logic dictates that no information has been transmitted. If, however, each is equally and independently likely to be 0 or 1, 1000 bits (in the information theoretic sense) have been transmitted. Between these two extremes, information can be quantified as follows. If x is the set of all messages {x1, ..., xn} that X could be, and p(x) is the probability of some x ∈ x, then the entropy, H, of X is defined:



(Here, I(x) is the self-information, which is the entropy contribution of an individual message, and EX is the expected value.) An important property of entropy is that it is maximized when all the messages in the message space are equiprobable p(x) = 1 / n,—i.e., most unpredictable—in which case .

The special case of information entropy for a random variable with two outcomes is the binary entropy function, usually taken to the logarithmic base 2:



Joint entropy

The joint entropy of two discrete random variables X and Y is merely the entropy of their pairing: (X,Y). This implies that if X and Y are independent, then their joint entropy is the sum of their individual entropies.

For example, if (X,Y) represents the position of a chess piece — X the row and Y the column, then the joint entropy of the row of the piece and the column of the piece will be the entropy of the position of the piece.



Despite similar notation, joint entropy should not be confused with cross entropy.


Kullback-Leibler divergence (information gain)

The Kullback–Leibler divergence (or information divergence, information gain, or relative entropy) is a way of comparing two distributions: a "true" probability distribution p(X), and an arbitrary probability distribution q(X). If we compress data in a manner that assumes q(X) is the distribution underlying some data, when, in reality, p(X) is the correct distribution, the Kullback–Leibler divergence is the number of average additional bits per datum necessary for compression. It is thus defined




Example

일렬로 나열된 16장의 카드가 있는데 상대방이 마음 속으로 하나의 카드를 고르고 내가 그 카드를 알아 맞추는 게임을 진행한다. 상대방은 나의 질문에 대해 <예, 아니오>로만 대답할 수 있다. 질문은 16장의 카드의 위치를 절반을 기준으로 물어 들어간다. 예를 들어 고른 카드가 가운데를 기준으로 왼쪽에 있습니까? 라는 질문을 하게 되는 것이다. 그럼 결국 상대방이 고른 카드를 알아맞추는 데에는 총 4회의 질문이 필요하다. 이것을 수식으로 나타내면 log2 16 = 4이다. 여기서 4는 정보량이다. 이것의 단위는 bit로 둘 중 하나를 선택하는 정보량의 단위이다. 그러므로 16장의 카드에서 어떤 특정 카드를 고르는 정보는 4비트이다. Shannon은 이것을 확률적 방식으로 표현하였다. 16장 중에 하나를 고를 확률은 1/16이므로 이것을 n = - log2 1/16 으로 4를 구할 수 있다.



References


저작자표시 비영리 변경금지

티스토리툴바