Approximating solution structure of the Weighted Sentence Alignment problem
We study the complexity of approximating solution structure of the bijective weighted sentence alignment problem of DeNero and Klein (2008). In particular, we consider the complexity of finding an alignment that has a significant overlap with an optimal alignment. We discuss ways of representing the solution for the general weighted sentence alignment as well as phrases-to-words alignment problem, and show that computing a string which agrees with the optimal sentence partition on more than half (plus an arbitrarily small polynomial fraction) positions for the phrases-to-words alignment is NP-hard. For the general weighted sentence alignment we obtain such bound from the agreement on a little over 2/3 of the bits. Additionally, we generalize the Hamming distance approximation of a solution structure to approximating it with respect to the edit distance metric, obtaining similar lower bounds.
Code (0)
등록된 구현이 없습니다.
Tasks
SentenceSimilar Papers 제목 키워드 기반
A Sentence Meaning Based Alignment Method for Parallel Text Corpora Preparation
Text alignment is crucial to the accuracy of Machine Translation (MT) systems, some NLP tools or any other text processing tasks requiring bilingual data. This research proposes a language independent sentence alignment …
Machine TranslationPositionSentenceTranslationProjection-based Annotation of a Polish Dependency Treebank
This paper presents an approach of automatic annotation of sentences with dependency structures. The approach builds on the idea of cross-lingual dependency projection. The presented method of acquiring dependency trees …
ARCDependency ParsingMachine TranslationQuestion Answering+1Weighted Set-Theoretic Alignment of Comparable Sentences
This article presents the STACCw system for the BUCC 2017 shared task on parallel sentence extraction from comparable corpora. The original STACC approach, based on set-theoretic operations over bags of words, had been p…
Machine TranslationSentenceInter-Weighted Alignment Network for Sentence Pair Modeling
Sentence pair modeling is a crucial problem in the field of natural language processing. In this paper, we propose a model to measure the similarity of a sentence pair focusing on the interaction information. We utilize …
Machine TranslationNatural Language InferenceParaphrase IdentificationQuestion Answering+6Learning Landmark-Based Ensembles with Random Fourier Features and Gradient Boosting
We propose a Gradient Boosting algorithm for learning an ensemble of kernel functions adapted to the task at hand. Unlike state-of-the-art Multiple Kernel Learning techniques that make use of a pre-computed dictionary of…