広告配信のための高速疎ベクトル検索エンジンの開発@WebDBフォーラム2015 #webdbf2015

広告配信のための 高速疎ベクトル検索エンジンの開発 ヤフー株式会社 宇野秀平

自己紹介 • 宇野秀平 – Yahoo! JAPAN 2006年入社 – 情報検索黒帯(2015) – 仕事内容 • 検索関連の仕事がメイン • 広告検索、商品検索、記事レコメンド、検索基盤etc

概要 • 検索エンジンは広告配信アーキテクチャの中 心 • 性能の良し悪しが収益に大きな影響を与える • 性能改善・機能追加のために先端理論を試 行錯誤し、自社製検索エンジンを磨きこんで いる

アジェンダ 1. YDNにおける検索エンジンの役割 2. LuceneでのYDN実現性 3. Senju概要 4. まとめ

YDNにおける検索エンジンの役割

YDNとは • Yahoo!ディスプレイアドネットワーク – Yahoo! JAPANのコンテンツページの他、さまざま な提携サイトのコンテンツページに広告を表示

YDNの立ち位置 • 2015Q2売上 ・広告売上の33%がYDN ヤフー全体で広告事業の売上は53％ 広告商品別 売上高推移(四半期) ・売上高215億 ・前年同期比164% 1000 900 800 700 プレミアム広告 600 YDN 売上(億円) 500 400 ディスプレイ広告 300 検索連動型広告 200 100 0 2014Q2 2015Q2 出典：ヤフー2015年度第2四半期決算より ヤフー成長の中心事業

YDN • 広告商品 – インタレストマッチ • ユーザが興味がある、コンテンツにマッチした広告を 配信 – ターゲティング • 広告主が特定のユーザに限定して広告を配信 – – – – – 一度サイトに訪れた事がある 特定の検索ワードを検索した事がある 特定の性別・年齢・地域のユーザ 特定のデバイスを持ったユーザ 配信したいサイト、配信したくないサイトを設定

YDNおける検索エンジンの役割 検索エンジン ・高速に真に正しい結果を含めた結果を返却 Modeler Reranker Re-ranker ・限られた候補に対して複雑なモデルによる高精度 な結果を算出 すべての結果に複雑なモデルは適応出来ない Searcher 真に正しい結果 Log server モデルを全体に適応した結果 検索結果 をなるべく包含した結果を高速に返す

YDNおける検索エンジンの重要性 検索エンジンが良い結果を返せないとモデルが高精度でも良い結果が返却出来ない 真の答えが含まれていない 真に正しい結果 モデルを全体に適応した結果 検索結果 検索エンジンが高速であれば複雑なモデルが使用可能になり、精度があがる 真に正しい結果 モデルを全体に適応した結果 モデルが真の答えを包含出来る可能性が上がる 検索結果 検索エンジンの性能向上は売上に大きな影響を与える

LuceneでのYDN実現性

Luceneの機能 機能 実現 性 YDNへの必要 性 キーワード検索 ○ × 複数単語検索 × ○ グループ化 ○ △ RangeQuery ○ × FuzzyQuery ○ × Boolean Index × ○ Luceneのキーワード検索機能は十分に充実 しかし、YDNで必要な機能は非搭載

実現したい事 • コンテンツマッチの実現 – ベクトル空間モデルを使ってコンテンツと類似度 が高い広告を検索 – 文書ベクトルが疎ベクトルになり、高速な疎ベクト ル検索を実現 tokenize tokenize Index：広告の単語ベクトル クエリ：コンテンツの単語ベクトル (0.2, 0, 0, ………, 0.13,0.33,…..,0) (1, 0, 0, ………, 1,1…..0) クエリと広告のcos類似度が高いTOP-Kを返却

転置indexによる実現方法 • クエリに出現した単語を重み付きORで検索 • 該当した文書のスコア(内積)を計算 • 上位K件を返却 tokenize tokenize Index：広告の単語ベクトル クエリ：コンテンツの単語ベクトル (0.2, 0, 0, ………, 0.13,0.33,…..,0) トヨタ:0.2 or 本気:0.1 or クルマ：0.5 or … 転置index クエリと広告の内積が高いTOP-Kを返却

Luceneの検索アルゴリズム 『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索 柏木由紀 1, 3, 6, 8, 9, 10, 12, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 16, … , 909779 小嶋陽菜 1, 4, 6, 7, 9, 11, 16, … , 909779 辞書 Result = [1(31)] 柏木由紀が存在する文書ID ポスティングリスト 文書1を登録して文書のスコアを計算

Luceneの検索アルゴリズム 『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索 柏木由紀 1, 3, 6, 8, 9, 10, 12, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 16, … , 909779 小嶋陽菜 1, 4, 6, 7, 9, 11, 16, … , 909779 辞書 Result = [1,3] ポスティングリスト 柏木由紀が存在する文書ID

Luceneの検索アルゴリズム 『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索 柏木由紀 1, 3, 6, 8, 9, 10, 12, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 16, … , 909779 小嶋陽菜 1, 4, 6, 7, 9, 11, 16, … , 909779 辞書 Result = [1,3,4] ポスティングリスト 柏木由紀が存在する文書ID

Luceneの検索アルゴリズム 『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索 柏木由紀 1, 3, 6, 8, 9, 10, 12, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 16, … , 909779 小嶋陽菜 1, 4, 6, 7, 9, 11, 16, … , 909779 クエリ数 辞書 ポスティングリストの長さ Result = [1,3,4] 速度は(クエリ数 × ポスティングリスト数)に依存 クエリ数が多いとレスポンスタイムが大きく劣化

Luceneで実現出来ない理由 • コンテンツマッチのクエリ数はコンテンツの単 語 – 30単語以上使用 • Luceneはクエリ数にレスポンスタイムが依存 – 要件を満たすためには万オーダーでサーバが必 要になりそう そこで自社で高速な検索エンジンを実装

ターゲティング • 広告主が設定した条件にマッチしたユーザに 広告を出す ユーザ情報 ユーザ情報 ・40代 ・北海道出身 ・男性 広告主が設定した条件にマッチした広告

既存の検索エンジン 広告1 出身(東京) and 趣味(野球) and 年代(40代) 広告2 出身(北海道) and 年代(40代) 40代, 北海道出身 Query(40代 and 北海道) 広告3 趣味(盆栽) and 年代(40代) 出身：東京 1, 3 出身：北海道 2 年代：40代 1, 2, 3 趣味：盆栽 3 辞書 ポスティングリスト 広告2はクエリの条件を満たす

条件を複雑にすると 入れ子を作ると 広告1 出身(東京) and 趣味(野球) and 年代(40代) 広告2 出身(北海道) and {年代(40代) or 性別(女性)} 40代, 北海道出身, 男性 広告3 趣味(盆栽) and 年代(40代) and 性別(男性) クエリの条件に2がマッチしなくなってしまう 出身：東京 1, 3 出身：北海道 2 年代：40代 1, 2, 3 趣味：盆栽 3 性別：男性 性別：女性 3 2 Query(40代 and 北海道 and 男性) 辞書 ポスティングリスト

Luceneでは実現出来ない理由 • 複雑な条件を持った検索が出来ない – 入れ子はビジネス要件として存在 – 検索条件をindex側に持つBoolean Indexが必要 • Luceneはクエリ側に検索条件 自社でビジネス要件を満たすエンジンを実装

Senjuの概要

Senju • Yahoo! JAPAN独自の転置Index型の検索ライ ブラリ • 主な特徴 – コンテンツマッチを高速検索する仕組みを実現 • WANDの導入 – Broder CIKM2003 – 複雑なターゲット条件による検索機能を実現 • Boolean Indexの導入 – Marcus SIGMOD2010

Senju • Yahoo! JAPAN独自の転置Index型の検索ライ ブラリ • 主な特徴 – コンテンツマッチを高速検索する仕組みを実現 • WANDの導入 – Broder CIKM2003 – 複雑なターゲット条件による検索機能を実現 • Boolean Indexの導入 – Marcus SIGMOD2010

WAND • WAND – WeakANDの略 – ORクエリにANDクエリのような振る舞いをさせる • ANDクエリは高速に検索可能

ANDが高速な理由 Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香) クエリに該当したポスティングリストすべてに同じ文書ID存在した場合、そのIDは成立 この場合1は全リストに存在してるので成立 柏木由紀 1, 3, 6, 7, 8, 10, 19, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 19, … , 909779 小嶋陽菜 1, 2, 6, 7, 18, 19, 55, … , 909779 島崎遥香 1, 19, … , 999999 Result = [1]

ANDが高速な理由 Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香) 次に一致してるIDを探す 最大の19が他のリストに存在しているか探す 柏木由紀 1, 3, 6, 7, 8, 10, 19, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 19, … , 909779 小嶋陽菜 1, 2, 6, 7, 18, 19, 55, … , 909779 島崎遥香 1, 19, … , 999999 Result = [1]

ANDが高速な理由 Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香) この部分の文書の評価をSKIPできる ORより高速に動作 柏木由紀 1, 3, 6, 7, 8, 10, 19, … , 909999 指原莉乃 1, 4, 6, 7, 9, 11, 19, … , 909779 小嶋陽菜 1, 2, 6, 7, 18, 19, 55, … , 909779 島崎遥香 1, 19, … , 999999 Result = [1, 19]

WAND UB ポスティングリスト内で最大のスコアを保存 柏木由紀 : 43 1, 3, 6, 7, 8, 10, 12, … , 909999 指原莉乃 : 13 1, 4, 6, 7, 9, 11, 16, … , 909779 小嶋陽菜 : 67 1, 2, 6, 7, 18, 19, 55, … , 909779 島崎遥香 : 21 1, 4, 6, 7, 8, 10, 16, … , 909779 Top-3が欲しい Result = [7(142), 1(141), 6(138)] 3件分の候補をスコア順に並べる 7以降の文書はスコアが138以上必要、つまり、UBの合計値が138以上になる事が条件 柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香 スコアの下限値を利用して擬似的にANDを生み出して高速化させる

Senju • Yahoo! JAPAN独自の転置Index型の検索ライ ブラリ • 主な特徴 – コンテンツマッチを高速検索する仕組みを実現 • WANDの導入 – Broder CIKM2003 – 複雑なターゲット条件による検索機能を実現 • Boolean Indexの導入 – Marcus SIGMOD2010

Interval algorithm クエリが下記を満たせば成立 ・intervalがstartからgoalまで辿りつける 文書の条件 = (A and B) or C or (D and E and F) の場合 interval クエリがA, Bの時 A：1 B：2−10 1〜10を満たすので成立 クエリがB, Dの時 B：2-10 D：1-4 1-4だと2-10に接続出来ないた め不成立

さらなる磨き込み • WANDの後継 – Block Max WAND • S. Ding and T. Suel SIGIR2011 • プロトタイプ実装 – 論文読み • 2014年以降、枝刈りアルゴリズムがあまり出ない • Boolean Index – 各種論文を読み問題に対応出来る解決策か調 査

まとめ • 検索エンジンは広告配信アーキテクチャの中 心 • 性能の良し悪しが収益に大きな影響を与える • 性能改善・機能追加のために先端理論を試 行錯誤し、自社製検索エンジンを磨きこんで いる

ご静聴有難うございました！