世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例 / YJTC19 in Shibuya B-3 #yjtc

3.1K Views

December 12, 19

yjtc

スライド概要

Yahoo! JAPAN研究所は、深層学習で生成されるようなベクトルデータを高速に検索できるNGTをOSSとしていち早く提供し、改良してきました。そして、ついにNGTがベンチマークで世界最速クラスの検索速度を達成しました。
本セッションでは、NGTがなぜ高速な検索を実現できるのかを解説し、さらに、NGTを用いた深層学習によるファッション類似画像検索の概要についてご紹介しました。

Yahoo!デベロッパーネットワーク

@ydnjp

スライド一覧

2023年10月からSpeaker Deckに移行しました。最新情報はこちらをご覧ください。 https://speakerdeck.com/lycorptech_jp

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

関連スライド

深層学習による自然言語処理入門: word2vecからBERT, GPT-3まで

Yahoo!デベロッパーネットワーク 133.8K

ゼロから始める転移学習

Yahoo!デベロッパーネットワーク 75.3K

ヤフーにおける WebAuthn と Passkey の UX の紹介と考察 #idcon #fidcon

idcon fidcon

Yahoo!デベロッパーネットワーク 64.7K

OpenID Connectとネイティブアプリを取り巻く仕様と動向 Yahoo! JAPANの取り組み #openid #openid_tokyo

openid openid_tokyo

Yahoo!デベロッパーネットワーク 52.5K

運用業務とスクラムは本当に組み合わせにくいのか︖運用業務が大半を占めるプロダクト開発での試行錯誤

devsumi

Yahoo!デベロッパーネットワーク 28.1K

ヤフーのオンプレ機械学習基盤AIPFについて #ml_kubernetes

ml_kubernetes

Yahoo!デベロッパーネットワーク 25.8K

各ページのテキスト

アジェンダ 1. 近傍検索ライブラリNGT • ベンチマークによる検索性能 • インデックスの生成と検索 • 高性能な検索を実現する最適化グラフ 2. 深層学習による類似ファッション検索応用事例 • インデックスの生成と検索 • 特徴量の構成と検索結果 • 学習データによるモデル生成 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例 NGTとは Neighborhood Graph and Tree for Indexing High-dimensional Data ツリー構造 n 高次元ベクトルの近傍検索 n ツリーとグラフによるインデックスグラフ構造 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例 NGTの特徴 n 世界トップレベルの高速高精度な近似近傍検索 n オープンソース n 追加削除が可能 n 多様な利用形態（Python、C++、C、Go、コマンドライン、Ruby） n サーバ版NGT（ngtd、vald）を提供 ngtd: https://github.com/yahoojapan/ngtd vald: https://github.com/vdaas/vald n 共有メモリ（マップドメモリ）版でメモリサイズ以上のデータ登録可能 n 量子化版NGT（NGTQ）により、さらなる大規模化が可能 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例近傍検索ベンチマーク -ANN benchmarksANN benchmarks n Dockerにより独立した動作環境 n AWSのEC2 c5.4xlargeで実行 ANN benchmarks NGT python API NGT Ubuntu Docker Linux AWS EC2 c5.4xlarge Ann benchmarks: https://github.com/erikbern/ann-benchmarks Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. Containers NGT faiss hnsw n 多種多様なデータセット（全10セット） Annoy n Annoy, Faiss, HNSWなど主要21種を網羅 annoy n 近傍検索専用のベンチマーク

https://github.com/erikbern/ann-benchmarks

10.

11.

12.

13.

14.

15.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例ツリーの生成 n グラフの探索起点の取得に利用 n 超球を用いた空間分割によるツリー(DVP-tree)の生成 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. DVP-tree: 岩崎, 類似画像検索を実現する距離空間インデックスの実装及び評価, 情報処理学会論文誌データベース（TOD） 40(SIG03(TOD1)), 24-33, 1999

16.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例グラフの生成 n 逐次ノードを追加し近傍オブジェクト同士を接続 n 近傍ノードの検索に生成中のインデックスを利用 ANNG Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. Approximate k-Nearest Neighbor Graph

17.

18.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例近傍検索 1. ツリーをたどりクエリの近傍オブジェクトを探索起点として取得 2. 探索起点からグラフを探索 1回の距離計算で下位部分空間の特定が可能 3最近傍検索 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. 参考： https://techblog.yahoo.co.jp/lab/searchlab/ngt-docs-2/ https://techblog.yahoo.co.jp/lab/searchlab/ngt-docs-3/

19.

20.

21.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例 ONNGの生成 Optimized Nearest Neighbors Graph 有向エッジとしてANNGを最適化 n ノード単位の入次数、出次数の最適化 n パスを考慮した出次数の削減 n 検索時の参照エッジ数調整出次数：2 入次数：4 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

22.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例ノード単位の入次数、出次数の最適化 n 入次数の引き上げと均一化入次数が少ないと到達確率が減少 →引き上げと均一化により到達確率の底上げ n 出次数の削減出次数は重い距離計算回数に直結 →出次数の削減により探索時間の削減 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

23.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例ノード単位の入次数、出次数の最適化出次数調整：３ ⑥ ② ⑦ ② ③ ① ④ ⑤ 出次数：３入次数：６ ① ⑥ ② ④ ③ ⑥ ANNG （出力エッジに着目） ② ⑥ ④ ⑤ 入次数調整：６ Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. ② ⑤ ONNG ④ ① ③ ⑤ ① ① 全ノードに適用 ③ ③

24.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例ノード単位の入次数、出次数の最適化検索時間 n 最適な入出次数は？ • データセットに強く依存 • 最適次数の探索が必要 n 多くのデータセットに有効な次数入次数：120、出次数：10 入次数出次数（次元数が少ない場合など入次数の削減可能） ONNGの入出次数と検索時間の関係 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

25.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例パスを考慮した出次数の削減 n ツリーによりクエリ近傍に到達可能 n 長いショートカットエッジは不要 nd nd nd e2 e1 e3 n1 ns ns e1削除 n3 n2 代替パスに複数のノード e3削除せず e4 クエリ e5 ns n4 代替パスのノードn4が遠方 e4削除せずグラフ全体にパスの最適化を適用 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. re

26.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例検索時の参照エッジ数調整 n 精度が低くてもよい時は参照エッジ数（出次数）が少ない方が良い n 精度は探索範囲係数εで決定 n 参照エッジ数を探索範囲係数εから算出探索範囲 rs=(1+ε)r 参照エッジ数： we, e0はデータセットに強く依存インデックス生成時にwe, e0の最適化を実行 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. 検索範囲

27.

28.

29.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例 Yahoo!ラボ FavNavi n 研究所と社内有志でスタートして研究開発したファッション検索実験アプリ n ファッション検索の基盤技術をサービスへ提供アプリの特徴 • Yahoo!ショッピングのファッション商品検索 • 検索対象領域表示 • 商品以外のアイテムで検索可能 • 撮影画像による検索（近日公開予定） https://apps.apple.com/jp/app/favnavi/id1478926680 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved.

https://apps.apple.com/jp/app/favnavi/id1478926680

30.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例類似ファッション検索アプリ n Yahoo!ショッピング回遊型類似ファッション検索 n Yahoo!ブラウザー撮影画像によるファッション検索写真：アフロ https://commerceapp.yahoo.co.jp/shoppingappli/ Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. https://promo-ybrowser.yahoo.co.jp/

31.

32.

33.

34.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例特徴量の構成領域画像 n 低次特徴量：色やテクスチャをtripletで学習 n カテゴリ特徴量：商品カテゴリで学習 n 領域アスペクト比低次特徴量抽出低次特徴量カテゴリ特徴量抽出カテゴリ特徴量 300 統合特徴量 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. 429次元領域アスペクト比 128 1

35.

36.

37.

世界最速クラスのベクトル近傍検索NGTと深層学習によるファッション検索への応用事例学習データによるモデル生成モデル画像種別物体検出ヤフオク！ Yahoo!ショッピング 50,000件 20,000件低次特徴量 Yahoo!ショッピング 8,000,000件カテゴリ特徴量 Yahoo!ショッピング 400,000件物体検出のアノテーションデータは手作業で生成 Copyright© 2019 Yahoo Japan Corporation. All Rights Reserved. 画像数

38.

39.