ユーザー投稿型ドキュメントのタイトル多様性を考慮した検索リランキングを試す

エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(po3rin) です。好きな言語はGo。情報検索系の話が好物です。今回は多様性を考慮したリランキング手法と実際にPythonで実装を試した話をします。

課題
検索結果のリランキング
リランキング実装
まとめ
- We're hiring !!!
- Reference

課題

エムスリーのAskDoctorsというサービスではユーザーがお医者さんに直接質問ができるサービスです。質問できる以外にも、ユーザーは自分の症状や悩みに近い質問を検索できます。

www.askdoctors.jp

Askdoctorsの検索の問題点として、同じようなタイトルが並んでしまうという問題があります。ユーザーの投稿ドキュメントのタイトルには「~~について」など具体的な質問内容がタイトルから分からないことも多いです。

例えばAskDoctorsで「コロナワクチン」と検索すると、質問数が非常に多いため、似たようなタイトルが上位に並び、どれが自分が読みたい質問なのかが検索結果からは判断できません。下記はとある日のAskDoctorsの「コロナワクチン」での検索結果です。

コロナウイルスのワクチン
コロナウイルスワクチン
コロナウイルスのワクチン
コロナウイルスワクチン
コロナワクチン
コロナのワクチン
コロナワクチン
コロナワクチン
コロナワクチンをしても
コロナワクチン
コロナウイルスのワクチンについて
コロナウイルスワクチンについて。
コロナウイルスワクチンについて
コロナウイルスワクチンについて
コロナウイルスワクチンについて
コロナウイルスワクチンについて
コロナウイルスワクチンについて
コロナウイルスのワクチンについて
コロナウイルスワクチンについて
コロナウイルスワクチンと薬

こうなる理由としては、BM25のアルゴリズムの特性が挙げられます。簡略化のためにタイトルだけが検索対象の場合を考えると、BM25の計算では検索タームが出現するかつ、短いタイトルのスコアが高くなります。そのため、ドキュメントが多い、かつ、似たようなタイトルが多くなるユーザー投稿型のサービスの場合は上記のようにタイトルが似たようなものになってしまいます。特に弊社ではタイトルフィールドをスコアブーストしているので、よりタイトルが偏ってしまう傾向にあります。

特にAskDoctorsのような専門的な質問サイトでは質問が一言で言えない場合が多いので、タイトルが抽象的で似通ってしまう点も挙げられます。

余談ですが、フィールドごとにスコアブーストしたい場合は最近Elasticsearchにも入ったBM25Fアルゴリズムがおすすめです。BM25Fはタイトル、ボディなどのドキュメント構造を考慮に入れたBM25の自然な拡張です。BM25Fはターム頻度( $tf$ )をフィールドごとにフィールド重みを乗算して調整します。

BM25,BM25Fの解説に関しては下記の書籍が詳しいです。バイナリ独立モデルからのBM25、BM25Fの導入がかなり詳しく書いてあります。

情報検索 :検索エンジンの実装と評価

森北出版

Amazon

今回は検索結果のCTRを高めるという目的で、検索結果のタイトルを対象に多様性を高める手法に取り組んでみます。

検索結果のリランキング

検索エンジンから生成された結果リストをリランキングしつつ、クエリとの関連性を維持しながら多様性を高めることを考えます。

一番簡単なのは貪欲なリランキング方法です。アルゴリズムは下記は論文[1]からの引用になります。

f:id:abctail30:20211217131958p:plain — Kaminskas, Marius, and Derek Bridge. “Diversity, serendipity, novelty, and coverage: a survey and empirical analysis of beyond-accuracy objectives in recommender systems." ACM Transactions on Interactive Intelligent Systems (TiiS) 7.1 (2016): 1-42. より引用

簡単に説明すると検索結果リストから、リランキング結果リストに対してもっとも似ていないアイテムをリランキング結果リストに追加する処理を繰り返していく方法です。 $C$ は検索エンジンから返ってきた候補集合であり、 $R$ は最終的に返すリランキング結果リストです。このアルゴリズムは検索リランキングだけでなくレコメンデーションの多様性の文脈でも使われます[2][3]。

$f_{obj}$ 目的関数の実装は様々です。初期の実験では The use of MMR, diversity-based reranking for reordering documents and producing summaries[4]でMMR(Maximal Marginal Relevance)という手法を提案しており、元々の検索の関連度からすでにリランキング結果リストに追加されているアイテムとの類似度のなかで最大の関連度を引いたものになります。

$f_{obj}(i, R) = α \cdot rel(i) - (1-α) \cdot \max_{j \in R }sim(i,j)$

$rel(i,j)$ はアイテム $i$ の元々の検索エンジン上でのスコア(今回はBM25の値)です。 $sim(i,j)$ はアイテム $i$ と $j$ の類似度を表します。 $α$ は調整値であり、関連度か多様性どちらを重視するかを調整できます。

また、先に示した論文[1]などではリランキング結果リストにすでに含まれているアイテムまでの距離の平均を用いる手法が紹介されています。

$f_{obj}(i, R) = α \cdot rel(i) + (1-α) \cdot \frac{1}{|R|} \sum_{j \in R } dist(i,j)$

$dist(i,j)$ はアイテム $i$ と $j$ の距離を表します。2つの式で使っている類似度関数が違うので注意しましょう。 $sim(i,j)$ は類似しているほど値が高くなり、 $dist(i,j)$ は類似しているほど値が低くなります。

二番目に紹介した目的関数の方がリランキング結果リスト全体を考慮できますが、1つの非常に似ているアイテムの存在を軽視してしまう恐れがあります。

他の目的関数について知りたい場合は、Diversityについてまとまっている論文[1]がおすすめです。

リランキング実装

今回は先ほど紹介したアイテムまでの平均距離を使った目的関数を採用してPythonで実装してみます。

アーキテクチャ

今回はElasticsearchの結果をMMRでリランキングして結果を返す2段階構成を試します。

f:id:abctail30:20211217132257p:plain — 今回実装するリランキングアーキテクチャ

今回はElasticsearchを検索した結果リストのリランキングをPythonで実装してみます。 Elasticsearchからの結果は100件取得し、そこから多様化した20件の結果を抽出して返すことを考えます。

前準備

今回の実装では下記のモジュールを利用します。Pythonは3.9.0を利用します。

from abc import ABC, abstractmethod

import pandas as pd

import requests
from requests.auth import HTTPBasicAuth

from sudachipy import tokenizer
from sudachipy import dictionary

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

PythonでElasticsearchにリクエストしてドキュメントを取得します。この際に利用しているランキングアルゴリズムはBM25です。

data = {"from": 0, "size": 100, "query": {"match": {"title": "コロナ ワクチン"}}}

res = requests.get(
    "localhost:9200",
    timeout=10,
    json=data,
    auth=HTTPBasicAuth("user", "pass"))

ここからのちに使うためのmax_scoreとtitleのリスト、idのリストを生成しておきます。

docs = res.json()['hits']['hits']
max_score = docs[1:][0]['_score']

docs = {
    d['_id']: {
        'title': d['_source']['title'],
        'body': d['_source']['body'],
        'score': d['_score']
    }
    for d in docs
}
ids = list(docs.keys())

これでElasticsearchから返ってきた結果をリランキングする準備ができました。

TF-IDF vector

続いてドキュメントの類似度を計算するクラスを用意します。まずはTF-IDFベクトルを使った類似度計算を試してみます。TF-IDFの形態素を取得するために今回は形態素解析器のSudachiを使います。後ほど別の類似度計算を試すので、抽象クラスとして実装しておきます。

mode = tokenizer.Tokenizer.SplitMode.B
tokenizer_obj = dictionary.Dictionary().create()


def tokenize(text: str):
  return [m.surface() for m in tokenizer_obj.tokenize(text, mode)]


class Similarity(ABC):
  @abstractmethod
  def calcurate(self, doc1: str, doc2: str):
    pass


class TFIDFSimilarity(Similarity):
  def __init__(self, corpus: list):
    self.vectorizer = TfidfVectorizer(smooth_idf=True)

    noun_corpus = [' '.join(tokenize(c)) for c in corpus]
    self.vectorizer.fit_transform(noun_corpus)

  def calcurate(self, doc1: str, doc2: str):
    targets = [' '.join(tokenize(d)) for d in [doc1, doc2]]
    vecs = self.vectorizer.transform(targets)
    return cosine_similarity(vecs, vecs)[0][1]

試しに実行してみましょう。

corpus get_random_docs() # TF-IDFベクトル学習用のドキュメントのランダムサンプリング10000件
sim = TFIDFSimilarity(corpus=corpus)
print(sim.calcurate('病気になる', '病気になる')) # 1.0
print(sim.calcurate('病気になる', '病気を直す')) # 0.79786
print(sim.calcurate('病気になる', 'がん検診を受けました')) # 0.0

ちゃんと似ているものの値が大きく出てきました。

続いて、リランキングの責務を持つRerankerクラスの実装します。

class Reranker():
  def __init__(self, docs, max_score, similarity: Similarity):
    self.docs = docs
    self.max_score = max_score
    self.similarity = similarity

  def es_score(self, id) -> float:
    doc = self.docs[id]
    return doc['score'] / self.max_score

  def dist(self, i: int, j: int):
    text1 = self.docs[i]['title']
    text2 = self.docs[j]['title']
    return 1 - self.similarity.calcurate(text1, text2)

  def sum_dist(self, item: int, results: list[int]) -> int:
    return sum(self.dist(item, result) for result in results)

  def select_item_id(self,
                     candidate_items: list[int],
                     results: list[int],
                     alpha=0.5) -> int:
    max_score = -1
    max_score_item_id = -1
    for i in candidate_items:
      if len(results) == 0:
        return i

      score = alpha * self.es_score(i) + (1 - alpha) * self.sum_dist(
          i, results) / len(results)
      if score > max_score:
        max_score = score
        max_score_item_id = i
    return max_score_item_id

  def greedy_reranking(self, candidate_items: list[int], n: int, alpha=0.5):
    results = []
    while len(results) < n:
      doc_id = self.select_item_id(candidate_items, results, alpha)
      results.append(doc_id)
      candidate_items.remove(doc_id)
    return results

先ほど実装したSimirarityクラスを使ってRerankerクラスの初期化を行います。

corpus get_random_docs() # TF-IDFベクトル学習用のドキュメントのランダムサンプリング10000件
sim = TFIDFSimilarity(corpus=corpus)
reranker = Reranker(docs, max_score, sim)

これで準備完了です。早速実行してみます。

# before
print(pd.DataFrame([docs[i]['title'] for i in ids[:20]]))

results = reranker.greedy_reranking(ids, n=20)

# after
print(pd.DataFrame([docs[i]['title'] for i in results]))

beforeは課題の章でお見せしたリストです。リランキングの結果は下記になります。

コロナウィルスワクチン
コロナウイルスとインフルエンザワクチン
コロナワクチンいつまで
コロナワクチンって｡｡
コロナウイルスワクチンの授乳
コロナウィルスワクチンのメリット
コロナワクチンできるか？
コロナウィルスのワクチン
コロナウイルスワクチンとインフルエンザワクチン
ピルとコロナ・コロナワクチン
コロナワクチンに関して
コロナウィルスワクチン
コロナワクチン　風疹ワクチン
コロナウイルスワクチン接種
赤ちゃんのワクチンとコロナウィルス
コロナ、コロナワクチン微熱
コロナウイルスワクチン
コロナウイルスワクチン
コロナウィルスワクチン接種
インフルエンザワクチンとコロナ

リランキング前の結果よりもタイトルに多様性が出ているのがわかります。こちらの結果を検索結果ページに出した方が、ユーザー自身がクリックする質問を選びやすくなるでしょう。

結果は良い感じですが、このgreedy_rerankingの実行にはVSCodeのJupyter環境で25.3sかかってしまいました。検索におけるリランキングはパフォーマンスも重要なのでこれは問題です。一度計算したベクトルをキャッシュしておいてそれを利用したりすれば、もっと高速化できそうです。一方でもっと軽量な類似度計算を採用する手もあります。

Jaccard係数

より軽量に類似度計算するために、Jaccard係数を考えます。記事タグや単語など色々要素として採用できるものはありますが、今回はn-gramを採用します。理由は直接タイトルを形態素解析不要で扱えるためです。n-gram Jaccard係数は下記で計算できます。

$μ_{jaccard}(d_1, d_2) = 1 - \frac{|ngram(d1)\cap{ngram(d2)}|}{|ngram(d1)\cup{ngram(d2)}|}$

$T(d)$ はドキュメント $d$ から得られるn-gramを表します。

class NgramJaccardSimilarity(Similarity):
  def n_gram(self, txt, n):
    return [txt[idx:idx + n] for idx in range(len(txt) - n + 1)]

  def jaccard_distance(self, a, b):
    a = set(a)
    b = set(b)
    return 1.0 * len(a & b) / len(a | b)

  def calcurate(self, doc1: str, doc2: str):
    return self.jaccard_distance(self.n_gram(doc1, 2), self.n_gram(doc2, 2))

この実装を使ってリランキングを実行すると下記の結果になります。

コロナウイルスワクチン
コロナワクチンとインフルエンザワクチン
コロナワクチンのことで。
コロナのワクチンとおたふくのワクチン
コロナウィルスのワクチンについて
コロナワクチンをしても
コロナウイルスワクチンとサノレックスなど
ワクチン　コロナワクチン
コロナウイルスのワクチンとインフルエンザのワクチンについて
コロナワクチン、インフルエンザワクチン
コロナウイルスのワクチン
コロナワクチンの「本命」は？
コロナのワクチン
コロナウィルスワクチンについて
コロナと湿気とワクチン
コロナウイルスワクチン
コロナワクチンとインフルワクチン
コロナウイルスのワクチン
コロナワクチンとインフルエンザワクチン
コロナウィルスワクチンについて

悪くなさそうです。しかも実行時間は200msです。検索エンジンからの候補100件という数を減らせばもう少し速くできそうです。これくらいならリランキング実装としてAPIに組み込めるギリギリの速さでしょうか。

本実装の課題

この実装だとページングができないのが問題です。検索エンジンから候補100件を取ってきて、その中から20件に絞っている今回のような実装だと、検索エンジンは候補を出力するだけなので、検索エンジンに対してページングができません。

もしページングがしたいなら、前ページで表示したドキュメントをexcludeした検索を行って100件取得が必要です。

まとめ

今回は検索結果多様性向上のためのアルゴリズムを紹介しました。導入する際はパフォーマンスやページングなどの要件を確認して採用するといいでしょう。弊社では多様性向上がROI的に低いことがわかっているのでまだ実装に至ってませんが、いつか検索エンジンや推薦システムの多様性向上をする際には貪欲なリランキング手法は使えそうな武器だと感じました。