2 値判別問題
入力値に対してラベルを割り当てて複数のグループに振り分ける問題を判別問題と言います。特に 2 つのグループに振り分ける問題を 2 値判別問題と言います。例えば迷惑メールの振り分けは 2 値判別問題の典型例です。
今回は 2 値判別問題を機械学習の枠組みで定式化します。
入力値全体を 、出力値全体を とし*1 、入力値 に対するラベル を仮説 によって予測することを考えます。入力データ に対して と が同符号の場合、予測は的中し、異符号の場合、予測は外れたと判断します。
ここで解析を容易に行う為、( に値を取る)仮説 を直接求めることはせず、実数値関数 の での値 の符号 により の符号を予測することを考えます。 と が同符号(異符号)であることと ( ) を満たすことが同値であることに注意して、以下の言葉を定義します。
定義 1 を入力値全体、 を出力値全体、 をデータ、 を仮説集合とする。
- となる可測関数 を判別関数と呼ぶ。
- 判別関数 に対して をマージンと呼ぶ。
- 判別関数 、非負値可測関数 に対して を の -マージン損失と呼ぶ。また をマージン損失と呼ぶ。
- を確率空間、 をテストデータ、 を判別関数、 を の-マージン損失とする。このとき\begin{equation*}\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}\end{equation*}を判別関数 の予測 -損失と呼ぶ。
次のマージン損失は機械学習においてしばしば目にするものです。
- (0-1 マージン損失)
- (ヒンジ損失)
- (指数損失)
- (ロジスティック損失)、ただし .
特に、2 値判別の観点から 0-1 マージン損失は重要です。実際、\begin{equation*}\phi_{\mathrm{err}}(yf(x))=\begin{cases}1, & yf(x)\le0,\\0, & yf(x)>0,\end{cases}\end{equation*}より 0-1 マージン損失は判別関数 が誤判別した場合の損失と解釈できます。従って 2 値判別問題において求めるべき判別関数 は、テストデータに関して平均的に 0-1 マージン損失を最も小さくするもの、つまり を極小にするものになります。
命題 2 、 () とする。このとき は で最小となる。
証明 が条件付確率であるから となることに注意する。\begin{equation*}\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}\end{equation*}
とすると より
ここで と が異符号となる 全体を とする。つまり\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*}
このとき任意の判別関数 に対して \begin{equation*} \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} \end{equation*}となり、 は で最小となる。(証明終)
さて、以降の議論において次を仮定します。
仮定 判別関数 は を満たす。
もし とすると により正負が判別できない が分布 に関して無視できない程多数存在していることを表しています。そのような を判別に用いることは適切では無いため、求めるべき判別関数 に の制約を課すことにします。
この仮定の下、任意の判別関数 に対して次式が成り立ちます。
\begin{equation}R_{\mathrm{err}}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g)=\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}なお について とは限りませんが、もし ならば となります。
次回に続きます。
*1:ラベルの集合は問題に応じて(主に利便性の観点から)設定されます。