Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report

Sanny: 大規模 EC サイトのための精度と速度を両立した
分散可能な近似近傍探索エンジン
三宅 悠介1,a)

松本 亮介1,b)

概要：EC サイトの商品種類増大に伴う情報過多問題を解決するため，利用者の要求を満たす商品を自動的に提案する機能が EC サイトにとっての関心事となる．大規模 EC サイトで商品を提案するために扱う
特徴量は大規模かつ高次元ベクトルの集合となるため，類似度の比較は精度と計算量を抑えた近似解を用いなければならない．商品を自動的に提案する機能には、可用性を担保しつつ，提案内容の的確さと充分な応答速度が求められる．本報告では，大規模 EC サイトで商品を提案することを想定して，精度と速度を両立した分散可能な近似近傍探索エンジン Sanny を提案する．Sanny は，検索質問データ (クエリ) に対する高次元ベクトル集合の近傍探索結果の上位集合が，クエリと高次元ベクトル集合を任意の次元数で等分した部分ベクトル単位で近傍探索した結果と類似しやすいことに着目して，提案すべき商品の近傍探索を部分ベクトル単位での探索に分解することで分散処理可能にし，その探索結果の和集合である近傍候
補から再度近傍探索を行うことにより，全体として高速に近似近傍探索を行える．実験では，従来の近似近傍探索に対する速度並びに精度面での性能比較について評価を行う．

Sanny: Scalable Approximate Nearest Neighbors Search System Using
Partial Nearest Neighbors Sets
Yusuke Miyake1,a)Ryosuke Matsumoto1,b)Abstract: Building a recommendation system has become a big concern to solve the information overload
problem of the electronic commerce sites. Implementing a feature selection system based on machine learning requires approximation of the nearest neighbor search for maintaining the availability and speed whileallowing to reducing the accuracy and complexity since the feature sets consist of large and high dimensional
vectors. In this report, we propose Sanny, a search engine by approximation of nearest neighbors and using
the partial neighbor set. Sanny aggregates the neighbors of the low dimensional vectors using the property
that the neighbors of high dimensional vectors obtained from the neural network overlap with the neighborsof partial vectors. Sanny searches the candidates generated by the aggregation, which results in reducing
the total time of searching. We evaluate performance and accuracy comparison of Sanny with the existing
methods.

1. はじめに案は商品同士の類似性を根拠とすることから，商品を自動的に提案する機能では，商品の特性を機械的に扱えるよう

EC サイトの商品種類増大に伴う情報過多問題を解決す

数値化し距離空間における近傍集合を求める．この数値化るため，利用者が興味を持つであろう商品を自動的に提案した商品特性を特徴量と呼び，一般に多次元ベクトルとしする機能が EC サイトにとっての関心事となる．商品の提て表現される．深層ニューラルネットワークの発展によって，これまで適切な特徴量を導くことが難しかった画像や

1

a)
b)

GMO ペパボ株式会社 ペパボ研究所
Pepabo R&D Institute, GMO Pepabo, Inc., Tenjin, Chuo
ku, Fukuoka 810-0001 Japan
miyakey@pepabo.com
matsumotory@pepabo.com

c 2018 Information Processing Society of Japan
⃝

テキストに対しても，人の感性に近い，特性をよく表現する
高精度な特徴量を得られるようになったことから [4], [16]，これらの深層ニューラルネットワークから得られる数百か

1Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report

ら数千次元の高次元ベクトルである特徴量が EC サイトの

本報告の構成を述べる．2 章では EC サイトの商品提案

商品提案機能に利用され始めている [20], [21]．また，数十機能で利用する特徴量について整理し，これらを利用した

万から数百万件の商品を扱うような大規模な EC サイトで近似近傍探索の課題を整理する．3 章では，近似近傍探索は，特徴量の集合の要素数も，扱う商品数に比例して大規エンジンの実装について述べる．4 章では提案手法の評価

模なものとなっている．このような大規模 EC サイトにおを行い，5 章でまとめとする．

ける商品を自動的に提案する機能では，大規模かつ高次元ベクトルな集合に対して，提案内容の的確さと充分な応答速度を両立しながら可用性の担保が求められる．

2. 従来手法の課題
2.1 EC サイトの商品提案機能で利用する特徴量

商品提案機能における近傍集合の探索において，精度とEC サイトの商品提案機能では推薦根拠として，利用者速度の両立の観点から，正確ではあるがデータ数と次元数

間，商品間の相関や商品の特徴を表現する属性情報などをに比例して計算量が増加する線形探索の利用は現実的でな利用する．商品の提案は任意の観点での商品同士の類似性い．そこで，精度を犠牲にして近似解を用いることで計算を根拠とすることから，これらの情報源を機械的に扱える量の増加に対処する近似近傍探索の手法が提案されている

よう数値化し，任意の距離空間で近傍に位置する商品を求が [1], [15], [19]，各手法の想定するデータ数や次元数を超める．この数値化した商品特性を特徴量と呼び，一般に多えた大規模かつ高次元ベクトルな集合に対しては，精度と次元ベクトルの形で表現する．

探索速度の両立が困難になる．このようなデータ数と次元

EC サイトの商品提案機能では，相関情報の元となる評数の増加に伴う近似近傍探索の性能劣化に対処するため，価や購買履歴が不足している状況で，推薦精度が低下した

探索対象を分割する手法が用いられる．探索対象のベクト

り推薦対象に含まれないといった問題が発生する．この，ル集合を行方向に分割し，各部分ベクトル集合の近傍探索

いわゆるコールドスタート問題 [8] を回避するため，評価結果を近傍候補とする手法 [13] では，次元数の増加に伴うや履歴の蓄積に依存しない商品画像や説明文などの属性情課題が残る．一方，列方向の分割 [10] では，検索質問デー

報を用いた内容ベース型推薦を組み合わせて利用する [2]．

タ (クエリ) を同様に分割し各部分ベクトル集合における

深層畳み込みニューラルネットワークを始めとする深層距離計算の一部を並列して求め，これをまとめる．しかし学習の発展 [4], [16] により，これまで適切な特徴量を導くながら，最終的な距離計算量はデータ数に比例することかことが難しかった画像に対しても，人の感性に近い，特性

ら，列方向の分割による探索速度の改善は限定的となる．

をよく表現する高精度な特徴量を得られるようになった．

また，EC サイトにおいて応答速度の低下が販売の機会

畳み込みニューラルネットワークは，画像の局所領域の特損失につながるため [6]，商品提案機能には安定した応答

徴抽出を行う畳み込み層と，抽出した特徴を縮小し，位置速度の確保が求められる．そこで，可用性の観点から同一感度を低下させるプーリング層を繰り返すネットワーク構

データを保持する近似近傍探索機能を持つサーバを複数台造を持つ [5], [9], [12]．また，この層を多層にすることでよ用意することで負荷分散する手法が用いられるが，処理能り精度を向上させたものを深層畳み込みニューラルネット

力がサーバ台数に依存してしまう．サーバ障害時においてワークと呼ぶ．学習済みの深層畳み込みニューラルネットも安定した応答速度を確保するためには，影響を局所化しワークの上位層から得られる特徴量が，画像内容をよく表処理能力の低下を最低限に留める必要がある．

現することが示されており [11]，これらの特徴量が画像をそこで，本報告では，大規模 EC サイトで商品を提案することを想定して，精度と速度を両立した分散可能な近似用いた内容ベース型推薦の情報源として利用され始めている [20], [21]．

近傍探索エンジン Sanny を提案する．筆者らは，商品特性

また，商品説明文を始めとするテキストによる内容ベーをよく表現しており高精度に類似度が比較可能な高次元かス型推薦では，従来の単純なキーワード検索や TF-IDF 尺

つ密なベクトルの集合において，クエリに対する高次元ベ度による類似度比較で生じる単語の重要度や文脈が考慮さ

クトル集合の近傍探索結果の上位集合が，クエリと高次元れない課題を解決するため，前後の出現単語やパラグラフ

ベクトル集合を任意の次元数で等分した部分ベクトル単位を考慮して学習を行うことで特徴表現の精度を向上させる

で近傍探索した結果の上位集合と類似しやすいことに着目

Word2vec や Doc2vec などのモデルベースの手法 [14], [18]した．これにより，提案すべき商品の近傍探索を部分ベクが利用されている．

トル単位での探索に分解することで分散処理可能にし，そこれらの深層畳み込みニューラルネットワークやの探索結果の和集合である近傍候補から再度近傍探索を行

Word2vec によって出力される特徴量は，入力となる画

うことにより，全体として高速に近似近傍探索を行う．ま

素値や単語リストからなる多次元の特徴量からは次元数がた，近似近傍探索処理は，列方向で分割した部分ベクトル削減されているものの，数百から数千次元の高次元ベクト

集合単位になることから，障害時の影響は近傍候補の減少

ルとなる．加えて，数十万から数百万件の商品を扱うようのみに留めることが可能となる．

な大規模な EC サイトでは，特徴量の集合の要素数も，扱c 2018 Information Processing Society of Japan⃝2

Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report

う商品数に比例して大規模なものとなっている．商品を自としてデータ数の増加に伴う性能劣化の課題は残る．

動的に提案する機能では，提案内容の的確さと充分な応答

また，列方向へ圧縮する手法として，主成分分析 [17] を速度が求められることから，このような大規模かつ高次元始めとする次元削減の手法が用いられる．これらの手法でベクトルな集合に対して精度と速度を両立する近傍探索のは情報量を損なわないよう表現に必要な特徴量の次元数

手法が必要となる．

を削減することで，次元数増加に対処する．しかしながら次元削減に伴う精度低下は避けられないため，充分な精度

2.2 従来の近似近傍探索の課題
2.1 節で述べた大規模かつ高次元ベクトルな集合に対しも求められる EC サイトの商品提案機能では削減に限界がある．

て，正確ではあるがデータ数と次元数に比例して計算量がそのため，従来の近似近傍探索の課題を解決するために増加する線形探索の利用は現実的でない．そこで，事前には，各手法の想定するデータ数や次元数に探索対象を抑え近傍候補となる集団を求めておくことで，少数の近傍候補

ながらも分割結果の集約においてデータ数に依存しない方から計算量を抑えて近傍点を得る空間分割や局所性鋭敏型式が求められる．

ハッシュといった手法が用いられる．しかしながら，高次元ベクトル集合においては正確な近傍を求めるための近傍

2.3 EC サイトにおける近似近傍探索機能の課題

候補を求める計算量が線形探索と同程度となると考えられここまで述べたように，EC サイトにおける商品提案機ており [22]，精度を犠牲にして近似解を用いることで計算能には，推薦根拠となる商品特性を特徴量とした大規模か量の増加に対処する近似近傍探索の手法が利用されていつ高次元ベクトルな集合に対する近似近傍探索が必要となる [1], [15], [19]．だが，近似近傍探索は精度と探索速度がる．利用者の効率的な閲覧を補助する商品提案機能には，

トレードオフ関係にあることから，各手法のアルゴリズム

提案内容の的確さと充分な応答速度が求められる．これらが想定するデータ数や次元数を超えた大規模かつ高次元ベの性能低下は販売の機会損失につながるため，可用性の観

クトルな集合に対しては，精度と探索速度の両立が困難に点から同一データを保持する近似近傍探索機能を持つサーなる．

バを複数台用意することで負荷分散する手法が用いられ

データ数と次元数の増加に伴う近似近傍探索の性能劣化る．一方で，計算資源の有効利用の観点から，EC サイトに対処するため，探索対象を分割することで，各手法の想から求められる近似近傍探索の処理能力は負荷分散構成を定するデータ数や次元数に収める手法がある．この場合，前提としたものとなり，処理能力がサーバ台数に依存して分割された対象ごとの探査結果または距離計算の結果が集しまうことから，サーバ障害時において，処理能力の低下

約され，元のクエリに対する近傍集合が最終的に求められが懸念される．サーバ障害時においても安定した応答速度る．このような手法として，集合のベクトルを行に，ベクを確保し，EC サイトにおける機会損失を回避するためにトルの持つ各次元を列とする行列とみなした場合，行方向は，障害時の影響を局所化し処理能力の低下を最低限に留での分割と列方向での分割の二種類がある．

める必要がある．

行方向での分割では，クエリに対する近傍探索は分割された部分ベクトル集合ごとに行われる．各部分ベクトルの

3. 提案手法

集合からの探索結果が近傍候補であり，これらの集合から2 章で述べた，大規模 EC サイトの商品提案機能におけ元のクエリに対する近傍集合が求められる．この時，各近る大規模かつ高次元ベクトルな集合に対する近似近傍探索

傍候補とクエリ間の距離は算出済みであるため，距離によに関する課題を解決するためには，以下の要件を満たす必る並び替えのみが行われる [13]．行方向での分割は，各部要がある．

分集合に対する探索は独立していることから分散処理が可( 1 ) 近似近傍探索の精度と速度を両立するため，アルゴリ

能であるため，データ数に対する性能劣化への対処としてズムの想定するデータ数と次元数に収まるよう探索対は有効だが，高次元ベクトル集合に対する解とはならない．

象を分割し，データ数に依存しない集約が行える．

直積量子化 [10] は，探索対象の高次元ベクトル集合を列( 2 ) 近似近傍探索の可用性を担保するため，分散構成にお方向に分割することで，独立した低次元ベクトル集合に対ける障害時の影響が局所化されている．

する距離計算の問題に分解する．近傍探索時は，クエリを筆者らは商品特性をよく表現しており高精度に類似度が同様に列方向に分割し，対応する部分ベクトル集合に対し比較可能な高次元かつ密なベクトルの集合において，クエて距離計算を行い，その和をとる．この手法では，高次元リに対する高次元ベクトル集合の近傍探索結果の上位集合

ベクトル集合に対する性能劣化への対象として有効だが，が，クエリと高次元ベクトル集合を任意の次元数で等分し近傍集合を求めるための計算量はデータ数に比例してしまた部分ベクトル単位で近傍探索した結果の上位集合と類似う．転置インデックスの利用によりデータ数に対する計算しやすい特性があることを見出した．このような集合とし量の増加を抑える方法も合わせて提案されているが，依然て 2.1 節で述べた，学習済み深層畳み込みニューラルネッ

c 2018 Information Processing Society of Japan⃝3

Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report

トワークを特徴抽出器として利用して画像から得られる特徴量集合や，テキストを分散表現へ変換する Word2vec のネットワークから得られる特徴量集合がある．このような部分が類似しているものは全体としても類似する可能性が高いという特性のベクトル集合に対しては，列方向に分割
した部分ベクトル単位での探索に分解し，その探索結果の和集合である近傍候補から再度近傍探索を行うことにより，全体として高速に近似近傍探索を行える．また，部分
ベクトル集合単位に分散可能な構成であることから，一部

図 1 Sanny の処理フロー

Fig. 1 Process flow of Sanny.

の部分ベクトル集合からの近傍候補が得られずとも探索速度を落とさずに近似近傍探索の機能を継続することができ
る．以降の節では，提案手法を用いた具体的な探索処理を処理フローを図 1 に示す．
提案手法は以下の 3 点の工程を要しており，各工程の実行時間を短縮することで，全体として高速な近似近傍探索

説明する．

が可能となる．

( 1 ) 各部分ベクトル集合での近傍探索

3.1 探索対象となるベクトル集合の分割
ここでは，対象となるベクトル集合を Y ⊂ RD と置く．
∗

これを D = D/m 次元の部分ベクトル集合 Sj (1 ≤ j ≤ m)に等分する．なお，部分ベクトル集合の持つ要素は各集合( 2 ) 各近傍探索結果を近傍候補として集約( 3 ) 固定数の近傍候補から線形探索
ここで，(1) 工程では各部分ベクトル集合は独立しており，並列に近傍探索を行うことができる．各部分ベクトル間で重複しないものとする．

集合は元のベクトル集合に比べて低次元のベクトル集合に対する近傍探索となることから次元数に依存する計算量が3.2 近似近傍探索
ベクトル集合 Y に対する近似近傍探索は次のように行削減され，並列処理によって全体として探索処理時間が削う．はじめに，クエリベクトル q ∈ RD を qj (1 ≤ j ≤ m)

減される．また，(2) と (3) 工程では元のベクトル集合に比に等分し，対応する添え字 j の部分ベクトル集合 Sj に対べて小規模かつ固定数の近傍候補に対して線形探索を行う

して上位 n 件を得る近傍探索を行う．

ため，探索時間は短くなるが，Sanny では線形探索処理を簡略化または並列化することで高速化する．線形探索処理の近似には，(3) 式を用いる．ここでは，距離関数はユー

N N (qj ) = arg min d(qj , s)

(1)

s∈Sj

ここで，距離関数 d にはユークリッド距離を想定していクリッド距離とし，a を探索対象のベクトル，b をクエリベクトルとする．

る．なお，各部分ベクトル集合における近傍探索の手法はargmina (a − b)2 = argmina a2 − 2ab + b2

問わない．

= argmina a2 − 2ab

次に，各部分ベクトル集合に対する (1) 式で得られた

N N (pj ) の結果を n 個の識別子からなる集合 Nj とし，全ての Nj の和集合を N としてこれを近傍候補とする．
最後にベクトル集合 Y のうち，近傍候補 N に対応する
ベクトル集合 Y N ⊂ RD に対して正確な類似度を比較する
ために元のクエリベクトル q との線形探索を行う．

(3)

b はクエリベクトルであり，全てのベクトル集合に対する計算において b2 は同じ値となることから省略することができる．また a2 はクエリベクトルに依存しないため，ベクトル集合が与えられた際に事前に求めておくことができる．このため線形探索時には 2ab を求め，事前算出済みの

a2 に対する減算のみ必要となる．また，線形探索処理を
N N (q) = arg min d(q, yn)(2)

実行する端末の CPU が Single Instruction Multiple Datayn∈Y N(SIMD) 演算に対応している場合，ユークリッド距離を求

ここで，|Y N | は最大 n ∗ m 個であり，(2) 式における線

める積和演算においてベクトルの複数次元に対して同時計

形探索の計算量はデータ数に依存しない．

算ができるため，Sanny ではこれに対応することで線形探索の高速化を図った．

3.3 提案手法の実装
上述の提案手法に対し，筆者らは探索速度を考慮した実装である Sanny*1 を開発，OSS として公開した．Sanny の*1

https://github.com/monochromegane/sannyc 2018 Information Processing Society of Japan
⃝

4. 評価と考察
4.1 データ特性による有効性の評価
提案手法が有効なデータ特性を検証するため，複数の4

Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report

データセットに対して提案手法を適用した．本報告では，

表 1 提案手法による適合率

データ数が 6 万件の各データセットを 4 つの部分ベクトル

Table 1 Precision by proposed method.

集合に分割し提案手法による上位 10 件の近傍集合に対す
データセット

部分 1

部分 2

部分 3

部分 4

提案手法

Inception-v3

0.57

0.37

0.50

0.65

0.97

Word2vec

0.67

0.68

0.68

0.69

0.97

Fashion-MNIST

0.10

0.23

0.31

0.16

0.63

る 5 つのデータセットについて述べる．一つ目は，画像を

一様乱数

0.05

0.05

0.05

0.05

0.18

高次元密ベクトルの特徴量に変換する深層畳み込みニュー

正規分布

0.05

0.04

0.04

0.04

0.17

る適合率を確認する．なお，部分ベクトル集合に対する近傍探索は線形探索を採用し，部分ベクトル集合からの上位

30 件の近傍集合を近傍候補として利用した．評価対象とな

ラルネットワークのモデルの一つである Inception-v3[3] のうち，ImageNet の画像群で学習済みのモデルから得られたデータセットである．このモデルから得られる特徴量は 2048 次元のベクトルであり，EC サイトのプロダクショ
ン環境の商品提案機能で利用している商品画像のうち，6万件を評価対象とした．二つ目は，単語を高次元密ベク
トルの分散表現に変換する Word2vec のうち，日本語版

Wikipedia を用いて学習済みのモデル*2 から得られたデー
タセットである．このモデルから得られる特徴量は 200 次
元のベクトルであり，利用可能な単語のうち 6 万件を評価対象とした．三つ目は，機械学習ベンチマークで利用される Fashion-MNIST*3 である．28x28 のグレースケール画像
であり，786 次元の疎なベクトル集合である．提供されている 6 万件を評価に利用した．残り二つのデータセットは乱数を用いた．各次元の値を一様または正規分布に従う乱数とし，200 次元で 6 万件のデータセットとした．
各データセットに対する提案手法による適合率の比較を表 1 に示す．乱数を元にしたデータセットと比較して，画像を元にした Inception-v3，日本語の単語を元にした

図 2 2048 次元のデータセットにおける適合率と部分集合ごとの近傍数のトレードオフ評価

Fig. 2 Precision-Number of neighborhoods tradeoﬀ.

Word2vec や服飾画像から成る Fashion-MNIST のデータセットが提案手法の精度が高い．また，画素値を元にした

傍数であり，20 件から 1000 件までの評価結果を対数表示

疎なベクトル集合である Fashion-MNIST データセットよしている．縦軸は適合率を表す．提案手法では，分割数をりも，密なベクトル集合である Inception-v3 や Word2vec

増加すると同一近傍数において精度が下がる関係にある

データセットが精度が高い．これらから，元の情報が意味ことが分かる．また，各データセットでの分割後の次元数や特性を表現し得る情報を持っており，高次元かつ密ベク

が 100 以下になると精度の落ち込みが大きく，データ数のトルで表現される特徴量から成るデータが提案手法の前提

0.1%を超える近傍数が必要になることから，速度と精度をとする特性を持つと推測される．

両立する近似近傍探索のためには，これらの分割数内で最提案手法では，部分ベクトルごとの次元数と，部分ベク

適な近傍数を求めることが必要になることが分かる．

トルごとに得られる近傍集合の数が少ないほど，個別の近傍探索ならびに結果の集約処理が高速になる．一方で，分

4.2 精度並びに速度に関する評価

割数を増やすことで部分の類似と全体の類似の関係性が提案手法による精度並びに探索速度の改善を検証するた

薄れることが想定された．そこで，分割数と部分ベクトル

め，4.1 節で評価したデータセットのうち，提案手法が有ごとの近傍数による適合率の変化を検証した．検証は，先効で大規模かつ高次元ベクトルな集合であった商品画像をの検証で提案手法の有効性が見込めるデータセットとし元にした特徴量に対する評価を行なった．

て，画像を元にした Inception-v3，日本語の単語を元にし

本報告では，近似近傍探索の精度と速度の両立を評価す

た Word2vec から得られる特徴量を用いた．データセット

るため，クエリベクトルに対する上位 10 件の近傍集合のの件数はそれぞれ，約 95 万件と約 100 万件である．結果適合率と探索速度を計測する．評価対象となるベクトル集をそれぞれ図 2 と図 3 に示す．横軸は部分集合ごとの近合からランダムに選択した 500 件をクエリベクトルとし，*2*3

http://www.cl.ecei.tohoku.ac.jp/˜m-suzuki/jawiki vector/
https://github.com/zalandoresearch/fashion-mnistc 2018 Information Processing Society of Japan⃝

残りのベクトル集合から近傍探索を行う．また，評価対象の手法には，近傍探索アルゴリズムである空間分割を利用

5

Vol.2018-IOT-42 No.2
2018/6/28

情報処理学会研究報告
IPSJ SIG Technical Report
表 2

手法ごとの近傍探索パラメタ

Table 2 Parameters of nearest neighbors search.
手法

パラメタ

Annoy

Tree
SearchK

100〜400000
0〜80

Edge

LSH

Hash table size

20

Hash value size

20

Slot size

5.0

Split

8

Top

20〜100Tree

100〜400

SearchK
Sanny-NGT

200 次元のデータセットにおける適合率と部分集合ごとの近傍

100〜400

NGT

Sanny-Annoy

図3

値

Sanny-LSH

数のトレードオフ評価

Fig. 3 Precision-Number of neighborhoods tradeoﬀ.

したライブラリの Annoy[19]*4 ，NGT[15]*5 ，そして局所

100〜400000

Split

8

Top

20〜100

Edge

0〜80

Split

8

Top

20〜100Hash table size

20

Hash value size

20

Slot size

5.0

性鋭敏型ハッシュを利用した LSHForest[1]*6 を用いる．これらの手法を従来通り利用したものと，提案手法における部分ベクトル集合単位での近傍探索アルゴリズムとして利用した場合における性能改善を検証した．各手法ごとの近傍探索のパラメタを表 2 に示す．なお，LSHForest については，アルゴリズム特性上，多くのメモリを使用することから検証機の制限上，実時間で検証が終わるパラメタによる検証に留めている．評価方法は近似近傍探索ライブラリのベンチマークである ann-benchmarks*7 で比較可能とするため，同様の方法で結果を取得した．具体的には，評価手法ごとに近似近傍探索の挙動を調整するためのパラメタを変えながら，全クエリによる近傍探索を 3 回実行し，適合率は平均，探索速度には最小のものを採用している．
評価結果を図 4 に示す．X 軸は適合率で右に向かうほど精度が高い．Y 軸は探索速度の逆数を表しており上に行くほど速い探索が行われたことを示している．なお，複数の探索が同一の適合率となる場合は速度が速いものを図示している．提案手法の適用により従来手法と比較して，同程度の精度での探索時間短縮，または頭打ちとなっていた精

図 4 適合率と探索速度のトレードオフ評価

Fig. 4 Precision-Query per second tradeoﬀ.

5. まとめ度が向上するといった性能の改善が確認できた．これらは本報告では，大規模 EC サイトで商品を提案するために提案手法の適用によって，元のベクトル集合よりも低次元扱う大規模かつ高次元ベクトルな集合に対して，精度と速な空間が対象となることで，より多くの近傍候補を短時間度を両立した分散可能な近似近傍探索エンジン Sanny を提で探索できるようになったためである．また，従来手法で案した．商品の提案機能で利用される商品画像や説明文をは高次元ベクトル集合に対する精度の限界についても複数情報源とするニューラルネットワークから得られる特徴量の低次元空間探索問題に分割することで，精度を向上させにおいて部分の類似が全体の類似と関連することに着目することが可能となっている．

ることで，列方向の分割時の課題であったデータ数に依存

*4
*5
*6
*7

https://github.com/spotify/annoy
https://github.com/yahoojapan/NGT
https://github.com/ekzhu/lsh
https://github.com/erikbern/ann-benchmarksc 2018 Information Processing Society of Japan⃝

する集約処理を短縮し，従来手法と比較して精度と探索速度が向上することを確認した．
提案手法では，部分ベクトル集合の分割は，直積量子化

6情報処理学会研究報告
IPSJ SIG Technical Reportに倣い単純な等分を行なったが，データの偏りを考慮したより効果的で少ない次元数での分割の可能性も検討した
い [7]．また，分散処理可能な特性を活かした拡張性ある構成としてネットワークをまたぐ大規模な近似近傍探索エンジンとしての実装と評価も進めていきたい．
参考文献
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Bawa, Mayank, Tyson Condie, and Prasanna Ganesan.
”LSH forest: self-tuning indexes for similarity search.”
Proceedings of the 14th international conference on
World Wide Web. ACM, 2005.
Burke, Robin. ”Hybrid recommender systems: Survey
and experiments.” User modeling and user-adapted interaction 12.4 (2002): 331-370.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan,
Vincent Vanhoucke, Andrew Rabinovich, Going Deeper
with Convolutions, The IEEE Conference on Computer
Vision and Pattern Recognition (CVPR), 2015
Christian Szegedy, Vincent Vanhoucke, Sergey Ioﬀe, Jon
Shlens, Zbigniew Wojna, Rethinking the Inception Architecture for Computer Vision, The IEEE Conference
on Computer Vision and Pattern Recognition (CVPR),
pp. 2818-2826, 2016
K. Fukushima. Neocognitron: a self organizing neuralnetwork model for a mechanism of pattern recognition
unaﬀected by shift in position, Biological Cybernetics,
36(4):93-202, 1980
Galletta, Dennis F., et al. ”Web site delays: How tolerant
are users?.” Journal of the Association for Information
Systems 5.1 (2004): 1.
Ge, Tiezheng, et al. ”Optimized product quantization for
approximate nearest neighbor search.” Computer Vision
and Pattern Recognition (CVPR), 2013 IEEE Conference on. IEEE, 2013.
Hyung Jun Ahn, A new similarity measure for collaborative filtering to alleviate the new user coldstarting
problem, Information Sciences 178, pp. 37-51, 2008
Jeﬀ Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoﬀman, Ning Zhang, Eric Tzeng, Trevor Darrell, DeCAF:
A Deep Convolutional Activation Feature for Generic Visual Recognition. In Proc. ICML, 2014
Jegou, Herve, Matthijs Douze, and Cordelia Schmid.
”Product quantization for nearest neighbor search.”
IEEE transactions on pattern analysis and machine intelligence 33.1 (2011): 117-128.
Krizhevsky, Alex, Ilya Sutskever, and Geoﬀrey E. Hinton. ”Imagenet classification with deep convolutional
neural networks.” Advances in neural information processing systems. 2012.
Y. Lecun, L. Bottou, Y. Bengio, P. Haﬀner, Gradientbased learning applied to document recognition, Proc.
IEEE, vol. 86, no. 11, pp. 2278-2324, Nov. 1998
Muja, Marius, and David G. Lowe. ”Scalable nearest
neighbor algorithms for high dimensional data.” IEEE
transactions on pattern analysis and machine intelligence36.11 (2014): 2227-2240.
Mikolov, Tomas, et al. ”Eﬃcient estimation ofword representations in vector space.” arXiv preprint
arXiv:1301.3781 (2013).
Kohei Sugawara, Hayato Kobayashi, and Masajiro
Iwasaki, On Approximately Searching for Similar Wordc 2018 Information Processing Society of Japan⃝

Vol.2018-IOT-42 No.2
2018/6/28

Embeddings , In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics（ACL 2016）, pages 2265-2275. Association for Computational Linguistics, 2016.
[16] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause,
Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej
Karpathy, Aditya Khosla, Michael Bernstein, Alexander
C. Berg, and Li Fei-Fei. 2015. ImageNet Large Scale Visual Recognition Challenge. Int. J. Comput. Vision 115,
3, pp. 211-252, December 2015[17] Pearson, Karl. ”LIII. On lines and planes of closest fit
to systems of points in space.” The London, Edinburgh,
and Dublin Philosophical Magazine and Journal of Science 2.11 (1901): 559-572.
[18] Le, Quoc, and Tomas Mikolov. ”Distributed representations of sentences and documents.” International Conference on Machine Learning. 2014.
[19] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Wenjie Zhang, Xuemin Lin, Approximate Nearest Neighbor
Search on High Dimensional Data — Experiments, Analyses, and Improvement (v1.0), In Proc. 2016[20] S. Zhang, L. Yao, and A. Sun, Deep learning based
recommender system: A survey and new perspectives,
arXiv preprint arXiv:1707.07435, 2017.
[21] 三宅 悠介, 松本 亮介, 力武 健次, 栗林 健太郎, 特徴抽出器の学習と購買履歴を必要としない類似画像による関連
商品検索システム, 研究報告インターネットと運用技術（IOT）,2017-IOT-37(4),1-8 (2017-05-18) , 2188-8787[22] 和田俊和. ”最近傍探索の理論とアルゴリズム.” 研究報告コンピュータビジョンとイメージメディア (CVIM) 2009.13(2009): 1-12.

7