Tractable probabilistic description logic: algorithms and implementation (2020)
- Authors:
- Autor USP: LOPES, ANDREW IJANO - IME
- Unidade: IME
- Subjects: PROGRAMAÇÃO LINEAR; REPRESENTAÇÃO DE CONHECIMENTO
- Language: Inglês
- Abstract: Lógicas de descrição (LDs) são uma família de linguagens de representação de conhecimento. Uma delas, o EL++, está dentre uma das LDs mais expressivas cuja complexidade de raciocínio inferencial é tratável. Entretanto, simplesmente adicionar restrições probabilísticas deixa complexidade de decisão intratável. Este trabalho apresenta algoritmos para um raciocínio probabilístico em um fragmento do EL++, chamado Graphic EL. Os algoritmos modelam seu problema de satisfatibilidade probabilística como um programa linear, que pode ser resolvido por uma adaptação do método simplex com geração de colunas. Então, é possível reduzir o problema de geração de colunas para o de satisfatibilidade máxima partial ponderada para GEL (GEL-MaxSAT). Esse fragmento permite modelar axiomas como arestas de um grafo com pesos, o que motiva o uso de técnicas baseadas em grafos, calculando cortes mínimos, para desenvolver um algoritmo tratável para GEL-MaxSAT e, consequentemente, uma lógica de descrição probabilística tratável. Esses algoritmos foram implementados e, para essa solução, um limite superior teórico foi estimado e análises experimentais confirmam a complexidade polinomial do tempo de execução.
- Imprenta:
-
ABNT
LOPES, Andrew Ijano. Tractable probabilistic description logic: algorithms and implementation. 2020. Trabalho de Conclusão de Curso (Graduação) – Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2020. Disponível em: https://bdta.abcd.usp.br/directbitstream/df4c49ed-7c72-46f2-940f-6226633d3026/3054865.pdf. Acesso em: 21 mar. 2025. -
APA
Lopes, A. I. (2020). Tractable probabilistic description logic: algorithms and implementation (Trabalho de Conclusão de Curso (Graduação). Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo. Recuperado de https://bdta.abcd.usp.br/directbitstream/df4c49ed-7c72-46f2-940f-6226633d3026/3054865.pdf -
NLM
Lopes AI. Tractable probabilistic description logic: algorithms and implementation [Internet]. 2020 ;[citado 2025 mar. 21 ] Available from: https://bdta.abcd.usp.br/directbitstream/df4c49ed-7c72-46f2-940f-6226633d3026/3054865.pdf -
Vancouver
Lopes AI. Tractable probabilistic description logic: algorithms and implementation [Internet]. 2020 ;[citado 2025 mar. 21 ] Available from: https://bdta.abcd.usp.br/directbitstream/df4c49ed-7c72-46f2-940f-6226633d3026/3054865.pdf
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3054865.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
