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
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
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
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
