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

ICML2012もアクセプトされた論文のタイトルとアブストが公開され、
いよいよ盛り上がってまいりましたが、でも僕はNIPS2011！
懲りずに斜め読み第2弾いきます。
間違って理解している可能性も大いにあり得るので、
それを発見した際には、指摘していただければ幸いです。

Heavy-tailed Distances for Gradient Based Image Descriptors

コンピュータビジョン分野で、SIFTやHOGなどの勾配ベースの特徴量を利用して、
対応点マッチングやbag of keypointsの構築が行われますが、
その際、特徴量同士の比較には大抵ユークリッド距離が用いられます。
ユークリッド距離はノイズがガウス分布の場合に対応する距離ですが、
SIFTのような勾配ベースの特徴量は、ガウス分布に従わないよ！と主張し、
Gamma compound-Laplace (GCL)分布という新たな分布と、
それに基づく距離の計算方法を提案しています。
まず、GCL分布ですが、
$p(x \| \mu;\alpha , \beta)=\frac{1}{2}\alpha \beta^{\alpha}(\|x - \mu \| + \beta)^{- \alpha - 1}$
という式で定義され、高尖度かつheavy-tailedな特性を持つ分布になります
（1次元の確率分布であることに注意）。
ここで、 $\mu$ は特徴のプロトタイプ（サンプル $x$ は $\mu$ にノイズが乗って生成されるという考え方？）、
$\alpha,\beta$ は特性を制御する超パラメータです。
この特性は、SIFT特徴量の分布にフィットするようです。
じゃあ、この分布に基づく距離はどのように定義するか？ですが、
これには、尤度比検定で使われる尤度比を利用します。
具体的には、2つの独立したサンプル $x,y$ が与えられた時、
「2つのサンプルの距離が小さい」->「この2つは同じ分布から生成された」場合は、
$s(x,y)=\frac{p(x \| \hat{\mu}_{xy})p(y \| \hat{\mu}_{xy})}{p(x \| \hat{\mu}_{x})p(y \| \hat{\mu}_{y})}$
（ただし、 $\hat{\mu}_{xy}$ は2つのサンプル $\{x,y\}$ からの最尤推定解、
$\hat{\mu}_{x}$ と $\hat{\mu}_{y}$ はそれぞれ1つのサンプル $\{x\}$ 、 $\{y\}$ から推定される最尤推定解）
という尤度比が大きくなるはずです。
従って、この尤度比に基づき、1つの次元の距離を
$d(x,y)=\sqrt{-\log{(s(x,y))}}$
と定義しています。
これをGCL分布に当てはめると、
$\hat{\mu}_{xy}=x$ または $\hat{\mu}_{xy}=y$ （どちらを採用しても結果は同じ）、
$\hat{\mu}_{x}=x$ 、 $\hat{\mu}_{y}=y$ なので、結果的に距離は、
$d^2(x,y)=(\alpha + 1)(\log{( \| x - y \| + \beta)} - \log{\beta})$
となります。なお、 $\alpha,\beta$ はサンプル集合から最尤推定で求めます。
これは、1次元上の距離なので、多次元ベクトルの場合は、
各次元でこの距離の2乗を算出し、足し合わせてベクトル同士の距離とします。

確率分布を基に距離を定義するため、尤度比を利用するやり方は、
これ以外にも色々応用できそうです。

Efficient Methods for Overlapping Group Lasso

Group Lassoやproximal operatorなど僕が知らなかった&アツそうなトピック満載の論文。
正直、あまり理解できていません。難しい…
まず、Group Lassoですが、それぞれの特徴がいくつかのグループにわけられていた時、
そのグループ毎に正則化を行うことで、グループ単位でパラメータが0になる解が
得られるという手法です。式で表すと、
$\displaystyle \min_{\bf{x} }\hspace{1ex} l(\bf{x})+ \phi_{\lambda_2}^{\lambda_1}(\bf{x})$ 　ただし、 $\phi_{\lambda_2}^{\lambda_1}(\bf{x})=\lambda_1 \parallel \bf{x} \parallel_1 + \lambda_2 \sum_{i=1}^g w_i \parallel \bf{x}_{G_i} \parallel_2$
( $l$ は連続で凸な損失関数、 $\bf{x}_{G_i}$ はグループ $i$ に属する特徴のベクトル、
$w_i$ はグループ毎の重みで、実験ではそのグループに所属する特徴数の平方根を採用)
を解く問題になります。
このGroup Lassoの最適化問題ですが、特徴がそれぞれ1つのグループに所属している場合に比べ、
所属するグループがオーバーラップしている場合、解くのがより難しい問題になるそうです。
これを解くために、この論文では、accelerated gradient descentという最適化の手法を
適用することを提案しています。
手法としては、
$f_{L, {\bf x} } ({\bf y}) = l( {\bf x} )+{<} l'( {\bf x} ) , {\bf y}-{\bf x}\ {>} + \phi_{\lambda_2}^{\lambda_1}({\bf y})+ \frac{L}{2} \parallel {\bf y} - {\bf x} \parallel_2^2$
とし、 ${\bf x}_{i+1} = \arg \min_{{\bf y}}f_{L_i,{\bf s}_i}({\bf y})$ という計算を繰り返していくというものです。
ここで、 $\bf{s}_i={\bf x}_i + \beta_i ({\bf x}_i - {\bf x}_{i-1})$ であり、 $L_i$ と $\beta_i$ は毎回適切なものを探索する必要があります。
さて、
$\displaystyle \pi_{\lambda_2}^{\lambda_1}({\bf v}) = \arg \min_{{\bf x}} \hspace{1ex} \frac{1}{2} \parallel {\bf x} - {\bf v} \parallel_2^2 + \phi_{\lambda_2}^{\lambda_1}({\bf x})$
とすると、毎ステップの最適化式は、次のように変換できます。
${\bf x}_{i+1} = \pi_{\lambda_2/L_i}^{\lambda_1/L_i} \hspace{1ex} ({\bf s}_i - \frac{1}{L_i}l'({\bf s}_i))$
この、 $\pi_{\lambda_2}^{\lambda_1}({\bf v})$ は、proximal operatorと呼ばれ、いろいろと便利な性質を有しています。
例えば、 $\lambda_2=0$ （つまり、通常のlasso）なら、
proximal operatorの最適化問題の解は、解析的に求まります。
この論文でも、group lassoの問題におけるproximal operatorの性質を解析し、
そこから、問題のサイズを小さくするための前処理方法の提案や
その双対問題を解いて更に効率化できると主張しています。
Proximal Operatorを用いた最適化手法は、
損失関数が微分可能かつ凸な関数で、正則化項が凸だが微分不可能という場合に
有効なようで、調べてみると、「解くべき最適化問題のサイズが大きすぎて困っちゃうわ」->
「そんなときは、これ！Proximal Operator」->
「よーし、この問題におけるProximal Operatorを解析しちゃうぞ」
という流れの論文をちらほら見かけました。
また、どちらかというと、Group Lassoという言葉に惹かれてこの論文を読んだので、
そちらに関しても、関連文献をサーベイしたいですね。

Transfer Learning by Borrowing Examples for Multiclass Object Detection

その、Group Lassoを転位学習に応用した論文。
物体検出を目的とした論文で、その検出器の学習を対象となるクラスのサンプル（画像）だけでなく、
他の似たクラスのデータも利用しましょうという手法です。
例えば、ソファの検出器を作る際、色々なクラスの画像データセットを与えると、
ソファクラスの画像だけでなく、肘掛け椅子などの似た画像のクラスも
学習に利用して検出器を構築します。
どのクラスのデータをどれだけの重みで利用するかということも学習します。
今、n枚の画像サンプルがあり、それぞれ $\cal C=\{1 \cdots C \}$ 中の
いずれかのクラスが割り当てられているとします。
加えて、バックグラウンドの画像サンプルもb枚用意し、それには-1と言うクラスを割り当てます。
従って、n+b枚の画像サンプル $({\bf x}_i , y_i)$ ( $i=1,\cdots,n+b$ 、 ${\bf x}_i$ は特徴ベクトル、 $y_i$ はクラスラベル)から
検出対象の検出器の識別関数を学習することになります。
ということで、クラス $c$ における検出器の目的関数は以下の通り。
$\displaystyle \sum_{c \in \cal C} \min_{{\bf \beta}^c} \hspace{1ex} \min_{{\bf w}^{*,c}} \sum_{i=1}^{n+b}(1-w_i^{*,c}) \hspace{2ex} l(<{\bf \beta}^c , {\bf x}_i> , \rm sign(y_i)) + \lambda R({\bf \beta}^c) + \Omega_{\lambda1 , \lambda2}({\bf w}^{*,c})$

( $\min$ の左の $\sum$ は必要なんでしょうか？)
ここで、 ${\bf \beta}^c$ は検出器の識別関数の重みベクトル、
${\bf w}^{*,c}$ はどのサンプルをどの程度の重みで利用するか
決めるベクトル（各要素が $0 \leq w_i^{*,c} \leq 1$ ）です。
従って、 $w_i^{*,c}$ が小さければ小さいほど、そのサンプルの重みは高くなります。
また、検出対象であるクラスcに属するサンプルとバックグラウンドである
クラス-1に属するサンプルの重みは $w_i^{*,c}=0$ という制約を設けます。
（なお、論文内では、 ${\bf w}^{c}=1-\bf{w}^{*,c}$ を重みとして話を進めているのですが、
式の議論を明瞭にするため（?）、目的関数内では ${\bf w}^{*,c}$ を使用しているようです。）
また、 $R(\cdot)$ は ${\bf \beta}^c$ は損失関数に対する正則化項、
$\Omega_{\lambda1 , \lambda2}(\cdot)$ は先ほどみたGroup Lassoの正則化項です。
ここで言うgroupはクラスです。従って、Group Lassoの効果により、
クラスごとにサンプルを学習に利用するか否かの決定がなされます。
あとは、 ${\bf \beta}^c , {\bf w}^{*,c}$ を得るために目的関数の最適化を行う必要がありますが、
それには、一方を固定して一方を最適化する操作を繰り返すという手法をとっています。
この論文のさわりとしてはこんな感じだと思います。
他にも、ソファのクラスの検出器学習に車クラスを利用しなかった場合は、
車クラスの検出器学習にソファクラスを利用しないという制限を加える方法や
対象クラスに適合するための画像変換方法も示されていますが、ここでは言及しません。

しかし、なぜ ${\bf w}^{c}$ のまま式を構築せず、わざわざ ${\bf w}^{*,c}$ を使ったんでしょう？
Group Lassoの正則化項を $\Omega_{\lambda1 , \lambda2}({\bf w}^{c})$ にすれば、
対象に似たクラスのサンプルには高い重みが与えられ、それ以外の重みは0になると思うので、
こちらの方がシンプルだし、理にかなっているような気がするんですが・・・

と言ったところで今回はお開き。
最近、論文読んでばっかりで、全然実装してないですね。