Elasticserchにおける類似度ベクトル検索のベストプラクティスを求めて
伊藤敬彦（@takahi_i） 氏（以下、伊藤）：「Elasticserchにおける類似度ベクトル検索のベストプラクティスを求めて」ということで、いろいろ調査をしてみましてとりあえずまとめてみましたというお話です。
シュッとやると最初は書いていたんですが、そんなにシュッとできなことがわかりました。それは本当に申し訳なかったと思っています。これ以外にも良い方法がありましたら、懇親会などで「もっといいのあるよ！」と教えてくれることを期待しています。よろしくお願いします。
僕はソフトウェアエンジニアとしてクックパッドで働いています。
12、13年前に博士を取って、Fast Search&Transferという検索エンジンの会社に就職しました。知っている人は知っているけどほとんど知らないんじゃないかと思います。実はこの組織のオーナーを任されている平賀さんとか、けっこう知り合いがいる会社です。検索エンジンのすごい古い会社です。
その後、検索エンジンやデータマイニングまわりをずっとフラフラしていました。「どっち側が強いか？」と言われるとどっちも中途半端という感じです。オープンソースを作るのが好きで、「RedPen」というのは3年ぐらい前に作ったものなのですが、最近は機械学習でやることが多くて、機械学習用のDockerテンプレートのDocker Scienceを作ったりしています。
ということで本題に入ります。
簡単に実現できそうだったが、しかし…
僕は検索をやっていたと言いましたが、実はそんなに強くありません。でもそういうイメージがあるらしくて、知人から「類似画像検索をやりたいんだけど、どうやったらいいの？」と常々聞かれるんですね。「これってメルカリさんなんかが大規模に運用されていて、最近はけっこう当たり前に出てくるフィーチャーだから、こんなのElasticsearchでやれば誰でもできるでしょ。デフォルト機能で提供されているでしょ」と、そう思いますよね。
「うちのサービスで使うこともありそうだし、ちょっと調べてみるわ」というのが、この春先の話です。その頃はできそうだったので「シュッとやる」と書いたんですが、調べれば調べるほどそこまでシュッとはできないことが分かり……。
（会場笑）
ということで、関連検索ですけど、テキスト同士の関連検索はけっこう簡単で、SolrやElasticsearchなどのフルフィーチャーな検索プラットフォームではだいたい提供されています。
ただ、画像の類似検索に使えるようなベクトルの類似検索で決定打になるようなものが、あまり見つからない。それで、Elasticsearchをベースとした画像の類似度検索、ベクトル検索用のパッケージもありますが、だいたい古典的な手法やHashingを使って離散化してインデックスするという方法です。
だけど、これはそれほど精度は良くないと言われていて、できれば最新のディープラーニングでガーっとエンベッディングして類似度を取ってきて高精度にやりたいじゃないですか。メルカリさんもやられてるような画像検索もそのようになっていますが、それを手軽にやりたいというのがモチベーションです。
Faissというものがあります。
これはFacebookによって開発されたパッケージなんですが、非常によくできていて、メルカリさんも利用されています。これはメルカリさんのAI活用事例のページです。べつに僕はメルカリさんの回し者ではないんですけど。
（会場笑）
Elasticsearchで実現したい理由
だけど自分としては、検索プラットフォームで実現したい。ElasticsearchやSolrで実現したい。
なぜかと言うと、ElasticsearchやSolrを運用しているチームはけっこうあります。僕は検索エンジンの導入に携わった経験がありますが、新しい検索エンジンを導入することってけっこう嫌がられるんですね。
「こういうのを新しく入れたいんだけど」と言うと、運用実績がないから嫌われます。ただ、Elasticsearchは運用している場所が多いんですよ。Elasticsearchはインデックスが増えるぐらいはだいたい許容してくれるのではないかと。
あとはもう1個、エンジニアリングチームなんですけど、普通のWebベンチャーの大きさだと、専任の検索エンジニアはいないか、せいぜいいても1人とか。そんな状況でインデックスしかないものから作りあげていくのはなかなかつらい。なので、Elasticsearchのプラグイン追加とそれ用のインデックスの消去や追加ぐらいで実現できないものかというのを僕は常々探しているわけなんですけど、そんなに良いものはない。
あとはFaissもそうなんですけど、安定した検索サービスを提供する上で実装しないといけない補助機能がたくさんあります。インデックスしかもたないパッケージだとある程度自作しないといけなくて、これは相当大きなエンジニアリングチームじゃないと安定運用まで持っていくのは相当厳しいというのがありました。ShardingやReplication、マルチテナントとか、のあたりは少なくともある程度持っていないと、本番運用のお金が関わってくるところで使おうと思うとなかなか厳しい。
そこでやはりElasticsearchを使おう。そいうことで、まとめるとだいたいこんな感じです。
高速で結果が帰ってきてほしい。O(N)で帰ってきますとなると数百万件の画像とかベクトルを検索すると「10秒とか掛かります」と言われるとWebではサクサクとまでは使えないので、Log(N)ぐらいに抑えてほしい。精度が悪いのはやめたい。LSHとかHashingの方法でできるのはわかっているんですけど、やっぱりディープラーニングを使いたいじゃないですか。かっこいいから。
（会場笑）
ということで、普通のベクトルの手法は使えるようになりたいなと。あとは運用性なんですけど、インデックスだけ与えられてあとは自分たちで自作しろということを多くの検索チームでやるのはなかなか厳しい。検索自体がお金になるような会社でないとなかなか厳しい。
Elasticserchが使えるか検証する
ということで、簡単にElasticsearchやSolrにのせられるような方向性を調べています。実はElasticsearchでベクトル検索は普通にできるんですね。
あるんですけど、検索にめちゃくちゃ時間が掛かってO(N)で、普通のWebサービスだったら数百万件が10秒ぐらいで帰ってくるので問題ないと言えばないんですけど、やっぱりWebサービスで使おうと思ったら厳しい。
いろいろ調べると、がんばってくれている人のブログの記事を見つけました。Linkdinにブログの記事機能があるのを初めて知ったんですけど、『Searching with Deep Learning』という記事があって、この人がプラグインの組み合わせで「そこそこぽい類似度検索をやれるぞ！」と言ってくれています。
肝は2段階あります。LuceneのKD木が空間木を持っているので、まずはそれを使って粗く取ってくる。ただ、このとくにすごい弱点があって、LuceneのKD木、空間木のインデックスはデフォルトでは8次元までしか対応をしていないのでめちゃくちゃ小さいです。その8次元で絞り込んだ空間で絞り込み検索をした上で、最期コサイン類似度を2段階目で精密に計算して類似度が高いものを取ってくればいいじゃない、と提案しているというのがこのブログです。
先ほども出てきた空間木なんですが、基本的に近傍探索を定石みたいなアルゴリズムというかデータ構造で、空間を木で表現するものです。数十次元とか百次元ぐらいまでは近傍探索で役に立ちます。今言った通りでLuceneでサポートされています。
このように、先ほどのプラグインはLuceneで提供されているKD木を利用して絞り込み検索をします。それで、ちょっとやってみました。
実験してみた
画像検索をやりたかったんですけど、実務が忙しくて画像が料理できず、「しょうがないからword2vecでやろうか。同じベクトルだしいいよね」ということで、小さく単語単語で学習させてやってみました。
これは先ほどのブログを見ると出てくる話なんですが、2段階あって、まずは低次元ベクトルでワードを粗く絞り込む。そのあと高次元ベクトルでコサイン類似度を取るという方法になります。reduced_vectorというのは8次元で取ってくるんですけど、8次元じゃないといけないんですね。
もしくは8次元以下だったらいけるはずです。あとはコサイン類似度を精緻に取るためのもともとのベクトル、今回は200次元を使うんですが、こんな感じのマッピングを用意してあげます。そして、普通にインデックスをしてあげると。
8次元と200次元のベクトルを普通に……これはPythonのやつだと思うんですけど、インデックスを付けると。
検索クエリがまた2段階になっているので、ちょっと読みにくいです。
上のfunction_scoreの部分がrangeクエリになっていて、from_vectorとto_vectorで、空間の下限と上限を指定してあげます。
それで取れたものに対してファンクションスコアのスクリプトスコアを計算するfast_coslineが下の部分にあるんですけど、fast_coslineで精緻に類似度を計算してやろうというストラテジになっています。
先ほども言ったように部分空間を取ってこないといけないんですけど、入力のベクトルがあったときに下限のベクトル、定数から各要素を引いてあげます。
上限についてはここで2.5というのは完全に決め打ちで、正直チューニングが必要なんですけどこんな感じで適当に2.5とやっています。
結果を検証
各要素に対して下限のベクトルと上限のベクトルを指定してあげて、とりあえず結果が出しました。
グラタンという単語に対してグラタンが1位なのは当たり前ですね。とりあえず10万単語で大した学習もしていないんですけど、食事が出たので、それだけでもまずよかったです。これを見たときは数日間がんばったかいがありました。
「落胆」とやったら、一応感情に関するものが出てきました。
それっぽいベクトルの検索ができているような気がします。
どうせ時間があるので、脱脂粉乳とか麻耶とかグラタンとかでちょっとしたスクリプトでインデックス回すと、脱脂粉乳に対しては脱脂粉乳が一番で、でんぷんがきて、粉ミルクがきて「まぁ、いいじゃないか」ということで、どうやらとんちんかんな結果にはなっていないし、速度もそんなにベクトルの数も多くないのでそもそも時間は掛からないんですけど、絞り込みができているというところです。
今みたいにと言ってもわからないと思うんですけど、最低限、全件探索よりは速度も出ていると思います。精度も大したことをやっていないわりに最低限似たようなものを取れている気がします。本当に時間のない状況で実験をしていたので、精度がここまでで申し訳ないんですけど。
Elasticserchにおける課題
ただ、課題もあります。
絞り込みのベクトルの大きさが8次元で固定というのがやっぱり良くないと。KD木の次元数がデフォルトで8以下に決まっているらしいんですけど、先ほどTextKernelさんのページを見たら「by default 8, you can re-compile lucene with higher values..」と書いてあって、どうやら50次元とかでもやれるらしい。誰かにやってもらいたいです。本当にできるなら。
これができたら、けっこう良い速度で良い精度ができる気がします。今回、ベクトルを8次元と200次元の2個用意して、2回学習が走らないといけないのでちょっとできなかったんですよ。なので、もし無理矢理やろうとするなら、REST APIを作ってそれで登録するときにデフォルトのベクトルから計算して足し合わせるみたいなことをすれば、ある程度の精度で低次元ベクトルを作ることができるのではないかと思いますが、これも時間がなかったのでやれませんでした。
このあたりがそろってくると実用に耐えうるものになってきそうな気がするという状況です。
ということで、今回実験で使ったレポジトリです。
KD木による絞り込みとコサイン類似度とか、インデックス用のやつとか、REST APIをいろいろ同梱したやつを公開する場所に置いてあるんですけど、正直あまりできがよくないので恥ずかしいので1ヶ月ぐらいで消そうかなと思います。
(会場笑）
なので、興味がある人はそれまでに持っておいてください。
Elasticserchによる類似度ベクトル検索は望みあり
ということで、このやり方はElasticsearchのフルフィーチャーの検索プラットフォームの機能をフルで使えるので、うまくいくと化けるぞ！ みたいな感じはしています。だけど正直僕は別のタスクのPythonとかでめちゃくちゃ忙しくて、あまりコンテキストスイッチが大きくてJavaまわりの仕事があまりできる気がしなくて「誰か作ってくれないかな。……チラッ」というのが正直な状況です。
もし誰かがそういうものを出してくれたら、質問をくれた友人に「これがいいよ」と推薦したいと考えています。
ということでまとめますと、Elasticsearchである程度高速に類似画像検索をする方法について調査して、簡単に検証をしてみました。
そんな簡単ではありませんが、ある程度簡単ですね。KD木を併用した方法が利用できて、ただ弱点がありますと。とはいえ、望みはありそうな気はしていました。という状況です。
ご清聴ありがとうございました。
(会場拍手）
