Lattice arc LM score

[Vassil Panayotov]

Hi,

I want to play a little with the lattice.py code from SphinxTrain.
I am looking at forward() method. There is a comment in it's body which says
that only bigram LM scores are used "for now". The formula calculating the
alpha score for an arc i currently is:

http://latex.codecogs.com/gif.latex?\alpha_i&space;=&space;\sum_{p(i)}&space;
\alpha_{p(i)}&space;A_i&space;L_i&space;=&space;\sum_{p(i)}&space;\alpha_{p(i)
}&space;A_i&space;P(l(i)|l(p(i)))

, where i is the current arc, p(i) is a predecessor arc for i, l(i) is the
label for arc i and A_i is the acoustic score.

I wonder how an alpha using trigram LM scores should look like?

Is it:

[http://latex.codecogs.com/gif.latex?\alpha_i&space;=&space;\sum_{p(i)}&space;
\alpha_{p(i)}&space;A_i&space;\sum_{p(p(i))}P(l(i)|l(p(i)),&space;l(p(p(i))))]
(http://latex.codecogs.com/gif.latex?%5Calpha_i&space%3B=&space%3B%5Csum_%7Bp%
28i%29%7D&space%3B%5Calpha_%7Bp%28i%29%7D&space%3BA_i&space%3B%5Csum_%7Bp%28p%
28i%29%29%7DP%28l%28i%29%7Cl%28p%28i%29%29%2C&space%3Bl%28p%28p%28i%29%29%29%2
9)

i.e. should I sum together the probabilities of the arc i conditioned on it's
predecessor arc and every predecessor's predecessor (grandparent of the arc
i)?

PS: Although the question is formulated using SphinxTrain code, it is also
about the lattices in general, so I believe it is not entirely irrelevant to
this forum.

Thanks!

[Nickolay V. Shmyrev]

Hello Vassil

Before applying trigrams you basically need to expand lattice (split all the
paths in it) so each trigram will be unique. I'm too lazy to think about
formulas, but SRILM should be a reference implementation for it.

There is a very recent research on how to rescore lattices without expansion
with approximate methods by IBM on ICASSP 2011:

HILL CLIMBING ON SPEECH LATTICES: A NEW RESCORING FRAMEWORK

Ariya Rastrow, Markus Dreyer, Abhinav Sethy, Sanjeev Khudanpur, Bhuvana
Ramabhadran and Mark Dredze

[Vassil Panayotov]

Thank you Nickolay,

I will read about lattice expansion and the paper that you pointed. I thought
the expansion and rescoring are used mostly to incorporate higher order
knowledge sources, than those used during the decoding.
If the lattice is created from S3 using trigram model isn't it possible to use
3-gram LM score without expansion?

[Nickolay V. Shmyrev]

Hello Vassil

The way you create the lattice - with 3-gram search in s3 or 4-gram search in
s3 or however else doesn't matter. Bigram lattice is just a lattice which has
language score between words on edges. So you have edge w1 and edge w2 and
language score between them. You can just load bigram lattice with weights
from a file.

[Vassil Panayotov]

Hello Nickolay,

Yes, that's what I guessed too - it depends on how the lattices are generated.
I've just read the section 2.10 of David Huggins-Daines' thesis where he
explains briefly these issues and says the Sphinx lattices are always unigram.
Are there papers/surveys on lattice generation and expansion that are
considered standard references?

[Nickolay V. Shmyrev]

Unfortunately I'm not aware about good survey on lattices. As in other area
there is lack of good reviews. There is a part on WFST algorithms applied to
lattices, part on various lattice expansion methods, several important
application of the lattices like indexing of them.

SRILM toolkit has long history of lattice algorithms implementation, for
example this one paper is imporant:

Efficient Lattice Representation and Generation
Fuliang Weng Andreas Stolcke Ananth Sankar

[Vassil Panayotov]

Thanks!

[Nickolay V. Shmyrev]

I started some bibliography here

http://cmusphinx.sourceforge.net/wiki/asr:lattices

feel free to add new items

[Vassil Panayotov]

Sure, if I find something interesting I will update the wiki.