nips nips2008 nips2008-69 nips2008-69-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicol N. Schraudolph, Dmitry Kamenetsky
Abstract: We give polynomial-time algorithms for the exact computation of lowest-energy states, worst margin violators, partition functions, and marginals in certain binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it does not impose any submodularity constraints; instead we require planarity to establish a correspondence with perfect matchings in an expanded dual graph. Maximum-margin parameter estimation for a boundary detection task shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/. 1
[1] V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Analysis and Machine Intelligence, 26(2):147–159, 2004.
[2] A. T. White and L. W. Beineke. Topological graph theory. In L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, chapter 2, pages 15–49. Academic Press, 1978.
[3] J. M. Boyer and W. J. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241–273, 2004. Reference implementation (C source code): http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3/planarity.zip
[4] A. Windsor. Planar graph functions for the boost graph library. C++ source code, boost file vault: http: //boost-consulting.com/vault/index.php?directory=Algorithms/graph, 2007.
[5] C. Gutwenger and P. Mutzel. Graph embedding with minimum depth and maximum external face. In G. Liotta, editor, Graph Drawing 2003, volume 2912 of LNCS, pages 259–272. Springer Verlag, 2004.
[6] P. W. Kasteleyn. The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209–1225, 1961.
[7] M. E. Fisher. Statistical mechanics of dimers on a plane lattice. Phys Rev, 124(6):1664–1672, 1961.
[8] A. Globerson and T. Jaakkola. Approximate inference using planar graph decomposition. In B. Sch¨ lkopf, o J. Platt, and T. Hofmann (eds), Advances in Neural Information Processing Systems 19, 2007. MIT Press.
[9] J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards, 69B:125–130, 1965.
[10] J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965.
[11] W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal on Computing, 11(2):138–148, 1999. C source code: http://www.isye.gatech.edu/˜wcook/blossom4
[12] N. N. Schraudolph and D. Kamenetsky. Efficient exact inference in planar Ising models. Technical Report 0810.4401, arXiv, 2008. http://aps.arxiv.org/abs/0810.4401
[13] S. V. N. Vishwanathan, N. N. Schraudolph, M. Schmidt, and K. Murphy. Accelerated training conditional random fields with stochastic gradient methods. In Proc. Intl. Conf. Machine Learning, pages 969–976, New York, NY, USA, 2006. ACM Press.
[14] B. Taskar, C. Guestrin, and D. Koller. Max-margin Markov networks. In S. Thrun, L. Saul, and B. Sch¨ lkopf (eds), Advances in Neural Information Processing Systems 16, pages 25–32, 2004. MIT Press. o
[15] H. Schramm and J. Zowe. A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM J. Optimization, 2:121–152, 1992.
[16] C. Rother, V. Kolmogorov, A. Blake, and M. Brown. GrabCut ground truth database, 2007. http:// research.microsoft.com/vision/cambridge/i3l/segmentation/GrabCut.htm
[17] S. V. N. Vishwanathan, K. Borgwardt, and N. N. Schraudolph. Fast computation of graph kernels. In B. Sch¨ lkopf, J. Platt, and T. Hofmann (eds), Advances in Neural Information Processing Systems 19, 2007. o
[18] V. Kolmogorov and C. Rother. Minimizing nonsubmodular functions with graph cuts – a review. IEEE Trans. Pattern Analysis and Machine Intelligence, 29(7):1274–1279, 2007.