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.8k
Engineer's meetup for students
kosukearase
0
2.4k
Other Decks in Programming
See All in Programming
Compose 1.7のTextFieldはPOBox Plusで日本語変換できない
tomoya0x00
0
200
as(型アサーション)を書く前にできること
marokanatani
10
2.7k
Click-free releases & the making of a CLI app
oheyadam
2
120
みんなでプロポーザルを書いてみた
yuriko1211
0
280
Hotwire or React? ~アフタートーク・本編に含めなかった話~ / Hotwire or React? after talk
harunatsujita
1
120
macOS でできる リアルタイム動画像処理
biacco42
9
2.4k
React への依存を最小にするフロントエンド設計
takonda
8
2.1k
3 Effective Rules for Using Signals in Angular
manfredsteyer
PRO
0
100
EMになってからチームの成果を最大化するために取り組んだこと/ Maximize team performance as EM
nashiusagi
0
100
[Do iOS '24] Ship your app on a Friday...and enjoy your weekend!
polpielladev
0
110
Better Code Design in PHP
afilina
PRO
0
130
イマのCSSでできる インタラクション最前線 + CSS最新情報
clockmaker
2
140
Featured
See All Featured
Designing on Purpose - Digital PM Summit 2013
jponch
115
7k
Agile that works and the tools we love
rasmusluckow
327
21k
How to train your dragon (web standard)
notwaldorf
88
5.7k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.7k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.9k
Imperfection Machines: The Place of Print at Facebook
scottboms
265
13k
How GitHub (no longer) Works
holman
310
140k
The Language of Interfaces
destraynor
154
24k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
93
16k
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
The Power of CSS Pseudo Elements
geoffreycrofte
73
5.3k
Building Your Own Lightsaber
phodgson
103
6.1k
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 すごい まとめ