Structure Approximation of Most Probable Explanations in Bayesian Networks
Berlin : Springer
InLecture Notes in Computer Science, (2013)Gaag, L.C. van der (ed.), Symbolic and Quantiative Approaches to Resoning with Uncertainty. 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, 2013, Proceedings, pp. 340-351
Article in monograph or in proceedings
Display more detailsDisplay less details
Gaag, L.C. van der
SW OZ DCC CO
Lecture Notes in Computer Science
Gaag, L.C. van der (ed.), Symbolic and Quantiative Approaches to Resoning with Uncertainty. 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, 2013, Proceedings
SubjectLecture Notes in Computer Science; Action, intention, and motor control; DI-BCB_DCC_Theme 2: Perception, Action and Control
Typically, when one discusses approximation algorithms for (NP-hard) problems (like Traveling Salesperson, Vertex Cover, Knapsack), one refers to algorithms that return a solution whose value is (at least ideally) close to optimal; e.g., a tour with almost minimal length, a vertex cover of size just above minimal, or a collection of objects that has close to maximal value. In contrast, one might also be interested in approximation algorithms that return solutions that resemble the optimal solutions, i.e., whose structure is akin to the optimal solution, like a tour that is almost similar to the optimal tour, a vertex cover that differs in only a few vertices from the optimal cover, or a collection that is similar to the optimal collection. In this paper, we discuss structure-approximation of the problem of finding the most probable explanation of observations in Bayesian networks, i.e., finding a joint value assignment that looks like the most probable one, rather than has an almost as high value. We show that it is NP-hard to obtain the value of just a single variable of the most probable explanation. However, when partial orders on the values of the variables are available, we can improve on these results.
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.