YJTC18 D-4 AnnexML: 近似最近傍検索を⽤いたextreme multi-label分類の⾼速化

AnnexML: 近似最近傍検索を用いた Extreme Multi-label分類の高速化 田頭 幸浩

自己紹介 • 田頭 幸浩（たがみ ゆきひろ） • 機械学習技術の実サービス適用 およびそのための技術開発

取り組む問題とその背景

背景 • ヤフーのサービスの様々な場所で、機械学習技術を用いた レコメンデーションやランキングが行われている 例：スマホ版トップページ レコメンドされたニュース記事 インフィード広告

背景 • ユーザー体験を損なわないように、限られた時間の中で、 大量の候補の中からユーザーにマッチしたアイテムを選択する ことが求められる 各リクエストに対し 10〜100ミリ秒程度 で応答 幅広い層の ユーザー集合 アイテムの候補数は 1000万から数億にも

よく用いられるシステム構成 • 学習済みモデルと検索インデックスを組み合わせることで、 膨大な候補の中から予測スコアが高い少数のアイテムを 高速に取得可能 レコメンドモデルの学習 検索インデックスの構築 高速な応答が可能な レコメンドエンジン

よく用いられるシステム構成の課題 • 2段階の最適化で、精度と速度を担保しているので、 どちらの点でもベストとは言えない 最適化1（精度） 最適化2（速度） レコメンドモデルの学習 検索インデックスの構築 高速な応答が可能な レコメンドエンジン

より良いシステム構成 • 予測モデルの学習と検索インデックスの構築を同時に行う ことで、精度と速度のさらなる最適化が行えるようにしたい 統合された最適化 学習と構築を同時に行う さらに高精度かつ高速な レコメンドエンジン

Extreme Multi-label分類と AnnexML

Extreme Multi-label分類 • Extreme multi-label分類は、膨大な候補の中から 当てはまるものを選択する問題 • レコメンデーションやランキングもこの問題と見なすことが できるので、以降はレコメンデーションの例で説明 例：Wikipediaのページにカテゴリを付与 • • • Machine learning Cybernetics Learning 数十万の候補

AnnexML • AnnexMLはk近傍法によるextreme multi-label分類器 • Approximate Nearest Neighbor Search for Extreme Multi-label Classification レコメンド対象の ユーザー 探索 推定 興味が既知のユーザーの中で 行動履歴が似ているユーザー（k=3の例）

AnnexML • 既存手法のSLEECをベースに、学習および予測時に グラフ構造を用いることで予測精度と速度の両方を改善 レコメンド対象の ユーザー 探索 推定 興味が既知のユーザーの中で 行動履歴が似ているユーザー（k=3の例）

予測速度と精度の比較 予測精度の向上 予測速度の向上 +30%の精度向上 58倍の高速化

AnnexMLの構造 Coarse Partitioner Tree Graph Tree Graph Tree Graph • Coarse Partitionerを用いて クエリが含まれるpartitionを判定 • Treeインデックスを用いて 近似的に近傍点を獲得 • Graphインデックスを用いて 近似精度を高める（局所探索）

学習方針 • 行動履歴をもとに計算される類似度関数の値が、 似た興味を持つユーザー間で高くなるようにしたい 学習 予測 推定 類似度高 類似度高

学習方法の概要 • Coarse Partitionerの学習 • 興味が似たユーザーが同じpartitionに入るようにしたい • 特徴量空間上でのグラフカット問題として定式化 • FTRL-Proximalアルゴリズムでマルチクラス分類器を学習 • 各partition内での学習 • 似た興味を持つユーザーの類似度が高くなるようにしたい • グラフ構造上でのランキング問題として定式化 • AdaGrad+SGDで類似度関数内の射影行列を学習

実験結果：予測精度の比較

実験結果：予測速度の比較

手法と実験結果の詳細は論文にて https://dl.acm.org/citation.cfm?id=3097987

• https://dl.acm.org/citation.cfm?id=3097987

OSSとしてコードを公開 https://github.com/yahoojapan/AnnexML

• https://github.com/yahoojapan/AnnexML

まとめ • ユーザー体験向上のために、高速かつ高精度な レコメンデーションやランキング技術が不可欠 • 機械学習モデルの学習と検索インデックスの構築を統合した AnnexMLを開発した • 既存手法のSLEECと比較して、 速度で58倍、精度で+30%程度の性能向上を達成した