A Difference-of-Convex Programming Approach With Parallel Branch-and-Bound For Sentence Compression Via A Hybrid Extractive Model
Sentence compression is an important problem in natural language processing with wide applications in text summarization, search engine and human-AI interaction system etc. In this paper, we design a hybrid extractive sentence compression model combining a probability language model and a parse tree language model for compressing sentences by guaranteeing the syntax correctness of the compression results. Our compression model is formulated as an integer linear programming problem, which can be rewritten as a Difference-of-Convex (DC) programming problem based on the exact penalty technique. We use a well-known efficient DC algorithm -- DCA to handle the penalized problem for local optimal solutions. Then a hybrid global optimization algorithm combining DCA with a parallel branch-and-bound framework, namely PDCABB, is used for finding global optimal solutions. Numerical results demonstrate that our sentence compression model can provide excellent compression results evaluated by F-score, and indicate that PDCABB is a promising algorithm for solving our sentence compression model.
Code (0)
등록된 구현이 없습니다.
Tasks
global-optimizationLanguage ModelingLanguage ModellingSentenceSentence CompressionText SummarizationSimilar Papers 제목 키워드 기반
Sentence Compression via DC Programming Approach
Sentence compression is an important problem in natural language processing. In this paper, we firstly establish a new sentence compression model based on the probability model and the parse tree model. Our sentence comp…
SentenceSentence CompressionPrismatic Algorithm for Discrete D.C. Programming Problem
In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bo…
BIG-bench Machine Learningfeature selectionDC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming
Achieving globally optimal point cloud registration under partial overlaps and large misalignments remains a fundamental challenge. While simultaneous transformation ($\boldsymbolθ$) and correspondence ($\mathbf{P}$) est…
Point Cloud RegistrationAn Efficient Pruning Algorithm for Robust Isotonic Regression
We study a generalization of the classic isotonic regression problem where we allow separable nonconvex objective functions, focusing on the case of estimators used in robust regression. A simple dynamic programming app…
regressionHybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets
In many applications, we need algorithms which can align partially overlapping point sets and are invariant to the corresponding transformations. In this work, a method possessing such properties is realized by minimizin…