Untitled in english

Author(s)

Jaime Shinsuke Ide

• Document type: Doctoral Thesis
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Escola Politécnica (EP/BC)
• Defense date: 2005-12-16

Examining board members

Fabio Gagliardi Cozman; Alexandre Kawano; Newton Maruyama; Marcos Hiroyuki Tsuchida; Rosa Maria Vicari

• Advisor: Fabio Gagliardi Cozman
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Indexed in: Banco de Dados Bibliográficos da USP-DEDALUS
• Location: Universidade de São Paulo. Biblioteca Central da Escola Politécnica; EPBC/FT-2220

Abstract

Graphical models associated with probabilities find use in many fields. Bayesian networks are the most popular probabilistic graphical model in the literature. In situations where we have lack of data, incomplete beliefs and divergence between expert opinions, uncertainty can be represented by sets of probability measures called credal sets. Such sets, when associated with directed acyclic graphs, result in credal networks. Inference algorithms in creedal networks generally display high complexity, and approximate inference seems to be a natural solution for large networks. In this thesis, we present three new approximate algorithms for inference in binary credal networks: Loopy 2U (L2U), Iterated Partial Evaluation (IPE) and Structured Variational 2U (SV2U). The first one, the L2U algorithm, is an extension of the Loopy Belief Propagation algorithm for Bayesian network inference. The second one, the IPE algorithm, is directly based on the Localized Partial Evaluation (LPE) technique. Finally, the SV2U algorithm implements a variational approach; in this work, it is shown how to formulate mean field approximations for credal sets using naive (fully factorized) and structured (tree-like) schemes. The algorithms were implemented and a software package (2UBayes) has been made available. Experiments were conducted and a comparative analysis between algorithms was performed. These empirical results showed that accurate approximations with low computational cost are achieved. (AU)