Algorithms for the nearest assignment problem
Pages 5096 - 5102
Abstract
We consider the following nearest assignment problem (NAP): given a Bayesian network B and probability value q, find a configuration ω of variables in B such that the difference between q and probability of ω is minimized. NAP is much harder than conventional inference problems such as finding the most probable explanation in that it is NP-hard even on independent Bayesian networks (IBNs), which are networks having no edges. We propose a two-way number partitioning encoding of NAP on IBNs and then leverage poly-time approximation algorithms from the number partitioning literature to develop algorithms with guarantees for solving NAP. We extend our basic algorithm from IBNs to arbitrary probabilistic graphical models by leveraging cutset-based conditioning, local search and (Rao-Blackwellised) sampling algorithms. We derive approximation and complexity guarantees for our new algorithms and show experimentally that they are quite accurate in practice.
References
[1]
B. Bidyuk and R. Dechter. On finding minimal w-cutset. In UAI, pages 43-50, 2004.
[2]
B. Bidyuk and R. Dechter. Cutset Sampling for Bayesian Networks. JAIR, 28:1-48, 2007.
[3]
A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
[4]
R. Dechter, K. Kask, E. Bin, and R. Emek. Generating random solutions for constraint satisfaction problems. In AAAI, pages 15-21, 2002.
[5]
R. Dechter. Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artificial Intelligence, 41(3):273-312, 1990.
[6]
P. Domingos and D. Lowd. Markov Logic: An Interface Layer for Artificial Intelligence. Morgan & Claypool, San Rafael, CA, 2009.
[7]
L. Fournier, Y. Arbetman, and M. Levinger. Functional verification methodology for microprocessors using the genesys test-program generator. In DATE, 1999.
[8]
V. Gogate. Results of the 2014 uai competition. http://www.hlt.utdallas.edu/~vgogate/uai14-competition/index.html, 2014.
[9]
M. Henrion, J. Breese, and E. Horvitz. Decision Analysis and Expert Systems. AI Magazine, 12:64-91, 1992.
[10]
N. Karmarkar and R. M. Karp. The differencing method of set partitioning. Technical Report UCB/CSD-83-113, EECS Department, University of California, Berkeley, 1983.
[11]
K. Kask and R. Dechter. A graph-based method for improving GSAT. In AAAI, pages 350- 355, 1996.
[12]
R. E Korf. A complete anytime algorithm for number partitioning. Artificial Intelligence, 106(2):181- 203, 1998.
[13]
Todd Kulesza, Margaret Burnett, Weng-Keen Wong, and Simone Stumpf. Principles of explanatory debugging to personalize interactive machine learning. In IUI, pages 126-137. ACM, 2015.
[14]
F. Matteo and M. Silvano. Worst-case analysis of the differencing method for the partition problem. Mathematical Programming, 37(1):117- 120, Feb 1987.
[15]
J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA, 1988.
[16]
M. Richardson and P. Domingos. Markov Logic Networks. Machine Learning, 62:107-136, 2006.
[17]
D. B. Smith, S. Rouhani, and V. Gogate. Order statistics for probabilistic graphical models. In IJCAI, pages 4625-4631, 2017.
[18]
V. V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001.
Recommendations
The bilinear assignment problem: complexity and polynomially solvable special cases
In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, $$m\le n$$m≤n. BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that ...
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem
FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer ScienceIn this work we look back into the proof of the PCP Theorem, with the goal of finding new proofs that are "more combinatorial" and arguably simpler. For that we introduce the notion of an assignment tester, which is a strengthening of the standard PCP ...
Tight Lower Bound for the Channel Assignment Problem
We study the complexity of the Channel Assignment problem. An open problem asks whether Channel Assignment admits an O(cn) (times a polynomial in the bit size) time algorithm, where n is a number of the vertices, for a constant c independent of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Adobe
- IBMR: IBM Research
- ERICSSON
- Microsoft: Microsoft
- AI Journal: AI Journal
Publisher
AAAI Press
Publication History
Published: 13 July 2018
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024