?
Minimizing sparse high-order energies by submodular vertex-cover
.
Delong A., Veksler O., Osokin A., Boykov Y.
Inference in high-order graphical models has become important in recent years. Several approaches are based, for example, on generalized message-passing, or on transformation to a pairwise model with extra 'auxiliary' variables. We focus on a special case where a much more efficient transformation is possible. Instead of adding variables, we transform the original problem into a comparatively small instance of submodular vertex-cover. These vertex-cover instances can then be attacked by existing algorithms (e.g. belief propagation, QPBO), where they often run 4-15 times faster and find better solutions than when applied to the original problem. We evaluate our approach on synthetic data, then we show applications within a fast hierarchical clustering and model-fitting framework.
Language:
English
In book
Lake Tahoe: Curran Associates, Inc., 2012.
Kostylev Ilya, Kalyagin Valeriy, Operations Research Forum 2025 Vol. 6 Article 188
Graphical modelling has become a useful tool in modern data mining. Graphical model selection by observations is an important challenge for various practical applications of this technique. Optimization-based approaches are a basis for many fast and effcient algorithms to solve this problem. Many known properties of graphical model selection algorithms are related with the case ...
Added: November 26, 2025
Shpakova T., Bach F., Osokin A., , in: Proceedings of the international conference on Uncertainty in Artificial Intelligence (UAI 2018).: [б.и.], 2018. P. 1–11.
We consider the structured-output prediction problem through probabilistic approaches and generalize the ``''perturb-and-MAP'' framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many related MAP inference problems. We show that for log-supermodular pairwise models these operations can be performed efficiently ...
Added: October 29, 2018
Grechikhin I., /. 2017.
Graphical models are used in a variety of problems to uncover hidden structures. There is a huge number of different identification procedures, constructed for different purposes. However, it is important to research different properties of such procedures and compare them in order to find out the best procedure or the best use case for some ...
Added: October 20, 2017
Kohli P., Osokin A., Jegelka S., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2013).: Portland: IEEE, 2013. P. 1971–1978.
We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while ...
Added: October 19, 2017
Delong A., Osokin A., Isack H. et al., International Journal of Computer Vision 2012 Vol. 96 No. 1 P. 1–27
The α-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. It is commonly used to minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main algorithmic contribution is an extension of α-expansion that also optimizes “label costs” with well-characterized optimality bounds. Label costs penalize a solution based ...
Added: October 18, 2017
Osokin A., Vetrov D., Kolmogorov V., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011).: Colorado Springs: IEEE, 2011. P. 1889–1896.
In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submodular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial ...
Added: October 18, 2017
Delong A., Osokin A., Isack H. et al., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010).: San Francisco: IEEE, 2010. P. 2173–2180.
The α-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend α-expansion so that it can simultaneously optimize “label costs” as well. An energy with label ...
Added: October 18, 2017
Kirillov A., Gavrikov M., Lobacheva E. et al., , in: Proceedings of the 27th British Machine Vision Conference.: -, 2016. P. 1–12.
The Shape Boltzmann Machine (SBM) and its multilabel version MSBM have been recently introduced as deep generative models that capture the variations of an object shape. While being more flexible MSBM requires datasets with labeled parts of the objects for training. In the paper we present an algorithm for training MSBM using binary masks of ...
Added: February 24, 2017
Arefiev N., / Series WP BRP "Basic research program". 2016. No. 124/EC/2016.
The literature on graphical models and the literature on identification pursue similar goals, but do not use entirely each other’s results, because represent them in different languages. To ease the communication between these fields, I translate the most important theorems on identification of linear Gaussian Simultaneous Equations Models (SEMs) and Structural Vector Autoregressions (SVARs) into ...
Added: April 14, 2016
Кириллов А. Н., Гавриков М. И., Lobacheva E. et al., Интеллектуальные системы. Теория и приложения 2015 Т. 19 № 2 С. 75–95
In this paper we consider the Shape Boltzmann Machine(SBM) and its multi-label version MSBM. We present an algorithm for training MSBM using only binary masks of objects and the seeds which approximately correspond to the locations of objects parts. ...
Added: September 30, 2015
Osokin A., Vetrov D., IEEE Transactions on Pattern Analysis and Machine Intelligence 2015 Vol. 37 No. 7 P. 1347–1359
In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approach (SMR) based on a ...
Added: July 6, 2015
Vetrov D., Kohli P., Osokin A. et al., Lecture Notes in Computer Science 2015 Vol. 8932 P. 406–420
Structured-output learning is a challenging problem; particularly so because of the difficulty in obtaining large datasets of fully labelled instances for training. In this paper we try to overcome this difficulty by presenting a multi-utility learning framework for structured prediction that can learn from training instances with different forms of supervision. We propose a unified ...
Added: April 9, 2015
Vetrov D., Osokin A., Rodomanov A. et al., Journal of Machine Learning Research 2014
In the paper we present a new framework for dealing with probabilistic graphical models. Our approach relies on the recently proposed Tensor Train format (TT-format) of a tensor that while being compact allows for efficient application of linear algebra operations. We present a way to convert the energy of a Markov random field to the ...
Added: March 18, 2015
Vetrov D., Osokin A., Novikov A. et al., , in: JMLR Workshop and Conference ProceedingsIssue 32: Proceedings of The 31st International Conference on Machine Learning.: Beijing: Microtome Publishing, 2014. P. 811–819.
In the paper we present a new framework for dealing with probabilistic graphical models. Our approach relies on the recently proposed Tensor Train format (TT-format) of a tensor that while being compact allows for efficient application of linear algebra operations. We present a way to convert the energy of a Markov random field to the ...
Added: March 14, 2015
Bartunov S., Korshunov A., Park S. et al., , in: Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining, Workshop on Social Network Mining and Analysis.: ACM, 2012.
In the modern Web, it is common for an active person to have several profiles in different online social networks. As new general-purpose and niche social network services arise every year, the problem of social data integration will likely remain actual in the nearest future. Discovering multiple profiles of a single person across different social ...
Added: March 4, 2015
Arefiev N., / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2014. No. WP BRP 79/EC/2014.
I propose a method identification of structural vector autoregressions (SVARs) and simultaneous equations models (SEMs) with orthogonal structural shocks using testable identification restrictions. If some sparsity conditions are satisfied, the method produces a set of testable inclusions and exclusions, sufficient for the full identification. The method stems from the theory of probabilistic graphical models and ...
Added: November 28, 2014