NBNNについて調べてみた

Naive-Bayes Nearest Neighbor(NBNN)とは近年注目されはじめている一般物体認識手法のことです. 現在, 一般物体認識をする手法は大きくに2つに分かれていて, ひとつはSVMやBoosting, 生成モデルに代表されるようなパラメトリックな手法, もうひとつは最近傍探索を基礎とするノンパラメトリックな手法です. ノンパラメトリックな手法は, 学習が必要ない, パラメータチューニングが必要ない, クラスが増えたときなど柔軟に対応できる(パラメトリックな手法だと再学習しないといけない)など, 利点が多くあります.

NNBNはノンパラメトリックな手法に分類されます. パラメトリックな手法では, まず局所特徴量をクラスタリングしてコードブックを作成し, 学習画像をBag-of-Feature(BoF)表現にしてから学習を行うのが一般的です. 一方, ノンパラメトリックな手法では, 量子化誤差の影響で局所特徴量の弁別能力が低下してしまうため, 局所特徴量をそのまま用います.

例えは, 人の顔を分類する場合を考えると, 目や口など特徴的な特徴は全学習画像のなかで顔画像にだけ生起し, エッジなどの特徴はどの画像でも多く生起します. BoF表現を生成する際, クラスタを成していない稀な特徴も, エッジなど多く生起する特徴のクラスタに割り当てられてしまうため, せっかく分類に役立つ特徴を量子化によって失うことになってしまいます. ちなみにパラメトリックな手法では量子化誤差による弁別能力の低下を学習アルゴリズムでカバーすることで高い分類率を誇っている手法もあります(\chi^2-RBFカーネルを用いたSVMによる分類とか ).

さて, 前置きはこのへんにしてNBNNの導出をしたいと思います.
問題は「ある画像Qが与えられた場合, それが属するクラスCを答える」というものです.

クラスの事前分布p\left(C\right)が一様分布と仮定してMAP推定を考えると , 以下の決定則が得られます.
\displaystyle{   \hat{C} = \arg \max_C p \left(C | Q \right)= \arg \max_C \frac{p \left(Q | C \right) p\left(C\right)} {p\left(Q\right)} =  \arg \max_C p \left(Q | C \right) =  \arg \max_C \log p \left(Q | C \right)   }
ここで, クラスCを観測した場合にQの局所特徴量d_1, d_2, \cdots d_nが独立同一分布に従うと仮定すると. 以下の単純ベイズ分類器が得られます.
\displaystyle{  \hat{C} = \arg \max_C  \sum_{i=1}^n \log{p \left(d_i | C \right)}  }

んで, どうやってp\left(d|C\right)なんちゅうもんを求めるかというと, カーネル密度推定法を用います. 局所特徴量の個数は学習画像集合のピクセル数のオーダーとなり非常に多く, カーネル密度推定法でp\left(d|C\right)を近似可能であることがわかっています.
d_1^C, d_2^C, \cdots, d_L^C をクラスCに含まれる全局所特徴量とすると以下のように分布を近似できます.
\displaystyle{  \hat{p} \left (d|C\right) = \frac{1}{L} \sum_{j=1}^L K \left(d -d_j^C \right)   }
\displaystyle{  K\left(d-d_j^C \right)=\exp\left(-\frac{1}{2\sigma^2} || d- d_j^C||^2 \right)  }
カーネル密度推定法は, クラスCに含まれる全局所特徴量と距離を求めなければならないため, 計算量的に重い処理になってしまいます. そこで, 最近傍探索を用いた近似アルゴリズムを考えます.

局所特徴量の分布は裾が重く, 局所特徴量空間中で広範囲に渡って散らばっていることがわかっています. また, 関数Kは距離に依存して指数的に減少していきます(関数の影響範囲はそれほど大きくないということ). そのため, \hat{p} \left(d|C\right)d \in Q近傍のKが大きくなる数個のd_{{NN}_j}^Cのみから, 以下のように近似することができます.
\displaystyle{  p_{NN} \left(d|C\right)=\frac{1}{r} \sum_{j=1}^r K\left(d-d_{{NN}_j}^C \right)  }

上記の近似された分布を用いれば, p\left(Q|C\right)
\displaystyle{  p\left(Q|C\right) = p \left(d_1, d_2, \cdots, d_n|C\right) =\prod_{i=1}^n p_{NN} \left(d_i|C\right)  }
対数をとると
\displaystyle{  \log p\left(Q|C\right)= n \log \frac{1}{r} + \sum_{i=1}^n \log \sum_{j=1}^r K \left(d_i - d_{{NN}_j}^C \right)    }
となります. nはクエリの局所特徴量の個数でCに依存しないので, MAP推定は
\displaystyle{  \hat{C} = \arg \max_C \log p\left(Q|C\right) =  \arg\max_C \sum_{i=1}^n \log \sum_{j=1}^r K \left(d_i - d_{{NN}_j}^C \right)   }
となります. さらに単純化のためr=1とします(著者がrを1〜1000まで変化させて実験したところ分類率に大きな変化は見られなかったそうです). 最終的に, MAP推定は以下のようになります
\displaystyle{  \hat{C} =  \arg \min_C \sum_{i=1}^n \left| d_i - NN_C \left(d_i \right)  \right|^2   }
ようは, クエリの局所特徴量とその最近傍までの距離の総和を各クラスごとに求め, それがもっとも小さいクラス
に分類するということです. まとめるとNBNNのアルゴリズムは以下のようになります.

  1. クエリから局所特徴量d_1, d_2, \cdots d_nを抽出する
  2. \forall C, \forall d_iから最近傍NN_C\left (d_i\right)を求める
  3. クラスの推定値を求める. \hat{C} =  \arg \min_C \sum_{i=1}^n \left| d_i - {NN}_C \left(d_i \right) \right|^2

In Defense of Nearest-Neighbor Based Image Classification

広告
カテゴリー: Computer Vision, Machine Learning パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中