Cross-Entropy and KL Divergence
eli.thegreenplace.net
eli.thegreenplace.net
"The mean number of bits to encode a member of P, assuming an optimal code."
And the KL divergence KL(P,Q) is probably best thought of as:
"The mean number of WASTED bits if you encode members of P assuming that they had come from Q."
https://mathoverflow.net/questions/210469/kullback-leibler-v...
Entropy, in some sense would seem to measure "complexity", but it's more accurately related as "surprise" I think.
It's useful but limited (for example, you can measure the "entropy" present in a string -- of keystrokes, or text -- and determine how likely it is that it's "coherent" or "intelligent" but this is fuzzy, i.e., "too much" entropy, and you are at "randomness", too little and you are at "banality"). It seems like a more precise (but still 0 - 1 bounded) metric would be possible to measure "order" or "organization". Entropy fails at this: 0 entropy does not equal "total order". Just "total boringness" (heh :))
I considered something related to some archetypal canonical compression scheme (like LZ), but didn't flesh it out. Considering again now, what about the "self similarity" of the dictionary, combined with the diversity of the dictionary?
It's more of a "two-axis" metric but surely we can find a way to corral it into 0..1.
Very self-similar, and rather diverse? Highly organized.
Low self-similarity, and highly diverse? High entropy / highly disorganized.
Low self-similarity, and low diversity? Low entropy / high banality. I.e., simplicity heh :)
High self-similarity, low diversity - organized, but "less organized" than something with more diversity.
I don't think this is quite there yet, but there's intuitive sync with this.
Any takers???? :)
[0] https://arxiv.org/pdf/2201.07979#subsection.5.1.2
[1] https://case.edu/artsci/math/mwmeckes/publications.html
[2] 'thisness' - in the sense that, the entropy quantifies the bits needed to pick some named option from more options
Edit: this is not to say that there couldn't be a practical measure of organization for specific examples/types/subsets of sequences. The halting problem doesn't prevent us from analyzing program "correctness" in specific formal systems. It just prevents us from having universal ability to fully determine the answer for a generic example.
I'm not an expert, but let me brainstorm a bit here. Something closer to the specific correlation might be what you want? In vague terms it would measure how much the various bytes of a file are related to each other, by considering how much more likely they are to be given values taken together vs considering each byte individually.
But once again, having extremely high specific correlation might indicate a trival low-complexity example? I'd have to play around with it some more to get a good intuition for how it behaves.
Edit: It seems like this might also be very sensitive to parametrization. The specific correlation in terms of byte values would not be much more useful than the information content, because the marginal distributions aren't very interesting (eg over all files, how likely is byte #57 to be 0xf3 or whatever). It would be a better measure with more meaningful variables, or even something like a markov chain where you consider many short substrings.
Anyway, specific correlation (like information) measures a specific file. The expected specific correlation over all possible files gives the total correlation, which (like entropy) measures the whole distribution. Total correlation is also the KL divergence between the joint distribution and the product of the marginal distributions! Total correlation is also the same thing as mutual information, just generalized to more than two variables. And specific correlation is the generalization of pointwise mutual information.
You're train of thought re. compressibility vs. organization is very in line with kolmogorov's.
1.https://www.taylorfrancis.com/books/mono/10.1201/97804295028... 2.https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
\[D_{KL}(P,Q)=-\sum_{j=1}^{n}\log_2 \frac{q_j}{p_j}=\sum_{j=1}^{n}\log_2 \frac{p_j}{q_j}\]
The post is just basic definitions and simple examples for cross entropy and KL divergence.
There is a section about the relation of cross entropy and maximum likelihood estimation at the end that seems not so easy to understand but implies that the limit of a estimator applied to a sample from a distribution is the KL divergence when the sample length tends to infinity.