9月
06

A comparison of query and term suggestion features for interactive searching

D. Kelly
K. Gyllstrom
E. Bailey
In Proc. of SIGIR 2009 (http://dl.acm.org/citation.cfm?id=1572006)

連続してD. Kellyの論文．クエリ推薦（いわゆる関連検索）とターム推薦（推薦された語をクリックされると元クエリに追加される）の比較．

  • クエリ推薦： “MS Windows” for “MS”
  • ターム推薦: “Windows” for “MS”

本質的には変わらないが，ターム推薦の方は”Windows”という語をクリックすると，元クエリ”MS”に追加され，”MS Windows”となるだけで，即座に検索は行われない．
一方で，”MS Windows”というクエリ推薦をクリックするとすぐにその検索結果が得られる．

得られた知見

今回は省略気味に55人の被験者を用いた実験で得られた知見だけを述べる．

  • 実際，あんまりこれらの推薦機能は使われない．
  • 難しい検索トピックでは両推薦共によく使われた．
  • クエリ推薦の方がターム推薦よりもよく使われる．
  • クエリ推薦の方がターム推薦よりも好まれる．（主観的な評価から）（性能に関する有意差はないが）
  • クエリ推薦は次にどのようなクエリを入力しようか考えるときに参考になる．（被験者のコメントから）

私感

思えば，この論文は一度勉強会的なところで紹介したのだが，やっぱりどうも物足りない感じがした．というか，未だにどっちでもいいと思っている．
ただし，query articulation，特に推薦がクエリ形成に与える影響に関しては興味深いものがあると思う．

9月
02

The Loquacious User: A Document-Independent Source of Terms for Query Expansion

Diane Kelly
Vijay Deepak Dollu
Xin Fu

In Proc. of SIGIR2005 (http://dl.acm.org/citation.cfm?id=1076112)

一般にクエリを入力することは難しい．だから，大抵のクエリは短く曖昧になってしまう．
ユーザからもしより多くの情報を引き出すことができたら，どれくらい精度が改善できるか，という話．
2ページ弱に及ぶIntroductionが実に秀逸．

背景

ここの紹介に力を入れたい．

ユーザはクエリを入力するのが難しいと思っている．[1]

Specified Searching （ユーザは検索対象を特定しなくてはならない．また，検索対象が得られるようなクエリを作らねばならない．）
このような検索で（一般的な検索）では下記のようなことは困難である．

  • どうやって知らないことを特定するか．
  • どのように欲しい情報が書かれているか想像しなくてはならない．
  • 重要な表現（語）を想像しなくてはならない．

When people engage in information-seeking behavior, it’s usually because they are hoping to resolve some problem, or achieve some goal, for which their current state of knowledge is inadequate.

長いクエリの方が精度はいい．しかし，現実のユーザのクエリは短い．

ユーザのクエリ入力支援には大きく二つの流れがある．

  • 適合フィードバック
  • クエリ拡張

ユーザはこれらの機能を欲しいというけど，実際にはこれらはあまり使われない…[2]
でも，最近は使われるようになってきたという報告もある．[3]

やったこと

2004 TREC High Accuracy Retrieval from Documents Track (HARD)の一部．

明らかにしたい点

  • クエリ，ユーザ，検索コンテキストのメタデータは精度改善に役立つか．
  • ユーザからのフィードバックは精度改善に役立つか．
  • パッセージ検索は精度改善に役立つか．（与えられる情報は自然文であるため）

検索トピックを決定後，トラック参加者に下記の情報を各トピックに対し最大3分間で入力してもらった．

  • Q1. 過去にどれくらいこのトピックで検索したか．
  • Q2. このトピックについてすでに知っていること．
  • Q3. なぜこのトピックで検索しようと思ったか．
  • Q4. このトピックに関する適当なキーワード．

結果

  • Q2,Q3,Q4の順で多くの情報（語数）が得られた．
  • Q2を使うとかなり精度が上がった．Q2,Q3,Q4の順に効果的．
    たとえば擬似適合フィードバックを行った場合よりもずっといい結果が得られる．
  • 追加情報でクエリ拡張したとき，その拡張されたクエリの長さと結果はきれいな正比例関係．

残念なことに，Q2,Q3,Q4の順でよかったことに関して「多い情報」がよかったのか，「質問の種類」がよかったのわからない．

私感

Q1とQ2,Q3,Q4の量に関しての相関を載せて欲しかったのに･･･
ユーザフィードバックの話と思ったら，クエリ長，もしくは，クエリ拡張の話だった･･･
Diane KellyはInteractive IRではとても有名らしい．

  1. [1] Belkin, N. J. (2000). Helping people find what they don’t
    know. Communications of the ACM, 43(8), 58-61. ↩
  2. [2] Belkin, N. J., Cool, C., Kelly, D., Lin, S. J., Park, S. Y., Perez-Carballo, J., & Sikora, C. (2001). Iterative exploration, design and evaluation of support for query reformulation in interactive information retrieval. Information Processing & Management, 37(3), 404-434. ↩
  3. [3] Anick, P. (2003). Using terminological feedback for web
    search refinement: A log based study. In Proceedings of the 26th Annual ACM International Conference on Research and Development in Information Retrieval (SIGIR ’03), Toronto, CA, 88-95. ↩
8月
11

Precision-At-Ten Considered Redundant

William Webber
Alistair Moffat
Justin Zobel
Tetsuya Sakai

In Proc. of SIGIR2008 (http://portal.acm.org/citation.cfm?id=1390456)

たまに思い出しては「このタイトルかっこいいな」と思う論文．心の中では「Precision-At-Ten is Redundant」と思っている．

検索指標の評価，というメタ的な研究．最近私もおもしろさがわかってきたような気がする．結論はタイトル通り．

P@10は無駄

検索指標の評価をするためにはまたその評価を考えなくてはいけないのだけれど，おそらく広く用いられている原則は「違いがわかる」ということである．一般にも言えるかもしれないが，ある物と別の物との違いが何であるかわかるということはそれだけ賢いと言うことである．（料理の味とか？）（しかし，一方で汎化も高度に知的な能力であるが．）
検索システム評価の文脈で言えば，検索評価指標はあるシステムと別のシステムの違いがわからなくてはならない．
このような考えから（おそらく），著者らはいくつかの検索指標を使って，検索システムのランキングを作成し，1) そのランキングに一貫性があるか，2) 他の指標との相関はどれだけあるか，について述べている．一貫性を見るのは，しっかりと違いがわかるのならば，どのようなデータを使っても同じ検索システムランキングは同じになるよね，という考え．

比較された検索指標は以下の5つである．

  • P@10 (上位10件の適合率)
  • RR (最初の逆順位)
  • RBP.95 (初めて聞いた)
  • AP (平均適合率)
  • nDCG (normalized Discounted Cumulative Gain) (和訳はなんだろう？ 正規減価累積利得？)

AP, nDCGと一緒にP@10もとりあえず乗せておきたい．そういう心情もあるかと思うが，それは無駄らしい．

1) そのランキングに一貫性があるか

TRECのデータセットを半分に割り，一方での「検索システムのランキング」と他方のものでケンドールの順位相関係数を求めた．結果は，RRが最悪，P@10が次に悪く，他のより複雑な評価指標ではより高い自己相関が見られている＝そのランキングに一貫性がある．つまり，一方のデータではAシステムはBシステムより優れていると言ったり，他のデータではBシステムはAよりいいと言ったりするのがP@10だったりRRだったりするわけである．（タスクによってはRRにこれをやらせるのは酷かもしれない．）

2) 他の指標との相関はどれだけあるか

RBP.95，AP，nDCGの間には高い類似性がある．特にAPとnDCGの相関は非常に高い．APとnDCGの自己相関が高いことも併せて，どちらも良いということが言いたいのだと思う．AP-nDCGに比べるとP@10-nDCGなどの相関は低い．

他にも使う検索トピック数を徐々に上げていくと，nDCGの自己相関は早く上がるが，P@10はそうでもない．さらには，トピック数をある程度増やすとnDCG-P@10の相関がP@10の自己相関とほぼ同じになってしまう．つまりは，P@10の自己相関は他の指標と同じくらい相関してしまう程度の低いものだという表れだと思われる．Redundantであるとはすなわち，P@10とnDCGを別々に計算したとしてもP@10ではnDCGを補うに足りないということである．（うまく論理立てられないが，P@10で検出できる差異~nDCG-P@10の差異なら，P@10が何かしらnDCGとは異なったものを見つけられるとしても，その違いがP@10の誤差の範囲になってしまったら意味がない．）

私感

というわけで，P@10とnDCG, APを同時に使わないよう気をつけましょう．（文末に「この条件では」という注意書きはありますが．）
ところで，APとnDCGは互いに補い合ったりするのでしたっけ？

似た種の論文にこの論文の著者の一人で，MSRAでのメンターであった酒井氏の「Alternatives to Bpref」[1]がある．こちらはまたの機会に．

 

  1. [1] T. Sakai. Alternatives to Bpref, In Proc. of SIGIR2007. ↩
8月
11

Competition-based User Expertise Score Estimation

Jing Liu
Young-In Song
Chin-Yew Lin

In Proc. of SIGIR 2011 (http://portal.acm.org/citation.cfm?id=2009975)

記念すべき最初の論文紹介はMSRAの時の友人によるExpertに関する論文．

問題

Q&AコミュニティでユーザのExpert度を計算したい．

既存研究としては例えば下記がある．

  • ユーザのQとAの数をカウント [1]
  • ユーザのベストアンサー数をカウント [2]
  • リンク解析による方法 （おそらくHITSによるHub-Authority発見） [1] [3]

 

方法

基本的なアイデアは「複数ユーザが1つの質問に回答して，その中からベストアンサーが選ばれるというプロセスを競争と見なせば，そのユーザ同士の間に格付けが生じる．これをExpert度計算に利用する．」というものである．シンプルでありながら既存の研究が扱えなかった，回答者間の暗黙的な競争(competition)がモデル化されている．

CQA独自の設定ではあるが，ある質問qに対して複数の回答者A=\{a_1, a_2, \ldots\}が回答を行ったときに，そこにはR=\{(a_i, a_j), \ldots\}といった関係が生じる．(a_i, a_j)はa_iはa_jに勝った，すなわち，a_iの回答はベストアンサーとなり，a_jの回答はベストアンサーにならなかったという関係である．このデータを各qから収集することによって，あとは適当なアルゴリズム（論文中ではTrue skill[4]とSVMの2つが用いられている）によって，各回答者a_iのExpertise scoreを計算することができる．

また彼らはExpert scoreの質を評価する方法についても提案を行っている．彼らはExpert度を直接的に評価する方法に関してはあまり肯定的でなく，付与できるグラウンドトゥルースの量の問題やその困難性（他者のExpert度を人間が評価できるか？）を指摘している．そのため，彼らは「より優れたユーザ（Expert度の高いユーザ）はより良い回答ができる」という基本的な理念に基づき，MRRやDCGに似た評価手法を用いることを提案している．

知見

この論文の1つの優れた点は，Expertise scoreに関する緻密な分析である（事実，第1著者は第2著者と毎日のように議論していた）．データにはYahoo! JapanのYahoo!知恵袋が利用されている．特にNTCIR-8 CQA taskで用いられてたデータセットが用いられ，このデータには4人の評者による回答品質情報が付与されている．ベストアンサーは質問者の主観によるとこ ろが大きく，バイアスが懸念されたためにこのようなデータセットが作成されたという．

主な知見は下記の点であると思われる．

  • ベストアンサー比率（ユーザの回答のうち何パーセントがベストアンサーか）を単純に用いたものでもExpert度をかなりいい感じに推定できる（HITSやPageRankを回答者-質問者間リンク上で行った場合よりも精度は良かった）
  • ベストアンサー比率はすごいユーザとすごくないユーザを分けることはできるが，中間層のExpert度判定には向いていない．
  • ベストアンサー比率と提案手法を比べた場合，全ユーザをふくめると，あまり差がない（むしろ，負ける場合もある）．
  • 提案手法，すなわち，回答者間の関係を考慮した手法はアクティブユーザ（回答数50件以上）のExpert度計算においてその効果を発揮する．このとき，ベストアンサー比率よりも有意に優れた結果が得られる．（先の，ベストアンサー比率はおおざっぱな計算はできるが細かい計算に向いていないことに関連．）

最後にベストアンサー比率と提案手法の判別能力(Discriminative Power)についても議論している．判別能力とはある正解データ(a_i,a_j)が与えられたときにその2つをどれほど区別できるかという能力である．（情報検索の評価尺度で言えば，2つの異なる検索システムに対し，どれほど異なった評価を下せるか，というもの）．彼らはある興味深い手法[4]を用いており，それは一方が判別するのが難しいと思う正解データを他方に与え，それを解かせるという，判別能力の比較実験である．結果として提案手法がベストアンサー比率よりも判別能力において優れているということが明らかとなった．

 

私感

1本ちゃんと読んで適当な文にするのは骨が折れる．このペースでやったら間違いなくすぐ止めそう．もっと適当に書こうと思う．

さておき，ソーシャル的な流行は収まらず，CQAやTwitterなどなどまだ論文は出そうである．また，Expert度判定に関連し，情報ではなく人を探し，その人に回答してもらおう，という流れもなんとなくあるようである．（たぶん．） （個人的にはあんまり好きじゃないが．）答えの品質情報をガリガリと推定しましょうみたいな話になるとあんまりおもしろくないのだが，CQA独自の点，例えば，ベストアンサーがいかに主観的に決定されるかとかはおもしろい．（この[5]論文でやられているようだが，なんだか結果が芳しくない＝あんまり影響ない．こちらも関連するかも[6]．余談だが←の著者はSIGIR2011のベストペーパー受賞者．）

 

 

  1. [1] J. Zhang, M. Ackerman, and L. Adamic. Expertise networks in online communities: structure and algorithms. In Proc. WWW, pages 221–230. 2007. ↩
  2. [2] M. Bouguessa, B. Dumoulin, and S. Wang. Identifying authoritative actors in question-answering forum: the case of Yahoo! answers. In Proc. SIGKDD, pages 866–874. 2008. ↩
  3. [3] P. Jurczyk and E. Agichtein. Discovering authorities in question answer communities by using link analysis. In Proc. CIKM, pages 919–922. 2007. ↩
  4. [4] R. Herbrich, T. Minka, and T. Graepel. TrueSkill: A Bayesian skill rating system. In Proc. NIPS, 20:569–576, 2007. ↩
  5. [5] Chirag Shah, Jefferey Pomerantz. Evaluating and Predicting Answer Quality in Community QA, In Proc. of SIGIR2010. ↩
  6. [6] E. Agichtein, C. Castillo, D. Donato, A. Gionis, and G. Mishne. Finding High-Quality Content in Social Media. WDSM’08, 2008. ↩
Go back to top