『統計的学習理論』の第1章のメモ：2値判別問題におけるベイズ規則とベイズ誤差について

p.9 の定義 1.1 を引用する。

損失関数 $l$ を定めたとき、任意の可測関数 $h : \mathcal{X} \rightarrow \mathcal{Y}$ のもとでの予測損失の下限

$\begin{align*} \mathop{\rm inf} \limits_{h: \text{可測関数}} R(h) \end{align*}$

を、損失関数 $l$ のもとでのベイズ誤差（Bayes error）という。下限を達成する仮説が存在するとき、その仮説をベイズ規則（Bayes rule）という。

学習の目標は、学習データからベイズ規則を達成する仮説 $h_0$ を求める（推定する）ことである。

2値判別問題におけるベイズ規則は p.10 に記述が見つかる。すなわち、「入力 $x$ が与えられたとき、最も出現する確率が大きなラベルを予測ラベルとする仮説が最適」である。そこに書かれている内容で実質的な証明になっているが、もう少し整理しておきたい。

データの確率分布を $D$ とする。すなわち評価データは $(X, Y) \sim D$ のように分布するが、 $D$ を $Y$ に関して周辺化した分布を $D_{\mathcal{X}}$ と書く。さらに $X$ を固定したときの $Y$ の分布を $D_{Y \mid X}$ と書く。また 0-1 損失関数を $l_{\text{err}}$ と書き、そのときの予測損失（予測判別関数）を $R_{err}$ とする。任意の仮説 $h: \mathcal{X} \rightarrow \mathcal{Y}$ について、

$\begin{align*} R_{\text{err}}(h) &= \mathbb{E}_{(X, Y) \sim D} [ l_{\text{err}} (h(X), Y)] \\ &= \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \mathbb{E}_{Y\sim D_{Y \mid X}} [ l_{\text{err}} (h(X), Y) \mid X] ] \\ &= \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h(X) \neq Y ] ] ] \end{align*}$

となる。さらに期待値 $\mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h(X) \neq Y ] ]$ について、

$\begin{align*} \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h(X) \neq Y ] ] &= \mathrm{Pr}(Y =1 \mid X) \mathbf{1} [ h(X) =0 ] + \mathrm{Pr}(Y =0 \mid X) \mathbf{1} [ h(X) =1 ] \end{align*}$

と展開できる。ここで

$\begin{align*} \alpha_{X} = \mathrm{min} \{ \mathrm{Pr}(Y =1 \mid X), \mathrm{Pr}(Y =0 \mid X)\} \end{align*}$

と置いてみる。 $h(X) =0$ のとき期待値は $\mathrm{Pr}(Y =1 \mid X) \geq \alpha_{X}$ であり、また $h(X) =1$ のときも同様に $\mathrm{Pr}(Y =0 \mid X) \geq \alpha_{X}$ であるから、まとめると以下を得る。

$\begin{align*} \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h(X) \neq Y ] ] &\geq \alpha_{X} \end{align*}$

ゆえに

$\begin{align*} R_{\text{err}}(h) \geq \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \alpha_{X} ] \end{align*}$

であり、下限（下界）が得られた。

次に下限を達成する仮説が実際に存在することを示したい。式を簡略化するため、 $\mathrm{Pr}(Y =1 \mid X) = \beta_{X}$ とおく。 $X=x$ が与えられたとき、 $\beta_{X} \geq 1/2$ ならば $1$ を出力し、 $\beta_{X} \lt 1/2$ ならば $0$ を出力する仮説 $h_{0}$ を考えてみる。前者の条件は $\beta_{X} \geq 1- \beta_{X} = \mathrm{Pr}(Y =0 \mid X = x)$ と等価であり、後者は $\beta_{X} \lt 1- \beta_{X}$ と等価である。両者の条件付き確率が等確率ならば、どちらも $1/2$ である。予測損失は次式で与えられる。

$\begin{align*} R_{\text{err}}(h_{0}) &= \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h_0(X) \neq Y ] ] ] \end{align*}$

さらに期待値 $\mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h_{0}(X) \neq Y ] ]$ は

$\begin{align*} \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h_{0}(X) \neq Y ] ] &= \mathrm{Pr}(Y =1 \mid X) \cdot \mathbf{1} [\beta_X \lt 1/2 ] + \mathrm{Pr}(Y =0\mid X) \cdot \mathbf{1} [\beta_X \geq 1/2 ] \\ &= \beta_{X} \cdot \mathbf{1} [\beta_X \lt 1/2 ] + (1-\beta_{X})\cdot \mathbf{1} [\beta_X \geq 1/2 ] \\ &= \mathrm{min} \{\beta_X, 1-\beta_X \} \end{align*}$

であって、最右辺は $\alpha_{X}$ の定義そのものである。最終的に

$\begin{align*} R_{\text{err}}(h) \geq R_{\text{err}}(h_{0}) \end{align*}$

という不等式を得るが、これは $h_{0}$ が下限を達成する仮説すなわちベイズ規則であることを示している。

記号をテキストに合わせれば、ベイズ規則は次式で書くこともできる。

$\begin{align*} h_{0} (x) = \mathop{\mathrm{argmax}} \limits_{y \in \mathcal{Y}} \mathrm{Pr}(Y = y \mid X = x) \end{align*}$

さらにまた、

$\begin{align*} \alpha_{X} &= \mathrm{min} \{ \mathrm{Pr}(Y =1 \mid X), \mathrm{Pr}(Y =0 \mid X)\}\\ &= \mathop{\mathrm{min}} \limits_{y \in \mathcal{Y}} \mathrm{Pr}(Y =y \mid X)\\ &= 1- \mathop{\mathrm{max}} \limits_{y \in \mathcal{Y}} \mathrm{Pr}(Y =y \mid X) \end{align*}$

であるから、テキストの式 (1.2) の0-1損失関数 $l_{\text{err}}$ のもとでのベイズ誤差が次式で与えられることも分かる。

$\begin{align*} R_{\text{err}}^{*} = R_{\text{err}}(h_{0}) &= \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \mathbb{E}_{Y\sim D_{Y \mid X}} [ \mathbf{1} [ h_0(X) \neq Y ] ] ]\\ &= \mathbb{E}_{X\sim D_{\mathcal{X}}} [ \alpha_{X} ] \\ &= 1 - \mathbb{E}_{X\sim D_{\mathcal{X}}} \left[ \mathop{\mathrm{max}} \limits_{y \in \mathcal{Y}} \mathrm{Pr}(Y =y \mid X) \right] \end{align*}$

参考

統計解析特論-2016（講義資料 4） URL