エムスリーエンジニアリンググループ AI・機械学習チームの中村(@po3rin) です。 好きな言語はGo。仕事では主に検索周りを担当しています。最近、ユーザーの検索体験の向上のために、以下の検索評価に関する本を読んでいました。
- 作者:酒井 哲也
- 発売日: 2015/05/19
- メディア: 単行本
そこで今回は検索評価指標の1つであるsDCG (session-based Discounted Cumulative Gain)を使ってエムスリーの検索ログから体験の悪かった検索を抽出してみたのでその方法を紹介します。
現状の検索監視
エムスリーでは検索ログを分析して検索のクオリティを改善するための活動に役立てています 例えば下記のような項目をチェックしています。
- 直近30日の検索Word (検索回数、検索人数、クリック数)
- 直近30日で検索結果0件表示のクエリ
この項目から検索結果が出ていないものや、クリック率の低いクエリを調査することで検索エンジンの質を高めていくことが可能です。
現状の検索監視の問題
上に挙げた項目は単発のクエリ結果にのみ焦点を当てているため、複数回のクエリ修正を跨いだユーザーの検索行動にフォーカスした検索監視ができていません。 例えば、初回のクエリでは期待する検索結果が出ず、クエリを何度も修正して再検索しているパターンを考えてみましょう。このような検索行動は単発のクエリを監視しているだけでは気づけません。そのためクエリ単発での評価ではなく、一連の検索行動(検索セッション)に注目した評価指標が必要です。そこで今回は検索セッション評価指標であるsDCG (Session Discounted Cumulative Gain)を試してみました。
nDCG
sDCGの紹介の前にsDCGの基礎となる検索評価指標であるnDCGを紹介します。もうすでにご存知の方は飛ばしていただいて構いません。
nDCG (normalized Discounted Cumulative Gain)は検索結果順位に依存したスコア減損を考慮した検索評価指標です。
例えば検索結果には検索意図に対して高適合、部分適合、非適合の文書が混ざっているとします。今回はクエリに対してどの文書を適合とするかの詳細には踏み入りません。
このように複数の適合グレードを持つ検索に対する評価指標として使えるのがDCG (Discounted Cumulative Gain)です。簡単に言うと高適合文書が上位にランクする検索結果のスコアが高くなるように調整する検索評価指標です。数式でみていきましょう。検索結果順位に依存したスコア減損を与えていることを確認できます。
は
における利得であり、ここでは高適合に3点、部分適合に2点、非適合に0点を設定しています。
は検索結果の観測長です。実際に下図の検索結果では利得の合計は同じですが、高適合が上の方にある検索結果の方がスコアが高くなっています。
このDCGの最大値を1に正規化したものがnDCG (normalized DCG)です。正規化するためにはまず下図のように適合グレード順に文書が並んだ検索結果を考えます。これの結果は検索意図に完璧に沿っている理想的な結果なので、これを理想リストと呼びます。
nDCGでは理想リストのDCGを計算してその値を使ってDCGを割り算することでDCGを正規化しています。
sDCG
nDCGの説明が終わったところでいよいよ本題のsDCG (session-based Discounted Cumulative Gain)です。sDCGはnDCGを拡張した検索評価指標であり、クエリ修正やクエリ推薦による再検索を考慮できる評価指標です。例えば初回クエリの結果とクエリを修正した場合の結果、下図のようにユーザーがクリックしたとします。今回はクリックしたドキュメントを適合文書、それ以外を非適合文書と考えます。
このような検索セッションを評価するために、sDCGではユーザーの行動に3つの仮定をおいています。
線形横断
ユーザーは検索結果を上から順に調べていく。
最下位クリックにおける検索結果の破棄
線形横断の仮定のもと、各検索結果でクリックしたランクのうち最下位のランクで検索行動を中断するか、クエリ修正を行うとする
クリック＝適合文書
クリックされた各文書は適合文書であるとする。もちろん、この仮定は拡張でき、文書の閲覧時間などでも補正できる。
このようなユーザーモデルを仮定すると、ユーザーは実質的に各検索結果を連結した連結リストを走査していると考えられます。
sDCGは下記のように連結リストに対するDCG計算にクエリ数による減損を与えたものです。
ここでは連結リストランキング
が何個目のクエリで得られたかを表します。つまりここでクエリ数による減損を行なっています。上の式を見るとクエリ数による減損の対数の底は4ですが、ここはクエリ数による減損をどのくらい強くかけたいかによって調整できます。
sDCGを理想リストのsDCGで除算すると最大1に正規化されたnsDCG (normalized sDCG)を計算できます。検索セッションにおける理想リストは下図のように初回クエリで全ての適合文書が取得できた場合と設定します。
nsDCGを実際の検索ログに使ってみる
nsDCGの計算には実際に弊社の検索クエリでどれほど有効か実験してみました。nsDCGの計算に必要なのは下記のデータのみなので、検索ログが充実していればすぐに計算可能です。
- クリックした記事が検索結果の何番目にランクされたか
- クエリ文字列
- 検索した時間
また、sDCGを使う際にもっとも重要なことは検索セッションをどのように定義するかです。1人のユーザーの検索開始から30分を検索セッションとする方法や、時系列でクエリのn-gramが一致していたら検索セッションとする方法や、形態素解析でのセッション判定もあり得ます。今回は単純に「ユーザーの前回の検索からprefix2文字が変わっていないこと」と定義しました。
この検索セッション定義の上でsDCGを計算して、nsDCG(sDCGを最大1になるように正規化)が0.3以下のセッションを抽出してみました。下記のようなスコアの低い検索セッションを確認できました。
*「コロナ」-> 「コロナワクチン」
「コロナ」では多くの記事が引っかかってしまうのでより検索意図を表した「コロナワクチン」で再検索している。
*「ワクチン 副作用」->「ワクチン 成分」->「ワクチン 成分 mRNA」
上位をクリックしている(高適合文書のランクが高い)がクエリ修正を何度も行なっている。
*「国立医学部 私立医学部」->「国立医学部 私立医学部 マンガ」
国立医学部と私立医学部の違いを描いたマンガをみたことがあってそれをもう1回みたかったっぽい？ ある程度初回クエリの結果をクリックしたのちに初回クエリに「マンガ」を付け足して再検索している。
- 「弘前」
「弘前」と検索して100位までに散布している11記事をクリックしている。これは何か明確な目的のある検索というよりかは「何か"弘前"で面白いニュースないかな」とボンヤリと探索していたのかもしれない。
sDCGを使って感じたこと
今回対象にした検索アプリケーションでは1単語のクエリでたくさんスクロールして記事を見つけるという行動をする人が目立った。検索システムとしてクエリ推薦やクエリ補完を実装することでユーザーの負荷を下げられるかもしれない。
今回対象にした検索アプリケーションでは「面白そうな記事ないかな」と1単語クエリで検索巡回をする人もいるので、sDCGが仮定するユーザーモデルが完全にユーザーの行動を表現しているとは言い難い。欲しい回答を得たら検索行動がストップする確率が高いQ&A検索(弊社サービスでいうとAskDoctorsのような検索の方がsDCGが合っているかもしれない。
もう少しセッションの切り方や検索サービスにあった指標に調整することによって、問題の検索セッションを抽出する精度が上がりそう。特にクエリだけから検索意図が同じかを判定するのは面白いタスクかもしれない(まだ探せてないけどどっかに論文とかあるのだろうか)。
まとめ
nDCGの紹介からsDCGの導入までを紹介し、実際に検索アプリケーションに適用した例を紹介しました。次はよりsDCGが仮定するユーザーモデルに近い検索サービスで試してみるのも面白いかもしれません。sDCGで上手く問題の検索セッションを検知できるようになれば週1回Slackで通知して検索品質の検討なんかもできるかもしれません。
今回紹介したsDCG以外にもたくさんの検索評価指標が提案されているので皆さんも是非「情報アクセス評価方法論」を手にとってみてください。
- 作者:酒井 哲也
- 発売日: 2015/05/19
- メディア: 単行本
また、 今回紹介した評価指標の変化形(sDCG/qやesNDCG)などもあるのでぜひこちらの論文を読んでみてください！
Correlation Between System and User Metrics in a Session https://people.cs.umass.edu/~jpjiang/papers/chiir16_metrics.pdf
We're hiring !!!
エムスリーでは検索基盤の開発&改善を通して医療を前進させるエンジニアを募集しています！ 社内では最近、検索チームを中心に「Elasticsearch & Lucene コードリーディング会」が発足し、検索の仕組みに関する議論も活発です。
「ちょっと話を聞いてみたいかも」という人はこちらから！
Reference
「Cumulated gain-based evaluation of IR techniques」(nDCGの元論文) https://dl.acm.org/doi/10.1145/582415.582418
「Evaluating multi-query sessions」(sDCGの元論文) www.researchgate.net
「情報アクセス評価方法論」
- 作者:酒井 哲也
- 発売日: 2015/05/19
- メディア: 単行本
