The complexity of MAP inference in Bayesian networks specified through logical languages

Denis D. Mauá; Cassio P. De Campos; Fabio G. Cozman

The complexity of MAP inference in Bayesian networks specified through logical languages

Denis D. Mauá, Cassio P. De Campos, Fabio G. Cozman

Resultado de la investigación: Contribución a una conferencia › Artículo de conferencia

8 Citas (Scopus)

Resumen

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as contextsensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.

Idioma original	Inglés estadounidense
Páginas	889-895
Número de páginas	7
Estado	Publicada - 1 ene. 2015
Publicado de forma externa	Sí
Evento	IJCAI International Joint Conference on Artificial Intelligence - Duración: 1 ene. 2015 → …

Conferencia

Conferencia	IJCAI International Joint Conference on Artificial Intelligence
Período	1/01/15 → …

Otros archivos y enlaces

Citar esto

@conference{5f5eefac0bb44695af6d48875385aab4,

title = "The complexity of MAP inference in Bayesian networks specified through logical languages",

abstract = "We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as contextsensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.",

author = "Mau{\'a}, {Denis D.} and {De Campos}, {Cassio P.} and Cozman, {Fabio G.}",

year = "2015",

month = jan,

day = "1",

language = "American English",

pages = "889--895",

note = "IJCAI International Joint Conference on Artificial Intelligence ; Conference date: 01-01-2015",

}

TY - CONF

T1 - The complexity of MAP inference in Bayesian networks specified through logical languages

AU - Mauá, Denis D.

AU - De Campos, Cassio P.

AU - Cozman, Fabio G.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as contextsensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.

AB - We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as contextsensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84949775474&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84949775474&origin=inward

M3 - Conference Paper

SP - 889

EP - 895

T2 - IJCAI International Joint Conference on Artificial Intelligence

Y2 - 1 January 2015

ER -

The complexity of MAP inference in Bayesian networks specified through logical languages

Resumen

Conferencia

Otros archivos y enlaces

Huella

Citar esto