はじめに

指示関数$I$は以下で定義される．

I(x) = \left\{\begin{array}{ll}
1 \ (x = true) \\
0 \ (x = false)
\end{array}\right.

この指示関数は，こんなものを最適化したい！というものを表す時に便利に使える．しかし，こいつは，連続ではない．どうしたものか...，という人に向けた記事です笑．

代理損失

この記事では以下の形をした指示関数を考える．

I(u > 0)

これを連続な関数にするために，代理損失を導入する．ここでは，ヒンジ損失と，ロジスティック損失を紹介する．

ヒンジ損失は以下のように定義される．

\max\{0, 1 - u\}

ロジスティック損失は以下のように定義される．

\log \left(1 + e^{-u}\right)

これらは主に分類のための損失．回帰の場合はどうするんだ？とにかく，以下の形で表そう．

I(u > 0)

入力を$x \in \mathcal{X}$, 出力を$y \in \mathcal{Y}$，モデルを$f: \mathcal{X} \rightarrow \mathcal{Y}$とする．エラーを$\epsilon$以下に抑えるという以下のような形はどうだろう？

I(|y - f(x)| < \epsilon) = I(\epsilon - |y - f(x)| > 0)

おお，これで例の形で表せた．じゃあ，ヒンジ損失を使ってみよう．

\max\{0, |y - f(x)| - \epsilon\}

はい，かの有名な$\epsilon$-insensitive lossが出来上がりました．世の中の有名なロスはこうやってできてるんですね．素晴らしい．

応用: Recommendation

応用例を一つご紹介します．Recommendationです．ユーザ$u \in U$とアイテム$i \in I$を考える．implicitなフィードバック$D \subseteq U \times I$が与えられたとする．そして，ユーザ$u$にとってポジティブなアイテム集合を$I_u^{+} = \{i | (u, i) \in D\}$とする．最後に$D_s = \{(u, i, j) | u \in U, i \in I_u^{+}, j \in I \setminus I_u^{+}\}$とすれば，これがペアワイズ学習でよく使われる学習データ．要は，ユーザ$u$にとって，アイテム$j$よりアイテム$i$の方が好きというデータセットだ．

ここで，学習基準を導入する．ユーザ$u$にとってのモデル$f: U \times I \rightarrow \mathbb{R}$の良さは例えば以下のように表せるだろう．

AUC(u) = \frac{1}{|I_u^{+}||I \setminus I_u^{+}|}\sum_{i \in I_u^{+}} \sum_{j \in I \setminus I_u^{+}} I(f(u, i) - f(u, j) > 0)

（指示関数が出てきている．ワクワクする．）

これを全ユーザで平均しよう．

\begin{align*}
AUC &= \frac{1}{|U|} \sum_{u \in U} AUC(u) \\
&= \frac{1}{|U||I_u^{+}||I \setminus I_u^{+}|} \sum_{(u, i, j) \in D_s} I(f(u, i) - f(u, j) > 0)
\end{align*}

要はこれが高い方が良いわけで，これを最大化しよう，となる．さて，指示関数は連続じゃないので扱いづらいが，例の形で指示関数が出てきているので我々には代理損失というものがある．まずはヒンジ損失で置き換えてみよう．

\begin{align*}
AUC 
&= \frac{1}{|U||I_u^{+}||I \setminus I_u^{+}|} \sum_{(u, i, j) \in D_s} \max\{0, 1 - f(u, i) + f(u, j)\}
\end{align*}

これは例えば確率的勾配法とかで最適化できそう．$f$にMatrix Factorization (MF)を採用すれば，Maximum margin matrix factorization (MMMF)になるぽい．次にロジスティック損失で置き換えてみよう．

\begin{align*}
AUC 
&= \frac{1}{|U||I_u^{+}||I \setminus I_u^{+}|} \sum_{(u, i, j) \in D_s} \log\left(1 + \exp\left(f(u, j) - f(u, i)\right)\right)
\end{align*}

これは勾配法や確率的勾配法で最適化できそう．多分後者はBayesian Personalized Rankingとかになる．

おわりに

このように，指示関数は，「こんな感じのもの」を定義するときにかなり便利に使える．例えば応用例に出したAUCなど．そしてそれを連続にして最適化手法を使えるようにするには，代理損失を使えばいい．このアイデアは多くのアルゴリズムを生み出していて，本当に素晴らしいと感じたので，メモがてら共有させていただきました．読んでいただきありがとうございました．