嵌套重复结构定义文本距离，新方法轻量无训练超越BERT
速览
arXiv新论文提出Ladderpath方法，从序列中提取嵌套与层次化重复子结构，基于算法信息论定义三种文本距离度量。集成KNN分类器后，该方法在分布内、分布外及少样本文本分类任务中表现稳定，特别是所有三种距离均优于gzip压缩距离和BERT在OOD及低资源场景下的效果。该工作展示了基于AIT的结构化表示能捕捉序列内在属性，提供了一种轻量、可解释且无需训练的文本建模方案。
AI 深度解读
背景
文本距离度量在自然语言处理（NLP）中扮演着基础性角色，广泛应用于文本分类、聚类、相似度检索等任务。传统方法主要依赖两种路径：一是基于深度学习的嵌入表示（如BERT），通过对大量标注数据训练获得上下文敏感的特征；二是基于信息论的压缩距离（如gzip），通过压缩率近似序列的Kolmogorov复杂度。前者在数据充足时表现优异，但在低资源、跨分布（OOD）场景下泛化能力有限，且需要大量计算资源；后者虽然无需训练、轻量级，但仅考虑一阶重复模式，忽略了序列中嵌套和层次化的结构关系。这一结构性缺失导致压缩距离在面对复杂语言模式时精度不足。
在此背景下，该工作从算法信息论（Algorithmic Information Theory, AIT）出发，提出一种名为Ladderpath的方法，旨在提取文本中嵌套且层次化的重复子结构，从而更精确地反映序列的内在生成复杂性，并以此定义新的文本距离。该方法兼顾了AIT“用最小生成程序描述数据”的核心思想，同时具有轻量、可解释、无需训练的特点。
核心内容
该工作提出了一种基于算法信息论的结构化序列分析方法，核心组件是 Ladderpath 方法。Ladderpath 能够从语言序列中提取出嵌套和层次化的重复子结构之间的关系——这正是AIT“通过最小生成程序描述数据”原则的一种具体实现。在此基础上，作者定义了三种文本距离度量：
- 归一化压缩距离（NCD）：使用Ladderpath提取的重复结构替代传统gzip压缩器，计算序列间的标准化压缩距离。
- 两种基于Ladderpath表示的替代距离：直接利用Ladderpath所构建的层次化结构表示，不经过压缩率计算，从拓扑或组合角度度量序列的差异性。
这些距离度量被集成到一个 k-近邻分类器（k-NN） 中，并在三类文本分类任务上进行评估：
- 分布内分类（In-distribution, ID）
- 跨分布/分布外分类（Out-of-distribution, OOD）
- 小样本分类（Few-shot）
实验结果一致表明：
- 所有三种基于Ladderpath的距离度量在ID任务上与现有方法竞争力相当，在OOD和低资源场景下显著优于基线方法。
- 具体而言，三种方法均优于基于gzip的NCD以及BERT模型在OOD和低资源设置下的表现。
- Ladderpath捕获的结构化表示保留了序列的内在属性，无需任何训练数据即可直接用于分类。
该工作论证了Ladderpath所提取的结构化表示能够保留序列的“内在性质”，并作为一种轻量、可解释、无需训练的文本建模替代方案。这项工作突显了基于算法信息论的方案在无领域假设的序列理解（structural and domain-agnostic sequence understanding）中的潜力。
关键要点
- Ladderpath方法从算法信息论出发，聚焦于序列中嵌套且层次化的重复子结构，比gzip只考虑一阶重复更能反映数据的生成过程。
- 定义了三种距离度量：一种归一化压缩距离（NCD）和两种直接基于Ladderpath表示的替代距离，均无需训练。
- 结合k-NN分类器，在分布内、分布外、小样本三类文本分类任务上评估。
- 在分布外（OOD）和低资源（Few-shot）场景下，所有三种Ladderpath距离均优于gzip-based NCD和BERT。
- 该方法的优势在于轻量级（无需GPU训练）、可解释（距离可由层次化重复结构解释）、无监督/免训练（训练-free）。
- Ladderpath无需领域知识或标注数据，适用于跨领域的泛化序列理解。
- 与基于深度学习的模型相比，Ladderpath在数据匮乏时鲁棒性更强，且计算成本显著更低。
意义与影响
该工作为文本距离度量提供了一种全新的结构主义视角。传统压缩距离（如gzip）虽然无参数、免训练，但由于其忽视序列中嵌套和层次化的重复模式，在面对复杂语言学结构时信息丢失严重。Ladderpath通过显式提取这种层次化重复，克服了这一局限，同时保留了轻量、可解释、无需训练的优良特性。
从方法论意义上看，该研究在 算法信息论与 自然语言处理之间架起了一座桥梁。它证明了即使不使用深度神经网络，仅通过结构化的重复模式也能在OOD和少样本条件下超越BERT等预训练模型。这为低资源任务（如小语种、医学文本、隐私受限场景）提供了极具吸引力的替代方案。
从应用影响看，Ladderpath距离可以直接嵌入任何基于距离的机器学习算法（如k-NN、层次聚类），且无需训练数据，部署成本极低。在数据标注昂贵的场景下（如冷启动分类、跨域迁移），该方法可快速落地。此外，其可解释性使得模型行为可溯，有助于建立信任。
最后，该工作也提示了未来研究方向：将Ladderpath与其他特征（如词嵌入）结合，或将其层次化表示作为深度学习模型的先验知识，可能进一步提升性能。整体而言，这是一项具有启发性的、回归算法信息论本源的序列理解探索。