Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

On the Semantics and Complexity of Probabilistic Logic Programs

Texto completo
Autor(es):
Cozman, Fabio Gagliardi [1] ; Maua, Denis Deratani [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Escola Politecn, Sao Paulo - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH; v. 60, p. 221-262, 2017.
Citações Web of Science: 5
Resumo

We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato's distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the ``credal semantics{''}) produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels. (AU)

Processo FAPESP: 16/18841-0 - Algoritmos para inferência e aprendizado de programas lógicos probabilísticos
Beneficiário:Fabio Gagliardi Cozman
Linha de fomento: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
Processo FAPESP: 16/01055-1 - Aprendizagem de modelos probabilísticos tratáveis e seu uso na classificação multirrótulo
Beneficiário:Denis Deratani Mauá
Linha de fomento: Auxílio à Pesquisa - Regular