類似商品APIで使っている近傍探索のツールをNGTからfaissに切り替えたお話

この記事はBASE Advent Calendar 2019の10日目の記事です。

devblog.thebase.in

お久しぶりです。 BASEビール部部長（兼Data Strategyチーム)の氏原です。

1年ちょっと前にYahoo!の近傍探索ツールNGTを使って類似商品APIをつくるという記事を書きました。あれからだいぶ経ちましたがその間に類似商品APIはコツコツと改善を続けています。例えばファッション系以外で精度が良くないという話を前の記事にも書きましたが、画像以外に商品のタイトルや説明文の特徴量も使うようにするなどしてそれも改善されています。

そうした取り組みのなかで近傍探索に使っていたNGTを別のものに切り替えましたので、それを紹介したいと思います。

類似商品APIについて

類似商品APIはBASEのアプリで各商品の詳細ページを開いたときに表示される「関連する商品」という部分などで利用されています。

その時開いた商品と似た商品を提示することで良い商品探しに役立つようにとAPIを開発しています。

NGTについて

NGTはYahoo!Japanさんが開発している近傍探索用のツールです。

NGTは任意の密ベクトルに対して事前に登録した（同次元の）ベクトルから最も距離が近いベクトルの上位数件（k件）を高速に近似k最近傍探索（k-Nearest Neighbor Search）するためのソフトウエアです。 高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介

以前はこれで画像の特徴量vectorを保存して、商品ページが開かれた際に似た画像をもつ商品を関連商品として提示していました。

NGTはとても性能がよく、1024次元の特徴量vector350万個を登録しても数十msecでレスポンスを返してくれてオンデマンドで関連商品を出すのにとても重宝してました。

問題点

ただ運用を続けていると色々と問題もでてきました。特に辛いのはindexの構築にかかる時間とindexのサイズです。

NGTは登録したvectorを全てそのまま持っています。そのため1024次元の特徴量vector350万個を登録した時点でindexのサイズは20G程になります。これがメモリに全部載るので、AWSでサーバを立てると結構なサイズのメモリを持ったインスタンスが必要になります。

また、NGTは必要なvectorを全てinsertした後にbuild_indexでindexingをする必要があります。登録したvectorをdeleteするメソッドがなく、差分更新が（おそらく）できないため、daily batchで毎度indexを作り直していました。（※私の理解不足の可能性もあります。間違ってたらごめんなさい。）

faiss

上記の問題を解決するために、現在では別のツールで近傍探索を行っています。faissです。

faissはNGTと同じくvectorの近傍探索のためのツールでFacebookが開発しています。 NGTと比べてなにが嬉しいかと言いますと、最終的に出来上がるindexのサイズです。 faissは高速化やindexの圧縮のための仕組みが用意されていて、いろいろ試した結果indexのサイズがNGTでやっていた時の1/200くらいになりました。衝撃です。

もちろん圧縮するがゆえにある程度の精度低下は覚悟しなくてはいけないんですが、目立つほどでもありませんでした。

使い方はこんな感じです。

• index作成

import faiss
import numpy as np
import random


dim = ... # 特徴量の次元数
nlist = ... # 特徴量が何個の空間に分割されるか
m = ... # 近傍探索するときに対象の空間以外に隣の空間を何個まで利用するか
nbits = ... # 特徴量をここで指定したbit数で表現するように圧縮する

quantizer = faiss.IndexFlatL2(dim)
index = faiss.IndexIVFPQ(quantizer, dim, nlist, m, nbits)

vecs = [(item_id, vec), ...] # 商品IDと特徴量のセットのリスト

# 圧縮のために特徴量の分布を学習する必要がある
# 実際の運用ではここは事前に学習しておいて学習済みのindexをloadする
assert not index.is_trained
train_data = [v for _, v in vecs if random.random() < 0.01]
index.train(train_data)
assert index.is_trained

# indexへの追加はまとめてではなくこんな感じで細切れでもよいので
# vecsが大きすぎて全部をメモリに乗せられない場合は
# generatorで必要な分だけ読み込みながらやったりしても大丈夫
batch_size = 10000
for i in range(0, len(vecs), batch_size):
    input_vecs = []
    input_ids = []
    for item_id, vec in vecs[i:i+batch_size]:
        input_vecs.append(vec)
        input_ids.append(item_id)
    input_vecs = np.array(input_vecs, dtype=np.float32)
    input_ids = np.array(input_ids, dtype=np.int64)
    index.add_with_ids(input_vecs, input_ids)

# 保存
faiss.write_index(index, "features.index")

• indexの利用

import faiss

index = faiss.read_index("features.index")

vec = ... # 近傍探索のターゲット
vecs = np.array([vec], dtype=np.float32)
D, I = index.search(vecs, 1000) # 近傍1000個とってくる
D = D[0]
I = I[0]
for item_id, distance in zip(I, D):
    # add_with_idsでindex作ってるとここでIDが返ってくる
    ...

wikiが充実してるので使うにあたってあまり困ることはありませんでした。

差分更新

faissで作成したindexは、(サポートしているindexなら)登録されたvectorの部分削除が可能です。

import faiss

index = faiss.read_index("features.index")
target_id = ... # 消したいitem_id
index.remove_ids(np.array([target_id])

つまりdaily batchで差分更新ができるため、index構築時間を激減させることができます。これならdailyと言わずもっと更新頻度を上げられます。

ちなみにindexのmergeとかもできるそうなので、vectorが大量にある場合はN個に分けて、N個のjobでindexを作成して後でmergeするみたいな使い方もできるようです。

まとめ

faissはFacebookが使ってるだけあって1兆個のvectorを登録して動かすなんてスケールまで想定しているようです。もちろんそのためには色々工夫が必要なようですが。

faissを導入したことでindexの構築やAPIの運用がかなり楽になり、インフラやアルゴリズムの改善に力をいれることができるようになりました。リコメンドのシステムを作る際などで近傍探索用のツールが必要であればfaissを検討してみてはいかがでしょうか。

明日はプロダクトマネジメントグループの船坂さんとエンジニアの白数さんです。お楽しみに。