Belief propagation for permutations, rankings, and partial orders
| Autor: | George T. Cantwell, Cristopher Moore |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Computer Science - Machine Learning Artificial Intelligence (cs.AI) Statistical Mechanics (cond-mat.stat-mech) Computer Science - Artificial Intelligence Statistics - Machine Learning FOS: Physical sciences Computer Science - Social and Information Networks Machine Learning (stat.ML) Condensed Matter - Statistical Mechanics Machine Learning (cs.LG) |
| Zdroj: | Physical Review E. 105 |
| ISSN: | 2470-0053 2470-0045 |
| DOI: | 10.1103/physreve.105.l052303 |
| Popis: | Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method, we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection between competing probabilistic models, such as the Bradley-Terry-Luce model of noisy comparisons and its cousins. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|