Importance Sampling for Event Discovery via Guesswork

技术摘要：通过猜谜（Guesswork）进行事件发现的重要性采样

问题陈述
传统的重要性采样（Importance Sampling, IS）旨在通过最小化估计量的方差来估计稀有事件的概率。然而，许多现代应用（例如安全审计、压力测试）优先考虑的是快速发现：即尽可能快地生成稀有集合 $A_n$ 中的特定轨迹，而非估计该集合的总概率质量。

这种从“估计”到“生成”的转变需要不同的设计原则。其主要指标变成了命中时间 $\tau_{A_n} := \inf\{t \ge 1 : Y^n_t \in A_n\}$，其中 $Y^n_t$ 是从提议分布 $q_n$ 中抽取的样本。虽然最小化命中时间指数 $J_{hit}(q_n)$ 可以确保在亚指数时间内发现事件，但许多不同的提议分布都可以满足这一条件。本文指出存在一个差距：经典的 IS 选择最小化与稀有集合的 KL 散度 $D(Q\|p)$ 的提议分布（侧重于“质量主导型”），但这并不一定能产生在名义模型 $p$ 定义的搜索顺序下最高效的发现。

方法论与框架
本文将**发现质量（Quality of Discovery）**问题进行了形式化。目标是寻找一个提议分布 $q_n$，使其能够：

1. 确保亚指数级的命中时间（$J_{hit}(q_n) = 0$）。
2. 最小化在名义模型 $p$ 下被发现轨迹的描述长度（或惊异度/surprisal）。

作者建立了这一优化问题与猜谜（Guesswork）之间的理论桥梁。猜谜衡量了通过顺序查询识别随机向量实现过程所需的搜索工作量，通常查询按概率降序排列。核心见解是：最小化被发现轨迹的期望描述长度，等价于最小化名义秩指数（nominal rank exponent）（或猜谜指数）。

对于以类型集 $\Gamma$ 定义稀有集的 i.i.d. 模型，本文推导出了最优提议分布 $Q^*_{GW}$。与经典 IS 针对 $Q^*_{IS} = \arg\min_{Q \in \Gamma} D(Q\|p)$ 不同，猜谜最优的提议分布为：
$$Q^*_{GW} \in \arg\min_{Q \in \Gamma} [H(Q) + D(Q\|p)]$$
其中 $H(Q)$ 是提议类型的熵。该目标函数代表了猜谜的基本指数，支配着在按概率排序的搜索中的序列秩。

主要贡献与结果

1. 发现质量的形式化： 本文定义了一个关注个体轨迹属性而非集合整体的 IS 性能指标。本文证明了最小化名义模型下的期望描述长度，等价于最小化猜谜指数。
2. 推导最优提议： 对于 i.i.d. 模型和由类型定义的稀有集，本文推导出了 $Q^*_{GW}$ 作为最优解。研究表明，虽然经典 IS 最小化 KL 散度（侧重于稀有集合中最可能的区域），但发现最优性要求最小化熵与 KL 散度的之和。这确保了被发现的序列是相对于名义模型的搜索顺序而言“最不令人惊讶”的代表。
3. 词典序决胜（Lexicographic Tie-Breaking）： 在存在预算约束（即提议必须满足 $D(Q\|p) \le \delta$）或当多个提议具有相同命中时间的情况下，猜谜指数充当了词典序决胜工具。本文展示了 $Q^*_{GW}$ 如何在 KL 等价的边界点之间打破对称性，选择在允许集合内最小化搜索深度（秩）的类型。
4. 算法实现： 本文提出了算法 1，一种猜谜引导的事件发现程序。该算法涉及求解关于 $Q^*_{GW}$ 的优化问题，构建乘积形式的提议，并进行采样直到找到目标集合中的轨迹。理论分析确认了该方法实现了亚指数级命中时间和渐近秩最优性。

意义与主张
本文声称为基于发现的采样提供了一个“基本蓝图”。作者认为，在精确数学解难以触及的高维系统中，该框架指导了如何选择那些针对“最易发现”轨迹而非仅仅是“最可能区域”的提议。

作者强调，最快命中目标集的方法并不一定是理解该集性的最佳方式。通过优化“发现质量”，该框架确保了模拟事件（如系统故障）不仅能被快速发现，而且是根据系统原始规则而言最具代表性和“可信度”的示例。这在随机采样与系统化搜索（如基于列表的猜谜）之间建立了正式的桥梁，将范式从方差缩减转向了搜索效率与轨迹质量。

本文明确指出，i.i.d. 设置作为一个概念性的原型验证（proof-of-concept），旨在将猜谜指数从大偏差指数中分离出来，从而为处理由复杂路径定义的更复杂的模型提供清晰的目标。