Pairwise Ranking Aggregationについて

前置き

この記事はカレーのちぴょこりんクラスタ Advent Calendar 2018 - Adventarのために書かれたものです。ちなみにこのACが何なのかについては、ぴょこりんクラスタ Advent Calendar is 何？ - ぴょこりんブログが詳しいです。

サマリ

"Pairwise Ranking Aggregation in a Crowdsourced Setting"という論文に興味があり、実装してみました。
- Chen and Bennett, Pairwise Ranking Aggregation in a Crowdsourced Setting, WSDM13.
これはぴょこりんクラスタ夏の大ハッカソン（仮）の成果です。

本文

論文の内容

データから順序関係を学習することを目的とする。例えば、画像が10枚あったとして、(画像1)>(画像10)>...>(画像8)のような好みのランキングを学習することが目的。
この論文はCrowdSouringによりデータを取得することを目的とする。問題設定には以下のように反映される。

評価者の負荷を鑑み、入力を2オブジェクト間の比較結果（一対比較）の組とする。すなわち画像が10枚あったときに10枚すべての順序関係ではなく、(画像1)>(画像7)のような1対の比較を入力とする。
適当に入力するspammerがいることを前提とする。この評価者はあてにならないみたいことがある。

詳細は論文にゆずるが

比較すべきオブジェクト[\tex:o_{i},o_{j}]について、順序関係が[\tex:o_{i}>o_{j}]となる確率を下記とおき(Bradley-Terry model)

$Pr(o_{i}>o_{j}) = \frac{e^{ s_{i} }} {e^{s_{i}}+e^{s_{j}}}$

評価者kが順序関係を正しく評価する確率を $\eta_{k}$

とする。
順序関係をつけるべきオブジェクト $o_{1},o_{2},...,o_{N}$ 、評価者K人がいたもとで、
入力データである（評価者, 一対比較結果)の組に対して正則化付き対数尤度
$\sum^{K}_{k=1} \sum_{(i,j) \in S_{k}} \log( \eta_{k} \frac{e^{ s_{i} }} {e^{s_{i}}+e^{s_{j}}} + (1 - \eta_{k}) \frac{e^{ s_{j} }} {e^{s_{i}}+e^{s_{j}}}) + \lambda \sum_{i=1}^{N} \log( \frac{e^{ s_{0} }} {e^{s_{0}}+e^{s_{i}}} + \frac{e^{ s_{i} }} {e^{s_{0}}+e^{s_{i}}})$
を最大化することで、パラメータ $s_{1},...,s_{N},s_{0},\eta_{1},...,\eta_{K}$ を推定する。
( $s_{0}$ は正則化に関わるパラメータ、 $S_{i}$ は評価者iによる一対比較結果の集合）

第一項が対数尤度、第二項が正則化項。
なお、論文では、逐次的な入力に対するオンライン推定についても提案しているが、今回の実装は一括での推定である。

実装

試しに遊んでみるデータとしてsushi preference datasetを用いる。
www.kamishima.net
2種類のアイテム集合に対するデータセットがあるが、今回はAのもの（sushi3a.5000.10.order）を用いる。
これは10種類の寿司ネタの好みのランキングを含んだデータセットである。

0 10 5 0 3 4 6 9 8 1 7 2
0 10 0 9 6 3 7 2 8 1 5 4
0 10 7 0 2 3 8 4 5 1 9 6

1行が1人に対応、最初の0はヘッダ、次は集合の要素数10、以降が寿司ネタ好みのランキングである。
ちなみに寿司ネタのidは

0:えび 1:穴子 2:まぐろ 3:いか 4:うに
5:いくら 6:玉子 7:とろ 8:鉄火巻 9:かっぱ巻

である。

これだと今回の問題設定に合わないので、（情報量は落ちるが）一対比較の組として作りなおす。
github.com

0 0 2
0 1 2
0 5 4
0 8 1
0 4 2

のような（評価者、一対比較結果）の形に変換した。一対比較はもとのデータセットからランダムに２つ選択して生成した。
試しに評価者20人、1人あたり30組の一対比較結果をサンプルして、手法を適用してみた。
ソース下記。
github.com

#評価者が正しく評価する確率
[0.43379004 0.22232044 0.79776574 1. 0.19814816 0.22618328
1. 0.33754379 0.82956798 0.42050427 0.63106899 0.94282202
1. 0.5472771 0.74122849 1. 0.41946646 1.
0.96373038 1. ]
#学習されたランキング：
[7 4 5 1 0 3 2 8 6 9]

とろ、ウニ、いくらが上位とあるように、なんとなくみんなの好みにあった結果になっているように見える。
例として、正しく評価する確率が低い（ $\eta$ が低い）評価者の内容を、元データから眺めると、