確率的情報検索について

概要

情報検索の分野でBüttcher本と呼ばれるInformation Retrieval: Implementing and Evaluating Search Engines*1という本がある。確率的な情報検索モデルについて知りたくなったためこの本の8章と9章を読んだのだが、これが想像以上に素晴らしかったのでScrapboxのメモを編集しながら久々にブログを書くことにした。

内容的にはProbability Ranking Principleと呼ばれる原理から始まり(TF)IDF, BM25, 適合性フィードバック, クエリ拡張(Query Expansion)へと綺麗に繋がっていく。この分野は歴史があってやや強引な仮定も所々あるのだけど、その論理の展開が工学的な視点という意味で現代でもとても参考になる。以下その詳細と最後に感想を述べておく。

確率ランキング原理について

Probability Ranking Principle

  • (クエリに対して)関連度が高い文書をランキング(降順)で返すことがユーザの満足度を最も高めることに繋がるというもの

この原理に従って議論を進めていく。まず問題となるのは、あるクエリに対して対象の文書がどのくらい関連しているかをどのように確率で示すかということである。

この問題を解くため準備も兼ねて以下を考える。

準備

文書とクエリを表す確率変数として D, Q, 関連度を示す2値を取る確率変数として Rを導入して p(R=1|D=d,Q=q)を考える。
以下 D=d,Q=q DとQとして、 R=1 r, R=0 \bar{r}で簡約する。

ベイズの定理を使うと

\displaystyle p(r|D,Q)= \frac{p(D,Q|r)p(r)}{p(D,Q)}, \displaystyle p(\bar{r}|D,Q)= \frac{p(D,Q|\bar{r})p(\bar{r})}{p(D,Q)}

とできる。ここで logit(p)=\log(\frac{p}{1-p})を導入する。

  • ここがまず一つ目のポイントだろう。 logitは順序を維持した写像(Rank-equivalent transformations)なので以下はこの値を考える。

ある文書とクエリが与えられたときの r \bar{r} logitは、 p(\bar{r}|D,Q) = 1 -  p(r|D,Q)とすると

\displaystyle \log{\frac{p(r|D,Q)}{p(\bar{r}|D,Q)}} = \log{ \frac{p(D,Q|r)p(r)}{p(D,Q|\bar{r})p(\bar{r})}}

となり、ここで p(D,Q|r) = p(D|Q,r)p(Q|r)とできるから、さらに式変形すると

\displaystyle \log{\frac{p(r|D,Q)}{p(\bar{r}|D,Q)}} = \log{\frac{p(D|Q,r)p(Q|r)p(r)}{p(D|Q,\bar{r})p(Q|\bar{r})p(\bar{r})}} = \log{\frac{p(D|Q,r)p(r|Q)}{p(D|Q,\bar{r})p(\bar{r}|Q)}}

で表せる。展開すると

\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}} + \log{\frac{p(r|Q)}{p(\bar{r}|Q)}}

になるが、第二項目の値は文書Dに関連しないので無視できる。

以上からPRPの元では各文書に対して

\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}}...(1)

この値を求めてランキングにして並べればよいことになった!

  •  p(D|Q,r)のまま考えるのでなくlogitにすることで考えやすくなるというのは参考になる。

Binary Independence Modelの導出

ここで文書Dの再定義を行う。 D = (D_1, D_2..)というベクトルで表現し、各要素は語彙となる単語が出現したら1, そうでないときに0をとる確率変数とする。

  • 文書Dは構成する単語で表現できると考えている

ここで強い仮定が2つ出てくる。

仮定1

Assuption T: Given relevance, terms are statically independent.

  • 文書に出現する単語(term)は互いに独立しているというもの。BoWでお馴染み。
  • この仮定により(1)は簡単になる。

さてこの仮定のもとで(1)の p(D|Q,r)

\displaystyle p(D|Q,r) = \prod_{i=1}^{|V|}p(D_i|Q,r)

となり、同様に \bar{r}も同じ処理をできるので結局

\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}} = \sum_{i=1}^{|V|} \log{\frac{p(D_i|Q,r)}{p(D_i|Q,\bar{r})}}

となる。だいぶ簡単になってきた。

仮定2

Assuption Q: The presence of a term in a document depends on relevance only when that term is present in the query.

  • ユーザのニーズと関連文書を紐づけるのはクエリのみである
  • 要はクエリに対応した単語によって関連性が決められるということ

この仮定を取り入れることで先ほどの式を計算することがかなり容易くなる。全ての語彙に対して計算するのでなく、クエリの単語だけを対象に計算すれば良くなったため。

具体的にクエリQをみると Q = q_i q_i=0となる場合は上記の仮定で考慮しなくて済むわけだから、その場合は \log{\frac{p(D_i|Q,r)}{p(D_i|Q,\bar{r})}} = 0でよい。

結局Queryとして出現しているtermだけが対象になるので q_i=1を簡略して

\displaystyle \sum_{t \in q}^{} \log{\frac{p(D_t|r)}{p(D_t|\bar{r})}}

と書ける。

次に文書Dについて個別にみていくと、文書の中にはクエリとなるtermを含まないものもあるので

\displaystyle \sum_{t \in q}^{} \log{\frac{p(D_t=d_t|r)}{p(D_t=d_t|\bar{r})}} - \sum_{t \in q}^{} \log{\frac{p(D_t=0|r)}{p(D_t=0|\bar{r})}}

としたい。そして第二項は仮定2から定数とみなせる(関連性はクエリから決定されるので)

ここでクエリを含む文書とそうでない文書で分けて考える。なおかつ第二項目を0にするために両方の項に工夫を加えると。。

\displaystyle \sum_{t \in (q \cap d)}^{} \log{\frac{p(D_t=1|r)p(D_t=0|\bar{r})}{p(D_t=1|\bar{r})p(D_t=0|r)}} - \sum_{t \in q \backslash d}^{} \log{\frac{p(D_t=0|r)p(D_t=0|\bar{r})}{p(D_t=0|\bar{r})p(D_t=0|r)}}

となり第二項は0なので結局

\displaystyle \sum_{t \in (q \cap d)}^{} \log{\frac{p(D_t=1|r)p(D_t=0|\bar{r})}{p(D_t=1|\bar{r})p(D_t=0|r)}} ...(2)

となる!これがBinary Independet Modelとして知られるモデルである。

IDFが導かれるまで

(2)を \sum_{t \in (q \cap d)}^{} w_tとおいて、 p(D_t=1|r) p_t, p(D_t=1|\bar{r}) \bar{p_t}と置くと

\displaystyle w_t = \log{\frac{p_t(1-\bar{p_t})}{\bar{p_t}(1-p_t)}} (= \log\frac{p_t}{1-p_t} + \log\frac{1-\bar{p_t}}{\bar{p_t}})

と変形できる。この方程式はRobertson/Sparck Jones formulaと呼ばれる。

ここで全文書の数を N, tを含む文書の数を N_t, 関連文書の数を N_r, 関連文書かつtを含むものを N_{t,r}として、 p_t, \bar{p_t}最尤推定を使うと

\displaystyle w_t = log \frac{N_{t,r}}{N_r - N_{t,r}} + \log\frac{N - N_r - N_t + N_{t,r}}{N_t - N_{t,r}}

が成り立つが、ここで N N_t, N_r N_{t,r}の関係を考えると前者は後者に比べてかなり大きい値を取ると想定できる。すなわち

\displaystyle w_t = logit(p_t) + \log\frac{N-N_t}{N_t}

とみなしてもよいだろう。

CroftとHarper(1979)は p_t = \frac{1}{2}かつ N_t Nに比べてかなり小さいと仮定できることから w_t = \log\frac{N}{N_t}を導いた。これは標準的なIDFである。

  • メモ:  p_t p(D_t=1|r)だったわけだから、 p_t = \frac{1}{2}というのは関連文書にクエリが出現する確率は半々ということ。必ずしも関連文書にクエリが出現するわけではないからこれは妥当な仮定とされているが、適合性フィードバックによってこの確率をもっと正確に見積もることはできる。これが適合性フィードバックのベースの一つとなる。

TF(単語頻度)の扱い方

Binary Independence Modelの導出のところまで戻ると文書Dは各単語が2値の確率変数を持つベクトルとして表現されていたのだった。単語の頻度を考慮するために各単語の頻度 F_tを確率変数として D=(F_1,F_2...)というようにさらに再定義する。

Binary Independet Modelの式は

\displaystyle \sum_{t \in q }^{} \log{\frac{p(F_t=f_t|r)p(D_t=0|\bar{r})}{p(F_t=f_t|\bar{r})p(D_t=0|r)}}

となる。さて関連文書と非関連文書の単語頻度を確率変数として扱いたいわけだが、どのようなモデルを考えればよいか。

ここで以下のようにElitenessを新しい概念として導入する。

Elitenessの導入

 p(F_t=f_t|r) p(F_t=f_t|\bar{r})を考えたいわけだが、ここでeliteという概念を導入する。

  • 文書があるトピックについて論じているときそれはelitenessを持つと考える
  • そしてelitenessは単語頻度に影響を与えると考える

すなわち関連文書の単語頻度はelitenessを導入することで、それぞれ別の確率モデルから単語頻度が決まるとみなすことができる。そして単語頻度を決める分布としてポアソン分布を仮定する。

簡易的なTwo-Poisson Model

Two-Poisson Modelの詳細については本書を参考にしてほしいが、RobertsonとWalker(1994)がTwo-Poisson Modelに期待される性質を満たした簡易的な重み付けとして

\displaystyle  \sum_{t \in q }^{} \frac{f_{t,d}(k_1+1)}{k_1+f_{t,d}} w_t ...(3)

を提案している。kはパラメータで通常1から2の間の値が用いられ、k=1.2が論文ではよく採用される。

  • Q. なぜ対数オッズである w_tに重みを掛けて良いの?
  • Q. ポアソン分布の導入がなぜ最終的に↑の式になるの?
    • A. Two-Poisson Modelが直接簡易式になるわけではなく、Two-Poisson Modelが w_tに対して及ぼす影響と同じ性質を持つ式を代わりに取り入れたということ。こういう技もあるんですね。

 f_{t,d}は単語の頻度を示すがこれがとても大きくなっても重みは (k_1 +1)w_tに留まる。要は単語頻度が増えるに従い重みがsaturateするような関数となる。

  • 関数の特徴を調べて簡単なもので置き換えるのはなるほどという感じ。

ちなみにBM11の頃の論文だと  \sum_{t \in q }^{} \frac{f_{t,d}}{k_1+f_{t,d}} w_t となっていてサチることがわかりやすい。(k+1)の項は定数になるのでランキングに影響は及ぼさないが f_{t,d}の値と対応づけやすいようにするための工夫だそうだ。

以下の論文にこの辺りの事情が書いてある(p.361あたり)

BM25について

前述した(3)は文書の長さを加味していなかった(ポアソン分布を導入したときに全文書は同じ長さだと仮定していた)。
文書の平均長を使って以下のようにスケーリングさせる。

\displaystyle f'_{t,d} = f_{t,d} * (l_{avg}/l_d)

しかし長い文書の方が質の高い文書である可能性が高いと想定することもあるだろう。パラメータbを導入してスケーリングの影響度合いを調節できるようにする。

(3)と上記をまとめると以下の重み付けの式が導出できる。

\displaystyle  \sum_{t \in q }^{} \frac{f_{t,d}(k_1+1)}{k_1 ( (1-b) + b(l_{avg}/l_d) )+f_{t,d}} w_t

これはBM25として知られている。パラメータとなるbは0.75がよく使われるらしい。

  •  (l_{avg}/l_d)がbにかかっているのは f_{t,d}に元々かかっていたものが約分されてるから。

適合性フィードバックによる拡張

最後に確率的検索モデルが適合性フィードバックについてどのように方針と理論的土台を与えるかを簡単にメモ。

これまで検索モデルは以下の2点で改善の余地がある

  • (2)式での p_tに対する見積もり
  • ユーザが潜在的に想定しているクエリの追加(Query Expansion)
    • Assuption Qによって適切なクエリ拡張は関連性に対して良い影響を及ぼすだろう

Term Selectionによる明示的な適合性フィードバックも解説されているが、擬似的な適合性フィードバック(Pseudo-Relevance Feedback)についての記述が秀逸だったのでメモする。

擬似的な適合性フィードバック(Pseudo-Relevance Feedback)について

適合性フィードバックはユーザによる明示的なインタラクションを必要とするが、ユーザはこのような作業を好まないとされている。
Pseudo-Relevance Feedbackは、上位k(=20)件の文書を関連文書と仮定しm(=10)個程度の特徴語を抽出し、元々のクエリに追加するというものである。

ポイントになるのは以下の考え。

k=20とすると擬似的適合性フィードバックの仮定から n_{r} = 20とできるから、各単語の n_{t,r}をカウントすることで p_tを推定することができる。さらに N, N_tはわかっているわけだから、Robertson/Sparck Jones formulaがこの手法で拡張できることがわかる!

  • 具体的には拡張するクエリ(元々のクエリも含む)の p_tを求められることと、ユーザの入力したクエリを関連文書の単語で拡張できる。なお拡張クエリの重みは1/3程度にすると実証的に良いようだ。

Pseudo-Relevance Feedbackは再現率と精度に良い影響を与えることが知られており、本書ではBM25にPRFを組み合わせた形式が有効であることが示されていた。

感想など

冒頭で述べたように仮定や導入しているモデルにナイーブさがあるが、どうしてもヒューマンファクターが絡みがちな情報検索という分野に確率的な視点を導入することで、不確かさについての議論がしやすくなる点は評価したい。個人的にIIR本よりも例が豊富で記述もわかりやすいので好み(といってもIIR本は日本語訳版しか読んだことはないんだけど)。

あとメモを書き上げてから他のひとが同じ章の記事を書いてる*2ことに気づきました。自分のメモと見比べてみると視点の違いとかが垣間みえて面白いですね。

ドワンゴを退職しました

2019/2/28をもって株式会社ドワンゴを退職しました。

ドワンゴにエンジニアとして新卒入社して今年で約4年になります*1。色々と注目度の高い会社で様々な経験をさせてもらいました。ここでは備忘録の役割も込めて、何をやってきたか・どんなこと感じたかを書いていきたいと思います。

何をやってきたか

初年度はドワンゴの教育事業であるN予備校の企画開発とAndroidアプリの開発、2年目以降はN予備校やniconareといった新規サービスのインフラ構築やSREを担当していました。AndroidからSREに転向したのは一度フロントエンドから離れたところで経験を積んでみたかったというのがあります(当時人数が少なくて大変そうだったというのもある)。

結果的にネットワークなどの基礎的な部分から負荷対策、例外やアクセスログ監視、オンコール対応、パフォーマンスの改善といった、今でいうところのSRE的なものの最先端を追うことができ、一歩離れた視点からアプリケーション開発を見直すことができました。特にDevOpsでいうところのOps部分を垣間見ることができたのは本当に良かったと思います。

直近はTerraformを使ってAWSのインフラを構築したり、既存のEC2で動いているアプリケーションをコンテナ化してCI/CDの改善を行ったりFargate上で動かして運用するといったことをやってました。全体的に大企業ならではの信頼性やアクセスログのトレーサビリティが要求されるところがあって、そのあたりはベンチャーでは身に着けることが難しい内容の経験を積めたと思います。

ドワンゴという会社について

多くの方がブログで言及されている通り、ドワンゴでは真の裁量労働が行われています。自分がとても恵まれた部署にいたからかもしれませんが、待遇や環境に関して不満はありませんでした。

サービスリリース前は忙しい時期ももちろんありましたが、基本的には昼頃出社して21時頃帰る生活で、ラッシュ時間を避けることができたため出社時は電車で座りながら本や論文を読んでいました。全体的にエンジニアが働く環境としてはかなり良いのではないかと思います。

超会議について

何かと話題になりがちなニコニコ超会議ですが、せっかくなので少しばかり触れておきましょう。

ニコニコ超会議について皆さんはどんな印象を抱くでしょうか。実を言うと自分は入社するまで超会議というものに参加したことがありませんでした。2009年頃からプレミアム会員で動画も生放送もほぼ毎日使っているヘビーユーザでしたが、リアルのイベントはどこか距離を感じていたためです(会場が物理的にも遠かったというのもある)。

もう4回ほどスタッフとして参加していますが超会議ほど参加してみないとその良さがわからないものもないんじゃないかと今では思っています。

確かに今年で8回目というのあって多少マンネリ化してきている部分もあるとは思いますが、去年なら超バーチャルYouTu"BAR"ブースはものすごい盛況でしたし、超コンパスブースのようなゲーム系のブースの盛り上がりが凄かったのを覚えています。去年の超会議の来場者数が過去最大だったのはニコニコの可能性を示しているともいえるでしょう*2。あと休憩時間に超歌舞伎を見たり、超ボカニコステージというのが個人的に毎年楽しみなので時間を見つけては参加していました。

もちろんなかなか重労働だし大変なところもあります。個人的に一番大変なのが始発で出発しないとスタッフ集合時間に間に合わないので朝5時には起きないといけないことでしょうか*3

去年は超クリエイターズLab.というブースでスタッフとして参加していました。「うp主ふれあいセンター」という投稿者同士で交流できる場所で、投稿者プロフィール帳を書いてもらったり自分の投稿した動画を流してもらうという企画をkoizukaさんと一緒にやっていました。客寄せからブース説明まで行う必要があったので(ちょっとした営業気分)なかなか大変でした。とはいえこのような仕事は志願制で、このような内容が嫌なら別なことをすることもできます。一昨年は超ニコラジというところで裏方をやったりしました。

投稿者とのコミュニケーションから

うp主ふれあいセンターという企画の性質上、動画投稿者の方とコミュニケーションすることができ、良い機会だったので雑談含みで色々と話を聞いていました。紹介される動画はカテゴリもジャンルもバラバラで、三年かけて一つの動画をつくった高校生くらいのひともいれば、スマホで撮った動画をスマホ上で編集して投稿するひともいました。全体的に年代層が若く、まだまだニコニコにも新しい投稿者のひとはいるし、自分の知らないジャンルがこんなにあるんだなあとあたらめて思ったのを覚えています。

最も印象に残っているのは日曜の夕方もう終わりに差し掛かったときのことで、とても良くできた動画の紹介が続いたとき、その場にいた見知らぬはずの投稿者同士で交流が始まったことです。その光景をみたとき僕は何か懐かしいものを感じました。

それは僕が20歳のときにニコ生で配信をしていたときの、名前も知らないツワモノたちがどこからともなく集まってきて、そのゲームについて熱い議論をするという言ってみればWeb2.0的な光景でした。最近すっかり自分が忘れていたインタレストグラフから生まれるコミュニケーションがそこにはありました。懐かしく思ったのは僕自身が過去にニコニコというプラットフォームで救われた人間だったというのもあるのかもしれません。

さて超会議で学んだのは、リアルイベントを通して量的な指標には現れにくいユーザの温度感やニーズを知ることはなんだかんだ今の時代でも重要ということです。

一見当たり前なことのように思えますが、このような質的なフィードバックを現場で捕まえにいくことを重視しているのがAWSだと思っていて、各国でやっているAWS Summitなどの場で彼らはきちんと企業の開発者のニーズを捉える努力をしています。ビジネスという面においてAWSGCPにはない強さを発揮していますが、この辺りの人間的な部分を重視した戦略がその成功要因として大きいのではないかと思っています。 

どうしても研究がやりたい

Menthas*4というニュース推薦システムを個人で開発していたというのもあって、情報検索や推薦システムの論文は卒業後もよく時間を見つけては読んでいました。そしてある日ふとCold-Start Collaborative FilteringというXiaoxue Zhao氏の博士論文*5を読んでとても感銘を受けてしまい、このことが博士課程進学への遠縁となりました。

またMenthasを作っていくうちに人間の可能性を広げるのは人間単体ではなく人間とアルゴリズムによるコラボレーションだと確信したことがあります。アルゴリズムが人間の視野を狭めるというフィルタバブルの問題は常に考え続けていましたが、アルゴリズムに頼らない情報収集という観点ではやはり限界があるし、結局はフィルタを超えて人間の能力を高めるという目標を持ったアルゴリズムを作れるかどうかなんじゃないかという結論に至りました。同様にインタフェースでも効率的ではあるが慣れない操作や見慣れていないアクションをどう受け入れるかという問題は残っていますし、まだまだ研究できる余地はあると思っています*6

というわけで次は最近流行りのGAFA..ではなく慶應SFCの増井先生の研究室に博士課程で進学します。この歳での進学はなかなかいばらの道ではありますが悔いのないように頑張ろうと思います。

最後にお世話になった皆様、本当に4年間ありがとうございました。

f:id:atria:20190304233119j:plain

またどこかで!

*1:正確には3年と11ヶ月なんですが。

*2:「ニコニコ超会議2018」リアル来場者数が過去最高の16万人超え! ネット来場者数も盛り返す - ねとらぼ

*3:もちろん近場に住んでいるひとはこの限りではありません

*4:https://menthas.com/

*5:多腕バンディット問題とMarkov Decision Processを組み合わせてコールドスタートな状態の推薦システムに対処するという内容。まだ完全に理解できてはいませんが素晴らしいです。

*6:例えば最近読んだものだと Supporting Novice to Expert Transitions in User Interfaces (https://dl.acm.org/citation.cfm?id=2658850.2659796) 辺りの話。この辺の話については別の機会に書きます