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

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

2 値判別問題における代理損失と判別適合性

今回は 2 値判別問題に代理損失を用いることの正当性について考えることにします。

記号は前回定義したものを断りなく使用します。

前回の議論から予測 \phi_{\mathrm{err}}-損失にはベイズ規則が存在し、ベイズ規則を条件付確率で表現することができました。機械学習の一般論に従えば、現時点で入手可能な教師データを使って予測 \phi_{\mathrm{err}}-損失の推定量を考えて、学習アルゴリズムによってその損失を最小化する仮説(推定量)を求め、直接得ることが出来ないベイズ規則の代わりに用いる、というようになるのですが、0-1 損失を最小化する方法は 2^{n} 通りある判別方法を総当たりで調べる以外の良い方法が知られていません。そこで \phi_{\mathrm{err}}-損失の代わりとなる損失(これを代理損失と言います)を用いて 2 値判別を行うということが機械学習では良く行われています。

2 値判別に代理損失を用いることの正当性について考えるために、まずは予測 \phi-損失 R_{\phi}(f) により予測 \phi_{\mathrm{err}}-損失 R_{\mathrm{err}}(f) を上から評価することを目標とします。

\displaystyle C_{\eta}(\alpha):=\frac{1+\eta}{2}\phi(\alpha)+\frac{1-\eta}{2}\phi (-\alpha), \quad \eta \in [-1,1],\,\alpha \in \mathbf{R}

と置くと

\begin{equation*}\begin{split}R_{\phi}(f) & =\int_{\mathcal{X}}\left(\phi(f(x) )P^{Y}(\{1\}\,|\,x)+\phi(-f(x) )P^{Y}(\{-1\}\,|\,x)\right)P^{X}(dx)\\ & =\int_{\mathcal{X}}C_{f_{0}(x)}(f(x) )P^{X}(dx)\end{split}\end{equation*}と書けます。オーマンの可測選択定理より

 \inf_{g \in L^{0}(\mathcal{X})}\int_{\mathcal{X}}C_{f_{0}(x)}(g(x) )P^{X}(dx)=\int_{\mathcal{X}}\inf_{\alpha\in\mathbf{R}}C_{f_{0}(x)}(\alpha)P^{X}(dx)

が成り立つことから次式を得ます。

 R_{\phi}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\phi}(g)=\int_{\mathcal{X}}\left(C_{f_{0}(x)}(f(x) )-\inf_{\alpha\in\mathbf{R}}C_{f_{0}(x)}(\alpha)\right)P^{X}(dx).

ここで右辺の被積分関数が非負であることと(R_{\mathrm{err}}(f)を上から評価することが今の目標であることから)前回の式 (1) に注意して\begin{equation}R_{\phi}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\phi}(g)\ge\int_{\Delta(f,f_{0})}\left(C_{f_{0}(x)}(f(x) )-\inf_{\alpha\in\mathbf{R}}C_{f_{0}(x)}(\alpha)\right)P^{X}(dx).\label{eq:estimation_for_diff_predictive_phi_margin_loss}\end{equation}式 \eqref{eq:estimation_for_diff_predictive_phi_margin_loss} の右辺の被積分関数に注目し、次の補題を考えます。

補題 1 [-1,1] 上の関数 \psi_{0}

\displaystyle \psi_{0}(\eta):=\inf_{\alpha\in\mathbf{R};\alpha\eta\le0}C_{\eta}(\alpha)-\inf_{\alpha\in\mathbf{R}}C_{\eta}(\alpha),\quad\eta\in[-1,1 ]

とし、 \psi_{0}\ge\widetilde{\psi} を満たす [-1,1] 上の凸関数全体を \widetilde{\Psi} として

\displaystyle \psi(\eta):=\sup_{\widetilde{\psi}\in\widetilde{\Psi}}\widetilde{\psi}(\eta),\quad\eta\in[-1,1 ]

と定義する。

  1. \psi[-1,1] 上の凸関数である。
  2. \psi(-1,1) 上連続な関数である。
  3. \psi_{0}\psi は偶関数である。
  4. \psi[0,1] 上単調増加関数である。
  5. \psi_{0}(\eta)\ge0 であり、特に \psi_{0}(0)=0 が成り立つ。
  6. \psi(\eta)\ge0 である。

 証明 (1) \psi の定義より明らか。

(2) 凸関数に関する一般論より従う。

(3) \psi_{0} が偶関数であることは直接計算により示せる。

\psi が偶関数であることを示す。\widetilde{\psi}\in\widetilde{\Psi} に対して \widetilde{\psi}_{-1}(\eta):=\widetilde{\psi}(-\eta) と定義すると \widetilde{\psi}_{-1}\in\widetilde{\Psi} である。実際、\widetilde{\psi}_{-1} の凸性は\widetilde{\psi} の凸性から直ちに分かる。また \psi_{0} が偶関数より

\displaystyle \widetilde{\psi}_{-1}(\eta)=\widetilde{\psi}(-\eta)\le\psi_{0}(-\eta)=\psi_{0}(\eta)

が成り立つ。ここで \widetilde{\Psi}_{-1}:=\{\widetilde{\psi}_{-1}\,|\,\widetilde{\psi}\in\widetilde{\Psi}\}=\widetilde{\Psi}であることに注意すると

 \displaystyle \psi(\eta)=\sup_{\widetilde{\psi}\in\widetilde{\Psi}}\widetilde{\psi}(\eta)=\sup_{\widetilde{\psi}_{-1}\in\widetilde{\Psi}_{-1}}\widetilde{\psi}_{-1}(\eta)=\sup_{\widetilde{\psi}\in\widetilde{\Psi}}\widetilde{\psi}(-\eta)=\psi(-\eta).

(4) \psi は凸な偶関数より t\in[0,1]、\eta\in[0,1] に対して

\displaystyle \psi(t\eta)=\psi\left(\frac{1+t}{2}\eta+\frac{1-t}{2}(-\eta)\right)\le\frac{1+t}{2}\psi(\eta)+\frac{1-t}{2}\psi(-\eta)=\psi(\eta).

これは \psi が単調増加であることを意味している。

(5) \psi_{0}(\eta)\ge0\psi_{0} の定義から明らか。また \psi_{0}(0)=0 は全ての \alpha\in\mathbf{R} に対して \alpha\cdot0\le 0 より

 \displaystyle \inf_{\alpha\in\mathbf{R};\alpha\cdot0\le0}C_{0}(\alpha)=\inf_{\alpha\in\mathbf{R}}C_{0}(\alpha)

となることから直ちに導かれる。

(6) 0 に値を取る定数関数 1_{\emptyset} は凸関数であり \psi_{0}\ge1_{\emptyset} を満たす、つまり 1_{\emptyset}\in\widetilde{\Psi} であるから、\psi の定義より \psi(\eta)\ge1_{\emptyset}(\eta)=0 が成り立つ。(証明終)

 

上記補題で定義した \psi を使って、R_{\phi}(f) により R_{\mathrm{err}}(f) を上から評価することが出来ます。

定理 2 判別関数 fP^{X}(f^{-1}(\{0\}) )=0 を満たすとする。任意のマージン損失 \phi に対して次式が成り立つ:\begin{equation}\psi\left(R_{\mathrm{err}}(f)-\inf_{g  \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g)\right)\le R_{\phi}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\phi}(g).\label{eq:psi_diff_0-1_margin_le_diff_phi_margin}\end{equation}

証明 前回の式 (1) と \psi の凸性、およびイェンセンの不等式より

 \psi \left(R_{\mathrm{err}}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g)\right) \le\int_{\mathcal{X}}\psi\left(1_{\Delta(f,f_{0})}(x)|f_{0}(x)|\right)P^{X}(dx).

\psi_{0} が偶関数より\begin{equation*}\psi\left(1_{\Delta(f,f_{0})}(x)|f_{0}(x)|\right)\le\psi_{0}\left(1_{\Delta(f,f_{0})}(x)|f_{0}(x)|\right)=\psi_{0}\left(1_{\Delta(f,f_{0})}(x)f_{0}(x)\right)\end{equation*}であるから\begin{equation*}\begin{split}\psi & \left(R_{\mathrm{err}}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g)\right) \\ & \le\int_{\mathcal{X}}\psi_{0}\left(1_{\Delta(f,f_{0})}(x)f_{0}(x)\right)P^{X}(dx)\\ & =\int_{\Delta(f,f_{0})}\psi_{0}\left(f_{0}(x)\right)P^{X}(dx)+\psi_{0}(0)P^{X}(\Delta(f,f_{0})^{c})\\ & =\int_{\Delta(f,f_{0})}\psi_{0}\left(f_{0}(x)\right)P^{X}(dx).\end{split}\end{equation*}

一方、任意の x\in\Delta(f,f_{0}) に対して

 C_{f_{0}(x)}(f(x) )-\inf_{\alpha\in\mathbf{R}}C_{f_{0}(x)}(\alpha)\ge\inf_{\alpha\in\mathbf{R};\alpha f_{0}(x)\le0}C_{f_{0}(x)}(\alpha)-\inf_{\alpha\in\mathbf{R}}C_{f_{0}(x)}(\alpha)=\psi_{0}(f_{0}(x) )

であるから、式 \eqref{eq:estimation_for_diff_predictive_phi_margin_loss} より

 R_{\phi}(f)-\inf_{g \in L^{0}(\mathcal{X})}R_{\phi}(g)\ge\int_{\Delta(f,f_{0})}\psi_{0}(f_{0}(x) )P^{X}(dx).

よって式 \eqref{eq:psi_diff_0-1_margin_le_diff_phi_margin} が成り立つ。(証明終)

 

ここで \{f_{n}\}_{n\in\mathbf{N}}R_{\phi}(f_{n})\inf\limits _{f \in L^{0}(\mathcal{X})}R_{\phi}(f) に収束するような判別関数列とします。このとき式 \eqref{eq:psi_diff_0-1_margin_le_diff_phi_margin} を使って R_{\mathrm{err}}(f_{n})\inf\limits _{f \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(f) に収束することが言えれば 2 値判別が代理損失によって実現できたことになるのですが、\psi(\eta)=0 となる \eta\eta=0 に限定されていないため、欲しい結論を得ることは出来ません。そこで \phi に対して次の条件を課します。

定義 3(判別適合的損失) \psi_{0}(\eta)=0 となる \eta\eta=0 に限られるとき、マージン損失 \phi を判別適合的損失という。

ヒンジ損失や指数損失、ロジスティック損失は判別適合的損失です。 

補題 4 マージン損失 \phi が判別適合的であるとき、\psi(\eta)=0 となる \eta\eta=0 に限られる。

証明  \varepsilon\gt 0 とする。\phi は判別適合的であるから m_{\varepsilon}:=\min\limits_{\eta \in [\varepsilon,1] }\psi_{0}(\eta) \gt 0 である。

 \displaystyle \widetilde{\psi}_{\varepsilon}(\eta):= \begin{cases}\frac{m_{\varepsilon}}{1-\varepsilon}(|\eta|-\varepsilon), \quad \eta\in[-1,-\varepsilon ]\cup[\varepsilon,1 ],\\0, \qquad \qquad \quad \ \ \eta\in(-\varepsilon,\varepsilon),\end{cases}

と定義すると \psi_{0}\ge\widetilde{\psi}_{\varepsilon} を満たす凸な偶関数である。\psiの定義より任意の  \varepsilon\gt 0 に対して

 \displaystyle \psi(\eta)\ge\widetilde{\psi}_{\varepsilon}(\eta)\gt 0,\quad\eta\in [\varepsilon,1].

つまり \psi(\eta)=0 となる \eta\eta=0 に限られる。 (証明終)

 

以上の準備の下、2 値判別に代理損失を用いることの正当性を与えます。

 

定理5  次の(1)、(2)は同値である。

  1. マージン損失 \phi が判別適合的である。
  2. \{f_{n}\}_{n\in\mathbf{N}}\mathcal{X}\times\mathcal{Y} 上の分布 P^{(X,Y)} に対して
     \displaystyle R_{\phi}(f_{n}) \to \inf_{g \in L^{0}(\mathcal{X})} R_{\phi}(g) , \quad(n\to\infty)
    を満たす判別関数列とすると\begin{equation*} R_{\mathrm{err}}(f_{n}) \to \inf\limits _{f \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(f),\quad (n\to\infty). \end{equation*}

証明 マージン損失 \phi が判別適合的であるとすると、定理 2 と補題 4 により (2) が成り立つ。

次に (2) ならば (1) を示す。 そのためにマージン損失 \phi が判別適合的でない場合、(2) が成り立たないことを示す。

マージン損失 \phi は判別適合的でないから、\psi_{0}(\eta_{0})=0 となる \eta_{0}\in(0,1] が存在する。

 \displaystyle 0=\psi_{0}(\eta_{0})=\inf_{\alpha\in\mathbf{R};\alpha\eta_{0}\le0}C_{\eta_{0}}(\alpha)-\inf_{\alpha\in\mathbf{R}}C_{\eta_{0}}(\alpha)

より \alpha_{n}\le0

 \displaystyle \lim_{n\to\infty}C_{\eta_{0}}(\alpha_{n})=\inf_{\alpha\in\mathbf{R}}C_{\eta_{0}}(\alpha)

となるものが存在する。

x_{0}\in\mathcal{X} を任意の 1 点とする。\mathcal{X}上の確率測度

 P^{X}(B):=1_{B}(x_{0})

\mathcal{Y}上の確率測度

 \displaystyle P^{Y}(C\,|\,x):=\left( \frac{1+\eta_{0}}{2}\,1_{C}(1)+\frac{1-\eta_{0}}{2}\,1_{C}(-1) \right)1_{\{x_{0}\}}(x)+1_{C}(-1)1_{\mathcal{X}\setminus\{x_{0}\}}(x)\

によって \mathcal{X}\times\mathcal{Y} 上の分布 P^{(X,Y)}

 \displaystyle P^{(X,Y)}(B\times C):=\int_{\mathcal{X}}P^{Y}(C\,|\,x)P^{X}(dx)

で定義する。また判別関数列 \{f_{n}\}_{n\in\mathbf{N}}

 f_{n}(x):=\alpha_{n}

で定義する。このとき

 \displaystyle f_{0}(x)=2P^{Y}(\{1\}\,|\,x)-1=(1+\eta_{0})1_{\{x_{0}\}}(x)-1.

\eta_{0}\neq0 より f_{0}^{-1}(\{0\})=\emptyset である。ここで直接計算により次を得る:

 \displaystyle R_{\phi}(f_{n})=C_{\eta_{0}}(\alpha_{n}),
 \displaystyle \inf_{g \in L^{0}(\mathcal{X})}R_{\phi}(g)=\inf_{\alpha\in\mathbf{R}}C_{\eta_{0}}(\alpha),
 \displaystyle R_{\mathrm{err}}(f_{n})=\frac{1+\eta_{0}}{2},
 \displaystyle \inf_{g \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g)=R_{\mathrm{err}}(f_{0})=\frac{1-\eta_{0}}{2}.

 \alpha_{n} の定義から R_{\phi}(f_{n})\inf\limits _{g \in L^{0}(\mathcal{X})}R_{\phi}(g) に収束する一方、R_{\mathrm{err}}(f_{n})\inf\limits _{g \in L^{0}(\mathcal{X})}R_{\mathrm{err}}(g) に収束することは無い。(証明終)

 

参考文献

  • 金森敬文, 統計的学習理論, 講談社, 2015