1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
\documentclass{beamer}
\usepackage{pythonhighlight}
\hypersetup{colorlinks=true}
% https://arxiv.org/abs/2212.09410
% https://arxiv.org/abs/2309.10668
% https://github.com/Futrell/ziplm
% https://bellard.org/nncp/nncp.pdf
% https://bellard.org/nncp/nncp_v2.1.pdf
% https://prize.hutter1.net/ (blocked by AMD 🤷)
% https://kenschutte.com/gzip-knn-paper/
% https://kenschutte.com/gzip-knn-paper2/
\title{Less is More: Parameter-Free Text Classification with Gzip}
\author{Anthony Wang}
\begin{document}
\frame{\titlepage}
\begin{frame}
\frametitle{Task: text classification}
\begin{itemize}
\item Given some categories, classify strings into the categories
\item Example from AG News dataset:
\begin{itemize}
\item 4 categories: World, Sports, Business, Sci/Tech
\item Example string: "AMD Will Have An Edge Over Intel Through 2005. Piper Jaffray said Advanced Micro Devices (nyse: AMD - news - people ) should have an edge over Intel (nasdaq: INTC - news - people ) quot;throughout 2005 quot; but resumed coverage of both companies at quot;market perform quot; and both at price targets of \$25."
\end{itemize}
\item Usually solved using neural networks, i.e. BERT
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{gzip}
\begin{itemize}
\item Compression program using LZ77 and Huffman coding
\item Pretty fast and used everywhere
\item Doesn't require giant GPUs
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Intuition}
\begin{itemize}
\item Compressors are good at capturing regularity
\item Objects from the same category share more regularity than those that aren't
\item Compressor $C$, strings $x,y$ similar, different from $z$
\item Then $C(xy) < C(xz)$
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Kolmogorov complexity}
\begin{definition}
\textbf{Kolmogorov complexity} $K(x)$: length of shortest program that outputs $x$, basically an ideal compressor
\end{definition}
\begin{definition}
\textbf{Information distance} $E(x, y)$: length of shortest program that converts $x$ to $y$, equal to $K(xy)-K(x)$
\end{definition}
\end{frame}
\begin{frame}[fragile]
\frametitle{K(x) is uncomputable!}
\begin{itemize}
\item Equivalent to the halting problem
\item Analogy: "The smallest positive integer not definable in under eleven words."
\item
\begin{python}
for x in all_strings:
if K(x) > len(this_program):
print(x)
\end{python}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Instead, approximate $K$}
\begin{itemize}
\item Simply swap out $K$ for our gzip compressor $C$
\item Normalize by length
\end{itemize}
\begin{definition}
\textbf{Normalized compression distance} \[NCD(x,y) = \frac{C(xy)-\min(C(x),C(y))}{\max(C(x),C(y))}\]
\end{definition}
\end{frame}
\begin{frame}
\frametitle{Method for classification}
\begin{itemize}
\item $k$-nearest-neighbor among all strings in the training set, using $NCD$ as the distance
\item That's all!
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Code}
\begin{python}
from gzip import compress as C
import numpy as np
for (x1, _) in test_set:
Cx1 = len(C(x1.encode()))
distance_from_x1 = []
for (x2, _) in training_set:
Cx2 = len(C(x2.encode()))
x1x2 = " ".join([x1, x2])
Cx1x2 = len(C(x1x2.encode()))
ncd = (Cx1x2 - min(Cx1,Cx2)) / max(Cx1, Cx2)
distance_from_x1.append(ncd)
sorted_idx = np.argsort(np.array(distance_from_x1))
top_k_class = training_set[sorted_idx[:k], 1]
predict_class = max(set(top_k_class), key=top_k_class.count)
\end{python}
\end{frame}
\begin{frame}
\frametitle{Performance optimizations}
\begin{itemize}
\item Can reuse $C(x)$ when computing $C(xy)$
\item Multithreading
\item Use C instead of Python
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Results}
"Outperforms BERT"
\begin{tabular}{c|c|c}
Dataset & NNs average & gzip \\
\hline
AGNews & 0.901 & \textbf{0.937} \\
DBpedia & 0.978 & 0.970 \\
YahooAnswers & 0.726 & 0.638 \\
20News & 0.656 & \textbf{0.685} \\
Ohsumed & 0.433 & \textbf{0.521} \\
R8 & 0.903 & \textbf{0.954} \\
R52 & 0.815 & \textbf{0.896} \\
\hline
\end{tabular}
\end{frame}
\begin{frame}
\frametitle{Actually\dots}
\begin{itemize}
\item Experiments use $k=2$ with top-2 accuracy rather than randomly breaking ties!
\item Contamination between training and test sets!
\item gzip is not great for text classification, but still an interesting idea
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Connections between compression and ML}
\begin{itemize}
\item Autoencoders, dimensionality reduction
\item Compressors can generate text!
\item LLMs can do compression!
\item Both compressors and LLMs model the probability distribution of the next character given the current text
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{ziplm: text generation using gzip}
\begin{itemize}
\item Idea: generate character that makes text compress the best
\item Results with gzip: theudcanvas. ;cm,zumhmcyoetter toauuo long a one aay,;wvbu.mvns. x the dtls and enso.;k.like bla.njv
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{ziplm code}
\begin{python}
class ZipModel:
def logprobs(self, prefix="", temperature=1):
code_lengths = np.array([
len(self.compressor.compress("".join([self.training, prefix, v]).encode()))
for v in self.vocabulary
])
return scipy.special.log_softmax(-code_lengths*self.conversion*(1/temperature))
def sample(self, prefix="", temperature=1):
scores = self.logprobs(prefix, temperature=temperature)
i = np.random.choice(range(len(self.vocabulary)), p=np.exp(scores))
return self.vocabulary[i]
\end{python}
\end{frame}
\begin{frame}
\frametitle{Compression using LLMs}
\begin{itemize}
\item Idea: LLM generates list of candidate tokens, store the index of the token that the text uses
\item Very predictable text (i.e. digits of $\pi$) turn into 11111111111111111
\item Then run that through gzip
\item Amazing compression ratio, but slow
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{References}
\begin{itemize}
\item \href{https://arxiv.org/abs/2212.09410}{Less is More: Parameter-Free Text Classification with Gzip}
\item \href{https://kenschutte.com/gzip-knn-paper/}{Bad numbers in the "gzip beats BERT" paper?}
\item \href{https://github.com/Futrell/ziplm}{ziplm GitHub}
\item \href{https://bellard.org/nncp/nncp.pdf}{Lossless Data Compression with Neural Networks}
\item \href{https://arxiv.org/abs/2309.10668}{Language Modeling Is Compression}
\end{itemize}
\end{frame}
\end{document}
|
