クエリログとスニペットの単語連接頻度に基づくWeb検索クエリのセグメンテーション

クエリログとスニペットの単語連接頻度に 基づくWeb検索クエリのセグメンテーション ヤフー株式会社 三宅 純平，塚本 浩司，颯々野 学

発表内容 • • • • 研究背景 研究目的 Web検索クエリの傾向分析 クエリログとスニペットの単語連接頻度に基づく クエリセグメンテーション – 提案手法の説明 – 評価実験 • SVMの点推定手法によるクエリセグメンテーション の検証 – 提案手法の説明 – 評価実験 • まとめと今後の課題 2 Yahoo! JAPAN CONFIDENTIAL

研究背景 • Web検索クエリのセグメント位置による 検索結果の変動 – セグメント位置の違いによるクエリ意図の曖昧化 – 新語・流行語に対する単語分割誤り 3 嵐■トラブルメーカー 嵐■トラブル■メーカー レッドストーン レッド■ストーン リンチーリン リン■チーリン iphone4 iphone■4 Yahoo! JAPAN CONFIDENTIAL

【例1】嵐■トラブルメーカー 嵐の音楽PVのページ Yahoo!オークションへの誘導リンク ※2010年10月 Google検索エンジンに移行前 4 Yahoo! JAPAN CONFIDENTIAL 嵐のCD・DVDの広告

【例1】嵐■トラブル■メーカー 広島大の音楽サークル 個人ブログ サークルページ 別の曲 外構工事の広告 ※2010年10月 Google検索エンジンに移行前 5 美肌の広告 Yahoo! JAPAN CONFIDENTIAL

【例2】iphone■4 ASCII.jpブログ 日経トレンド 6 ※Google検索エンジンに移行後 Yahoo! JAPAN CONFIDENTIAL

【例2】iphone4 クチコミ掲示板、 ニュースブログ 7 セグメント位置の違いによって検索結果の劣化が生じる ※Google検索エンジンに移行後 Yahoo! JAPAN CONFIDENTIAL

目的 入力クエリに対して、検索精度が向上する クエリセグメンテーション 嵐■トラブル■メーカー 8 竹内■結子■画像 グランド■セフト■オートバイ■スシティ × × × ○ ○ ○ 嵐■トラブルメーカー 竹内結子■画像 グランド■セフト■オート■バイスシティ Yahoo! JAPAN CONFIDENTIAL

関連研究 • 一般的なクエリセグメンテーションは 単語単位による統計的な意味境界の推定 new york times■subscription – Bergsmaら, 2007 • 様々なルール、単語頻度、単語表記の素性を用いたSVMに よるセグメンテーション – Tanら, 2008 • クエリログとWikipediaコーパスの言語モデル尤度と相互情 報量に基づくセグメンテーション 分かち書きがされていない日本語では、 未知語が多く含まれるWeb検索クエリへの対応は難しい 9 Yahoo! JAPAN CONFIDENTIAL

Web検索クエリの傾向分析 • 入力が最も多いセグメンテーションパターン （最頻クエリ）が検索精度向上に適切か？ 必ずしもそうではない！ • 全体的に単語を長く連接させる傾向がある – 【ex. 】無料サンプル動画，オリンピック参加国， グランドセフトオートバイスシティ■攻略…etc – カタカナ文字列は全て連接させる傾向が高い 検索精度を考慮してクエリに 注意深くセグメントを入れる人は少ない 10 Yahoo! JAPAN CONFIDENTIAL

クエリログとスニペットの連接頻度情報に 基づくクエリセグメンテーション クエリセット クエリ 頻度占有率 シェラトングランデ東京ベイ 0.91 0.03 0.02 0.01 シェラトン■グランデ■東京ベイ シェラトングランデ■東京ベイ シェラトン■グランデ■東京■ベイ クエリログから異なりセグメント 位置を持つクエリセットを抽出 ①検索クエリの候補選択 頻度か言語モデル尤度を基準に セグメント数の多いクエリを選択 シェラトン■グランデ■東京■ベイ ② Web検索のスニペットを抽出 シェラトン■グランデ■東京ベイ 11 スニペットの単語連接頻度に基づいて 適切なセグメント位置の推定 Yahoo! JAPAN CONFIDENTIAL

① 検索クエリの候補選択 • Web検索結果のスニペットから単語連接頻度を 得るための検索クエリ候補を選択 – 最頻クエリの形態素解析 • Yahoo!Japan デベロッパーネック 日本語形態素解析 WebAPIと同等のもの – 最多セグメント数による選択 • クエリセットの頻度占有率の0.1%を棄却し セグメント数が最大のクエリを選択 90 シェラトングランデ東京ベイ シェラトン■グランデ■東京ベイ 3 2 シェラトングランデ■東京ベイ シェラトン■グランデ東京ベイ 0.05 – 文字3gram言語モデル尤度による選択 • セグメント位置を<sp>としてカウント • 1~3gramの生起・連接の対数確率の 相加平均で最大のクエリを選択 12 Yahoo! JAPAN CONFIDENTIAL n  log P( x | x max qQ i 1 i n 1 i 2 , xi 1 )

② Web検索のスニペット抽出＆ 単語連接頻度によるセグメンテーション • Web検索のスニペットから単語頻度(unigram,bigram)を 求め、セグメント位置の推定 – スコア計算にはシンプソン係数を使用(閾値は0.9) シェラトン グランデ 東京 ベイ score = 0.7 score  13 C (シェラトングランデ) min(C (シェラトン), C (グランデ)) score = 0.6 score = 0.9 シェラトン グランデ 東京ベイ Yahoo! JAPAN CONFIDENTIAL

評価実験の内容 • 評価方法 – 人手の正解データと提案手法による セグメントしたクエリの一致率を評価 – 正解データ • クエリセットにおける最頻クエリの頻度占有率でバランス よく含まれるように抽出 • 正解データ作成は同じサンプルデータに対し、 2名 でアノテーションを行なった • 評価基準 Query Accuracy Segment Accuracy 14 クエリの完全一致率 セグメント位置の一致率 Yahoo! JAPAN CONFIDENTIAL

実験条件 • 比較手法 ベースライン 最頻クエリ 提案手法 形態素解析（スニペットあり，なし） 言語モデル尤度（スニペットあり，なし） 最多セグメント数（スニペットあり，なし） 2010.10.01 – 31(1ヵ月) 正解データの期間 正解データのサンプル数 615件 正解データ同士の一致率 82.4% 言語モデルの学習データ 2010.10.01 – 31(1ヵ月) 検索結果取得数 15 20 Yahoo! JAPAN CONFIDENTIAL

実験結果 Query Accuracy(%) 人手正解データ 同士の一致率 (82.4%) 最頻クエリ 形態素解析 言語モデル 尤度選択 最多セグメント数 選択 最頻クエリよりもクエリセット内から 適切なクエリを選ぶことで正解率が向上 16 Yahoo! JAPAN CONFIDENTIAL

ここまでのまとめ • 検索精度が向上するクエリセグメンテーション • クエリログとスニペットの単語連接頻度から 適切なクエリのセグメント位置を推定 – クエリセット内から言語モデル尤度や 最多セグメントの基準にクエリ選択 – Web検索のスニペットでの単語連接頻度の考慮 – 最頻クエリより約10pt改善 • 異なりセグメント位置を持つクエリセットが必要 文字や文字種、辞書単語などの素性を用いて、 適切なセグメントを行えないかを検証 17 Yahoo! JAPAN CONFIDENTIAL

SVMの点推定手法による クエリセグメンテーション • 文字、文字種、辞書素性を用いて セグメンテーション位置を推定 – SVMの点推定手法による単語分割[Sassano, 2002]、[Neubigら, 2010] – 学習データはクエリログとスニペットから作成したクエリデータ – 単語辞書はipadicと日・英語のWikipedia L フィギュアスケート R 浅田真央 窓幅=5 1gram : L5/ア L4/ス L3/ケ L2/ー L1/ト R1/浅 R2/田 R3/真 R4/央 2gram : L5/アス L4/スケ L3/ケー L2/ート L1/ト浅 R1/浅田 R2/田真 R3/真央 3gram : L5/アスケ L4/スケー L3/ケート L2/ート浅 L1/ト浅田 R1/浅田真 R2/田真央 辞書素性 : L1/スケート R1/浅田 文字種素性 : 文字素性（ひらがな、カタカナ、漢字、数字、英字、シンボル）を文字種に置き換えたもの 18 Yahoo! JAPAN CONFIDENTIAL

クエリログとスニペットの連接頻度情報に 基づくクエリセグメンテーション クエリセット シェラトングランデ東京ベイ シェラトン■グランデ■東京ベイ シェラトングランデ■東京ベイ シェラトン■グランデ■東京■ベイ 出力クエリを学習データ として分割精度を検証 ※ 理想的には人手正解データ シェラトン■グランデ■東京■ベイ 学習 シェラトン■グランデ■東京ベイ 19 SVMの点推定による クエリセグメンテーション Yahoo! JAPAN CONFIDENTIAL

評価実験 • 実験内容 – 人手の正解データとの一致率を評価 – 評価基準はQuery Accuracy，Segment Accuracy • 実験条件 SVMの学習データ 2010.10.01～31の上位10万件に対して前 手法を適用した結果 liblinear SVM学習器 素性 文字ngram，文字種ngram，辞書単語 その他 20 窓幅=5, ngram=3 Yahoo! JAPAN CONFIDENTIAL

実験結果 • クエリログとスニペットを用いた手法の 約85%の精度を達成 – ウェブやクエリの単語頻度を素性として組み込みが 今後の課題 Query-Acc(%) 言語モデル+スニペット 77.3 96.2 最多セグメント数+スニペット 78.1 96.2 SVM 言語モデル+スニペット 65.9 94.3 SVM 最多セグメント数+スニペット 66.7 94.5 ※ 学習データでの5-fold CVで約83.3% 21 Seg-Acc(%) Yahoo! JAPAN CONFIDENTIAL

まとめと今後の展開 • まとめ – 検索精度が向上するクエリのセグメンテーションの 提案 • クエリログのスニペットの単語連接頻度より 適切なセグメンテーション位置の推定 • SVMの点推定手法によるクエリセグメンテーション • 今後の課題 – SVMの点推定によるクエリセグメンテーションの 精度改善 • クエリカウントやウェブカウントの素性組み込み 方法の検討 – 英語・カタカナクエリの未知語分割器としての応用 22 Yahoo! JAPAN CONFIDENTIAL

おわり • ご清聴ありがとうございました 23 Yahoo! JAPAN CONFIDENTIAL