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

クエリログとスニペットの単語連接頻度に基づく Web 検索クエリのセグメンテーション 三宅 純平 颯々野 学 塚本 浩司 ヤフー株式会社 {jmiyake, kotsukam, msassano}@yahoo-corp.jp 1 はじめに いる． クエリセグメンテーションにおいて最も簡潔な手法 Web 検索サービスでは，入力されるクエリが適切に セグメンテーションされていないことが原因で，検索 としては，クエリを形態素解析で分割し，クエリカウ 精度の劣化が起こることが観察されている．特にゲー いて分割位置を推定する手法が考えられる．しかしな ム名などのカタカナ文字列は，連続した 1 語として扱 がら，日本語は英語とは違い，分かち書きがされてい われることが多く，検索精度の劣化の原因となる．そ ないため，新語や流行語（複合語）などの未知語が多 のため，クエリのセグメンテーション誤りの対策とし く含まれる Web 検索クエリへの対応を考えると上記 て，人手の精査により未知語や複合語の辞書更新で誤 の方法では適切なセグメント位置の推定は難しい． ントやウェブカウントから求めた何らかの尤度に基づ り訂正が行われることが多い．しかしながら，これら は非常にコストのかかる作業であり，クエリセグメン テーションの自動化への要求は高い． クエリログとスニペットの単語連 3 そこで，本稿では検索精度の改善を目的として，ク 接に基づくクエリセグメンテーシ エリログとスニペットの単語連接頻度に基づくクエリ ョン セグメンテーションの手法を提案する．また，セグメ ンテーションしたクエリコーパスを学習データとして SVM の点推定手法を用いたセグメンテーターの実用 性に関しても評価した． ここではまず，クエリログにおけるアンド検索のス ペース位置の分析結果について述べる，次に検索精 度が改善するクエリのセグメンテーション手法を提案 する． 2 関連研究 Bergsma ら [1] は，様々な二値の素性や単語および 3.1 ユーザが入力するクエリの傾向 単語連接の対数頻度，境界前後の単語を素性として， クエリログの分析では，クエリログからデリミター SVM による意味の境界を推定する手法の提案をした． この手法は従来手法である相互情報量による境界推定 を削除した時に同一となる異なりセグメント位置を持 より大幅な精度改善が報告されており，現段階におい ト位置の傾向について分析した．デリミターは空白と て最も精度高い手法とされている．Tan ら [2] は大規 中黒「・」とした．クエリセットの例を表 1 に示す． 模な Web コーパスから構築した単語 5-gram 言語モデ クエリログの分析より得た知見を以下にまとめる． ルを用いて意味の境界を推定する手法を提案した．ま つクエリの抽出を行ない，ユーザが入力するセグメン 最頻クエリの傾向 た，Wikipedia のタイトルやアンカーテキストをコー 最頻クエリには， 「無料動画」などのようなクエリ特 パスに含めることで大幅な精度改善が報告されている． 有の複合語が多い．また，口語表現で使われるフレー Wang ら [3] は，Microsoft Web N-gram コーパスを用 ズがそのまま入力されることがある．例えば，クエリ いた言語モデルによる単語分割において，タイトルや 「めざまし占い」は，実際の正式名称は「めざましテレ アンカーテキストだけを用いたモデルが Web 全体の ビ・今日の占い CountDown」であり，入力クエリと コーパスを用いることより精度が高いことを報告して

異なりセグメント位置を 表 1: クエリログから抽出した異なりセグメント位置 を持つクエリセットの例 クエリ 頻度占有率 シェラトングランデ東京ベイ 0.915 シェラトン■グランデ■東京ベイ 0.03 0.02 0.013 シェラトングランデ■東京ベイ シェラトン■グランデ■東京■ベイ シェラトン・グランデ・東京ベイ ... 0.011 ... 持つクエリの抽出 シェラトングランデ東京ベイ シェラトン■グランデ■東京ベイ クエリログ シェラトン■グランデ■東京■ベイ 頻度か言語モデルを基準に， スニペットの単語連接 頻度に基づいて適切な セグメント数の多いクエリを 選択する クエリのセグメント位置を推定 シェラトン■グランデ■東京ベイ シェラトン■グランデ■東京■ベイ 図 1: 検索精度が改善するセグメント位置の推定 要求する文書に含まれる表現とが異なることがある． カタカナ文字列における中黒「・」 エリセグメンテーションが行われる． われわれは提案手法の 1 段目であるセグメント数 カタカナ文字列は，複数の単語が繋がるものでも連続 の多いクエリを選択する手法として，以下の 2 つの手 した 1 語として入力される傾向が高い．また，デリミ 法を用いた． ターとして空白の代わりに中黒「・」が挿入されてい 最多セグメント数による選択 ることが多く，これは正しいセグメント位置であるこ 最多セグメント数による選択は，ヒューリスティックな とが多い． 方法である．異なりセグメント位置を持つクエリセッ 英数字文字列 トから頻度占有率 0.1% 以上のものを対象に最もセグ 英語文字列の最頻クエリは，正しくセグメントされて メント数の多いクエリを選択する．セグメント数の同 いることが多い．また「iphone4，iphone 4」のよう じクエリが複数ある場合は頻度占有率の高いクエリを な型番を含むクエリは，カタカナ文字列の場合と比べ 選択する． て，スペース位置が検索ランキングに大きく影響する 言語モデル尤度による選択 ことが確認された． 言語モデル尤度による選択では，クエリセットから文 字 3-gram 言語モデルの尤度を用いて最尤のクエリを これらの分析より，最頻クエリは必ずしも検索の精 選択する．これは誤りセグメント位置の棄却に対応す 度改善に適切なセグメント位置ではないことが確認さ る他，アンド検索がされ易い単語が含まれるクエリ対 れた．しかしながら，中頻度クエリは適切にセグメン してはよりセグメント数の多いクエリを選択する効果 トされているクエリも多く，適切なセグメント位置の がある．ただし，英数字文字列のみで構成されている 手掛かりになると考えられる．そこで，われわれは異 クエリに関しては最頻のクエリを選択している．これ なりセグメント位置を持つクエリセットを用いて，検 は，3-gram モデルでは適切なクエリ選択がされなかっ 索精度を改善するセグメント位置を推定する手法を提 たためであり，英数字文字列への対応にはより高次の 案する． n-gram が必要であると考えられる．各クエリ q のク エリセットを Q，各クエリ q の文字 xi の長さを N と 3.2 3.2.1 クエリログとスニペットを用いたクエ リセグメンテーションの提案 クエリのセグメント位置の推定手法 図 1 に提案手法を示す．提案手法は 2 段階に分かれ ている．1 段目では，クエリセットから誤りセグメン ト位置を含まず，よりセグメント数の多いクエリの選 択を行なう．2 段目では，選択したクエリの Web 検 おく． q = {x0 , x1 , x2 , ..., xN }， q∈Q この時，クエリ文字列に対する 3-gram 言語モデルの 対数尤度の相加平均よりクエリセット Q における最 尤の q を選択する． ∑N log P (xi |xi−2 , xi−1 ) max i=1 N −1 q∈Q 索結果のスニペットを取得し，各単語の頻度と単語連 接頻度を算出し，シンプソン係数に基づいてクエリの セグメント位置の再判定を行なう．これにより，実際 の Web ページに含まれるクエリの単語を考慮したク 3.2.2 提案手法による検索精度改善の検証 提案手法 (言語モデル+スニペット，セグメント数+ スニペット) が検索精度を改善するものであるかを検証

表 2: クエリログとスニペットを用いたクエリセグメ ンテーションの実験条件 正解データの期間 エリを選ぶ傾向があるが，クエリに特化したモデルで あるため，クエリ特有の複合語はセグメントされない ままのクエリは選択されてしまう．言語モデルでより 2010 年 10 月 1 日〜31 日 適切なクエリ選択を行うためには，クエリコーパス以 615 件 外に Wikipedia など他コーパス資源とのマージが必要 人手正解データの一致率 82.4 % であると考えられる． 言語モデルの学習データ 2010 年 10 月 1 日〜31 日 サンプル数 検索結果取得数 20 SVM の点推定手法を用いた クエリセグメンテーターの実用性 評価 4 表 3: 提案手法と比較手法のクエリセグメンテーショ ンの実験結果 Qry-Acc Seg-Acc 前節の提案手法では，クエリログやウェブの頻度情 0.937 0.923 0.951 報に基づいてクエリのセグメンテーションを行なった 言語モデル 0.645 0.617 0.731 セグメント数 0.732 0.953 こで，われわれはクエリコーパスを SVM の点推定に 形態素解析+スニペット 0.739 0.952 よる単語分割手法に適用したクエリセグメンテーター 言語モデル+スニペット 0.773 0.781 0.962 0.962 を実装し，実用性の評価を行なった． 最頻クエリ 形態素解析 セグメント数+スニペット が，文字や文字種などの素性を用いることで精度の良 いセグメンテーションができることも期待される．そ SVM の点推定による単語分割手法 するために，人手で Web 検索に適切なクエリのセグメ 4.1 ント位置を付与した正解データを作成し，提案手法に として，最頻クエリのセグメント位置と，最頻クエリを SVM の点推定による単語分割手法は Sassano[4] や Neubig ら [5] より提案されており，高精度に単語分割 が行えることが報告されている．これらの手法は，各 形態素解析1 し，スニペットの単語連接頻度に基づいて 文字列間が単語境界であるかどうかの二値分類問題と セグメント位置を推定する手法 (形態素解析+スニペッ してとらえたものであり，注目している文字列間の前 ト) を扱う．評価基準は，Bergsma らが用いた Query 後の文字 n-gram や文字種 n-gram，辞書単語の始端終 よるセグメント位置との一致率を評価した．比較手法 Accuracy(Qry-Acc) と Segment Accuracy(Seg-Acc) 端であるかなどを素性として組み込み，SVM による を用いる．Qry-Acc はクエリの完全一致率であり，Seg- 学習を行なっている． Acc は文字列境界の正解率である．シンプソン係数は 精度が最高となる 0.9 を用いる． 表 2 に実験条件を示す．正解データは，1ヵ月分の クエリログの上位 10 万件のクエリから頻度 2 以上の 4.1.1 素性 異なりセグメント位置を持つクエリセットを抽出し， SVM で用いる素性は以下のものである． 文字 n-gram 最頻クエリの頻度占有率の 100%から 5%で間隔でラ セ グ メ ン テ ー ション を 識 別 す る xi , xi+1 ンダムサンプリングを行ない，合計が 600 件に近くな るように均等に選んだ．正解データのタグ付与は 2 名 で行ない，実験結果の正解率では平均をとった． 表 3 の実験結果より，提案手法である「セグメン に おける窓幅前後それぞれ w 文字の文字列 xi−w+1 , .., xi , xi+1 , ..., xi+w の文字 n-gram 文字種 n-gram ト数+スニペット」が Qry-Acc と Seg-Acc において一 上記の文字 n-gram における文字種（ひらがな，カ 番精度が高い． 「セグメント数+スニペット」ではカタ タカナ，漢字，アルファベット，数字，その他）の カナ文字列の分割精度の改善が確認されている．言語 n-gram モデル尤度ではある程度多くセグメントされているク 1 Yahoo! Japan デベロッパーネットワーク日本語形態素解析 Web API と同等のもの http://developer.yahoo.co.jp/webapi/jlp/ma/v1/parse.html 辞書単語素性 文字 n-gram において辞書に含まれる単語．ただし，

• http://developer.yahoo.co.jp/webapi/jlp/ma/v1/parse.html

表 4: SVM の点推定手法の適用によるクエリセグメ 表 5: SVM の点推定手法の適用によるクエリセグメ ンテーターの実験条件 ンテーターの精度 クエリログの期間 2010 年 10 月 1 日〜31 日 サンプル数 言語モデルの学習データ 10 万件 Qry-Acc Seg-Acc 言語モデル+スニペット 0.659 0.943 セグメント数+スニペット 0.667 0.945 2010 年 10 月 1 日〜31 日 検索結果取得ページ数 SVM 学習器 20 5 おわりに liblinear 本報告では，入力クエリにおけるセグメント位置の セグメンテーションを識別する xi , xi+1 において，始 端になっている単語には R，終端になっている単語 には L，xi , xi+1 を跨いでいる単語には I のフラグも 共に付与している． 辞書単語には，ipadic-2.7.0-20070801 と日本語・英語 Wikipedia のアブストラクトから英数字単語のみをカ ウントして作成した辞書を用いた (日本語 Wikpedia: 頻度 2 以上，英語 Wikipedia:頻度 10 以上)． 違いによる検索精度劣化への対策のため，クエリログ のアンド検索のスペース位置とスニペットの単語連接 頻度を用いて，Web ページに出現するクエリの単語を 考慮したセグメント位置を推定する手法を提案した． 実験結果より，クエリ選択として異なりセグメント位 置を持つクエリセット内の最多セグメント数を用いた ものが最も良い精度であった．また，クエリコーパス から SVM の点推定手法を用いたクエリセグメンテー ターの実用性の評価を行なった．今後はクエリセグメ ンテーターの精度改善を目指すとともに未知語分割器 4.2 実験条件 としての応用にも取り組む． 評価実験では SVM の点推定手法よるクエリセグメン テーションと正解データとの一致率を評価した．SVM の学習データは，1ヵ月分の Web 検索のクエリログに おける上位 10 万件（正解データは含まない）を提案手 法 (言語モデル+スニペット，セグメント数+スニペッ ト) でセグメントしたクエリコーパスを用いた．表 4 に実験条件を示す．評価基準は，Qry-Acc と Seg-Acc を用いる．SVM の学習器としては，liblinear[6] を用 いた．また，点推定手法の窓幅は 5，n-gram のサイズ は 3 を用いた． 4.3 実験結果 実験結果を表 5 に示す．前節同様に「セグメント数+ スニペット」の手法が最も良い精度を示した．点推定 手法では局所的にセグメントの識別を行うため，クエ リに対し多くセグメントされる傾向が見られる．先行 研究よりクエリカウントやウェブカウントがセグメン ト位置推定に有効であるという報告が多くされている 他，離れた単語の組み合わせによるセグメント位置の 変化やクエリ全体から適切なセグメント位置の推定な どを考慮することで更なる精度改善も期待できる． 参考文献 [1] S. Bergsma and Q.I. Wang. Learning noun phrase query segmentation. In Proc. of EMNLP-CoNLL, 2007. [2] B. Tan and F. Peng. Unsupervised query segmentation using generative language models and wikipedia. In Proceeding of the 17th international conference on World Wide Web, pp. 347–356. ACM, 2008. [3] K. Wang, C. Thrasher, E. Viegas, X. Li, and B.P. Hsu. An overview of Microsoft web N-gram corpus and applications. In Proceedings of the NAACL HLT 2010 Demonstration Session, pp. 45–48. Association for Computational Linguistics, 2010. [4] M. Sassano. An empirical study of active learning with support vector machines for Japanese word segmentation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pp. 505–512. Association for Computational Linguistics, 2002. [5] Graham Neubig, 中田陽介, 森信介. 点推定と能動 学習を用いた自動単語分割器の分野適応. 言語処 理学会第 16 回年次大会 (NLP2010), 東京, 3 2010. [6] R.E. Fan, K.W. Chang, C.J. Hsieh, X.R. Wang, and C.J. Lin. LIBLINEAR: A library for large linear classification. The Journal of Machine Learning Research, Vol. 9, pp. 1871–1874, 2008.