0
$\begingroup$

This question is based on , "A Symbolic Representation of Time Series, with Implications for Streaming Algorithms".

Let, $N = w\cdot l$ where $N$ is the number of data points in a time series composed of symbols from a finite alphabet set $\mathcal{A} = \{a_1,a_2,...,a_n\}$. For example, for $n=2$ (binary source) : A data sequence of lenght $N$ can be segmented into equal sized blocks $w_i$, $i =1,2,3$ each of lenght $l$ such as $00000, 10111, 11111$ $(w = 3, l = 5)$ .Mathematically, the source output is an unending sequence, $X_1,X_2,X_3,...$ of randomly selected symbols from a finite set. The probability of occurrence of each symbol $X_k$ is not equal and each source symbol is statistically independent from the previous outputs.

Another example can be a data set of natural language, where each letter is represneted by an integer value.

Question:

Consider, the data as a string as composed of words $w$ of length $l$. Is there a way to determine $l$ or $w$ using information theoretic concepts such as entropy?

Assumptions:

  • The probability of occurence of each symbol is not same as the other, so non-equiproable occurrence of each symbol.
  • Each source symbol is statistically independent from the previous outputs.

Solution idea:

The length $l$ of each block can be determined by the self-information of the symbols in that block. The largest length is the one that allows the entropy rate to remain invariant as $l$ is changed. If the length of the sequence is larger than $l$, then the symbolic space properties change abruptly. But I am confused what is the mathematical expression for entropy rate and entropy. The self information $$E = -\log2(p_i), \quad i=1,2,...,n$$ I can take the $l$ as the maximum self information among all distinct symbols $l = \max{E}$.

The MATLAB code is for data of length $N = 100$ and $n =4$ is $b = \{1,3,1,4,3,2,1,4,...\}$. How can I determine the block size $l$?

I am not sure if the following implementation is correct or not. What is the plot that I should do? Any other solution approach would be helpful as well.

The following code is for $4$ unique symbols having integer values $1,2,3,4$.

clear all
N= 100; %total length of the sequence
n=4; % number of unique symbols (alphabets)
b = randi([1 n],1,N); % creating the sequence
p_1 = sum(b==1)/length(b); %calculating probability 
p_2 = sum(b==2)/length(b);
p_3 = sum(b==3)/length(b);
p_4 = sum(b==4)/length(b);


p = [p_1,p_2,p_3,p_4];
H_N = -sum(p(p>0).*log2(p(p>0))) % entropyfor the whole sequence for N =100

Window = [1,2,4,6,8,10,12];  %this is the array of different block size
Base=2;

   ShEntropy = zeros(1,length(Window));
for NWindows=1:length(Window)
blk_size = Window(NWindows);
    ShEntropy(NWindows) =BlockEntropy(Series,blk_size,Base );% this is H_w
    store_entropy(NWindows,:) = [ShEntropy(NWindows),blk_size] ;
 EntropyRate(NWindows) = ShEntropy(NWindows)/blk_size ;
 store_EntropyRate(NWindows,:) = [EntropyRate(NWindows),blk_size] ;
end
temp1 = sortrows(store_entropy,1);
maxEntropy = temp1(end,1)
blksze1 = temp1(end,2)
figure(1)
subplot(1,2,1)
plot(Window(1:end), ShEntropy(1:end));
subplot(1,2,2)
temp2 = sortrows(store_EntropyRate,1);
maxEntropyRate = temp2(end,1)
blksze2 = temp2(end,2)
plot(Window(1:end),  EntropyRate(1:end));
LargestEntropy_Theory =log2(n)


 function ShEntropy =BlockEntropy(Series,Window,Base )

    n=length(Series);
    D=zeros(n,Window);  % Pre Allocate Memory
    for k=1:Window;    D(:,k)=circshift(Series,1-k);end
    D=D(1:end-Window+1,:); % Truncate Last Part
    %
    % Repace each Row with a "SYMBOL"
    % in this Case a Number ...............
    [K l]=size(D);
    for k=1:K; MyData(k)=polyval(D(k,:),Base);end
    clear D

    UniqueMyData = unique(MyData);
    nUniqueMyData = length(UniqueMyData);
    FreqMyData = zeros(nUniqueMyData,1); % Initialization
    for i = 1:nUniqueMyData
        FreqMyData(i) = ....
            sum(double(MyData == UniqueMyData(i)));
    end
    % Calculate sample class probabilities
    P = FreqMyData / sum(FreqMyData);
    % Calculate entropy in base 2
         ShEntropy= -sum(P .* log2(P)); % entropy of each block, H_n
    end
$\endgroup$
  • $\begingroup$ You want to transmit a message using symbols from the alphabet $\mathcal{A}$: can you use a source code that encodes each symbol within 1 bit of $H(X)/\log_2 M$ bits? (that's optimal by the source coding theorem). $\endgroup$ – Atul Ingle Feb 22 '17 at 21:33
  • $\begingroup$ Do you care only about source coding / data compression, or do you care about channel coding/error correction? $\endgroup$ – Atul Ingle Feb 22 '17 at 21:41
  • $\begingroup$ The assumption equi-probable occurrence of symbols is not applicable for my data set and application. So, I am not sure if the suggestion / solution in your first comment can still be applied for unequal probability of occurence of each symbol. I want to know if the determination of word length can be viewed and solved from the perspective of source coding theorem. Channel coding is not applicable. $\endgroup$ – SKM Feb 22 '17 at 21:51
  • $\begingroup$ I was thinking if this makes sense : the largest length is the one that allows the entropy rate to remain invariant as $l$ is changed. If the length of the sequence is larger than $l$ then the symbolic space properties change abruptly. But I am confused what is the mathematical expression for entropy rate and entropy. I have put up an explanation and program in another question dsp.stackexchange.com/questions/37618/… This is a lengthier version of this question asked here. $\endgroup$ – SKM Feb 22 '17 at 21:53
  • $\begingroup$ How can I send one bit based on your first comment? I want to send a collection of symbols called as words. IF the symbol set is composed of DNA sequences ${A,T,C,G}$ then sending 1 bit does not make any sense. What I would send is $A,A,T,G$ (l=4) or $A,A,T,G,C$(l=5) but I don't know how to determine $l$? $\endgroup$ – SKM Feb 22 '17 at 21:57
0
$\begingroup$

Suppose $X_1, X_2,\ldots$ is a long sequence of i.i.d. random variables each with a probability mass function $p$. By Shannon's source coding theorem, lossless compression of this sequence must require at least $H(p)$ bits per symbol (i.e. $N H(p)$ bits for the whole sequence), where $H(p)$ is the entropy defined as $\sum_{i=1}^n p_i \log \frac{1}{p_i}$ where $p_i$ is the probability of observing the symbol $a_i$ from the alphabet $\mathcal{A}$. As $N \rightarrow \infty$, no lossless compression technique can provide you better compression than $H(p)$ bits per symbol. So, as far as compressibility is concerned, there is no advantage in encoding blocks of symbols instead of each symbol individually.

Example:

If you have 4 equiprobable symbols $\mathcal{A}=\{1,2,3,4\}$, the most you can compress to is $\sum_{i=1}^4 \frac{1}{4}\log_2 4=2$ bits/symbol. Using a word length of $l>1$ will not give you more compression. For instance, if you try using $l=2$, you end up with 16 "compound" symbols $\{11, 12, 13, 14, 21, 22, \ldots, 44\}$, and it's easy to see these are all equiprobable again. So the entropy with this new symbol set is $\sum_{i=1}^{16} \frac{1}{16} \log _2 16=4$ bits per "compound" symbol, which works out to 2 bits per symbol (because each "compound" symbol is 2 symbols of the original alphabet). You can use a similar argument for any $l>1$.

For specific applications (such as DNA sequences, or letters of the English alphabet) the assumption of statistical independence usually does not hold. So it may be possible to group symbols together to get better compression than just encoding each symbol individually. For example, it would make sense to encode frequently used English words with shorter bit sequences.

As for your Matlab simulation, since you have a very short sequence of length $N=100$, you end up not hitting many of the patterns i.e. letter combinations for larger values of your block lengths. For example, a block length of $12$ corresponds to $4^{12}$ different letter combinations. You can't expect to cover them all in $N=100$ and so your estimate

P = FreqMyData / sum(FreqMyData);

behaves poorly in a statistical sense.

$\endgroup$
  • $\begingroup$ Thank you but some things are still very unclear to me. (1) say there are 4 unique symbols, then p = [p_1,p_2,p_3,p_4]; H_N = -sum(p(p>0).*log2(p(p>0))) = 1.9995 bits per symbol N =100 and the blok lengths to be considered is [2,3,4]. Then, can you please say how this would allow to determine the block size? 100*1.999 would be the total but I want to know which word length to select? would it be 2 or 3 or 4? any other example will also work. $\endgroup$ – SKM Feb 27 '17 at 22:17
  • $\begingroup$ Are you interested in optimizing this for the specific case of $N=100$? Information theoretic results are usually asymptotic; as $N \rightarrow \infty$, it does not matter what word length you select. You can just use $l=1$ and use a compression scheme like Huffman coding that brings you arbitrarily close to $H(p)$ bits per symbol. $\endgroup$ – Atul Ingle Feb 27 '17 at 22:25
  • $\begingroup$ No, I don't want to optimize to N=100. In my code, I am trying to find what length $l<N$ should be selected to be compressed. If the entropy of the symbols in the entire sequence is $H_N$ then theory says that I need $N*H_N$ bits. Can I use this result to find $l$ that is of shorter length?If the symbols are not correlated then certainly I can make words of shorte length from the whole sequence. Consider the data : [1,2,3,1,3,2,2,3] from a finite alphabet set of symbols $\{1,2,3,4\}$. $\endgroup$ – SKM Feb 28 '17 at 1:47
  • $\begingroup$ Let entropy = log_2(4) = 2 assuming equiprobability. Now, I can select the word length as the one which gives me the entropy close to the theoretical (value 2). So, I check which block length $l=2,3,4$ gives entropy close to theoretical value. Let's say $l=3$ gives entropy close to theoretical. Then, I transmit only 3 symbols at a time. This is my intension. Does it make any sense? $\endgroup$ – SKM Feb 28 '17 at 1:47
  • $\begingroup$ If you have 4 equiprobable symbols, the most you can compress to is 2 bits/symbol. Using a word length of $l>1$ will not give you more compression. For instance, if you try using $l=2$, you end up with 16 "compound" symbols $\{11, 12, 13, 14, 21, 22, \ldots, 44\}$, and it's easy to see these are all equiprobable again. So the entropy with this new symbol set is $\sum_{i=1}^{16} \frac{1}{16} \log _2 16=4$ bits per "compound" symbol, which works out to 2 bits per symbol (because each "compound" symbol is 2 symbols of the original alphabet). You can use a similar argument for any $l>1$. $\endgroup$ – Atul Ingle Feb 28 '17 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.