NIPS2012自棄読み　その１ - 甲斐性なしのブログ

気が付いたら3月も中旬です。昨年末に27歳の誕生日を迎えたばかりだと思っていたら、もう3ヶ月経ってしまいました。このまま、あっという間に三十路を迎えるのでしょう。時の流れは早くて残酷です。生え際の後退もかなり進行してきました。悲しいです。昔の写真をみると涙が出そうになります。悲しすぎるので、僕の誕生日より少し前に開催されたNIP2012の論文を自棄読みしました。

Multi-Task Averaging

多くのマルチタスク学習は分類問題や回帰問題に対して提案された手法ですが、この論文は母平均をマルチタスク学習で推定するという珍しい（？）手法Multi-Task Averaging（MTA）を提案しています。異なるタスク同士でも、お互い情報を共有し合って母平均を推定することで推定精度を上げられると主張しています。早速、目的関数です。

$\displaystyle \left\{ {Y}_t^* \right\}_{t=1}^T =\mathop{\rm argmin}\limits_{\left\{ \hat{Y}_t \right\}_{t=1}^T} \frac{1}{T} \sum_{t=1}^{T} \sum_{i=1}^{N_t} \frac{\left(Y_{ti} - \hat{Y}_t \right)^2}{\sigma_t^2} + \frac{\gamma}{T^2} \sum_{r=1}^{T} \sum_{s=1}^{T} A_{rs} \left(\hat{Y}_r - \hat{Y}_s \right)$

$Y_{ti}$ はタスク $t$ の $i$ 番目のサンプル、 $A_{rs}$ はタスク $r$ とタスク $s$ の類似度を表します。その他記号のNotationは論文の方をご覧ください。この式の第1項は各タスクの経験誤差最小化の作用、第2項にはタスク間の類似度が高いほどその推定平均値の差が小さくなるように制御する作用があります。
ここで、 $A_{rs}$ が全て0以上、かつ、 $A_{rs}$ を要素とする行列 ${\bf A}$ が対称行列だとすると、上記の最小化問題は解析的に解を得ることができます。

${\bf Y}^* = \left({\bf I} + \frac{\gamma}{T} \Sigma {\bf L}\right)^{-1} {\bf \bar{Y}}$

$\Sigma$ は $\Sigma_{tt}={\sigma_t^2}/{N_t}$ という要素を持つ対角行列、 ${\bf L}$ は ${\bf A}$ のグラフラプラシアン、 $\bf{\bar{Y}}$ は各タスクのサンプル平均 $\left(\frac{1}{N_t}\sum_{i=1}^{N_t}Y_{it}\right)$ を縦に並べたベクトルです。
さて、この論文ではタスク数が2の場合について解析し、このタスク間の実際の母平均の差 $\Delta$ がそれぞれのタスクの分散に比べて小さい時、MTAによる推定結果の平均二乗誤差は、単純なサンプル平均による推定結果の平均二乗誤差より小さくなるという結論を得ています（つまり、タスク間の母平均が近いならMTAは有効）。また、2つのタスクの平均二乗誤差の和を最小にする $a$ は、

$a^* = \frac{2}{\Delta^2}$

として得られます。
この結果を用いて、タスク間の類似度行列 ${\bf A}$ を求める方法を2つ提案しています。ここでは、そのうちの1つであるConstant MTAについて少しだけ記述します。やりたいことは、以下の式のように、実際の各タスクの母平均 ${\bf \mu}$ とMTAによる推定結果の平均二乗誤差を最小化することです。

$R\left({\bf \mu} , {\bf W}{\bf \bar{Y}} \right) = E [\left({\bf W} {\bf \bar{Y}} - {\bf \mu} \right)^T \left(\bf{W} \bf{\bar{Y}} - \bf{\mu} \right)] = \rm{tr} \left({\bf W} \Sigma {\bf W} \right) + {\bf \mu}^T \left({\bf I} - {\bf W} \right)^T \left({\bf I} - {\bf W} \right) {\bf \mu}$
ただし、
${\bf W}= \left({\bf I} + \frac{\gamma}{T} \Sigma {\bf L}\right)^{-1}$

これを最小化する ${\bf A}$ を求めたいのですが、タスク数が2より大きい場合、求めたいパラメータの数が多くなり解析的に ${\bf A}$ を求めるのは、格段に難しくなります。そこで、行列の全要素は $a$ であるという大胆な仮定を置きます。更に、 $\gamma=1$ で全タスクの分散は同じであるという仮定を置くと、損失を最小にする $a$ は、

$\displaystyle a^* = \frac{2}{ \frac{1}{T \left(T - 1 \right)} \sum_{r=1}^{T} \sum_{s=1}^{T} \left(\mu_r - \mu_s \right)^2}$

となります。ただし、 $\mu$ は実際の母平均の値で当然分からないので、結局のところサンプル平均の $\bar{y}$ を用います。とどのつまり、タスク間の平均差の二乗 $\Delta^2$ をタスクの組み合わせ分求めて平均したものを分母に用いるという方法で、タスク数が2の場合の拡張をしてることになります。結果をみると、やはりタスク間の類似度が高ければ、このConstant MTAは良く働くようです。

Hamming Distance Metric Learning

入力ベクトルを $\{-1 , 1\}$ の２値のベクトル（バイナリコードベクトル）として表現することで、近傍探索などにおいてメモリ使用量や計算速度の改善が期待できます。では、どのようにバイナリコードベクトルに変換するのが適切か？これをサンプル集合から学習するのがこの論文の目的です。
${\bf x} \in {\bf R}^p$ を入力ベクトル、 ${\bf h} \in {\bf R}^q$ を目的のバイナリコードベクトルとすると、その関係を

${\bf h} = b\left({\bf x};{\bf w}\right) = \rm{sign}\left(f\left({\bf x};{\bf w}\right)\right)$

という式で表すことができます。 $f$ は、 ${\bf R}^p \rightarrow {\bf R}^q$ とする線形または非線形の写像です。多くのバイナリコード変換の学習は、 $f$ を決定づけるパラメータ ${\bf w}$ を学習します。これまで、この $f$ として、線形写像を使うよとか多段ニューラルネット使いましょうなどの、様々な写像が提案されていますが、この論文では $f$ を決めず、それらを包括するような枠組みを提案しています。
まず、この論文の前提としてサンプル集合 ${\cal D}$ は、 ${\bf x}$ と ${\bf x}^+$ の類似度は ${\bf x}$ と ${\bf x}^-$ の類似度より高いという三つ組 $\left({\bf x} , {\bf x}^+ , {\bf x}^-\right)$ の集合として得られるものとします（入力インプットのベクトル同士の類似度を計算できるなら、この三つ組は得ることができます）。そして、バイナリコードへの変換を学習するために以下のような損失関数を定義しています。

$\displaystyle {\cal L}\left( {\bf w} \right) = \sum_{\left({\bf x} , {\bf x}^+ , {\bf x}^-\right) \in {\cal D}} \ell_{{\rm triple}} \left(b\left({\bf x};{\bf w}\right) , b\left({\bf x}^+;{\bf w}\right) , b\left({\bf x}^-;{\bf w}\right) \right) + \frac{\lambda}{2} \parallel {\bf w} \parallel_2^2$
ただし、
$\ell_{{\rm triple}} \left({\bf h} , {\bf h}^+ , {\bf h}^-\right) = [ \parallel {\bf h} - {\bf h}^+ \parallel_H - \parallel {\bf h} - {\bf h}^- \parallel_H + 1 ]_+$

$[\alpha ]_+ = \max \left(\alpha , 0 \right)$ 、 $\parallel \cdot \parallel_H$ はベクトルの非ゼロ要素の数。
この ${\cal L}\left( {\bf w} \right)$ を最小化する $\bf{w}$ を求めることで、類似度の順序関係を保持したバイナリコード変換が得られることを期待できます。しかし、この目的関数は非凸かつ $\bf{w}$ で微分不可という面倒な性質を持っています。ということで、損失の上限式に対して最小化を行うことを考えます。 $\ell_{\rm{triple}} \left(b\left({\bf x};{\bf w}\right) , b\left({\bf x}^+;{\bf w}\right) , b\left({\bf x}^-;{\bf w}\right) \right)$ の上限は以下のようになります。

$\displaystyle \max_{{\bf g} , {\bf g}^+ , {\bf g}^-} \left\{\ell_{{\rm triple}} \left({\bf g} , {\bf g}^+ , {\bf g}^-\right) + {\bf g}^T f\left({\bf x};{\bf w}\right) + {{\bf g}^+}^T f\left({\bf x}^+;{\bf w}\right) + {{\bf g}^-}^T f\left({\bf x}^-;{\bf w}\right)\right\} \\ \displaystyle \hspace{1em} - \max_{{\bf h}} {\bf h}^T f\left({\bf x};{\bf w}\right) - \max_{{\bf h}^+} {{\bf h}^+}^T f\left({\bf x};{\bf w}\right) - \max_{{\bf h}^-} {{\bf h}^-}^T f\left({\bf x};{\bf w}\right)$

こうすることで ${\bf w}$ で微分可能になります。後は確率的勾配法を用いてこれを解いていきます。具体的には、 ${\bf w}$ に初期値を与えた後、サンプル集合 ${\cal D}$ から三つ組 $\left({\bf x} , {\bf x}^+ , {\bf x}^-\right)$ をランダムに1つ抽出し、それに対し上の式を満たす ${\bf g} , {\bf g}^+ , {\bf g}^- , {\bf h} , {\bf h}^+ , {\bf h}^-$ を求めてから、次のように ${\bf w}$ を更新します。

$\displaystyle {\bf w}^{t+1} \leftarrow {\bf w}^{t} + \eta \left[\frac{\partial f\left({\bf x};{\bf w}\right)}{\partial {\bf w}} \left({\bf h} - {\bf g} \right) + \frac{\partial f\left({\bf x}^+;{\bf w}\right)}{\partial {\bf w}} \left({\bf h}^+ - {\bf g}^+ \right) + \frac{\partial f\left({\bf x}^-;{\bf w}\right)}{\partial {\bf w}} \left({\bf h}^- - {\bf g}^- \right) - \lambda {\bf w} \right]$

この手順を繰り返すして、パラメータ ${\bf w}$ を推定します。
ところが、この式にある ${\bf g} , {\bf g}^+ , {\bf g}^-$ を求めるのにも一工夫が必要です。この ${\bf g} , {\bf g}^+ , {\bf g}^-$ を求める過程も、このベクトルが $-1$ か $1$ のどちらかしかとらないことを利用し動的計画法で解くなど、なかなかテクニカルで面白いですが、この部分の詳細は論文を参照してください。
あと、論文にある式(8)は $\ell ' \left(\alpha \right) = [ \alpha - 1 ]_+$ となっていますが、 $\ell ' \left(\alpha \right) = [ \alpha + 1 ]_+$ のような気がします。どうなんでしょう・・・

とりあえず、今回はここまでにします。近いうちに第2弾を書ければなぁと思います。