Hi Amir You could also try this paper for a derivation of the complexity of PBMT decoding https://www.aclweb.org/anthology/E/E09/E09-1061v2.pdf
cheers - Barry On 27/02/17 15:54, Philipp Koehn wrote: > Hi, > > I am not sure if you follow your question - in the formula you cite, > there are exponential terms: 2^n and T^n. > > The Knight paper is worth trying to understand (it's on IBM Models, > but applies similarly to phrase-based models). > > Also keep in mind that limited reordering windows and beam search > makes actual decoding algorithm implementations linear. > > -phi > > On Sun, Feb 26, 2017 at 1:16 PM, amir haghighi > <[email protected]> wrote: >> Hi all, >> >> In the Moses manual and also in SMT textbooks it is mentioned that the >> decoding complexity for PB-SMT is exponential in the source sentence length. >> If we have a source sentence with length n, in decoding by hypothesis >> expansion, we have power(2,n) state, each of them can be reordered in n! >> orders, and each state can be translated in power(T,n), where T is the >> number of translation options, right? >> so the decoder complexity is power(2,n)*n!*power(T,n), so why its mentioned >> that the complexity is exponential? >> >> Could someone please explain for me how the decoder complexity is >> calculated? >> I've read the Knight(1999) paper, but I couldn't understand it. Could you >> please introduce another reference? >> >> Thanks >> >> >> _______________________________________________ >> Moses-support mailing list >> [email protected] >> http://mailman.mit.edu/mailman/listinfo/moses-support >> > _______________________________________________ > Moses-support mailing list > [email protected] > http://mailman.mit.edu/mailman/listinfo/moses-support > -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. _______________________________________________ Moses-support mailing list [email protected] http://mailman.mit.edu/mailman/listinfo/moses-support
