技術要約：$(\epsilon, \delta)$-正確なレベルセット推定と停止基準

問題定義

レベルセット推定（Level Set Estimation: LSE）は、未知の、かつ評価コストの高い関数 $f(x)$ が、指定された閾値 $\theta$ を超える（または下回る）領域を、候補集合の中から特定することを目的としている。能動学習戦略によって、必要な関数評価回数を最小化する手法が提案されてきたが、停止基準に関する理論的な定式化には大きな空白が存在する。

既存の手法は、多くの場合 $\epsilon$-正確な解（閾値の周囲にマージンを許容する解）を見つけるための逐次最適化に依存しているが、厳密な停止ルールを欠いている。一般的なアプローチには以下のようなものがある：

• 予算ベースの停止： 固定された実験回数の後に停止する。これは、リソースの浪費や精度の不足を招く可能性がある。
• Fスコアサンプリング（FS）： サンプリングされたFスコアのパーセンタイルが目標を超えたときに停止する。しかし、これには事前に達成可能な最大Fスコアを知っておく必要があるが、それは多くの場合不明確である。さらに、停止時点での実際のFスコアが目標を満たしていない場合があり、また、計算コストの高いサンプリングに依存している。
• 完全分類（FC）基準： すべての点が分類されたときにのみ停止する。これは、ノイズが存在する場合、閾値付近の点が永遠に「未決定」のままとなるため、終了できないことが多い。

本論文は、さらなる探索が改善をもたらす可能性が低いときにアルゴリズムを停止させ、不必要な評価を減らしつつ、精度に関する確率的な保証を提供することを確実にするために、理論的に裏付けられた停止基準を組み込んだ獲得戦略の必要性に対処している。

手法

1. ガウス過程フレームワーク

本手法は、ガウス過程回帰（GPR）を用いて未知の関数をモデル化する。与えられたデータセット $S_N$ に対して、新しい点 $x^*$ における関数値の事後分布は、ガウス分布 $N(\mu_N(x^*), \sigma_N^2(x^*))$ となる。

2. 提案される獲得関数

誤分類確率（$p_{min}(x)$）に基づく従来の獲得関数は、事後分散が高い点、または平均が閾値に近い点を選択する。著者らは、これが閾値の近くにある真の関数値（「マージン領域」）において冗長な探索を招き、収穫逓減を引き起こすと主張している。

これに対処するため、本論文ではマージン $\epsilon > 0$ を導入する。点 $x$ は、単に $f(x) \approx \theta$ であるときだけでなく、$f(x) \in (\theta - \epsilon/2, \theta + \epsilon/2]$ であるときも「分類が困難」であるとみなされる。目標は、推定された集合 $\tilde{H}_\theta$（上側）、$\tilde{L}_\theta$（下側）、および $\tilde{U}_\theta$（未決定／マージン）が、真の集合に対して特定の包含特性を満たすような $\epsilon$-正確性 を達成することである。

提案される獲得関数 $r_{min}(x)$ は次のように定義される：
$$r_{min}(x) = \min \{ \Pr(x \in H_\theta), \Pr(x \in L_\theta), \Pr(x \notin U_\theta) \}$$
ここで：

• $\Pr(x \in H_\theta)$ および $\Pr(x \in L_\theta)$ は、それぞれ上側および下側のレベルセットに属する確率である。
• $\Pr(x \notin U_\theta)$ は、関数値がマージン領域 $U_\theta = \{x \mid |f(x) - \theta| \le \epsilon/2\}$ の外側にある確率である。

アルゴリズムは、次の点 $x_{new} = \arg \max_{x \in X} r_{min}(x)$ を選択する。この関数は、分類が困難な点（$H_\theta$ または $L_\theta$ に属する確率が低い点）、あるいはマージン領域内に存在することに関する不確実性が高い点を優先する。極めて重要な点は、ある点が徹底的に探索され、事後分散が減少すると、その点がマージン内に存在する確率（$\Pr(x \in U_\theta)$）が増加し、結果として $\Pr(x \notin U_\theta)$ が減少することである。これにより、$\epsilon$ の許容範囲内で既に「解決済み」である点の獲得値が自然に低下し、無限ループを防ぐことができる。

3. 停止基準

アルゴリズムは、信頼パラメータ $\delta \in (0, 1)$ に対して以下の不等式が満たされたときに停止する：
$$1 - \sum_{x \in X} r_{min}(x) \ge \delta$$
この条件は、すべての候補点における「不確実性」（獲得値）の総和が十分に低いことを保証する。

4. 理論的保証

本論文は 定理 3.1 を証明している。分類ルールがそれぞれの確率を最大化することに基づいて点 $\tilde{H}_\theta, \tilde{L}_\theta, \tilde{U}_\theta$ を割り当てる場合、停止基準を満たしたとき、三つ組 $(\tilde{H}_\theta, \tilde{L}_\theta, \tilde{U}_\theta)$ は少なくとも確率 $\delta$ で $\epsilon$-正確である。

さらに、命題 3.2 は、この理論的保証が性能指標にも及ぶことを確立している。具体的には、Fスコア、精度（Accuracy）、再現率（Recall）、適合率（Precision）、および特異度（Specificity）は、確率 $1 - \sum r_{min}(x)$ で特定の条件下限を上回ることが保証される。サンプリングを通じてFスコアの下限を推定する従来の手法（Qing et al., 2022b）とは異なり、本手法は解析的な下限を提供する。

5. パラメータ選択

• $\delta$ (信頼度): 1に近い値（例：0.99）に設定する。停止時間は、1付近での $\delta$ の小さな変動に対して鈍感であることが示されている。
• $\epsilon$ (マージン): $\epsilon$ を直接設定する代わりに（$\epsilon$ は関数の範囲やノイズに依存するため）、パラメータ $L$（有効な観測数の最小値を表す）に基づいた適応的な手法を提案している。$\epsilon$ は事後分散 $\sigma_N(x)$ と $L$ から導出され、ノイズの分散や関数のスケールに対して頑健である。

主な貢献

1. 新しい獲得関数： 分類難易度の分布に基づく獲得関数であり、マージン領域を明示的に考慮することで、真の値が閾値に近い点における冗長な探索を防ぐ。
2. 理論的な停止基準： $(\epsilon, \delta)$-正確性を保証する停止ルール。アルゴリズムは、解が $\epsilon$-正確である確率が $1-\delta$ を超えたときに停止する。
3. 性能指標の保証： Fスコア、精度、再現率、適合率、および特異度の下限を、サンプリングなしで解析的に計算可能であることを示す理論的証明。
4. 計算効率： 停止基準は標準正規分布の累積分布関数（CDF）に依存しており、候補点の数に対して線形な計算量となる。これは、モンテカルロ・サンプリングにより二次的な計算量を必要とするFスコア・サンプリング法とは対照的である。

実験結果

本手法は、合成テスト関数（Rosenbrock, Branin, Cross in tray）およびシリコンインゴットにおける「レッドゾーン」（不純物領域）の推定を含む実世界のアプリケーションを用いて評価された。

• パフォーマンス： 提案手法は、既存の最先端の獲得関数（Straddle, MILE, RMILE, MELK, Uncertainty Sampling）と同等のFスコアを達成した。
• 停止効率：
  • 完全分類（FC）： ノイズの多い環境では、閾値付近の点が未決定のまま残るため、ほとんどの手法で停止に失敗した。
  • Fスコアサンプリング（FS）： Fスコアが収束する前に早期に停止したり、実用において決定が困難なターゲットFスコアの微調整を必要としたりすることが多かった。場合によっては、停止時点での実際のFスコアが希望の閾値を下回っていた。
  • 提案手法： 最終的な収束Fスコアの値に関わらず、十分な推定精度が得られた時点でアルゴリズムを正常に停止させた。問題固有の停止閾値のチューニングを必要とせず、異なるノイズレベルや関数形状に対して頑健性を示した。
• 実世界への応用： シリコンインゴットの実験において、提案手法は高いFスコアを維持しながらLSEプロセスを効果的に早期終了させたが、FC基準は予算を使い果たすまで継続した。

意義と主張

本論文は、レベルセット推定における決定的な欠陥、すなわち効果的で理論的に裏付けられた停止基準の欠如に対処していると主張している。$\epsilon$-正確さの概念を通じて停止条件を獲得戦略に直接組み込むことで、本手法は、さらなる探索が指定された許容範囲内での分類を改善する可能性が低いときにアルゴリズムを終了させることを保証する。

著者らは、本アプローチがレベルセット推定の精度と、標準的な性能指標の下限の両方に対して確率的な保証を提供することを強調している。これは、理論的な裏付けを欠いた既存のヒューリスティックまたはサンプリングベースの停止ルールとは対照的である。本手法は、実験のコストと時間が制約される適応的な実験設計における実用的なソリューションとして提示されており、研究者が結果が定義された精度基準を満たしているという確信を持って実験を終了できるようにするものである。著者らは、本手法が保守的であることを控えめに述べており（これは安全性が重視されるアプリケーションにおいては有益である）、これらの理論的保証とより積極的な停止とのバランスをとることは、今後の課題であるとしている。