最近傍探索と直積量子化(Nearest neighbor search and Product Quantization)
6 likes4,948 views
最近傍探索の問題と手法についての説明です。木構造や表構造などを使用するkd木探索、LSHの手法について説明します。次元の呪いという問題を解決するための直積量子化(Product Quantization)も含めます。
![高次元と低次元
参考文献 1
定理 1(引用)
Let F is an arbitrary distribution of n points (from a database of N
uniformly distributed points), the distance function is an k-norm
Minkowski distance function inside an Euclidean space RD
. Therefore,
Ck ≤ lim
D→+∞
E
[
dmax ? dmin
D1/k?1/2
]
≤ (N ? 1)Ck (4)
, where dmax, dmin are the farthest and nearest distance from a point in F
to the query point, respectively. Ck is a constant value that depends on k.
1
A. Hinneburg et al , “What Is the Nearest Neighbor in High
Dimensional Spaces?”, Proceedings of the 26th International Conference
on Very Large Data Bases, pp.506-515, 2000
NGUYEN ANH TUAN Group study memo 9 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-13-320.jpg)
![Vector Quantization
コードブック (codebook) C = {pi|0 ≤ i < k}
量子器 (quantizer) Q : RD
→ C
x ∈ RD
の時、Q(x) ∈ C
RD
を k 領域に分割する → ボロノイ図のイメージ
Q(x) = arg min
ci∈C
d(x, ci) (6)
ボロノイ領域を Vi = {x ∈ RD
: Q(x) = ci} とすると、
ci = E[x|i] =
∫
Vi
p(x)xdx (7)
NGUYEN ANH TUAN Group study memo 35 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-56-320.jpg)
![Product Quantization
発想
64 bit のコードブック ? log2 k = 64 ? k = 264
264
個の整数型データを保存するのに、コードブックのサイズ
は 264
× 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte]
NGUYEN ANH TUAN Group study memo 39 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-67-320.jpg)
![Product Quantization
発想
64 bit のコードブック ? log2 k = 64 ? k = 264
264
個の整数型データを保存するのに、コードブックのサイズ
は 264
× 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte]
例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必
要な個数は
NGUYEN ANH TUAN Group study memo 39 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-68-320.jpg)
![Product Quantization
発想
64 bit のコードブック ? log2 k = 64 ? k = 264
264
個の整数型データを保存するのに、コードブックのサイズ
は 264
× 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte]
例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必
要な個数は 2 × 232
= 233
個
NGUYEN ANH TUAN Group study memo 39 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-69-320.jpg)
![Product Quantization
発想
64 bit のコードブック ? log2 k = 64 ? k = 264
264
個の整数型データを保存するのに、コードブックのサイズ
は 264
× 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte]
例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必
要な個数は 2 × 232
= 233
個
コードブックのサイズは 233
× 32[bit]≈ 32, 000[GB]=32[TB]
NGUYEN ANH TUAN Group study memo 39 / 45](https://image.slidesharecdn.com/slide20140515-140513105215-phpapp01/85/Nearest-neighbor-search-and-Product-Quantization-70-320.jpg)
![[DL輪読会]GLIDE: Guided Language to Image Diffusion for Generation and Editing](https://cdn.slidesharecdn.com/ss_thumbnails/glide2-220107030326-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://cdn.slidesharecdn.com/ss_thumbnails/20220325okimura-220405024717-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Deep Reinforcement Learning that Matters](https://cdn.slidesharecdn.com/ss_thumbnails/deeprlthatmatters-171212050658-thumbnail.jpg?width=560&fit=bounds)
![SSII2021 [OS2-01] 転移学習の基礎：異なるタスクの知識を利用するための機械学習の方法](https://cdn.slidesharecdn.com/ss_thumbnails/os2-02final-210610091211-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Wasserstein GAN/Towards Principled Methods for Training Generative Adv...](https://cdn.slidesharecdn.com/ss_thumbnails/wgan-1-170224021826-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to 最近傍探索と直積量子化(Nearest neighbor search and Product Quantization) (20)
![[DL輪読会]Convolutional Conditional Neural Processesと Neural Processes Familyの紹介](https://cdn.slidesharecdn.com/ss_thumbnails/20191220readingpaperconvcnp-191220034420-thumbnail.jpg?width=560&fit=bounds)
Recently uploaded (11)
最近傍探索と直積量子化(Nearest neighbor search and Product Quantization)
- 1. Nearest Neighbor Search(NNS) NGUYEN ANH TUAN Bachelor 4th year The Engineering Falcuty, the University of Tokyo May 14, 2014 NGUYEN ANH TUAN Group study memo 1 / 45
- 2. 自己紹介 2008 年?来日 2009 年～2012 年?兵庫県明石高専 卒論:「エッジ方向のヒストグラムを利用した電子透かしの手 法」(対象:文章画像) 2012 年?東大 2 年に編入 好きなプログラミング言語:C/C++、Java、最近は Ruby を 触っています。 NGUYEN ANH TUAN Group study memo 2 / 45
- 3. 本日の流れ 1 概要 問題の定義 定義の解説 空間と距離 次元 課題:次元の呪縛 関連問題 k 近傍法 ボロノイ図 近似最近傍探索 2 アルゴリズム 線形探索 kd 木 Locality Sensitive Hashing その他 3 最近の研究 Vector Quantization Product Quantization 最近傍探索との関連 4 まとめ NGUYEN ANH TUAN Group study memo 3 / 45
- 4. 問題の定義 Nearest Neighbor Search(NNS problem) D 次元ユークリッド空間 RD において ベクトル x = ( x1, x2, . . . xD ) 距離 d ( x, y ) = √ (x1 ? y1)2 + (x2 ? y2)2 + . . . + (xD ? yD)2 と表記すると、 入力:部分集合 Y ? RD とベクトル x ∈ RD 出力:Y の要素の中で x と “一番近い”要素 NN(x)。 要するに、入力 ( Y, x ) が与えられた時、 NN(x) = arg min y∈Y d(x, y) (1) を求める問題 NGUYEN ANH TUAN Group study memo 4 / 45
- 5. 解説 空間と距離 高次元と低次元 NGUYEN ANH TUAN Group study memo 5 / 45
- 6. ユークリッド空間内の距離 ユークリッド距離 → 直感的、通常の距離 →Minkowski 距離 dp(x, y) = ( D∑ i=1 |xi ? yi|p )1 p → p = 2 の時、ユークリッド距離 NGUYEN ANH TUAN Group study memo 6 / 45
- 7. ユークリッド空間内の距離 ユークリッド距離 → 直感的、通常の距離 →Minkowski 距離 dp(x, y) = ( D∑ i=1 |xi ? yi|p )1 p → p = 2 の時、ユークリッド距離 p = 1 の時、マンハッタン距離 dM (x, y) = D∑ i=1 |xi ? yi| (2) NGUYEN ANH TUAN Group study memo 6 / 45
- 8. ユークリッド空間内の距離 ユークリッド距離 → 直感的、通常の距離 →Minkowski 距離 dp(x, y) = ( D∑ i=1 |xi ? yi|p )1 p → p = 2 の時、ユークリッド距離 p = 1 の時、マンハッタン距離 dM (x, y) = D∑ i=1 |xi ? yi| (2) Question: p > 2 の Minkowski 距離を利用するか? NGUYEN ANH TUAN Group study memo 6 / 45
- 9. Hamming Space Hamming Space:H = {0, 1} の時、すべての長さ D のビッ ト列からなる空間を D 次元 Hamming Space HD NGUYEN ANH TUAN Group study memo 7 / 45
- 10. Hamming Space Hamming Space:H = {0, 1} の時、すべての長さ D のビッ ト列からなる空間を D 次元 Hamming Space HD Hamming 距離 → 二つのビット列の相違度 dH(x, y) = {i|xi ?= yi} (3) NGUYEN ANH TUAN Group study memo 7 / 45
- 11. Hamming Space Hamming Space:H = {0, 1} の時、すべての長さ D のビッ ト列からなる空間を D 次元 Hamming Space HD Hamming 距離 → 二つのビット列の相違度 dH(x, y) = {i|xi ?= yi} (3) 例: 00011 と 00101 の相違度が 2 NGUYEN ANH TUAN Group study memo 7 / 45
- 12. 解説 空間と距離 高次元と低次元 NGUYEN ANH TUAN Group study memo 8 / 45
- 13. 高次元と低次元 参考文献 1 定理 1(引用) Let F is an arbitrary distribution of n points (from a database of N uniformly distributed points), the distance function is an k-norm Minkowski distance function inside an Euclidean space RD . Therefore, Ck ≤ lim D→+∞ E [ dmax ? dmin D1/k?1/2 ] ≤ (N ? 1)Ck (4) , where dmax, dmin are the farthest and nearest distance from a point in F to the query point, respectively. Ck is a constant value that depends on k. 1 A. Hinneburg et al , “What Is the Nearest Neighbor in High Dimensional Spaces?”, Proceedings of the 26th International Conference on Very Large Data Bases, pp.506-515, 2000 NGUYEN ANH TUAN Group study memo 9 / 45
- 14. 高次元と低次元 k > 2 の Minkowski 距離 dk(x, y) を利用した時、 NGUYEN ANH TUAN Group study memo 10 / 45
- 15. 高次元と低次元 k > 2 の Minkowski 距離 dk(x, y) を利用した時、 空間の次元 D を増加させると、 NGUYEN ANH TUAN Group study memo 10 / 45
- 16. 高次元と低次元 k > 2 の Minkowski 距離 dk(x, y) を利用した時、 空間の次元 D を増加させると、 dmax ? dmin が 0 に収束 NGUYEN ANH TUAN Group study memo 10 / 45
- 17. 高次元と低次元 k > 2 の Minkowski 距離 dk(x, y) を利用した時、 空間の次元 D を増加させると、 dmax ? dmin が 0 に収束 → 高次元で k > 2 の Minkowski 距離の時、データセットの中の最 短距離と最長距離はほぼ一致してしまう NGUYEN ANH TUAN Group study memo 10 / 45
- 18. 次元の呪縛 ざっくり見ると、普通な問題 一番簡単な手法:線形探索 → 時間計算量 O(nD) NGUYEN ANH TUAN Group study memo 11 / 45
- 19. 次元の呪縛 ざっくり見ると、普通な問題 一番簡単な手法:線形探索 → 時間計算量 O(nD) 次元の一定の値を超えると、いかなるアルゴリズムでも線形 探索 (全探索) と等価である。 NGUYEN ANH TUAN Group study memo 11 / 45
- 20. 関連問題 k 近傍法 ボロノイ図 近似最近傍探索 (ANN) NGUYEN ANH TUAN Group study memo 12 / 45
- 21. k 近傍法の例 学習用のデータが二つカテゴリ A, B に 分けた時、問い合わせデータ “?”はどの カテゴリに入るか？→ データの分類問題 アルゴリズム: NGUYEN ANH TUAN Group study memo 13 / 45
- 22. k 近傍法の例 学習用のデータが二つカテゴリ A, B に 分けた時、問い合わせデータ “?”はどの カテゴリに入るか？→ データの分類問題 アルゴリズム: 1 k を適切に選ぶ 2 “?”と学習用のデータとの距離を 計算 3 距離でデータを並び替える NGUYEN ANH TUAN Group study memo 13 / 45
- 23. k 近傍法の例 学習用のデータが二つカテゴリ A, B に 分けた時、問い合わせデータ “?”はどの カテゴリに入るか？→ データの分類問題 アルゴリズム: 1 k を適切に選ぶ 2 “?”と学習用のデータとの距離を 計算 3 距離でデータを並び替える 4 学習用のデータから k 個だけを選 別する。選択されたデータで多数 決投票を行う 5 最多となるデータのカテゴリが、 “?”の推測されたカテゴリとなる。 NGUYEN ANH TUAN Group study memo 13 / 45
- 24. 関連問題 k 近傍法 ボロノイ図 近似最近傍探索 (ANN) NGUYEN ANH TUAN Group study memo 14 / 45
- 25. ボロノイ図:2点のみ NGUYEN ANH TUAN Group study memo 15 / 45
- 26. ボロノイ図:2点のみ → A, B それぞれに近い領域に分割 NGUYEN ANH TUAN Group study memo 15 / 45
- 27. ボロノイ図:3点の場合 NGUYEN ANH TUAN Group study memo 16 / 45
- 28. ボロノイ図 NGUYEN ANH TUAN Group study memo 17 / 45
- 29. 関連問題 k 近傍法 ボロノイ図 近似最近傍探索 (ANN) NGUYEN ANH TUAN Group study memo 18 / 45
- 30. 近似最近傍探索(ANN) 次元の呪いへの対策 正確な解を求めるよりも、ある確率以上でそのベクトルが最 近傍となるものを求めたい。 NGUYEN ANH TUAN Group study memo 19 / 45
- 31. 手法 線形探索 kd 木 Locality Sensitive Hashing(LSH) その他 NGUYEN ANH TUAN Group study memo 20 / 45
- 32. 線形探索 すべてのデータをスキャンして、クエリベクトルとの距離を 計算する。 計算した距離の中の最小値とそれに対する位置を求める。 時間計算量 O(nD)、追加メモリなし NGUYEN ANH TUAN Group study memo 21 / 45
- 33. 手法 線形探索 kd 木 Locality Sensitive Hashing(LSH) その他 NGUYEN ANH TUAN Group study memo 22 / 45
- 34. kd木 二分木の探索 → 平均時間計算量:O(D log n)、最悪時 (偏りの 木):O(nD) 空間分割を表現する。 (a) 二次元空間データ (b) kd 木 NGUYEN ANH TUAN Group study memo 23 / 45
- 35. kd木:探索アルゴリズム 1 二分探索木と同じ探索になるが、 2 一致するものではなく、近いものをもとめる。 3 葉へ到着する直前のノードを暫定的な最近傍 temp 4 back track を行い、temp から root へ戻る道で、query と より近いものがあれば、temp を更新する。 NGUYEN ANH TUAN Group study memo 24 / 45
- 36. kd木:次元の呪い 平衡木にすれば、1～3 の平均時間計算量が O(D log n) になる が、その時でも 4 の計算量が生じる。 2 D.T. Lee, C. K. Wong, “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”, Acta Informatica 13. XII. 1977, Volume 9, Issue 1, pp 23-29 NGUYEN ANH TUAN Group study memo 25 / 45
- 37. kd木:次元の呪い 平衡木にすれば、1～3 の平均時間計算量が O(D log n) になる が、その時でも 4 の計算量が生じる。 次元の呪い:参考文献 2 では、最悪時 kd 木での探索の時間計算 量は O(Dn1?1/D ) となる。 2 D.T. Lee, C. K. Wong, “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”, Acta Informatica 13. XII. 1977, Volume 9, Issue 1, pp 23-29 NGUYEN ANH TUAN Group study memo 25 / 45
- 38. kd木:次元の呪い 平衡木にすれば、1～3 の平均時間計算量が O(D log n) になる が、その時でも 4 の計算量が生じる。 次元の呪い:参考文献 2 では、最悪時 kd 木での探索の時間計算 量は O(Dn1?1/D ) となる。 D → +∞ の時 Dn1?1/D → Dn (5) 2 D.T. Lee, C. K. Wong, “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”, Acta Informatica 13. XII. 1977, Volume 9, Issue 1, pp 23-29 NGUYEN ANH TUAN Group study memo 25 / 45
- 39. kd木:最悪時の例 NGUYEN ANH TUAN Group study memo 26 / 45
- 40. kd木:もう一つの問題点 暫定解を格納するメモリが生じる。→ データを葉につめる。 データを葉につめる。一個のデータを一つの箱にいれる。→ 箱の分け方？ NGUYEN ANH TUAN Group study memo 27 / 45
- 41. 手法 線形探索 kd 木 Locality Sensitive Hashing(LSH) その他 NGUYEN ANH TUAN Group study memo 28 / 45
- 42. 手法 線形探索 kd 木 Locality Sensitive Hashing(LSH) その他 NGUYEN ANH TUAN Group study memo 29 / 45
- 43. AESA 距離の三公理を使う。→ 距離の選択:Minkowski 距離なら OK NGUYEN ANH TUAN Group study memo 30 / 45
- 44. AESA 距離の三公理を使う。→ 距離の選択:Minkowski 距離なら OK アルゴリズム 1 全データでペアの距離を計算する。 2 表で計算結果をまとめる。 3 距離の三公理と表のデータで最近傍になり得ないものを除去 する。 NGUYEN ANH TUAN Group study memo 30 / 45
- 45. AESA 距離の三公理を使う。→ 距離の選択:Minkowski 距離なら OK アルゴリズム 1 全データでペアの距離を計算する。 2 表で計算結果をまとめる。 3 距離の三公理と表のデータで最近傍になり得ないものを除去 する。 → 問題点:距離のデータを格納する表の作成に時間がかかる。 探索時、蓄積データのためにメモリ量がかかる。 NGUYEN ANH TUAN Group study memo 30 / 45
- 46. AESA 距離の三公理を使う。→ 距離の選択:Minkowski 距離なら OK アルゴリズム 1 全データでペアの距離を計算する。 2 表で計算結果をまとめる。 3 距離の三公理と表のデータで最近傍になり得ないものを除去 する。 → 問題点:距離のデータを格納する表の作成に時間がかかる。 探索時、蓄積データのためにメモリ量がかかる。 →LAESA:蓄積データの一部のみを使用する。 NGUYEN ANH TUAN Group study memo 30 / 45
- 47. ボロノイ分割 ボロノイ分割を行ってから、クエリベクトルはどのボロノイ 領域になるかを調べて、その領域の母点を最近傍となる。 ボロノイ分割を行うのに O(n2 D) の時間がかかる。 NGUYEN ANH TUAN Group study memo 31 / 45
- 48. 最近の研究 Product Quantization3 3 H. Jegou et al., “Product Quantization for Nearest Neighbor Search”, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL. 33, NO. 1,JANUARY 2011, pp 117-126 NGUYEN ANH TUAN Group study memo 32 / 45
- 49. Quantization 量子化 NGUYEN ANH TUAN Group study memo 33 / 45
- 50. Quantization 量子化 スカラ量子化 NGUYEN ANH TUAN Group study memo 33 / 45
- 51. Vector Quantization スカラ量子化 →1 次元データの表現 (数値だけ?) NGUYEN ANH TUAN Group study memo 34 / 45
- 52. Vector Quantization スカラ量子化 →1 次元データの表現 (数値だけ?) ベクトル量子化 NGUYEN ANH TUAN Group study memo 34 / 45
- 53. Vector Quantization コードブック (codebook) C = {pi|0 ≤ i < k} 量子器 (quantizer) Q : RD → C x ∈ RD の時、Q(x) ∈ C NGUYEN ANH TUAN Group study memo 35 / 45
- 54. Vector Quantization コードブック (codebook) C = {pi|0 ≤ i < k} 量子器 (quantizer) Q : RD → C x ∈ RD の時、Q(x) ∈ C RD を k 領域に分割する → ボロノイ図のイメージ NGUYEN ANH TUAN Group study memo 35 / 45
- 55. Vector Quantization コードブック (codebook) C = {pi|0 ≤ i < k} 量子器 (quantizer) Q : RD → C x ∈ RD の時、Q(x) ∈ C RD を k 領域に分割する → ボロノイ図のイメージ Q(x) = arg min ci∈C d(x, ci) (6) NGUYEN ANH TUAN Group study memo 35 / 45
- 56. Vector Quantization コードブック (codebook) C = {pi|0 ≤ i < k} 量子器 (quantizer) Q : RD → C x ∈ RD の時、Q(x) ∈ C RD を k 領域に分割する → ボロノイ図のイメージ Q(x) = arg min ci∈C d(x, ci) (6) ボロノイ領域を Vi = {x ∈ RD : Q(x) = ci} とすると、 ci = E[x|i] = ∫ Vi p(x)xdx (7) NGUYEN ANH TUAN Group study memo 35 / 45
- 57. Vector Quantization コードブックのサイズ k NGUYEN ANH TUAN Group study memo 36 / 45
- 58. Vector Quantization コードブックのサイズ k 各ベクトルを表現するのに ?log2 k? ビットが必要 NGUYEN ANH TUAN Group study memo 36 / 45
- 59. Vector Quantization コードブックのサイズ k 各ベクトルを表現するのに ?log2 k? ビットが必要 空間を k 領域に分割 → k-means 法の量子器 NGUYEN ANH TUAN Group study memo 36 / 45
- 60. Vector Quantization:次元の呪い コードブックのサイズ k NGUYEN ANH TUAN Group study memo 37 / 45
- 61. Vector Quantization:次元の呪い コードブックのサイズ k k はどのぐらいとれば良いか? NGUYEN ANH TUAN Group study memo 37 / 45
- 62. Vector Quantization:次元の呪い コードブックのサイズ k k はどのぐらいとれば良いか? → k ≈ exp(D) NGUYEN ANH TUAN Group study memo 37 / 45
- 63. Vector Quantization:次元の呪い コードブックのサイズ k k はどのぐらいとれば良いか? → k ≈ exp(D) → 次元が増えると、コードブックのサイズが指数的に増加 NGUYEN ANH TUAN Group study memo 37 / 45
- 64. Product Quantization ベクトル量子化の欠点を補いたい → 直積量子化 NGUYEN ANH TUAN Group study memo 38 / 45
- 65. Product Quantization 発想 NGUYEN ANH TUAN Group study memo 39 / 45
- 66. Product Quantization 発想 64 bit のコードブック ? log2 k = 64 ? k = 264 264 個の整数型データを保存するのに、コードブックのサイズ は NGUYEN ANH TUAN Group study memo 39 / 45
- 67. Product Quantization 発想 64 bit のコードブック ? log2 k = 64 ? k = 264 264 個の整数型データを保存するのに、コードブックのサイズ は 264 × 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte] NGUYEN ANH TUAN Group study memo 39 / 45
- 68. Product Quantization 発想 64 bit のコードブック ? log2 k = 64 ? k = 264 264 個の整数型データを保存するのに、コードブックのサイズ は 264 × 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte] 例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必 要な個数は NGUYEN ANH TUAN Group study memo 39 / 45
- 69. Product Quantization 発想 64 bit のコードブック ? log2 k = 64 ? k = 264 264 個の整数型データを保存するのに、コードブックのサイズ は 264 × 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte] 例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必 要な個数は 2 × 232 = 233 個 NGUYEN ANH TUAN Group study memo 39 / 45
- 70. Product Quantization 発想 64 bit のコードブック ? log2 k = 64 ? k = 264 264 個の整数型データを保存するのに、コードブックのサイズ は 264 × 32[bit]≈ 64, 000, 000, 000, 000[GB]=64[Zettabyte] 例えば、各 ci を二つの 32 ビットの ci1, ci2 に分割すると、必 要な個数は 2 × 232 = 233 個 コードブックのサイズは 233 × 32[bit]≈ 32, 000[GB]=32[TB] NGUYEN ANH TUAN Group study memo 39 / 45
- 71. Product Quantization コードブック (codebook) C = {pi|0 ≤ i < k} の D = log2 k 次元の空間を m 個 Cj の子空間 (次元が D/m) に分割する。 C = C1 × C2 × . . . × Cm (8) NGUYEN ANH TUAN Group study memo 40 / 45
- 72. Product Quantization コードブック (codebook) C = {pi|0 ≤ i < k} の D = log2 k 次元の空間を m 個 Cj の子空間 (次元が D/m) に分割する。 C = C1 × C2 × . . . × Cm (8) 子量子器 Qj : RD/m → Cj 子コードブックのサイズ k? = 2 D m = 2 log2 k m = k 1 m (9) 総コードブックのサイズは mk 1 m NGUYEN ANH TUAN Group study memo 40 / 45
- 73. Searching algorithm(By H. Jegou et al.) 1 Indexing 2 Searching NGUYEN ANH TUAN Group study memo 41 / 45
- 74. Indexing 前提条件:次元 D、距離関数 d(x, y) 入力:ベクトル y ∈ RD NGUYEN ANH TUAN Group study memo 42 / 45
- 75. Indexing 前提条件:次元 D、距離関数 d(x, y) 入力:ベクトル y ∈ RD アルゴリズム 1 y を Qc(y) に量子化 2 距離 r(y) = y ? Qc(y) を計算 3 r(y) を Qp(r(y)) に量子化。r(y) を uj(y), j = 1, 2, . . . m に分 割。uj(y) → Qj(y) の対応づけ 4 (Q1, Q2, . . . Qm) をインデクスとする → 転置インデクス NGUYEN ANH TUAN Group study memo 42 / 45
- 76. Searching algorithm(By H. Jegou et al.) 1 Indexing 2 Searching NGUYEN ANH TUAN Group study memo 43 / 45
- 77. Searching 前提条件:次元 D、距離関数 d(x, y) 入力:ベクトル x ∈ RD 出力:最近傍 NN(x) ∈ RD NGUYEN ANH TUAN Group study memo 44 / 45
- 78. Searching 前提条件:次元 D、距離関数 d(x, y) 入力:ベクトル x ∈ RD 出力:最近傍 NN(x) ∈ RD アルゴリズム 1 y を Qc(y) に量子化 2 距離 r(y) = y ? Qc(y) を計算 3 r(y) を Qp(r(y)) に量子化。r(y) を uj(y), j = 1, 2, . . . m に分 割。uj(y) → Qj(y) の対応づけ 4 (Q1, Q2, . . . Qm) をインデクスとする NGUYEN ANH TUAN Group study memo 44 / 45
- 79. まとめ 最近傍探索問題 空間と距離、次元?次元の呪い k 近傍法、ボロノイ図、ANN 最近傍探索の手法 木構造、表、ボロノイ図、ハッシュ Product Quantization VQ、PQ、直積、次元の分割 NGUYEN ANH TUAN Group study memo 45 / 45