• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2021.tde-19062021-063556
Documento
Autor
Nome completo
Heitor Reis Ribeiro
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2021
Orientador
Banca examinadora
Mauá, Denis Deratani (Presidente)
Cerri, Ricardo
Prati, Ronaldo Cristiano
Título em inglês
A benchmark for Maximum-a-Posteriori Inference algorithms in discrete Sum-Product Networks
Palavras-chave em inglês
Maximum-a-posteriori
Probabilistic models
Sum-product networks
Resumo em inglês
The solution to Maximum-a-Posteriori Inference problems in Sum-Product Networks provides the most probable configuration of the Random Variables encoded in its structure; a key step in Probabilistic reasoning that can be used for many applications, such as image auto-completion. It has been proven that this problem is NP-Hard (even to approximate) in Sum-Product Networks. Multiple algorithms have been developed to reach either approximate or exact solutions to this problem, but the experiments have been limited. In this Dissertation, we provide descriptions, analysis, and a benchmark for experimental testing for algorithms that solve this problem. We conclude that, given limited time, a Local Search algorithm starting with a solution found by the Argmax-Product algorithm reaches, on average, better results on the tested datasets.
Título em português
Um benchmark para algoritmos de Inferência de Maximum-a-Posteriori em Redes Soma-Produto discretas
Palavras-chave em português
Maximum-a-posteriori
Modelos probabilísticos
Redes soma-produto
Resumo em português
A solução para problemas de Inferência de Maximum-a-Posteriori em redes de Soma-Produto resultam na configuração mais provável das Variáveis Aleatórias representadas em sua estrutura; um passo importante em raciocínio probabilístico que pode ser usado para muitas aplicações, como preenchimento automático de imagens. Já foi provado que este problema é NP-difícil (até para aproximar) em redes de Soma-Produto. Vários algoritmos já foram desenvolvidos para obter uma solução boa ou exata para esse problema, mas os experimentos realizados até agora foram limitados. Nesta dissertação nós fornecemos descrições, análises, e um benchmark para realizar mais testes experimentais para algoritmos que resolvem esse problema. Nós concluímos que, dada uma janela de tempo limitada, um algoritmo de Busca Local iniciado com uma solução retornada pelo algoritmo Argmax-Product alcança, em média, os melhores resultados nos conjuntos de dados testados.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Dissertation.pdf (1.03 Mbytes)
Data de Publicação
2021-09-03
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.