数学、ときどき統計、ところによりIT

理論と実践の狭間で漂流する数学趣味人の記録

2 値判別問題

入力値に対してラベルを割り当てて複数のグループに振り分ける問題を判別問題と言います。特に 2 つのグループに振り分ける問題を 2 値判別問題と言います。例えば迷惑メールの振り分けは 2 値判別問題の典型例です。

今回は 2 値判別問題を機械学習の枠組みで定式化します。

 入力値全体を \mathcal{X}、出力値全体を \mathcal{Y}=\{-1,1\} とし*1 、入力値 x\in\mathcal{X} に対するラベル y\in\mathcal{Y} を仮説 h:\mathcal{X}\to\mathcal{Y} によって予測することを考えます。入力データ (x,y)\in\mathcal{X}\times\mathcal{Y} に対してh(x)y が同符号の場合、予測は的中し、異符号の場合、予測は外れたと判断します。

ここで解析を容易に行う為、(\mathcal{Y} に値を取る)仮説 h を直接求めることはせず、実数値関数 f:\mathcal{X}\to\mathbf{R}x\in\mathcal{X} での値 f(x) の符号 \mathrm{sign}(f(x)) により y\in\mathcal{Y} の符号を予測することを考えます。f(x)y が同符号(異符号)であることと \( yf(x)>0\) ( \( yf(x)<0\) ) を満たすことが同値であることに注意して、以下の言葉を定義します。

 定義 1 \mathcal{X} を入力値全体、\mathcal{Y}=\{-1,1\} を出力値全体、(x,y)\in\mathcal{X}\times\mathcal{Y} をデータ、\mathcal{H} を仮説集合とする。

  1. \mathrm{sign}\circ f\in\mathcal{H} となる可測関数 f:\mathcal{X}\to\mathbf{R} を判別関数と呼ぶ。
  2. 判別関数 f に対して yf(x) をマージンと呼ぶ。
  3. 判別関数 f 、非負値可測関数 \phi:\mathbf{R}\to\mathbf{R}_{\ge0} に対して \phi(yf(x))f\phi-マージン損失と呼ぶ。また \phi をマージン損失と呼ぶ。
  4. (\Omega,\mathcal{F},P) を確率空間、(X,Y):\Omega\to\mathcal{X}\times\mathcal{Y} をテストデータ、f を判別関数、\phi(yf(x))f\phi-マージン損失とする。このとき\[\begin{split}R_{\phi}(f) & :=E_{P}[\phi(Yf(X))]\\ & =\int_{\mathcal{X}\times\mathcal{Y}}\phi(yf(x))P^{(X,Y)}(d(x,y))\\ & =\int_{\mathcal{X}}P^{X}(dx)\int_{\mathcal{Y}}\phi(yf(x))P^{Y}(dy\,|\,x)\end{split}\]を判別関数 f の予測 \phi-損失と呼ぶ。

 

次のマージン損失は機械学習においてしばしば目にするものです。

  1. (0-1 マージン損失)\phi_{\mathrm{err}}(t)=1_{(- \infty,0] }(t).
  2. (ヒンジ損失)\phi(t)=\max\{1-t,0\}.
  3. (指数損失)\phi(t)=e^{-t}.
  4. (ロジスティック損失)\phi(t)=\log_{a}(1+e^{-t})、ただし \( a>1\) .

特に、2 値判別の観点から 0-1 マージン損失は重要です。実際、\[\phi_{\mathrm{err}}(yf(x))=\begin{cases}1, & yf(x)\le0,\\0, & yf(x)>0,\end{cases}\]より 0-1 マージン損失は判別関数 f が誤判別した場合の損失と解釈できます。従って 2 値判別問題において求めるべき判別関数 f は、テストデータに関して平均的に 0-1 マージン損失を最も小さくするもの、つまり R_{\mathrm{err}}(f):=R_{\phi_{\mathrm{err}}}(f) を極小にするものになります。

命題 2 f_{0}:=2\,P^{Y}(\{1\}\,|\,\cdot)-1f_{0,a}:=f_{0}+a\,1_{f^{-1}(\{0\})} (a\neq0) とする。このとき R_{\mathrm{err}}(f)f=f_{0,a} で最小となる。

証明 P^{Y}(\{1\}\,|\,\cdot) が条件付確率であるから -1\le f_{0}\le1 となることに注意する。\[\begin{split}R_{\mathrm{err}}(f) & =\int_{\mathcal{X}}P^{X}(dx)\int_{\mathcal{Y}}1_{(-\infty,0]}(yf(x) )P^{Y}(dy\,|\,x)\\ & =\int_{\mathcal{X}}\left(1_{(-\infty,0]}(f(x) )P^{Y}(\{1\}\,|\,x)+1_{(-\infty,0]}(-f(x) )P^{Y}(\{-1\}\,|\,x)\right)P^{X}(dx)\\ & =\int_{f^{-1}( (-\infty,0])}P^{Y}(\{1\}\,|\,x)P^{X}(dx) + \int_{f^{-1}([0,\infty) )}(1-P^{Y}(\{ 1 \}\,|\,x) )P^{X}(dx)\\ & =\int_{\mathcal{X}}\frac{1+f_{0}(x)}{2}P^{X}(dx) \\ & \qquad+\int_{f^{-1}(\{0\})}\frac{1-f_{0}(x)}{2}P^{X}(dx) -\int_{f^{-1}( (0,\infty) )}f_{0}(x)P^{X}(dx).\end{split}\]

f=f_{0,a} とすると f_{0,a}^{-1}(\{0\})=\emptyset より \[R_{\mathrm{err}}(f_{0,a})=\int_{\mathcal{X}}\frac{1+f_{0}(x)}{2}P^{X}(dx)-\int_{f_{0}^{-1}( (0,1])}f_{0}(x)P^{X}(dx).\]

ここで f(x)f_{0}(x) が異符号となる x\in\mathcal{X} 全体を \Delta(f,f_{0})とする。つまり\begin{gather*}\Delta_{+}(f,f_{0}):=f^{-1}( (-\infty,0) )\cap f_{0}^{-1}( (0,1])\\\Delta_{-}(f,f_{0}):=f^{-1}( (0,\infty) )\cap f_{0}^{-1}([-1,0) )\\\Delta(f,f_{0}):=\Delta_{+}(f,f_{0})\cup\Delta_{-}(f,f_{0}).\end{gather*}

このとき任意の判別関数 f に対して \[\begin{split}R_{\mathrm{err}}(f) & -R_{\mathrm{err}}(f_{0,a})\\= & \int_{f^{-1}(\{0\})}\frac{1-f_{0}(x)}{2}P^{X}(dx)\\ & \qquad +\int_{\Delta_{+}(f,f_{0})}f_{0}(x)P^{X}(dx)+\int_{\Delta_{-}(f,f_{0})}(-f_{0}(x) )P^{X}(dx)\\= & \int_{f^{-1}(\{0\})}\frac{1-f_{0}(x)}{2}P^{X}(dx)+\int_{\Delta(f,f_{0})}|f_{0}(x)|P^{X}(dx)\\\ge & 0\end{split}\]となり、 R_{\mathrm{err}}(f)f=f_{0,a} で最小となる。(証明終)

 

さて、以降の議論において次を仮定します。 

仮定 判別関数 fP^{X}(f^{-1}(\{0\}) )=0 を満たす。

 もし \( P^{X}(f^{-1}(\{0\}) )>0 \) とすると f により正負が判別できない x\in\mathcal{X}が分布 P^{X} に関して無視できない程多数存在していることを表しています。そのような f を判別に用いることは適切では無いため、求めるべき判別関数fP^{X}(f^{-1}(\{0\}) )=0 の制約を課すことにします。

この仮定の下、任意の判別関数 f に対して次式が成り立ちます。

\begin{equation}R_{\mathrm{err}}(f)-\inf_{f\,'\in L^{0}(\mathcal{X})}R_{\mathrm{err}}(f\,')=\int_{\mathcal{X}}1_{\Delta(f,f_{0})}(x)|f_{0}(x)|P^{X}(dx).\label{eq:diff_predictive_0-1_margin_loss}\end{equation}なお f_{0} について P^{X}(f_{0}^{-1}(\{0\}) )=0 とは限りませんが、もし P^{X}(f_{0}^{-1}(\{0\}) )=0 ならば f_{0,a}=f_{0} となります。

 

次回に続きます。

*1:ラベルの集合は問題に応じて(主に利便性の観点から)設定されます。