技术摘要：用于动力系统辨识的自适应对称性发现

1. 问题陈述

本文研究了从单条观测状态转移轨迹中进行动力系统辨识的问题。具体而言，研究对象是关于对称群 $G$ 具有等变性（equivariant）的系统，其中群 $G$ 本身对学习者而言是未知的。

作者考虑了一类特征提升线性动力系统（feature-lifted linear dynamical systems），其中状态演化 $x_{t+1} = f(x_t)$ 由作用在提升后的特征空间 $\Phi(x_t)$ 上的线性映射 $W$ 控制，即 $x_{t+1} = W\Phi(x_t)$。假设动力学具有 $G$-等变性，这意味着参数矩阵 $W$ 满足交织条件 $\rho(g)W = W\rho_\Phi(g)$，对于所有 $g \in G$ 均成立，其中 $\rho$ 和 $\rho_\Phi$ 分别是 $G$ 在状态空间和特征空间上的表示。

核心挑战有两个方面：

1. 可辨识性（Identifiability）： 当对称群 $G$ 已知时，确定唯一确定系统参数 $W$ 所需的最短轨迹长度 $T$。
2. 自适应发现（Adaptive Discovery）： 开发一种方法，能够从单条轨迹中同时辨识未知的对称群 $G$ 和系统参数 $W$，并实现与已知 $G$ 时相同的样本效率（轨迹长度）。

2. 方法论

本文利用群表示理论和**凯莱图扩展器（Cayley graph expanders）**理论来推导理论保证和算法。

2.1 已知对称性：样本复杂度表征

当 $G$ 已知时，作者表征了实现泛型可辨识所需的最小轨迹长度 $T_\Phi(G)$。

• 同型分解（Isotypic Decomposition）： 利用状态空间和特征空间在 $G$ 的不可约表示（irreps）下的分解，等变矩阵 $W$ 分解为对应于每个不可约表示 $\pi$ 的独立块。
• 秩条件（Rank Condition）： 可辨识性简化为确保每个活跃的不可约表示块对应的“特征设计矩阵”具有全行秩。具体而言，对于特征空间中具有多重数 $m_\pi$ 的每个不可约表示 $\pi$，轨迹必须充分激发系统，使得堆叠特征向量的泛型秩等于 $m_\pi$。
• 下界： 作者建立了一个表示论下界：$T_\Phi(G) \ge \max_{\pi: n_\pi > 0} \lceil m_\pi / d_\pi \rceil$，其中 $d_\pi$ 是不可约表示的维度，$n_\pi$ 是其在状态空间中的多重数。
• 关键洞察： 对于特定对称性（例如多项式系统中的置换等变性），该界限可以显著低于泛型情况（即 $T \approx$ 总特征维度的情况），通常将所需的轨迹长度降低到与状态维度无关的常数。

2.2 自适应对称性发现

当 $G$ 未知时，本文提出了算法 1，它遍历一个已知的候选群族 $\mathcal{G}$。

• 生成集（Generating Sets）： 算法并非测试针对整个群（这可能呈指数级增长）的等变性，而是从每个候选群 $G \in \mathcal{G}$ 中采样一小组随机元素 $S_G$。
• 随机生成元： 利用有限群可以由 $O(\log |G|)$ 个随机元素以高概率生成的特性（基于子群增长性质和凯莱图的性质），算法仅对这些采样的生成元施加等变性约束。
• 可行性测试： 对于每个候选群，算法检查是否存在满足轨迹约束和采样生成元等变性约束的参数矩阵 $W$。
• 选择： 算法选择在容许可行解的候选群中基数最大的一个。
• 理论保证： 在**泛型候选分离（generic candidate separation）**条件下（即不同的候选群可以通过短轨迹进行区分），该算法能以高概率恢复真实的动力学和真实的对称群，且使用的轨迹长度不超过 $T_\Phi(G_{true})$。

2.3 有界指数子群发现

对于未知群是已知环境群 $\Gamma$ 的有界指数 $B$ 子群的情景，本文提出了算法 2。

• 拒绝采样（Rejection Sampling）： 算法不再枚举候选子群，而是从环境群 $\Gamma$ 中均匀采样元素。
• 逐元素测试： 对每个采样的元素进行可行性测试（即是否存在一个与轨迹一致且对该特定元素具有等变性的 $W$）。
• 生成： 收集被接受的元素，直到形成未知子群的生成集。所需的期望环境采样次数与指数界 $B$ 成正比。

3. 核心贡献

1. 样本复杂度降低： 本文证明了已知对称群可以比泛型设置实现更短轨迹的系统辨识。通过特征空间中不可约表示的多重数，本文精确地表征了这种减少。
2. 具有最优效率的自适应发现： 作者提出了一种直接从单条轨迹中发现未知对称群的方法。至关重要的是，他们表明这种自适应发现带来的轨迹长度开销可以忽略不计；即使在 $G$ 未知的情况下，只要候选族是泛型分离的，仍能从长度为 $T_\Phi(G)$ 的轨迹中识别出系统。
3. 计算效率： 所提算法避免了迭代遍历全群元素。通过利用随机生成集（其大小与群规模呈对数关系），计算复杂度保持在状态维度的多项式级别以及群规模的对数级别，这使得处理大型群（如置换群）变得可行。
4. 理论框架： 该工作引入了将群表示理论和凯莱图扩展性质应用于动力系统辨识的新颖方法，并为对称性发现提供了可证明的保证。

4. 结果

• 理论界限： 本文推导了各种对称群（包括线性系统、多项式系统和置换等变系统）的最小轨迹长度 $T_\Phi(G)$ 的精确公式。例如，对于具有全置换对称性 ($S_d$) 的二次系统，所需的轨迹长度是一个与状态维度 $d$ 无关的常数 (4)，而泛型情况则需要 $O(d^2)$。
• 算法性能：
  • 算法 1 使用每个候选群 $O(\log |G|)$ 个样本，成功以至少 $1-\delta$ 的概率恢复真实的动力学和对称群。
  • 算法 2 在不枚举候选群的情况下恢复有界指数子群，其期望采样开销为 $O(B \log |\Gamma|)$。
• 实证验证： 在具有置换对称性的线性动力学上的概念验证实验证实了理论预测。在预测的轨迹长度处，可行解集的维度精确下降，涵盖了平凡群、单置换群和全对称群。

5. 意义与主张

本文声称解决了文献中的一个基本空白：虽然已知对称性能提高学习效果，但对于动力系统中对称性发现的可证明定量保证一直缺乏。现有的大多数方法都是启发式的或特定于模型的。

作者强调，其工作提供了：

• 基础极限： 对通过对称性可以获得多少样本效率，以及在没有预先知晓对称性的情况下如何实现这种增益，提供了理论理解。
• 最优自适应： 证明了即使在对称性未知的情况下，也能实现与“已知对称性”情况相同的最优轨迹长度，从而有效地消除了在数据需求方面的发现成本。
• 新工具： 将表示论和扩展图性质集成到系统辨识中，作者认为这对于研究动力系统中的对称性可能具有独立的学术价值。

本文对研究范围保持了适度的审慎，指出目前的结果适用于无噪声环境和有限群。作者指出，将这些结果扩展到噪声系统和无限（李）群是重要的未来研究方向。