{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/99111"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/99111","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Evaluating exact and approximate algorithms for integer linear programming formulations of MAP inference","abstract":"Structured prediction tasks involve an inference step which allows for producing coherent label assignments to the output structure. This can be achieved by constraining the output using prior knowledge about the domain. This paradigm is called Constrained Conditional Models; and it involves augmenting the learning of conditional models with declarative constraints. The MAP inference problem in CCM framework can be solved by formulating an Integer Linear Programming problem. This ILP formulation is generally relaxed to an Linear Programming problem by dropping the integrality constraints and making it tractable. In this work, we evaluate other approximate inference algorithms for the MAP estimate for structured prediction task in the CCM framework. We model the constrained structured prediction problem as a factor graph and use different graphical models based algorithms. We evaluate these methods for the quality of their solution and the computation time over some NLP tasks with varying complexity. For large-scale problems, the tradeoff between inference time and the approximateness of the solution is a crucial aspect. Furthermore, these inference solvers are provided as black-box implementations in Saul, which is a declarative programming language for structured prediction tasks.","abstract_html":"Structured prediction tasks involve an inference step which allows for producing coherent label assignments to the output structure. This can be achieved by constraining the output using prior knowledge about the domain. This paradigm is called Constrained Conditional Models; and it involves augmenting the learning of conditional models with declarative constraints. The MAP inference problem in CCM framework can be solved by formulating an Integer Linear Programming problem. This ILP formulation is generally relaxed to an Linear Programming problem by dropping the integrality constraints and making it tractable. In this work, we evaluate other approximate inference algorithms for the MAP estimate for structured prediction task in the CCM framework. We model the constrained structured prediction problem as a factor graph and use different graphical models based algorithms. We evaluate these methods for the quality of their solution and the computation time over some NLP tasks with varying complexity. For large-scale problems, the tradeoff between inference time and the approximateness of the solution is a crucial aspect. Furthermore, these inference solvers are provided as black-box implementations in Saul, which is a declarative programming language for structured prediction tasks.","abstract_has_math":false,"creators":["Mangipudi, Bhargav"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Roth, Dan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-03-02T19:59:42Z","date_published":"2018-03-02T19:59:42Z","updated_at":"2026-07-22T22:24:37Z","subjects":["Structured inference","Constrained conditional models","Graphical models"],"languages":["en"],"rights":["Copyright 2017 Bhargav Mangipudi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/99111","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Roth, Dan"]},{"key":"dc:creator","label":"Author","values":["Mangipudi, Bhargav"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-03-02T19:59:42Z","2020-03-03T10:15:35Z","2017-07-17","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Structured inference","Constrained conditional models","Graphical models"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Bhargav Mangipudi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/99111"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Structured prediction tasks involve an inference step which allows for producing coherent label assignments to the output structure. This can be achieved by constraining the output using prior knowledge about the domain. This paradigm is called Constrained Conditional Models; and it involves augmenting the learning of conditional models with declarative constraints. The MAP inference problem in CCM framework can be solved by formulating an Integer Linear Programming problem. This ILP formulation is generally relaxed to an Linear Programming problem by dropping the integrality constraints and making it tractable. In this work, we evaluate other approximate inference algorithms for the MAP estimate for structured prediction task in the CCM framework. We model the constrained structured prediction problem as a factor graph and use different graphical models based algorithms. We evaluate these methods for the quality of their solution and the computation time over some NLP tasks with varying complexity. For large-scale problems, the tradeoff between inference time and the approximateness of the solution is a crucial aspect. Furthermore, these inference solvers are provided as black-box implementations in Saul, which is a declarative programming language for structured prediction tasks.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-08-01","The student, Bhargav Mangipudi, accepted the attached license on 2017-07-17 at 10:20.","The student, Bhargav Mangipudi, submitted this Thesis for approval on 2017-07-17 at 10:24.","This Thesis was approved for publication on 2017-07-17 at 12:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11490 on 2018-03-02 at 13:02:20","Made available in DSpace on 2018-03-02T19:59:42Z (GMT). No. of bitstreams: 2 MANGIPUDI-THESIS-2017.pdf: 416049 bytes, checksum: e15dc7aaa87df495d28ac95da637b29d (MD5) LICENSE.txt: 4214 bytes, checksum: 606582efcc2e4e486448b999ae9643e5 (MD5) Previous issue date: 2017-07-17","Embargo set by: Seth Robbins for item 105065 Lift date: 2020-03-02T19:59:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105065 Lift date: 2020-03-02T20:02:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105065 on 2020-03-03T10:15:35Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Evaluating exact and approximate algorithms for integer linear programming formulations of MAP inference"]}]}],"canonical_facts":{"dc:contributor":["Roth, Dan"],"dc:creator":["Mangipudi, Bhargav"],"dc:date":["2018-03-02T19:59:42Z","2020-03-03T10:15:35Z","2017-07-17","2017-08"],"dc:description":["Structured prediction tasks involve an inference step which allows for producing coherent label assignments to the output structure. This can be achieved by constraining the output using prior knowledge about the domain. This paradigm is called Constrained Conditional Models; and it involves augmenting the learning of conditional models with declarative constraints. The MAP inference problem in CCM framework can be solved by formulating an Integer Linear Programming problem. This ILP formulation is generally relaxed to an Linear Programming problem by dropping the integrality constraints and making it tractable. In this work, we evaluate other approximate inference algorithms for the MAP estimate for structured prediction task in the CCM framework. We model the constrained structured prediction problem as a factor graph and use different graphical models based algorithms. We evaluate these methods for the quality of their solution and the computation time over some NLP tasks with varying complexity. For large-scale problems, the tradeoff between inference time and the approximateness of the solution is a crucial aspect. Furthermore, these inference solvers are provided as black-box implementations in Saul, which is a declarative programming language for structured prediction tasks.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-08-01","The student, Bhargav Mangipudi, accepted the attached license on 2017-07-17 at 10:20.","The student, Bhargav Mangipudi, submitted this Thesis for approval on 2017-07-17 at 10:24.","This Thesis was approved for publication on 2017-07-17 at 12:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11490 on 2018-03-02 at 13:02:20","Made available in DSpace on 2018-03-02T19:59:42Z (GMT). No. of bitstreams: 2 MANGIPUDI-THESIS-2017.pdf: 416049 bytes, checksum: e15dc7aaa87df495d28ac95da637b29d (MD5) LICENSE.txt: 4214 bytes, checksum: 606582efcc2e4e486448b999ae9643e5 (MD5) Previous issue date: 2017-07-17","Embargo set by: Seth Robbins for item 105065 Lift date: 2020-03-02T19:59:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105065 Lift date: 2020-03-02T20:02:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105065 on 2020-03-03T10:15:35Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/99111"],"dc:language":["en"],"dc:rights":["Copyright 2017 Bhargav Mangipudi"],"dc:subject":["Structured inference","Constrained conditional models","Graphical models"],"dc:title":["Evaluating exact and approximate algorithms for integer linear programming formulations of MAP inference"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:37Z"}