A Mixed-Integer Linear Programming reformulation approach to Maximum A Posteriori inference in Sum-Product Networks (2021)
- Authors:
- Autor USP: KATAGUE, GUSTAVO PEREZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2021.tde-05032021-193406
- Subjects: INTELIGÊNCIA ARTIFICIAL; RECONHECIMENTO DE PADRÕES; PROGRAMAÇÃO LINEAR
- Keywords: Diagramas de decisão algébrica parametrizados; Inferência de máximo a posteriori; Maximum a posteriori inference; Mixed-integer linear programming; Modelos probabilísticos baseados em grafos; Parameterized algebraic decision diagrams; Probabilistic graphical models; Programação linear inteira mista; Redes soma-produto; Sum-product networks
- Agências de fomento:
- Language: Inglês
- Abstract: Rede Soma-Produto (SPN) é uma classe de modelos probabilísticos baseados em grafos relativamente nova. Elas diferem de outros modelos probabilísticos por permitir a representação explícita de independência sensível a contexto e a computação de inferência marginal em tempo linear. Redes Bayesianas e redes de Markov, por exemplo, exigem esforço #P-difícil para computar inferência marginal. Entretanto, continua sendo NP-difícil encontrar a configuração mais provável para um conjunto de variáveis em uma SPN, e atualmente há uma escassez de técnicas eficientes que solucionam o problema. Uma técnica amplamente utilizada para solucionar problemas de otimização NP-difíceis consiste em transformá-los em um programa de Programação Linear Inteira Mista (MILP), que então poderia ser solucionado por otimizadores de alta performance disponíveis comercialmente. Além de aproveitar o potencial dos otimizadores atuais, formular o problema como um programa MILP nos permite obter um algoritmo anytime que continuamente encontra soluções melhores quanto mais recursos (tempo e memória) forem disponibilizados, e pode ser interrompido a qualquer momento obtendo-se uma solução válida com margens de erro. Neste trabalho nós desenvolvemos um novo algoritmo que soluciona o problema de computar a configuração mais provável (inferência de Máximo A Posteriori) para um conjunto de variáveis em SPNs através de sua reformulação como um programa MILP. Esta reformulação é consideravelmente complexa e sebaseia em diversos resultados dispersos pela literatura, tal como a reformulação de SPNs em Redes Bayesianas com variáveis latentes, a representação compacta das tabelas de probabilidades através de Diagramas de Decisão Algébrica, e manipulações simbólicas de expressões multilineares na forma de Diagramas de Decisão Algébrica Parametrizados
- Imprenta:
- Data da defesa: 03.02.2021
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
KATAGUE, Gustavo Perez. A Mixed-Integer Linear Programming reformulation approach to Maximum A Posteriori inference in Sum-Product Networks. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2021. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/. Acesso em: 07 abr. 2026. -
APA
Katague, G. P. (2021). A Mixed-Integer Linear Programming reformulation approach to Maximum A Posteriori inference in Sum-Product Networks (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/ -
NLM
Katague GP. A Mixed-Integer Linear Programming reformulation approach to Maximum A Posteriori inference in Sum-Product Networks [Internet]. 2021 ;[citado 2026 abr. 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/ -
Vancouver
Katague GP. A Mixed-Integer Linear Programming reformulation approach to Maximum A Posteriori inference in Sum-Product Networks [Internet]. 2021 ;[citado 2026 abr. 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
