Abstract de nuestro grupo en 1996/UTAI Research Group Abstracts in 1996


Importance Sampling Algorithms for Belief Networks
BY José Cano, Luis D. Hernández, Serafín Moral

Submitted to: International Journal of Approximate Reasoning, 1995. (20 pages)

This paper investigates the use of a class of importace sampling algorithms for probabilistic graphs in graphical structures. A general model for constructing importance sampling algorithms is given and then some particular cases are considered. Logical sampling and likelihood weigthing are particular cases of the model. Our proposal will be an algorithm which uses the functions with less entropy (more informative) to simulate the variables and the functions with more entropy to weight the simulations, in this way we expect to obtain more uniform weights. Some experimental tests are carried out comparing the performance of the proposed algorithms in randomly generated graphs.


Importance sampling algorithms for the calculation of Dempster-Shafer belief
BY S. Moral, N. Wilson

To appear in: Proceedings of IPMU-96 Conference, 1996. (8 pages)

This paper presents importance sampling Monte-Carlo algorithms for the calculation of belief functions combination. When the conflict between the evidence is not very high a simple Monte-Carlo algorithm can produce good quality estimations. For the case of highly conflicting evidences a Markov chain Monte-Carlo algorithm was also proposed. In this paper, a new class of importance sampling based algorithms is presented. The performance of them is compared by experimental tests.


A Genetic algorithm to approximate convex sets of probabilities
BY A. Cano and S. Moral

To appear in: Proceedings of IPMU-96 Conference , 1996. (7 pages)

An Evolution Program is presented to propagate convex sets of probabilities. This algorithm is useful when the number of extreme points in the 'a posteriori' convex set for a variable is too high and a single probabilistic propagation is feasible. We have tested the algorithm in a random causal network with a random number of conditional probabilities in each one of the variables. The experimental evaluation show that the resulting intervals obtained for the cases of a variable are similar to those obtained using an exact method of propagation.


BENEDICT: An Algorithm for Learning Probabilistic Belief Networks
BY S.Acid, L.M. de Campos

Presented in Sixth Internatational Conference IPMU'96, 1996. (6 pages)

We develop a system that, given a database containing instances of the variables in a domain of knowledge, captures many of the dependence relationships constrained by those data, and represents them as a graph. If we enlarge this graph by adding numerical values, corresponding to the conditional probabilities of every node given its parents nodes, we obtain a belief network The resultant belief network provides an insight into the probabilistic dependencies that exist among the variables and it can be used as an expert system to perform tasks of diagnosis, classification, decision making,... To obtain the network structure, we have designed a new learning algorithm, called BENEDICT, which has been implemented and incorporated as a module within the system. The numerical component, i.e., the conditional probability tables, are estimated directly from the database. We have tested the system on databases generated from simulated networks by using probabilistic sampling, including an extensive database, corresponding to the well-known Alarm Monitoring System. These databases were used as inputs for the learning module, and the networks obtained, compared with the originals, were consistently similar.


An Algorithm for Finding Minimum d-Separating Sets in Belief Networks
BY S.Acid, L.M. de Campos

To appear in Proceedings of UAI'96, 1996. (8 pages)

The criterion commonly used in directed acyclic graphs (dags) for testing graphical independence is the well-known d-separation criterion. It allows us to build graphical re\-presentations of dependency models (usually probabilistic dependency models) in the form of belief networks, which make easy interpretation and management of independence relationships possible, without reference to numerical parameters (conditional probabilities). In this paper, we study the following combinatorial problem: finding the minimum d-separating set for two nodes in a dag. This set would represent the minimum information (in the sense of minimum number of varia\-bles) necessary to prevent these two nodes from influencing each other. The solution to this basic problem and some of its extensions can be useful in several ways, as we shall see later. Our solution is based on a two-step process: first, we reduce the original problem to the simpler one of finding a minimum separating set in an undirected graph, and second, we develop an algorithm for solving it.


Importance sampling algorithms in belief networks based on approximate computation
BY L.D. Hernández, S. Moral, A. Salmerón

Proceedings of IPMU-96, Vol. II (1996) 859-864., 1996. (6 pages)

In this paper we study a new general class of algorithms for the propagation of probabilities on graphical structures based on importance sampling techniques. The idea is to make an approximate and fast propagation in order to obtain a sampling distribution as close as possible to the true one. Our proposal is based on a deletion sequence of the variables to calculate the a posteriori probability in one variable. This deletion procedure is the basic for exact propagation algorithms. Here the difference is that, sometimes, when the cost of the exact deletion exceeds a given limit, an approximated deletion is done. Some experimental tests are carried out to compare our procedure with other known methods.


Fast Markov Chain Algorithms for Calculating Dempster-Shafer belief
BY Nic Wilson and Serafín Moral

ECAI'96 Proceedings (W. Wahlster, ed.) J. Wiley (1996) 672-676, 1996. (5 pages)

We present a new type of Markov Chain algorithm for the calculation of combined Dempster-Shafer belief which is almost linear in the size of the the frame, thus making the calculation of belief feasible for a wider range of problems. We also indicate how these algorithms may be used in the calculation of belief in product spaces associated with networks.


Characterizations of decomposable dependency models
BY Luis M. de Campos

Journal of Artificial Intelligence Research 5, 289-300, 1996.

Decomposable dependency models possess a number of interesting and useful properties. This paper presents new characterizations of decomposable models in terms of independence relationships, which are obtained by adding a single axiom to the well-known set characterizing dependency models that are isomorphic to undirected graphs. We also briefly discuss a potential application of our results to the problem of learning graphical models from data.



Ir Atrás         Página DECSAI
Go back          Home DECSAI