Information Retrieval and Web Search まとめ(25): パーソナライズ

前回は、質問応答とその手法（テキストベース、ナレッジベースを使った方法、それらのハイブリッド）について説明した。今回はパーソナライズについてまとめる。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の25日目の記事です。

adventar.org

パーソナライズ
講義資料
参考資料

パーソナライズ

クエリの曖昧性とパーソナライズ

短いクエリではユーザの情報ニーズを明確に表現できない
たとえば chi は以下のような意味をもつ
- Calamos Convertible Opportunities & Income Fund quote
- The city of Chicago
- Balancing one’s natural energy (or ch’i)
- Computer-human interactions
つまり、1つのランキングでは、すべてのユーザに最適なものにはできない
- パーソナライズドランキング (personalized ranking) がそのギャップを埋めるただ1つの方法
パーソナライズに以下のような情報を使うことができる：
- ユーザの長期的な振る舞い（ユーザの長期的な興味を判定するため）
- 短期的なセッション情報（ユーザの現在のタスクを判定するため）
- ユーザの位置情報
- SNS (social network)
- ...

パーソナライズのポテンシャル

[Teevan, Dumais, Horvitz 2010]
RQ
- パーソナライズすることによってどのくらいランキングを改善できるか？
- そして、それをどのように計測するか？
評価者 (rater) に明示的に検索結果のレーティングを付けてもらう
- ただし、評価者にユーザの情報ニーズが何であったか予想してもらうのではなく、個人的な考えで適合しているかどうかの観点で評価
各クエリ q に対して
- 各検索結果の平均レーティングを計算
- 平均レーティングを使って最適ランキング $R_q$ を決定
- 各評価者 i に対して、ランキング $R_q$ をもとにした NDCG を計算
- そうして計算された各評価者の NDCG の平均 $Avg_q$ を計算
すべてのクエリでの $Avg_q$ の平均を $Avg$ とする
パーソナライズのポテンシャルを $(1 - Avg)$ とする

f:id:takuya-a:20201225215923p:plain — ([Teevan+ 2010] Figure 4) 最適なパーソナライズによるスコア（平均 NDCG）を 1 (Individual) としたときの、パーソナライズしなかった場合の NDCG (Group)

パーソナライズド検索の概要

[Pitkow et al. 2002]
パーソナライズド検索 (personalizing search) の2つの一般的な方法
- クエリ拡張 (query expansion)
  - ユーザのクエリを、ユーザの意図 (intent) に応じて修正 (modify) もしくは拡張 (augment) する
  - 例： IR --> "information retrieval", "Ingersoll-Rand"
- リランキング (reranking)
  - 同じようにクエリを発行し、検索結果を取得したあと、それを並べ替える
  - パーソナライズされた結果を得ることも、全体的に適合する (globally relevant) 結果を得ることもできる

ユーザ意図

ユーザによって与えられたもの
- ときには役立つ（とくに新しいユーザの場合）
ユーザの振る舞いやユーザのデータから推論されたもの
- 過去に発行されたクエリ
- 過去に訪れた Web ページ
- 個人の文書データ
- Email
プライバシーを守ることが非常に重要

適合性フィードバックによるパーソナライズ

[Teevan, Dumais, Horvitz 2005]

f:id:takuya-a:20201225220047p:plain — ([Teevan+ 2005] Figure 1) 古典的な適合性フィードバック（左）と、ユーザプロファイルを使った適合性フィードバック（右）

古典的な適合性フィードバック (traditional relevance feedback)
- $N$ : コーパスの文書数
- $n_i$ : ターム i を含む文書数
- $R$ : 適合する文書数
- $r_i$ : ターム i を含み、かつ適合する文書
個人プロファイル適合性フィードバック (personal profile relevance feedback)
- 適合する文書 (R) として、コーパス外のユーザデータを使う
- $R$ : 適合する文書数
- $r_i$ : ターム i を含み、かつ適合する文書
- $N' = (N+R)$ : コーパスの文書数 + ユーザデータの文書数
- $n_i' = (n_i + r_i)$ : ターム i を含む文書数

リランキング

スコア関数として、BM25 を変えたものを使う
スコア関数は以下の形のものを使う:

$tf_i$ はタームが文書中に出現した頻度 (term frequency)
$w_i$ はそのタームの重み (term weight)
古典的な適合性フィードバック ([Teevan+ 2005] Figure 1a) では、タームの重み $w_i$ は以下のようになる

$N' = (N+R)$ と $n_i' = (n_i + r_i)$ を使って、ユーザデータを使った適合性フィードバック ([Teevan+ 2005] Figure 1b) でのターム重み $w_i$ は以下のようになる

コーパスの表現

とを推定する
- コーパスは Web の文書すべて
- クライアント側でパーソナライズを行う場合、コーパスの統計情報に直接アクセスすることはできない
- Web 検索を実行して返ってきた検索結果を使って推定する
$N$ の推定: 英語でもっとも頻度の高い単語である "the" のヒット数を使う
$n_i$ の推定: その単語 i の1単語だけで検索したヒット数を使う

ユーザの表現

とをローカルの検索インデックスから推定する
- ユーザが閲覧したページ
- ユーザが閲覧したり送信した Email
- カレンダーの予定
- クライアントマシン上の文書
$R$ の推定: ローカルのインデックス上の文書数を使う
$r_i$ の推定: ローカルのインデックスで単語 i を検索したときのヒット数を使う

文書とクエリの表現

文書はタイトルとスニペットで表現される
クエリは、クエリ文字列の近くに出現した単語で拡張される
- もとのクエリが cancer だったとき、以下の下線の単語がクエリになる

The American Cancer Society is dedicated to eliminating cancer as a major health problem by preventing cancer, saving lives, and diminishing suffering through...

Personalized PageRank

[Haveliwala 2002]
[Jeh and Widom 2003]
通常の PageRank では、すべてのページにおいてテレポート確率ベクトル (teleportation probability vector) p は一様 (uniform) だった
ユーザの嗜好 (preference) をその p によって表現する
- ユーザがどのページにテレポートするかが、ユーザによって変わる
- p はユーザのブックマークにあるページのなかで一様とする
- もしくは、ユーザが興味をもっているトピックのページについてはテレポート確率が存在することにする
しかし、 Personalized PageRank を計算するのは高コスト

Linearity theorem

任意の preference vector $\boldsymbol{u_1}$ と $\boldsymbol{u_2}$ に対して、 $\boldsymbol{v_1}$ と $\boldsymbol{v_2}$ がそれぞれに対応する personalized PageRank vector だとする
このとき、 $a_1 + a_2 = 1$ となる任意の非負の定数 $a_1$ , $a_2$ に対して以下が成り立つ

Topic-sensitive PageRank

トピックごとに personalized PageRank vector を計算する
- Open Dictionary Project にある 16 のトップレベルのトピックを使用
- ページに対してトピックが手で分類されている
- トピックに対する preference vector は、トピック内では一様分布とする
- トピック外では 0 とする
Note: [Jeh and Widom 2003] によりさらに一般化されている

クエリタイミングでの計算

クエリのトピックに対する分布を構築する
- ユーザプロファイルからトピックの分布を計算
- 他のコンテキスト情報も使える
トピックの preference を使って、topic PageRank vector の重み付き線形和を計算し、それを通常の PageRank の代わりに使う

ソーシャルネットワークでのパーソナライズド検索

[Curtiss et al. 2013]
Unicorn: Facebook Graph Search のバックエンド
Facebook Graph Search
- ノード (node) は人やもの（エンティティ）を表す
- エンティティ (entity) はユニークな 64 ビットの id
- エッジ (edge) はノード間の関係 (relationship) を表す
  - エッジの種類は数千タイプある： friend likes likers ...

Unicorn のデータモデル

ノード数は数億だが、グラフは疎 (sparse)
- グラフを隣接リストを使って表現する
- ポスティングは sort-key （重要度）でソートされ、次に id でソートされる
- インデックスは id でシャーディングされる
- オプショナルで HitData というバイト配列を保存できる
  ([Curtiss+ 2013] Figure 2) Unicorn のデータモデル。ノードのエッジを転置インデックスのポスティングリストとして表現する

Unicorn の基本的な集合演算

クエリ言語は基本的な集合演算をサポートしている
- and or difference
例1: id 5 か id 6 どちらかの友達
- (or(friend:5 friend:6))
例2: id 5 の女性の友達で、 id 6 の友達ではない人
- (difference (and friend:5 gender:1) friend:6)

サジェスト (Typehead)

最初の数文字を入力するだけでユーザを見つける
インデックスサーバは、ある一定の文字数までのすべての名前の接頭辞 (prefix) に対してポスティングリストを持っている
他の演算子と組み合わせられる
- 例： (and mel* friend:3)

weak-and 演算子

Unicorn は weak-and という特殊な演算子をサポートしている
optional-hits optional-weight というオプションをもつ
- その条件が満たされていなくてもよいという意味

f:id:takuya-a:20201226055823p:plain — ([Curtiss+ 2013] Figure 4) weak-and のクエリ実行時のインデックス構造

(weak-and (term friend:3 :optional-hits 2) (term malanie) (term mars*)) の検索
- :optional-hits 2 は、2件まで、この条件（1つめの term）が満たされていなくても結果に含める、という意味
- 検索結果は 20 7 88 64 となる
- 62 は返されない
- 3 つの term 条件の全てを満たしているのは 7 と 64 だけ
- 左から順番に見ていって、 20 と 88 は条件を 2 つしか満たしていないが、この2つまでは検索結果に含まれる
- 62 に達したときにはすでに optional-hits の 2 を使い果たしているので、これは含まれない

講義資料

Personalization

stop-the-world

takuya-a のブログ