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
