2 ms·

I often wondered that entropy is often not the right measure which you want and something like what he describes as complexity is actually what you want. It's t

I often wondered that entropy is often not the right measure which you want and something like what he describes as complexity is actually what you want. It's the first time that I have heard of this concept and that it's formally defined as sophistication or logical depth. The only downside is that this is not computable. This lead me to the question, whether there is a simpler variant of complexity (with similar properties) which is computable: https://math.stackexchange.com/questions/2387690/simple-computable-approximate-complexity-sophistication-for-a-string https://math.stackexchange.com/questions/2387690/simple-comp...

jpfed 9y ago
The approach I've long thought would bear fruit turns out to be a dumbed-down version of Aaronson's. Imagine a "meta-sequence" whose elements are features of the original sequence in question, then take the entropy of the meta-sequence. Different features yield different kinds of "interestingness". For example, you could form your meta-sequence with a histogram of the original sequence. Original: A B A A B B A B Meta: 4 4 (4 As, 4 Bs) Entropy of the meta sequence is low. But instead of just looking at the values of the PMF or PDF, you might want to look at things like transition probabilities between different elements in the original sequence to capture the fact that A A A A B B B B and A B A B A B A B have more boring transition probabilities than A A B A B A B B And so on; one can imagine having an ever-more-sophisticated array of features to look for when forming the meta-sequence. But Kolmogorov complexity seems to cut more directly to the heart of the matter. If I'm specifically looking for something computationally feasible, maybe I would do a weighted sum of the entropies of k-order transition matrices, from k=1 to some limit.
pureGuano 9y ago
You may find this interesting: http://www.necsi.edu/research/multiscale/infotheory http://www.necsi.edu/research/multiscale/infotheory

jpfed 9y ago

The approach I've long thought would bear fruit turns out to be a dumbed-down version of Aaronson's. Imagine a "meta-sequence" whose elements are features of the original sequence in question, then take the entropy of the meta-sequence. Different features yield different kinds of "interestingness". For example, you could form your meta-sequence with a histogram of the original sequence. Original: A B A A B B A B Meta: 4 4 (4 As, 4 Bs) Entropy of the meta sequence is low. But instead of just looking at the values of the PMF or PDF, you might want to look at things like transition probabilities between different elements in the original sequence to capture the fact that A A A A B B B B and A B A B A B A B have more boring transition probabilities than A A B A B A B B And so on; one can imagine having an ever-more-sophisticated array of features to look for when forming the meta-sequence. But Kolmogorov complexity seems to cut more directly to the heart of the matter. If I'm specifically looking for something computationally feasible, maybe I would do a weighted sum of the entropies of k-order transition matrices, from k=1 to some limit.

pureGuano 9y ago

You may find this interesting: http://www.necsi.edu/research/multiscale/infotheory http://www.necsi.edu/research/multiscale/infotheory