Home › Blogs › OptimusMaplePrime's blog

Calculate the Shannon Entropy of a Matrix

Posted on 2008-05-02 10:50 By OptimusMaplePrime (Maple Rating 1 18)
Categories:

Maple includes a useful StringTools:-Entropy procedure which computes the Shannon Entropy, or Information Entropy of a string.  Wikipedia has a nice article describing the measure online at http://en.wikipedia.org/wiki/Shannon_entropy.  I wanted to compute this value over a Matrix so I wrote the following procedure.  Let me know if you have any comments or improvements on the implementation.

View 8408_ShannonEntropy.mw on MapleNet or Download 8408_ShannonEntropy.mw
View file details

Comments

acer's picture

faster, simpler?

Comment on 2008-05-07 18:12 from acer (Maple Rating 4 1007)

Does this do the same thing? It acts about 20 times faster (on my machine) for a 500x500 Matrix with random integer entries between 1 and 4.

ShannonEntropy := proc (a::Matrix)
local i, L, m, n;
  m, n := LinearAlgebra:-Dimension(a);
  L := Statistics:-Tally(ArrayTools:-Alias(a,[m*n]));
  return -add(rhs(i)*log[2](rhs(i)/(m*n)), i in L)/(m*n);
end proc:

If there's some difference in behaviour, then it could likely be easily sorted out.

acer

Much more Maple-esque.

Comment on 2008-05-07 22:08 from OptimusMaplePrime (Maple Rating 1 18)

Thanks acer.  Your version is much faster and simpler.  The use of Maple's Statistics:-Tally and ArrayTools:-Alias avoids all of the convoluted looping I was doing.  I have added a new file with your implementation.

View 8408_InformationIndices.mw on MapleNet or Download 8408_InformationIndices.mw
View file details

I have also added a test file that runs an example matrix on an expanded version of your code so that the intermediate results can be seen.

View 8408_ShannonEntropy-RegressionTest.mw on MapleNet or Download 8408_ShannonEntropy-RegressionTest.mw
View file details

Thanks, this is a great improvement.

ImageTools[Entropy]

Comment on 2008-05-07 19:24 from Joe Riel (Maple Rating 4 1065)

You could use ImageTools:-Entropy to do this computation. For example,
 

M := LinearAlgebra:-RandomMatrix(100,density=1,generator=0..1.0): 
Img := ImageTools:-Create(M):                                    
ImageTools:-Entropy(Img);                                        
                                  7.982864178

General Solution for Numeric Matrix Data

Comment on 2008-05-07 22:17 from OptimusMaplePrime (Maple Rating 1 18)

Thanks for pointing out ImageTools:-Create.  I did not realize how easily a matrix could be used with the ImageTools:-Entropy procedure.  This use can be made more general by adding a call to LinearAlgebra:-Normalize before ImageTools:-Create to account for the case when the contents of the matrix are not all between 0 and 1.0.  I tried to generalize even further to the case where the matrix contains string or heterogeneous types but I was not able to find a solution for such a matrix.  I put a longer discussion with some example data in a file to test the algorithm:

View 8408_ShannonEntropy-RegressionTest.mw on MapleNet or Download 8408_ShannonEntropy-RegressionTest.mw
View file details

I am not very familiar with all of the options for type conversion in Maple so I may have missed some easy transformations that might make ImageTools:Entropy more useful.

acer's picture

ArrayTools:-Alias

Comment on 2008-05-07 22:45 from acer (Maple Rating 4 1007)

You may be interested to learn that the ArrayTools:-Alias routine does not make a full copy of the data. What it does, instead, is provide an alternate view of the data.

Suppose for example that V is a 1-D Alias view of some M, a 2-D Matrix, where one of V or M had been created by an ArrayTools:-Alias call on the other. These two names, V and M point at the same data. Changing an element in one will show up if accessed from the other, and vice versa.

This makes Alias very popular, as it allows a no-copy bypass around difficulties where one routine produces a Matrix and another routine expects a Vector, and one wishes to pass the same data back and forth. No extra storage is used up, by the Alias call. And no extra time is taken for copying elements from one structure to another.

This may be useful, with respect to the last section in the above uploaded worksheet. The convert() calls may be avoided altogether, I suspect. A code fragment might look something like this, where b is the data Matrix,

m,n := LinearAlgebra:-Dimension(b);
d := ArrayTools:-Alias(b,[m*n]):
LinearAlgebra:-Normalize(d,inplace);
Img := ImageTools:-Create(b):
ImageTools:-Entropy(Img);

acer

Pass by Reference versus Pass by Value

Comment on 2008-05-08 12:41 from OptimusMaplePrime (Maple Rating 1 18)

Thanks for the explaination acer.  I did not realize that ArrayTools:-Alias offered so many efficiencies.  The use of Alias in this case is more efficient but since it does use the same underlying data the call to LinearAlgebra:-Normalize changes the input.  Removing the inplace option returns a vector that then needs a conversion to a matrix for input to the ImageTools:-Create procedure.  Alternatively ArrayTools:-Copy can be used to run the routine on a copy of the original matrix thus preserving the original data.

I really appreciate the advice.  I can see myself using ArrayTools:-Alias quite a bit in the future.  It is a very handy procedure.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}