金森敬文「統計的学習理論」（講談社）他1の内容を元にまとめる。
概要
- リスク $R(f)$ を小さくする判別関数 $f$ を見つけたい
- $R(f)$ の代わりに $R_\phi(f)$ を小さくする $f$ を見つけてもよい
- ただし、$\phi$ が判別適合的であることが条件
準備
与えられるもの
- 確率空間 $(\Omega, F, P)$
- 確率変数 $X: \Omega \to \mathcal{X}$
- 確率変数 $Y: \Omega \to \{-1, +1 \}$2
求めたいもの
- $f: \mathcal{X} \to \mathbb{R}$ （判別関数）3
満たしたい条件
- $R(f) := \mathbb{E}[Y \not = \text{sign}(f(X)]$ (リスク)を最小化
- ここで $y \not = x$ は、 $y \not = x$ なら 1, そうでなければ 0 の意味
参考: 以下へ書き直せる3:
$R(f) = \mathbb{E}[\text{step}(-Y f(X))]$
（不連続でいたるところで微分が0の関数のため、扱いにくそうに見える）
例
確率変数
\begin{align}
P(X=0, Y=+1) &= 0/6\\
P(X=0, Y=-1) &= 3/6\\
P(X=1, Y=+1) &= 2/6\\
P(X=1, Y=-1) &= 1/6
\end{align}
判別関数
$$f_b(X) := X + b$$
この $b$ を調整してリスク $R(f_b)$ を小さくすることを考える。
リスク
\begin{align}
R(f_b) = & \mathbb{E}[Y \not = \text{sign}(f(X)]\\
= & P(X=0, Y=+1) \times (+1 \not = \text{sign}(1 + b))\\
& P(X=0, Y=-1) \times (-1 \not = \text{sign}(1 + b))\\
& P(X=1, Y=+1) \times (+1 \not = \text{sign}(2 + b))\\
& P(X=1, Y=-1) \times (-1 \not = \text{sign}(2 + b))\\
= & 0/6 \times ((1 + b) < 0)\\
& 3/6 \times ((1 + b) \geq 0)\\
& 2/6 \times ((2 + b) < 0)\\
& 1/6 \times ((2 + b) \geq 0)\\
\end{align}
$R(f)$ は $f$ の変化に対して不連続な部分があったり、変化がない領域があったりと、扱いが悪そう。代わりに扱い良いφ-リスクを以下で導入する。
φ-リスク
定義
- $\phi: \mathbb{R} \to [0, \infty)$
- $R_\phi(f) := \mathbb{E}[\phi((Y f(X))]$ （φ-リスク）
- $Y f(X)$をマージンと呼ぶ
例（φが指数損失）
$$\phi(m) = e^{-m}$$
\begin{align}
R_\phi(f_b) = & \mathbb{E}[\phi(Y (f(X))]\\
= & P(X=0, Y=+1) \times (\phi(+1 (1 + b))\\
& P(X=0, Y=-1) \times (\phi(-1 (1 + b))\\
& P(X=1, Y=+1) \times (\phi(+1 (2 + b))\\
& P(X=1, Y=-1) \times (\phi(-1 (2 + b))\\
= & 0/6 \times (\exp(-1 - b))\\
& 3/6 \times (\exp(+1 + b))\\
& 2/6 \times (\exp(-2 - b))\\
& 1/6 \times (\exp(+2 + b))\\
\end{align}
$R(f)$ と比較すると:
$R_\phi(f)$ が $R(f)$ の上界を与える。その定量的な関係をみていく。
ψ変換
$R_\phi(f)$ と $R(f)$ の関係は、以下が証明できる。
$$\psi (R(f) - R^*) \leq R_\phi (f) - R_\phi^*$$
ここで:
$$R^* := \inf_{f} R(f)$$
$$R_\phi^* := \inf_{f} R_\phi(f)$$
$\psi$ は $\phi$ が変換された関数:
$$\phi(m) \to C(\eta, f) \to H(\eta), H^-(\eta) \to \psi(\theta)$$
それぞれの定義を順にみていく。
C (条件付きφ-リスク)
定義:
$$C(\eta, \alpha) := \eta \phi(\alpha) + (1 - \eta) \phi(-\alpha)$$
これは、 $R_\phi(f)$ の要素になっている:
\begin{align}
R_\phi(f) &= \mathbb{E}[\mathbb{E}[\phi(Y f(x))|X]] \\
&= \mathbb{E}[P(Y=+1|X)(\phi(f(x))) + P(Y=-1|X)(-\phi(f(x)))] \\
&= \mathbb{E}[C(P(Y=+1|X), f(x))]
\end{align}
例: $\phi(m) = e^{-m}$の場合:
H, Hマイナス
$$H(\eta) := \inf_{\alpha \in \mathbb{R}} C(\eta, \alpha)$$
$$H^-(\eta) := \inf_{\alpha: \alpha(\eta - 1/2) \leq 0} C(\eta, \alpha)$$
例: $\phi(m) = e^{-m}$の場合:
ψ
$$\psi_0(\theta) := H^-\left(\frac{1 + \theta}{2}\right) - H\left(\frac{1 + \theta}{2}\right)$$
$$\psi := \text{convex hull of } \psi_0$$
例: $\phi(m) = e^{-m}$の場合:
$\psi$ が凸関数の場合、 $\psi_0 = \psi$ 。
この場合の$\psi(R(f) - R^*)$ と $R_\phi(f) - R_\phi^*$:
青線がオレンジ線の下側にきていて、定理が成り立っていることがわかる。
悪いφの例
$\psi(\theta) = 0$ の様な場合には、$R_\phi(f) - R_\phi^*$ を小さくしても $R(f) - R^*$ が小さくなることが保証できない。例えば以下。
$$\phi(\alpha) = \max \{-\alpha, 0\}\
\Rightarrow \psi(\theta) = 0$$
良いφの条件
任意の関数列 $f_1, f_2, \cdots$ について
$$\lim_{i \to \infty}R_\phi(f_i) = R_\phi^* \Rightarrow \lim_{i \to \infty}R(f_i) = R^*$$
なら、$R_\phi(f)$ を小さくすれば $R(f)$ も小さくなるので、上記を満たせるφは素性が良い。
これは、以下と同値（証明できる）。
$$H^-(\eta) > H(\eta) \quad (\forall \eta \not = 1/2)$$
この時 $\phi$ が判別適合的と言う。
また、 $\phi$ が凸関数の場合は、判別適合的であることは以下と同値（証明できる）。
$$\phi^{\prime}(0) < 0$$