Rest Term

Blog

GPU対応の類似検索(最近傍探索)ライブラリ Faissの紹介 part1 導入/チュートリアル

Facebook AI Research (FAIR)が開発したGPU対応の類似検索ライブラリ Faiss を紹介します。

論文は以下で公開されています。

論文タイトルの通り、10億スケールの大規模データに対してGPUを駆使した効率的な最近傍探索アルゴリズムの研究事例となっています。分量が多くなりそうなので複数の記事に分けて紹介しようと思います。

環境

Amazon Linux AMI release 2017.03
Intel Xeon CPU E5-2686 v4 @ 2.30GHz
NVIDIA GK210GL [Tesla K80]
Ubuntu 16.04 LTS (x86_64)
Intel Core i5-2500K CPU @ 3.30GHz
NVIDIA GM204 [GeForce GTX 970]
CUDA Toolkit 8.0
GCC 4.8.3 / 5.4.0
Python 3.5.2
NumPy 1.12

最初はTesla系GPUを使いたかったのでEC2のp2.xlargeインスタンス上で動作確認をしてましたけど、やっぱりオレゴンは遠くてターミナルがもっさりするので途中から自宅サーバに切り替えて作業しました。快適です。ちょっと前にGTX 1070を買いましたので、お下がりのGTX 970をLinuxサーバに挿しています。GTX 760は使い途がないのでメルカリかヤフオク行きですかね。

導入

※ GPU環境がある場合はNVIDIA DriverとCUDA Toolkit 8.0以降の事前導入が必要です

ここでは通常のC++ライブラリ(GPU非対応)、GPU対応のC++ライブラリ、Python用のライブラリをそれぞれソースコードからコンパイル/インストールします。プラットフォーム毎にMakefileから読み込む設定(makefile.inc.xx)が用意されているのでコピー・編集して使います。2017/05現在、CMake対応も進められているようですけれどまだ作りかけなので普通にmakeでコンパイルした方がいいかと思います。

CPU版C++/Pythonライブラリはビルド時にBLASライブラリをリンクしますが、ここではBLAS実装としてOpenBLASを利用しました。Intel MKLやAtlasでもOK、macOSならAccelerateフレームワークにBLAS実装が含まれているのでそれも利用できます。対応ライブラリの中ではIntel MKLが最速ですので、もしプロダクション環境等で可能な限り高速化したい場合はMKLをリンクさせましょう。GPU版はcuBLASが利用されます。こちらはCUDA Toolkitに含まれているので別途インストールする必要はありません。最近のCUDAだとBLAS drop-inライブラリとしてNVBLASが付属しているのでそちらをリンクするプロダクトも増えてきたように思いますが、FaissではcuBLASでこつこつと実装されているようです。

GTX 970のCompute Capability(CC)は5.2なのでそれ以外のコード生成オプションは削っておきます。デフォルトのままでも問題ないですけど、無駄を省いてコンパイル時間を短くしたいならハードウェア環境に合わせて設定すると良いです。

PythonインタフェースはSWIG(3.x以上)でビルドされます。依存ライブラリとしてNumPyも必要なので事前にインストールしておきます。

Makefileの準備と依存ライブラリの導入が終わったら後はコンパイルするだけですが、最低限 SSE4.2/POPCOUNT/OpenMP に対応しているCPU/C++コンパイラが必要となっています。AVXは使ってないようなのでSandy Bridge以前のかなり古いモデルでも大丈夫なはずです。

GPU版 C++ライブラリはコンパイルにかなり時間がかかると思います。最近だとこういう手順でプロダクトをインストールするのは逆に新鮮に感じます。リリース初期の頃のCaffeみたいだ。

ちなみに付属のMakefileはinstallターゲットがないので、手動でライブラリとヘッダファイル群を任意の場所に配置します。ここでは既にパスの通ったディレクトリに置きました。

動作確認

CPU版 C++ライブラリのビルド時にテストプログラムもコンパイルされて実行可能バイナリが生成されているのでそのまま実行できます。GPU版も用意されているのですが、これは2017/05現在、バグがあって特定のGPUだとSEGVしてしまうので完走できません。どうやらGeForce系GPU(GTX 970や1080)でのクラッシュ報告が多いようです。EC2 p2-xlargeインスタンスのTesla-K80なら大丈夫でした。

テストプログラム内部で行われていることはチュートリアルを進めていけばわかるようになるのでここでは省略します。公式のチュートリアルよりもコードは綺麗な気がしますけど。。

チュートリアル

公式のチュートリアルに補足を加えながら順番に動作確認していきます。

Faissが提供するクラスや各機能が扱うデータの型を意識しながら学んだ方がより理解しやすいと思うので、最初はC++インタフェースで試します。Pythonインタフェースは前述の通りSWIGで生成されているため、C++インタフェースが使えるようになればPythonインタフェースを使うための学習コストは少なくなります。

データの準備

Faissが扱うベクトルデータは基本的に単精度(32bits)浮動小数点値を要素とした配列を用います。C++ならfloat型配列 、Python(NumPy)だと numpy.ndarray オブジェクトとなり、1つのベクトルを1行としたrow-majorな行列データとして扱うことになります。

64次元ベクトルデータをデータベース登録用に10万個、検索クエリ用に1万個それぞれ作成しています。各ベクトルの1次元目の値だけ修正してますが、検索時にその意図がわかるのでここでは気にしなくても良いです。このチュートリアルでは通常のfloat型配列で入力データを管理していますが、Faissの実装を読んでみたところ、インデックス作成時に std::vector のコンテナにデータを詰め替えています。もしOpenCVと併用するなら cv::Mat に変換するアダプタを作っておきたいですね。

インデックスの作成

データベースのインデックスを作成します。ここからはFaissのAPIを使っていきますが、インデックスの種類はたくさんあるのでここでは基本的なものをピックアップして紹介していこうと思います。

faiss::IndexFlatL2

まずは基本となる距離尺度にL2ノルム(L2距離)を利用したインデックスの作り方を確認します。

IndexFlatL2 はL2ノルムでの全探索用(Brute-force search)インデックスとなっており、入力ベクトルデータは未加工のまま全て登録します。publicなメンバとして is_trainedntotal を参照していますが、それぞれインデックスの学習済フラグ(データ分布等を事前解析、IndexFlatL2では利用されない)、登録データ数を示しています。

検索

データの登録が終わったら検索してみます。前手順で作成した検索クエリ用データを利用してk-近傍探索を行います。

* 出力結果例

データベースに登録したデータ、検索クエリ用のデータも全てランダムに生成したにもかかわらず、類似検索結果のインデックスに偏りがあることがわかります。ここで、データ生成時に各ベクトルの1次元目のデータだけ少し加工したことを思い出しましょう。データ配列のインデックス値に依存する数値が加算されており、検索結果にもその影響が表れていることが確認できます。

もし、データを加工しない場合は以下のような検索結果になります。

2017/05現在のCPU版の実装では、次元数が4の倍数かつ同時検索クエリ数が20件以下の場合はSSEを使って距離計算をしてくれるようです。つまり、上記コード中の最初のsanity checkではSSEを利用、検索クエリデータ xq での検索ではインストール時に採用したBLAS実装(ここではOpenBLAS)に計算処理が委譲されます。また、マルチスレッドで処理される箇所はOpenMPを使って実装されているので大変読みやすくて助かります。

faiss::IndexIVFFlat

IndexFlatL2 をそのまま利用すると、いくらSSEやOpemMPを駆使して計算をしたとしても検索速度が遅くなってしまうため、Billion-scaleの大規模データに対応することは困難です。ここでは、入力ベクトルデータをクラスタリングしておき、検索時にはクエリデータに対応するセルおよび近隣のセルをいくつか選び出して、それらのセルに属するデータのみを最近傍点の候補として距離計算を行うことで検索時間を削減します。

* 出力結果例

IndexIVFFlat は各セルの代表ベクトル(母点)を保存しておくための転置ファイル(転置インデックス)用のクラスとなっており、処理手順としてはベクトル量子化処理の学習ステップが一つ増えています(IndexIVFFlat::train)。publicなメンバである nprobe で検索対象のセル数を管理しており、この値を増やすと検索精度の向上と引き替えに検索時間が増えます。上記チュートリアルでは全探索と比較してnprobe=1で15 ~ 20倍、nprobe=10で3 ~ 5倍くらい検索速度が向上しました。

faiss::IndexIVFPQ

IndexFlatL2 および IndexIVFFlat を併用した場合でも、入力ベクトルデータは全て未加工でインデックス登録していました。これでは数億オーダーのデータを全てメモリ上に載せるのは現実問題として困難です(NVMe等ストレージハードウェアも急激に進歩しているのですがここでは考えないこととします)。次は、入力ベクトルデータをProduct Quantization(PQ: 直積量子化)により圧縮することでインデックスするデータ量を削減します。PQはハッシュベースの手法に替わってここ数年の論文等でよく見かけますね。Product Quantizationに関する日本語の概要説明については以下の映像奮闘記さんのエントリーが読みやすくて参考になるかと思います。

  1. クエリベクトルをM分割し、N/M次元のサブベクトルに分解する
  2. クエリのサブベクトルと、それぞれのコードブックに記された代表ベクトル間の距離を予め計算しておく
  3. それぞれのエントリがどのインデックスに位置しているのか確認し、2で計算した距離を参照して足し算を行う
  4. 最小距離をもつエントリを候補として提出する

* 出力結果例

IndexIVFPQ はPQを伴う転置ファイル用クラスです。上記チュートリアルではサブベクトル数を8、各サブベクトルは8bitsにベクトル量子化されます。つまり、元データは64(次元数)*32(float)=2048bits、PQすると8*8=64bitsとなり32分の1のデータサイズとなります。また、各サブベクトル毎の距離計算は独立しているため並列処理とも相性が良さそうです。IndexFlatL2 による全探索(線形探索)結果を比較すると量子化の影響は見られますが、高い精度を維持できていることが確認できます。

注意点として、C++版チュートリアルのコードはGPUではなくCPUで動作します。GPU版実装の詳細は次回パート以降に紹介する予定です。

おわりに

今回はチュートリアルレベルの内容でしたので特に目新しい部分は無かったかと思います。Faissの論文は一通り読みましたが、主にGPU上で効率的に計算するアルゴリズムの記述が主でしたので、次パート以降はその理論や実装面についても深掘りしていきたいと思います。

SSEやOpenMP、CUDAを活用した処理は学生時代にけっこう勉強したんですけど、すっかり知識が抜けていたので焦りました。普段のWebアプリケーション開発の現場だと触れる機会がないですから、この分野の技術はプライベートの時間を使ってじっくり学んでいきたいです。

参考

 

Tags: , ,

NumPy入門記事をアップデートしました

4年以上前の記事ですけど、今もたくさんのアクセスがあるようなので内容を少し更新しました。さすがに古すぎる記事をずっと見続けてもらうのは気が引けますから。

更新内容

  • CentOS 7.0, Python 3.6, NumPy 1.12で動作確認
  • Record Arrays, Automatic Reshaping, 乱数生成, Linear Algebra(線形代数)について新規説明を追加

NumPyは多くの機械学習系フレームワークや画像処理ライブラリ内部で利用されているのでインタフェースの互換性には十分気を遣っているようです。今後も必要に応じて内容更新していければと思います。

 

Tags:

JavaScriptでLSDによる高精度な直線検出

ここ半年くらいは機械学習関連技術のJavaScript実装を行ってきましたが、今回は久しぶりに画像処理関連の要素技術を調べました。

Line Segment Detector (LSD) と呼ばれるアルゴリズムになります。

画像: 東京ガーデンテラス紀尾井町 - Tokyo Garden Terrace Kioicho

LSDによりデジタル画像中から高精度に直線(line segmentなので厳密には線分)を検出することができます。直線検出と言えば、Hough(ハフ)変換と呼ばれる古典的なアルゴリズムが著名かと思いますが、LSDはHough変換よりも検出精度が高い手法となっています。LSDの論文が出たのが2012年のようなので思ってたより新しいですね。直線検出のようなシンプルかつ重要な要素技術もまだ枯れてなくて、地道に発展しているのはなんだか嬉しい感じです。

まとめ

時間がない人のため。

Line Segment Detector (LSD)アルゴリズムをJavaScriptで実装し、評価用の簡単なデモを作りました。

* ソースコード: JavaScript (ES2015) + React + Material-UI

* デモ (Chrome, Firefoxで動作確認)

LSD Demo

LSD Demo

LSD (Line Segment Detector) 概要

LSDのアルゴリズムは以下のようになっています(元論文より画像引用)。

LSDでは以下のFigure 1ような画像中の場所をLevel Line、小さな領域内(2x2画素)での輝度勾配とLevel Lineの角度(LLA: Level Line Angles)を画像全体で計算したものをLevel Line Fieldと定義しています(Figure 2)。そして生成したLevel Line Field内から直線領域候補(Line Support Regions)を計算します。

Algorithm 1 L6: RegionGraw のアルゴリズム詳細は以下の通り、LLAの情報を元に直線の領域をちょっとずつ(8近傍画素を都度見ながら)増やしていく反復処理になっています。

直線領域候補を計算できたら、L7: Rectangle でその領域を矩形に近似することで直線を検出します(Figure 3)。L8: AlignedPixelDensity 以降の処理は L7: Rectangle で求めた矩形の形を整えたり、不要な領域を削除して精度を向上させる処理となっています。

実は、 L12: ImproveRectangle 以降の処理を省略しても精度はそれほど悪くなりません。実際、後述するOpenCVのLSD実装ではデフォルトパラメータでは L12: ImproveRectangle 以降の処理は実行されません。それ以上に L1: ScaleImage 内で前処理として行われるガウシアンフィルタの有無の方が精度に大きな影響を与えるようです。サブピクセル精度を求めたいケースでは全ての処理を行うといった使い方が良いかもしれません。

実装

今回はTypeScriptではなくJavaScript(ES2015)で実装してみました。

その前に既存の実装についていくつか紹介します。一つ目はオリジナルのC言語ソースコード、論文PDFといっしょに公開されています。注意点としては、ソースコードのライセンスがAGPLv3になっていることです。もし業務等で利用する際には十分注意してください。

二つ目はOpenCVのC++実装です。ハードウェアレベルでもいくらか最適化されているため、不都合がなければOpenCV版(C++/Python)の利用をオススメします。今回はこのOpenCV版を参考にJavaScript実装を行いました。

三つ目はnpmのパッケージです。emscriptenでオリジナルのC言語のソースコードをJavaScriptに変換して作成されています。なので処理の実体はオリジナルと同じですね。

emscriptenは便利で僕も好きですけど、バインディングを作っても理論の勉強ができないので今回も素朴にJavaScriptで一から書いています。ソースコード群はいつものようにGitHubにUPしています。

* デモ (Chrome, Firefoxで動作確認)

JavaScriptでの使い方は以下のようにしました。

LSD内部ではたくさんのパラメータがあってあまり吟味できてないんですけど、とりあえず論文に載ってる値やOpenCV実装内部の値をそのまま設定しています。

また、今回作成したデモはReactを使っているので、LSD動作確認用のReactコンポーネントも作ってみました。完全にデモ用なので汎用性は無いですけど。

* Reactコンポーネント使用例

コンポーネントのsrc属性に画像を指定するだけで利用できます。Material-UIを併用しているので、material-uiモジュールが必須になっているのはかっこ悪い気がします。より良いReactコンポーネントの設計方法を学びたいです。

精度評価

古典的手法であるHough変換はJavaScriptで実装していないのでまずはOpenCV実装を使って比較します。左がHough変換、右がLSDによる検出結果です。注意点としては直線ではなく線分検出処理を比較したいので、標準的Hough変換ではなく確率的Hough変換を使っています。

* 左: Hough変換(cv::HoughLinesP) 右: LSD(cv::LineSegmentDetector)

今回実装したJavaScript版のLSDの検出結果は以下の通りです。OpenCV版とほぼ同じ出力結果になりましたが細部の結果は異なっています。実はOpenCV内部ではatan2などの数学関数を高速化の為に近似処理(cv::fastAtan2など)をしているのですが、僕のJS実装ではMathモジュールの数学関数をそのまま利用しています。さらに、JavaScriptだとC/C++と異なり、単一の整数値(charやint型)を直接扱えないのでその影響が積もって多少精度に差がでているようです。

* 今回実装したJavaScript版の検出結果

検出難易度が高そうな画像で比較すると差は歴然です。確率的Hough変換が苦手とするタイプの画像でもLSDなら大きな精度低下はなく安定しています。

* 左: Hough変換(cv::HoughLinesP) 右: LSD(cv::LineSegmentDetector)

JavaScript版の検出結果は以下の通り、細かい線分がたくさんある画像だとOpenCV版との検出精度の差が大きくなるようです。近似処理をしていない分、JS版の方が精度が高いような気もしますけど、まぁ気のせいです。

* 今回実装したJavaScript版の検出結果

いずれにせよ確率的Hough変換と比べてLSDの方が精度が高いことが確認できました。LSDの方が複雑な処理をしているので精度が高いのは当然だよなぁという印象です。パラメータを吟味すればさらに精度は上がるのかもしれませんけど、元論文には「It is designed to work on any digital image without parameter tuning.」とあるので論文内のパラメータをそのまま使うのが適切なんでしょう。確率的Hough変換は投票値の閾値や同一の直線とみなす画素間隔などのパラメータ調整が面倒ですから、精度だけでなく使い勝手の点においてもLSDが勝っていると言えそうですね。

処理速度の点においては確率的Hough変換の方に分がありそうですが、これは実装の質にかなり依存するようです。OpenCV実装では確率的Hough変換よりLSDの方が高速でしたが、オリジナルのC実装はかなり遅かったです。

おわりに

LSDはたぶん僕が今までJavaScriptで実装したアルゴリズムの中でも一番実装が大変だった気がします。ここ数回は機械学習アルゴリズムを実装・公開してきましたけど、それと比べたら遙かに面倒でした。ただ、機械学習と違って学習データを集めたりする雑務が不要だったのは救いです。古い手法と比較したい場合は、新しい手法から先に実装してしまうと古い手法を実装するモチベーションが湧かなくなってしまうので今後は注意して取り組みたいです。LSDを先に実装してしまったらHough変換はもう作らなくていいかってなってしまったので。ちなみに、特徴量ベースのアプローチとして Line Band Descriptor (LBD) という手法も提案されています。時間を作ってまた調べておこうと思います。

 

Tags: , ,

PCパーツ新調メモ 2017/01

このお正月にOSとSSDを新調しました。前回のエントリーからの差分をメモ(記載価格は購入当時の価格)。

OS Windows10 Pro \13,824
SSD PLEXTOR M8Pe PX-512M8PeG-08 512GB SSD \31,900
VIDEO GeForce® GTX 1070 GAMING X 8G \61,775

PCパーツは値動きが激しいので欲しいと思った時が買い時。1万円未満の価格差なら誤差と考えると気楽に買い物できるのでオススメです。

ねんがんのNVMe SSDをてにいれたぞ。

USBフラッシュメモリと並べてみるとコンパクトさがよくわかります。

容量単価は高いですが性能も高いです。ただし、M.2接続のSSDを使う際には発熱によるサーマルスロットリングを避けるためにも温度管理には気を遣いたいところ。室温20℃の環境においてCrystalDiskInfoで計測すると人の体温と同程度の温度。SATA接続のHDDよりも8 ~ 10℃前後高かったです。ヒートシンク付きモデルなのでこの程度で済んでいるのかどうか、夏場は一層注意したいです。

あとはNASとしてQNAP TS-251+も去年秋頃に購入し、ユーザーデータは全てNAS上に置くようにしました。もちろん外部からもアクセスできるようにVPN環境も整えています。クラウドストレージのAmazon DriveとMicrosoft OneDriveも併用していますが、速度面を考慮するとNASの方がストレスが少ないです。

これまではメインのWindowsマシンをゲーミングPC兼開発機として運用するべくいろいろ調整してきましたが、Windows7以前の環境ではなかなか上手くいきませんでした。Windows10 ProではHyper-Vが利用できるので、Docker for Windowsを導入することでLinuxの開発環境を整えやすいです。Windows7以前のようにVirtualBox等を併用しなくて済むので構築のハードルが低くなっています。Bash on Ubuntu on Windowsはまだ安定したプロダクトではないようなので、こちらはもうすこし様子見をしようと思います。

 

Tags: ,