A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints
A method of calculating probability values from a system of marginal constraints is presented. Previous systems for finding the probability of a single attribute have either made an independence assumption concerning the evidence or have required, in the worst case, time exponential in the number of attributes of the system. In this paper a closed form solution to the probability of an attribute given the evidence is found. The closed form solution, however does not enforce the (non-linear) constraint that all terms in the underlying distribution be positive. The equation requires O(r^3) steps to evaluate, where r is the number of independent marginal constraints describing the system at the time of evaluation. Furthermore, a marginal constraint may be exchanged with a new constraint, and a new solution calculated in O(r^2) steps. This method is appropriate for calculating probabilities in a real time expert system
Code (0)
등록된 구현이 없습니다.
Tasks
AttributeSimilar Papers 제목 키워드 기반
Bayesian Tensor Network with Polynomial Complexity for Probabilistic Machine Learning
It is known that describing or calculating the conditional probabilities of multiple events is exponentially expensive. In this work, Bayesian tensor network (BTN) is proposed to efficiently capture the conditional proba…
BIG-bench Machine LearningMarkov Chain Monte Carlo Data Association for Multiple-Target Tracking
This paper presents Markov chain Monte Carlo data association (MCMCDA) for solving data association problems arising in multiple-target tracking in a cluttered environment. When the number of targets is fixed, the sing…
Combinatorial Pure Exploration for Dueling Bandit
In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidate…
PositionCombinatorial Pure Exploration of Dueling Bandit
In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidate…
PositionPMBO: Enhancing Black-Box Optimization through Multivariate Polynomial Surrogates
We introduce a surrogate-based black-box optimization method, termed Polynomial-model-based optimization (PMBO). The algorithm alternates polynomial approximation with Bayesian optimization steps, using Gaussian processe…
Bayesian OptimizationEvolutionary AlgorithmsGaussian Processes