近似近傍探索ライブラリgannによる関連記事推薦方法

こんにちは、データ分析部の川口です。 f:id:makuramoto1:20190627180055p:plain

本日はGunosy社が提供しているニュースパスとLUCRAというニュースアプリケーションの関連記事推薦で用いられている、弊社メンバーが開発したGo言語の近似近傍探索用ライブラリgann

とその実装例/方法について述べます。

概要

gannライブラリを用いた関連記事推薦の実装方法を説明いたします。弊社のニュースアプリケーションでは、下図のように、ニュース記事ページの下部に関連記事のリストを表示しております。(※画像はイメージです) f:id:makuramoto1:20190627174955p:plain

関連記事リストは、アプリケーションが記事ページに遷移した際に関連記事推薦を行った結果を表示してます。この関連記事推薦は下記のような特徴があります。

ニュースアプリケーションからの記事ページを要求するリクエストの度に関連記事推薦を行い、その結果を即座に記事ページに反映させる必要がある
関連記事推薦の候補となる記事数が1万近くあり、また記事のベクトルが数百次元で表現されている

上記の関連記事推薦の計算コストが重くなりがちな要因が多々ある中、gannを用いることにより、高速に推薦を行なっております。

実装

簡易的でありますが、関連記事推薦を行う際の構成は下記となります。

f:id:makuramoto1:20190627142808p:plain

記事ベクトルストレージ

数百次元の記事ベクトルが1万ベクトルほど格納してあるストレージ
随時入稿されている新規の記事に対応するために、関連記事推薦候補対象の記事を全てベクトル化して定期的に格納

関連記事推薦サーバ

アプリケーションからのリクエストに対し関連記事リストをレスポンスするAPIサーバ

定期的に下記のことを行う

記事ベクトルストレージに格納されている全記事ベクトルを収集
ベクトル間の近傍関係を空間分割したindexを計算し、キャッシュに格納

2に関してですが、つまりはgannのREADMEのexampleにおけるCreateNewIndexの処理が重いので、定期的に計算してキャッシュに格納することを指してます。アプリケーションからリクエストが来る際にはindexを計算することを回避し、キャッシュからindexを引き出して関連記事計算を行うことで高速にレスポンスできるようにしています。

// create index
idx, err := gann.CreateNewIndex(rawItems, dim, nTrees, k, m)
if err != nil {
    // error handling
    return
}

そして、アプリケーションからリクエストが来る度に

関連記事のリストをレスポンス

gannのREADMEのexampleにおける

// search
var searchNum = 5
var bucketScale float64 = 10
q := []float64{0.1, 0.02, 0.001}
res, err := idx.GetANNbyVector(q, searchNum, bucketScale)
if err != nil {
    // error handling
    return
}

を行い、関連記事推薦を完了しております。

補足

上記の実装の項では、gannのパラメータに関しては触れませんでしたが、下記のパラメータに関してはチューニングする必要があります。

nTree
k
searchNum
bucketScale

適用する環境とどのくらいの近傍のベクトルを抽出したいのかを考慮し、適切に設定してください。

おわりに

今回は近似近傍探索ライブラリの具体的な使用例を示した上で実装方法について説明いたしました。弊社では、最適な情報を世界にお届けするために日々弊社アプリの記事提供アルゴリズム/ロジックを改善しております。自らアルゴリズムを考え、開発を行ない、問題解決をしていきたいエンジニア並びにデータサイエンティストを募集しております。興味のある方は下記の募集要項から是非ご応募ください。