用压缩理论分析文本嵌套结构，实现无需训练的高效分类
Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective
- 基于算法信息论构建层级重复结构提取方法Ladderpath
- 三种新距离度量在少样本和分布外场景均超越gzip与BERT
- 轻量可解释，适合低资源及跨领域文本任务
我们提出一种基于算法信息论（AIT）的结构化序列分析新方法。核心是Ladderpath方法，用于提取语言序列中嵌套与层级重复子结构——这是AIT通过最小生成程序描述数据原理的具体体现。这些结构被用于定义三种距离度量：归一化压缩距离（NCD）及两种直接基于Ladderpath表示的替代距离。结合k近邻分类器，在分布内、分布外（OOD）及少量样本文本分类任务中表现强劲且稳定。尤其在分布外与低资源条件下，所有三种方法均优于gzip-based NCD与BERT。结果表明，Ladderpath捕捉的结构化表征保留了序列内在特性，为文本建模提供了一种轻量、可解释、无需训练的替代方案。该工作凸显了基于AIT的方法在结构化与领域无关序列理解中的潜力。
原文摘要 · Abstract (English)
We present a new method for structural sequence analysis grounded in Algorithmic Information Theory (AIT). At its core is the Ladderpath approach, which extracts nested and hierarchical relationships among repeated substructures in linguistic sequences -- an instantiation of AIT's principle of describing data through minimal generative programs. These structures are then used to define three distance measures: a normalized compression distance (NCD), and two alternative distances derived directly from the Ladderpath representation. Integrated with a $k$-nearest neighbor classifier, these distances achieve strong and consistent performance across in-distribution, out-of-distribution (OOD), and few-shot text classification tasks. In particular, all three methods outperform both gzip-based NCD and BERT under OOD and low-resource settings. These results demonstrate that the structured representations captured by Ladderpath preserve intrinsic properties of sequences and provide a lightweight, interpretable, and training-free alternative for text modeling. This work highlights the potential of AIT-based approaches for structural and domain-agnostic sequence understanding.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。