sum of out-transition probabilities != 1.0 ?

[Andreas Stolcke]

In message <3E43D254.80406 at ei.tum.de>you wrote:
> Hello SRILM users,
> 
> how is it possible that PFSGs, generated with ngram-count and
> make-ngram-pfsg (default discounting) have nodes whose sum of the
> probabilities of all outgoing transitions do not sum to 1.0 (but, e.g.,
> 1.1)?
> 
> I thought this was an important constraint, but maybe I am missing some
> theory...

The PFSG generate by make-ngram-pfsg are meant to be used in a
Viterbi decoding framework.  This means the cost along any given
path through the network corresponds to the correct LM probability 
of the word strings, but there is no need to probabilities to sum to 
1 at any given node.

Specifically, the network has the following structure which can lead to 
probabilities summing to more than 1.  From a given context, you have
transitions corresponding to the explicit N-gram probabilities in the 
LM ("a b", "a c", "a d", etc. out of context "a").  In addition you
have a transition into a backoff node that carries a "probability" equal
to the backoff weight for the context.  The backoff weight multiplied by the
sum of the probabilities of all the words that don't have explicit N-grams
in that context equals the probability mass left over from those 
N-grams.  The backoff weight itself is not a true probability and therefore
the sum over transitions out of the context may well exceed 1.

--Andreas