梯径
概述
由刘宇（Yu Liu）、狄增如（Zengru Di）和菲利普·格利（Philip Gerlee）于2022年提出的梯径方法，源自组装理论（assembly theory），是一种新颖的框架，用于量化单一结构化对象（如字符串、空间模式、分子或语言片段）的复杂性和信息。
梯径包括一系列生成操作，用于逐步构建目标对象。每一步，可重复使用的较小的子结构单元会被组合或连接起来。经过梯径重构的步骤后，整个序列会形成一个偏序多重集或梯图，用于捕获层次依赖关系。
传统的复杂性度量（如柯尔莫哥洛夫复杂度或香农熵）要么依赖于无限集合，要么在计算上难以处理。相比之下，梯径提供了一种构造性的、层级化的视角，强调对象如何通过利用重复和重用来合理地构建。
梯径包括一系列生成操作，用于逐步构建目标对象。一个梯径本质上是一系列构建（或称“进化”）生成的序列，通过这些生成步骤将更小的组件（称为梯元，ladderon）组合成日益复杂的结构。这些阶梯子可以在构建步骤中重复使用，它们的组装关系可以通过一个偏序多重集（partially‑ordered multiset）或一个梯图（laddergraph）来捕捉。从这个表示中，衍生出两个互补的度量指标：
- 梯径度（[math]\displaystyle{ \lambda }[/math]）：表示通过最优重用组件来构造对象所需的最少步骤数。
- 有序度（[math]\displaystyle{ \omega }[/math]）：量化了相较于一种无结构构建（即每个基本元素都单独添加）所节省的步骤数。其形式化定义为[math]\displaystyle{ \omega=S-\lambda }[/math]，其中 [math]\displaystyle{ S }[/math] 是规模度（size-index），即不进行任何重用的从头构建成本。
这两个指数提供了一个二维的复杂性度量谱系：[math]\displaystyle{ \lambda }[/math]反映了内在的新颖性或信息成本，而[math]\displaystyle{ \omega }[/math]反映了结构的冗余性或有序度。重要的是，该方法是领域无关的（domain-agnostic）——它同样适用于字符串、空间配置、生物分子、语言结构，甚至进化系统。
将梯径度和有序度看作“复杂性”的两个轴，结合以上其衍生的指标，可以用梯径框架衡量一个序列结构或组件结构的复杂度。
除了理论上的简洁与优雅，梯径框架还具有广泛的实际意义和应用前景。它可以用于检测基因或蛋白质序列中的模块化重复、分析语言中的句法结构，以及模拟生物系统（从简单的化学网络到复杂的生物体）中的进化组装过程。它与“进化就像修修补补”（evolution-as-tinkering）范式的契合性，使其成为探索自然和人工系统中复杂性涌现的强大工具。
背景
单个对象的句法复杂性度量
梯径理论的发展源于一个长期存在的挑战：如何在不依赖统计集合或无限数据集的情况下，测量单个对象（如序列、分子或模式）的句法复杂性（syntactic complexity）。
柯尔莫哥洛夫复杂度（Kolmogorov complexity）和香农熵（Shannon entropy）等经典方法提供了宝贵的见解，但存在固有的局限性：柯尔莫哥洛夫复杂度因停机问题（halting problem）而通常不可计算；而香农熵则只反映平均不确定性聚焦于跨统计集合的平均值，而忽略了序列内部模式、语法结构，具体为：
- 柯尔莫哥洛夫复杂度
柯尔莫哥洛夫复杂度（Kolmogorov Complexity），又称算法复杂度，是指描述某一对象（如字符串、序列或数据结构）所需的最短计算机程序长度。形式上，对于给定的通用图灵机[math]\displaystyle{ U }[/math]和输入对象[math]\displaystyle{ x }[/math]，[math]\displaystyle{ l(x) }[/math]表示二元串的长度，当给定程序[math]\displaystyle{ p }[/math]时，令[math]\displaystyle{ U(p) }[/math]表示计算机U关于程序p的输出，其柯尔莫哥洛夫复杂度定义为：
[math]\displaystyle{ K_U(x)=\underset{p:U(p)=x}{min}l(p) }[/math]
即柯尔莫哥洛夫复杂度定义为能够输出x的并且停止的所有程序的最小长度，也可以理解为可由计算机[math]\displaystyle{ U }[/math]说明的[math]\displaystyle{ x }[/math]的描述中的最短描述长度（信息论基础） 柯尔莫哥洛夫复杂度对于单个对象的句法复杂性度量的不足在于，由于停机问题的不可判定性，无法构造通用算法来精确算出任意对象的最短描述程序长度 [math]\displaystyle{ K(x) }[/math]。我们至多只能给出上界估计（例如通过通用压缩算法获得的压缩后长度），但无法知道这是否就是最短程序，因此无法得到真正的复杂度值。
- 香农熵（Shannon entropy）
香农熵（Shannon Entropy）是信息论中用于度量来源不确定性的经典量度。对于离散随机变量[math]\displaystyle{ X }[/math] 及其概率分布[math]\displaystyle{ {p_i} }[/math]，香农熵定义为：
[math]\displaystyle{ H(X) = -\sum_{i=1}^n p_i \log_2 p_i }[/math]
它反映了一个序列从该分布中抽样时平均每次可获得的信息量（以比特为单位）。 香农熵对于单个对象的句法复杂性度量的不足在于，香农熵度量的是从一个已知概率分布中抽样时的平均信息量，而非针对某一具体样本的独特结构。即使两条序列内部模式、语法结构截然不同，只要它们在整体分布下的符号频率相同，香农熵给出的值也完全相同，无法区分个体间的细节差异。
鉴于这些挑战，一些强调模块化重用和层级化组合的观点提供了引人注目的替代方案。这些观点包括弗朗索瓦·雅各布（François Jacob）提出的“进化即修补”（evolution as tinkering, 1977）概念、高德纳（Donald Knuth）的加法链问题（addition-chain problem），以及更近期的路径复杂性（pathway complexity）和组装空间理论（assembly space theories）。这些框架关注复杂结构如何从更简单的亚单元构建而成，强调组合效率（combinatorial efficiency）和重复利用（repetition）。
在这一概念基础上发展起来的组装理论（Assembly Theory，由克罗宁（Cronin）、沃克（Walker）等人开创），将“追溯从基本组件构建对象所需的最小组装操作序列”这一思想形式化，从而提供了一种称为组装指数（assembly index）的度量。该指数有助于区分可能由生物或技术过程塑造的对象与偶然产生的对象，为探测生物特征（biosignatures）和生命起源开辟了道路。
在此基础上，梯径理论通过提供一个层级化的路径模型——一个由可重用构建块组成的“阶梯”（ladder），扩展并形式化了这些先前的思想。通过这个模型，单个对象可以在最优效率的步骤中被构造出来。该方法能够同时量化生成的新颖性（需要多少新的构建步骤）和重用或结构的程度，而无需诉诸基于统计集合的方法。
组装理论
组装理论提供了一个量化单个分子结构内在复杂性的框架，其核心思想是：考虑从一组预定义的基本构建模块（例如化学键）出发，构建目标分子所需的最少组装步骤序列——每一步骤都涉及将两个分子亚基连接起来。一条组装路径在形式上表示为一个有向多重图：其中顶点对应分子片段，边对应连接操作；多重边允许相同片段存在不同的组合方式。分子的分子组装指数（MA） 定义为构建该分子的最短可能组装路径的长度（即连接操作的数量），并允许路径中生成的中间片段在后续步骤中复用。
梯径理论的框架：算法信息论
由算法信息论引导的复杂性度量——单个结构化对象的信息
长期以来，对单个结构化对象（如字符串、分子或模式）复杂性的度量探索一直由算法信息论（Algorithmic Information Theory, AIT） 所引导。AIT 由 Kolmogorov、Chaitin 和 Solomonoff 在 20 世纪 60 年代创立，它通过能在通用图灵机（universal Turing machine）上生成该对象的最短可能程序的长度来定义复杂性，即柯尔莫哥洛夫复杂度（Kolmogorov complexity）。这种方法抓住了我们的直觉：高度有序或重复的结构是低复杂度的，而随机、无模式的对象具有最大的复杂度。
然而，AIT 的核心度量是不可计算的：由于停机问题（halting problem），不存在确定确切最短程序的通用算法。对于物理对象（如分子），AIT 将需要指定一个能生成它们的通用分子构造器，这使得直接计算变得不可行。虽然存在像 Lempel-Ziv 压缩这样的近似方法，但这些方法通常反映的是统计冗余性而非真正的算法结构，并且可能无法区分随机性和结构化复杂性。
梯径方法和算法信息论的联系
梯径理论，旨在通过关注结构的层级化、基于组装的本质来解决这些局限性。和组装理论（Assembly Theory）密切相关 ，梯径理论通过最小化“组装指数（assembly index）”——即通过可重用的子结构构造一个对象所需的最少步骤数——来度量复杂性。
梯径理论和 AIT紧密相关（两者都寻求对象的最短描述），然而在范围和可计算性上稍有不同。它不是进行通用压缩，而是模拟一个领域特定的构造机器，该机器执行一系列组合操作（连接、键合等），并在一个组装池（assembly pool）中跟踪可重用的子单元。这产生了构建过程的层级化多重集表示（梯图，laddergraph），从而得到两个可计算的度量：
-梯径度（[math]\displaystyle{ \lambda }[/math], ladderpath-index）：重构目标序列结构最少的组装步骤数。
-有序度（[math]\displaystyle{ \omega }[/math], order-index）：通过重用节省的开销，即结构有序度。
这些度量满足公式[math]\displaystyle{ S=\lambda+\omega }[/math]，其中[math]\displaystyle{ S }[/math]是规模度（size-index）（即无重用构造的成本）。至关重要的是，这个框架对于有限对象是可计算的，为柯尔莫哥洛夫复杂度的不可行计算提供了一种实用的替代方案。
综上所述 ，梯径方法在算法信息论的框架上，实现了以下的优化：
- AIT 提供了一种基于最短通用描述的信息度量原则，但通常是不可计算的。
- 基于组装理论，梯径理论提出了一种可计算的、考虑层级结构的复杂性度量，其基础是构造规则和重用，使其适用于物理和生物系统。
- AIT和梯径在深层理论上有联系——都寻求最短描述。但在实用性、侧重点以及对显式组装路径（explicit assembly pathways） 与通用计算（universal computation） 上存在差异。
定义
定义“生成操作”
假设我们有一个包含英文字符 A, B, C, D, E, F 的集合，现在需要获得一个特定的英文字符串 [math]\mathcal{X}=ABCDBCDBCDCDEFEF[/math] 问如何以最快的方式得到[math]\mathcal{X}[/math]?
首先我们定义一个基础集[math]S_0 = \{A(0), B(0), C(0), D(0), E(0), F(0)\}[/math] “生成操作”(Generation-operation) 是指，取此类偏序多重集中的若干组件，其重数相应地减少，再以某种方式结合在一起，最后将结合而成的新组件放回到该集中，放在其构成组件最高层次的下一层。经过这个操作，就产生了一个新的偏序多重集。 以第一次生成操作举例，[math]\displaystyle{ S_0 : C + D = CD \rightarrow S_1 = \{ A(0), B(0), C(-1), D(-1), E(0), F(0) \ / \ CD(1) \} }[/math]
定义“梯径”
对于一条使我们达到最终目的的路径[math]\displaystyle{S_0 \rightarrow S_1 \rightarrow S_2 \rightarrow \dots \rightarrow S_n \Rightarrow \mathcal{X}}[/math],我们以如下的方法来构造偏序多重集 [math]\displaystyle{\mathcal{J}}[/math]：
1. 取最终的集合 [math]\displaystyle{\mathcal{S}_{\mathcal{n}}}[/math]；
2. 删掉所有重数为零的元素；
3. 将所有的负重数取绝对值作为对应组件的重数；
4. 保留所有的偏序不变。
该过程构造出的这个偏序多重集[math]\displaystyle{\mathcal{J}}[/math]，称为这条路径的“梯径”（Ladderpath）。
任一梯径都能被完备地表示为一个偏序多重集。但有时候将梯径用图的形式表示可能更为直观，称为“梯图”，其中的层次即为梯径的偏序关系，组件之间的连接表示生成操作（比如 E 和 F 向上连接到 EF，表示 EF 由 E 和 F 生成）。
从梯径表示中，衍生出三个关键度量指标用于描述一个系统：
1. 梯径度（[math]\displaystyle{\lambda}[/math], Ladderpath-index）：
- 此指数衡量在考虑阶梯元重用的前提下，构造对象所需的最少的组装步骤数，即最短梯径的长度。
2. 规模度（[math]\displaystyle{S}[/math],Size-index）:
- 一个组件的最短的平凡梯径的长度。
3. 有序度指数（[math]\displaystyle{\omega}[/math], Order-index）：
- 定义为规模度（S, size-index） 与梯径度（λ）之间的差值，即 ω = S − λ。 - 等价于通过最短梯径来生成该目标组件所节约的“长度”，即所节约出来的结合组件的操作所花费的步骤。
最短梯径的算法
1. 首先创建一个空的多重集 H 用以存放组件。在最后我们可以通过 H 计算出梯径。
2. 从目标系统 Q 出发，每个不同的组件都只保留一个在 Q 中，其余的重复组件全部放入 H 中。
3. 以某种预先规定的特定方式，持续切割Q 中的组件，直到 Q 中有至少 2 个子字符串或字符相同。然后在 Q 中只保留一个该字符串，其余重复的字符串全部放入 H 中。
4. 重复步骤 3，直到 Q 中不再能找到重复的字符串或字符。最后把剩下的全部切割成基础组件， 然后全部放入 H中。此时的 H 即记录了一条梯径。
5. 最后，需要将 H 中各字符串的层次关系（即，根据它们是如何被分割的：谁是父字符串，谁是子字符串）排列清楚，即最终得到该梯径的偏序多重集表示。
该算法可通过 GitHub 仓库获取：https://github.com/yuernestliu/ladderpath_v0
应用
用梯径进行分词
为实现对自然语言中结构性冗余的高效压缩，我们提出了一种基于梯径结构的子词词表构建方法。该方法以预构建的梯元结构为基础，通过梯元的重要性排序与代价控制，选取若干高复用性、高贡献度的子结构单元，组成最终用于表征原文的词表。
应用领域：
- 自然语言处理（NLP）：在 NLP 中，梯径分词器可用于将文本分割成有意义的子结构，从而促进句法分析和语义分析等任务。
- 生物信息学（Bioinformatics）：在生物信息学中，此方法可用于分析 DNA 或蛋白质序列，识别指示功能元件的重复基序（motifs）和结构模式。
- 计算生物学（Computational Biology）：梯径分词器有助于理解生物系统的模块化构建方式，从而为其复杂性和进化提供见解。
将梯径用于分析生物序列信息
生物序列信息作为一种由有限基本单元组成、包含大量重复嵌套结构的信息结构，十分适合进行梯径分析。
梯径理论通过模拟“生成—重用”的过程，将生物序列（如DNA、蛋白质序列）分解为可重用的子单元（梯元），并构建出反映层次化结构的阶梯图。相比传统的多序列比对和熵分析，阶梯路径更关注“对象如何被生成”，从而捕捉到统计方法难以描述的层次化关系。
对于生物序列做梯径分析，其核心优势在于：首先，序列的基本单元（如核苷酸或氨基酸）数量有限，却能通过不同的重复与组合产生丰富多样的功能片段；其次，这些重复片段往往以嵌套、串联或分支的形式出现，例如基因组中的复制子或蛋白质中的结构域家族，使得序列天然具备多层次的模块化特征；再次，进化过程中频繁的重复插入、删除或重排事件，正是阶梯路径分解算法所要捕捉的“生成—重用”轨迹。通过对这些嵌套重复结构进行阶梯路径分解，可以定量地揭示序列在进化历史上经历的关键生成步骤，以及不同层次上子单元的重用频度与模式。这不仅有助于比较不同物种或同源蛋白在层次化结构上的差异，也能为功能预测、蛋白工程和进化重建等应用提供新的思路和指标。
相关的研究为：Evolutionary Tinkering Enriches the Hierarchical and Interlaced Structures in Amino Acid Sequences[1]
用梯径做压缩
以字符串"ABCDBCDBCDCDEFEF"为例，经梯径方法处理后，我们获得了如图深灰色所示的三个梯元{'BCD','CD','EF'}。原始字符串本质上是由基础构件与这些梯元组合而成。
下面给出在技术层面，如何使用梯径方法进行压缩，将原始的字符串压缩为一个序列。
import ladderpath as lp
import ladderpath_tools.compress as lp_c
X = ['ABCDBCDBCDCDEFEF']
lpjson = lp.get_ladderpath(X)
compressed_list = lp_c.compress(lpjson, SEP='@')
# 输出结果：
# compressed_list = [1, '@', 'A', 2, 2, 2, 1, 0, 0, '@', 'EF',
# '@', 'CD', '@', 'B', 1]
现对compressed_list进行说明：分隔符"@"用于区分不同序列和梯元；第一个元素"1"表示目标序列仅包含一个字符串，后续元素"A", 2, 2, 2, 1, 0, 0描述原始字符串的重构过程：基础构件"A"首先与元素2组合再与元素2组合两次依次与元素1、元素0（两次）组合；三个"@"分隔符划分三个梯元："EF"表示梯元0，由基础构件E和F组合生成；"CD"表示梯元1，由C和D组合生成；同理，"B", 1组成梯元2。 需注意，compressed_list中的梯元ID可能因实现细节与梯径算法给出的梯元ID存在差异。
用梯径分析神经网络
梯径 (Ladderpath) 方法最近被应用于人工神经网络（ANNs），特别是多层感知机（MLPs）的结构分析中，作为一种理解网络架构与性能之间关系的新颖方法。 这种方法允许通过梯径度 (ladderpath-index) 和有序度 (order-index) 这两个指标来量化结构的有序性和复杂性，它们的归一化比值被称为有序率 (order-rate, [math]\displaystyle{ \eta }[/math])。 有序率[math]\displaystyle{ \eta }[/math]的定义方式为：
1. 首先考虑有序度
[math]\displaystyle{ \omega(x) }[/math]： [math]\displaystyle{ \omega(x)=s-l(x) }[/math]
其中[math]\displaystyle{ s }[/math]表示规模度，即序列[math]\displaystyle{ x }[/math]的长度，[math]\displaystyle{ l(x) }[/math]为序列[math]\displaystyle{ x }[/math]的梯径度。
2. 确定长度[math]\displaystyle{ s }[/math]、有序度[math]\displaystyle{ \omega(x) }[/math]的边界值
最大有序指数 [math]\displaystyle{ \omega_{max}(S) }[/math]：
当序列完全有序时取得（例如全重复序列 AAAA...）。此时梯径度为 1（只需构建一个符号），故：
[math]\displaystyle{ \omega_{max}(S)=S-1 }[/math]
- 基准有序指数 ω0(S)：
指在给定字母表（如 {A,B,C,D}）上，纯随机长度为 S的序列的有序度的期望值。实践中通过以下方式确定：
(a) 理论推导 或 (b) 对大量随机序列计算 ω后取平均值。
3.归一化计算有序率
有序率的计算公式为：
[math]\displaystyle{ \eta(x)=\frac{\omega(x)-\omega_0(S)}{\omega_{max}(S)-\omega_0(S)} }[/math]
根据设计原则：
- [math]\displaystyle{ \eta }[/math]≈0时，序列无显著层次结构（完全随机）
- [math]\displaystyle{ \eta }[/math]≈0.5时，序列呈现最丰富的嵌套模块化结构
- [math]\displaystyle{ \eta }[/math]≈1时，序列呈现极致层次化（完全重复）
在神经网络的背景下，[math]\displaystyle{ \eta }[/math] 作为一个标量度量，反映了网络层次结构的丰富程度。[math]\displaystyle{ \eta }[/math] 值接近 0 表示随机性或缺乏结构，而 [math]\displaystyle{ \eta }[/math] 接近 1 则意味着过度规则化。具有中等 [math]\displaystyle{ \eta }[/math] 值（约 0.5 左右）的网络展现出最复杂且深度嵌套的模块化层次结构。实证研究表明，此类网络在各种任务上的表现往往优于其他网络，这表明层次结构的丰富程度与功能能力之间存在直接关联。
为了将梯径应用于神经网络，研究人员首先将网络转换为一组能够捕捉信息在网络路径中流动的序列。这涉及对实值连接权重进行粗粒化处理，并将这些连接编码为符号序列。随后，将梯径算法应用于这些序列以计算 [math]\displaystyle{ \eta }[/math]。通过涉及超过 600 种 MLP 架构、在诸如奇偶校验分类、回归和时间序列预测等任务上进行训练的广泛实验发现，当 [math]\displaystyle{ \eta }[/math] 处于中等范围内时，网络性能达到峰值，这证实了结构的复杂性有助于学习和泛化。
这些发现表明，梯径理论复杂性度量指标之一的[math]\displaystyle{ \eta }[/math] 既可以作为一种初始化或设计人工神经网络架构的指导。
参考文献
- ↑ Zhang, Zecheng & Liu, Chunxiuzi & Zhu, Yingjun & Peng, Lu & Qiu, Weiyi & Tang, Qianyuan & Liu, He & Zhang, Ke & Di, Zengru & Liu, Yu. (2023). Evolutionary Tinkering Enriches the Hierarchical and Interlaced Structures in Amino Acid Sequences. 10.21203/rs.3.rs-3440555/v1.