Rocchioフィードバックアルゴリズム

情報検索 (IR) の分野におけるフィードバックアルゴリズムの1つであるRocchioアルゴリズムについて紹介します。

Rocchioフィードバックアルゴリズムとは

IRにおいて、検索クエリをTF*IDF等でベクトル化した後で、過去のラベリング情報 (フィードバック) を使って、修正するアルゴリズムの1つです。
フィードバックが必要なため、クエリに対してドキュメントが関連する or しないというラベリングが何らかの方法でされていることが前提となります。

以下の図のように、クエリベクトルを関連する文書に近づけるように修正するイメージです。

具体的には下式の通りで、元のクエリベクトル を へ修正してます。

• 第1項は、元のクエリベクトルで、フィードバック無しの場合は そのもので文書との類似度が計算されます
• 第2項は、クエリと関連する文書 のベクトルを使って修正する項です
  • クエリベクトルが関連する文書の重心へより近づくように、文書ベクトルの平均値を加算してます
• 第3項は、クエリと関連しない文書 のベクトルを使って修正する項です
  • クエリベクトルが関連しない文書の重心から遠ざかるように、文書ベクトルの平均値を減算してます
• 各項はハイパーパラメータ (α, β, γ) で重み付けされます

Rocchioによるクエリ修正の例

例えば4つの文書 (d0, ..., d3) が、それぞれビットベクトル化 ( ) されているものとします。

• d0 = {犬, 画像},
• d1 = {ワンちゃん, 写真},
• d2 = {猫, 写真},
• d3 = {ペンギン, 画像},

修正無しの場合、クエリ = {犬, 写真} ( ) に対して、 d0,d1,d2が同じ類似度で計算されてしまいます。

$$ \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} ^{\mathrm{T}} = \begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix} $$

同じクエリ {犬, 写真} のフィードバックが過去に得られていたとします。

• d0 → 関連有り
• d1 → 関連有り
• d2 → 関連無し

この時、Dr={d0, d1}、Dnr={d2}となるため、α=0.7, β=0.2, γ=0.1とすると、修正後のクエリベクトルは(1.1, 0.1, 0.1, 0, -0.1, 0)となります。

これで計算すると、類似度は (1.2, 0.1, -0.1, 0) でd0 > d1,d3 > d2となり、元のランキングよりは良くなりました。

• フィードバックが無かったd3のランクも上がっていることに注目してください
  • 通常の文書はもっとたくさんの次元数を持ちますので、 とマッチせずに除外されるかと思います

$$ \begin{pmatrix} 1.1 & 0.1 & 0.1 & 0 & -0.1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} ^{\mathrm{T}} = \begin{pmatrix} 1.2 & 0.1 & -0.1 & 0.1 \end{pmatrix} $$

ハイパーパラメータについて

α、β、γで、フィードバックの影響度が調整できますが、情報検索の文脈においては、基本的には以下の指針に従うのがベストプラクティスです。目安としてα=1, β=0.75, γ=0.15というのが、最初のスタートとして良さそうとのことでした。

• α >> β, γとすることで、元のクエリと文書の内容がマッチすることを重視する
• 関連しない文書よりも、関連する文書の方が検索結果にとって重要な情報であるため、β > γとする
• 関連しない文書のベクトルについては、しばしば重心が定められない (0付近になる) ため、低めに設定する (あるいは0にする)

参考書籍

理論的な内容については、以下の書籍の9章を参考にしました。

情報検索の基礎