[HN Gopher] A Parameter-Free Classification Method with Compressors
       ___________________________________________________________________
        
       A Parameter-Free Classification Method with Compressors
        
       Author : danielam
       Score  : 66 points
       Date   : 2023-07-13 11:21 UTC (11 hours ago)
        
 (HTM) web link (aclanthology.org)
 (TXT) w3m dump (aclanthology.org)
        
       | homarp wrote:
       | also at https://news.ycombinator.com/item?id=36705472
        
         | homarp wrote:
         | and https://news.ycombinator.com/item?id=36707193
        
       | awinter-py wrote:
       | david huffman puts down his eternal origami to look into the
       | camera and wink
        
       | cs702 wrote:
       | 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!
        
         | dilap wrote:
         | (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.
        
         | regularfry wrote:
         | 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.
        
       | skybrian wrote:
       | Here's the Arxiv link from December:
       | 
       | https://arxiv.org/abs/2212.09410
        
       ___________________________________________________________________
       (page generated 2023-07-13 23:02 UTC)