[{"title":"Computing the M most probable modes of a graphical model","department":[{"_id":"HeEd"},{"_id":"VlKo"},{"_id":"ChLa"}],"author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Zhu","last_name":"Yan","full_name":"Yan, Zhu"},{"first_name":"Dimitris","full_name":"Metaxas, Dimitris","last_name":"Metaxas"},{"full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"3846","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:00:35Z","citation":{"chicago":"Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69. JMLR, 2013.","ista":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model. AISTATS: Conference on Uncertainty in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.","mla":"Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model. Vol. 31, JMLR, 2013, pp. 161–69.","short":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169.","ieee":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the M most probable modes of a graphical model,” presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013, vol. 31, pp. 161–169.","ama":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.","apa":"Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013). Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169). Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR."},"status":"public","type":"conference","conference":{"name":" AISTATS: Conference on Uncertainty in Artificial Intelligence","start_date":"2013-04-29","end_date":"2013-05-01","location":"Scottsdale, AZ, United States"},"_id":"2901","date_published":"2013-01-01T00:00:00Z","volume":31,"date_created":"2018-12-11T12:00:14Z","page":"161 - 169","day":"01","language":[{"iso":"eng"}],"year":"2013","publication_status":"published","month":"01","intvolume":" 31","scopus_import":1,"publisher":"JMLR","alternative_title":[" JMLR: W&CP"],"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://jmlr.org/proceedings/papers/v31/chen13a.html"}],"oa":1,"oa_version":"None","abstract":[{"text":" We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. ","lang":"eng"}]},{"department":[{"_id":"VlKo"}],"date_updated":"2023-10-17T09:51:32Z","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2013-06-16","location":"Atlanta, GA, USA","end_date":"2013-06-21"},"type":"conference","status":"public","_id":"2272","related_material":{"record":[{"id":"1794","status":"public","relation":"later_version"}]},"issue":"3","volume":28,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515","open_access":"1"}],"scopus_import":"1","alternative_title":["JMLR"],"intvolume":" 28","month":"06","abstract":[{"lang":"eng","text":"We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.\r\nWe present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case. "}],"oa_version":"Submitted Version","article_processing_charge":"No","publist_id":"4672","author":[{"full_name":"Takhanov, Rustem","last_name":"Takhanov","first_name":"Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"title":"Inference algorithms for pattern-based CRFs on sequence data","citation":{"ista":"Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs on sequence data. ICML’13 Proceedings of the 30th International Conference on International. ICML: International Conference on Machine Learning, JMLR, vol. 28, 145–153.","chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference on International, 28:145–53. ML Research Press, 2013.","short":"R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, ML Research Press, 2013, pp. 145–153.","ieee":"R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs on sequence data,” in ICML’13 Proceedings of the 30th International Conference on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.","apa":"Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.","ama":"Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence data. In: ICML’13 Proceedings of the 30th International Conference on International. Vol 28. ML Research Press; 2013:145-153.","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"145 - 153","date_created":"2018-12-11T11:56:41Z","date_published":"2013-06-01T00:00:00Z","year":"2013","publication":"ICML'13 Proceedings of the 30th International Conference on International","day":"01","oa":1,"quality_controlled":"1","publisher":"ML Research Press"},{"_id":"2274","pubrep_id":"671","status":"public","type":"report","ddc":["530"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-03-20T08:31:49Z","citation":{"ista":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space, IST Austria,p.","chicago":"Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. Proofs of Space. IST Austria, 2013.","ieee":"S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of Space. IST Austria, 2013.","short":"S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space, IST Austria, 2013.","ama":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space. IST Austria; 2013.","apa":"Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs of Space. IST Austria.","mla":"Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013."},"title":"Proofs of Space","file_date_updated":"2020-07-14T12:45:36Z","department":[{"_id":"VlKo"},{"_id":"KrPi"}],"publist_id":"4670","author":[{"first_name":"Stefan","full_name":"Dziembowski, Stefan","last_name":"Dziembowski"},{"last_name":"Faust","full_name":"Faust, Sebastian","first_name":"Sebastian"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"oa_version":"Published Version","abstract":[{"text":"Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees. ","lang":"eng"}],"month":"11","oa":1,"scopus_import":1,"publisher":"IST Austria","language":[{"iso":"eng"}],"day":"28","file":[{"creator":"system","file_size":405870,"date_updated":"2020-07-14T12:45:36Z","file_name":"IST-2016-671-v1+1_796.pdf","date_created":"2018-12-12T10:16:11Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"5197","checksum":"37b61637b62fc079d9141c59d9f1a94f"}],"year":"2013","publication_status":"published","has_accepted_license":"1","date_created":"2018-12-11T11:56:42Z","related_material":{"record":[{"status":"public","id":"1675","relation":"later_version"}]},"date_published":"2013-11-28T00:00:00Z"},{"scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1309.5469"}],"month":"04","intvolume":" 7422","abstract":[{"text":"In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.\r\n","lang":"eng"}],"oa_version":"Preprint","volume":7422,"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"start_date":"2012-04-19","location":"Athens, Greece","end_date":"2012-04-21","name":"ISCO: International Symposium on Combinatorial Optimization"},"status":"public","_id":"2930","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T07:00:46Z","quality_controlled":"1","publisher":"Springer","oa":1,"acknowledgement":"We would like to thank Andrei Krokhin for encourag- ing our cooperation, for helpful discussions, and for his critical reading of the manuscript.\r\n","page":"451 - 462","doi":"10.1007/978-3-642-32147-4_40","date_published":"2012-04-01T00:00:00Z","date_created":"2018-12-11T12:00:24Z","year":"2012","day":"01","publist_id":"3806","author":[{"first_name":"Anna","last_name":"Huber","full_name":"Huber, Anna"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"title":"Towards minimizing k-submodular functions","citation":{"mla":"Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions. Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40.","apa":"Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions (Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40","ama":"Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol 7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40","short":"A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462.","ieee":"A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,” presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece, 2012, vol. 7422, pp. 451–462.","chicago":"Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40.","ista":"Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"month":"05","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1205.6352"}],"oa":1,"publisher":"ArXiv","oa_version":"Preprint","abstract":[{"text":" This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. ","lang":"eng"}],"date_created":"2018-12-11T12:00:23Z","date_published":"2012-05-29T00:00:00Z","page":"16","language":[{"iso":"eng"}],"publication":"arXiv","day":"29","year":"2012","publication_status":"published","status":"public","type":"preprint","_id":"2928","department":[{"_id":"VlKo"}],"title":"Generalized sequential tree-reweighted message passing","external_id":{"arxiv":["1205.6352"]},"article_processing_charge":"No","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"first_name":"Thomas","full_name":"Schoenemann, Thomas","last_name":"Schoenemann"}],"publist_id":"3809","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:00:45Z","citation":{"ama":"Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message passing. arXiv. 2012.","apa":"Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted message passing. arXiv. ArXiv.","short":"V. Kolmogorov, T. Schoenemann, ArXiv (2012).","ieee":"V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted message passing,” arXiv. ArXiv, 2012.","mla":"Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv, ArXiv, 2012.","ista":"Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, .","chicago":"Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv. ArXiv, 2012."}}]