Conformalized Data-Driven Reachability Analysis with PAC Guarantees

本文提出了名为 CDDR 的框架，通过 Learn Then Test 校准程序为数据驱动的可达性分析提供 PAC 覆盖保证，仅需校准轨迹独立同分布，从而在无需已知噪声界或系统特定结构参数（如 Lipschitz 常数）的情况下，有效处理线性及非线性系统的可达集计算问题。

要点

这篇论文介绍了一种名为 CDDR（校准化数据驱动可达性分析）的新方法。为了让你轻松理解，我们可以把这项技术想象成**“给自动驾驶汽车画安全圈”**的过程。

1. 核心问题：我们如何保证绝对安全？

想象你正在开发一辆自动驾驶汽车。你需要知道：在接下来的一分钟内，这辆车可能会开到哪些地方？ 这个“可能到达的区域”就是可达集（Reachable Set）。

• 传统方法的困境：
  以前的方法就像是一个**“死记硬背的学霸”**。它必须知道所有规则：比如路有多滑（噪声界限）、转弯有多急（系统参数）。但在现实生活中，路况千变万化，我们往往不知道确切的规则，或者规则太复杂算不出来。如果学霸猜错了，车就可能冲出安全圈，发生危险。
• 现有数据驱动方法的缺陷：
  另一种方法是“看样学样”。它收集了很多以前的行驶数据，然后说：“看，以前最远只开到过这里，所以以后也不会超过这里。”
  • 风险：这就像你只见过 100 只白天鹅，就断定“世界上没有黑天鹅”。如果第 101 次遇到一只黑天鹅（极端情况），你的预测就失效了。以前的方法无法保证在没见过的情况下也绝对安全。

2. CDDR 的解决方案：像“保险精算师”一样思考

CDDR 提出了一种聪明的新策略，它不依赖死板的规则，也不盲目相信过去的经验，而是引入了**“统计学保险”**的概念。

核心比喻：试穿与尺码校准

想象你要给一群身高体重各异的人（未来的行驶轨迹）定制一套**“安全防护服”**（可达集）。

1. 收集数据（训练与校准）：
   你找来了 5000 个志愿者（数据轨迹）。

   • 训练组：用来做衣服版型（学习系统大概怎么动）。
   • 校准组：用来**“试穿”**。你让这些人穿上衣服，看看哪里太紧，哪里太松。

2. LTT 校准（Learn Then Test，先学后测）：
   这是 CDDR 最厉害的地方。以前的方法可能只是看一眼校准组，说：“嗯，大家都穿得下，那就定这个尺码吧。”
   CDDR 的做法是：它像一位严谨的保险精算师。它会问：“如果我换一批人来试穿，这件衣服还会合身吗？我有 95% 的把握（置信度）保证，无论换谁来，衣服都能包住他们，而且漏掉人的概率不超过 5%。”

   • 它通过一种叫 PAC（Probably Approximately Correct，概率近似正确） 的数学保证，确保这套“安全圈”在绝大多数情况下都是绝对可靠的。

3. 应对未知（分布无关）：
   不管路上的噪声是像“温和的小雨”（高斯分布），还是像“突如其来的冰雹”（重尾分布），CDDR 都不需要预先知道雨有多大。它只需要通过“试穿”过程，自动调整衣服的大小，直到能包住 99% 的情况。

3. 三大应用场景（CDDR 能做什么？）

论文展示了 CDDR 在三种复杂情况下的能力：

• 场景一：普通直线运动（LTI 系统）
  就像在平直公路上开车。以前需要知道轮胎打滑的极限，现在 CDDR 直接看数据就能算出安全范围。
• 场景二：传感器有误差（带测量噪声）
  就像你的 GPS 信号有点飘忽不定，显示的坐标和实际位置不一样。CDDR 知道“我的眼睛（传感器）会看错”，所以它会把安全圈画得稍微大一点，把“看错”的可能性也包进去。
• 场景三：复杂的非线性运动（非 Lipschitz 系统）
  这是最难的。就像开车在崎岖的山路上，或者车子有特殊的“分数阶阻尼”（一种奇怪的物理特性，像弹簧突然变硬或变软）。以前的数学公式在这里会失效，但 CDDR 不管它多奇怪，只要数据够多，它就能通过“试穿”把安全圈画出来。

4. 实验结果：为什么它更牛？

作者在实验中做了两个对比：

1. 普通数据法（Emp-max）：就像“看样学样”。在遇到极端天气（重尾噪声）时，它漏掉了 0.1% 的危险情况（虽然看起来很少，但在安全领域是致命的）。
2. CDDR：在同样的极端天气下，100% 成功把所有轨迹都包在了安全圈内。

代价是什么？
为了获得这种“绝对安心”的保险，CDDR 画的安全圈可能会比“看样学样”的方法稍微大一点点（就像为了保险起见，衣服做得稍微宽松一点）。但论文还提出了一种**“智能剪裁”**（归一化分数函数），可以在保持安全的前提下，把衣服做得更合身，减少不必要的浪费。

5. 总结：这篇论文带来了什么？

简单来说，CDDR 就像是为自动驾驶和机器人安全设计了一个**“智能安全网”**：

• 不需要懂物理公式：不需要知道路有多滑、车有多重。
• 不需要猜极限：不需要假设噪声的最大值。
• 提供“保险单”：它不仅仅告诉你“大概安全”，而是给你一张数学上的保险单，保证在绝大多数情况下，系统不会失控。

这就好比以前我们只能靠经验说“这桥大概能承重”，现在 CDDR 能告诉你：“经过严格测试，我有 99% 的把握保证，只要不超过这个重量，桥绝对不会塌。”这对于构建真正安全的未来智能系统至关重要。

技术摘要

论文技术总结：具有 PAC 保证的保形化数据驱动可达性分析 (CDDR)

1. 研究背景与问题定义

背景：
可达性分析（Reachability Analysis）用于计算动态系统在给定初始条件和输入集下所有可能到达的状态集合，是验证网络物理系统（CPS）安全性的核心工具。传统的基于模型的方法需要显式的系统模型，而在实际应用中，模型往往难以获取或成本高昂。因此，数据驱动的可达性分析应运而生，旨在直接从含噪数据中构建可达集。

现有方法的局限性：
现有的数据驱动方法通常依赖于难以满足的强假设：

• 噪声界限已知： 如文献 [2] 的方法需要预先知道过程噪声的界限 $Z_w$。在真实应用中，噪声分布往往未知，导致无法构造 $Z_w$。
• 结构参数已知： 非线性扩展方法通常需要已知多项式阶数或 Lipschitz 常数（$L^*$）及覆盖半径，这些参数对于一般的非线性或非光滑系统是不可用的。
• 保证的脆弱性： 基于经验最大值（Empirical-max）的方法依赖于训练集是否覆盖了最坏情况，这在有限数据下无法验证，因此无法提供形式化保证。

核心问题：
如何在噪声分布未知、系统模型未知（甚至包含非 Lipschitz 非线性动力学）且无先验噪声界限的情况下，构建可达集，并提供有限样本下的概率覆盖保证？

2. 方法论：CDDR 框架

作者提出了**保形化数据驱动可达性（Conformalized Data-Driven Reachability, CDDR）框架。该方法结合了保形预测（Conformal Prediction, CP）与先学习后测试（Learn Then Test, LTT）**校准程序。

2.1 核心流程

CDDR 将数据驱动可达性转化为一个校准问题，主要包含三个阶段：

1. 模型拟合（训练集）： 使用训练数据 $D_{tr}$ 拟合系统模型（对于 LTI 系统使用最小二乘法，对于非线性系统使用局部线性化模型）。
2. 残差评分与阈值选择（校准集）： 在独立同分布（i.i.d.）的校准集 $D_{cal}$ 上计算每一步的残差评分（Score），并利用 LTT 框架选择阈值 $\hat{q}_k$。
3. 可达集传播： 利用拟合的模型和校准得到的误差集（Zonotope）进行可达集传播。

2.2 三种应用场景

CDDR 适用于以下三种设置：

1. 无测量噪声的 LTI 系统： 状态直接观测，过程噪声分布任意且未知。
2. 有测量噪声的 LTI 系统： 观测值包含有界噪声 $v(k)$（已知其 Zonotope 界限 $Z_v$），过程噪声分布未知。
3. 无测量噪声的一般非线性系统： 动力学函数 $f$ 未知且可能非 Lipschitz（如分数阶阻尼系统）。

2.3 关键机制：LTT 与 PAC 保证

• LTT 校准： 不同于传统的保形预测仅提供边际保证（Marginal Guarantee，即针对单次校准划分的保证），LTT 框架通过扫描候选阈值并执行假设检验（基于 Hoeffding-Bentkus 不等式计算 p 值），确保在随机选择校准数据的情况下，覆盖率达到 $1-\alpha$的概率至少为$1-\delta$。
• 模型与保证解耦： CDDR 的一个核心特性是模型精度与统计保证的解耦。无论模型拟合得多么不精确（线性化误差、非光滑性、未建模动态），这些误差都会被吸收到残差评分中，并通过 LTT 校准的阈值 $\hat{q}_k$ 进行覆盖。因此，保证的有效性不依赖于模型类别的准确性。
• 分数函数设计：
  • 各向同性分数： 使用 $\ell_\infty$ 范数，对所有维度应用统一阈值。
  • 归一化分数（Normalized Score）： 针对各向异性噪声，利用训练数据估计噪声形状矩阵 $T_k$，计算 $\|T_k^{-1} r\|_\infty$。这种方法能在保持 PAC 保证的同时，显著减小可达集体积，且无需增加校准样本量。

3. 主要贡献

1. 形式化与 PAC 保证： 首次将未知噪声下的数据驱动可达性形式化为校准问题，并通过 LTT 提供了 $(\alpha, \delta)$-PAC 覆盖保证。该保证独立于校准数据的随机划分。
2. 模型 - 保证解耦原则： 证明了 PAC 保证独立于模型准确性，使得该方法能应用于测量噪声下的 LTI 系统以及现有方法无法处理的非 Lipschitz 非线性系统。
3. 几何与覆盖的权衡控制： 提出了归一化分数函数，利用残差的各向异性特性，在保持 PAC 保证的前提下，将可达集体积减少了几个数量级。

4. 实验结果

作者在两个系统上进行了实验验证：

• 系统 1： 5 维 LTI 系统，分别在高斯噪声和重尾 Student-t 噪声（无界）下测试。
• 系统 2： 2 维非线性系统，具有分数阶阻尼（非 Lipschitz 动力学）。

对比基线：

• Emp.-max： 使用训练集残差最大值作为噪声界限（无形式化保证）。
• Marginal CP： 传统的保形预测（仅提供边际保证，无 PAC 置信度）。

关键发现：

1. 覆盖率与鲁棒性： CDDR 在所有测试中均实现了 100% 的轨迹覆盖率，且失败率为 0%（即 1000 次随机校准划分中，没有一次未能满足 95% 的覆盖要求）。相比之下，Emp.-max 在重尾噪声下覆盖率下降至 99.9%（因训练集未覆盖极值），Marginal CP 虽然平均覆盖率高，但存在约 6.5% 的失败率。
2. 体积效率：
   • 在重尾噪声下，CDDR 生成的可达集比 Emp.-max 更紧凑。
   • 使用归一化分数处理各向异性噪声时，CDDR 将可达集体积减少了四个数量级（从 $1.36 \times 10^5$降至$41.0$），同时保持了与各向同性分数相同的 PAC 保证和最小的校准样本需求（$n_{min}=459$）。
3. 非 Lipschitz 适用性： 在分数阶阻尼系统中，CDDR 成功构建了可达集，而基于 Lipschitz 常数的方法完全失效。

5. 意义与结论

理论意义：
CDDR 填补了数据驱动可达性分析中“未知噪声分布”与“强形式化保证”之间的空白。它证明了无需知道噪声界限或系统 Lipschitz 常数，仅依靠 i.i.d. 轨迹假设，即可通过 LTT 获得强概率保证。

实际应用价值：

• 安全性验证： 为缺乏精确模型或噪声特性未知的复杂系统（如自动驾驶、机器人控制）提供了可靠的安全证书。
• 鲁棒性： 能够处理重尾分布、非高斯噪声以及非光滑动力学，适应性强。
• 计算效率： 基于 Zonotope 的表示和传播保证了计算的高效性，实验显示在标准桌面计算机上运行时间极短。

未来方向：
包括非平稳环境下的自适应校准、缓解 Bonferroni 校正保守性的轨迹级分数设计、与安全规划控制的集成，以及扩展到非凸可达集。

总结：
CDDR 是一种强大的、分布无关的、模型无关的数据驱动可达性分析框架，它通过引入 LTT 校准和创新的分数设计，在保持严格 PAC 保证的同时，显著提升了可达集计算的精度和适用性。