【論文紹介】WSABIE: Scaling Up To Large Vocabulary Image Annotation (IJCAI 2011)

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は、WSABIE: Scaling Up To Large Vocabulary Image Annotation という論文を読んだのでメモします。
手法のところ、特に損失関数をメインに解説します。

<a href="https://dl.acm.org/citation.cfm?id=2283856">論文リンク</a>

## 3行まとめ

大きなimage annotationデータセットに対して、画像とタグを同一空間上に埋め込んで内積をとるJoint Word-Image Modelと、Precisionを近似したWARP lossを組み合わせたWSABIEを提案。

## 問題設定

image annotationタスクは、画像に対して適切なタグ(単語)をつけるというタスクで、今回は与えられたタグリストの中からどれが近いかをランキングにして表示する、みたいな状況を想定している。

評価指標はPrecision@kとしている。

## Joint Word-Image Model

こちらは単純で、modelと呼ぶほどのこともなくて、単純に画像とtagのembeddingを得て、内積をとることで類似度を計算している。

同じ長さのembeddingをとるので同じ空間上にtagとimageがembedされる。

## WARP loss

今回の目玉(だと個人的に思っている)。

Precisionの近似になっているlossらしい。

与えられるデータセットには正解のtagが与えられているので、これをrank=1だと思って、この画像に対して予測したランクが1位から離れていれば離れているほどlossが大きくなるように設計している。
予測した順位が$rank_y(f(x))$と表記されている。

予測した順位に対してどのようにペナルティをかけるかはハイパーパラメータで決める。
下のような形を使っている。

$\alpha_1=1$で残りが0だと、正解ラベルを1位で当てればペナルティなし、他は全部lossが同じくらいかかる、というlossになる。
逆に全ての$\alpha_j$が同じ値だと、予測した順位が1位から離れていれば離れた分だけペナルティがかかる、というような仕組みである。

ここまでは既存の研究で使われているlossで、既存研究では後者の設定がprecision@kでいいパフォーマンスが出ているので今回もそれに倣うとのこと。

ただ、既存の手法ではそのままこのlossが使えたが、今回のembeddingモデルには使えず、またデータが多くなってメモリに乗らなくなった時にしんどいので、onlineバージョンで動くように近似したバージョンのlossを考えました、というのが今回の貢献。

もとのlossを、indicator functionのところをヒンジ損失みたいにして、あと(ここはよく分からないですが)マージンを追加している(1足している？)ように見える。

これをデータセットに関して積分したものを最小化する。

画像 xと正解タグyをもらったあと、分子のヒンジ損失が0でない(損失を生じてしまう)ようなタグ$\bar y$をもってくる。

このtripletは全体のlossに対して

だけ寄与する。(損失を生じるtag $\bar y$をとってくるところの確率が元の損失の分子の部分に相当するので、期待値をとると、元のlossをバイアスなく表現できている。)

あとはこのlossの勾配をとって勾配降下して更新すればいいけれど、まだ二つ問題がある

* $\bar y$を見つけるのに全タグで予測する必要がある
* $rank^1_y(f(x))$を計算するのに、全タグで予測する必要がある

今回の論文では、この問題を同時に解決している。

解決方法は、

損失を生じるタグが出るまでtagをランダムにサンプリングし、出るまでにかかった試行回数を記録しておく。
これはパラメータが$\frac{rank^1_y(f(x))}{Y-1}$の幾何分布なので、逆に

$$
rank^1_y(f(x)) \approx \lfloor \frac{Y-1}{N} \rfloor
$$

と推定できる。($N$が試行回数)

## おわりに

実験は省略します。興味を持たれた方は読んでみてください。

個人的に面白ポイントは、サンプリング回数でランキングを推定できる、というところですね。
同時に二つの課題を解決しているのが面白いです。

今回この論文を読んだ理由に、LightFMというライブラリがWARP lossをサポートしていて、どんなlossなのか気になったからというのがあります。

LightFMを触ってみて書いた記事がこちらです。よかったらぜひ。

ぐぐりらにっき