Information Entropy

APAM 1601y
Columbia University

Introduction

This notebook introduces "information entropy" as a measure of information content. Entropy is a concept first developed for statistical physics. It is a measure of the disorder of a system. When dealing with digital data, the entropy measures the disorder (or complexity) of the data. When the entropy is small, the data is not disordered, and only a few digital values exist within the entire data set. For example, if you had 1000 data points with values all equal to 1, then the information entropy would be exactly zero. The data is not at all disordered, and (theoretically) you could represent the information contained within this data set by one bit. When the entropy is large, the data is very disordered, and many digital values exist in the data set.

Claude Shannon (1916-2001)

Claude Shannon was the American engineer now known as "the father of Information Theory". In his famous 1948 paper (published in the Bell System Technical Journal), Shannon defined "information entropy" as a measure of the information content of a message. In essense, the information entropy measures the absolute smallest data record required to represent the message without loss.

Claude Shannon also coined the word "bit". According to Shannon's biography in Wikipedia, Shannon is considered one of the greatest scientists in the 20th century. His colleague at AT&T Bell Labs wrote in his obituary, "He's one of the great men of the century. Without him, none of the things we know today would exist. The whole digital revolution started with him."

Review : Physical Entropy (and Random Walkers)

The concept of entropy was developed by the German physicist Rudolf Clausius in 1865. He explained that physical processes always increase the disorder of the system (and of the universe.) The increase in entropy sets the direction of time and defines the second law of thermodynamics.

Entropy is defined as a measure of the disorder of the distribution of physical objects. 
For random walkers, it is defined as S(t) = – ∫P(x,t)  Log[P(x,t)]dx, where P(x,t) is the probability of a walker being at cell x at time t. 
Initially, all of the walkers are located at x = 0 with probability of 100%, The entropy is zero. As the probability become more uniform in x, then the entropy will increase. According to the ergodic hypothesis, all of the available states of a system in equilibrium will be occupied with equal probability. For our random walkers, x can range from -∞ to +∞ with equal probability as t -> ∞. Therefore, the way we will calculate entropy below is only valid for a limited time when there are enough walkers within each cell in order to accurately estimate the probability as the ratio, P(x,t) ≈ (# of walkers within grid box x)/(total number of walkers).

1000 Random Walkers

s[]:=2 RandomInteger[{0,1}]-1;
walk1D[n_] := NestList[(# + s[])&, 0, n];

nWalkers = 1000;
walkList = Table[walk1D[500],{nWalkers}]; (* Data record of 1000 walkers taking 500 steps. *)

pos[n_] := walkList[[All, n+1]] (* walker locations after n steps *)

pos[100] // Shallow

Manipulate[ListPlot[pos[n], PlotRange -> {-50, 50}, AxesLabel -> {"walker", "x/Δx, n= " <> ToString[n]}], {n, 0, 500}]

pos[3] // Shallow

?Tally

Tally[pos[3]]

Reverse[Tally[pos[3]],2]

First[Transpose[Reverse[Tally[pos[3]],2]]]
First[Transpose[Reverse[Tally[pos[3]],2]]]/nWalkers // N (* Probability *)

(-Plus@@N[#1 Log[#1]]&) [%]

physEntropy[l_List] := (-Plus@@N[#1 Log[#1]]&) [First[Transpose[Reverse[Tally[l],2]]]/Length[l] ]

physEntropy[pos[3]]

pEntropyTime = Table[physEntropy[pos[n]], {n, 0, 500}];

ListPlot[pEntropyTime,AxesLabel->{"n","Entropy[n], "<>ToString[nWalkers]<>" Walkers"},Joined->True,PlotRange->{0,4}]

Defining Information Entropy

The Mathematica function for information entropy is written as

iEntropy[list_List]:=(-Plus@@(#1 Log[2,#1])&)[((First[Transpose[Reverse[Sort[Tally[list]],2]]])/(Length[list]))]

This function computes the sum of the logs of the "probability" of each value in the data.

For example, a simple list with high entropy (and requiring at least 100 bits of data) is

i1=RandomInteger[{1,10},30]

Step 1: Sorting values into bins…

Reverse[Tally[i1],2]
Reverse[Sort[Tally[i1]],2]

Step 2: Computing the probability of each value…

First[Transpose[Reverse[Sort[Tally[i1]],2]]]
First[Transpose[Reverse[Sort[Tally[i1]],2]]]/Length[i1]

(#1 Log[2,#1])&[First[Transpose[Reverse[Sort[Tally[i1]],2]]]/Length[i1]]

Step 3: Adding the weighted probabilities, in analogy with physical entropy,…

Print["Entropy = ",iEntropy[i1], "; Bits Required = ", iEntropy[i1] Length[i1]];

For example, a different list with lower entropy  (and requiring at least 30 bits of data) is

i2 = Table[If[i<15,1, 2], {i, 1, 30}]

Reverse[Sort[Tally[i2]],2]

Print["Entropy = ",iEntropy[i2], "; Bits Required = ", iEntropy[i2] Length[i2]//N];

Since version 7, information Entropy[ ...] is built into Mathematica...

?Entropy

Print["Entropy = ",iEntropy[i2], "; or ", Entropy[2,i2], ", ", N[Entropy[2,i2]]];

As the data becomes more orderly, the information entropy decreases. Fewer bits are required to represent the data.
In other words: Many data bits do not contain much information. They represent data "structure" not content.

For multiple-dimensional data, your must first Flatten[…] the data list before using iEntropy[…]. This converts the multiple-dimensional data to a one-dimensional list.

i3 = Table[1, {i, 1, 30}]

Print["Entropy = ",iEntropy[i3], "; or ", Entropy[i3], ", ", N[Entropy[i3]]];

Quantization: Real versus Integer Data Types

You should be very aware of the difference between Real and Integer numbers. The iEntropy[…] function works with quantized real numbers as well as integers. However, once you operate on Real data, this data (usually) becomes not quantized. The information entropy will grow considerably. Therefore, in examining Real data, you must first quantize your data before you measure the information content with iEntropy[…].

i1Real=Table[x (1 - x), {x, 0.0, 1.0, 0.02}]
ListPlot[%]

Print["Entropy = ",iEntropy[i1Real], "; Bits Required = ", iEntropy[i1Real] Length[i1Real]];

i1RealQuantized = Floor[10 i1Real]
ListPlot[%]

Print["Entropy = ",iEntropy[i1RealQuantized], "; Bits Required = ", iEntropy[i1RealQuantized] Length[i1RealQuantized]];

i1RealQuantized = Floor[50 i1Real]
ListPlot[%]

Print["Entropy = ",iEntropy[i1RealQuantized], "; Bits Required = ", iEntropy[i1RealQuantized] Length[i1RealQuantized]];

Built - In Entropy

Version 7 and higher of Mathematica contains a built-in Entropy function:

?Entropy

iEntropy[i1]
Entropy[2,i1] // N

Examples

iExample = Table[Floor[50 Sin[x]/x], {x, 0.01, 10.0, 0.01}];
Print["Entropy = ",N[Entropy[2,iExample]], "; Bits Required = ", N[Entropy[2,iExample]] Length[iExample]];
ListPlot[iExample]

ByteCount[iExample] 8

?Compress

Compress[iExample] // Short

ByteCount[Compress[iExample]] 8

iExample = Table[Floor[50 Sin[x]/x], {x, 0.01, 10.0, 0.1}];
Print["Entropy = ",N[Entropy[2,iExample]], "; Bits Required = ", N[Entropy[2,iExample]] Length[iExample]];
ListPlot[iExample]

Print["Mathematica BitCount = ",ByteCount[iExample] 8, "; Bits Compressed = ", ByteCount[Compress[iExample]] 8];

iExample = Table[Floor[5 Sin[x]/x], {x, 0.01, 10.0, 0.1}];
Print["Entropy = ",N[Entropy[2,iExample]], "; Bits Required = ", N[Entropy[2,iExample]] Length[iExample]];
ListPlot[iExample]

Print["Mathematica BitCount = ",ByteCount[iExample] 8, "; Bits Compressed = ", ByteCount[Compress[iExample]] 8];

iExample = Table[Floor[2 Sin[x]/x], {x, 0.01, 10.0, 0.1}];
Print["Entropy = ",N[Entropy[2,iExample]], "; Bits Required = ", N[Entropy[2,iExample]] Length[iExample]];
ListPlot[iExample]

Print["Mathematica BitCount = ",ByteCount[iExample] 8, "; Bits Compressed = ", ByteCount[Compress[iExample]] 8];

Summary

Information entropy is measure of the "complexity" or "information content" of a message. For any list of numbers (representing the data of the message), the minimum data record needed to represent the message is the (length of the data record) × (the information entropy).