Re: [Moses-support] SMT decoding complexity

[amir haghighi]

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

[Barry Haddow]

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

[Philipp Koehn]

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

[Moses-support] SMT decoding complexity

[amir haghighi]

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