NIPS2011斜め読み - 甲斐性なしのブログ

NIPSは毎年12月頃に開催される機械学習関連の国際会議です。
Proceedingsはweb上に公開されているので、
今回は昨年末に開催されたNIPS2011の中から、
興味を惹かれた論文を何本か適当にチョイスして読んでみました。
斜め読みした程度なので、かなり理解が甘いです。
でも、自分用メモ書としてブログに書いちゃう。

Sparse Filtering

タイトルのシンプルさに惹かれ、思わず保存した論文。
M個のサンプル ${\bf x}^{(i)} \hspace{1ex} (i=1 \cdots M)$ が与えられて、
教師なし学習でそれぞれのサンプルをより良い
特徴ベクトル ${\bf f}^{(i)}$ にしてあげましょうというものです。
（この枠組みがUnsupervised Feature Learningと言われるそうですが、
次元削減とかとは違うのでしょうか？）
で、各サンプルの特徴ベクトルの要素 $f_{j}^{(i)}$ は、
$f_{j}^{(i)}={\bf w}_j^T {\bf x}^{(i)}$ という線形和で得るんですが、
なるべく、得られる特徴ベクトルはスパースにしたい（0要素を多くしたい）。
もう少し言うと、特徴抽出後のM個のサンプル ${\bf f}^{(i)}$ は
Population Sparsity、Lifetime Sparsity、High Dispersalという
3つの性質を有した集合にしたい。
そのためには、
${\rm minimize} \sum_{i=1}^M \parallel \hat{{\bf f}}^{(i)}\parallel_1$
ただし、
$\hat{{\bf f}}^{(i)} = \frac{\tilde{{\bf f}}^{(i)}}{\parallel \tilde{{\bf f}}^{(i)}\parallel_2}$
$\tilde{{\bf f}}^{(i)} = \frac{{{\bf f}}^{(i)}}{\parallel{{\bf f}}^{(i)}\parallel_2}$
を解けばいいのよーというものです。
超パラメータがすくないぜ（抽出後の次元数だけ？）、
実装楽チンだぜ、収束速いぜという3拍子がそろってるらしいので、
試してみたいですね。

Learning a Distance Metric from a Network

ネットワークの解析にリンク情報だけでなく、
各ノードの特徴ベクトルも考慮しましょうという論文。
例えば、twitterなんかのSNSを利用していると、おすすめのユーザが提示されますが、
その推薦のために、リンク関係（twitterだとフォロー関係）だけでなく、
各ユーザの特徴ベクトル（twitterでは、ツイートから構築される特徴ベクトル）も
考慮すれば、より洗練された推薦ができるようです。
じゃあ、具体的にどうするのって話ですが、これには計量学習の枠組みを利用します。
これは特徴ベクトル集合 ${\bf X}$ とネットワークの接続行列 ${\bf A}$ から
特徴ベクトル同士の距離の計算方法 $D_M ({\bf x}_i,{\bf x}_j )$ を学習するというものです。
この距離は、半正値行列 ${\bf M}$ を用いて、
$D_M ({\bf x}_i,{\bf x}_j )=({\bf x}_i-{\bf x}_j )^T {\bf M}({\bf x}_i-{\bf x}_j )$
として表されるので、 ${\bf X}$ と ${\bf A}$ から最適な ${\bf M}$ を求めることになります。
さて、どのような ${\bf M}$ を求めればよいのかですが、
${\bf X}$ の各特徴ベクトル同士の（ $D_M$ で計算される）距離関係のみから
得られる接続行列（例えば、あるサンプルのk近傍のサンプルは接続しているとみなす）が
実際のネットワークの接続行列 ${\bf A}$ と一致するように、 ${\bf M}$ を求めるというものです。
その（特徴ベクトルの距離関係から計算される）接続行列を得る方法として、
k-nearest neighborを使う場合と、maximum weight subgraphを使う場合の
2つの場合の最適化アルゴリズムが、論文内に示されていますが、
その辺りはまだよくわかりません。

Metric Learning with Multiple Kernels

計量学習をマルチカーネル化する手法を示した論文。
多くの計量学習はこの論文に示されている方法で、
マルチカーネルに拡張できそうです。
まず、マルチカーネル学習ですが、
$k_{\mu}({\bf x}_i , {\bf x}_j)=\sum_{l=1}^{m} \mu_lk_l({\bf x}_i , {\bf x}_j) , \mu_l \geq 0 , \sum_{l=1}^{m} \mu_l = 1$
のように、 $m$ 個あるカーネル関数を重みつきで足し合わせることで、
新たなカーネル関数を作るための重み $\mu_l$ を学習する枠組みです。
このカーネル関数 $k_{\mu}({\bf x}_i , {\bf x}_j)$ で、内積が定義される空間を $\cal H_{\mu}$ とし、
元の特徴ベクトル ${\bf x}$ を $\cal H_{\mu}$ に写像したベクトルを ${\bf \Phi}_{\mu}( {\bf x} )$ とするとその空間上での計量距離は、
$d_{{\bf M},\mu}^2 ({\bf \Phi}_{\mu}( {\bf x}_i ) , {\bf \Phi}_{\mu}( {\bf x}_j )) = ({\bf \Phi}_{\mu}( {\bf x}_i ) - {\bf \Phi}_{\mu}( {\bf x}_j ) )^T {\bf M} ({\bf \Phi}_{\mu}( {\bf x}_i ) - {\bf \Phi}_{\mu}( {\bf x}_j ) )$
となるので、学習サンプルから最適な半正値行列 ${\bf M}$ とカーネルの重み $\mu_l$ を求めるのが、
マルチカーネルの計量学習となります。
多くのカーネル空間上の計量学習アルゴリズムは、
$\displaystyle \min_{{\bf M}_l}F_h({\bf M}_l) \hspace{1ex} s.t. \hspace{1ex} C_h(d_{{\bf M}_l}^2 ({\bf \Phi}_l( {\bf x}_i ) , {\bf \Phi}_l( {\bf x}_j ))) , {\bf M}_l \succeq 0$
という最適化問題を解いていて、その最適解は $\eta_h {\bf I}+{\bf \Phi}_l( {\bf X} )^T {\bf A}_l {\bf \Phi}_l( {\bf X} )$ になるようです
（ ${\bf \Phi}_l( {\bf X} )^T$ は、各行が写像後の学習サンプルの行列）。
しかも、多くの計量学習アルゴリズムは $\eta_h = 0$ になります。
そして、マルチカーネル化したいアルゴリズムの最適解が ${\bf \Phi}_l( {\bf X} )^T {\bf A}_l {\bf \Phi}_l( {\bf X} )$ という形なら、
マルチカーネル化した時の、最適解も ${\bf \Phi}_{\mu}( {\bf X} )^T {\bf A} {\bf \Phi}_{\mu}( {\bf X} )$ となるそうです。
あとは、これを行列 ${\bf A}$ を固定して $\mu$ を求めて、次に $\mu$ を固定して ${\bf A}$ を求める
という操作を収束するまで繰り返します。
このまま、 $\mu_l$ と ${\bf A}$ を求めるのが、 $ML_h-MKL_{\mu}$ と論文内で呼んでいるもので、
これは、採用する計量学習アルゴリズムが凸なら、 ${\bf A}$ を固定して $\mu_l$ の最適解を解く問題も
凸になりますよという手法です。
また、 ${\bf P}={\bf \mu}{\bf \mu}^T$ として、最適化式をちょっと変形した $ML_h-MKL_{P}$ も
提案しているのですが、これは、計量学習アルゴリズムが ${\bf P}$ に対して線形で、
カーネル数が少ない時には、 ${\bf A}$ を固定して ${\bf P}$ を求める問題が、
等価な凸最適化問題に変換できるというものです。
更に、 $\mu$ を半正値行列 ${\bf A}''$ 内にひっくるめてしまうことで、
その ${\bf A}''$ のみを推定する問題になるので、
既存の計量学習アルゴリズムをそのまま利用できる
$NR-ML_h-MKL$ というものも提案しています。
マルチカーネル学習+計量学習がこれまで提案されていなかったって言うのがちょっと意外でした。

Trace Lasso: a trace norm regularization for correlated designs

回帰問題などで正則化項として $l1$ ノルムを利用すると、
解がスパースが得られやすくなります。
これはlassoと呼ばれ、多くの研究で特徴選択や回帰・分類問題に利用されています。
ところが、特徴間に強い相関がある場合、lassoはあまりよろしくない結果をもたらします。
ということで、特徴間の相関に適応する新たな正則化項を提案したのがこの論文です。
まず、学習サンプル ${\bf x} \in \cal R^p$ とし、n個のサンプルをまとめた行列を
${\bf X}=({\bf x}_1,\cdots,{\bf x}_n)^T \in \cal {R}^{n \times p}$ とします。
一般に線形の教師あり学習は、
$\displaystyle \hat{{\bf w}}=\arg \min_{{\bf w}} \frac{1}{n}\sum_{i=1}^{n}\hspace{1ex}l(y_i,{\bf w}^T{\bf x}_i)+\lambda f({\bf w})$ 　（ $y_i$ は学習のラベル、 $l$ は損失関数）
を解くことになるんですが、ここで $f({\bf w})$ として
$l2$ ノルムの2乗 $\parallel {\bf w}\parallel_2^2$ を採用すればリッジ回帰、
$l1$ ノルム $\parallel {\bf w}\parallel_1$ を採用すればlassoになります。
このとき、 $\bf{X}$ の各列が正規化（たぶん、 $l2$ ノルムを1にする正規化）されていれば、
$\parallel {\bf w}\parallel_2=\parallel {\bf X} \rm{diag}({\bf w}) \parallel_F$ , $\parallel {\bf w}\parallel_1=\parallel {\bf X} \rm{diag}({\bf w}) \parallel_{2,1}$ と変形できます。
（ $\parallel \cdot \parallel_F$ はフロベニウスノルム、 $\parallel \cdot \parallel_{2,1}$ は各列の $l2$ ノルムの和）
リッジ回帰もlassoもノルムが異なるだけで、その中身は共通しています。
そこで、このノルムをトレースノルム $\parallel {\bf X} \rm{diag}({\bf w}) \parallel_*$ を採用しよう
というのが、この論文で提案しているトレースlassoです。
（トレースノルムは $\parallel{\bf A} \parallel_* =\rm{trace}( \sqrt{ {\bf A}^T {\bf A}})$ というもので、 ${\bf A}$ の特異値の和になります。）
このトレースlassoですが、 ${\bf X}$ の各列同士が直交してる（各特徴量同士無相関）なら、
通常のlassoと等価になります。
一方、 ${\bf X}$ の各列が全て同じベクトルの場合、これはリッジ回帰と等価になります。
従って、トレースlassoは学習サンプルにおける特徴間の相関が強ければリッジ回帰、
弱ければlassoに近いふるまいをするといえます。
また、もっと一般的に各列が単位ベクトルである適当な行列 ${\bf P}$ を用いて、
$\parallel {\bf P} \rm{diag}({\bf w}) \parallel_*$ という正則化項も提案しています。
この ${\bf P}$ 次第で、lassoもリッジ回帰も今話題の（?）グループlassoも記述できるようです。

今回はここまで。
全体を通して感じた印象としては、

やっぱり皆スパースがお好き
数年前に比べて、Multi ViewとかMulti Taskとかの論文が少なくなった？
どの論文読んでも、最適化や近似のテクニックが眩しすぎる
グループlassoうまそう
タイトルがシンプルな論文が多い

などなど

あと、自分のチョイスが偏りすぎてちょっとよろしくないのかなって気がします。
しかも、チョイスしたのはいいけど、読んでてちんぷんかんぷんの論文や、
パッと見ただけでそっと閉じた論文も多々あり、
自分の知識や能力、モチベーション的な何かの欠如を改めて実感しました。
研究を行う機関に所属していない自分にとっては、
NIPSやICMLなど、ただでProceedingsをweb公開してくれる国際会議は本当にありがたいです。