Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
メルカリにおけるアルゴリズム ~写真検索機能を例に~
Search
KosukeArase
June 17, 2020
Programming
0
3.6k
メルカリにおけるアルゴリズム ~写真検索機能を例に~
ソフトウェアエンジニア育成プログラム「Build@Mercari」のアルゴリズムの講義において、メルカリの写真検索機能で用いられている近似最近傍探索アルゴリズムについて話した際の資料です
KosukeArase
June 17, 2020
Tweet
Share
More Decks by KosukeArase
See All by KosukeArase
メルカリにおける写真検索機能
kosukearase
5
7.7k
Engineer's meetup for students
kosukearase
0
2.3k
Other Decks in Programming
See All in Programming
ECSのサービス間通信 4つの方法を比較する 〜Canary,Blue/Greenも添えて〜
tkikuc
11
2.3k
外部システム連携先が10を超えるシステムでのアーキテクチャ設計・実装事例
kiwasaki
1
230
Generative AI Use Cases JP (略称:GenU)奮闘記
hideg
0
160
RailsのPull requestsのレビューの時に私が考えていること
yahonda
5
1.7k
Golang と Erlang
taiyow
8
1.9k
Pinia Colada が実現するスマートな非同期処理
naokihaba
2
160
What’s New in Compose Multiplatform - A Live Tour (droidcon London 2024)
zsmb
1
350
Snowflake x dbtで作るセキュアでアジャイルなデータ基盤
tsoshiro
2
430
CSC305 Lecture 13
javiergs
PRO
0
130
Macとオーディオ再生 2024/11/02
yusukeito
0
210
Vue3の一歩踏み込んだパフォーマンスチューニング2024
hal_spidernight
3
3.1k
現場で役立つモデリング 超入門
masuda220
PRO
13
2.9k
Featured
See All Featured
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5k
Making Projects Easy
brettharned
115
5.9k
Thoughts on Productivity
jonyablonski
67
4.3k
Visualization
eitanlees
144
15k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2.1k
Scaling GitHub
holman
458
140k
We Have a Design System, Now What?
morganepeng
50
7.2k
Unsuck your backbone
ammeep
668
57k
Designing for humans not robots
tammielis
249
25k
Typedesign – Prime Four
hannesfritz
39
2.4k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
43
6.6k
Git: the NoSQL Database
bkeepers
PRO
425
64k
Transcript
1 メルカリにおけるアルゴリズム ~写真検索機能を例に~ 2020/06/17 Kosuke Arase (@arase) Software Engineer at
US@Tokyo (ML/DE)
2 荒瀬 晃介 (Kosuke Arase) • US@Tokyo ML/DE Team エンジニア
◦ 東京大学大学院 原田研究室卒 ◦ 2017/08~2019/03: インターン ◦ 2019/04: 新卒入社 ◦ 2019/07~2020/03: 写真検索 (TechLead) ◦ 2020/04~: US@Tokyo ML/DE Team • 専門: 画像認識,3次元点群認識 • 出品時の画像認識機能/写真検索機能 • Twitter, GitHub: @KosukeArase $ whoami
3 • 持ち帰って欲しいこと ◦ アルゴリズムの強力さ ◦ 計算量大事 • 持ち帰らなくて良いこと ◦
メルカリの写真検索や近似近傍探索の詳細な仕組み 今日の目的
4 • いわゆる画像検索機能 (iOS のみ) • 商品名を知らなくても画像から商品を検索可能 What is 写真検索
動画リンク: https://youtu.be/kTni8EvOCgI
5 • 画像から Neural Network を用いて 特徴量 (ベクトル) を抽出 •
ベクトルを近傍探索インデックスに追加 データの流れ Neural Network 0.32 0.55 0.23 0.12 ︙ 0.33 ベクトル 近傍探索 インデックス
6 最近傍探索 クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 最も距離が近いものを探す 特徴ベクトル空間 クエリ画像
7 最近傍探索 クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 最も距離が近いものを探す 特徴ベクトル 特徴空間 クエリ画像
8 最近傍探索 クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 最も距離が近いものを探す 特徴ベクトル 特徴空間 クエリ画像
9 ベクトルの距離の計算 (2次元) の距離:
10 ベクトルの距離の計算 (N次元) の距離: の距離:
11 最近傍探索 クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 最も距離が近いものを探す 特徴ベクトル 特徴空間 クエリ画像
12 ある検索クエリについて、データベース内の 全ての特徴ベクトルとの距離を計算する際の計算量をO記法で答えよ • 特徴ベクトルの次元数: d 次元 • 特徴ベクトルの数: N
個 問題
13 ある検索クエリについて、データベース内の 全ての特徴ベクトルとの距離を計算する際の計算量をO記法で答えよ • 特徴ベクトルの次元数: d 次元 • 特徴ベクトルの数: N
個 1組の特徴ベクトル間の距離を計算: O(d) N個の特徴ベクトルそれぞれとの距離を計算: O(Nd) 答え: O(Nd) 問題
14 • 特徴ベクトルの次元数: d = 1,840 次元 • 特徴ベクトルの数: N
= 数千万 O(Nd) なので 1,840 x 数千万 = 数百億回の計算を毎回する…? 実際には…
15 • 特徴ベクトルの次元数: d = 1,840 次元 • 特徴ベクトルの数: N
= 数千万 O(Nd) なので 1,840 x 数千万 = 数百億回の計算を毎回する…? 2.9 GHz で動作する CPU が1クロックで1命令処理できるとすると、 秒間の計算数は数十億 → 検索に毎回数十秒かかってしまう 実際には…
16 • 特徴ベクトルの次元数: d = 1,840 次元 • 特徴ベクトルの数: N
= 数千万 データベースのサイズも問題。 float32 (4 Bytes) のベクトルとすると、index のサイズは、、 4 x 1,840 x 数千万 = 数百 GB →メモリに載らない! 実際には…
17 import faiss, timeit import numpy as np d =
1024 # ベクトルの次元数 N = 10**5 # データ数 index_flat = faiss.IndexFlatL2(d) # 近傍探索 index index_flat.add(np.random.random((N, d)).astype('float32')) # N本のd次元ベクトルを作成しindexへ追加 query = np.random.random((1, d)).astype('float32') # クエリの作成 def search(_index, _query): _index.search(_query, 10) # 検索 timeit.timeit("search(index_flat, query)", setup="from __main__ import search, index_flat, query", number=1) Facebook AI Research (FAIR) が開発した近傍探索ライブラリ Faiss Demo
18 • PCA などによりベクトルの次元を削減 (e.g. d = 1840 -> 128)
• 近似最近傍探索 高速化
19 • PCA などによりベクトルの次元を削減 (e.g. d = 1840 -> 128)
• 近似最近傍探索 高速化
20 最近傍探索 (再掲) クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 最も距離が近いものを探す 特徴ベクトル 特徴空間 クエリ画像
21 近似最近傍探索 クエリ画像とインデックス内の 各データについて 特徴ベクトルどうしの距離を計算し、 厳密に最近傍でなくても良いので 距離が近いものを高速に探す 特徴ベクトル 特徴空間 クエリ画像
22 • Locality Sensitive Hashing (LSH) ◦ Falconn, etc. •
Tree based ◦ FLANN, Annoy*1, etc. • Graph based ◦ NMSLIB • データ圧縮 ◦ ハミング系、ベクトル量子化 (VQ)、直積量子化 (PQ) • 転置ファイルインデックス (IVF) 近似近傍探索アルゴリズム/ライブラリ *1 Approximate Nearest Neighbors Oh Yeah
23 • Locality Sensitive Hashing (LSH) ◦ Falconn, etc. •
Tree based ◦ FLANN, Annoy*1, etc. • Graph based ◦ NMSLIB • データ圧縮 ◦ ハミング系、ベクトル量子化 (VQ)、直積量子化 (PQ) • 転置ファイルインデックス (IVF) 近似近傍探索アルゴリズム/ライブラリ *1 Approximate Nearest Neighbors Oh Yeah
24 • 近似最近傍探索の最前線 ◦ 松井勇佑 (相澤・山崎・松井研究室講師) ◦ 以下ではこちらの資料の画像を引用 • メルカリUSの
@kumon とともに CVPR@2020 で Tutorial 開催 ◦ Image Retrieval in the Wild ◦ 08:30-, June 19th (AM), 2020 ◦ (日本時間6/20の午前0:30) ◦ メルカリの写真検索がトップに! 参考資料
25 (コードブックは事前に 訓練データにk-meansを施し獲得)
26 (コードブックは事前に 訓練データにk-meansを施し獲得)
27 • 近似精度 (Kの大きさ) と量子化の計算量 (O(DK)) のトレードオフ • データ圧縮のために使うのは難しい
28
29 • メモリ効率が良い • 入力とコードの距離を近似計算可能
30 1本のベクトル (D=1,024次元、32bit float) を M=64分割してK=256個 (8bit) のコードブックを保持する場合のメモリは? 直積量子化 (メモリ効率)
31 1本のベクトル (D=1,024次元、32bit float) を M=64分割してK=256個 (8bit) のコードブックを保持する場合のメモリは? • Before:
32D [bit] = 4D [Byte] = 4,096 [Byte] 直積量子化 (メモリ効率)
32 1本のベクトル (D=1,024次元、32bit float) を M=64分割してK=256個 (8bit) のコードブックを保持する場合のメモリは? • Before:
32D [bit] = 4D [Byte] = 4,096 [Byte] • After: 8M [bit] = M [byte] = 64 [Byte] 直積量子化 (メモリ効率)
33 直積量子化 (距離近似) クエリベクトルとデータベース内のベクトルの距離は クエリベクトルとPQコードとの距離で近似され高速に計算可能
34 直積量子化 (距離近似) ルックアップテーブル クエリベクトルとデータベース内のベクトルの距離は クエリベクトルとPQコードとの距離で近似され高速に計算可能 • D次元のクエリをM分割し、各コード(K個)との距離を 予め計算してルックアップテーブルに保存 (O(DK))
35 クエリベクトルとデータベース内のベクトルの距離は クエリベクトルとPQコードとの距離で近似され高速に計算可能 • D次元のクエリをM分割し、各コード(K個)との距離を 予め計算してルックアップテーブルに保存 (O(DK)) • データベース内のN個のPQコードとの距離は ルックアップテーブルを参照して足し合わせる
(O(MN)) 直積量子化 (距離近似) ルックアップテーブル O(DK + MN)
36 データベース中の各データベクトル Xi に対し以下の操作を行う • K-meansなどで粗い量子化器を用いて、空間を c 個に分割する 転置ファイルインデックス (IVF,
indexing)
37 データベース中の各データベクトル Xi に対し以下の操作を行う • K-meansなどで粗い量子化器を用いて、空間を c 個に分割する • 入力と最も近い代表点
(Cj) との距離の差 (残差、ri = Xi - Cj) を計算 転置ファイルインデックス (IVF, indexing)
38 データベース中の各データベクトル Xi に対し以下の操作を行う • K-meansなどで粗い量子化器を用いて、空間を c 個に分割する • 入力と最も近い代表点
(Cj) との距離の差 (残差、ri = Xi - Cj) を計算 • 粗い量子化の結果 (j) と残差 ri のPQコード (ri’) を保存 転置ファイルインデックス (IVF, indexing) j = 1 j = 2 j = c
39 クエリ q に対し以下の操作を行う • クエリ q に最も近い代表点 (Cj) との距離の差
(残差、r = q - Cj) を計算 転置ファイルインデックス (IVF, search)
40 クエリ q に対し以下の操作を行う • クエリ q に最も近い代表点 (Cj) との距離の差
(残差、r = q - Cj) を計算 • j に登録されている全てのコード (N個) との近似距離を計算 (O(DK+MN)) • 近似距離が最も近いものを選ぶ 転置ファイルインデックス (IVF, search) j = c j = 2 j = 1
41 結局どれくらい早くなるの? Brute force • O(ND) = 1,024 x 3,000万
= 300億回の計算 IVF+PQ • 粗い量子化: O(DC) = 1,024 x 8,192 = 1,000万回の計算 • PQ: O(DK+M(N/C)) = 1,024 x 256 + 64 x (3,000万/8,192) = 50 万の計算 数千倍の高速化! • 特徴ベクトルの次元数 : D = 1,024 次元 • 特徴ベクトルの数: N = 3,000万 • 粗い量子化: c = 8,192 • PQの分割数: M = 64 • コードサイズ: K = 256
42 import faiss, timeit import numpy as np d =
1024 # ベクトルの次元数 N = 10**6 # データ数 index_pq = faiss.index_factory(d, 'IVF512,PQ64') # 近傍探索 index (IVF + PQ) index_pq.train(np.random.random((10**5, d)).astype('float32')) # 事前学習 index_pq.add(np.random.random((N, d)).astype('float32')) # N本のd次元ベクトルを作成しindexへ追加 query = np.random.random((1, d)).astype('float32') # クエリの作成 def search(_index, _query): _index.search(_query, 10) # 検索 timeit.timeit("search(index_pq, query)", setup="from __main__ import search, index_pq, query", number=1) Brute force では 10**6 で xxx 秒、10**7 で OOM したが、、 Demo (IVF+PQ)
43 • メルカリで使用されているアルゴリズムの一例を示した • 持ち帰って欲しいこと ◦ アルゴリズムの強力さ ◦ 計算量大事 ◦
Faiss すごい まとめ