近傍検索ライブラリNGTと深層学習による類似ファッション検索 #yjbonfire

1.1K Views

November 05, 19

スライド概要

bonfire data&science #1 イベントで,ヤフーの類似画像検索について紹介した。NGTと呼ばれる大量の高次元ベクトルデータからクエリとして指定されたベクトルデータの近傍に存在するデータを高速に検索するソフトウェアについて詳しく触れられている。

profile-image

エンジニア・デザイナー向けのヤフー公式アカウント。イベント/登壇情報/ブログ記事など、ヤフーの技術・デザインに関わる情報を発信します。

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

近傍検索ライブラリNGTと 深層学習による類似ファッション検索 2019年11月5日 1 Yahoo! JAPAN研究所 岩崎 雅二郎 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

2.

自己紹介 岩崎 雅二郎 Yahoo! JAPAN研究所 l 某複写機メーカー研究所にて類似画像検索技術 をヤフーに提供し、2004年ヤフオク!でリリース l 2007年にヤフーに入社し、類似画像検索、物体 認識、近傍検索の研究開発 l Yahoo!ラボリリース: FavNavi、サイヤスカメラ、 FashionNavi、(monotag、VisualSeeker) 2 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

3.

内容 l 近傍検索ライブラリNGT • ベンチマークによる検索性能 • インデックスの生成と検索 • 高性能な検索を実現する最適化グラフの生成方法 l NGTを用いた深層学習による類似ファッション検索 • • • • 3 類似ファッション検索アプリの紹介 インデックスの生成と検索 特徴量の構成と検索結果 モデル生成用学習データ C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

4.

近傍検索ライブラリNGT 4 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

5.

NGTとは Neighborhood Graph and Tree for Indexing Highdimensional Data ツリー構造 l 高次元ベクトルの近傍検索 l ツリーとグラフによるインデックス グラフ構造 5 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

6.

近傍検索とは 距離空間上でクエリの近傍のオブジェクトを取得 ④ ③ ① ⑤ クエリ ② ⑥ 6 ⑦ l k最近傍検索 l 範囲検索 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

7.

NGTの特徴 • 世界トップレベルの高速高精度な近似近傍検索 • オープンソース • 追加削除が可能 • 多様な利用形態(Python、C++、C、Go、コマンドライン) • サーバ版NGT(ngtd、vald)を提供 • 共有メモリ版でメモリサイズ以上のデータ登録可能 • 量子化版NGT(NGTQ)により、さらなる大規模化が可能 7 ngtd: https://github.com/yahoojapan/ngtd vald: https://github.com/vdaas/vald C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

8.

NGTの性能 8 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

9.

近傍検索ベンチマーク -ANN benchmarks• 近傍検索専用のベンチマーク • Dockerにより独立した動作環境 ANN benchmarks NGT python API NGT Ubuntu Docker • AWSのEC2 c5.4xlargeで実行 Linux AWS EC2 c5.4xlarge 9 NGT faiss hnsw annoy • 多種多様なデータセット(全10セット) Annoy • Annoy, Faiss, HNSWなど主要21種を網羅 Containers ANN benchmarks Ann benchmarks: https://github.com/erikbern/ann-benchmarks C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

10.

ベンチマーク結果① gist 960 10 NGT(ONNG) HNSW(nmslib) Faiss Annoy C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. sift 128

11.

ベンチマーク結果② fashion-mnist 784 11 NGT(ONNG) HNSW(nmslib) Faiss Annoy nytimes 256 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

12.

ベンチマーク結果③ glove 100 12 NGT(ONNG) HNSW(nmslib) Faiss Annoy C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. glove 25

13.

ベンチマーク結果③ NGTがほぼすべてのデータセットでトップを獲得! glove 100 13 NGT(ONNG) HNSW(nmslib) Faiss Annoy C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. glove 25

14.

インデックス生成 14 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

15.

ツリーの生成 l グラフの探索起点の取得に利用 l 超球を用いた空間分割によるツリー(DVP-tree)の生成 DVP-tree: 岩崎, 類似画像検索を実現する距離空間インデックスの実装及び評価, 情報処理学会論文誌データベース(TOD) 40(SIG03(TOD1)), 24-33, 1999 15 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

16.

グラフの生成 l 逐次ノードを追加し近傍オブジェクト同士を接続 l 近傍ノードの検索に生成中のインデックスを利用 ANNG 16 Approximate k-Nearest Neighbor Graph C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

17.

近傍検索 17 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

18.

近傍検索 1. ツリーをたどりクエリの近傍オブ ジェクトを探索起点として取得 2. 探索起点からグラフを探索 1回の距離計算 で下位部分空間 の特定が可能 3最近傍検索 18 参考:https://techblog.yahoo.co.jp/lab/searchlab/ngt-docs-2/ C opyright © 2019 Y ahoo Japan C orporati on. A ll R ights R eserved. https://techblog.yahoo.co.jp/lab/searchlab/ngt-docs-3/

19.

高性能な検索を実現する グラフの生成 19 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

20.

ANNGの課題 エッジを減らすと エッジを増やすと 検索精度低下⤵ 検索精度向上⤴ 検索時間減少⤴ 検索時間増加⤵ 両立困難 20 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

21.

ONNG Optimized Nearest Neighbors Graph 有向エッジとしてANNGを最適化 l ノード単位の入出次数の最適化 l パスを考慮した出次数の削減 l 検索時の参照エッジ数調整 21 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 出次数:2 入次数:4

22.

ノード単位の次数の最適化 l 入次数の均一化 • 入次数が少ないと到達確率が減少 • 均一化により到達確率の底上げ l 出次数の削減 • 出次数は重い距離計算回数に直結 • 出次数の削減により探索時間の削減 22 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

23.

ノード単位の次数の最適化 出次数調整:3 ⑥ ② 出次数:3 入次数:6 ⑦ ② ③ ① ⑥ ④ ⑤ ① ③ ANNG (出力エッジに着目) ④ ⑥ ② ⑥ ④ ② ⑤ 入次数調整:6 ① ③ ⑤ ① ONNG ④ ⑤ 23 ② ① 全ノードに適用 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. ③ ③

24.

ノード単位の次数の最適化 • 最適な次数は? • データセットに強く依存 • 最適次数の探索が必要 • 多くのデータセットに有効な次数 入次数:120、出次数:10 (次元数が少ない場合など入次数の削減可能) 24 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 出次数 入次数

25.

パスを考慮した出次数の削減 • ツリーによりクエリ近傍に到達可能 • 長いショートカットエッジは不要 nd nd nd e4 e2 e1 n1 ns e1削除 25 e3 ns n3 n2 クエリ e5 re ns 代替パスに複数のノード ⇒e3削除せず n4 代替パスのノードn4が遠方 ⇒e4削除せず グラフ全体にパスの最適化を適用 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

26.

検索時の参照エッジ数調整 参照エッジ数(出次数)を指定範囲係数εから算出 参照エッジ数: 探索範囲 rs=(1+ε)r we, e0はデータセットに強く依存 インデックス生成時にwe, e0の最適化を実行 26 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 検索範囲

27.

ANNGとONNGの比較 (ONNG) (ONNG) SIFT 1M 27 (ONNG) GIST 1M C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. Glove 2M

28.

NGTを利用した深層学習による 類似ファッション検索 28 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

29.

Yahoo!ラボ FavNavi • 研究所+有志で研究開発したファッ ション検索実験アプリ • ファッション検索の基盤技術をサー ビスへ提供 アプリの特徴 • • • • Yahoo!ショッピングのファッション商品検索 検索対象領域表示 商品以外のアイテムで検索可能 撮影画像による検索(近日公開予定) https://apps.apple.com/jp/app/favnavi/id1478926680 29 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

30.

Yahoo!ショッピング ショッピング内回遊型類似ファッション検索 30 https://commerceapp.yahoo.co.jp/shoppingappli/ C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

31.

Yahoo!ブラウザー 撮影画像による類似ファッション検索 写真:アフロ https://promo-ybrowser.yahoo.co.jp/ 31 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

32.

類似ファッション検索の 処理の流れ 32 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

33.

インデックスの構築 検出された領域ごとに特徴量を抽出してNGTに登録 検出領域 特徴量 物体検出 特徴量抽出 登録商品画像 Yahoo!ショッピング 33 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. NGT

34.

類似画像検索 選択された領域の特徴量でNGTを検索 特徴量 物体検出 選択 特徴量抽出 クエリ画像 (撮影画像) 34 領域検索結果 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 検索 NGT

35.

特徴量の構成 l 低次特徴量:色やテクスチャをtripletで学習 l カテゴリ特徴量:商品カテゴリで学習 l 領域アスペクト比 低次特徴量抽出 カテゴリ特徴量抽出 低次特徴量 300 35 領域画像 領域アスペクト比 カテゴリ特徴量 128 統合特徴量 429次元 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 1

36.

検索結果比較① 低次特徴量(300次元) 36 カテゴリ特徴量(128次元) C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 統合特徴量(429次元)

37.

検索結果比較② 低次特徴量(300次元) 37 カテゴリ特徴量(128次元) C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 統合特徴量(429次元)

38.

モデル生成用学習データ モデル 画像種別 画像数 物体検出 ヤフオク! Yahoo!ショッピング 50,000件 20,000件 低次特徴量 Yahoo!ショッピング 8,000,000件 カテゴリ特徴量 Yahoo!ショッピング 400,000件 物体検出のアノテーションデータは手作業で生成 38 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

39.

最後に l 深層学習によりベクトルの生成が容易に l 世界トップレベルのNGTを利用して是非 フィードバックを! 39 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.

40.

40 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.