Algorithm 1: Compute n-gram posterior probabilities on hypergraph (Kumar et al., 2009) 1: sort hypernodes topologically 2: compute inside/outside probabilities and for each hypernode 3: compute edge posterior probability for each hyperedge 4: for each hyperedge do 5: merge n-grams on and keep the highest probability when n-grams are duplicated 6: apply the rule of edge to n-grams on and propagate gram prefixes/suffixes to 7: for each n-gram introduced by do 8: if then 9: 10: else 11: 12: end if 13: end for 14: end for 15: return n-gram posterior probability set 2 We omit the similar algorithm for lattices because of their homogenous structures comparing to hypergraphs as we discussed in Section 2.2.
the total gain score for hypothesis on can be further expanded as: where is a mixture ngram posterior probability.