Skip to content
The methodOpen data
Back to the collection

Clustering by compression

Rudi Cilibrasi, Paul Vitanyi

2003 · arXiv

Statistics & probabilityBiology & medicineAlgorithms
Read the paper
HN score
0
Mentions
5
Readers
5
Months
5
What’s in a score?

From the abstract

We present a new method for clustering based on compression. The method doesn't use subject-specific features or background knowledge, and works as follows: First, we determine a universal similarity distance, the normalized compression distance or NCD, computed from the lengths of compressed data files (singly and in pairwise concatenation). Second, we apply a hierarchical clustering method. The NCD is universal in that it is not restricted to a specific application area, and works across application area boundaries. A theoretical precursor, the normalized information distance, co-developed by one of the authors, is provably optimal but uses the non-computable notion of Kolmogorov complexity. We propose precise notions of similarity metric, normal compressor, and show that the NCD based on a normal compressor is a similarity metric that approximates universality. To extract a hierarchy of clusters from the distance matrix, we determine a dendrogram (binary tree) by a new quartet method and a fast heuristic to implement it. The method is implemented and available as public software, and is robust under choice of different compressors. To substantiate our claims of universality and robustness, we report evidence of successful application in areas as diverse as genomics, virology, languages, literature, music, handwritten digits, astronomy, and combinations of objects from completely different domains, using statistical, dictionary, and block sorting compressors. In genomics we presented new evidence for major questions in Mammalian evolution, based on whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta hypothesis against the Theria hypothesis.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

5 selected excerpts · 5 total mentions

Kim_Bruning
Neutral mention · rule
Thank you for talking with me! I do realize the benefits of the 'compression' model of ML. Sometimes you can even use compression directly, like here: https://arxiv.org/abs/cs/0312044 . I suppose you're right that you only need a few substantively similar outputs to potentially get sued already. (depending on who's scrutinizing you). While talking with you, it occurred to me that so far we've ignored the output set o, which is the set of all images output by -say- stable diffusion. n can then be defined as n = m ∩ o . And we know m is much larger than n, and o is theoretically practically infinite [1] (you can generate as many unique images as you like) , so o >> m >> n .…
Read the full comment
[2] Really already at this point I think calling SD a compression algorithm might be just a little odd. It doesn't look like the goal is compression at all. Especially when the authors seem to treat n like a bug ('overfit'), and keep trying to shrink it. That's before looking back at the "compression ratio" and "loss ratio" of this algorithm, so maybe in future I can save myself some maths. It's an interesting approach to the argument I might try more in future. (Thank you for helping me to think in this direction) * I think in the case of the Getty lawsuit they might have a bit of a point, if the model might have been overfitted on some of their images. Though I wonder if in some cases the model merely added Getty watermarks to novel images. I'm pretty sure that will have had something to do with setting Getty off. * I am deeply suspicious of the NYT case. There's a large chunk of examples where they used ChatGPT to browse their own website. This makes me wonder if the rest of the examples are only slightly more subtle. IIRC I couldn't replicate them trivially. (YMMV, we can revisit if you're really interested) [1] However, in practice there appear to be limits to floating point precision. [2] I'm using >> as "much greater than"
Original comment Judge dismisses DMCA copyright claim in GitHub Copilot suit
nextos
Neutral mention · rule
Something important to note is that the authors use normalized compression distance (NCD). NCD is a way to approximate Kolmogorov complexity. This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons. [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
Original comment Gzip and KNN Outperforms Transformers on Text Classification
sischoel
Neutral mention · rule
This article is surprisingly short on actual applications. For some interesting applications one might look at the the Wikipedia article for the normalized compression distance: https://en.wikipedia.org/wiki/Normalized_compression_distanc... This paper here shows some interesting applications - it is not the first one, but the first non-paywalled one that I found: https://arxiv.org/pdf/cs/0312044.pdf There is also a book by Paul Vitanyi - it has been a while since I looked at it, but if I remember correctly it also discusses some of these applications: https://www.amazon.com/Introduction-Kolmogorov-Complexity-Ap...
Original comment Kolmogorov Complexity: Extensions and Applications
bediger4000
Neutral mention · rule
The author of the article would have been wise to include this information. I did find "Clustering by Compression", https://arxiv.org/abs/cs/0312044 The emphasis in this paper was not on "efficiency", but rather on phylogenetic grouping. The authors used the "Universal Declaration of Human Rights", which apparently has 52 translations as the subject text. See Fig 13 and section 5.2 for details. Instead of just compressing and normalizing, they developed a normalized compression distance, which involves concatenating two texts, compression, and division by the largest of the two texts, as compressed alone. I think that using the same encoding of all the languages and some kind of normalizing would wash the results of differences due to encodings.
Original comment The World's Most Efficient Languages (2016)
jkabrg
Neutral mention · rule
I guess it provides an objective definition of when something is simple or complicated. This could have applications in statistics or machine learning, where "simpler" hypotheses could be less likely to overfit. There are computable measures of "simplicity" (unlike Kolmogorov complexity) based on compression algorithms or computation time (Levin complexity). There are also apparently connections to statistical mechanics, but I haven't looked into it and I don't know if it's useful. See this paper on how to cluster using compression: https://arxiv.org/pdf/cs/0312044.pdf
Original comment Functional Bits: Lambda-calculus based algorithmic information theory [pdf]

Keep following the thread.

More in Statistics & probability

More from the same topics.