判別適合的損失


金森敬文「統計的学習理論」（講談社）他[^1]の内容を元にまとめる。

[^1]: Bartlett, Peter L., Michael I. Jordan, and Jon D. McAuliffe. "Convexity, classification, and risk bounds." Journal of the American Statistical Association 101.473 (2006): 138-156.

# 概要

* リスク $R(f)$ を小さくする判別関数 $f$ を見つけたい
* $R(f)$ の代わりに $R_\phi(f)$ を小さくする $f$ を見つけてもよい
  * ただし、$\phi$ が判別適合的であることが条件

# 準備

## 与えられるもの

* 確率空間 $(\Omega, F, P)$
* 確率変数 $X: \Omega \to \mathcal{X}$
* 確率変数 $Y: \Omega \to  \\{-1, +1 \\}$[^2]

[^2]: ここでは2値分類のみ考える。

## 求めたいもの

 * $f: \mathcal{X} \to \mathbb{R}$ （判別関数）[^3]

[^3]: 仮説 $h$ との関係は $h(X) = \text{sign} (f(X))$ 。


## 満たしたい条件
  * $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の関数のため、扱いにくそうに見える）

[^3]: $\text{step}(x)$ は $x < 0$ で 0、 $x \geq 0$ で 1 をとる関数。
## 例

### 確率変数

```math
\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)$ を小さくすることを考える。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/69845567-2410-0899-bad0-b243c67aff3e.png)

### リスク

```math
\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}
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/ec33cd24-642f-08e9-e092-de45e490f8a4.png)

$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}$$

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/fa2532be-375e-0994-96d6-8322f66cb648.png)


```math
\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}
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/f49515a2-97e9-20ef-51a8-60eed1f82737.png)

$R(f)$ と比較すると:

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/62881b98-1d76-e84e-09ed-87a3d42a2f85.png)

$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)$ の要素になっている:

```math
\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}$の場合:

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/a51fd9bb-8e7e-b01b-4f21-86e6eaf131e4.png)

## 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}$の場合:

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/1ae53c88-44bb-b1db-f0f7-664b078beba1.png)

## ψ

$$\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}$の場合:

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/d7e342a6-eb6d-a2cc-dd4f-8667eb57487d.png)

$\psi$ が凸関数の場合、 $\psi_0 = \psi$ 。

この場合の$\psi(R(f) - R^\*)$ と $R_\phi(f) - R_\phi^\*$:

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/560904/64eede36-1dcd-f682-57bf-84e530b9159e.png)

青線がオレンジ線の下側にきていて、定理が成り立っていることがわかる。

# 悪いφの例

$\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$$