Många fras anpassning modeller fungerar över combinatorial utrymme bijective fras anpassningar. Vi bevisar att hitta en optimal anpassning i detta utrymme är NP-hård, medan computing justering förväntningar är #P-hård. Å andra sidan visar vi att problemet med att hitta en optimal anpassning kan gjutas som ett heltal linjärt program, vilket ger en enkel, deklarativ inställning till Viterbi inference för fras anpassning modeller som är empiriskt ganska effektiv.
REF tar hänsyn till problemet med frasanpassning, dvs. problemet med att hitta en optimal frasbaserad anpassning för ett meningspar med källspråk/målspråk.
The Complexity of Phrase Alignment Problems
{'venue': 'Annual Meeting Of The Association For Computational Linguistics', 'journal': None, 'mag_field_of_study': ['Computer Science']}