【ML Tech RPT. 】第5回不均衡データ学習 (Learning from Imbalanced Data) を学ぶ (2)

f:id:ssatsuki040508:20181210005017p:plain
Sansan DSOC 研究員の吉村です. 気づけば入社から一年が経ち, 社会人二年目に突入しました. 今年もコツコツとブログを継続していこうと思っております.

さて, 本題に入っていきましょう.
今回は不均衡データ学習のアプローチの一つである Cost-Sensitive Learning についての話をします. 本記事は前回の記事の続編という立ち位置なので, 前回の記事をご覧になっていない方は, 是非下記の記事から読んでみてください.
buildersbox.corp-sansan.com

Notation

説明をする前に, 今回の記事で用いる変数についてこちらでまとめておきます.

$x_i$	$i$ 番目の事例. データ点.
$y_i$	$i$ 番目の事例に対応する真のラベル. 二値分類の場合は, $y_i \in \{-1, 1\}$ . 多クラス分類の場合は, $y\in\{1, 2, \cdots, M\}$
$\hat{y}$	$i$ 番目の事例のラベルの予測値.
$f$	判別関数. $f \in \mathbb{R}$
$L, \phi$	損失関数.
$L_i$	$i$ 番目の事例に対応する損失関数.
$C$	Cost Matrix.
$S$	事例に対応するスコアベクトル. $S=(S_1, S_2, \cdots, S_M)\top$ . $S_k$ はラベル $k$ に対応するスコア

Cost-Sensitive Learningの概要

Cost-Sensitive Learning (コスト考慮型学習) とは, 不均衡データ学習に対処するためのアプローチの一つで, 許容し難い誤りには大きなコストを, 許容できる誤りには小さなコストを課す損失関数でラベル予測をする方法です.

例えば, 製造した自動車の部品が不良品か良品かを機械学習を用いて判別するとき, 普通の分類問題としてモデルを学習する場合には, 実際は不良品のものを良品と識別することも, 実際は良品のものを不良品と識別することも同等の影響があるとみなします. つまり, このときの損失関数 $L$ は $L= \sum_i \mathbb{I}[y_i \neq \hat{y}_i$ ]のように表すことができます. ただし, $\mathbb{I}$ は指示関数を, $y_i$ は製品 $i$ の真の品質(良品なら $+1$ , 不良品なら $-1$ ), $\hat{y}_i$ は製品 $i$ の識別結果を表します. しかし, この問題は人によっては次のように考える人もいるかもしれません.

「製造しているのが自動車の部品であることから, もし不良品が出荷されると死亡事故につながる恐れがあるため絶対に不良品を良品とモデルで識別することは避けたい. しかし, 良品を不良品と識別することはその不良品を一つ製造するコストが無駄になるだけなのである程度は許容できる. 」

仮にこれを「不良品を良品と識別することは良品を不良品と識別することよりも $n$ 倍の影響がある」と判断したとすれば, このときの損失関数 $L$ は $L=\sum_i (n \mathbb{I} [(y_i=-1) \land (\hat{y}_i=+1) ] + \mathbb{I}[(y_i=+1) \land (\hat{y}_i=-1)])$ と書くことができます.

このように各種誤りの影響度をコストとして与えることで考慮するのがCost-Sensitive Learningです. 各種誤りに対するコストを損失関数に反映させるための方法の一つとしては, Cost Matrix(コスト行列)を用いる方法があります.

Cost Matrix

Cost Matrixは, 真のラベルが $k$ の事例に対して, 予測結果が $j$ の時に課すコスト $C_{jk}$ を要素に持つ行列 $C$ として表現されます. このCost Matrixを用いてラベル予測をするための方法として,
$\sum_kP(y=k|x)C_{jk}$ を最小化するラベル $j$ を選択する方法が考えられます. このCost Matrixが最低限満たすべき性質として[*1]ではReasonablenessが提案されています. Reasonablenessは次の二つからなります.

$C_{10}>C_{00}$ と $C_{01}>C_{11}$ を満たす.
任意の $k$ に対して $C_{mk} \geq C_{lk}$ となることを回避する.

一つ目は単に「必ず正解より誤りの場合のコストが大きくなる」ことを要請しています. 二つ目については, 任意の $k$ に対して $C_{mk} \geq C_{lk}$ が成り立ってしまうと, 常に $l$ と予測し続ければいいことになってしまうので, それを避けるための条件となります.

また, このCost Matrixは全ての要素に定数を掛けても, 足しても最適な場合の予測結果は変わらないため, 次のように簡略化することもできます.
$C= \begin{pmatrix} 0 & C_{01}' \\\ 1 & C_{11}' \end{pmatrix}$ ただし, $C_{01}' = (C_{01}-C_{00})/(C_{10}-C_{00}), C_{11}' = (C_{11}-C_{00})/(C_{10}-C_{00})$ です.

損失関数に関する望ましい性質

Cost-Sensitive Learningで損失関数を設計する上での目安となる性質について二つ紹介します.
一つ目がClassification Calibrated性[*2]で, 二つ目がGuess Averse性[*3]です. 簡単に説明すると, Classification Calibrated性はその損失関数でコストを評価した時に, 真のラベルを予測する方が, 誤ったラベルを予測するよりも必ずコストが小さくなることを保証する性質です. Guess Averse性はその損失関数でコストを評価した時に, 真のラベルのスコアが他のラベルのスコアより大きい時の方が, 全てのラベルに均等に信頼度を割り振る時よりも必ずコストが小さくなることを保証する性質です.

この他にも Margin Maximizing性などもありますが, こちらは割愛します.
さて, 以下ではこれら二つについての詳細を見ていきます.

Classification Calibrated性

Classification Calibrated性を説明するために, いくつかの用語を定義します.

Definition of $\phi-risk$ [P. L. Bartlett et.al. 2006]
$R_{\phi}(f)=\mathbb{E}(\phi(yf(x)))$ を $\phi$ リスクと呼ぶ.

Definition of $conditional\ \phi-risk$ [P. L. Bartlett et.al. 2006]
$\mathbb{E}(\phi(yf(x))|x)=\eta(x)\phi(\alpha)+(1-\eta(x))\phi(-\alpha)$ を条件付き $\phi$ リスクと呼ぶ. ただし, $\eta(x)=P(y=1|x)$ , $\alpha=f(x)$ .

このとき, 最適な条件付き $\phi$ リスクは次のように表現されます.

Definition of $optimal\ conditional\ \phi-risk$ [P. L. Bartlett et.al. 2006]
$\eta(x) \in [0, 1]$ に対して, $H(\eta)=\inf_{\alpha \in \mathbb{R}}\eta(x)\phi(\alpha)+(1-\eta(x))\phi(-\alpha)$ を最適な条件付き $\phi$ リスクと呼ぶ.

ここで, $H^{-}=\inf_{\alpha :\alpha(2\eta(x) -1)\leq0}\eta(x)\phi(\alpha)+(1-\eta(x))\phi(-\alpha)$ とすると, Classification Calibrated性は次のように定義されます.

Definition 1. [P. L. Bartlett et.al. 2006]
いずれの $\eta(x)\neq1/2$ に対しても, $H^{-}(\eta(x))>H(\eta(x))$ を満足する $\phi$ はClassification Calibrated性を持つ.

ここで $\phi$ は, $x$ に対する関数 $f$ から得られるスコア $f(x)$ を入力に受け取って, 何らかの実数値を返す損失関数です. この関数がClassification Calibrated性を持つというのは, スコアが実数空間全てをとるときの条件付き $\phi$ リスクの下限より, 予測が誤っている範囲 ( $\alpha(2\eta(x)-1)\leq0$ , つまり, スコアが正の時に予測が負, または, スコアが負の時に予測が正)のスコアのみをとる時の条件付き $\phi$ リスクの下限が常に大きいということを言っています. $H$ と $H^-$ で異なるのは考える $\alpha$ の範囲だけで, 当然 $H^-$ の方が狭い範囲を取るので, 結局Classification Calibrated性とは, 予測が誤っている時に最適な条件付き $\phi$ リスクとならないことを要請する性質ということになります.

この性質があることで, $\phi$ を最小化するとBayesリスクに近づくことが知られており, その点で有用な性質と言えます.

Guess Averse性

Guess Averse性の定義をする前の準備として, $support\ set$ と $arbitrary\ guess\ point$ という二つの概念を定義します.

Definition 1. [O. Beijbom et.al. 2014]
クラス $k$ の $support\ set$ とは $S_k$ が最大のスコアとなる全てのスコアベクトル集合のこと. すなわち,
$\mathcal{S}_k = \{S|S\in \mathbb{R}^M, S_k>S_j, \forall j\neq k\}.$

Definition 2. [O. Beijbom et.al. 2014]
$S_k(x)$ が $k$ に依存しない, つまり, $S_k(x)=S_1(x), \forall k$ を満たすならば, スコアベクトル $S(x)\in \mathbb{R}^M$ は $arbitrary\ guess\ point$ である. 全ての arbitrary guess point の集合を $\mathcal{A}$ で表す.

これら二つの定義を用いて, Guess Averse性は次のように定義されます.

Definition 3. [O. Beijbom et.al. 2014]
任意のコスト行列 $C$ , 任意のラベル $k$ , 任意の $S \in \mathcal{S}_k$ , そして, 任意の $A \in \mathcal{A}$ に対して, $L(C, k, S) < L(C, k, A)$ を満たすならば, 損失関数 $L$ はGuess Averse性を持つ.

結局のところこの定義では, 「コスト行列として $C$ を利用していて, 真のラベルが $k$ の時に, スコアベクトル $S$ の要素のうちラベル $k$ に対応する要素 $S_k$ が他のどの要素よりも大きいいかなるスコアベクトルを用いるよりも, 任意の arbitrary guess point を用いる方が必ず損失が大きくなる損失関数 $L$ は Guess Averse性をもつ.」ということを言っています. これは非常に直感的な損失関数の指標です. なぜなら, Guess Averse性を持つ損失関数 (Guess Averse損失) であれば, 真のラベルに対応するスコアが他のラベルに対応するスコアより大きい場合に比べて, 全てのラベルに対するスコアが均等な場合の損失が小さくなることはなくなることを言っているからです.

このGuess Averse損失を設計する方針について[O. Beijbom et.al. 2014]で提案されているので, 簡単に紹介します. その前に, $\gamma - \phi$ 損失を定義します.

Definition 4. [O. Beijbom et.al. 2014]
真のラベルが $k$ である事例を $x$ , コスト行列を $C$ , スコアベクトルを $S(x) \in \mathbb{R}^M$ とする. この時, 任意の可測関数 $\gamma(\cdot)$ と $\phi(\cdot)$ に対して, 損失関数
$L^{\gamma, \phi}(C, k, S(x))=\gamma \left( \sum_{j=1}^MC_{jk}\phi(S_k(x)-S_j(x)) \right)$ は $\gamma - \phi \ loss$ である.

この $\gamma - \phi$ 損失は可測関数 $\gamma(\cdot)$ と $\phi(\cdot)$ が特定の条件を満たす時にGuess Averse損失となります. その条件について述べた補題が次のようになります.

Lemma 1. [O. Beijbom et.al. 2014]
ある単調増加関数を $\gamma : \mathbb{R} \rightarrow \mathbb{R}$ とし, 条件 $\phi(v)<\phi(0)\ \ \forall v>0$ を満たすある関数を $\phi : \mathbb{R} \rightarrow \mathbb{R}$ とする.
この時, $\gamma - \phi$ 損失 $L^{\gamma, \phi}$ は Guess Averse損失である.

Guess Averse性があると, 予測性能が高くなることが実験的に示されており, その点で有用と言えます.

損失関数の設計

手動で損失関数を設計する方法

Cost Matrixを独自で設計する手法としては, 下記のようなものが提案されています.

[O. Beijbom et.al. 2014]では, Class Calibrated性を持つ損失関数として $L_t(C, k, S(x))=\sum_{l=1}^M\sum_{j=1}^MC_{jk}e^{S_{j}(x)-S_{l}(x)}$ が紹介されています. こちらは, Guess Averse性は持ちません.

一方でGuess Averse性をもつ損失関数としては, $\gamma - \phi$ 損失で $\gamma(v)=v$ , $\phi(v)=e^{-v}$ を利用する Generalized Exponential Loss (GEL)と $\gamma(v)=\log(1+v)$ , $\phi(v)=e^{-v}$ を利用する Generalized Logistic Loss (GLL)が提案されています. このうち, GLLはClassification Calibrated性を持ちません. これらを用いた予測手法としては, これらの損失を用いたMulti-Class Boost (MCBoost) が提案されています.

自動で損失関数を設計する方法

手動による損失関数の設計の欠点は, Cost Matrixを自ら決定する必要があることです. Cost Matrixを設計する場合, Reasonableness性を考える必要がありますが, これはmulti-class分類で候補クラス数が増えるほど難易度が高くなります. また, Cost Matrixの各要素をパラメータと見なせば, 当然チューニングする必要がありますが, こちらもmulti-class分類で候補クラス数の増加に対して二乗のスピードで変数が増えていきます. これを見れば, できればCost Matrixは自らで設定したくないことは納得してもらえると思います. そこで, Cost Matrixも自動で決定する手法として, CoSen CNN(Cost-Sensitive CNN)[*4]があります. これは, CNNの最後のsoft-max層の手前にCost Matrixによる演算を追加して, CNNとCost MatrixをSGDを用いた交互最適化で学習する手法です. この手法では, Cost Matrixの影響を適切に反映させるためCost-Sensitive Learning用に変更した三通りの損失関数(Cost-Sensitive MSE loss, Cost-Sensitive SMV hinge loss, Cost-Sensitive CE loss)のうちいずれかを用います(ただし, [S. H. Khan et. al. 2018]では, Cost-Sensitive CE Lossを用いた場合の実験しか行われていません).一般的には, Cost-Sensitive CE lossを用いる方が他の二つを用いるより性能が良くなる傾向にあるようです. また, Cost-Sensitive CE LossはClassification Calibrated性とGuess Averse性の両方を持っています.

まとめ

今回は不均衡データ学習の対処法の一つであるCost-Sensitive Learningについてまとめました. 直接不均衡データ学習に関することはほぼ出てきませんでしたが, 前回の記事で書いたように不均衡データ学習においては, 達成したい目標が何かということが重要であり, この目標を達成できるように損失関数を設定することで不均衡データへの対応につながります.

この記事からも分かる通り, この分野にはかなり理論的な背景があることがわかりました. 次回は異常検知を利用した不均衡データ学習の対処法についてまとめていきますのでご期待ください.

*1:C. Elkan, "The foundations of cost-sensitive learning, " in IJCAI, 2001.

*2:P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe, "Convexity, classification, and risk bounds," in ASA, 2006.

*3:O. Beijbom, M. Saberian, D. Kriegman, and N. Vasconcelos, "Guess-averse loss functions for cost-sensitive multiclass boosting," in ICML, 2014

*4:S. H. Khan, M. Hayat, M. Bennamoun, F. Sohel and R. Togneri, "Cost-Sensitive Learning of Deep Feature Representations from Imbalanced Data," in TNNLS, 2018.

Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信