Weighted Finite State Transducers

Weighted finite state transducers (WFSTs) are graphs capable of translating an input sequence of symbols to an output sequence of symbols and associate a particular weight to this conversion.

Firstly we define the input and output symbols:

julia> isym = [s for s in "hello"];

julia> osym = [s for s in "world"];

We can construct a WFST by adding arcs, where each arc has an input label, an output label and a weight (which is typically defined in a particular semiring):

julia> using FiniteStateTransducers

julia> W = ProbabilityWeight{Float64} # weight type

julia> A = WFST(isym,osym; W=W); # empty wfst

julia> add_arc!(A,1=>2,'h'=>'w',1); # arc from state 1 to 2 with in label 'h' and out label 'w' and weight 1

julia> add_arc!(A,2=>3,'e'=>'o',1); # arc from state 2 to 3 with in label 'e' and out label 'w' and weight 0.5

julia> add_arc!(A,3=>4,'l'=>'r',1);

julia> add_arc!(A,4=>5,'l'=>'l',1); 

julia> add_arc!(A,5=>6,'o'=>'d',1);

julia> initial!(A,1); final!(A,6) # set initial and final state
WFST #states: 6, #arcs: 5, #isym: 4, #osym: 5
h:w/1.0 → (2)
e:o/1.0 → (3)
l:r/1.0 → (4)
l:l/1.0 → (5)
o:d/1.0 → (6)

We can now plug the input sequence ['h','e','l','l','o'] into the WFST:

julia> A(['h','e','l','l','o'])
(['w', 'o', 'r', 'l', 'd'], 1.0)

The input sequence is translated into ['w', 'o', 'r', 'l', 'd'] with probability 1.0. A sequence that cannot be accepted will return a null probability instead:

julia> A(['h','e','l','l'])
(['w', 'o', 'r', 'l'], 0.0)

We could modify the WFST by adding an arc with an epsilon label, which is special symbol ϵ that can be skipped (see Sec. Epsilon label for more info):

julia> add_arc!(A,5=>6,'ϵ'=>'d',0.001);

julia> A(['h','e','l','l'])
(['w', 'o', 'r', 'l', 'd'], 0.001)

Here we used a small probability for this epsilon arc and this results in a low probability of the transduced output sequence. In fact the resulting probability of a sequence is the product of the weights of the arcs that were accessed (see Paths).


The method (transduce::WFST)(ilabels::Vector) transduce the sequence of ilabel using the WFST fst requires the WFST to be input deterministic, see is_deterministic.

See [1] for a good tutorial on WFST with the focus on speech recognition.