Re: [Moses-support] SMT decoding complexity
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 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 > 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
Re: [Moses-support] SMT decoding complexity
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 > 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 > -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Moses-support mailing list Moses-support@mit.edu http://mailman.mit.edu/mailman/listinfo/moses-support
Re: [Moses-support] SMT decoding complexity
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 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