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
- 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
-
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://www.teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/. Acesso em: 30 set. 2024. -
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://www.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 2024 set. 30 ] Available from: https://www.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 2024 set. 30 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-05032021-193406/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
