3 ms·

A Parameter-Free Classification Method with Compressors

83 points by danielam 3y ago

cs702 3y ago
This is clever -- and useful in many settings that preclude the use of a deep neural network for classification. Intuitively, the key idea is that if you have two documents, say, x1 and x2, and a target document y, if x1's statistical regularities are more similar to y's than to x2's, then len(compress(x1+y)) - len(compress(y)) < len(compress(x2+y)) - len(compress(y)), where "+" means concatenation and "compress" is a compression program like gzip. len(compress(x1+y)) - len(compress(y)) is, quite literally, the number of additional bytes we need to compress the statistical regularities in x1 given the statistical regularities in y. The more similar the statistical regularities between x1 and y, the fewer bytes we need to compress them together. The authors use kNN using a distance function called normalized compression distance (NCD), based on the above idea. Remarkably, this simple, intuitive method outperforms BERT on a variety of zero-shot classification tasks!
- regularfry 3y ago
  Related, there's also the Normalised Google Distance (how many results you get searching for X, Y, and X+Y, basically). I don't know if that still works. These techniques have been around for a long time, in the scale of these things.
- dilap 3y ago
  (i did not read the original paper but...) i think you want to subtract len(compress(x1)) and len(compress(x2)) on the lhs/rhs, instead of len(compress(y)) -- we care about the incremental complexity of adding y on top of x1 or x2, ignoring the base complexity of x1/x2.
  - cs702 3y ago
    There's a typo in my comment. Instead of "than to x2's", I actually mean to write "than X2's". Sorry about that!
awinter-py 3y ago
david huffman puts down his eternal origami to look into the camera and wink
skybrian 3y ago
Here's the Arxiv link from December: https://arxiv.org/abs/2212.09410 https://arxiv.org/abs/2212.09410
homarp 3y ago
also at https://news.ycombinator.com/item?id=36705472 https://news.ycombinator.com/item?id=36705472
- homarp 3y ago
  and https://news.ycombinator.com/item?id=36707193 https://news.ycombinator.com/item?id=36707193

83 points by danielam 3y ago

This is clever -- and useful in many settings that preclude the use of a deep neural network for classification. Intuitively, the key idea is that if you have two documents, say, x1 and x2, and a target document y, if x1's statistical regularities are more similar to y's than to x2's, then len(compress(x1+y)) - len(compress(y)) < len(compress(x2+y)) - len(compress(y)), where "+" means concatenation and "compress" is a compression program like gzip. len(compress(x1+y)) - len(compress(y)) is, quite literally, the number of additional bytes we need to compress the statistical regularities in x1 given the statistical regularities in y. The more similar the statistical regularities between x1 and y, the fewer bytes we need to compress them together. The authors use kNN using a distance function called normalized compression distance (NCD), based on the above idea. Remarkably, this simple, intuitive method outperforms BERT on a variety of zero-shot classification tasks!

regularfry 3y ago
Related, there's also the Normalised Google Distance (how many results you get searching for X, Y, and X+Y, basically). I don't know if that still works. These techniques have been around for a long time, in the scale of these things.
dilap 3y ago
(i did not read the original paper but...) i think you want to subtract len(compress(x1)) and len(compress(x2)) on the lhs/rhs, instead of len(compress(y)) -- we care about the incremental complexity of adding y on top of x1 or x2, ignoring the base complexity of x1/x2.
- cs702 3y ago
  There's a typo in my comment. Instead of "than to x2's", I actually mean to write "than X2's". Sorry about that!

awinter-py 3y ago

david huffman puts down his eternal origami to look into the camera and wink

skybrian 3y ago

Here's the Arxiv link from December: https://arxiv.org/abs/2212.09410 https://arxiv.org/abs/2212.09410

homarp 3y ago

also at https://news.ycombinator.com/item?id=36705472 https://news.ycombinator.com/item?id=36705472

homarp 3y ago
and https://news.ycombinator.com/item?id=36707193 https://news.ycombinator.com/item?id=36707193