ぽんぽこ日記

このブログはタヌキによって書かれています

Learning Fine-grained Image Similarity with Deep Ranking

Deep Metric Learning系の論文を読んでいこうかなと思います。
Learning Fine-grained Image Similarity with Deep Ranking [1]
この論文は有名なTriplet Lossが提案された論文です。CVPR2014で発表されました。
時の流れを感じる(´；ω；｀)

0. ざっくり説明

全部読むの面倒くさい人用

1. 導入

embeddingした画像同士の距離(非類似度)は以下のように定義できる。
この距離を上手く学習したい。

{ \begin{align} D(f(P), f(Q)) = | | f(P) - f(Q) | |_{2}^{2} \end{align}\tag{1}}

D(., .) : embedding spaceのユークリッド距離
f(.) : embedding function
P, Q : 画像

2. 主な考え

[2] より引用

Negative(Anchorと別カテゴリの画像)よりもPositive(Anchorと同じカテゴリ)よりもξ(マージン分)に遠くにいてねという考え
注: この論文ではAnchor, Positive, Nagetiveという表現ではなくQuery, Positive, Negativeという表現をしています。

具体的例

[1] より引用

3. 定式化

Negative(Anchorと別カテゴリの画像)よりもPositive(Anchorと同じカテゴリ)よりもξ(マージン分)に遠くにいてね

これを定式化 {\begin{align} D(f(p_i), f(p_i^{+})) \lt D(f(p_i), f(p_i^{-})),　 \\ \forall p_i, p_i^{+}, p_i^{-} ~ \mbox{such that} ~ r(p_i, p_i^{+}) \gt r(p_i, p_i^{-}) \end{align} \tag{2}}

r(., .) : pairwise relevance score (画像ペアの関連度合いを示す関数)

{t_{i}=(p_i, p_i^{+}, p_i^{-})} : クエリ(画像{p_i})に対して、距離が小さい(似ていてほしい画像)と距離が遠い(似てほしくない画像)の組み合わせ
ここでトリプレットという考え出てきたんですね。

各トリプレットに対して、損失は以下のように定義できる。
{\begin{align} l(p_i, p_i^{+}, p_i^{-}) = \max \lbrace 0, g+D(f(p_i), f(p_i^{+})) - D(f(p_i), f(p_i^{-})) \rbrace \end{align} \tag{3}}

{g} : {(p_i, p_i^{+})}と{(p_i, p_i^{-})}の距離を調整する正則化パラメータ

最適化問題

{ \begin{align} &\min \sum_{i} \xi_i + \lambda \| \textbf{W} \|_{2}^{2} \\\ &s.t. : \max \lbrace 0, g+D(f(p_i), f(p_i^{+})) - D(f(p_i), f(p_i^{-})) \rbrace \\\ &\forall ~ p_i, p_i^{+}, p_i^{-} ~ \mbox{such that} ~ r(p_i, p_i^{+}) \gt r(p_i, p_i^{-}) \end{align} \tag{4} }

{\xi_i} : { \max \lbrace 0, g+D(f(p_i), f(p_i^{+})) - D(f(p_i), f(p_i^{-})) \rbrace }と同じ
{\lambda} : 過学習を防ぐ正則化パラメータ(論文では{\lambda=0.001}を採用)
{\textbf{W}} : 学習されるパラメータ

[1] より引用

4. Network Architecture

式(4)で定義した損失関数を以下のアーキテクチャで学習

[1] より引用

5. OptimizationとSamplinng

5.1 Optimization

5.2 Triplet Sampling

基本的な考え: 検索結果上位に興味があるので、 対象となる画像の近くだけ上手く学習できていればいい
{ \begin{align} r_i=\sum_{j:c_j=c_i, j \neq i}^{N} r_{i,j} \end{align} \tag{4} } {c_i} : 画像{p_i}が属するカテゴリ
{r_i} : 画像{p_i}と同カテゴリの画像とのpairwise relevance scoreの総和

5.2.1 画像{p_i}の選び方

  • {r_i}の割合によってサンプリングされる。
  • {r_i}の値が大きければ大きいほど、画像{p_i}がクエリとしてサンプリングされやすくなる。

5.2.2 Positiveの選び方

{p_i}に対して高いpairwise relevance scoreを持つ画像をPositiveとしてサンプリングしたい

{ \begin{align} P(p_i^{+})= \frac{\min \lbrace T_{p} , r_{i,i^{+}} \rbrace}{Z_i} \end{align} \tag{5} } {T_p} : 閾値
{Z_i} : the normalization constant, {\sum_{i^{+}}P(p_i^{+})}と同じ

5.2.3 Nagetiveの選び方

2種類ある。
1つ目: 画像{p_i}とは異なるカテゴリから選ぶ方法 (Out of class negative sample)
別カテゴリに属する画像から一様にサンプリングされる。

2つ目: 画像{p_i}とは同じカテゴリから選ぶ方法(In-class negative samples)
画像{p_i}と同じカテゴリだが、画像{p_i}とのpairwise relevance scoreが低い画像

トリプレットが満たすべき条件

全てのトリプレットは式(6)を満たすようにする。
{ \begin{align} r_{i,i^{+}} - r_{i,i^{-}} \geq T_r, \\ \forall ~ t_i = (p_i, p_i^{+}, p_i^{-}) \end{align} \tag{6} }

どうやっているか

流れとしては画像{p_i}選んで、positiveを選び、negativeを選ぶ。

Positiveサンプル 学習データを全てメモリにのせて計算することは不可能なのでBuffersを使う。
- 各Bufferは一定の容量を待つ(下の図だと画像6枚分)。同じカテゴリの画像を保持する。
- Bufferに空きがあるなら画像{p_j}をBufferに入れる。
- Bufferが埋まっているならBuffer内の最小の{k^{ \prime }_j}の値を守る画像{p^{ \prime }_j}と画像{p_j}を入れ替える。

{k_j = u_j^{\frac{1}{r_j}}} : 画像をBufferに入れるかどうかを決めるスコア。{r_j}が大きければ大きい値を持つように設計されている。
{r_j} : 画像{p_j}と同カテゴリの画像とのpairwise relevance scoreの総和
{u_j} : {uniform(0,1)}からサンプリングされた値

Negativeサンプル 画像{p_i}とは異なるカテゴリから選ぶ方法では 他のBufferから一様にサンプリング。

画像{p_i}とは同じカテゴリから選ぶ方法
式(6)を満たすやつをサンプリングする。

どっちのNegativeサンプリングを行うかはパラメータを与えて制御する。

[1] より引用

6. 実験

6.1. データ

ImageNet ILSVRC-2012データセット
ConvNetのpre-trainに使用
- 1000カテゴリ
- 各カテゴリ約1000枚
- training images 約120万枚
- validation images 5万枚

Relevance training data
筆者が作ったデータセット。 fine-tuningに使用。
- Google画像検索から10万件の検索クエリより作成
- 各クエリから上位140件の画像結果を取得
- 画像数は約1400万枚
- 同じ検索クエリからの画像に対して{r_{i,j}}を計算
- 異なるクエリからの画像は{r_{i,j} =0}とする

Triplet Evaluation Data
トリプレットデータセット。モデルの評価に使用。
- 1000のクエリ用意し、Google画像検索エンジンから各クエリの検索結果上位50件からトリプレット(Q、A、B)をサンプリング
- 人間の評価者を用いて、トリプレット(Q、A、B)を評価
- 人間の評価者は以下の4種類の評価を各トリプレットに与える
(1) 画像AとBの両方がクエリ画像Qに類似する
(2) 画像AとBの両方がクエリ画像Qに類似しない
(3) 画像AはBよりもQに類似する
(4) 画像BはAよりもQに類似する
- 各トリプレットは3人の評価者によって評価される
- 3人の評価者の評価が一致したトリプレットのみが最終的なデータセットとして採用
- (1)と(2)の評価を与えられたトリプレットは画像の類似度順序を反映していないため、今回のデータセットしては採用しない
- 約14,000個のトリプレットが用意された

6.2. 評価指標

  • similarity precision

  • score-at-top-K (K=30)

実験1: representationの比較

比較手法

Hand-crafted Features
- Wavelet - Color (LAB histoghram) - SIFT-like features - SIFT-like Fisher vectors - HOG - SPMK Taxton features with max pooling

モデル
上の特徴量を全て使って以下のモデルを適用
- L1HashKCPA
- OASIS

実験結果

提案手法: Deep Ranking(画像{p_i}とは異なるカテゴリから選ぶ方法の割合を20%)

  • 学習させてない(Wavelet, Color, SIFT-like features, SIFT-like Fisher vectors, HOG, SPMK Taxton features with max pooling)やつの性能は微妙
  • L1HashKCPAは1000次元という次元の割にはいい性能だが、DeepRankingには負ける
  • OASISはRelevance training dataを情報を用いているが、DeepRankingには負ける。「特徴抽出」-「モデル学習」の二段階のアプローチよりも画像に対してランキングモデルを直接学習することがいい

Table 1. Similarity precision (Precision) and score-at-top-30 (Score-30) for different features.
[1] より引用

実験2: アーキテクチャーの比較

比較手法

  • ConvNet
  • Single-scale deep neural network for ranking
  • Single-scale deep neural network for rankingの出力に対して、OASIS学習させたもの
  • Single-scale deep neural network for rankingの出力とHand-crafted Featuresを組み合わせたもの

実験結果

  • Deep Ranking (提案手法)が強い

    Table 2. Similarity precision (Precision) and score at top 30 (Score-30) for different neural network architectures.
    [1] より引用

実験3: サンプリングの比較

画像{p_i}とは異なるカテゴリから選ぶ方法の割合変えたらどうなるの？

実験結果

  • 一様サンプリングよりもいい
  • Out of class negative sampleの割合を大きくするとscore-at-top30は下がる
  • Out of class negative sampleの割合を20%を超えるとsimilarity precisionが上がる

    Figure 6. The relationship between the performance of the proposed method and the fraction of out-of-class negative samples.
    [1] より引用

実験4: Ranking Examples

実際Rankingは上手くいっているのか?

実験結果

Figure 7. Comparison of the ranking examples of ConvNet, Oasis Features and Deep Ranking. [1] より引用

References

[1] Wang, Jiang, et al. "Learning fine-grained image similarity with deep ranking." Proceedings of the IEEE conference on computer vision and pattern recognition. 2014.
[2] Schroff, Florian, Dmitry Kalenichenko, and James Philbin. "Facenet: A unified embedding for face recognition and clustering." Proceedings of the IEEE conference on computer vision and pattern recognition. 2015.