Thanks Philipp, Yes, my formula has exponential terma but as the growth of factorial is greater than the growth of exponential, the complexity of the decoding algorithm(without any constraint on reordering or pruning the search space) is of O(n!), right?
Thanks Barry, I'll read the paper. On Mon, Feb 27, 2017 at 7:24 PM, Philipp Koehn <p...@jhu.edu> 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 > <amir.haghighi.tehr...@gmail.com> 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 > > Moses-support@mit.edu > > http://mailman.mit.edu/mailman/listinfo/moses-support > > >
_______________________________________________ Moses-support mailing list Moses-support@mit.edu http://mailman.mit.edu/mailman/listinfo/moses-support
