astamuse Lab

astamuse Labとは、アスタミューゼのエンジニアとデザイナーのブログです。アスタミューゼの事業・サービスを支えている知識と舞台裏の今を発信しています。

SPTAGを触ってみた

ご挨拶

どうもお久しぶりです、gucciです。
入社して1年半経ちまして、なんともう3回目のブログのターンが回ってきました。

パソコンを一日ずっと同じような姿勢で叩いていると、肩甲骨周りの筋肉が凝り固まってきて、しまいには肩こりからくる吐き気やストレスに襲われて日常生活に支障をきたしてしまいます。
そうなってしまっては生産性も上がらず、作業時間は伸びてしまいさらに肩が凝ってしまいます。
なんという悪循環でしょう。

そんな時にオススメなのが、ストレッチポールです。
ストレッチポールに乗ることで肩甲骨周りの筋肉をほぐすことができ、また背骨のS字を正しくもどしてあげることで腰痛も軽減されるという良いこと尽くし。
みなさんも是非ストレッチポールをお試しあれ。

最近やっていること

さて、
私がこの会社に入社してからここまで、様々なことに挑戦する機会をいただいてきました。
入社前のプログラミングスクールではRubyを3ヶ月ほど学んでいたのですが、入社後はJavaを半年ほど学び、
その後はアプリケーション開発で半年ほどScalaに触れ、その後データチームに移ってからはSparkを用いた大規模データ処理などを学び、
ここ最近はPythonを使ってバッチやアプリケーションを組んでおります。
使うライブラリやミドルウェアに合わせて選択したり、好きなものや興味があることを自ら選択することができるのでとてもやりがいを感じております。

f:id:astamuse:20190710024218j:plain
space
ここ最近は、
高次元ベクトルデータ検索を行うべくNGTというライブラリを用いてあれこれやっております。
まさか私がベクトルデータを扱うだなんて。いや、むしろベクトルデータって何それ?!と少し前の私ならなっておりました。
(いや、今でも正直あまりわかっておりませんが)

NGTって何?ベクトルデータって何?というのは、我がぶちょー・弊社並河の個人ブログにとてもわかりやすいエントリーがありますので、是非そちらを参考にしてみてください。
NGTがYahoo!の公開しているOSSに対して、
Microsoftが公開している近傍検索を行えるライブラリであるSPTAG (Space Partition Tree And Graph)という存在を同僚のaranが教えてくれたので、
このブログではそちらのSPTAGを実際にお試しで触ってみた内容をご紹介しようと思います。

SPTAGをインストールしてみよう

github.com

NGTのGithubには日本語の説明があるのに対して、SPTAGは英語オンリーの模様ですね。
この時点で難易度の高さが伺えます。
必要項目を見てみると、

swig >= 3.0
cmake >= 3.12.0
boost >= 1.67.0
tbb >= 4.2

とありますので、順々にインストールしていきましょう。
当方の環境は Ubuntu 18.04.2 LTSを使っております。
それでは必要ライブラリのインストールからレッツゴー。

Swigのインストール

必要ver : swig >= 3.0

swingはパッケージがあるのであっという間に入れられます。

$ apt list swig
Listing... Done
swig/bionic,now 3.0.12-1 amd64 [installed]

よしよし。

$ sudo apt install swig

これでばっちりです。

cmakeのインストール

必要ver : cmake >= 3.12.0

cmakeなんてもちろんすぐ入れられるよ、むしろ入ってるんじゃないかな、
と思ったらなんと残念。

$ cmake --version
cmake version 3.10.2

versionが古いではないか・・・

$ apt list cmake
Listing... Done
cmake/bionic 3.10.2-1ubuntu2 amd64

なるほど。パッケージにあるのがそれなのですね。
自分の手で最新版にしてあげましょう。

$ wget https://github.com/Kitware/CMake/releases/download/v3.14.5/cmake-3.14.5-Linux-x86_64.sh  
$ chmod +x cmake-3.14.5-Linux-x86_64.sh
$ sudo ./cmake-3.14.5-Linux-x86_64.sh
$ sudo mv cmake-3.14.5-Linux-x86_64 /opt
$ sudo ln -s /opt/cmake-3.14.5-Linux-x86_64/bin/* /usr/bin
$ cmake --version
cmake version 3.14.5

成功です。

boostのインストール

必要ver : boost >= 1.67.0

続いてboost。
恐る恐るパッケージを見てみると・・・

$ apt list libboost-dev
Listing... Done
libboost-dev/bionic 1.65.1.0ubuntu1 amd64

ブーストよ、お前もか。
これも経験、レッツトライ。

$ wget https://dl.bintray.com/boostorg/release/1.68.0/source/boost_1_68_0.tar.bz2
$ tar --bzip2 -xf boost_1_68_0.tar.bz2
$ cd boost_1_68_0/
$ ./bootstrap.sh
$ sudo ./b2 install
〜少し時間がかかります〜

無事に終わりましたね。お疲れ様です。

tbbのインストール

必要ver : tbb >= 4.2

最後にtbbのインストールです。

$ apt list libtbb-dev
Listing... Done
libtbb-dev/bionic 2017~U7-8 amd64

お、ありますね。

$ sudo apt install libtbb-dev

さあ準備は整いました。いよいよSPTAGをインストールしてみましょう。

SPTAGをインストール

$ git clone https://github.com/microsoft/SPTAG.git

クローンしてあげたら、後はREADMEにあるとおりに実行すれば・・・

$ cd SPTAG
$ mkdir build
$ cd build && cmake .. && make

最後にインストールです!

$ sudo make install
・・・
CMake Error at Wrappers/cmake_install.cmake:87 (file):
  file INSTALL cannot find "/home/develop/SPTAG/Wrappers/src/SPTAG.py".
Call Stack (most recent call first):
  cmake_install.cmake:43 (include)

こけました!!
なんということでしょう。
ログをみるとふむふむ、SPTAG.pyというファイルが見つからないと、って怒っていますね。
探して見ましょう。

$ cd ..
$ find . -name SPTAG.py
./Wrappers/inc/SPTAG.py
./Release/SPTAG.py

いたぁあああああああああ!
どちらが正しいのか・・・
diffをとってみると同じでした。

$ cp ./Wrappers/inc/SPTAG.py ./Wrappers/src/

コピーしてきて、再実行!お願い!

$ cd build/
$ sudo make install

エラー起きず!やりました! READMEには「テストやってみてね」と書いてあるのでやりましょう。

$ cd ../Release/
$ ./test
Load Data From delindices/vectors.bin
Load Data (97, 10) Finish!
Load BKT From delindices/tree.bin
Load BKT (1,98) Finish!
Load Graph From delindices/graph.bin
Load Graph (97,32) Finish!
10@(1,1) 90@(3,3) 250@(5,5) 

*** No errors detected

やりました。我々はついにたどり着いたのです。

GettingStartに詳しい使い方があるので、さっそく試してみましょう。
上記ページには大文字で記載されていますが、indexbuilderの小文字でパスが通っていて、Usageが出るのでそれを見てみましょう。

$ indexbuilder
Required option not set:
  -d, --dimension <value>       Dimension of vector.
Required option not set:
  -v, --vectortype <value>      Input vector data type. Default is float.
Required option not set:
  -i, --input <value>           Input raw data.
Required option not set:
  -o, --outputfolder <value>    Output folder.
Required option not set:
  -a, --algo <value>            Index Algorithm type.

Usage: 
  -t, --thread <value>          Thread Number.
  --delimiter <value>           Vector delimiter.
  -d, --dimension <value>       Dimension of vector.
  -v, --vectortype <value>      Input vector data type. Default is float.
  -i, --input <value>           Input raw data.
  -o, --outputfolder <value>    Output folder.
  -a, --algo <value>            Index Algorithm type.
  -c, --config <value>          Config file for builder.

ふむふむ。なるほど。上の5つは必要なオプションなのですね。

そしてInputのformatは、

<metadata1>\t<v11>|<v12>|<v13>|
<metadata2>\t<v21>|<v22>|<v23>|

であると。なるほど。 手元に実況パワフルプロ野球2018年の開幕版データがたまたまあるので、それを使ってやってみましょう。
少しデータが古いのはご了承ください。
こんなデータがインプットになっております。

山田哲人        50|73|81|65|77|62|
大引啓次        36|53|67|60|58|73|
西浦直亨        25|51|60|51|50|48|
川端慎吾        56|51|65|58|56|50|
武内晋一        30|46|48|46|71|65|
荒木貴裕        33|54|60|62|51|53|
畠山和洋        32|61|29|54|65|61|
・
・
・

6次元のベクトルで、

<選手名>        ミート力 |パワー|走力|肩力|守備|捕球|

といったステータスになっております。
本来パワプロはこれらのデータに加えて特殊能力があり、それによるプラスマイナスが大きいのですが、今回はお試しということでご了承くださいませ。
それでは作って見ましょう。

インデックスの作成

$ indexbuilder -d 6 -i ./input_yasyu_list_sptag.tsv -o ./powerpro2018_SPTAG -v Int8 -a KDT
Setting NumberOfThreads with value 32
・
・
・
Start to build KDTree 1
1 KDTree built, 394 396
build RNG graph!
Refine 1 0%Refine RNG, graph acc:0.992813
Refine 2 0%Refine RNG, graph acc:0.997813
Build RNG Graph end!
Save Data To ./powerpro2018_SPTAG/vectors.bin
Save Data (396, 6) Finish!
Save KDT to ./powerpro2018_SPTAG/tree.bin
Save KDT (1,396) Finish!
Save Graph To ./powerpro2018_SPTAG/graph.bin
Save Graph (396,32) Finish!

やりました。成功です!

インデックスの検索

続いて検索を行ってみましょう!

適当に検索クエリ用のファイルを作成します。

パワー100       0|100|0|0|0|0|

これを使って検索を投げてみます。

$ indexsearcher ./powerpro2018_SPTAG Index.QueryFile=./testSPTAG_Query.tsv Index.ResultFile=./testSPTAG_Result.tsv Index.K=10
・
・
・
Load Data From ./powerpro2018_SPTAG/vectors.bin
Load Data (396, 6) Finish!
Load KDT From ./powerpro2018_SPTAG/tree.bin
Load KDT (1,396) Finish!
Load Graph From ./powerpro2018_SPTAG/graph.bin
Load Graph (396,32) Finish!
Set []/powerpro2018_SPTAG = ./powerpro2018_SPTAG
Set [Index]QueryFile = ./testSPTAG_Query.tsv
Set [Index]ResultFile = ./testSPTAG_Result2.tsv
Set [Index]K = 10
Load data: (1, 6)
        [avg]       [99%]   [95%]   [recall]    [mem]
Setting MaxCheck with value 2048
2048    0.000129    0.0001  0.0001  0.0000      0GB
Output results finish!

やりました。成功です! 結果のファイルを見てみると・・・

パワー100:0.307@アマダー|0.362@G後藤武敏|0.370@マレーロ|0.370@山川穂高|0.378@阿部慎之助|0.386@黒瀬健太|0.394@園部聡|0.394@デスパイネ|0.402@バティスタ|0.402@メヒア|

実データで並べてみると・・・

アマダー 37|80|18|52|30|38|
G後藤武敏 25|61|31|39|35|30|
マレーロ    57|85|42|56|37|36|
山川穂高    51|86|41|53|46|40|
阿部慎之助 46|69|15|51|27|41|
黒瀬健太    19|51|21|51|24|15|
園部聡   18|60|42|56|21|19|
デスパイネ 45|84|52|66|36|40|
バティスタ 46|81|53|69|35|29|
メヒア   42|80|42|60|44|47|

おぉぉ、力自慢の男たちがずらりとでてきましたね。
ふむ。なるほどなるほど。

NGTでやってみる

同じ元データで作ったインデックスに対して、同様のクエリを投げる作業をNGTでもやってみました。

Query No.1
Rank    ID  Distance
1   316 81.2711
2   84  82.1766
3   280 84.5044
4   217 87.327
5   42  91.1757
6   375 91.4549
7   385 91.4549
8   286 95.3625
9   31  96.566
10  186 98.3972
Query Time= 0.000167582 (sec), 0.167582 (msec)
Average Query Time= 0.000167582 (sec), 0.167582 (msec), (0.000167582/1)

こちらを実データで並べてみると・・・

19   51  21  51  24  15  黒瀬健太    316
25  61  31  39  35  30  G後藤武敏 84
37  80  18  52  30  38  アマダー    280
18  60  42  56  21  19  園部聡   217
46  69  15  51  27  41  阿部慎之助 42
41  62  45  33  30  35  清宮幸太郎 375
41  62  45  33  30  35  今井順之助 385
27  60  56  42  29  32  岩見雅紀    286
26  60  46  46  39  36  鵜久森淳志 31
24  51  44  63  20  20  青木陸   186

ほほお・・・SPTAGとは異なる結果になりました。
実に興味深いですね。 このあたりは実際のアルゴリズムを理解していかないと真相に辿りつけなさそうですね。
オプションの付け方などでもインデックスの作成や検索は微妙に変わりそうなので、
精度や速度比較など、まだまだ調べられることはたくさんありそうです。
インストールのしやすさや、Outputの見やすさはNGTの方に分がありそうですね。

おわりに

いかがだったでしょうか。
SPTAGとNGTの比較検証をもっとやろうかと思っていたのですが、SPTAGのインストール自体で思いの外知見がたまったので、そちらをメインにアウトプットさせて頂きました。
文書や画像などをベクトル化し、そのベクトルの距離が近いものでサーチする近傍検索。実に面白いですね。
いつの日か、人間の遺伝子をベクトル化することで、その人間がどんな特徴を持つのかなどがわかってしまう日が来るのかもしれないし、来ないのかもしれない・・・。

ということで! アスタミューゼは常に新しいものや面白いものに挑戦しています!
エンジニア・デザイナーを絶賛募集中です! 是非一緒に面白いことをやっていきましょう!ご応募お待ちしております!

Copyright © astamuse company, ltd. all rights reserved.