2
$\begingroup$

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?

E.g. linear search problem. We have an ordered set of incomparable elements (no < and >, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds "not contains" (for one message 00000...0 ) and "contains" (all other messages). For uniform probability of being equal A for each position, entropy of responses equals: $$H=-\frac{1}{N+1}\cdot \log_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log_2\left(\frac{N}{N+1}\right)$$ $H$ goes to zero quickly:

H vs N plot

We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm!

But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}>1$ steps, and all improved techniques require comparability (e.g. binary search).

This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).

But then what is the link between both? Is there any relationship between the number of steps for the abstract "best code" and the entropy of message?

$\endgroup$
  • 1
    $\begingroup$ What problem is an "algorithm for classification of messages" supposed to solve? $\hspace{1.54 in}$ $\endgroup$ – user12859 Aug 14 '14 at 18:32
  • $\begingroup$ It has to answer "contains" or "does not contain", for given message (e.g. 0000 "does not contain", 0010 "contains"), it's just a linear search. $\endgroup$ – Евгения Карпова Aug 14 '14 at 18:49
1
$\begingroup$

I believe you are looking for algorithmic information theory. This defines the information contained in a string as proportional to the size of the smallest program that produces that string. The metric is called Kolmogorov (Колмогоров) complexity.

The problem with normal Shannon entropy, is that it is defined relative to your assumed model of the producer of the information stream. Shannon entropy really only deals with models that produce infinite and stationary random streams. When you know that the producer is deterministic then the Shannon entropy of the stream is 0 (even though you don't know the algorithm of the producer.) You can often model a deterministic stream as some kind of Markov process, but there will always be a Markov process with more states that models the deterministic stream and in which the entropy is smaller.

$\endgroup$

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.