TrueSkill Beyond Gaussians
Project Report
Masterproject 2024/25: TrueSkill Beyond Gaussians
Approximate Inference Methods for Skill-based Ranking and Bayesian Neural Networks
Overview
This master project researches message passing (MP) on factor graphs by incorporating richer distributions beyond the standard Gaussian approximation. Our goal is to improve the accuracy of approximate inference in skill-based ranking (e.g., TrueSkill) and Bayesian neural networks (BNNs) by using distributions with more parameters, providing a more expressive alternative to Gaussians. Through robust updates, the estimated skills are known to improve log likelihood of observed game outcomes compared to other ranking systems such as ELO.
We extend TrueSkill and Bayesian Neural Networks by incorporating Mixtures of Gaussians (GMs) and Uniform Mixtures (UMs)—also known as quantile distributions or histograms—and compare their performance against the typically used Gaussians in terms of accuracy and calibration.
Our framework is primarily implemented in Julia, which enables us to perform efficient sampling-based experiments and fast message-passing inference. This makes it possible to run large-scale probabilistic inference tasks on datasets such as historical Tennis and League of Legends matches. However, we also experimented with a Python codebase (under development), which provides a better debugging experience and higher code readability.
Features
- We implement both slow, high-accuracy methods (e.g., Expectation Maximization) for fitting Gaussian Mixture approximations of marginals and fast, analytically derived message-passing updates for efficient inference.
- We optimized the message computation by using segment trees for efficient multiplication and division of multiple distributions.
- We extend TrueSkill, Linear Regression, and Bayesian Neural Networks (BNNs) to work with Gaussian Mixtures (GMs), Uniform Mixtures (UMs), and standard Gaussians.
[!NOTE] The project’s focus was on exdending TrueSkill with more expressive distributions, so the corresponding code is more robust and validated compared to the code for Bayesian Neural Networks, which is more experimental and might not be empirically robust (e.g. for scaling the network and/ or training data size).