従来型BoVWの変換

Explicit feature map

これに関してはどちらかというと識別器の工夫で、BoVWという表現そのものは何も変わりないのですがけっこう大事だと思うので。

冒頭で述べたようにBoVWには非線形カーネルの利用が必要でした。もともとカーネルはunknownな高次元空間における内積を観測空間で行うためのツールでしたが、これを用いるとサンプル数に対するスケーラビリティは著しく落ちます（O(n^2)〜O(n^3)）。だったら、その高次元空間への写像（feature map）を明示的に書き下してしまって直接線形識別器（O(n)）を使えばいいじゃないかというのがモチベーションです。もちろん、一般的にはそのような高次元空間が書けるとは限りませんが、BoVWのようなヒストグラム特徴でよく用いられるカーネルについては比較的簡単に設計できることが分かっています。

おそらく、最初に有名になったのは次の論文です。この論文では、ヒストグラムインタセクションカーネルのfeature mapが示されています。

Subhransu Maji, Alexander C. Berg, Max-Margin Additive Classifiers for Detection, ICCV 2009.

このアプローチはすぐに、さまざまなadditive kernelへ拡張されています。Additive kernelとは、ヒストグラムのビンごとに定義される非線形カーネルの線形和で書けるカーネルのことで、さっきのインタセクションカーネルやカイ二乗カーネルなどが代表例です。

A. Vedaldi and A. Zisserman, Efficient additive kernels via explicit feature maps, CVPR 2010.

Florent Perronnin, Jorge Sánchez and Yan Liu, Large-Scale Image Categorization with Explicit Data Embedding, CVPR 2010.

一般的なRBFカーネルについては同様の方法がもっと前から提案されています。フーリエ変換を利用して代表点をサンプリングするようです。

A. Rahimi and B. Recht, Random features for large-scale kernel machines, NIPS 2007.

これをgeneralized RBFカーネルに応用したものも提案されています。

Sreekanth Vempati, Andrea Vedaldi, Andrew Zisserman, C. V. Jawahar,
Generalized RBF feature maps for Efficient Detection, BMVC 2010.

一般的に、カイ二乗距離等を用いたGRBFが精度面では最も優れているので、これが一つの完成形であると言えるでしょう。

Feature mapの考え方は非線形識別問題における一般的なもので、BoVWという表現そのものを変えるものではありません。次節で見ていきますが、最近はBoVW自体の意味を見直す動きが広がり新しい特徴表現が登場してきたこともあり、feature mapは現在ではあまり見なくなった気がします。が、逆に言えば今までに抽出したBoVW*1があればそれはそのまま利用できます。
前述のMaji & Bergの手法をBoVWに適用し、10,000クラスの大規模な識別実験を行った例が報告されています。

Jia Deng, Alexander C. Berg, Kai Li, and Li Fei-Fei,
What Does Classifying More Than 10,000 Image Categories Tell Us? ECCV 2010.

*1:もちろん、他の特徴ベクトルでも利用できるでしょう。