近似最近傍探索の最前線

https://bit.ly/2Mn7uNd 近似最近傍探索の最前線松井勇佑東京大学生産技術研究所助教 http://yusukematsui.me 2019/7/29, MIRU 2019
チュートリアル 1

https://bit.ly/2Mn7uNd 1 , 2 , … , ∈ ℝ 最近傍探索
➢個のベクトルがある 2

https://bit.ly/2Mn7uNd 0.23 3.15 0.65 1.43 探索 0.20 3.25 0.72 1.68
∈ ℝ 74 argmin ∈ 1,2,…, − 2 2 結果 1 , 2 , … , ∈ ℝ 最近傍探索 ➢個のベクトルがある ➢クエリが与えられたとき，一番近いベクトルを探す ➢計算機科学における基本的な問題 ➢真面目に線形探索：遅い 3

∈ ℝ 74 argmin ∈ 1,2,…, − 2 2 結果 1 , 2 , … , ∈ ℝ 近似最近傍探索 ➢近似最近傍探索 ➢厳密に最近傍でなくてもよいので，高速に解を求める ➢速度，メモリ，精度のトレードオフ 4

∈ ℝ 74 argmin ∈ 1,2,…, − 2 2 結果 1 , 2 , … , ∈ ℝ 近似最近傍探索 ➢近似最近傍探索 ➢厳密に最近傍でなくてもよいので，高速に解を求める ➢速度，メモリ，精度のトレードオフ ➢今日紹介する手法の規模感．大規模探索をオンメモリ 32GB RAM 100 106 to 109 10 ms 5

https://bit.ly/2Mn7uNd CV分野で探索が使われる例画像検索 https://www.sciencedirect.com/science/article/pii/S0028393214002942 https://about.mercari.com/press/news/article/20190318_image_search/ https://jp.mathworks.com/help/vision/ug/image-classification-with-bag-of-visual-words.html クラスタリング距離行列（類似度行列） kNN認識もともとはBoFのassignのためにCV分野で発達した
（今でもベンチマークはSIFT） https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm 6

https://bit.ly/2Mn7uNd 7 スタートはいくつ？ GPUがある？ < 106 106 ≤ <
109 109 ≤ faiss-gpu: 線形探索 (IndexFlatL2) faiss-cpu: 線形探索 (IndexFlatL2) nmslib (hnsw) falconn annoy faiss-cpu: hnsw + ivfadc (IndexHNSWFlat + IndexIVFPQ) PQのパラメータ調整：Mを小さく近似ではなく厳密最近傍探索 faiss-cpuのfaiss.IndexHNSWFlatでもよい注意： = 100ぐらいを想定している。問題のサイズは大体で決まる．が1,000や10,000のときはまずPCAで = 100程度にする場合が多いあるない GPUメモリにのらない時遅い or メモリにのらない時データ追加が遅い時複数プロセスから呼びたい時遅い時性能調整したい時 rii 部分集合探索をしたいときメモリにのらない時訓練に時間がかかってもいいのなら，PQをOPQに置き換える IVFのパラメータ調整： nprobeを大きく➡精度上がるが遅く性能調整したい時 PythonおすすめANN手法選択フローチャート（2019年度版. condaかpipで入るもの）

https://bit.ly/2Mn7uNd 第一部：最近傍探索第二部：近似最近傍探索 8

∈ ℝ 74 argmin ∈ 1,2,…, − 2 2 結果 1 , 2 , … , ∈ ℝ 最近傍探索（Nearest Neighbor; NN） ➢まず近似ではない厳密な最近傍探索を考える ➢高速な実装の紹介 ✓ faissライブラリ（今日何度も出てきます。CPU&GPU） ✓ 後に登場する「直積量子化」の著者らがFAIRで開発 ➢まず愚直な実装を紹介し、次にfaissの実装を紹介します ➢「同じアルゴリズムでもなぜ高速なのか？」を体感 10

https://bit.ly/2Mn7uNd 本の次元クエリベクトル = 1 , 2 , … , 本の次元データベースベクトル
= 1 , 2 , … , タスク： ∈ , ∈ に対し − 2 2を計算 11

= 1 , 2 , … , タスク： ∈ , ∈ に対し − 2 2を計算 parfor q in Q: for x in X: l2sqr(q, x) def l2sqr(q, x): diff = 0.0 for (d = 0; d < D; ++d): diff += (q[d] – x[d])**2 return diff 愚直な実装クエリ側の forを並列化本当はここで heapで最小選択 12

= 1 , 2 , … , タスク： ∈ , ∈ に対し − 2 2を計算 parfor q in Q: for x in X: l2sqr(q, x) def l2sqr(q, x): diff = 0.0 for (d = 0; d < D; ++d): diff += (q[d] – x[d])**2 return diff 愚直な実装クエリ側の forを並列化本当はここで heapで最小選択 faiss （場合１） < 20かつ%4 = 0のとき： − 2 2をSIMDで計算（場合２）その他： − 2 2 = 2 2 − 2⊤ + 2 2をBLASで計算 13

https://bit.ly/2Mn7uNd float fvec_L2sqr (const float * x, const float *
y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } − 2 2をSIMDで計算参考都合上変数名を変更してます x y D=31の場合 float: 32bit 15 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 16 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

https://bit.ly/2Mn7uNd float: 32bit float fvec_L2sqr (const float * x, const
float * y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる − 2 2をSIMDで計算都合上変数名を変更してます 17 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる ⊖⊖⊖⊖ ⊖ ⊖ ⊖⊖ − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 18 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 msum1 a_m_b1 ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる ⊖⊖⊖⊖ ⊖ ⊖ ⊖⊖ ⊗⊗⊗⊗⊗⊗⊗⊗ += − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 19 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる msum1 += − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 20 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる ⊖⊖⊖⊖ ⊖ ⊖ ⊖⊖ msum1 += − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 21 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 msum1 a_m_b1 ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる ⊖⊖⊖⊖ ⊖ ⊖ ⊖⊖ ⊗⊗⊗⊗⊗⊗⊗⊗ += − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 22 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 msum1 a_m_b1 msum2 ➢ 256bitのSIMDレジスタ ➢ 8つのfloatを並列処理できる ⊖⊖⊖⊖ ⊖ ⊖ ⊖⊖ ⊗⊗⊗⊗⊗⊗⊗⊗ ⊕⊕⊕⊕ ➢ 128bitのSIMDレジスタ += − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 23 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 mx my a_m_b1 a_m_b1 msum2 ⊖⊖⊖⊖ ⊗⊗⊗⊗ += ➢ 128bitのSIMDレジスタ − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 24 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 0 0 0 mx 0 0 0 my a_m_b1 a_m_b1 ⊖⊖⊖⊖ ⊗⊗⊗⊗ msum2 += ➢ 128bitのSIMDレジスタあまり − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 25 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 0 0 0 mx 0 0 0 my a_m_b1 a_m_b1 ⊖⊖⊖⊖ ⊗⊗⊗⊗ ⊕ ⊕ ⊕ msum2 += ➢ 128bitのSIMDレジスタあまり最終結果 − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 26 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

y, size_t d) { __m256 msum1 = _mm256_setzero_ps(); while (d >= 8) { __m256 mx = _mm256_loadu_ps (x); x += 8; __m256 my = _mm256_loadu_ps (y); y += 8; const __m256 a_m_b1 = mx - my; msum1 += a_m_b1 * a_m_b1; d -= 8; } __m128 msum2 = _mm256_extractf128_ps(msum1, 1); msum2 += _mm256_extractf128_ps(msum1, 0); if (d >= 4) { __m128 mx = _mm_loadu_ps (x); x += 4; __m128 my = _mm_loadu_ps (y); y += 4; const __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; d -= 4; } if (d > 0) { __m128 mx = masked_read (d, x); __m128 my = masked_read (d, y); __m128 a_m_b1 = mx - my; msum2 += a_m_b1 * a_m_b1; } msum2 = _mm_hadd_ps (msum2, msum2); msum2 = _mm_hadd_ps (msum2, msum2); return _mm_cvtss_f32 (msum2); } x y D=31の場合 0 0 0 mx 0 0 0 my a_m_b1 a_m_b1 ⊖⊖⊖⊖ ⊗⊗⊗⊗ ⊕ ⊕ ⊕ msum2 += ➢ 128bitのSIMDレジスタあまり最終結果 ➢最後の「あまり」の部分は読み込みにコストがかかる ➢なので%4 = 0のときのみこの方式を採用していると思われる ➢FaissのSIMD部分のコードはシンプルでわかりやすいため、SIMDの勉強になる ➢一方で、素人がSIMDを書いても満足感があるだけで全然速くならない。愚直実装に-Ofastで自動SIMD化のほうが速かったりする（経験談） ➢しかし、SIMDを読めるようになっておくと「なぜ速いのか」を理解できて役に立つ場面がある ➢他のSIMD L2sqrの例：hnswの実装 https://github.com/nmslib/hnswlib/blob/master/hnswlib/space_l2.h − 2 2をSIMDで計算都合上変数名を変更してます float: 32bit 27 参考 def l2sqr(x, y): diff = 0.0 for (d = 0; d < D; ++d): diff += (x[d] – y[d])**2 return diff

https://bit.ly/2Mn7uNd − 2 2 = 2 2 − 2⊤ +
2 2をBLASで計算 q_norms = norms(Q) # 1 2 2, 2 2 2, … , 2 2 x_norms = norms(X) # 1 2 2, 2 2 2, … , 2 2 ip = sgemm_(Q, X, …) # parfor (m = 0; m < M; ++m): for (n = 0; n < N; ++n): dist = q_norms[m] + x_norms[n] – ip[m][n] 本の次元クエリベクトルをまとめて行列に = 1 , 2 , … , ∈ ℝ× 本の次元データベースベクトルをまとめて行列に = 1 , 2 , … , ∈ ℝ× 先ほどのようにSIMDで高速化された関数舐めて足し合わせるだけ ➢ BLASの行列積計算 ➢ ボトルネックがここになる ➢ , が大きいと、相対的に恩恵が大きい ➢ バックエンドがIntel MKLかOpenBLASかで 30%性能が違うらしい（MKLのほうが良い） 29

https://bit.ly/2Mn7uNd CPU版に比べ、faiss-gpuの最近傍探索は10倍速い ➢ GPUの場合は常に 2 2 − 2⊤ + 2
2に展開して計算している ➢ 1M個のベクトルに対するk-means (D=256, K=20000) • 11 min on CPU • 55 sec on 1 Pascal-class P100 GPU (float32 math) • 34 sec on 1 Pascal-class P100 GPU (float16 math) • 21 sec on 4 Pascal-class P100 GPUs (float32 math) • 16 sec on 4 Pascal-class P100 GPUs (float16 math) *** (majority of time on the CPU) ➢ GPUが利用でき、またデータがGPUメモリに載るのなら、GPUのNNを試すべき ➢ CPUとは挙動が違うのに注意（Dが増えた時の挙動。topkの個数に制限がある。等）ベンチマーク：https://github.com/facebookresearch/faiss/wiki/Low-level-benchmarks x10早い 30

https://bit.ly/2Mn7uNd 参考資料 ➢ faissのL2sqrの切り替えについて [https://github.com/facebookresearch/faiss/wiki/Implementation-notes#matrix-multiplication-to-do- many-l2-distance-computations] ➢ SIMD入門について、Markus Püschel教授によるETHの講義 [How
to Write Fast Numerical Code - Spring 2019]のうち[SIMD vector instructions]が参考になる ✓ https://acl.inf.ethz.ch/teaching/fastcode/2019/ ✓ https://acl.inf.ethz.ch/teaching/fastcode/2019/slides/07-simd.pdf ➢ SIMDに関する日本語の記事 ➢ 名工大福嶋慶繁先生による「ネットワーク系演習II: ハイパフォーマンスコンピューティング」[https://fukushimalab.github.io/hpc_exercise/] ➢ 一週間でなれる！スパコンプログラマ Day7: SIMD化 [https://kaityo256.github.io/sevendayshpc/day7/index.html] ➢ faissのSIMD部分のコード [https://github.com/facebookresearch/faiss/blob/master/utils_simd.cpp] ➢ faissのSIMDのNNをAVX512に拡張したうえでのL2sqrのベンチマーク [https://gist.github.com/matsui528/583925f88fcb08240319030202588c74] 31

https://bit.ly/2Mn7uNd 109 106 billion-scale million-scale 転置インデクス＋データ圧縮圧縮データを直接探索 Locality Sensitive Hashing
(LSH)系 Tree系 / Space Partitioning系 Graph探索系 0.34 0.22 0.68 0.71 0 1 0 0 ID: 2 ID: 123 0.34 0.22 0.68 0.71 ざっくり空間分割データ圧縮 ➢ k-means ➢ 複数k-means ➢ PQ/OPQ ➢ etc… ➢ 生データのまま ➢ Scalar quantization ➢ PQ/OPQ ➢ etc… PQTable Multi hash table ルックアップ系ハミング系 ADC 線形探索 … ハミング線形探索生データを直接扱う：精度〇，メモリ効率× データを圧縮する：精度△，メモリ効率〇 33

https://bit.ly/2Mn7uNd 35 Locality Sensitive Hashing (LSH) ➢近いベクトルを高い確率で同じ値に変換するような「ハッシュ関数」と，問い合わせの「データ構造」登録 13
ハッシュ1 ハッシュ2 … ⑬ ⑬ 探索ハッシュ1 ハッシュ2 … ④㉑㊴ ⑤㊼と4 , 5 , 21 , …を実際に比較

ハッシュ1 ハッシュ2 … ⑬ ⑬ 探索ハッシュ1 ハッシュ2 … ④㉑㊴ ⑤㊼と4 , 5 , 21 , …を実際に比較例えばランダムな射影 [Dater+, SCG 04] = ℎ1 , … , ℎ ℎ = +

ハッシュ1 ハッシュ2 … ⑬ ⑬ 探索ハッシュ1 ハッシュ2 … ④㉑㊴ ⑤㊼と4 , 5 , 21 , …を実際に比較例えばランダムな射影 [Dater+, SCG 04] = ℎ1 , … , ℎ ℎ = + ☺: ✓ 数学的な解析が容易 ✓ 理論分野では今でも解析が盛ん : ✓ 精度を上げるにはテーブルがたくさん必要 ✓ また、元のデータ（）を保持する必要有り ✓ なのでメモリ消費が多い ✓ 実データではデータ依存手法(PQ等)のほうが精度良い ✓ ・・・なので、近年のCVの論文では関連研究として昔の手法扱いされるだけの場合が多かった

https://bit.ly/2Mn7uNd 38 ハッシュ2 … ④㉑㊴ ⑤㊼と4 , 5 ,
21 , …を実際に比較探索㉙㊹ハッシュ1 ➢「次の候補」も考慮すると実用的なメモリ消費でいける（Multi-Probe [Lv+, VLDB 07]） ✓豆知識：この考え方はInverted Multi-Index(後述)における Multi-Sequence Algorithmと同じ ➢これを元に作られたライブラリ：FALCONN

https://bit.ly/2Mn7uNd 39 ★700 https://github.com/falconn-lib/falconn $> pip install FALCONN table =
falconn.LSHIndex(params_cp) table.setup(X-center) query_object = table.construct_query_object() # query parameter config here query_object.find_nearest_neighbor(Q-center, topk) Falconn ➢パラメータ設定がややめんどくさい ➢データ追加が高速（後述のannoyやnmlsibに比べ） ➢なのでその場でインデックスを構築する場合などに有利？

https://bit.ly/2Mn7uNd 40 参考資料 ➢ わかりやすいまとめスライド：CVPR 2014 Tutorial on Large-Scale Visual
Recognition, Part I: Efficient matching, H. Jégou [https://sites.google.com/site/lsvrtutorialcvpr14/home/efficient-matching] ➢ 実用的なQ&A：FAQ in Wiki of FALCONN [https://github.com/FALCONN- LIB/FALCONN/wiki/FAQ] ➢ 本発表で用いたハッシュ関数：M. Datar et al., “Locality-sensitive hashing scheme based on p-stable distributions,” SCG 2004. ➢ Multi-Probe：Q. Lv et al., “Multi-Probe LSH: Efficient Indexing for High- Dimensional Similarity Search”, VLDB 2007 ➢ まとめ記事：A. Andoni and P. Indyk, “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions,” Comm. ACM 2008

https://bit.ly/2Mn7uNd 42 ➢Tree系の代表格。「Randomized KD Tree」と「k-means Tree」から性能の良い方のアルゴリズムが自動的に選択される ➢https://github.com/mariusmuja/flann ☺ ✓
実装が使いやすく、00年代後半～10年代前半に非常に人気 ✓ OpenCVやPCLに含まれている  ✓ 元のデータを保持するのでメモリ消費大 ✓ 2019年現在、コードのメンテナンスが止まっている画像は[Muja and Lowe, TPAMI 2014]から引用 Randomized KD Tree k-means Tree FLANN: Fast Library for Approximate Nearest Neighbors

https://bit.ly/2Mn7uNd 43 Annoy 「2-means tree」+「複数trees」+「優先度付きキューを共用」登録探索ランダム二点選択→空間分割→階層的に ➢ クエリが落ちるセルに注目
➢ 実データで比較 Treeになっているので対数回の比較でたどり着ける以下の画像は全て著者ブログポスト(https://erikbern.com/2015/10/01/nearest-neighbors- and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html)より引用

https://bit.ly/2Mn7uNd 44 Annoy 「2-means tree」+「複数trees」+「優先度付きキューを共用」工夫1 より点数が欲しい場合は距離の優先度付きキュー工夫2 複数treeを用意して精度上げる（優先度付きキューは共用）以下の画像は全て著者ブログポスト(https://erikbern.com/2015/10/01/nearest-neighbors-
and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html)より引用

https://bit.ly/2Mn7uNd 45 Annoy https://github.com/erikbern/annoy $> pip install annoy t =
AnnoyIndex(D) for n, x in enumerate(X): t.add_item(n, x) t.build(n_trees) t.get_nns_by_vector(q, topk) ☺ ➢ Spotify技術者が開発。Spotifyで実際に使われている ➢ よく整備されていて安定している印象 ➢ パラメータが少なく直感的で、インタフェースがシンプル ➢ 近年のmillion-scaleのANNのベースライン的な扱い（性能そのものは後述のnmslib等に劣る） ➢ 保存されたデータをmmapで読むのでたくさんのプロセスから読むときに適しているらしい  ➢ 実データを保持するのでメモリ消費大 ➢ ちゃんとした技術詳細資料がない ★5700

https://bit.ly/2Mn7uNd 46 コメント：Annoyもflannもlshも後述するIVFADCも、最初にざっくり空間分割し、そこで注目したものだけ詳しく調べるという意味では似ている

https://bit.ly/2Mn7uNd 48 Graph探索系近年、熱い ➢ データ点をノードとするグラフを作っておく ✓ このグラフの作り方で様々な方式がある ➢ ランダム点からスタートし、「繋がっているノードのうちクエリに近いもの
へ移動」を繰返す（greedyなtraverse）火付け役：Navigable Small World Graphs (NSW) ➢ この階層バージョン（Hierarchical NSW; HNSW）が、million-scaleの実データに対し極めて高速・高精度であることが2017年ごろにわかってきた ✓ million-scaleなら全データがメモリにのるようになったので ➢ 特に、nmslibというライブラリに実装されているものが、使いやすさ・速度・精度を総合的に考えて2019年現在のmillion-scaleの決定版 ➢ Faissにも実装された

https://bit.ly/2Mn7uNd 49 登録画像は[Malkov+, Information Systems, 2013]から引用 ➢ データ点がノード ➢
新しい入力データ点に対し、近傍のものにリンクを張る、としてグラフを作っていく

新しい入力データ点に対し、近傍のものにリンクを張る、としてグラフを作っていく ➢ データ追加の最初のころのリンクは長くなりうる ➢ この「たまに長いやつ」が重要らしい

https://bit.ly/2Mn7uNd 54 探索画像は[Malkov+, Information Systems, 2013]から引用

https://bit.ly/2Mn7uNd 55 探索画像は[Malkov+, Information Systems, 2013]から引用 ➢ クエリが与えられる

https://bit.ly/2Mn7uNd 56 探索画像は[Malkov+, Information Systems, 2013]から引用 ➢ クエリが与えられる ➢
ランダム点から出発

ランダム点から出発 ➢ 繋がっているノードのうちクエリに近いものにgreedyに移動

https://bit.ly/2Mn7uNd 60 工夫画像は[Malkov and Yashunin, TPAMI, 2019]から引用 ➢ K-NNのとき、一度訪れたノードはもう考慮しない
[Malkov+, Information Systems, 2013] ➢ グラフを階層的に作る（実データで非常に強い） [Malkov and Yashunin, TPAMI, 2019] まず粗いグラフで探索しそこをスタートとして少し密なグラフで探索繰り返す

https://bit.ly/2Mn7uNd 61 NMSLIB (Non-Metric Space Library) https://github.com/nmslib/nmslib $> pip install
nmslib index = nmslib.init(method=‘hnsw’) index.addDataPointBatch(X) index.createIndex(params1) index.setQueryTimeParams(params2) index.knnQuery(q, topk) ☺ ➢“hnsw”は実データで精度・速度バランスで2019年現在ベスト（メモリに載れば） ➢インタフェースがシンプル ➢データがメモリに載るのであればこれを使えばいい  ➢実データを保持するのでメモリ消費大 ➢データ追加は早くない（annoyと同程度。falconnより遅い） ★1500

https://bit.ly/2Mn7uNd 様々な方式が提案されてきている ➢ Alibabaの系列： C. Fu et al., “Fast Approximate
Nearest Neighbor Search with the Navigating Spreading-out Graph”, VLDB19 https://github.com/ZJULearning/nsg ➢ Microsoft Research Asiaからの提案。Bingで使われているらしい: J. Wang and S. Lin, “Query-Driven Iterated Neighborhood Graph Search for Large Scale Indexing”, ACMMM12 (この論文をベースに色々改良されているらしい) https://github.com/microsoft/SPTAG ➢ Yahoo Japanからの提案。現状ベンチマークで一位を競っている： M. Iwasaki and D. Miyazaki, “Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data”, arXiv18 https://github.com/yahoojapan/NGT データおよびエンジニア力のある企業と組んで作っていくと楽しそう 62

https://bit.ly/2Mn7uNd 63 参考資料 ➢ Navigable Small World Graphの元論文：Y. Malkov et
al., “Approximate Nearest Neighbor Algorithm based on Navigable Small World Graphs,” Information Systems 2013 ➢ Navigable Small World Graphの階層版：Y. Malkov and D. Yashunin, “Efficient and Robust Approximate Nearest Neighbor search using Hierarchical Navigable Small World Graphs,” IEEE TPAMI 2019 ➢ nmslibの公式python binding [https://github.com/nmslib/nmslib/tree/master/python_bindings]

https://bit.ly/2Mn7uNd 65 基本的な考え方 0.54 2.35 0.82 0.42 0.62 0.31 0.34
1.63 3.34 0.83 0.62 1.45 1 2 N … ➢個の実数値ベクトルを表現するには floatを用いて4 byte 必要 ➢やが大きいとメモリに載らない ✓ 例： = 128, = 109の時，512 GB ➢各ベクトル「変換」し「ショートコード」に圧縮する ➢ショートコードはメモリ効率が良い ✓ 例：上のデータを32bitコードに圧縮するとわずか4GB ➢ショートコードの世界で探索を考える 1 2 N code code code 変換 …

https://bit.ly/2Mn7uNd 66 基本的な考え方 0.54 2.35 0.82 0.42 0.62 0.31 0.34
1.63 3.34 0.83 0.62 1.45 1 2 N … ➢個の実数値ベクトルを表現するには floatを用いて4 byte 必要 ➢やが大きいとメモリに載らない ✓ 例： = 128, = 109の時，512 GB ➢各ベクトル「変換」し「ショートコード」に圧縮する ➢ショートコードはメモリ効率が良い ✓ 例：上のデータを32bitコードに圧縮するとわずか4GB ➢ショートコードの世界で探索を考える 1 2 N code code code 変換 … どのような変換がいいか？ 1.コード間の「距離」が計算できる．その距離は元のベクトル間の距離を近似する 2.コード間距離は高速に計算できる 3.上の二つを十分に小さいコードで実現できる

https://bit.ly/2Mn7uNd 68 0.23 1.4 -0.3 9.6 0.0 2.3 3.21 0.5
42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ハミング系手法：原理

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ハミング系手法：原理

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () ハミング系手法：原理

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () ⟼ = ℎ1 ⋮ ℎ () ハミング系手法：原理

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () ⟼ = ℎ1 ⋮ ℎ () ℎ1 ハミング系手法：原理

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () ハミング系手法：原理 ⟼ = ℎ1 ⋮ ℎ () ℎ2

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () ハミング系手法：メモリ効率

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () float: 32 [bit] bool: 1 [bit] ハミング系手法：メモリ効率

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () float: 32 [bit] bool: 1 [bit] ハミング系手法：メモリ効率 e.g., = 128 : 128 × 32 = 4096 [bit] e.g., = 64 : 64 × 1 = 64 [bit]

42.0 -2.4 12.3 1.1 -0.1 1.4 4.2 9.1 0.2 3.1 0.4 1.3 2.2 4.5 0.4 -12.5 ・・・ Hash 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 ・・・ () float: 32 [bit] bool: 1 [bit] ハミング系手法：メモリ効率 e.g., = 128 : 128 × 32 = 4096 [bit] e.g., = 64 : 64 × 1 = 64 [bit] 64x Efficient

https://bit.ly/2Mn7uNd 1 0 1 1 0 1 0 1 1
0 0 1 1 1 0 0 ・・・ハミング系手法：距離計算 78

0 0 1 1 1 0 0 ・・・ 1 0 1 1 0 1 0 1 ( , ) = 3 ハミング系手法：距離計算二つのバイナリコードのハミング距離を使う 79

0 0 1 1 1 0 0 ・・・ 1 0 1 1 0 1 0 1 ( , ) = 3 _mm_popcnt( xor ) 1 0 1 1 0 1 0 1 ~10 [ns] ⋅,⋅ は専門の演算命令を使うことで高速に計算できるハミング系手法：距離計算二つのバイナリコードのハミング距離を使う 80

0 0 1 1 1 0 0 ・・・ 1 0 1 1 0 1 0 1 ( , ) = 3 _mm_popcnt( xor ) 1 0 1 1 0 1 0 1 ~10 [ns] ⋅,⋅ は専門の演算命令を使うことで高速に計算できるハミング系手法：距離計算二つのバイナリコードのハミング距離を使う 81 ➢・・・のはずだったが、近年は256bit以上のSIMDを使うとpopcnt より早いという報告もある ➢popcntはあくまで64bitごとにしか処理が出来ない ➢SIMDはより多くのbit(AVX2で256bit, AVX512で512bit)ごとの処理が出来るので、SIMD芸でpopcntを実現すると早い時があるらしい [Muła+, Comp. J., 18] [André+, arXiv18]

https://bit.ly/2Mn7uNd 82 ハミング系手法：ハッシュの設計 1 0 1 1 0 1 0
1 ( , ) = 3 0.23 1.4 -0.3 9.6 0.0 2.3 -0.1 1.4 4.2 9.1 0.2 3.1 ( , ) = 4.61 Hash ➢もし元の距離尺度が小さければ，ハミング距離も小さくなる ➢そのようなハッシュを設計したい

https://bit.ly/2Mn7uNd 83 ハミング系手法の分類データ非依存：訓練データを用いないデータ依存：訓練データを用いる ➢教師無し：ラベル無し訓練データを用いる例：訓練画像 ➢教師あり：ラベル付き訓練データを用いる例：猫の画像，犬の画像，etc ユークリッド距離ではなく意味を考慮した距離を表現
➢半教師あり：ラベル無しおよびラベル付き訓練データを用いるランダム射影など ➢ Deep hogehoge hashが無限にある ➢ 「データ表現」と「二値化」がごっちゃになっているのでよくない ➢ Spectral Hashing, Iterative Quantization (ITQ) など

https://bit.ly/2Mn7uNd 84 ハミング系手法の分類データ非依存：訓練データを用いないデータ依存：訓練データを用いる ➢教師無し：ラベル無し訓練データを用いる例：訓練画像 ➢教師あり：ラベル付き訓練データを用いる例：猫の画像，犬の画像，etc ユークリッド距離ではなく意味を考慮した距離を表現
➢半教師あり：ラベル無しおよびラベル付き訓練データを用いるランダム射影など ➢ Deep hogehoge hashが無限にある ➢ 「データ表現」と「二値化」がごっちゃになっているのでよくない ➢ Spectral Hashing, Iterative Quantization (ITQ) など ➢ 「データ表現」と「二値化」を完全に分離したいなら、 deep featureにITQをするのが最も簡単だと思う ➢ ドワンゴによるITQ実装（scipy準拠インタフェース） ✓ pip install pqkmeans

https://bit.ly/2Mn7uNd 86 ハミング系手法の高速計算 0 0 1 1 ・・・ 1 2
1 1 0 1 0 0 0 1 0 1 1 0 ➢ ハミング距離による線形探索は高速だが，計算量は ➢ 依然に対し線形であり，が大きいと遅い ➢ ハッシュテーブルを用いて，全く同様の結果を高速に計算出来る uint4 query vec<uint4> codes

https://bit.ly/2Mn7uNd 87 ハミング系手法の高速計算：データ登録 0 0 1 1 ・・・ 1 2
1 1 0 1 0 0 0 1 0 1 1 0 uint4 query

https://bit.ly/2Mn7uNd 88 0 0 1 1 ・・・ 1 2 1
1 0 1 0 0 0 1 0 1 1 0 [0000]から[1111]までの値を持つエントリを用意しておく 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 uint4 query ハミング系手法の高速計算：データ登録

https://bit.ly/2Mn7uNd 89 0 0 1 1 ・・・ 1 2 1
1 0 1 0 0 0 1 0 1 1 0 [0000]から[1111]までの値を持つエントリを用意しておく 1 2 各コードについて，それ自身をエントリとして，番号を挿入 N 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 uint4 query ハミング系手法の高速計算：データ登録

https://bit.ly/2Mn7uNd 2 N 0 0 1 1 1 0 0
0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 uint4 query 5 9 vec<list<int>> table ハミング系手法の高速計算：探索 90

0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 uint4 query 5 9 vec<list<int>> table 例： list<int> v = table[9]; Print(v); >> [5, 9] ハミング系手法の高速計算：探索 91

0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 vec<list<int>> table uint4 query ハミング系手法の高速計算：探索 (1) クエリと同じコードがあるか？配列アクセスなので， 1 ．すなわち，table[query] 92

https://bit.ly/2Mn7uNd 2 N 0 0 1 1 (2) ここでは，該当なし 1
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 vec<list<int>> table uint4 query ハミング系手法の高速計算：探索 (1) クエリと同じコードがあるか？配列アクセスなので， 1 ．すなわち，table[query] 93

https://bit.ly/2Mn7uNd 2 N 0 0 1 1 (2) ここでは，該当なし 1
0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 (3) クエリと1bit違いのコードを作り，同様に探索 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 vec<list<int>> table ハミング系手法の高速計算：探索 (1) クエリと同じコードがあるか？配列アクセスなので， 1 ．すなわち，table[query] 94

https://bit.ly/2Mn7uNd 5 9 2 N 0 0 1 1 1
0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 (3) クエリと1bit違いのコードを作り，同様に探索 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 (4) クエリに最も近いのは② (2) ここでは，該当なし vec<list<int>> table ハミング系手法の高速計算：探索 (1) クエリと同じコードがあるか？配列アクセスなので， 1 ．すなわち，table[query] 95

1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 ハミング系手法の高速計算：問題と発展 96

1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 2 ≪ 2のときスカスカ 5 9 ハミング系手法の高速計算：問題と発展 97

1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 ′ bit 違いの候補は ′ 通り ′が大きいと爆発 2 ≪ 2のときスカスカ 5 9 ハミング系手法の高速計算：問題と発展 98

1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 ′ bit 違いの候補は ′ 通り ′が大きいと爆発 2 ≪ 2のときスカスカ 5 9 ➢ テーブルを分割することでこれらの問題を解決する手法が知られている [Norouzi+, TPAMI 14] ➢ が大きい時はこれらのテーブルを用いる手法を検討すると良いハミング系手法の高速計算：問題と発展 99

https://bit.ly/2Mn7uNd 100 ハミング系手法の（身もふたもない）まとめ ➢ハミング系手法を使いたい状況は、高速探索ではなくデータ圧縮が目的の場面だと思う ➢データ表現 ✓ 特徴量抽出器を訓練できる場合：良いバイナリボトルネックフィーチャーを頑張って作る ✓
特徴量抽出器を訓練できない場合：特徴量にITQ ➢探索 ✓ faissに入ってるのでそれを使おう（前述の高速計算は無いが）

https://bit.ly/2Mn7uNd 101 参考資料 ➢ 教師無しの代表格。この分野の火付け役 ➢ Y. Weiss et al.,
“Spectral Hashing”, NIPS 2008 ➢ Y. Gong et al., “Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval”, PAMI 2013 ➢ Pipで入るITQ実装：https://github.com/DwangoMediaVillage/pqkmeans ➢ バイナリコードにハッシュテーブル：M. Norouzi et al., “Fast Exact Search in Hamming Space With Multi-Index Hashing”, TPAMI 2013 ➢ ハミング系のサーベイ： ➢ J. Wang et al., “Learning to Hash for Indexing Big Data - A Survey”, Proc. IEEE 2015 ➢ J. Wang et al., “A Survey on Learning to Hash”, TPAMI 2018 ➢ SIMDによるpopcountについて ➢ W. Muła et al., “Faster Population Counts Using AVX2 Instructions”, Computer Journal, 2018 ➢ F. André et al., “Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD”, arXiv 2018

https://bit.ly/2Mn7uNd 103 0.34 0.22 0.68 1.02 0.03 0.71 0.13 0.98
1.20 0.33 0.72 1.86 0.32 0.27 0.08 2.21 0.43 0.11 1.03 0.08 2.2 0.4 1.1 3.1 … ID: 1 ID: 2 ID: K 入力ベクトルコードブックベクトル量子化（Vector Quantization; VQ) ➢ベクトルを、一番近いコードワードの添え字で表現。データを圧縮 = 1 , 2 , … , VQコード

https://bit.ly/2Mn7uNd 104 0.34 0.22 0.68 1.02 0.03 0.71 ID: 423
0.13 0.98 1.20 0.33 0.72 1.86 0.32 0.27 0.08 2.21 0.43 0.11 1.03 0.08 2.2 0.4 1.1 3.1 … ID: 1 ID: 2 ID: K 入力ベクトルコードブックベクトル量子化（Vector Quantization; VQ) ➢ベクトルを、一番近いコードワードの添え字で表現。データを圧縮 = 1 , 2 , … , argmin ∈ 1,2,…, − 2 2 423という数字だけを保持するこれからはは423 として扱う VQコード

0.13 0.98 1.20 0.33 0.72 1.86 0.32 0.27 0.08 2.21 0.43 0.11 1.03 0.08 2.2 0.4 1.1 3.1 … ID: 1 ID: 2 ID: K 入力ベクトル VQコードコードブックベクトル量子化（Vector Quantization; VQ) ➢ベクトルを、一番近いコードワードの添え字で表現。データを圧縮 = 1 , 2 , … , argmin ∈ 1,2,…, − 2 2 423という数字だけを保持するこれからはは423 として扱う ➢古典的な手法。は事前に訓練データにk-meansを施し求める ➢が大きいと近似精度が上がるが量子化が遅くなる：() ➢データ圧縮のために直接使うことは現実的ではない

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する PQコード

0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する PQコード

ID: 123 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する PQコード

ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する PQコード

ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック ➢単純 ➢メモリ効率良い ➢距離入力, コード 2 を近似計算可能直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する

ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック直積量子化：メモリ効率が良い

https://bit.ly/2Mn7uNd float: 32bit 113 0.34 0.22 0.68 1.02 0.03 0.71
ID: 2 ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック直積量子化：メモリ効率が良い e.g., = 128 128 × 32 = 4096 [bit]

ID: 2 ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック e.g., = 128 128 × 32 = 4096 [bit] e.g., = 8 8 × 8 = 64 [bit] uchar: 8bit 直積量子化：メモリ効率が良い

ID: 2 ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック e.g., = 128 128 × 32 = 4096 [bit] e.g., = 8 8 × 8 = 64 [bit] 1/64に圧縮 uchar: 8bit 直積量子化：メモリ効率が良い

0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 Nearest? … Query 0.34 0.22 0.68 1.02 0.03 0.71 1 2 N 直積量子化：距離近似

0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 Nearest? … Query 0.34 0.22 0.68 1.02 0.03 0.71 1 2 N 直積量子化直積量子化：距離近似

https://bit.ly/2Mn7uNd 118 Query 0.34 0.22 0.68 1.02 0.03 0.71 …
ID: 42 ID: 67 ID: 92 ID: 221 ID: 143 ID: 34 ID: 99 ID: 234 ID: 3 1 2 N 直積量子化：距離近似

https://bit.ly/2Mn7uNd 119 Query （近似的距離で）線形探索が出来る 0.34 0.22 0.68 1.02 0.03 0.71
線形探索 … ID: 42 ID: 67 ID: 92 ID: 221 ID: 143 ID: 34 ID: 99 ID: 234 ID: 3 1 2 N 直積量子化：距離近似

https://bit.ly/2Mn7uNd 120 0.34 0.22 0.68 1.02 0.03 0.71 入力ベクトル ID:
2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N = 256 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 Distance: 0.04 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 Distance: 0.04 + 0.23 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 Distance: 0.04 + 0.23 + 1.02 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 Distance: 0.04 + 0.23 + 1.02= 1.29 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 Distance: 1.29 0.03 7.34 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表 = 256 直積量子化：距離近似

0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトルコードブック ID: 2 ID: 12 ID: 87 データベースのPQコード ID: 45 ID: 8 ID: 72 ID: 42 ID: 65 ID: 7 Distance: 1.29 0.03 7.34 ⋯ 1 2 N 1 2 ⋯ 256 1 8.2 0.04 2.1 2 3.4 11.2 5.5 3 0.31 1.1 2.4 距離表早い: - テーブル参照。( + ) 正確に近似: - 空間を 28 に分割 = 256 直積量子化：距離近似

ID: 123 ID: 87 0.13 0.98 0.32 0.27 1.03 0.08 … ID: 1 ID: 2 ID: 256 0.3 1.28 0.35 0.12 0.99 1.13 … ID: 1 ID: 2 ID: 256 0.13 0.98 0.72 1.34 1.03 0.08 … ID: 1 ID: 2 ID: 256 入力ベクトル PQコードコードブック ➢単純 ➢メモリ効率良い ➢距離入力, コード 2 を近似計算可能直積量子化（Product Quantization; PQ) [Jégou, TPAMI 2011] ➢ベクトルを分割してそれぞれベクトル量子化する

https://bit.ly/2Mn7uNd 131 ➢ 単純なのでpythonで数十行（上記は疑似コードではない） ➢ Pure Python ライブラリ: nanopq https://github.com/matsui528/nanopq
➢ pip install nanopq

https://bit.ly/2Mn7uNd 132 直積量子化のDeep化 (Trainable PQ) ➢T. Yu et al., “Product
Quantization Network for Fast Image Retrieval”, ECCV 18 ➢L. Yu et al., “Generative Adversarial Product Quantisation”, ACMMM 18 ➢B. Klein et al., “End-to-End Supervised Product Quantization for Image Search and Retrieval”, CVPR 19 T. Yu et al., “Product Quantization Network for Fast Image Retrieval”, ECCV 18 より ➢画像表現＋（PQ的な）レイヤ ➢どれも画像のクラス情報を使っている ➢クラスを使わないと弱い

https://bit.ly/2Mn7uNd 133 PQに関するより詳しいサーベイ ➢http://yusukematsui.me/project/sur vey_pq/survey_pq_jp.html ➢また、直積量子化の著者との共同サーベイ論文を書きました ➢Y. Matsui, Y.
Uchida, H. Jégou, S. Satoh “A Survey of Product Quantization”, ITE 2018. ➢ビッグネームと共著のサーベイ論文なので引用を稼げるかと期待したが全然稼げていない。あざといことはするべきではない（でも中身は本当にちゃんとしてます）

https://bit.ly/2Mn7uNd 135 PQTable 0.34 0.22 ⋮ 0.71 クエリベクトル ID: 2
ID: 123 ID: 87 ID: 101 PQコード 1 1 1 1 1 1 1 2 2 123 87 101 256 256 256 256 83 9 55 13 ハッシュテーブル PQ 適用ハッシュ最近傍のものを見つける 2 N 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 5 9 ➢バイナリコードはハッシュテーブルで探せた ➢PQにも同様のことができる ➢[Matsui+, ICCV15, TMM18] ➢速いが精度はイマイチ

https://bit.ly/2Mn7uNd 136 ハミング系ルックアップ系 0.34 0.22 0.68 1.02 0.03 0.71
0 1 0 1 0 0 0.34 0.22 0.68 1.02 0.03 0.71 ID: 2 ID: 123 ID: 87 ベクトル表現バイナリコード： 0, 1 PQコード： 1, … , 256 距離表現ハミング距離表参照距離表現能力 ◦ ◎ 距離計算速度 ◎ ◦ Pros 補助構造がいらない元のベクトルを近似再構成可能 Cons 近似再構成は出来ない補助構造が必要（コードブック）ハミング系とルックアップ系は兄弟

https://bit.ly/2Mn7uNd 138 PQを用いた探索システム：復習と表記 0.34 0.22 0.68 1.02 0.03 0.71 ID:
2 ID: 123 ID: 87 ∈ ℝ ഥ ∈ 1, … , 256 を圧縮したPQコードをഥ と表記する , ∈ ℝとして，が圧縮されてഥ となっているとき，二乗距離 , 2はコードഥ を用いて高速近似計算出来る , 2 ∼ , ഥ 2 ベクトルとベクトルの二乗距離は・・ベクトルとコードで近似出来る

https://bit.ly/2Mn7uNd 139 PQを用いた探索システム：データ登録粗量子化 1 3 2 4 5 6
7 ➢空間を分割する「粗量子化器」を用意しておく．ここでは単純なボロノイ空間分割（k-means割り当てそのもの） ➢各 =1 は訓練データに単純にk-meansを適用し作る = 1 = 2 = ・・・

https://bit.ly/2Mn7uNd 140 粗量子化 1 3 2 4 5 6 7
1.02 0.73 0.56 1.37 1.37 0.72 1 ➢ ベクトル1 の登録を考える = 1 = 2 = ・・・ PQを用いた探索システム：データ登録

1.02 0.73 0.56 1.37 1.37 0.72 1 ➢ ベクトル1 の登録を考える = 1 = 2 = ・・・ PQを用いた探索システム：データ登録

1.02 0.73 0.56 1.37 1.37 0.72 1 ➢ ベクトル1 の登録を考える = 1 = 2 = ➢ 1 に一番近いものは2 ➢ 1 と2 の残差 1 = 1 − 2 ( ) を計算する・・・ PQを用いた探索システム：データ登録

1.02 0.73 0.56 1.37 1.37 0.72 1 ➢ ベクトル1 の登録を考える = 1 = 2 = ➢ 1 に一番近いものは2 ➢ 1 と2 の残差 1 = 1 − 2 ( ) を計算する ID: 42 ID: 37 ID: 9 1 ・・・ ➢ 残差 1 をPQで圧縮し，コードത 1 を作り，番号「1」とともに記録する ➢ すなわち，(, ഥ )を記録する ത 1 PQを用いた探索システム：データ登録

ID: 42 ID: 37 ID: 9 245 ID: 25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … = 1 = 2 = ・・・ ➢ 全データに関して，「番号＋残差」をリストとして保存 PQを用いた探索システム：データ登録

https://bit.ly/2Mn7uNd 145 ID: 42 ID: 37 ID: 9 245 ID:
25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … = 1 = 2 = ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 ➢ クエリに近いデータを探す PQを用いた探索システム：探索

25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … = 1 = 2 = ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 ➢ クエリに近いデータを探す PQを用いた探索システム：探索

25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … = 1 = 2 = ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 ➢ クエリに近いデータを探す ➢ に一番近いものは2 ➢ と2 の残差 = − 2 を計算する PQを用いた探索システム：探索

25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … = 1 = 2 = ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 ➢ クエリに近いデータを探す ➢ に一番近いものは2 ➢ と2 の残差 = − 2 を計算する ➢ = 2に登録されている各 (, ത )について，と比べる , 2 = − 2 , − 2 2 = , 2 ∼ , ഥ 2 ➢ 最も近いものを選ぶ（リランキング．戦略色々） PQを用いた探索システム：探索

25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 42 ID: 37 ID: 9 1 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 18 ID: 4 ID: 96 3721 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 = 1 = 2 = ➢ 粗量子化のコスト＋リランキングのコストを調整することで，高速な探索を実現 ➢ 残差に注目することで，近似精度を高めた PQを用いた探索システム：探索

https://bit.ly/2Mn7uNd 150 Faiss https://github.com/facebookresearch/faiss $> conda install faiss-cpu -c pytorch
$> conda install faiss-gpu -c pytorch ➢PQの著者ら（もともとINRIA）がFAIR Parisに移籍し、彼らがもともと持っていたyaelというライブラリを元に、GPU専門家と一緒に作ったANNライブラリ ➢CPU版：PQベースの手法を網羅 ➢GPU版：PQベースの手法の一部を実装 ➢ボーナス： ➢通常の線形探索も実装されており、CPU版もGPU版も非常に高速 ➢k-meansも実装されており、CPU版もGPU版も非常に高速 ★7200 ベンチマーク： https://github.com/DwangoMediaVillage/pqkmeans/blob/master/tutorial/4_comparison_to_faiss.ipynb

https://bit.ly/2Mn7uNd 151 quantizer = faiss.IndexFlatL2(D) index = faiss.IndexIVFPQ(quantizer, D, nlist,
M, nbits) index.train(Xt) # 学習 index.add(X) # データ追加 index.nprobe = nprobe # 検索パラメータ dist, ids = index.search(Q, topk) # 検索 ID: 42 ID: 37 ID: 9 245 ID: 25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 1 3 2 4 5 6 7 = 1 = 普通は8 bit 粗量子化を選べる普通の線形探索

25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 = 1 =

https://bit.ly/2Mn7uNd 154 quantizer = faiss.IndexHNSWFlat(D, hnsw_m) index = faiss.IndexIVFPQ(quantizer, D,
nlist, M, nbits) ID: 42 ID: 37 ID: 9 245 ID: 25 ID: 47 ID: 32 12 ID: 38 ID: 49 ID: 72 1932 ID: 24 ID: 54 ID: 23 8621 ID: 77 ID: 21 ID: 5 145 ID: 32 ID: 11 ID: 85 324 ID: 16 ID: 72 ID: 95 1721 … ・・・ 0.54 2.35 0.82 0.42 0.14 0.32 粗量子化 = 1 = 普通は8 bit 粗量子化を選べる HNSW ➢粗量子化をHNSWにすると、billion-scaleのデータに対する速度・精度のトレードオフで2019年現在最も有効 ➢[Douze+, CVPR 2018] [Baranchuk+, ECCV 2018]

https://bit.ly/2Mn7uNd 155 ☺ ➢SOTAの研究者が作っており、高速。PQ系最新手法は今後このライブラリ上にインプリされそう ➢FAIRで実際に使われている ➢元のデータが直接メモリに載らないならfaiss一択（billion-scaleの問題など） ➢特にクエリがバッチのとき非常に高速（逆に、バッチでないときはそこまで劇的に早くはない）
 ➢ドキュメントが不足。特にpythonバインディングとGPU ➢様々な手法がインプリされているが、専門家じゃないとどれを使えばいいかわからない ➢conda必須（自前ビルドは苦行） ✓ 野良pip化の動きが強い ✓ https://github.com/facebookresearch/faiss/issues/170

https://bit.ly/2Mn7uNd 156 ☺ ➢SOTAの研究者が作っており、高速。PQ系最新手法は今後このライブラリ上にインプリされそう ➢FAIRで実際に使われている ➢元のデータが直接メモリに載らないならfaiss一択（billion-scaleの問題など） ➢特にクエリがバッチのとき非常に高速（逆に、バッチでないときはそこまで劇的に早くはない）
 ➢ドキュメントが不足。特にpythonバインディングとGPU ➢様々な手法がインプリされているが、専門家じゃないとどれを使えばいいかわからない ➢conda必須（自前ビルドは苦行） ✓ 野良pip化の動きが強い ✓ https://github.com/facebookresearch/faiss/issues/170

https://bit.ly/2Mn7uNd 157 参考資料 ➢ Faissのwiki: [https://github.com/facebookresearch/faiss/wiki] ➢ Faiss tips: [https://github.com/matsui528/faiss_tips]
オススメ ➢ Lookup系の様々な手法のjulia実装 [https://github.com/una-dinosauria/Rayuela.jl] ➢ PQ元論文：H. Jégou et al., “Product quantization for nearest neighbor search,” TPAMI 2011 ➢ IVFADC + HNSW (1): M. Douze et al., “Link and code: Fast indexing with graphs and compact regression codes,” CVPR 2018 ➢ IVFADC + NHSW (2): D. Baranchuk et al., “Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors,” ECCV 2018

https://bit.ly/2Mn7uNd 159 ベンチマーク ➢ https://github.com/erikbern/ann-benchmarks

https://bit.ly/2Mn7uNd 160 ベンチマーク ➢ https://github.com/erikbern/ann-benchmarks ➢ 右上なほど良い ➢ 2019/7現在、トップはNMSLIBと NGT
(yahoo japan)で競っている

https://bit.ly/2Mn7uNd 161 ベンチマーク ➢ https://github.com/erikbern/ann-benchmarks ➢ 右上なほど良い ➢ 2019/7現在、トップはNMSLIBと NGT
(yahoo japan)で競っている注意： ➢ このベンチはmillion-scaleだけ ➢ クエリパラメを変えながらプロットしているため、実際はデフォルトパラメである曲線中の一点が重要 ➢ faissに厳しい（ちゃんとパラメータ設定していない） ➢ いろいろ大きくなりすぎた結果、実行に一日以上かかる ➢ ann-benchmarks-simpleを作ってます

https://bit.ly/2Mn7uNd 162 「部分」に対して探す ➢ ANNはデータベース中の全データに対する探索は速いが、「部分」に対する探索は考えられてこなかった ✓ 例：画像検索で、まずタグで絞り込む。絞り込んだ結果は画像ID125, ID223, …のようにIDの集合で表現される。これらに対して画像検索をしたい
➢ ID集合もインプットとして与える検索 ➢ Y. Matsui, R. Hinami, and S. Satoh, “Reconfigurable Inverted Index,” ACM Multimedia 2018 ➢ pip install rii

https://bit.ly/2Mn7uNd 163 1T個（1012個）のベクトルに対する探索探索の規模感 ➢ K(= 103) ローカルで一瞬 ➢ M(=
106) データはメモリにのる。いろいろなことを試せる ➢ G(= 109) データを強く圧縮しなければメモリに載らない。ちょっと大がかりなことをすると一日かかる。データセットは２つしかない ➢ T(= 1012) 想像も出来ない https://github.com/facebookresearch/faiss/ wiki/Indexing-1T-vectors ➢ 唯一faissのwikiに記述がある ➢ 分散、ディスクをメモリにマップ、いろいろ。戦国時代に戻った https://github.com/facebookresearch/faiss/wiki/Indexing-1T-vectors 15エクサ要素の疎行列？？

https://bit.ly/2Mn7uNd 164 コンピュータビジョン―広がる要素技術と応用― 第6章：近似最近傍探索共立出版，米谷竜・斎藤英雄・池畑諭・牛久祥孝・内山
英昭・内海ゆづ子・小野峻佑・片岡裕雄・金崎朝子・川西康友・齋藤真樹・櫻田健・高橋康輔・松井勇佑別の参考資料直積量子化を用いた近似最近傍探索に関するサーベイ http://yusukematsui.me/project/survey_pq/survey_pq_jp.html サーベイ論文： Y. Matsui, Y. Uchida, H. Jégou, and S. Satoh, “A Survey of Product Quantization”, ITE Journal, 2018 関連する教科書：

https://bit.ly/2Mn7uNd 165 ANNの問題 ➢ 数学的背景がない。実データで実測で早ければ良いということになっている ✓ LSHのころは近似最近傍探索問題が数学的に定義されていたが、近年のデータ依存系ではスルーされている ➢ なので、手法そのものが良いのか、あるデータに対して偶然強いのか、実装が良
いのか、分離が難しい ✓ 事実、faissはSIMD芸の恩恵が大きいし、またバックエンドがOpenBLASか Intel MKLかで速度がかなり違う ➢ 「あるデータセットに対しこの手法はなぜ性能がいいのか」を説明できる方法が開発されると分野への貢献が大きい

https://bit.ly/2Mn7uNd 166 ANNの問題 ➢ データセット不足。現在billion級がSIFT1BとDeep1Bしかないのでこれらで測るしかない。しかしそれでいいのか？ ✓ 事実、どうやら2010年代のbillion系ANNはSIFT1B（要素が0-255のヒストグラム、ブロックワイズな相関、128D）に特化していたような印象がある ✓
billion以上のデータセットを作るのはそもそも大変そう ✓ million級であっても、様々な特性（スパースかどうか、値のレンジはどうか、）のデータセットがたくさんあればいい ✓ おもしろいリアルデータを公開できるという方、共同研究しませんか？？

近似最近傍探索の最前線

近似最近傍探索の最前線

More Decks by Yusuke Matsui

Other Decks in Research

Featured

Transcript