Lower Bounds on the Bayes Risk of the Bayesian BTL Model with Applications to Comparison Graphs
We consider the problem of aggregating pairwise comparisons to obtain a consensus ranking order over a collection of objects. We use the popular Bradley-Terry-Luce (BTL) model which allows us to probabilistically describe pairwise comparisons between objects. In particular, we employ the Bayesian BTL model which allows for meaningful prior assumptions and to cope with situations where the number of objects is large and the number of comparisons between some objects is small or even zero. For the conventional Bayesian BTL model, we derive information-theoretic lower bounds on the Bayes risk of estimators for norm-based distortion functions. We compare the information-theoretic lower bound with the Bayesian Cram\'{e}r-Rao lower bound we derive for the case when the Bayes risk is the mean squared error. We illustrate the utility of the bounds through simulations by comparing them with the error performance of an expectation-maximization based inference algorithm proposed for the Bayesian BTL model. We draw parallels between pairwise comparisons in the BTL model and inter-player games represented as edges in a comparison graph and analyze the effect of various graph structures on the lower bounds. We also extend the information-theoretic and Bayesian Cram\'{e}r-Rao lower bounds to the more general Bayesian BTL model which takes into account home-field advantage.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems
Recent work established a generalized-Fano framework for lower bounding prior-predictive (Bayesian) CVaR in interactive statistical decision making. In this paper, we show how to instantiate that framework in concrete in…
Decision MakingMisclassification excess risk bounds for PAC-Bayesian classification via convexified loss
PAC-Bayesian bounds have proven to be a valuable tool for deriving generalization bounds and for designing new learning algorithms in machine learning. However, it typically focus on providing generalization bounds with …
Generalization BoundsBayesian Regret Minimization in Offline Bandits
We study how to make decisions that minimize Bayesian regret in offline linear bandits. Prior work suggests that one must take actions with maximum lower confidence bound (LCB) on their reward. We argue that the reliance…
Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning
In parametric Bayesian learning, a prior is assumed on the parameter $W$ which determines the distribution of samples. In this setting, Minimum Excess Risk (MER) is defined as the difference between the minimum expected …
PAC-Bayesian Theory Meets Bayesian Inference
We exhibit a strong link between frequentist PAC-Bayesian risk bounds and the Bayesian marginal likelihood. That is, for the negative log-likelihood loss function, we show that the minimization of PAC-Bayesian generaliza…
Bayesian Inferenceregression