<p>Basically, almost any machine learning or compression method is an approximation to Kolmogorov complexity:</p>
<ul>
<li>If you have any computable probability distribution which assigns your data probability <span class="math-container">$p(x)$</span> then, by the Kraft inequality, you have a compressor which compresses your data in <span class="math-container">$- \log p(x)$</span> bits.</li>
<li>If you have any computable compressor C which compresses your data to <span class="math-container">$n$</span> bits, then you have <span class="math-container">$K(x) \leq n + s_C$</span>, where <span class="math-container">$s_C$</span> depends on your compressor, but not on <span class="math-container">$x$</span> (it's basically the number of bits you need to describe C to your universal Turing machine).</li>
</ul>
<p>Thus, you can just look for patterns with any compressor or probability distribution and the better they compress your data, the better your upper bound for K(x). Just make sure to add the size of the compressor itself to the size of the compressed data to get the estimate.</p>
<p>Better yet, write a self-contained program that outputs your data. The smaller you can make that program, the smaller <span class="math-container">$K(x)$</span> is.</p>
<p>Of course, bounding from above may not be enough. What if your estimate is quite big, what's the probability that <span class="math-container">$K(x)$</span> is actually very small? For this you need to make some assumptions, on your data: fix a class of probability distributions (like probabilistic automata), and use a Bayesian mixture over those distributions to compress your data. If your data was actually produced by a probabilistic automaton, the probability that <span class="math-container">$K$</span> is substantially smaller than your estimate vanishes exponentially.</p>
<p>You can also use a time bound to define your model class, which leads you to Suresh's answer. Basically, if you assume that your datasource has polynomial time complexity, and you try all polynomial Turing machines to compress it, you can be pretty sure that you've accurately estimated the Kolmogorov complexity. This may still not be that practical, but for lower time bounds, you may be able to compute the full Bayesian mixture, of a good approximation to it.</p>
<p>For technical details see <a href="https://www.researchgate.net/publication/266795088_A_safe_approximation_for_Kolmogorov_complexity" rel="nofollow noreferrer">this paper</a>. Disclaimer: I'm one of the authors.</p>
<p>Finally, you should note that <span class="math-container">$K(x)$</span> is only meaningful in an asymptotic sense. For any one dataset the value of <span class="math-container">$K(x)$</span> can change by a constant from one computer to the next, and that constant can be as large as you like. So take approximations of this kind with a grain of salt.</p>

CC BY-SA 4.0
2015-04-16T14:08:08.947Z
2021-05-19T21:28:15.030Z
2021-05-19T21:28:15.030Z
Peter
<p>I thought more about my question, and arrived at possible solution. It has two limitations, it is defined only on strings of length $n = 2^m$ (although I will discuss this more) and it doesn't talk about universal Turing machines, instead following a <a href="https://cstheory.stackexchange.com/q/7247/1037">previous question</a> and using an alternative model of computation.</p>

<hr>

<p>Basically, we can interpret a string $x$ with $|x| = 2^m$ as a function $f_x: \{0,1\}^m \rightarrow \{0,1\}$. Then our complexity measure $K'(x)$ is the size (number of edges) of the unique reduced ordered binary decision diagram (ROBDD; with the standard ordering fixed) representing $f_x$. This satisfies condition [1]. Also, since ROBDDs can be computed in time polynomial in $2^m$, we have an efficient measure.</p>

<p>To satisfy condition [2], we have to modify standard BDDs by allowing an special type on node. Usually nodes are labeled by indexes $i \in \{1,...,m\}$, we will include a special oracle node. For $K(x|y)$ where $|y| = 2^m$ we will allow special nodes in the BDDs as follows:</p>

<p>If we are running a BDD on input $a$ ($|a| = m$) then a normal node labeled by $i$ simply send us down the edge labeled $a_i$. An oracle node will instead send us down an edge labeled $f_y(a)$. Thus, $K'(x|x) = 2$ and with high probability $K'(x|y) \approx K(x)$ for a $y$ picked uniformly at random. </p>

<p>[Note: it is not clear if conditional complexity can still be efficiently computed :(]</p>

<p>Conviniently, we also have sub-additivity since to build an OBDD for $x.y$ we can have a query for the first bit and on $0$ go to the ROBDD for $x$ and on $1$ to the ROBDD for $y$. Thus, we have $K'(x.y) \leq K'(x) + K'(y)$.</p>

<hr>

<p>At the potential cost of sub-additivity we could define $K'(x)$ for any length $x$ by just taking power-of-two chunks and adding their complexities together. For instance for $|x| = 2^m$ and $|y| = 2^l$ with $m &gt; l$ we can define $K'(x.y) = K'(x) + K'(y)$.</p>

<p>There are also some unfortunately limitations with my approach. We can't go much beyond OBDDs, if we consider minimal decision trees or just BDDs then we will snag on the intractability issues addressed in <a href="https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees/7963#7963">this answer</a>. Even for variable ordering of OBDDs there seems to be <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=537122" rel="nofollow noreferrer">intractability results</a>. So it seems OBDDs is the limit of this not-so-similar-to-standard-Kolmogorov-complexity approach.</p>

CC BY-SA 3.0
2011-09-30T09:47:36.203Z
2011-09-30T09:47:36.203Z
2017-04-13T12:32:28.117Z
Artem Kaznatcheev
<p>I'm not an expert, but if you need a <em>practical</em> complexity measure for strings, you can take a look to the Titchener <strong>T-complexity</strong> measure.</p>

<p>See <a href="http://tcode.auckland.ac.nz/~mark/T-codes%3a%20Intro.html" rel="nofollow">Titchener's web site</a> for a quick introduction; his <a href="http://tcode.auckland.ac.nz/~mark/Papers.html" rel="nofollow">papers can be downloaded in pdf format</a>.</p>

<p><em>Abstract</em> - A new measure of string complexity for finite strings is presented based on a specific recursive hierarchical string <em>production process</em>. From the maximal bound we deduce a relationship between complexity and  total information content. <a href="http://tcode.auckland.ac.nz/~mark/Papers/00708931isit1998.pdf" rel="nofollow">..full article...</a></p>

<p>I found some papers on practical implementations, too (see for example "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.7394&amp;rep=rep1&amp;type=pdf" rel="nofollow">A Fast T-decomposition algorithm</a>")</p>

CC BY-SA 3.0
2011-09-29T22:16:10.603Z
2011-09-29T22:16:10.603Z
Marzio De Biasi
<p>You're looking for resource bounded Kolmogorov complexity. You can start with <a href="http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf" rel="nofollow">this paper</a> and branch out. </p>

CC BY-SA 3.0
2011-09-28T04:00:54.833Z
thanks for the link to the paper, I mention resource bounded complexity in the question, but there interest is really in measures that are efficiently computable. It seems like the paper shows that the 'random strings' for these models corresponds to sets of high complexity. This suggests that deciding the complexity of a string in these models is not efficiently computable, no?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-28T03:41:22.210Z
2011-09-28T03:41:22.210Z
Suresh Venkat
<p>Gzip.  Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. <a href="http://homepages.cwi.nl/~paulv/papers/cluster.pdf">Clustering by Compression</a></p>

CC BY-SA 3.0
2011-09-29T23:43:20.903Z
how do they define conditional complexity?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-30T14:34:18.640Z
Let A and B be two documents, and AB be the two concatenated. They look at the ratio of SIZE(gzip(A)+gzip(B)) to SIZE(gzip(AB)).
Chad Brewbaker
CC BY-SA 3.0
2015-04-17T20:52:04.413Z
One should be aware that there are downsides to using gzip (and similar) to approximate Kolmogorov complexity: http://bactra.org/notebooks/cep-gzip.html. That doesn't say it's not useful for clustering real-life data sets, but it does say that its utility for real-life data sets tells us something about how those data sets are different from, say, the output of a pseudorandom number generator...
Joshua Grochow
CC BY-SA 3.0
2011-09-29T20:43:04.257Z
2011-09-29T20:43:04.257Z
Chad Brewbaker
<p>Kolmogorov prefix complexity (i.e. <span class="math-container">$K(x)$</span> is the size of minimal self-delimiting program that outputs <span class="math-container">$x$</span>) has several nice features:</p>
<ol>
<li>It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.</li>
<li>It allows us to define conditional complexity <span class="math-container">$K(x|y)$</span>, or even better <span class="math-container">$K(x|O)$</span> for some oracle <span class="math-container">$O$</span>.</li>
<li>It is sub-additive <span class="math-container">$K(x,y) \leq K(x) + K(y)$</span>.</li>
</ol>
<p>However it has an awful downside: returning <span class="math-container">$K(x)$</span> given <span class="math-container">$x$</span> is undecidable.</p>
<p>I have wondered if there is a variant of Kolmogorov complexity <span class="math-container">$K'(x)$</span> using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?</p>
<p>The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for <span class="math-container">$K'$</span> is preferred, so that it might be possible to prove some reasonable theorems about how drastically <span class="math-container">$K'$</span> differs from <span class="math-container">$K$</span> and on what kind of strings.</p>
<h3>Relates questions</h3>
<p><a href="https://cstheory.stackexchange.com/q/7247/1037">Kolmogorov complexity with weak description languages</a></p>
<p><a href="https://cstheory.stackexchange.com/q/4016/1037">Is there a sensible notion of an approximation algorithm for an undecidable problem?</a></p>

<it.information-theory><kolmogorov-complexity><formal-modeling>
Efficiently computable variants of Kolmogorov complexity
Artem Kaznatcheev
# Efficiently computable variants of Kolmogorov complexity

(Asked by: username_0 on 2011-09-28)

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:

1. It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
2. It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
3. It is sub-additive $K(x,y) \leq K(x) + K(y)$.

However it has an awful downside: returning $K(x)$ given $x$ is undecidable.

I have wondered if there is a variant of Kolmogorov complexity $K'(x)$ using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?

The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for $K'$ is preferred, so that it might be possible to prove some reasonable theorems about how drastically $K'$ differs from $K$ and on what kind of strings.

### Relates questions

[Kolmogorov complexity with weak description languages](https://cstheory.stackexchange.com/q/7247/1037)

[Is there a sensible notion of an approximation algorithm for an undecidable problem?](https://cstheory.stackexchange.com/q/4016/1037)

**Tags:** it.information-theory, kolmogorov-complexity, formal-modeling


---

## 5 answers

### Answer by username_4 on 2011-09-29. Score: 11 | Accepted answer

Gzip. Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. [Clustering by Compression](http://homepages.cwi.nl/~paulv/papers/cluster.pdf)

> **Comments:**
> **username_0**: how do they define conditional complexity?  
> **username_4**: Let A and B be two documents, and AB be the two concatenated. They look at the ratio of SIZE(gzip(A)+gzip(B)) to SIZE(gzip(AB)).  
> **username_5**: One should be aware that there are downsides to using gzip (and similar) to approximate Kolmogorov complexity: http://bactra.org/notebooks/cep-gzip.html. That doesn't say it's not useful for clustering real-life data sets, but it does say that its utility for real-life data sets tells us something about how those data sets are different from, say, the output of a pseudorandom number generator...  

---

### Answer by username_1 on 2015-04-16. Score: 5

Basically, almost any machine learning or compression method is an approximation to Kolmogorov complexity:

* If you have any computable probability distribution which assigns your data probability $p(x)$ then, by the Kraft inequality, you have a compressor which compresses your data in $- \log p(x)$ bits.
* If you have any computable compressor C which compresses your data to $n$ bits, then you have $K(x) \leq n + s\_C$, where $s\_C$ depends on your compressor, but not on $x$ (it's basically the number of bits you need to describe C to your universal Turing machine).

Thus, you can just look for patterns with any compressor or probability distribution and the better they compress your data, the better your upper bound for K(x). Just make sure to add the size of the compressor itself to the size of the compressed data to get the estimate.

Better yet, write a self-contained program that outputs your data. The smaller you can make that program, the smaller $K(x)$ is.

Of course, bounding from above may not be enough. What if your estimate is quite big, what's the probability that $K(x)$ is actually very small? For this you need to make some assumptions, on your data: fix a class of probability distributions (like probabilistic automata), and use a Bayesian mixture over those distributions to compress your data. If your data was actually produced by a probabilistic automaton, the probability that $K$ is substantially smaller than your estimate vanishes exponentially.

You can also use a time bound to define your model class, which leads you to Suresh's answer. Basically, if you assume that your datasource has polynomial time complexity, and you try all polynomial Turing machines to compress it, you can be pretty sure that you've accurately estimated the Kolmogorov complexity. This may still not be that practical, but for lower time bounds, you may be able to compute the full Bayesian mixture, of a good approximation to it.

For technical details see [this paper](https://www.researchgate.net/publication/266795088_A_safe_approximation_for_Kolmogorov_complexity). Disclaimer: I'm one of the authors.

Finally, you should note that $K(x)$ is only meaningful in an asymptotic sense. For any one dataset the value of $K(x)$ can change by a constant from one computer to the next, and that constant can be as large as you like. So take approximations of this kind with a grain of salt.


---

### Answer by username_0 on 2011-09-30. Score: 4

I thought more about my question, and arrived at possible solution. It has two limitations, it is defined only on strings of length $n = 2^m$ (although I will discuss this more) and it doesn't talk about universal Turing machines, instead following a [previous question](https://cstheory.stackexchange.com/q/7247/1037) and using an alternative model of computation.

---

Basically, we can interpret a string $x$ with $|x| = 2^m$ as a function $f\_x: \{0,1\}^m \rightarrow \{0,1\}$. Then our complexity measure $K'(x)$ is the size (number of edges) of the unique reduced ordered binary decision diagram (ROBDD; with the standard ordering fixed) representing $f\_x$. This satisfies condition [1]. Also, since ROBDDs can be computed in time polynomial in $2^m$, we have an efficient measure.

To satisfy condition [2], we have to modify standard BDDs by allowing an special type on node. Usually nodes are labeled by indexes $i \in \{1,...,m\}$, we will include a special oracle node. For $K(x|y)$ where $|y| = 2^m$ we will allow special nodes in the BDDs as follows:

If we are running a BDD on input $a$ ($|a| = m$) then a normal node labeled by $i$ simply send us down the edge labeled $a\_i$. An oracle node will instead send us down an edge labeled $f\_y(a)$. Thus, $K'(x|x) = 2$ and with high probability $K'(x|y) \approx K(x)$ for a $y$ picked uniformly at random.

[Note: it is not clear if conditional complexity can still be efficiently computed :(]

Conviniently, we also have sub-additivity since to build an OBDD for $x.y$ we can have a query for the first bit and on $0$ go to the ROBDD for $x$ and on $1$ to the ROBDD for $y$. Thus, we have $K'(x.y) \leq K'(x) + K'(y)$.

---

At the potential cost of sub-additivity we could define $K'(x)$ for any length $x$ by just taking power-of-two chunks and adding their complexities together. For instance for $|x| = 2^m$ and $|y| = 2^l$ with $m > l$ we can define $K'(x.y) = K'(x) + K'(y)$.

There are also some unfortunately limitations with my approach. We can't go much beyond OBDDs, if we consider minimal decision trees or just BDDs then we will snag on the intractability issues addressed in [this answer](https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees/7963#7963). Even for variable ordering of OBDDs there seems to be [intractability results](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=537122). So it seems OBDDs is the limit of this not-so-similar-to-standard-Kolmogorov-complexity approach.


---

### Answer by username_2 on 2011-09-29. Score: 2

I'm not an expert, but if you need a *practical* complexity measure for strings, you can take a look to the Titchener **T-complexity** measure.

See [Titchener's web site](http://tcode.auckland.ac.nz/~mark/T-codes%3a%20Intro.html) for a quick introduction; his [papers can be downloaded in pdf format](http://tcode.auckland.ac.nz/~mark/Papers.html).

*Abstract* - A new measure of string complexity for finite strings is presented based on a specific recursive hierarchical string *production process*. From the maximal bound we deduce a relationship between complexity and total information content. [..full article...](http://tcode.auckland.ac.nz/~mark/Papers/00708931isit1998.pdf)

I found some papers on practical implementations, too (see for example "[A Fast T-decomposition algorithm](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.7394&rep=rep1&type=pdf)")


---

### Answer by username_3 on 2011-09-28. Score: -1

You're looking for resource bounded Kolmogorov complexity. You can start with [this paper](http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf) and branch out.

> **Comments:**
> **username_0**: thanks for the link to the paper, I mention resource bounded complexity in the question, but there interest is really in measures that are efficiently computable. It seems like the paper shows that the 'random strings' for these models corresponds to sets of high complexity. This suggests that deciding the complexity of a string in these models is not efficiently computable, no?  

---

