Partial Optimality in the Preordering Problem
Preordering is a generalization of clustering and partial ordering with applications in bioinformatics and social network analysis. Given a finite set $V$ and a value $c_{ab} \in \mathbb{R}$ for every ordered pair $ab$ of elements of $V$, the preordering problem asks for a preorder $\lesssim$ on $V$ that maximizes the sum of the values of those pairs $ab$ for which $a \lesssim b$. Building on the state of the art in solving this NP-hard problem partially, we contribute new partial optimality conditions and efficient algorithms for deciding these conditions. In experiments with real and synthetic data, these new conditions increase, in particular, the fraction of pairs $ab$ for which it is decided efficiently that $a \not\lesssim b$ in an optimal preorder.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Preordering: A hybrid of correlation clustering and partial ordering
We discuss the preordering problem, a joint relaxation of the correlation clustering problem and the partial ordering problem. We show that preordering remains NP-hard even for values in $\{-1,0,1\}$. We introduce a line…
ClusteringRecursive Neural Network Based Preordering for English-to-Japanese Machine Translation
The word order between source and target languages significantly influences the translation quality in machine translation. Preordering can effectively address this problem. Previous preordering methods require a manual …
Machine TranslationTranslationPhrase-based Machine Translation using Multiple Preordering Candidates
In this paper, we propose a new decoding method for phrase-based statistical machine translation which directly uses multiple preordering candidates as a graph structure. Compared with previous phrase-based decoding meth…
DecoderMachine TranslationTranslationIntegrating empty category detection into preordering Machine Translation
We propose a method for integrating Japanese empty category detection into the preordering process of Japanese-to-English statistical machine translation. First, we apply machine-learning-based empty category detection t…
Machine TranslationSentenceTranslationWord Alignment