---
title: 近傍検索ライブラリNGTと深層学習による類似ファッション検索 #yjbonfire
tags:  #yjbonfire  
author: [Yahoo!デベロッパーネットワーク](https://www.docswell.com/user/ydnjp)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/5G75N948J4.jpg?width=480
description: bonfire data&amp;science #1 イベントで，ヤフーの類似画像検索について紹介した。NGTと呼ばれる大量の高次元ベクトルデータからクエリとして指定されたベクトルデータの近傍に存在するデータを高速に検索するソフトウェアについて詳しく触れられている。
published: November 05, 19
canonical: https://www.docswell.com/s/ydnjp/5NQPR5-2019-11-05-122725
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/5G75N948J4.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/V9J252VVJR.jpg)

自己紹介
岩崎 雅二郎
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.


# Page. 3

![Page Image](https://bcdn.docswell.com/page/5DEYKY3Q7M.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/2VJNRPV2E8.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/GYE9M36DJ3.jpg)

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.


# Page. 6

![Page Image](https://bcdn.docswell.com/page/5GE8LMZ5JD.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/MLELL3D3ER.jpg)

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.


# Page. 8

![Page Image](https://bcdn.docswell.com/page/54JMMDPMJW.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/ZPJRV41LE9.jpg)

近傍検索ベンチマーク -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.


# Page. 10

![Page Image](https://bcdn.docswell.com/page/NPEXZ2G6JX.jpg)

ベンチマーク結果①
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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/63EK8M4GJD.jpg)

ベンチマーク結果②
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.


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4L732YL5E5.jpg)

ベンチマーク結果③
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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/V87DZ5NYJG.jpg)

ベンチマーク結果③
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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/4VJPDG52J8.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/L2EV16PXJQ.jpg)

ツリーの生成
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.


# Page. 16

![Page Image](https://bcdn.docswell.com/page/Z57G2NPR7L.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/V4EQPQ2YJP.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/DKJ4YNLZE1.jpg)

近傍検索
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/


# Page. 19

![Page Image](https://bcdn.docswell.com/page/PLE165LDJG.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/8GEWW5V8E2.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/W47Z5N49E3.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/KYJ6983DJV.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/5GJ5N9L8E4.jpg)

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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/4LE32YLGJ5.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/V8EDZ5NN7G.jpg)

パスを考慮した出次数の削減
• ツリーによりクエリ近傍に到達可能
• 長いショートカットエッジは不要
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.


# Page. 26

![Page Image](https://bcdn.docswell.com/page/4V7PDG5N78.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/L2JV16PY7Q.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/Z5EG2NPWEL.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/V4JQPQ2Q7P.jpg)

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.


# Page. 30

![Page Image](https://bcdn.docswell.com/page/DK74YNLYJ1.jpg)

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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/PLJ165LN7G.jpg)

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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/8GJWW5QMJ2.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/W4EZ5NWMJ3.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/KY7698G57V.jpg)

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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/5G75N9VGJ4.jpg)

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


# Page. 36

![Page Image](https://bcdn.docswell.com/page/V9J2523DJR.jpg)

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


# Page. 37

![Page Image](https://bcdn.docswell.com/page/5DEYKY1M7M.jpg)

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


# Page. 38

![Page Image](https://bcdn.docswell.com/page/2VJNRP23E8.jpg)

モデル生成用学習データ
モデル
画像種別
画像数
物体検出
ヤフオク！
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.


# Page. 39

![Page Image](https://bcdn.docswell.com/page/GYE9M31PJ3.jpg)

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


# Page. 40

![Page Image](https://bcdn.docswell.com/page/5GE8LM4XJD.jpg)

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


