比較データと確率モデル
個のアイテムからなる集合 を考える。本記事では、これらのアイテム間の比較に基づく観測データ(例えば二者間の勝敗など)に対して、適当な確率モデルを導入することで、その事象を説明することについて考える。また、その確率モデルの潜在変数を、観測データを元に推定することについて考える。
前提:Luce's Choice Axiom
この記事では特に、 Luce's choice axiom (ルースの選択公理) [Luce08] に基づく確率モデルのみを考える(公理の定義はこの記事では触れない)。
この公理のもとでは、各アイテムに紐づけられた潜在的なパラメタ (これらの値が である場合もあるが、この記事では簡単のため正の値として考える。)が存在し、比較はこれらの値に基づいて行われる。
なお、このパラメタは論文や文脈により異なる呼ばれ方をする。例えば "skill rating" [Caron+12] 、 "goodness value" [Koyama+17] 、 "quality scale" [Tsukida+11] などがある。
本題:比較データの形式と主な確率モデル
比較データにはいくつかの形式が考えられる。それぞれについて、それを説明するための確率モデルが考案されている。
なお、この節の内容は http://choix.lum.li/en/latest/data.html に簡潔にまとまっている。
Pairwise Comparison(一対比較)
Pairwise comparisonは日本語では一対比較などと呼ばれる。Paired comparisonとも表記される(例えば [神嶌09; Handley01] など)。これは2つのアイテムが比較された結果どちらかが選択されたという事象を表すデータ形式である。
アイテム がアイテム と比較された結果 が選ばれるという事象は
などと表現される。
Pairwise comparisonのデータを扱う確率モデルとしては Bradley-Terryモデル がある [Brochu+07; Hunter04; Tsukida+11] 。このモデルは、上記の事象が起こる確率を
とするものである。
指数関数やロジスティック関数を用いた表現
Bradley-Terryモデルは、その潜在変数を
として
と表現することも多い。この表現を用いてさらに式変形をすると、 を標準ロジスティック関数として
と表現することもできる。
その他のモデル
Pairwise comparisonを扱う確率モデルとしては、他にThurstone-Mostellerモデル [Chu+05; Handley01; Tsukida+11] が存在し、Bradley-Terryモデルと同様の文脈で議論されることがある [Handley01] 。Thurstone-Mostellerモデルは "Thurstone's Law of Comparative Judgement, Case V" を指している [Handley01] 。Bradley-Terryモデルは、Thurstone-Mostellerモデルが仮定しているGaussian分布をGumbel分布に置き換えたものと解釈することが可能である [Tsukida+11] 。
Generalized Bradley-Terryモデルというより表現力の高い確率モデルも存在する [Caron+12; Hunter04] 。
Top-1 List
Top-1 listはあまり共通認識のある呼称ではないかもしれないが、ここでは http://choix.lum.li/ に倣い、このように呼ぶことにする。これは、2つ以上のアイテムが同時に比較された結果ある1つのアイテムが選択されたという事象を表すデータ形式である。
アイテム群 からアイテム が選ばれるという事象は
などと表現される [Koyama+17] 。
Top-1 listのデータを扱う確率モデルとしては Bradley-Terry-Luceモデル がある [Koyama+17; Luce08; Tsukida+11] 。このモデルでは、上記の事象が起こる確率を
とする。
なお、比較対象がちょうど2つのときはBradley-Terryモデルと実質的に同じになる。
Partial Ranking
Partial rankingは、2つ以上のアイテムについて、それらの順序が与えられたという事象を表すデータ形式である。
アイテム群 に対し、 という順序が与えられるという事象は
などと表現される [神嶌09] 。
Partial rankingを扱う確率モデルとしては Plackett-Luceモデル がある [Guiver+09; 神嶌09] 。このモデルでは、上記の事象が起こる確率を
とする。これは、順位が早いものから逐次的に選択し取り除くという事象をBradley-Terry-Luceモデルを用いて表したものと解釈することができる。
潜在的なパラメタの推定
最尤推定 (maximum likelihood estimation)により、比較データから確率モデルの潜在的なパラメタを推定することができる [Tsukida+11] 。
また、潜在的なパラメタにある事前分布を仮定することで 最大事後確率推定 (maximum a posteriori estimation) により潜在的なパラメタを推定することもできる [Tsukida+11; Caron+12] 。
choix http://choix.lum.li/ というPythonライブラリは、これらの実装を提供している。
また、各アイテム間に類似度を定義できる場合には、ガウス過程などの分布を仮定して最大事後確率推定を行うこともある [Chu+05; Koyama+17] 。
余談:主観的な好み(preference)と比較データ
比較データを扱う確率モデルは preference learning という分野でも活用される(例えば [Chu+05; Brochu+07] など)。これは、人間(評価者)の 主観的な好み(preference) をデータから学習することに関連する分野である。
好みに関するデータを集める上で、あるアイテムに対する好みの評価値をそのまま評価者に聞く方法は望ましくなく、比較に基づくデータを集めるような方法が良いと考えられている [Tsukida+11; Koyama+17; Brochu+10] 。あるアイテムに対する好みの評価値を直接聞く方法が望ましくない理由として、
- (評価者が複数人いる場合)評価者によってスケールが異なる
- (複数のアイテムの評価を行う場合)スケールが時間経過と共に変化する(この効果はdriftと呼ばれる)
- (複数のアイテムの評価を行う場合)早い段階で評価を行ったアイテムによって全体のスケールが影響を受ける(この効果はanchoringと呼ばれる)
などにより、一貫したデータを取得できないことが考えられるためである [Brochu+10] 。
文献
以下に示す文献は本記事を書く上で実際に参考にしたもの(私がもともと良く知っていた文献や、キーワードで検索してたまたま発見した文献など)であって、記事の内容を説明する上で適切な文献を厳選したわけではない。
- [Brochu+07]: Eric Brochu, Nando de Freitas, and Abhijeet Ghosh. 2007. Active Preference Learning with Discrete Choice Data. In Proc. NIPS '07. pp.409–416. http://papers.nips.cc/paper/3219-active-preference-learning-with-discrete-choice-data.pdf
- [Brochu+10]: Eric Brochu, Tyson Brochu, and Nando de Freitas. 2010. A Bayesian Interactive Optimization Approach to Procedural Animation Design. In Proc. SCA '10. pp.103–112. DOI:https://doi.org/10.2312/SCA/SCA10/103-112
- [Caron+12]: Francois Caron and Arnaud Doucet. 2012. Efficient Bayesian Inference for Generalized Bradley-Terry Models. Journal of Computational and Graphical Statistics, 21, 1, pp.174-196 (April 2012). DOI:https://doi.org/10.1080/10618600.2012.638220
- [Chu+05]: Wei Chu and Zoubin Ghahramani. 2005. Preference learning with Gaussian processes. In Proc. ICML '05. pp.137–144. DOI:https://doi.org/10.1145/1102351.1102369
- [Guiver+09]: John Guiver and Edward Snelson. 2009. Bayesian inference for Plackett-Luce ranking models. In Proc. ICML '09. pp.377–384. DOI:https://doi.org/10.1145/1553374.1553423
- [Handley01]: John C. Handley. 2001. Comparative Analysis of Bradley-Terry and Thurstone-Mosteller Paired Comparison Models for Image Quality Assessment. In Proc. PICS '01.
- [Hunter04]: David R. Hunter. 2004. MM algorithms for generalized Bradley-Terry models. Ann. Statist. 32, 4, pp.384-406 (2004). DOI:https://doi.org/doi:10.1214/aos/1079120141
- [Koyama+17]: Yuki Koyama, Issei Sato, Daisuke Sakamoto, and Takeo Igarashi. 2017. Sequential line search for efficient visual design optimization by crowds. ACM Trans. Graph. 36, 4, pp.48:1-48:11 (July 2017). DOI:https://doi.org/10.1145/3072959.3073598
- [Luce08]: R. Duncan Luce. 2008. Luce's choice axiom. Scholarpedia. 3(12):8077. DOI: https://dx.doi.org/10.4249/scholarpedia.8077
- [Tsukida+11]: Kristi Tsukida and Maya R. Gupta. 2011. How to Analyze Paired Comparison Data. Technical Report. University of Washington. https://www2.ee.washington.edu/techsite/papers/refer/UWEETR-2011-0004.html
- [神嶌09]: 神嶌敏弘. 2009. 順序の距離と確率モデル. 人工知能学会研究会資料, SIG-DMSM-A902-07 (2009). http://www.kamishima.net/archive/2009-tr-jsai_dmsm2-print.pdf
注意とお願い
私は確率・統計・機械学習等の専門家ではありません。本記事は、私が学びながらとったメモを整形したものに過ぎず、根本的な誤りが含まれるかもしれません。また、些細なことでも構いませんので、誤りの訂正・表現に違和感のある箇所の指摘・改善の提案等ありましたらコメント頂けると幸いです。