[{"language":[{"iso":"eng"}],"doi":"10.1007/s00453-015-0017-7","quality_controlled":"1","project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7"}],"external_id":{"arxiv":["1210.0508"]},"oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1210.0508","open_access":"1"}],"month":"09","date_created":"2018-12-11T11:54:02Z","date_updated":"2023-10-17T09:51:31Z","volume":76,"author":[{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"},{"first_name":"Rustem","last_name":"Takhanov","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","full_name":"Takhanov, Rustem"}],"related_material":{"record":[{"id":"2272","status":"public","relation":"earlier_version"}]},"publication_status":"published","department":[{"_id":"VlKo"}],"publisher":"Springer","acknowledgement":"This work has been partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616160.","year":"2016","ec_funded":1,"publist_id":"5316","date_published":"2016-09-01T00:00:00Z","page":"17 - 46","publication":"Algorithmica","citation":{"mla":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7.","short":"V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.","chicago":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7.","ama":"Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7","ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.","apa":"Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016."},"day":"01","scopus_import":1,"oa_version":"Preprint","status":"public","title":"Inference algorithms for pattern-based CRFs on sequence data","intvolume":" 76","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1794","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) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We 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 (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights."}],"issue":"1","type":"journal_article"},{"license":"https://creativecommons.org/publicdomain/zero/1.0/","abstract":[{"lang":"eng","text":"Small synthetic discrete tomography problems.\r\nSizes are 32x32, 64z64 and 256x256.\r\nProjection angles are 2, 4, and 6.\r\nNumber of labels are 3 and 5."}],"file_date_updated":"2020-07-14T12:47:02Z","datarep_id":"46","type":"research_data","date_created":"2018-12-12T12:31:31Z","date_updated":"2024-02-21T13:50:21Z","file":[{"access_level":"open_access","file_name":"IST-2016-46-v1+1_discrete_tomography_synthetic.zip","file_size":36058401,"content_type":"application/zip","creator":"system","relation":"main_file","file_id":"5645","checksum":"aa5a16a0dc888da7186fb8fc45e88439","date_created":"2018-12-12T13:05:19Z","date_updated":"2020-07-14T12:47:02Z"}],"oa_version":"Published Version","author":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul","last_name":"Swoboda","full_name":"Swoboda, Paul"}],"contributor":[{"last_name":"Kuske","contributor_type":"data_collector","first_name":"Jan"}],"title":"Synthetic discrete tomography problems","ddc":["006"],"status":"public","department":[{"_id":"VlKo"}],"publisher":"Institute of Science and Technology Austria","year":"2016","_id":"5557","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"09","day":"20","has_accepted_license":"1","article_processing_charge":"No","keyword":["discrete tomography"],"date_published":"2016-09-20T00:00:00Z","doi":"10.15479/AT:ISTA:46","tmp":{"short":"CC0 (1.0)","image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)"},"citation":{"ama":"Swoboda P. Synthetic discrete tomography problems. 2016. doi:10.15479/AT:ISTA:46","ista":"Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science and Technology Austria, 10.15479/AT:ISTA:46.","apa":"Swoboda, P. (2016). Synthetic discrete tomography problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:46","ieee":"P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science and Technology Austria, 2016.","mla":"Swoboda, Paul. Synthetic Discrete Tomography Problems. Institute of Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:46.","short":"P. Swoboda, (2016).","chicago":"Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:46."},"oa":1},{"author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal","full_name":"Rolinek, Michal"},{"first_name":"Rustem","last_name":"Takhanov","full_name":"Takhanov, Rustem"}],"volume":9472,"date_created":"2018-12-11T11:53:10Z","date_updated":"2022-02-01T15:12:35Z","year":"2015","department":[{"_id":"VlKo"}],"publisher":"Springer Nature","publication_status":"published","publist_id":"5519","ec_funded":1,"doi":"10.1007/978-3-662-48971-0_48","conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","start_date":"2015-12-09","location":"Nagoya, Japan","end_date":"2015-12-11"},"language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1504.07067"]},"main_file_link":[{"url":"http://arxiv.org/abs/1504.07067","open_access":"1"}],"project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"quality_controlled":"1","publication_identifier":{"isbn":["978-3-662-48970-3"]},"month":"12","oa_version":"Preprint","_id":"1636","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","intvolume":" 9472","status":"public","title":"Effectiveness of structural restrictions for hybrid CSPs","abstract":[{"text":"Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.","lang":"eng"}],"type":"conference","alternative_title":["LNCS"],"date_published":"2015-12-01T00:00:00Z","citation":{"mla":"Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for Hybrid CSPs.” 26th International Symposium, vol. 9472, Springer Nature, 2015, pp. 566–77, doi:10.1007/978-3-662-48971-0_48.","short":"V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, pp. 566–577.","chicago":"Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness of Structural Restrictions for Hybrid CSPs.” In 26th International Symposium, 9472:566–77. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48971-0_48.","ama":"Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions for hybrid CSPs. In: 26th International Symposium. Vol 9472. Springer Nature; 2015:566-577. doi:10.1007/978-3-662-48971-0_48","ista":"Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 9472, 566–577.","apa":"Kolmogorov, V., Rolinek, M., & Takhanov, R. (2015). Effectiveness of structural restrictions for hybrid CSPs. In 26th International Symposium (Vol. 9472, pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48","ieee":"V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions for hybrid CSPs,” in 26th International Symposium, Nagoya, Japan, 2015, vol. 9472, pp. 566–577."},"publication":"26th International Symposium","page":"566 - 577","article_processing_charge":"No","day":"01","scopus_import":"1"},{"publist_id":"5261","ec_funded":1,"volume":37,"date_created":"2018-12-11T11:54:18Z","date_updated":"2021-01-12T06:53:33Z","author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"}],"publisher":"IEEE","department":[{"_id":"VlKo"}],"publication_status":"published","year":"2015","month":"05","language":[{"iso":"eng"}],"doi":"10.1109/TPAMI.2014.2363465","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1309.5655","open_access":"1"}],"oa":1,"issue":"5","abstract":[{"text":"We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","intvolume":" 37","title":"A new look at reweighted message passing","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1841","day":"01","scopus_import":1,"date_published":"2015-05-01T00:00:00Z","page":"919 - 930","citation":{"short":"V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930.","mla":"Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5, IEEE, 2015, pp. 919–30, doi:10.1109/TPAMI.2014.2363465.","chicago":"Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2015. https://doi.org/10.1109/TPAMI.2014.2363465.","ama":"Kolmogorov V. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2015;37(5):919-930. doi:10.1109/TPAMI.2014.2363465","ieee":"V. Kolmogorov, “A new look at reweighted message passing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5. IEEE, pp. 919–930, 2015.","apa":"Kolmogorov, V. (2015). A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465","ista":"Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37(5), 919–930."},"publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"type":"conference","abstract":[{"text":"Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \\emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.\r\nIn this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.\r\nWe show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm. ","lang":"eng"}],"ec_funded":1,"publist_id":"5240","status":"public","title":"A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle","publication_status":"published","publisher":"IEEE","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"_id":"1859","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:53:40Z","date_created":"2018-12-11T11:54:24Z","oa_version":"Preprint","author":[{"full_name":"Shah, Neel","last_name":"Shah","first_name":"Neel","id":"31ABAF80-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"},{"full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887"}],"scopus_import":1,"day":"01","month":"06","quality_controlled":"1","page":"2737 - 2745","project":[{"_id":"2532554C-B435-11E9-9278-68D0E5697425","grant_number":"308036","call_identifier":"FP7","name":"Lifelong Learning of Visual Scene Understanding"},{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.6804"}],"oa":1,"citation":{"chicago":"Shah, Neel, Vladimir Kolmogorov, and Christoph Lampert. “A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle,” 2737–45. IEEE, 2015. https://doi.org/10.1109/CVPR.2015.7298890.","short":"N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.","mla":"Shah, Neel, et al. A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle. IEEE, 2015, pp. 2737–45, doi:10.1109/CVPR.2015.7298890.","apa":"Shah, N., Kolmogorov, V., & Lampert, C. (2015). A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle (pp. 2737–2745). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. https://doi.org/10.1109/CVPR.2015.7298890","ieee":"N. Shah, V. Kolmogorov, and C. Lampert, “A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle,” presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 2737–2745.","ista":"Shah N, Kolmogorov V, Lampert C. 2015. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. CVPR: Computer Vision and Pattern Recognition, 2737–2745.","ama":"Shah N, Kolmogorov V, Lampert C. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. In: IEEE; 2015:2737-2745. doi:10.1109/CVPR.2015.7298890"},"language":[{"iso":"eng"}],"conference":{"name":"CVPR: Computer Vision and Pattern Recognition","start_date":"2015-06-07","location":"Boston, MA, USA","end_date":"2015-06-12"},"doi":"10.1109/CVPR.2015.7298890","date_published":"2015-06-01T00:00:00Z"}]