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

なんやかんやで前回から1ヶ月以上たってしまいました。
こりゃいかんということで、NIPS2012 part2いきます。
前回は機械学習の基礎的な手法を提案した論文を紹介しましたが、今回は応用よりの論文を2本取り上げてみました。

Learning Image Descriptors with the Boosting-Trick

画像のローカルな領域の特徴量（特徴ベクトル）記述手法としてSIFTやSURFなど勾配ベースの手法があります*1。これらは、回転・スケール変化などに不変であるため、物体検出等によく利用されますが、不変と言ってもやはり限界はつきもので、これらの特徴量を使っても検出に失敗することも多々あります。
そこで、ラベル付きのデータを用いて、この特徴量自体を教師あり学習的に求めて精度を上げようという枠組みがあります。ここで紹介する論文は、その枠組みの中で、領域の勾配情報を基にした弱学習器 + AdaBoostによって高次元に写像し、そこから特徴量に落とし込むという手法を提案しています。この弱学習器については、論文を参照していただくこととして、ここでは特徴量抽出までの大まかな流れを紹介します。
$\bf{x}$ 及び $\bf{y}$ を画像のパッチとします。また、 $f(\bf{x} , \bf{y})$ を両画像パッチの類似度を示す関数とし、教師データのラベル $l_i$ は与えられた両パッチ ${\bf x}_i ,{\bf y}_i$ が類似しているか ( $l_i = 1$ )、類似していないか( $l_i = -1$ )を表すとします。そして、以下の関数
$\cal{L} = \exp \left(-l_i f({\bf x}_i , {\bf y}_i)\right)$
を最小にする $f$ は何ぞや、ということを考えます。
この論文の手法（Low-Dimensional Boosted Gradient Maps : L-BGM）は、 $M$ 個の勾配ベースの弱学習器 $h_1({\bf x}) , h_2({\bf x}) , \cdots , h_M({\bf x})$ を用意し、それを用いて $f$ を次のような関数として定義しています。

$f({\bf x} , {\bf y}) = f_{LBGM}({\bf x} , {\bf y})=\sum_{i,j} \alpha_{ij}h_i({\bf x}) h_j({\bf y}) = {\bf h}^T({\bf x}) {\bf A} {\bf h}({\bf y})$
これを上記の目的関数に当てはめて、弱学習器 ${\bf h}$ とその重み行列 ${\bf A}$ を学習すればよいのですが、両方を同時に最適化するのは難しい。そこで、最初にAdaBoostの手法を使って各 ${h}_i$ を学習し、その後に目的関数を最小にするような ${\bf A}$ を確率的勾配法で求めるという2stepの手法を提案しています。また、AdaBoostにより各学習器の重み係数が出てきますが、その多くは0になるようです。そのため、 $M$ 個の学習器の一部である $P$ 個だけを使うことになります。ということで、実際には $M \times M$ の行列 ${\bf A}$ ではなく、使用する学習器に対応する要素で構築した $P \times P$ の行列 ${\bf A}_P$ を求め、使用することになります（当然、 $P < M$ ）。
これらを求めると次は、画像パッチ ${\bf x}$ に対する各弱学習器の分類結果及び ${\bf A}_P$ から特徴量を構築します。 ${\bf A}_P$ をランク $d$ の対称行列とすると、この行列は次のように分解できます。
${\bf A}_P = {\bf B}{\bf W}{\bf B}^T = \sum_{k=1}^d w_k {\bf b}_k {\bf b}_k^T$

${\bf B}$ は $P \times d$ の行列、 ${\bf W}$ は要素が1 or -1の対角行列です。すると、類似度は
$f_{LBGM}({\bf x} , {\bf y}) = \left({\bf B}^T {\bf h} ( {\bf x}) \right)^T {\bf W} \left({\bf B}^T {\bf h} ( {\bf y}) \right)$

というように、特徴ベクトル同士の符号付き内積の形で表せます。
従って、 ${\bf B}^T {\bf h}( {\bf x})$ を画像パッチ ${\bf x}$ の特徴量として用いましょうというのがこの論文で提案している手法です。 ${\bf A}_p$ に正定値行列の制約をつければ、 ${\bf W}$ 消せるしもっと良くなるんじゃないの？と考えましたが、論文によるとそのような制約を入れても結果はさほど変わらないようです。
いったん高次元に写像してから特徴ベクトルに落とし込むという点で、カーネルトリックに類似していますが、この論文で主張されているように、カーネルトリックに比べて直感的で良いかなと思います。また、弱学習器次第では他の分野にも応用できそうです。

A P300 BCI for the Masses: Prior Information Enables Instant Unsupervised Spelling

自分が学生時代やっていた研究とドンピシャだったので、思わず目を引いた論文。
脳波など脳活動を計測し、その信号でコンピュータを操作する技術をブレインコンピュータインタフェース（BCI）と言います。その1つとしてP300 Spellerと呼ばれる脳波を利用して文字入力を行うシステムが提唱されています。P300 Spellerでは、ユーザに行または列が１つずつパッと光るアルファベットや記号が羅列されたマトリックスを提示し、ユーザはその中の入力したい文字に着目します。すると、ユーザが入力したい文字が光った時、頭頂部付近から計測される脳波には、光ってから約300ms後にピーク成分が発生します。従って、計測した脳波にP300成分が発生しているか否かを識別すれば、ユーザがどの文字を入力したいか分かるという仕組みです。
ということで、この識別に機械学習の手法を利用した研究が過去多く提案されているのですが、その多くは教師あり学習の手法を利用するために、ユーザ本人から教師データとなる脳波データを予め採取する必要があります。この教師データ取得のための事前計測は、ユーザにとって負担になるため、P300 Spellerの1つの課題として挙がっています。じゃあ、他人の脳波予め採取しておいてそれを識別器に学習させればいいじゃないかと考えますが、個人差の関係上単純な方法ではうまくいきません。
そんな中、教師なし学習によるP300 Spellerの手法を今回取り上げる論文の著者らが提案しました*2。これは、ユーザが入力したい文字はどれであるかという変数を隠れ変数とみなし、EMアルゴリズムによってパラメータを学習する手法です。しかし、この手法ではユーザが使用していくうちに徐々に精度が良くなっていきますが、最初はほぼランダムな結果になってしまうという問題があります。そこで著者らは、他人の脳波データ及び言語モデル（n-gramモデル）を事前情報として利用することで、この問題を解消しようという手法を今回取り上げる論文で提案しています。
他人の脳波を利用する手法は転移学習の枠組みの1つといえます。この手法のモデルとして、著者らは以下のようなものを提案しています。

$p({\bf \mu}_w) = {\cal N} (0 , \alpha_p {\bf I} )$ , $p({\bf w}_s |{\bf \mu}_w) = {\cal N} ({\bf w}_s |{\bf \mu}_w , \alpha_s {\bf I})$
$p(c_{s,t}) = \frac{1}{C}$ , $p({\bf x}_{s , t , i} | c_{s,t} , {\bf w}_s , \beta_s) = {\cal N} ({\bf x}_{s , t , i} {\bf w}_s | y_{s , t , i}(c_{s,t}) , \beta_s)$

ここで、 $c_{s , t}$ は被験者 $s$ が $t$ 文字目として入力したい文字を表します。また、 ${\bf x}_{s , t , i}$ は脳波の特徴ベクトル（行ベクトル）で、被験者 $s$ 、 $t$ 文字目において $i$ 回目に取得した脳波データという意味になります。 $y_{s , t , i}(c_{s,t})$ は、その $i$ 回目において、入力した文字 $c_{s , t}$ が光ったか否かを表すラベル変数です。更に、 ${\bf w}_s$ は今求めたい被験者 $s$ のパラメータベクトル（脳波の特徴ベクトルをP300が発生しているか否かに写像するベクトル）、 $\alpha_s$ 及び $\beta_s$ はそれぞれのガウス分布の精度でこれもEMアルゴリズムで逐次更新されます。 ${\bf \mu}_w$ は各被験者のパラメータベクトルの事前情報となる平均ベクトル、 $\alpha_p$ はそのガウス分布の精度です。
このようなモデルを元に $c_{s , t}$ を隠れ変数と考えてEMアルゴリズムを適用して、 ${\bf w}_s$ , $\alpha_s$ , $\beta_s$ を求めます。大まかな学習の流れは以下の通り。

まず、最初の $S$ 人の被験者についての学習は、 ${\bf \mu}_w = {\bf 0} ,\alpha_p = 0$ として次の操作を収束するまで繰り返します。

$c_{s , t}$ の事後分布 $p(c_{s , t} | {\bf X}_{s ,t} , {\bf w}_s^{old} , \beta_s^{old})$ を求める
$\arg \displaystyle{\max_{{\bf w}_s ,\beta_s}} \sum_{c_s} p(c_{s} | {\bf X}_{s} , {\bf w}_s^{old} , \beta_s^{old}) \ln p( {\bf X}_{s} , c_s | {\bf w}_s , \beta_s) + \ln p({\bf w}_s |{\bf \mu}_w)$ を求めて更新する
$\alpha_s$ を更新する

次に被験者 $s=1 \cdots S$ の ${\bf w}_s$ 及び $\alpha_s$ を得たうえでの、 $S + 1$ 人目の被験者についての学習ですが、これは

${\bf \mu}_w = \frac{1}{\alpha_p} \sum_{s = 1}^{S} \alpha_s {\bf w}_s$ , $\alpha_p = \sum_{s = 1}^{S} \alpha_s$
として上記同様の繰り返しを実行します。

具体的な更新式は書くのがしんどくなってきたので割愛します。論文に載っているのでそちらを参照してください。
上記のモデルで文字の出現確率 $p(c_{s,t})$ は $\frac{1}{C}$ と一定値として扱っていましたが、これをn-gramの言語モデルに置き換えた手法もこの論文中で提案しています。
手法自体は素直にEMアルゴリズムを適用してるので、結構理解しやすかったです。後、P300 Spellerの学習アルゴリズムに関する論文が今でも結構出てるのが少し意外な気がしました。この論文に僕が知らなかったデータセットも載ってたので、久々になんかやってみようかなと思ったり思わなかったり・・・

ということで、前回のと合わせて、あきらめずに読んだNIPS 2012の論文うち4本紹介しました（紹介というより備忘録に近いですが）。ときどき、こうやって学生の頃やってた研究を思い出すのもいい刺激になります。

*1:通常、SIFTやSURFと言うと特徴点検出と特徴量の2段階をひっくるめた手法を指しますが、ここでは特徴量だけのことを指します

*2:P.-J. Kindermans, D. Verstraeten, and B. Schrauwen, A bayesian model for exploiting application constraints to enable unsupervised training of a P300-based BCI. PLoS ONE, 04 2012