全文検索の精度とスコアについて
Groongaで学ぶ全文検索 2015-11-06に参加してきた。
今日のお題は「精度」。
精度とは
精度とは何か、参加者からはこんな意見が出た。
- ユーザーの満足度
- 思った物が探せてる
- もれなく検索できてる
- ごみがない
ここから@ktouさんの説明。精度に入る前に、再現率と適合率の説明があった。
再現率
検索した時に返すべき物があるはず。
例えば「京都」で検索した時、「京都」を含む文書は全部返って来てほしい（ここではそういうことにする）。ところがトークナイザーに形態素解析器を使っていて、「京都」で検索した時に「東京都」はヒットしないような設定にしていたりすることもある。こういう時、その「東京都」の文書は検索結果から漏れてしまうので、再現率を下げてしまうことになる。
再現率は、「検索結果で返ってくるべき物のうち、実際に検索エンジンが返した物の割合」。
適合率
上で「返すべき物」という話をしたので引き続きそれを使うと、「実際に返って来た検索結果のうち、返すべきだった物の割合」が適合率。
再現率を上げるためには、例えば登録している文書すべてを検索結果として返すことができる。そうすると「返すべき物」は全て含まれているので、再現率は100%になる。しかし、この結果はいらない物を多量に含んでいるだろうから、期待する結果からは遠い。この時適合率は低いということになる。
精度
さて、検索エンジンの精度の話をする時、この再現率と適合率が、よく指標として使われる。最初に上げた参加者みんなの精度のイメージのうち「ユーザーの満足度」「思った物が探せてる」はふわっとしてるけど、再現率と適合率は数値化できるので議論しやすい。
ところが、一般に、どちらかを上げるとどちらかは下がってしまう（らしい）。
特許検索はふつう、適合率を下げても再現率が重要になる。特許出願を考える際には既存の特許とかぶらないことを確認する必要があるが、その時には、漏れがあっては困るからだ。
現実の話
再現率と適合率はよく指標として使われるが、現実的には、この二つだけで精度検索結果のよし悪しを議論できるわけではない。
例えば検索して、結果が1000件あったとする。この時、ふつう、1000件全部は確認しない。全部を確認しないのであれば、「全体に対しての割合」である再現率や適合率は、その厳密な数値には意味がないことになる。
Googleでヒットした時に大事なのは、多くの場合1ページ目、せいぜい3ページ目くらいまでで、みんなそれを目指してSEOを頑張っていた。なので、4ページ目以降は、不要な検索結果ばかりで適合率が低かったとしても問題ない。
もちろんこれはGoogle検索はそういう選択をした、またウェブの一般的な検索はそれでいいことが多いだろうということで、ケースバイケースである。
精度を高めるよい検索結果を提示するには
追記。始め「精度を高める」という書き方で書いていた。しかし、他の人のまとめ（前半、講師の@ktouさんが説明をして、後半で各々自分の言葉でまとめるという勉強会。この日記もそのまとめとして書いている）を聞いているうち、これがよくない表現だと気付いた。精度はやっぱり再現率と適合率のことで、この節で話したいのは「再現率と適合率を考えるだけではユーザによい検索結果を提示することはできない」ということだからだ。
精度を上げるユーザーによい検索結果を提示するにはどうすればいいか、方法は一概には言えない。ユースケースごとに求められる精度のタイプが変わるからだ。
上で見たような「上位n検の結果だけが特に重要」みたいなケースではスコア付けが大事になる。スコア付けには（昔の）GoogleのPageRankや、ほかにTF、TS・IDF、BM25などがある。それぞれが何なのかは省略する。
確かPageRankは、各ドキュメントの被リンクの数などをスコア付けに使っていたと思う。それが「いい結果」ということでGoogleが受け入れられていった一因になっていた。
これはTF・IDFなどの、文書中のキーワードから導出した指標の限界を示唆している。@ktouさんはこのように、キーワードだけを使うのでは、精度はそれほどよくならないと思っているらしい。それよりも文書のメタデータを使ってスコアを考えるほうが現実的にいい結果が得られることが多い。
メタデータには例えばタグがある。
TF・IDFでは、「文書中のTFが高いつまりある単語が多いという時、その単語はその文書を特徴づけている」と考えている。IDFについては、「ある語がたくさんの文書に含まれているほど、その語は文書の特徴を表現していない」と考える。つまり「その文書の特徴は何なのか」ということが知りたい、その知りたいことの導出に文書中のキーワードを利用していることになる。本質的には文書の特徴が知りたいだけなので、書き手の用意したタグというのは、多くの場合キーワード由来の指標よりも、その特徴を顕著に表していることになるだろう。そうしたわけでタグは、検索結果の重み付けに使う指標として有効と考えられる。
他に位置情報も考えられる。渋谷を歩いててラーメンを食べたくなった時に、「ラーメン」と検索すると、渋谷のお店を扱った文書が出てきてほしい。仮に文書中に店舗名しかなくて、「渋谷」みたいな場所を示すキーワードがないとする。でも文書のメタデータに渋谷の経緯度があるとすると、それを利用して渋谷の店を検索結果の上位に出すことができる。
こういった文書のメタデータの他に、検索する人の情報を使うこともできる。今、Googleの検索結果は、（ログインしていれば）訪問した回数の多いページが上位になるようになっている。フェイスブックでの検索も、自分に関連のあるユーザーなんかが結果の上位に来るようになっている。上のラーメンの例でも、スマホからGPSによる位置情報を検索クエリーに乗せて使うことができる。
こういう風に、精度を高めるユーザーによい検索結果を提示するには、文書中のキーワードを使うだけでは、限界がありそうだ。
Groongaでのスコア付け
Groongaでは以下のスコア付けの方法が用意されている
- TF
- TF・IDF
- TFで、リミットありの物。TFは参考情報に使って、メインの重み付けの指標は別にあるといった場合。TFは文書の内容に応じて無限に増えていく（例えばヒットしやすい語を埋め込みまくった記事とか）ので、ある単語を書きまくるというスパムの餌食になりやすい。「その語を含んでいる」という事実は考慮しつつも、その影響を一定範囲に抑えるために、重みのリミットを、例えば2（数値はユーザーが決める）とかにしてしまうやり方。Groongaに特徴的で、@ktouさんはこの重み付け方法を持っている全文検索エンジンを他に知らないとのこと（ちょっと自身なさそうだったw）。
- メタデータに重みを付けてスコアに反映させるやり方（以下で説明）
最後のは例えば、居酒屋のテーブルがあったとして、
- 居酒屋A … 重みは海鮮：10
- 居酒屋B … 海鮮：5
- 居酒屋C … 中華：100
たいなメタデータを入れておく。
グルメサイトで「海鮮が美味しいお店の中から探す」みたいなフィルタリングをしている時は、どんなにその値が高くても、居酒屋Cは上位には出てこないだろう。その重みは海鮮ではなくて中華なのだから。
と、今日はここまで。
参加者の一人から「では、他製品と競争するにはメタデータの扱いが重要になるのか」という質問が出ていて、鋭いなあと感心した。
あと、自分の理解のまとめとしてこの日記を書いている間に、すごい面白そうな話が後ろで繰り広げられていたけど、書くのに忙しくて聞けなかった……。
TF・IDFはAND検索、OR検索で使われる
追記。参加者の一人のまとめ発表で、「TF・IDFはAND検索、OR検索で使われる」といった物があった。まとめを書いている時に出た疑問を@ktouさんに質問して、そのフィードバックを入れたらしい。
これはぱっと見た時にすぐ意味が頭に入ってこなかったが、分かったらもやもやがすごいすっきりした。
TFは分かるけどTF・IDFの話が全文検索で出てくるのがぴんとこなくてもやもやしていた。僕がTF・IDFを知ったのは全文検索ではなくて類似文書検索、なので定義やその意味を聞かれれば一応答えられるけど、それが全文検索でどういう意味を持つのか、と聞かれると詰まってしまう（はずだとこの時に気付いた）。
IDFを考える気持ちは、ある文書とある文書を比べる時に「その二つに共通の特徴でも、そもそも全文書、多数の文書に共通の物は、さほど大事な特徴ではない」ということだ。二つ（以上）の文書を比べる時に出てくる概念なのである。でも全文検索では、ヒットした文書同士を比べるようなことはしないなのにDF・IDFを使っているのでもやもやしていた。
これがAND検索、OR検索のことを考えると、つまりクエリーが複数あって、それぞれについてヒットする文書群があって、その文書群の文書について何らかのスコア付けをする、ということになる。そう考えるとTF・IDFを使うのは自然に思えた。
またこういう風にも捉えられる。AND検索にせよOR検索にせよ、クエリーを「複数の単語からなるごく短い文書」だと考えられる。この「ごく短い文書」に似ている文書というのが、すなわち検索結果の文書なのだ。やはり、類似文書検索で使われる手法を使うことは、自然に思える。
他の人の（ちゃんと疑問を疑問と認識できる）視点で出てきたフィードバックがその場でシェアされるの、ありがたいことである。
BM25
追記二。（この日記を含む）みんなのまとめの発表が終わった後、解説が省かれていたBM25というスコア付けの方法も説明してもらった。
BM25はTFとIDFのほかに、文書の長さも考慮する指標。ある単語について「長い文書の中にたくさんあるとして、それはそういうものだろう。短い文書の中にたくさんあるようだと、それはその文書を特徴付けているているキーワードだろう」という考え方で計算する物らしい。
これはある種のスパムブログなんかを弾くことができる。スパムブログで「これ入れとけば検索上位になるっぽい」という単語をひたすら書き連ねているようなやつ、それは文書自体も長くなるので、その分スコアが下がる。
ただ計算量は増えて、計算量としては「TF < TF・IDF < BM25」という順番になっている。