En effektiv avkodningsalgoritm är en viktig del av alla statistiska maskinöversättningssystem. Vissa forskare har noterat vissa likheter mellan SMT avkodning och den berömda Traveling Salesman Problem; i synnerhet (Knight, 1999) har visat att alla TSP instans kan kartläggas till en delfall av en ordbaserad SMT modell, visar NP-hårdhet av avkodning uppgiften. I detta dokument fokuserar vi på den omvända kartläggningen, som visar att alla frasbaserade SMT-avkodningsproblem kan omformuleras direkt som en TSP. Omvandlingen är mycket naturlig, fördjupar vår förståelse av avkodningsproblemet, och tillåter direkt användning av någon av de kraftfulla befintliga TSP-lösarna för SMT-avkodning. Vi testar vårt tillvägagångssätt på tre datauppsättningar, och jämför en TSP-baserad avkodare med den populära strålsökningsalgoritmen. I samtliga fall ger vår metod konkurrenskraftiga eller bättre resultat.
REF formulerar det frasbaserade avkodningsproblemet som ett problem för resande säljare (TSP), och dra nytta av befintliga exakta och ungefärliga metoder utformade för TSP.
Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem
{'venue': 'ACL-IJCNLP', 'journal': None, 'mag_field_of_study': ['Computer Science']}