糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com

Learning to Estimate Query Difficulty (SIGIR 2005) 読んだメモ

メモ 論文

Learning to estimate query difficulty: including applications to missing content detection and distributed information retrieval
SIGIR 2005のbest paper．

目的

ある検索システムに対して投げられた検索クエリがどれほど難しいのかを測りたい．

めんどくさい事

  • クエリは長さがまちまちで→特徴ベクトルのサイズがまちまちになる．しかし大抵の学習器では特徴ベクトルは一定でなければならない
  • sub-queryの順序関係が保たれていないから順序関係を無視する学習器と相性が悪い（ちょっとよく分からない）

方法

  1. 線形和でスコアを付ける
  2. 決定木を作る

実験によると長いクエリには1.が，短いクエリには2.が効くらしい．
メリットとしては，方法がシンプルであり，検索システムそのものに手を加える必要がない事．

似た話

Clarityが提案した検索結果の良さを測る指標がある．これは検索クエリと，そのクエリでヒットした文書の上位（コレクション）で言語モデルを作り，それのKLダイバージェンスを比較するというもの

Sources of evidence for vertical selection (SIGIR 2009)読んだメモ - 糞ネット弁慶

前回読んだ論文でこんな話もありましたね．

使う特徴量

そもそもこの論文ではqueryはsub-queryの集合から構成されると考えている．

  • sub-queryそれぞれとfull-queryについて，検索結果上位N件のoverlap
  • sub-queryの検索結果の件数（DF）にlogを取ったもの

Query estimator using a histogram（線形和でスコアを付ける）

元論文の添字が非常に読みにくいので改変する．
クエリについて次のような操作で特徴ベクトルを作る．

  1. sub-queryのそれぞれとfull-queryについて検索結果のtop-Nのoverlapを取得，それらのヒストグラムを作る
  2. ついでにsub-queryのlog(DF)を取得してこっちも離散値変換してヒストグラムにする
  3. 二つのヒストグラムを重ね合わせてクロス表にする（この時，クロス表の要素の最大値がMであるとする）
  4. N×Mの行列を一列のベクトルにすればの完成

あとは学習させた重みベクトルを使ってで計算できる．
の学習はP@NもしくはMAPとのMean Square Errorを最小にする方向でMoore-Penrose pseudo-inverseを使って
でいける．はP@N/MAPのクエリをさっきの手段で特徴ベクトルに変換したもの，Hは行に訓練クエリrの特徴ベクトルを持つ行列．
で，ここに「クエリiがクエリjよりも順位が高い」みたいな制約を突っ込むとはケンドールの順位相関を最大化してくれるらしい（何との順位相関かは理解があやふやだがおそらくP@N/MAPとの？）．でこれをやりたきゃHをヒストグラム（を組み合わせたクロス表）から構築するのではなく，とやる（は訓練クエリの数）．

Query estimator using a modified decision tree（決定木を作る）

CARTっぽい決定木を作る．この決定木は特殊で，root/nodeのそれぞれにおいて//Score/thresholdという4つの値を持つ．

  1. sub-queryをDFでソート
  2. rootからソート済みsub-query1つに対しlog(DF)×とoverlap×がthresholdを超えなかったら左に，超えたら右に移動する
  3. これを順次繰り返しleafに到達/sub-queryを全てチェックしたらそのノードのScoreが難易度になる

という感じ．
木の学習は

During training of the decision tree, the weight vector is trained at each node to try and split the number of training queries equally among the branches of the tree according to their rank (i.e., their respective ranking according to P@10 or MAP).

Learning to estimate query difficulty: including applications to missing content detection and distributed information retrieval

と書かれているがここが理解できなかった．
Scoreの計算はrootを1.0として左に行ったら/1.5，右に行ったら*1.2するらしい（この値はヒューリスティックに決めたとか）．
決定木による難易度決定はこれだけじゃ終わらない．ランダムサンプリングで異なる木を作りAdaBoostのような事までやってる．

Evaluation

ケンドールのτで比較．

Applications

活用事例

  • Improving IR using query estimation
    • Automatic query expansion(AQE)．検索クエリに単語を追加する方法だがこれは通常簡単なクエリでしか有効に働かない．なのでクエリの難易度を使ってAQEすべきかどうかを判定してやる．
  • Detecting missing content
    • missing content queries (MCQs)：ドキュメント集合の中に関連するドキュメントが無いようなクエリ．これが特定できると利用者と管理者双方の利益になる．
    • クエリの難易度でprefilterかけて判定させるといい感じ
  • Merging the results in a distributed IR system according to difficulty estimation
    • distributed IR systemってのは文書集合が違う複数の検索システムという想定(?)
    • 複数の検索システムの結果をマージしたい時に，それぞれの検索システムでクエリに対する向き不向きの結果を使ってうまいことマージできるよね

読んだ感想

非常にシンプルな手法だったのでむしろ拍子抜けした．しかし決定木の学習部分がよくわかっていないのが問題．
あとこれは自分の論文メモ全般に言えるんだけど，手法そのものにしか興味が無いのでEvaluationの部分まで読む気力がない．どうにかしたい．