近傍検索ライブラリNGTと深層学習による類似ファッション検索 #yjbonfire
2K Views
November 05, 19
スライド概要
bonfire data&science #1 イベントで，ヤフーの類似画像検索について紹介した。NGTと呼ばれる大量の高次元ベクトルデータからクエリとして指定されたベクトルデータの近傍に存在するデータを高速に検索するソフトウェアについて詳しく触れられている。
2023年10月からSpeaker Deckに移行しました。最新情報はこちらをご覧ください。 https://speakerdeck.com/lycorptech_jp
関連スライド
各ページのテキスト
近傍検索ライブラリNGTと 深層学習による類似ファッション検索 2019年11月5日 1 Yahoo! JAPAN研究所 岩崎 雅二郎 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
自己紹介 岩崎 雅二郎 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.
内容 l 近傍検索ライブラリNGT • ベンチマークによる検索性能 • インデックスの生成と検索 • 高性能な検索を実現する最適化グラフの生成方法 l NGTを用いた深層学習による類似ファッション検索 • • • • 3 類似ファッション検索アプリの紹介 インデックスの生成と検索 特徴量の構成と検索結果 モデル生成用学習データ C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
近傍検索ライブラリNGT 4 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
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 ⑦ l k最近傍検索 l 範囲検索 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
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.
NGTの性能 8 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
近傍検索ベンチマーク -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.
ベンチマーク結果① 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
ベンチマーク結果② 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.
ベンチマーク結果③ 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
ベンチマーク結果③ 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 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
ツリーの生成 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.
グラフの生成 l 逐次ノードを追加し近傍オブジェクト同士を接続 l 近傍ノードの検索に生成中のインデックスを利用 ANNG 16 Approximate k-Nearest Neighbor Graph C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
近傍検索 17 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
近傍検索 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 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
ANNGの課題 エッジを減らすと エッジを増やすと 検索精度低下⤵ 検索精度向上⤴ 検索時間減少⤴ 検索時間増加⤵ 両立困難 20 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
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
ノード単位の次数の最適化 l 入次数の均一化 • 入次数が少ないと到達確率が減少 • 均一化により到達確率の底上げ l 出次数の削減 • 出次数は重い距離計算回数に直結 • 出次数の削減により探索時間の削減 22 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
ノード単位の次数の最適化 出次数調整：３ ⑥ ② 出次数：３ 入次数：６ ⑦ ② ③ ① ⑥ ④ ⑤ ① ③ ANNG （出力エッジに着目） ④ ⑥ ② ⑥ ④ ② ⑤ 入次数調整：６ ① ③ ⑤ ① ONNG ④ ⑤ 23 ② ① 全ノードに適用 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. ③ ③
ノード単位の次数の最適化 • 最適な次数は？ • データセットに強く依存 • 最適次数の探索が必要 • 多くのデータセットに有効な次数 入次数：120、出次数：10 （次元数が少ない場合など入次数の削減可能） 24 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 出次数 入次数
パスを考慮した出次数の削減 • ツリーによりクエリ近傍に到達可能 • 長いショートカットエッジは不要 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.
検索時の参照エッジ数調整 参照エッジ数（出次数）を指定範囲係数εから算出 参照エッジ数： 探索範囲 rs=(1+ε)r we, e0はデータセットに強く依存 インデックス生成時にwe, e0の最適化を実行 26 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 検索範囲
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
NGTを利用した深層学習による 類似ファッション検索 28 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
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.
Yahoo!ショッピング ショッピング内回遊型類似ファッション検索 30 https://commerceapp.yahoo.co.jp/shoppingappli/ C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
Yahoo!ブラウザー 撮影画像による類似ファッション検索 写真：アフロ https://promo-ybrowser.yahoo.co.jp/ 31 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
類似ファッション検索の 処理の流れ 32 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
インデックスの構築 検出された領域ごとに特徴量を抽出してNGTに登録 検出領域 特徴量 物体検出 特徴量抽出 登録商品画像 Yahoo!ショッピング 33 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. NGT
類似画像検索 選択された領域の特徴量でNGTを検索 特徴量 物体検出 選択 特徴量抽出 クエリ画像 （撮影画像） 34 領域検索結果 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 検索 NGT
特徴量の構成 l 低次特徴量：色やテクスチャをtripletで学習 l カテゴリ特徴量：商品カテゴリで学習 l 領域アスペクト比 低次特徴量抽出 カテゴリ特徴量抽出 低次特徴量 300 35 領域画像 領域アスペクト比 カテゴリ特徴量 128 統合特徴量 429次元 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 1
検索結果比較① 低次特徴量（300次元） 36 カテゴリ特徴量（128次元） C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 統合特徴量（429次元）
検索結果比較② 低次特徴量（300次元） 37 カテゴリ特徴量（128次元） C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved. 統合特徴量（429次元）
モデル生成用学習データ モデル 画像種別 画像数 物体検出 ヤフオク！ 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.
最後に l 深層学習によりベクトルの生成が容易に l 世界トップレベルのNGTを利用して是非 フィードバックを！ 39 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.
40 C opyright © 2019 Y ahoo Japan C orporation. A ll R ights R eserved.