(目次はこちら)
はじめに
もう1年前になるが、転移学習/Deep Features のことを書いた。
Deep Featuresの例として類似画像検索を試したが、実用に近づけるには精度以外にも処理速度を気にしなければならない。
以前から、YahooのNGT(Neighborhood Graph and Tree) は気にはなっていたが試したことはなかった。2ヶ月ほど前に、Facebookから、Faiss(Facebook AI Similarity Search) が公開された。とても気になるのでやってみる。
Faiss セットアップ
リポジトリ: https://github.com/facebookresearch/faiss
今回は、手元のMacBookProで試した。
基本的には、https://github.com/facebookresearch/faiss/blob/master/INSTALL を参考にやる。で、LAPACK/BLASは、howto-installing-lapack-and-blas-on-mac-os/を参照すればよい。
唯一ハマったポイントは、こちらで解決できた。https://github.com/facebookresearch/faiss/issues/72
makefile.incは、example_makefiles/makefile.inc.Mac.brewを使った。Python3を使うために、以下の部分だけは編集した。
PYTHONCFLAGS=-I/System/Library/Frameworks/Python.framework/Versions/2.7/include/python2.7 \
-I/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python/numpy/core/include
データ
転移学習/Deep Features で使ったデータでは、ちょっと少ないので、また別途用意した。もちろん、faissのtutorialにあるように、ダミーデータでも十分。でも、やった感が出ない。
import numpy as np
d = 64 # dimension
nb = 100000 # database size
nq = 10000 # nb of queries
np.random.seed(1234) # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.
とりあえず、Google Image Searchでライセンス的に再利用可能な画像を1万枚集めた。(雑に集めたので、重複していたり輝度が異なるだけのものが存在していたり。)
tutorialでは、64次元 x 100,000ベクトルなので、2048次元 x 10,000ベクトルの方がサイズ的には大きい。
Deep Features / 深層特徴
特徴抽出は、転移学習/Deep Features と同様でOK。これで、2048次元の特徴ベクトルが得られる。
最近は、tensorflow/modelsの方を使っていて、https://github.com/tensorflow/models/blob/master/inception/inception/slim/inception_model.py#L323 の netに2048次元のベクトルが含まれているのでそれを返してあげるようにすればいい。ちなみに、学習済みモデルはinception-v3-2016-03-01.tar.gz。
ここ。
with tf.variable_scope('logits'):
shape = net.get_shape()
net = ops.avg_pool(net, shape[1:3], padding='VALID', scope='pool')
# 1 x 1 x 2048
net = ops.dropout(net, dropout_keep_prob, scope='dropout')
net = ops.flatten(net, scope='flatten') ### <---------
# 2048
logits = ops.fc(net, num_classes, activation=None, scope='logits',
restore=restore_logits)
# 1000
end_points['logits'] = logits
end_points['predictions'] = tf.nn.softmax(logits, name='predictions')
return logits, end_points
類似画像検索
データ
jsonで保存してるのがナンセンスであることを理解しつつもjson。
ちなみに、1 行 1 jsonのjsonl (json lines)となっている。
with open('data.json', 'r') as f:
xb = np.array([np.array(json.loads(l.strip())).astype('float32') for l in f])
重複した画像が含まれるため、ランダムなノイズを加えて評価しやすくした。
for i in range(len(xb)):
xb[i][0] += np.random.random()
クエリ画像は、xbから必要な数だけ拝借
nq = 1
xq = np.copy(xb[:nq])
評価方法
- 検索処理時間
- recall@1
- もっとも近い画像が、もっとも近い画像として検索できた割合
- top x recall
- (この表現が正しいかわからないが)x番目までの近い画像が、x番目までに検索できた割合
下記コードは、こちら deep_features_faiss.py。
recall評価用
def evaluate(arr1, arr2):
top_1 = (arr1[:,0] == arr2[:,0]).sum() / arr1.shape[0]
total = 0
for t in np.c_[arr1, arr2]:
_, cnt = np.unique(t, return_counts=True)
total += (cnt >= 2).sum()
top_k = total / arr1.shape[0] / arr1.shape[1]
print('recall@1: {:.2f}, top {} recall: {:.2f}'.format(top_1, arr1.shape[1], top_k))
Brute Force
nb, d = xb.shape
n_candidates = 10
# Search (brute force)
s = time.time()
result_d, result_i = [], []
for q in xq:
dist = np.array([np.linalg.norm(d) for d in (xb - q)])
idx = np.array(sorted(range(len(dist)), key=lambda k: dist[k])[:n_candidates])
result_d.append(dist[idx])
result_i.append(idx)
result_d, result_i = np.array(result_d), np.array(result_i)
print('Average query time (brute force): {:.2f} [ms]'.format((time.time() - s) * 1000 / nq))
Faiss
# Index
s = time.time()
index = faiss.IndexFlatL2(d)
index.add(xb)
print('Index time (faiss): {:.2f} [ms]'.format((time.time() - s) * 1000))
# Search
s = time.time()
result_d1, result_i1 = index.search(xq, n_candidates)
print('Average query time (faiss): {:.2f} [ms]'.format((time.time() - s) * 1000 / nq))
# Evaluate
evaluate(result_i, result_i1)
Faiss (Quantize)
Faissでは高速化のために、データをベクトル量子化して、処理時間を短縮するような実装も含まれていて、内部的には、ボロノイ分割しているそうな。
ここでは、100分割するようにした。
# Index
s = time.time()
nlist = 100
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
index.train(xb)
index.add(xb)
print('Index time (faiss / quantize): {:.2f} [ms]'.format((time.time() - s) * 1000))
# Search (nprobe=1)
s = time.time()
index.nprobe = 1
result_d2, result_i2 = index.search(xq, n_candidates)
print('Average query time (faiss / quantize nprobe=1): {:.2f} [ms]'.format((time.time() - s) * 1000 / nq))
# Evaluate (nprobe=1)
evaluate(result_i, result_i2)
# Search (nprobe=10)
s = time.time()
index.nprobe = 10
result_d3, result_i3 = index.search(xq, n_candidates)
print('Average query time (faiss / quantize nprobe=10): {:.2f} [ms]'.format((time.time() - s) * 1000 / nq))
# Evaluate (nprobe=10)
evaluate(result_i, result_i3)
結果
複数同時にクエリできる/するような場合、Faissを使うととにかく高速に処理できる。
ある程度の精度の犠牲を許容できるなら、数百〜千倍以上の高速化が実現できそうだ。素晴らしい。
同時クエリ数 1 (nq = 1)
| Index Time [ms] | Query Time [ms] | Recall@1 | Top 10 Recall | 速度比 | |
|---|---|---|---|---|---|
| Brute Force | - | 90.04 | 1.00 | 1.00 | 1.0 |
| Faiss | 135.53 | 7.01 | 1.00 | 1.00 | 12.8 |
| Faiss Quantize(1) | 574.82 | 0.40 | 1.00 | 0.50 | 225.1 |
| Faiss Quantize(10) | 574.82 | 1.43 | 1.00 | 1.00 | 63.0 |
同時クエリ数 10 (nq = 10)
| Index Time [ms] | Query Time [ms] | Recall@1 | Top 10 Recall | 速度比 | |
|---|---|---|---|---|---|
| Brute Force | - | 78.01 | 1.00 | 1.00 | 1.0 |
| Faiss | 128.42 | 1.68 | 1.00 | 1.00 | 46.4 |
| Faiss Quantize(1) | 606.27 | 0.06 | 1.00 | 0.70 | 1300.2 |
| Faiss Quantize(10) | 606.27 | 0.31 | 1.00 | 1.00 | 251.6 |
同時クエリ数 100 (nq = 100)
| Index Time [ms] | Query Time [ms] | Recall@1 | Top 10 Recall | 速度比 | |
|---|---|---|---|---|---|
| Brute Force | - | 76.70 | 1.00 | 1.00 | 1.0 |
| Faiss | 130.05 | 0.68 | 1.00 | 1.00 | 112.8 |
| Faiss Quantize(1) | 665.09 | 0.05 | 1.00 | 0.77 | 1534.0 |
| Faiss Quantize(10) | 665.09 | 0.27 | 1.00 | 0.98 | 284.1 |
結果(画像)
一番左がクエリ画像で、左から右に距離が近い順に並べている。
Faissはこれだけではない
Faissは、BLASを利用している関係で、MKL-BLASを使うことでさらなる高速化が可能。また、GPUに対応した実装もされていることもすごくいい。さらに、ベクトル量子化した際に、(精度は犠牲になるが)データを圧縮して持つことで、1サーバのメモリにのるデータ数を増やすこともできる。
おわりに
転移学習/Deep Features の続きとして、処理速度改善の一つの案として、Facebook ResearchのFaiss(Facebook AI Similarity Search)を利用した類似画像検索を行った。検索対象が、数万〜、数百万〜、数千万〜、数億〜になるにつれ、処理コスト的に実用的でなくなっていくため、こういったデータ構造だとか近似計算の工夫が必要になってくることは明らかである。