3 Selection with Guaranteed Risk Control

訳文

本節では, 与えられた分類器 $f$ と $f$ に対する信頼度関数 $ \kappa_f : X \rightarrow {\mathbb R}^+ $ に基づいて, 性能が保証された選択関数を構築する一般的な手法を示す. $\kappa_f$ については何も想定しておらず, $x_1, x_2 \in X$ については $\kappa_f (x_1) \geq \kappa_f (x_2)$ であれば, 信頼関数 $\kappa_f$ が予測 $f(x_2)$ の信頼度が予測 $f(x_1)$ の信頼度よりも高くないことを示しているという意味で, $\kappa$ はランク付けができるという解釈である. このセクションでは, 良い $\kappa_f$ とは何かという問題には関心がない (セクション 4 で説明する); 私たちの目標は, 与えられた $g$ のパフォーマンスが保証された選択関数 $\kappa_f$ を生成することである.
本論文では, (特に明記されていない限り) 損失関数 $\ell$ は, 標準的な $0/1$ 損失関数とする. $S_m = \{(x_i , y_i)\}^m_{i=1} \subseteq ({\cal X} \times {\cal Y})^m$ を未知分布 $P(X, Y)$ から i.i.d. サンプリングされたと仮定した学習集合とする. また, 信頼度パラメータ $\delta > 0$ と希望するリスク目標 $r^* > 0$ が与えられている. $S_m$ に基づいて, 分類器 $(f, g)$ の選択リスクが (2) を満たすような選択関数 $g$ を学習することを目標とする.
$\theta > 0$ については, 選択関数 $g_θ : {\cal X} \rightarrow \{0, 1\}$ を次のように定義する

g_\theta(x) = g_\theta(x|\kappa_f) \triangleq \left\{
\begin{array}{ll}
1, & {\rm if} \ \kappa_f(x) \geq \theta \ ; \\
0, & {\rm otherwise}.
\end{array}
\right. \tag{3}

任意の選択的分類器 $(f, g)$ について, ラベル付きサンプル $S_m$ に関して, その経験的な選択的リスクを定義する,

$$\hat{r}(f, g|S_m) \triangleq \frac{\frac{1}{m} \sum^m_{i=1} \ell(f(x_i), y_i)g(x_i)}{\hat{\phi} (f, g|S_m)},$$

ここで, $\hat{\phi}$ は経験的カバレッジ, $\hat{\phi}(f, g|S_m) \triangleq \frac{1}{m} \sum^m_{i=1}g(x_i)$. 任意の選択関数 $g$ について, $S_m$, $g(S_m) \triangleq \{(x, y) \in S_m : g(x) = 1\}$ の $g$ 射影を $g(S_m)$ とする.
リスクが保証された選択 (SGR) 学習アルゴリズムは, アルゴリズム 1 である. アルゴリズムは, 入力として, 分類器$f$, 信頼度関数 $\kappa_f$, 信頼度パラメータ $\delta > 0$, 目標リスク $ r^* $, および学習集合 $S_m$ を受け取る. このアルゴリズムは, 必要なリスクを十分な信頼性で保証する最適境界を見つけるためにバイナリ探索を実行する. SGR アルゴリズムは, 選択的な分類器 $(f, g)$ とリスク境界 $ b^* $ を出力する. この節の残りの部分では, SGR アルゴリズムを分析する. これは, ラベル付けされた標本に対する検定に基づいて, 単一の分類器に対して可能な限り厳しい数値一般化境界を与えるものである.

Lemma 3.1 (Gascuel and Caraux, 1992, [10]) $P$ を任意の分布とし, 分類器 $f$ の真の誤差が, ラベル付き集合 $ S_m $ に対して, $P$ から i.i.d. サンプリングされたものであるとする. $ B^* (\hat{r}_i, \delta, S_m) $ を次の式の解 $b$ とする.

$$ \sum_{j=0}^{m \cdot \hat{r}(f|S_m)} b^j \binom{m}{j} (1 - b)^{m - j} = \delta \tag{4}$$

ここで, $Pr_{S_m} \{R(f|P) > B^*(\hat{r}_i, \delta, S_m) \} < \delta $ である.

この設定では, Lemma 3.1 の数値的拘束が最もタイトであることを強調しておく. [10] で議論されているように, 例えば Hoeffding 不等式 (または他の濃度不等式) を用いて導出された解析的な境界は, この数値的な境界に近似しており, ある程度の緩みが生じている.
任意の選択関数 $g$ に対して, $P_g(X, Y)$ を $g$ に $P$ を射影したものとする. 次の定理は, SGR 手続きの一様収束の結果である.

Theorem 3.2 (SGR) $S_m$ を, $P$ から i.i.d. サンプリングしたラベル付き集合とし, SGR 手法の応用を考える. $k \triangleq [\log_2 m]$ について, $(f, g_i)$ と $b_i^*$, $i = 1, \ldots ,k$ を, SGR が $i$ 回目の反復で計算した選択的分類器と境界とする. すると, 以下のようになる.

$$ Pr_{S_m} \{\exists i:R(f|P_{g_i}) > B^*(\hat{r}_i, \delta/k, g_i(S_m)) \} < \delta $$

Proof Sketch:

原文

In this section, we present a general technique for constructing a selection function with guaranteed performance, based on a given classifier $f$, and a confidence-rate function $ \kappa_f : X \rightarrow {\mathbb R}^+ $ for $f$. We do not assume anything on $\kappa_f$, and the interpretation is that $\kappa$ can rank in the sense that if $\kappa_f (x_1) \geq \kappa_f (x_2)$, for $x_1, x_2 \in X$, the confidence function $\kappa_f$ indicates that the confidence in the prediction $f(x_2)$ is not higher than the confidence in the prediction $f(x_1)$. In this section we are not concerned with the question of what is a good $\kappa_f$ (which is discussed in Section 4); our goal is to generate a selection function $g$, with guaranteed performance for a given $\kappa_f$.
For the reminder of this paper, the loss function $\ell$ is taken to be the standard $0/1$ loss function (unless explicitly mentioned otherwise). Let $S_m = \{(x_i , y_i)\}^m_{i=1} \subseteq ({\cal X} \times {\cal Y})^m$ be a training set, assumed to be sampled i.i.d. from an unknown distribution $P(X, Y)$. Given also are a confidence parameter $\delta > 0$, and a desired risk target $r^* > 0$. Based on $S_m$, our goal is to learn a selection function $g$ such that the selective risk of the classifier $(f, g)$ satisfies (2).
For $\theta > 0$, we define the selection function $g_θ : {\cal X} \rightarrow \{0, 1\}$ as

g_\theta(x) = g_\theta(x|\kappa_f) \triangleq \left\{
\begin{array}{ll}
1, & {\rm if} \ \kappa_f(x) \geq \theta \ ; \\
0, & {\rm otherwise}.
\end{array}
\right. \tag{3}

For any selective classifier $(f, g)$, we define its empirical selective risk with respect to the labeled sample $S_m$,

$$\hat{r}(f, g|S_m) \triangleq \frac{\frac{1}{m} \sum^m_{i=1} \ell(f(x_i), y_i)g(x_i)}{\hat{\phi} (f, g|S_m)},$$

where $\hat{\phi}$ is the empirical coverage, $\hat{\phi}(f, g|S_m) \triangleq \frac{1}{m} \sum^m_{i=1}g(x_i)$. For any selection function $g$, denote by $g(S_m)$ the $g$-projection of $S_m$, $g(S_m) \triangleq \{(x, y) \in S_m : g(x) = 1\}$.
The selection with guaranteed risk (SGR) learning algorithm appears in Algorithm 1. The algorithm receives as input a classifier $f$, a confidence-rate function $\kappa_f$ , a confidence parameter $\delta > 0$, a target risk $ r^* $ , and a training set $S_m$. The algorithm performs a binary search to find the optimal bound guaranteeing the required risk with sufficient confidence. The SGR algorithm outputs a selective classifier $(f, g)$ and a risk bound $ b^* $ . In the rest of this section we analyze the SGR algorithm. We make use of the following lemma, which gives the tightest possible numerical generalization bound for a single classifier, based on a test over a labeled sample.

Lemma 3.1 (Gascuel and Caraux, 1992, [10]) Let $P$ be any distribution and consider a classifier $f$ whose true error w.r.t. to the labeled set $ S_m $, sampled i.i.d. from $P$. Let $ B^* (\hat{r}_i, \delta, S_m) $ be the solution $b$ of the following equation,

$$ \sum_{j=0}^{m \cdot \hat{r}(f|S_m)} b^j \binom{m}{j} (1 - b)^{m - j} = \delta \tag{4}$$

Then, $Pr_{S_m} \{R(f|P) > B^*(\hat{r}_i, \delta, S_m) \} < \delta $.

We emphasize that the numerical bound of Lemma 3.1 is the tightest possible in this setting. As discussed in [10], the analytic bounds derived using, e.g., Hoeffding inequality (or other concentration inequalities), approximate this numerical bound and incur some slack.
For any selection function, $g$, let $P_g(X, Y)$ be the projection of $P$ over $g$; that is, $P_g(X, Y) \triangleq P(X, Y|g(X)=1)$. The following theorem is a uniform convergence result for the SGR procedure.

Theorem 3.2 (SGR) Let $S_m$ be a given labeled set, sampled i.i.d. from $P$, and consider an application of the SGR procedure. For $k \triangleq [\log_2 m]$, let $(f, g_i)$ and $b_i^*$, $i = 1, \ldots ,k$, be the selective classifier and bound computed by SGR in its $i$th iterations. Then,

$$ Pr_{S_m} \{\exists i:R(f|P_{g_i}) > B^*(\hat{r}_i, \delta/k, g_i(S_m)) \} < \delta $$

Proof Sketch: For any $i=1, \ldots ,k$, let $m_i = |g_i(S_m)|$ be the random variable giving the size of accepted examples from $S_m$ on the $i$th iteration of SGR. For any fixed value of $0 \leq m_i \leq m $, by Lemma 3.1, applied with the the projected distribution $P_{g_i} (X, Y)$, and a sample $S_{m_i}$, consisting of $m_i$ examples drawn from the product distribution $(P_{g_i})^{m_i} $,

$$ Pr_{S_m \sim (P_{g_i})^{m_i}} \{R(f|P_{g_i}) > B^*(\hat{r}_i, \delta/k, g_i(S_m)) \} < \delta / k \tag{5} $$

The sampling distribution of $m_i$ labeled examples in SGR is determined by the following process: sample a set $S_m$ of m examples from the product distribution $P^m$ and then use $g_i$ to filter $S_m$, resulting in a (randon) number $m_i$ of examples. Therefore, the left-hand side of (5) equals

$$ Pr_{S_m \sim P^m} \{R(f|P_{g_i}) > B^*(\hat{r}_i, \delta/k, g_i (S_m)) | g_i (S_m) = m_i \}.$$

Clearly,

$$ R(f|P_{g_i}) = E_{P_{g_i}} [\ell(f(x), y)] = \frac{E_P [\ell(f(x), y)g(x)]}{\phi(f, g)} = R(f, g_i) .$$

Therefore,

$$ Pr_{S_m} \{ R(f, g_i) > B^* (\hat{r}_i, \delta / k, g_{i}(S_{m}) ) \} $$

$$ = \sum_{n=0}^{m} Pr_{S_m} \{ R(f, g_i) > B^* (\hat{r}_i, \delta/k, g_i (S_m)) | g_i (S_m) = n \} \cdot Pr \{ g_i (S_m) = n \} $$

$$ \leq \frac{\delta}{k} \sum_{n=0}^{m} Pr \{ g_i (S_m) = n \} = \frac{\delta}{k} $$

An application of the union bound completes the proof.