Uma rede credal é uma ferramenta gráfica para representação e manipulação de incerteza, onde valores de probabilidade podem ser imprecisos ou indeterminados. Uma rede credal associa um grafo direcionado acíclico a uma coleção de conjuntos de medidas de probabilidade. Neste contexto, uma inferência é o cálculo de valores máximos e mínimos para probabilidades condicionais. Neste trabalho apresentamos resultados de complexidade de problemas de inferência e novas técnicas para inferência em redes credais baseados em programação multilinear. Através dessas idéias desenvolvemos novos algoritmos exatos e aproximados para inferência em tais redes. Experimentos indicam que estes algoritmos tem melhor desempenho que os conhecidos até o momento no sentido de produzir resultados mais precisos para redes de grande porte. Tratamos ainda outros modelos gráficos, como redes qualitativas e semi-qualitativas, pois elas também se encaixam no contexto das redes credais.

A credal network is a graphical tool for representation and manipulation of uncertainty, where probability values may be imprecise or indeterminate. A credal network associates a directed acyclic graph with a collection of sets of probability measures; in this context, inference is the computation of tight lower and upper bounds for conditional probabilities. In this work we present complexity results for the inference problems and new techniques for inference in credal networks based on multilinear programming. These techniques have led to new exact and approximate algorithms for inference in such networks. Experiments indicate that these new algorithms have better performance than existing ones, in the sense that they produce more accurate results in larger networks. We also deal with other graphical models as qualitative and semi-qualitative networks, as they also fit in the credal network model.