ICIC   25583
INSTITUTO DE CIENCIAS E INGENIERIA DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
(AUTORES LISTADOS EN ORDEN ALFABETICO) Probabilistic Models over Weighted Orderings: Fixed-parameter Tractable Variable Elimination (10 páginas)
Autor/es:
DAVID POOLE; MARIA VANINA MARTINEZ; THOMAS LUKASIEWICZ; GERARDO I. SIMARI
Lugar:
Ciudad del Cabo
Reunión:
Conferencia; 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 2016); 2016
Institución organizadora:
Association for the Advancement of Artificial Intelligence
Resumen:
Probabilistic models with weighted formulas, known as Markov models or log-linear models, are used in many domains. Recent models of weighted orderings between elements that have been proposed as flexible tools to express preferences under uncertainty, are also potentially useful in applications like planning, temporal reasoning, and user modeling. Their computational properties are very different from those of conventional Markov models; because of the transitivity of the ?less than? relation, standard methods that exploit structure of the models, such as variable elimination, are not directly applicable, as there are no conditional independencies between the orderings within connected components. The best known algorithms for general inference in these models are exponential in the number of statements. Here, we present the first algorithms that exploit the available structure. We begin with the special case of models in the form of chains; we present an exact O(n^3) algorithm, where n is the total number of elements. Next, we generalize this technique to models in which the set of statements are comprised of arbitrary sets of atomic weighted preference formulas (while the query and evidence are conjunctions of atomic preference formulas), and the resulting exact algorithm runs in time O(m∗ n^2 ∗ n^c), where m is the number of preference formulas, n is the number of elements, and c is the maximum number of elements in a linear cut (which depends both on the structure of the model and the order in which the elements are processed)?therefore, this algorithm is tractable for cases in which c can be bounded to a low value. Finally, we report on the results of an empirical evaluation of both algorithms, showing how they scale with reasonably-sized models.