论文技术总结：$\epsilon$-邻域决策边界受控估计 (EDGE)

1. 研究背景与问题定义

在现实世界的工程应用（如安全性、质量和可行性评估）中，准确估计**黑盒系统（Black Box Systems）**的决策边界至关重要。然而，由于缺乏系统的显式数学表达式，无法通过解析方法定义决策边界，通常依赖采样方法。

现有方法存在以下主要局限性：

• 缺乏误差保证：现有的自适应采样方法（如主动学习）虽然能细化边界估计，但无法保证估计边界与真实边界的距离在用户指定的 $\epsilon$ 邻域内。
• 采样效率低：为了探索不确定性区域，现有方法往往在远离边界的区域进行不必要的采样，导致在评估成本高昂（如高保真仿真、物理实验）时效率低下。
• 超参数依赖：许多方法需要复杂的超参数调优，且性能受随机性影响较大。

核心问题：如何在黑盒二元分类器中，以最小的采样次数，构建一个保证位于真实决策边界 $\epsilon$ 邻域内的近似边界，且无需超参数调优？

2. 方法论：EDGE 算法

本文提出了 $\epsilon$-邻域决策边界受控估计 (EDGE) 算法。该算法是一种函数无关（Function-agnostic）且样本高效的方法，其核心思想基于中间值定理 (Intermediate Value Theorem, IVT)。

2.1 核心原理

• $\epsilon$-邻域定义：定义内部点集 $S_1$（$f(x)=1$）和外部点集 $S_0$（$f(x)=0$）。目标是找到两个点集 $\tilde{S}_1$ 和 $\tilde{S}_0$，使得它们分别位于真实边界 $\partial S$ 的 $\epsilon$ 距离内（即 $d(x, \partial S) \le \epsilon$）。
• 中间值定理应用：如果存在两点 $x_{in}$ 和 $x_{out}$ 分别属于 $S_1$ 和 $S_0$，且它们之间的距离 $\|x_{in} - x_{out}\| \le \epsilon$，则根据 IVT，真实决策边界必然穿过连接这两点的线段。这保证了采样点严格位于 $\epsilon$ 邻域内。

2.2 算法流程

EDGE 算法主要包含三个阶段：

1. 初始化与二分查找 (Bisection)：
   • 首先找到一个内部点 $x_{in}^0$ 和一个外部点 $x_{out}^0$。
   • 在连接这两点的线段上执行二分查找，直到两点间距离小于 $\epsilon$。此时得到的点对作为后续“行走”的起点。
2. 决策边界行走 (Decision Boundary Walk)：
   • 利用几何操作，以当前边界点为圆心、$\epsilon$ 为半径画圆。
   • 计算两个相邻边界点（一个来自 $\tilde{S}_1$，一个来自 $\tilde{S}_0$）对应圆的交点。
   • 根据叉积方向选择下一个测试点，查询其函数值，并将其归类为内部或外部点，添加到相应集合中。
   • 该过程沿边界两侧以 $\epsilon$ 步长推进，直到形成闭环或触及定义域边界。
3. 定义域边界处理 (Domain Boundary Walk)：
   • 如果测试点超出定义域 $X$，算法会沿定义域边界 $\partial X$ 进行 $\epsilon$ 步长行走，直到重新检测到决策边界，然后恢复决策边界行走。

2.3 算法特性

• 100% 采样效率：除了初始化阶段的二分查找外，所有采样点均被添加到边界近似集合中，无浪费。
• 无超参数：仅需用户指定 $\epsilon$（允许的误差范围），无需调整其他参数。
• 适用范围：目前主要针对二维黑盒系统。

3. 实验验证与结果

研究通过三个非线性基准测试函数和一个电力网格稳定性案例进行了验证。

3.1 案例研究：含可再生能源的电力网格

• 场景：评估 IEEE 5 节点系统中，两个可再生能源源（发电机 1 和 5）的功率注入范围，确保直流最优潮流（DC-OPF）约束不被违反。
• 结果：EDGE 成功描绘了可行域的边界。当 $\epsilon=0.01$ MW 时，仅需 2866 个样本；当 $\epsilon=0.1$ MW 时，仅需 282 个样本。

3.2 基准测试函数

• 测试函数：Rosenbrock, Goldenstein-Price, Beale 函数。
• 对比算法：
  1. 朴素网格采样 (Naïve Grid Sampling)：提供 $\epsilon$ 保证，但采样量巨大（$O(1/\epsilon^2)$）。
  2. 主动学习边界 (ALB)：基于支持向量机 (SVM) 的迭代方法，无 $\epsilon$ 保证，且受随机性影响大。

3.3 性能对比 (表 1 数据总结)

| 指标 | EDGE | 朴素网格 (Grid) | 主动学习 (ALB) |
| :--- | :--- | :--- | : |
| 平均表面距离 (ASD) | 极低 (接近理论最优) | 低 (但采样成本极高) | 较高 (波动大，受初始化影响) |
| 采样数量 | 极少 (随周长 $L/\epsilon$ 线性增长) | 极大 (随面积 $1/\epsilon^2$ 增长) | 中等，但需多次迭代 |
| 计算时间 | 极短 | 短 (但采样查询成本高) | 长 (SVM 核矩阵计算复杂度 $O(m^3)$) |
| $\epsilon$ 保证 | 有 | 有 | 无 |
| 随机性 | 无 | 无 | 高 (需多次重复实验) |

• 关键发现：
  • EDGE 的采样效率远超网格搜索（在相同 $\epsilon$ 下，样本量减少数个数量级）。
  • EDGE 的边界近似精度（ASD）优于 ALB，且结果稳定，无随机性。
  • ALB 虽然能逐步优化，但无法保证边界在 $\epsilon$ 邻域内，且计算开销大。

4. 主要贡献

1. 提出 EDGE 算法：一种基于 IVT 的几何采样算法，能够严格保证估计边界位于真实边界的 $\epsilon$ 邻域内。
2. 样本效率突破：通过仅在边界附近采样，避免了传统方法在安全/不安全区域内部的无效探索，实现了极高的采样效率。
3. 无需调优：算法仅需一个用户定义的 $\epsilon$ 参数，适用于各种黑盒系统特性。
4. 实证验证：在电力网格稳定性和多个非线性基准函数上证明了其优越性，特别是在处理高成本评估函数时。

5. 意义与未来展望

• 工程意义：为安全关键系统（如自动驾驶、电网控制、航空航天）提供了一种可靠、高效的边界评估工具，能够在有限的计算预算下提供确定性的误差边界。
• 理论意义：证明了在二维空间中，利用简单的几何操作（圆交点）结合 IVT 可以高效解决黑盒边界估计问题。
• 未来方向：
  • 扩展到高维空间（目前受限于二维几何操作）。
  • 处理多分类问题（分解为多个二分类子问题）。
  • 应用于含噪声的系统（利用 $\epsilon$ 吸收测量噪声）。
  • 将 EDGE 生成的边界点作为支持向量机 (SVM) 的训练集，以增强 SVM 的分类性能和稳定性。

总结：EDGE 算法通过巧妙的几何策略，在“采样效率”和“边界定位精度保证”之间取得了最佳平衡，解决了现有黑盒边界估计方法中效率低、无保证、需调参的痛点。