NLP Wiki

User Tools

Site Tools

Trace: • bayesian_methods • em_algorithm • gumbel-max_trick • information_theory • automl • cloud_computing_platforms • integer_linear_programming
nlp:integer_linear_programming

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
nlp:integer_linear_programming [2021/04/01 08:25] – [Neural Papers] jmflanignlp:integer_linear_programming [2023/06/15 07:36] (current) – external edit 127.0.0.1
Line 9: Line 9:
   * [[https://www.aclweb.org/anthology/W04-2401.pdf|Roth & Yih 2004 - A Linear Programming Formulation for Global Inference in Natural Language Tasks]]   * [[https://www.aclweb.org/anthology/W04-2401.pdf|Roth & Yih 2004 - A Linear Programming Formulation for Global Inference in Natural Language Tasks]]
   * [[https://www.aclweb.org/anthology/P09-1039.pdf|Martins et al 2009 - Concise Integer Linear Programming Formulations for Dependency Parsing]]   * [[https://www.aclweb.org/anthology/P09-1039.pdf|Martins et al 2009 - Concise Integer Linear Programming Formulations for Dependency Parsing]]
 +  * [[https://www.aclweb.org/anthology/N09-2002.pdf|Riedel & Clark 2009 - Revisiting Optimal Decoding for Machine Translation IBM Model 4]] Optimal decoding for IBM model 4 using an ILP
   * [[https://www.isi.edu/natural-language/amr/smatch-13.pdf|Cai & Knight 2013 - Smatch: an Evaluation Metric for Semantic Feature Structures]]   * [[https://www.isi.edu/natural-language/amr/smatch-13.pdf|Cai & Knight 2013 - Smatch: an Evaluation Metric for Semantic Feature Structures]]
   * [[https://arxiv.org/pdf/1609.07034.pdf|Banerjee et al 2016 - Multi-Document Abstractive Summarization Using ILP based Multi-Sentence Compression]]   * [[https://arxiv.org/pdf/1609.07034.pdf|Banerjee et al 2016 - Multi-Document Abstractive Summarization Using ILP based Multi-Sentence Compression]]
     * Follow-up work (non ILP-based) here: [[https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7996331&casa_token=jZ-HBJM84t8AAAAA:-ACITeV2f0qoh8_p44VRZf2pchYpYNqYSq80lVkittMfd3xF_zHTLYdvyxtAjegvIJ25DKWQ&tag=1|2017 - Multi-Document Abstractive Summarization using Chunk-graph and Recurrent Neural Network]]     * Follow-up work (non ILP-based) here: [[https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7996331&casa_token=jZ-HBJM84t8AAAAA:-ACITeV2f0qoh8_p44VRZf2pchYpYNqYSq80lVkittMfd3xF_zHTLYdvyxtAjegvIJ25DKWQ&tag=1|2017 - Multi-Document Abstractive Summarization using Chunk-graph and Recurrent Neural Network]]
   * [[https://www.aclweb.org/anthology/N15-1145.pdf|Li et al 2015 - Improving Update Summarization via Supervised ILP and Sentence Reranking]]   * [[https://www.aclweb.org/anthology/N15-1145.pdf|Li et al 2015 - Improving Update Summarization via Supervised ILP and Sentence Reranking]]
 +  * [[https://www.aclweb.org/anthology/W18-1704.pdf|2018 - Multi-Sentence Compression with Word Vertex-Labeled Graphs and Integer Linear Programming]]
 +
  
 ===== Neural Papers ===== ===== Neural Papers =====
   * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.2787&rep=rep1&type=pdf|Cao et al 2015 - Ranking with Recursive Neural Networks and Its Application to Multi-document Summarization]]  Their best model uses an ILP decoder with RNN (see table 3)   * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.2787&rep=rep1&type=pdf|Cao et al 2015 - Ranking with Recursive Neural Networks and Its Application to Multi-document Summarization]]  Their best model uses an ILP decoder with RNN (see table 3)
   * [[https://www.aclweb.org/anthology/D18-1008.pdf|Lamm et al 2018 - Textual Analogy Parsing: What’s Shared and What’s Compared among Analogous Facts]]  Their best model uses a neural CRF with an ILP decoder for prediction (table 3)   * [[https://www.aclweb.org/anthology/D18-1008.pdf|Lamm et al 2018 - Textual Analogy Parsing: What’s Shared and What’s Compared among Analogous Facts]]  Their best model uses a neural CRF with an ILP decoder for prediction (table 3)
-  * [[https://www.aclweb.org/anthology/2020.coling-main.418.pdf|Chousa et al 2020 - SpanAlign: Sentence Alignment Method 
-based on Cross-Language Span Prediction and ILP]] 
   * [[https://www.aclweb.org/anthology/D19-1642.pdf|Ning et al 2019 - An Improved Neural Baseline for Temporal Relation Extraction]], using the ILP from [[https://www.aclweb.org/anthology/D17-1108.pdf|Ning et al 2017 - A Structured Learning Approach to Temporal Relation Extraction]]   * [[https://www.aclweb.org/anthology/D19-1642.pdf|Ning et al 2019 - An Improved Neural Baseline for Temporal Relation Extraction]], using the ILP from [[https://www.aclweb.org/anthology/D17-1108.pdf|Ning et al 2017 - A Structured Learning Approach to Temporal Relation Extraction]]
 +  * [[https://www.aclweb.org/anthology/2020.coling-main.418.pdf|Chousa et al 2020 - SpanAlign: Sentence Alignment Method based on Cross-Language Span Prediction and ILP]]
   * [[https://www.aclweb.org/anthology/2020.textgraphs-1.13.pdf|Gupta & Srinivasaraghavan 2020 - Explanation Regeneration via Multi-Hop ILP Inference over Knowledge Base]]   * [[https://www.aclweb.org/anthology/2020.textgraphs-1.13.pdf|Gupta & Srinivasaraghavan 2020 - Explanation Regeneration via Multi-Hop ILP Inference over Knowledge Base]]
 +  * [[https://aclanthology.org/2020.emnlp-main.9.pdf|Saha et al 2020 - PRover: Proof Generation for Interpretable Reasoning over Rules]]
 +  * [[https://aclanthology.org/2021.findings-acl.277.pdf|Sun et al 2021 - Probabilistic Graph Reasoning for Natural Proof Generation]]
 +
 +===== Theoretical Results =====
 +  * Not every problem solvable in polynomial-time has a compact extended ILP formulation (see Yannakakis’ problem, section 4.10.3, page 181 of Integer Programming by Conforti et al).
  
 ===== Software ===== ===== Software =====
   * Gurobi: [[https://www.gurobi.com/academia/academic-program-and-licenses/|Free Academic License]], also [[https://www.gurobi.com/academia/|Gurobi - Academia]].  Currently the best ILP solver   * Gurobi: [[https://www.gurobi.com/academia/academic-program-and-licenses/|Free Academic License]], also [[https://www.gurobi.com/academia/|Gurobi - Academia]].  Currently the best ILP solver
   * CPLEX.  Another good ILP solver   * CPLEX.  Another good ILP solver
 +
 +===== Courses and Slides =====
 +(Search "integer linear programming slides pdf" on Google)
 +  * [[http://www.cs.cmu.edu/~arielpro/15780s17/slides/integer_prog.pdf|Ziko Kolter - Integer Linear Programming]]
 +  * [[https://ilpinference.github.io/eacl2017/outline.html|Tutorial at EACL 2017]]
 +  * [[https://www2.cs.duke.edu/courses/fall10/cps296.1/|Integer Linear Programming at Duke]]
 +  * [[https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/lecture-notes/MIT15_053S13_lec10.pdf|MIT Sloan - ILP Lecture]]
 +  * [[https://www.isical.ac.in/~arijit/courses/autumn2016/ILP-Lecture-1.pdf|ILP Slides]]
 +
 +===== Related Pages =====
 +  * [[Structured Prediction Energy Networks]]
  
nlp/integer_linear_programming.1617265538.txt.gz · Last modified: 2023/06/15 07:36 (external edit)
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki