Weighted Finite State Transducers- directed graphs
- each node represents a "state"
- each edge represents a "state transition"
- symbol input/ouput is associated with transitions (not states, as in HMMs)
- each transition has an associated cost (usually positive, but not necessary)
- contain HMMs as a subset
- think of WFSTs as...
- a compact representation of a large set of string->string mappings
- associated weights
- efficient algorithms for manipulating those mappings
Basic WFST Operations- composition
- applying a language model to a recognition lattice
- building up a language model from components
- decoding
- Viterbi decoding
- full computation of posterior
- best path graph search, beam search
- construction and optimization
- intersection
- minimization
- epsilon removal
- determinization
- learning
Basic WFST Usage- dictionaries
- dictionaries are models of the form: (word space)* and associated word frequencies
- unigram models
- n-graph models
- sequences of characters/glyphs and their associated probabilities
- n-gram models
- sequences of words and their associated probabilities
- noise models, spelling error models
- allows deletion and insertion of characters in the input
Building WFSTs- you can build WFSTs "by hand"
- there are some utility classes
- fst_ignoring, keeping, edit_distance, limited_edit_distance, insdel, size_range -- simple WFSTs
- UnigramModel -- character (or word) frequencies
- DictionaryModel -- construct a Trie with addWord, addWordSymbol, addWordTranscription, etc.
- NgramModel -- construct a model with addNgram etc. (compute frequencies separately)
- there are several third party language modeling toolkits as well
- we'll be evaluating them and integrating them
Example-- (building of n-gram counts table not shown) -- model = openfst.make_NgramModel() for ngram,c in pairs(counts) do prefix = ngram:sub(1,ngram:len()-1) p = prefixes[prefix] cost = - math.log(c/p) model:addNgram(ngram,cost) end fst = model:take() fst:Write("2gram.fst")
|
|
