原文地址：Large Language Models and Nearest Neighbors, and More，by Sebastian Raschka, on 2023-07-30
大语言模型与近邻算法
我没有跟风本周最新的技术潮流，而是想深入探讨近邻算法在大语言模型（LLM）领域一项近期且极具吸引力的应用，该应用在今年7月引发了广泛关注。
大家可能知道我偏爱简洁优雅的基准方法，但考虑到当前绝大多数研究都围绕着对本已体量庞大的大语言模型进行扩容，我觉得这个方法让人耳目一新。尽管近邻算法这类看似简单的方法，或许无法适配当前大语言模型所擅长的各类问题，但它们自有其独特的价值。这也说明，基于基础或者说“经典”的技术进行创新、做出重要贡献的机会依然大量存在。
近邻算法概览
近邻方法是数据挖掘、模式识别与机器学习领域的基础方法之一，可应用于分类、回归任务，以及推荐系统、异常检测等诸多场景。
近邻方法最基础的形式是k近邻（kNN）算法。对新样本进行分类时，kNN算法会在训练数据中找出与该样本距离最近的k个点——k是由用户选定的超参数。随后，算法会根据这k个近邻的多数投票结果对新样本进行分类：如果近邻中的多数属于某个类别，就将新样本划归为该类别，如下图所示。
k=5时的k近邻分类器示意图
值得注意的是，该算法无需训练过程，因为每次对新数据点分类时，我们只需要在训练集中找出k个最近邻即可。（缺点是每次预测都需要遍历整个训练集，当训练集规模较大时，计算成本会很高。）
要理解下面这篇论文，了解上述kNN的基础知识基本就足够了。不过如果大家想了解更多细节，我在本文末尾补充了相关信息与拓展资料，其中包括提升kNN计算效率的方法。
《低资源场景下的文本分类：一种基于压缩器的无参数分类方法》
几周前，这篇论文（https://aclanthology.org/2023.findings-acl.426/）在ACL 2023（https://2023.aclweb.org/）上引发热议时，我就在自己的社交渠道聊过相关内容——当时我正在参加SciPy 2023会议（https://www.scipy2023.scipy.org/），这篇论文也成了好几次晚宴上的讨论话题。
不过我没有把它收录进上一期的《三句话讲AI研究亮点》（https://magazine.sebastianraschka.com/p/ai-research-highlights-in-3-sentences-738），因为严格来说，这篇工作是基于2022年12月发布在arXiv上的论文（https://arxiv.org/abs/2212.0941），而那篇论文可能是更早的会议投稿版本。
闲话不多说，我们来深入看看这篇ACL论文（https://aclanthology.org/2023.findings-acl.426/）到底讲了什么。
基于gzip的文本分类
简而言之，这篇《低资源文本分类》论文提出使用gzip压缩格式与工具（https://en.wikipedia.org/wiki/Gzip）结合kNN算法来完成文本分类任务。下方带注释的图中的Python代码总结了该方法的流程：
摘自论文（https://aclanthology.org/2023.findings-acl.426/）的注释图，展示kNN+gzip方法
其中，ncd全称为归一化压缩距离（Normalized Compression Distance），是一种基于两个字符串压缩后的长度来衡量字符串间相似度的指标。计算方式是分别压缩两个独立字符串，再压缩二者拼接后的字符串，通过对比压缩后的长度得到一个分值，范围从0（字符串完全相同）到1（字符串完全不相似）。（下一节会逐步讲解其计算过程。）
出人意料的是，该方法的竞争力很强，在多个数据集上的分类性能几乎和BERT（一种编码器架构的大语言模型，相关讨论见https://magazine.sebastianraschka.com/p/understanding-encoder-and-decoder ）不相上下，如下表所示。
摘自论文（https://aclanthology.org/2023.findings-acl.426/）的注释图，展示在各文本分类数据集上的性能
而在分布外（OOD）分类与少样本场景下，这种gzip方法的表现超过了BERT以及其他所有方法，如下图所示。（这里的分布外指的是，用于BERT微调与分类的数据集所使用的语言，是BERT预训练阶段从未见过的。）
摘自论文（https://aclanthology.org/2023.findings-acl.426/）的注释图，展示在分布外数据集上的性能
注意，由于代码存在一处问题，这些数值略有偏高，我们后面会谈到这一点。首先，我们先来讲解这个方法的基本原理。
Gzip方法的工作原理是什么？
从宏观层面来看，这种gzip方法利用了压缩算法会去除冗余信息的特性。
举例来说，如果文本1和文本2内容相似，那么文本1单独压缩后的大小，与文本1和文本2拼接后压缩的大小会非常接近。再举一个更极端的例子：一段文本和自身拼接后压缩的大小，和原文本压缩后的大小相近（只会多出用于反向引用的少量固定开销）。
听起来有点复杂？我们用实际的Python代码一步步演示。假设我们有如下两段文本：
txt_1 = "hello world" txt_2 = "some text some text some text"
我们用gzip对它们进行压缩，然后输出压缩后字符串的长度：
>>> import gzip >>> len(gzip.compress(txt_1.encode())) 31 >>> len(gzip.compress(txt_2.encode())) 33
可以看到，尽管第二段原文本的长度远长于第一段，但二者压缩后的大小却差不多。这是因为压缩算法利用了txt_2中存在重复内容的特点。
现在我们把文本1和文本2拼接起来，看看压缩后的结果如何：
>>> len(gzip.compress(" ".join([txt_1, txt_2]).encode()))
43
可以看到，拼接后的文本压缩后的长度明显比两个独立文本各自压缩后的长度都要长，这符合预期，因为两段文本内容差异很大。
相反，如果把每段文本和自身拼接，压缩后的长度和原文本压缩后的长度几乎没有差别：
>>> len(gzip.compress(" ".join([txt_1, txt_1]).encode()))
34
>>> len(gzip.compress(" ".join([txt_2, txt_2]).encode()))
33
注意，文本和自身拼接是一种极端情况。该方法的核心思想是：一段文本和相似文本拼接后压缩的长度，会比它和不同文本拼接后压缩的长度更接近原文本单独压缩的长度，下图总结了这一原理：
gzip方法的原理示意图
复现Gzip方法
论文作者分享了一个实现论文实验的代码仓库（https://github.com/bazingagin/npc_gzip）。不过在本节中，我们将根据论文中的描述自己复现该方法，并将其应用于斯坦福情感分类数据集（https://ai.stanford.edu/~amaas/data/sentiment/），该数据集并未出现在原论文的研究中。
代码仓库
我把下面所有实验的代码都放在了这个仓库中：https://github.com/rasbt/nn_plus_gzip
按照我下面的划分方式，IMDB电影评论数据集包含35000条训练样本和10000条测试样本：
import pandas as pd
from local_dataset_utilities import download_dataset, load_dataset_into_to_dataframe, partition_dataset
df_train = pd.read_csv("train.csv")
df_val = pd.read_csv("val.csv")
df_test = pd.read_csv("test.csv")
（local_dataset_utilities工具代码可在此处查看：https://github.com/rasbt/nn_plus_gzip/blob/main/local_dataset_utilities.py ）
该二分类任务（预测电影评论是正面还是负面）的基准准确率（始终预测多数类）为50.06%，因为数据集的类别是均衡的：
>>> bcnt = np.bincount(df_test["label"].values)
>>> print(bcnt)
array([5006, 4994])
>>> print("Baseline accuracy:", np.max(bcnt)/ bcnt.sum())
Baseline accuracy: 0.5006
现在，基于论文中的Python代码（再次展示如下），
摘自论文（https://aclanthology.org/2023.findings-acl.426/）的注释图，展示kNN+gzip方法
我们可以这样实现gzip方法：
import gzip
import numpy as np
from tqdm import tqdm
k = 2
predicted_classes = []
for row_test in tqdm(df_test.iterrows(), total=df_test.shape[0]):
test_text = row_test[1]["text"]
test_label = row_test[1]["label"]
c_test_text = len(gzip.compress(test_text.encode()))
distance_from_test_instance = []
for row_train in df_train.iterrows():
train_text = row_train[1]["text"]
train_label = row_train[1]["label"]
c_train_text = len(gzip.compress(train_text.encode()))
train_plus_test = " ".join([test_text, train_text])
c_train_plus_test = len(gzip.compress(train_plus_test.encode()))
ncd = ( (c_train_plus_test - min(c_train_text, c_test_text))
/ max(c_test_text, c_train_text) )
distance_from_test_instance.append(ncd)
sorted_idx = np.argsort(np.array(distance_from_test_instance))
top_k_class = list(df_train.iloc[sorted_idx[:k]]["label"].values)
predicted_class = max(set(top_k_class), key=top_k_class.count)
predicted_classes.append(predicted_class)
print("Accuracy:", np.mean(np.array(predicted_classes) == df_test["label"].values))
这段代码运行了大约一天，最终准确率为70.05%（文件路径：file:///Users/sebastian/CloudDrive/project-data/write__nn-gzip/1_1_nn_plus_gzip_original.ipynb ）。注意我们设置k=2，并且没有对数据进行预处理，这两个设置都和原论文作者在所有实验中使用的一致。
修正平局打破机制
实际使用k=2时会有一个小问题：比如当两个最近邻的标签是[0, 1]或者[1, 0]时，该如何打破平局？
按照论文提供的代码，出现平局时算法总会选择索引更小的类别标签。换句话说，该方法对类别标签0存在偏向：
>>> top_k_class = [0, 1] >>> max(set(top_k_class), key=top_k_class.count)) 0 >>> top_k_class = [1, 0] >>> max(set(top_k_class), key=top_k_class.count) 0 >>> top_k_class = [1, 0, 2] >>> max(set(top_k_class), key=top_k_class.count) 0
更合理的平局打破方式，是永远选择距离更近的那个近邻。我们可以用Counter对象实现这一点，如下所示。这里假设标签已经按照与待分类样本的近邻距离从小到大排序。
>>> from collections import Counter >>> top_k_class = [0, 1] >>> Counter(top_k_class).most_common()[0][0] 0 >>> top_k_class = [1, 0] >>> Counter(top_k_class).most_common()[0][0] 1 >>> top_k_class = [1, 2, 0] >>> Counter(top_k_class).most_common()[0][0] 1
使用这种改进的平局打破机制，我们可以将代码更新如下：
from tqdm import tqdm
from collections import Counter
k = 2
predicted_classes = []
for row_test in tqdm(df_test.iterrows(), total=df_test.shape[0]):
test_text = row_test[1]["text"]
test_label = row_test[1]["label"]
c_test_text = len(gzip.compress(test_text.encode()))
distance_from_test_instance = []
for row_train in df_train.iterrows():
train_text = row_train[1]["text"]
train_label = row_train[1]["label"]
c_train_text = len(gzip.compress(train_text.encode()))
train_plus_test = " ".join([test_text, train_text])
c_train_plus_test = len(gzip.compress(train_plus_test.encode()))
ncd = ( (c_train_plus_test - min(c_train_text, c_test_text))
/ max(c_test_text, c_train_text) )
distance_from_test_instance.append(ncd)
sorted_idx = np.argsort(np.array(distance_from_test_instance))
top_k_class = np.array(df_train["label"])[sorted_idx[:k]]
predicted_class = Counter(top_k_class).most_common()[0][0]
predicted_classes.append(predicted_class)
print("Accuracy:", np.mean(np.array(predicted_classes) == df_test["label"].values))
这一改动将准确率从70.05%（文件路径：file:///Users/sebastian/CloudDrive/project-data/write__nn-gzip/1_1_nn_plus_gzip_original.ipynb ）提升到了71.91%（https://github.com/rasbt/nn_plus_gzip/blob/main/1_2_nn_plus_gzip_fix-tie-breaking.ipynb ）。
注：我还实现了一个更高效的版本（https://github.com/rasbt/nn_plus_gzip/blob/main/1_2_caching-multiprocessing.py ），通过缓存训练样本的压缩结果，并在不同CPU核心上并行执行搜索。在MacBook Air上，该版本将IMDB电影评论数据集上的运行时间从12小时缩短到了2小时。
与其他方法的对比
我选择IMDB电影评论数据集做实验，是因为我之前在其他项目中对它比较熟悉。比如，我的《机器学习：基于PyTorch与Scikit-Learn》一书中有这些结果：
- 词袋模型 + 逻辑回归：89.9%（https://github.com/rasbt/machine-learning-book/blob/main/ch08/ch08.ipynb ）
- 循环神经网络：85.6%（https://github.com/rasbt/machine-learning-book/blob/main/ch15/ch15_part2.ipynb ）
- DistilBERT：93.27%（https://github.com/rasbt/machine-learning-book/blob/main/ch16/ch16-part3-bert.ipynb ）
使用我的深度学习基础课程（https://lightning.ai/courses/deep-learning-fundamentals/）中的代码（https://github.com/Lightning-AI/dl-fundamentals/blob/main/unit08-large-language-models/8.7-distilbert-finetuning/part3_distilbert-finetuning-whole.ipynb ），甚至有人用RoBERTa-large达到了96.12%的准确率（https://github.com/Lightning-AI/dl-fundamentals/discussions/41 ）
来自我的深度学习基础课程的基准实现（课程地址：https://lightning.ai/courses/deep-learning-fundamentals/unit-8.0-natural-language-processing-and-large-language-models/8.7-a-large-language-model-for-classification/）
计数向量与余弦相似度
另一个有意思的基准方法，是用kNN从词袋模型中选取相似的词计数向量。（如果大家想了解词袋模型，可以看我的课程：https://lightning.ai/courses/deep-learning-fundamentals/unit-8.0-natural-language-processing-and-large-language-models/8.1-working-with-text-data/ ）该方法的原理是：两段相似的文本应该具有相似的计数向量。因此，我们可以不用对比文本压缩后的长度与拼接文本压缩后的长度，而是使用词计数向量。
如果我们有文本1和文本2的词计数向量，当文本相似时，二者相加后的计数向量也会和原向量相似。例如，假设两段完全相同的文本的计数向量如下：
text_1 = [0, 3, 1] text_2 = [0, 3, 1]
那么，相加后的计数向量就是 [0, 3, 1] + [0, 3, 1] = [0, 6, 2] = 2 × [0, 3, 1]。因此，如果我们对相加前后的计数向量分别做归一化，结果会完全一致：
import numpy as np >>> text_1 = np.array([0., 3., 1.]) >>> text_2 = np.array([0., 3., 1.]) >>> text_1 /= np.sum(text_1) >>> print(text_1) [0. 0.75 0.25] >>> text_2 /= np.sum(text_2) >>> print(text_2) [0. 0.75 0.25] >>> added = text_1 + text_2 >>> print(added / np.sum(added)) [0. 0.75 0.25]
接下来，我们可以用欧氏距离计算两个向量之间的距离：
>>> dist = np.sqrt(np.sum((test_vec - added)**2))
不过，我们也可以直接计算两个向量之间的余弦相似度，二者本质上是等价的：
>>> from numpy.linalg import norm
>>> cosine = 1 - (np.dot(test_vec, train_vec) ...
/(norm(test_vec)*norm(train_vec)))
（注意，这里需要用1减去余弦相似度，才能得到余弦距离。）
完整代码如下：
from collections import Counter
from tqdm import tqdm
from numpy.linalg import norm
k = 2
predicted_classes = []
for i in tqdm(range(df_test.shape[0]), total=df_test.shape[0]):
test_vec = X_test[i].toarray().reshape(-1)
test_label = df_test.iloc[i]["label"]
distance_from_test_instance = []
for j in range(df_train.shape[0]):
train_vec = X_train[j].toarray().reshape(-1)
train_label = df_train.iloc[j]["label"]
cosine = 1 - np.dot(test_vec, train_vec)/(norm(test_vec)*norm(train_vec))
distance_from_test_instance.append(cosine)
sorted_idx = np.argsort(np.array(distance_from_test_instance))
top_k_class = np.array(df_train["label"])[sorted_idx[:k]]
predicted_class = Counter(top_k_class).most_common()[0][0]
predicted_classes.append(predicted_class)
print("Accuracy:", np.mean(np.array(predicted_classes) == df_test["label"].values))
最终得到的准确率为68.01%（https://github.com/rasbt/nn_plus_gzip/blob/main/4_r8-dataset.ipynb ），虽然不如gzip方法，但差距不大（在4%以内）！
快速测试R8数据集
上面我们在IMDB电影评论数据集上评估了gzip方法，而该数据集不在原论文的研究范围内。为了对比我改进平局打破机制后的复现结果，和原论文所用数据集上的结果，我们来看R8数据集（选它是因为它规模很小，只需要几分钟就能跑完）。
摘自论文（https://aclanthology.org/2023.findings-acl.426/）的注释图，突出标注了R8数据集
使用论文某张图中描述的“最小索引”平局打破策略，准确率为88.90%（https://github.com/rasbt/nn_plus_gzip/blob/main/4_r8-dataset.ipynb ），低于原论文报告的数值。（原因会在下一节说明。）相比之下，使用我前面提到的改进版平局打破策略，准确率达到了91.27%——但仍然低于原论文的结果。下一节会解释这种差异的来源。
原代码存在的问题
正如Ken Schutte在其文章（https://kenschutte.com/gzip-knn-paper/ ）中指出的，在需要解决[0, 1]或[1, 0]这类平局的场景下，选择k=2是个有点奇怪的决定。解决平局的方式有很多种，包括：
- 始终选择类别索引更小的标签（scikit-learn和原论文图中的Python代码都采用这种方式）；
- 选择两个近邻中距离更近的那个（这是我更推荐的方式，也就是上一节“修正平局打破机制”中实现的方法）；
- 随机决定胜出的标签。
Ken Schutte提到，原论文的代码仓库（https://github.com/bazingagin/npc_gzip ）使用了第四种策略，这可能是一个代码bug。比如，它在处理平局时，总会选择测试样本的真实标签：
# here, sorted_pred_lab[][] has the
# labels and counts corresponding
# to the top-k samples,
# [[label,count],[label,count],...]
# grouped-by label and sorted by count.
most_label = sorted_pred_lab[0][0]
most_count = sorted_pred_lab[0][1]
if_right = 0
for pair in sorted_pred_lab:
# we loop until we drop below 'most_count', ie
# this for-loop iterates over those classes
# tied for highest count
if pair[1] < most_count:
break
# this says if ANY of those
# in the tied-set are equal to
# the test label,
# it is marked correct (if_right=1)
if pair[0] == label[i]:
if_right = 1
most_label = pair[0]
# accumulate results:
pred.append(most_label)
correct.append(if_right)
根据Ken Schutte的分析，修正平局打破机制后，“gzip方法的表现从最优变成了最差”。
除此之外，数据集还存在重叠问题，Yann Dubois在这条推文中提到了这一点：https://twitter.com/yanndubs/status/1681325900170776578?s=20
基准测试中潜在的数据重叠问题
不过据我理解，这种重叠或多或少会影响论文中评估的所有方法。如果大家想了解训练集与测试集重叠问题的更多细节，推荐看Ken Schutte的后续文章：https://kenschutte.com/gzip-knn-paper2/
总结与思考
这篇ACL论文（https://aclanthology.org/2023.findings-acl.426/ ）提出的gzip方法是一项非常优雅、极具启发性的研究成果，我非常享受探索它的过程。
遗憾的是，该方法实际的预测性能可能比论文报告的要差，但它仍然是一个很有意思的思路。
我们应该在实际中使用它吗？一方面，这个方法有很多优点：它是一个很简洁的基准方法，而且不需要GPU，在当前GPU紧缺的背景下这是很大的优势。另一方面，它的效果显然没有宣传的那么好，而且kNN也不太容易适配更大规模的数据集——作为参考，我在IMDB上的朴素实现，用单个CPU跑了整整一天才完成。
这件事积极的一面在于，我们有了一种全新的、简洁的基准方法。同时这篇论文也凸显了，在学术成果传播中，开放源代码与社区讨论是多么重要——这是传统的同行评审无法替代的。
拓展阅读资料
下面是我觉得不错的几篇同主题文章：
- Ken Schutte 所著：https://kenschutte.com/gzip-knn-paper2/
- https://codeconfessions.substack.com/p/lz77-is-all-you-need ，作者为 https://open.substack.com/users/14520974-abhinav-upadhyay?utm_source=mentions 和 https://open.substack.com/users/6970039-alejandro-piad-morffis?utm_source=mentions
近邻方法详解
近邻算法是“最简单”的有监督机器学习算法之一，在过去一个世纪的模式识别领域中已经被研究得非常透彻。尽管近邻算法如今不如从前热门，但在实际中仍被广泛使用。我非常推荐大家在分类项目中把k近邻算法作为预测性能的基准，尤其是在开发更复杂的模型时。
如果大家想深入学习包括k近邻在内的近邻方法，我有一份20页的讲义，是几年前我教授机器学习课程时编写的。
不过即便你已经熟悉了基础知识，也可以看看第2.7节“提升计算性能”，其中的内容在实际机器学习工作和面试中都很实用：
- 使用优先队列
- 数据结构：分桶法、KD树、球树
- 降维
- 更快的距离度量与启发式方法
- 剪枝
- kNN的并行化
你可以在这里下载这份讲义：https://sebastianraschka.com/pdf/lecture-notes/stat451fs20/02-knn__notes.pdf
这本杂志是我个人的兴趣项目，没有直接的经济收益。不过如果大家想支持我，可以考虑购买我的书：https://sebastianraschka.com/books 。如果你觉得这些书有启发、有帮助，也欢迎推荐给你的朋友和同事。
https://www.amazon.com/Machine-Learning-PyTorch-Scikit-Learn-scikit-learn-ebook-dp-B09NW48MR1/dp/B09NW48MR1/ 、https://nostarch.com/machine-learning-and-ai-beyond-basics ，以及 http://mng.bz/M96o
你的支持对我意义重大！非常感谢！