Tag Archives: query analysis

WWW2010メモ: Query Analysis 1 session

0
Filed under 学会

WWW2010,Query Analysisセッションのメモ.発表者全員がMicrosoft Resarch関係者だったのが印象的だった.

 

“Exploring Web Scale Language Models for Search Query Processing”
Jian Huang, Jiangbo Miao, Xiaolong Li, Jianfeng Gao, Kuansan Wang

目的:

  • WebドキュメントとクエリログをコーパスとしたN-gramモデルの分析とそのクエリ処理への応用
  • 結果はMicrosoft Web N-gram コーパスとして配布?

背景:

  • 普通のドキュメントのlanguage modelとクエリのlanguage modelは当たり前だけど異なる
  • 例えばWebコーパスから作った言語モデルをクエリの言語処理に用いるのは不適当
  • 2種類のWebコーパスについて言語モデル(ngram)の性質の違いを分析
    • Title, anchor text, body
    • クエリログ

二つのN-gram言語モデルの違いを分析.
評価尺度:Cross entropyとperplexity (二つともエントロピーのようなモノ) .

  • (聞き逃したが)クエリログの

言語モデルのクエリスペル修正への応用

  • 2-gramよりも3-gram, 4-gramの方を使った方が断然性能は良い.しかし
  • Queryログから作成された言語モデル > Anchor > …

クエリ構造分析 (query bracketing)

  • 3語のクエリ: [Sore gum] treatment, sore [gum treatment]を見分けたい
  • これを行うために言語モデル(bi-gram)と単語間の共起関係(PMI),カイ二乗検定を駆使する手法を提案
  • 評価:
    • ベースラインとして左2語をペアリング: 60%程度
    • 明らかにクエリ構造があるクエリに関しては,PMIを使っただけでも90%でquery bracketingに成功(bi-gram, カイ二乗検定でも80%程度は出ている)
    • しかもコーパスはクエリログよりもWebドキュメント情報を使った方が精度が出る

長いクエリの分断(Long query segmentation)

  • 4語以上の単語: 20%
  • クエリの意図をちゃんと見極めるためにも長いクエリの分割が必要
  • 例: raleigh serengeti mountain bike candidate tire
    • [raleigh serengeti] [mountain bike] [candidate tire] etc..
  • 分割手法: Segment-based PMIを計算し値が最大になるようにクエリを分解していく.
    • 例: A B C D E F → [A B C D] [E F] → [A B ] [C D] [E F] →…

感想

  • クエリをコーパスにした言語モデルと純粋にドキュメントをコーパスにした言語モデルの違いを調べるのは良いことだと思ったが,クエリ処理(スペルコレクション等)を行うのに実はドキュメントから生成した言語モデルの方が有効に働くというのは意外だった(直感的には...).
  • Query bracketingもquery segmentationも実は「ユーザが入力したクエリの順序は正しい」という仮定を置いていたみたいだけどそうなのかな?

 

“Optimal Rare Query Suggestion With Implicit User Feedback”
Yang Song, Li-wei He

背景と手法

  • クエリ推薦に良く使用される手法としては(クエリ, ClickURL)から作成したクエリグラフにrandom walkモデル解析を適用することだが,これは頻度が高いクエリにしか通用しない.
  • そこでクリックされなかったURL情報も使ったクエリ推薦手法を構築するのが目的

手法の詳細

  • 疑似フィードバックを組み込む
    • 仮説: SkippedURLはClickURLよりは適合性が低い
  • (query, ClickedURL) の二部グラフ,(query, SkippedURL)の二部グラフを別々に作成してRandom Walk解析
    • Random walk解析(僕の予想): (1) ipodを含むクエリ (ipod nano, ipod mini, ipod touchなど)をクエリログから収集.(2) 収集されたクエリとURLのペアからなる二部グラフ作成.(3)二部グラフとはいうもののグラフと見なしてPageRank的にRandomWalkしたときに最も滞在確率が高いノードを探す(dampling factorの項をクエリ拡張対象語以外の値を0とする)
  • その後二つの結果を結合して,あるクエリに関して最適なクエリ語を推薦
    • 結局の所,ClikedURLとクエリの二部グラフの分析結果とSkippedURLのそれとの分析結果をマージするということ

感想

  • Rare queryへのクエリ推薦とかいってたので面白いかなぁと思っていたら,ふたを開けてみるとクエリ推薦の精度改善のために既存手法を拡張したという話だった.
  • 実はSkippedURLとかあんまり必要ないのでは?そもそもレアクエリに対して本当に精度が上がっているのかが謎.
  • クエリ推薦のための解析手法であるrandom walk modelが分かっていることが前提でプレゼンされたので訳が分からなかった(あとで論文を読んだら分かった).