1
$\begingroup$

I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly.

In this scenario there is a reference transducer 'B' which accepts input strings in language 'a', and outputs strings in language 'b'. 'B' is constructed prior to starting the search. There is then an acceptor 'A' which constitutes a directed, weighted, acyclic automaton (a lattice) and which encodes strings in language 'a'. 'A' is constructed dynamically, arc-by-arc, and composed with 'B' on-the-fly. The output side of A*B is then projected, resulting in 'C' - a directed, weighted, acyclic automaton that encodes strings in language 'b'. In the static case this process can be summarized as,

C = project_output( compose(A, B) )

where 'A' is constructed dynamically.

I am interested in computing the k-shortest paths through 'C' dynamically. Because 'A' is a lattice, it is also possible that there will be multiple paths through 'C' that are equivalent, but arrived at via different paths through the input side of 'B'. Thus the weight corresponding to any unique path through 'C' seems like it should correspond to the sum of the weights of all input paths that share the same output. Intuitively, if we have two distinct input paths in the lattice that result in the same output from 'C', their associated probabilities should be summed in some way. Thus in fact we would like to compute 'D',

D = k_shortest_unique( project_output( compose(A, B) ) )

In the static case I believe we could compute this by performing,

D = k_shortest( minimize( determinize( rm_epsilon( project_o( compose(A, B) ) ) ) ) )

and running all of the operations except for the final k_shortest algorithm in the log semiring. Assuming I've thought this out correctly ( a big assumption ) this should ensure that when identical paths through 'C' are merged, their weights are summed. Computing the k-shortest paths through 'D' in the tropical semiring should then still produce the correct summed result.

This approach is fine for computing the result statically, and most of these operations admit a lazy implementation anyway, but I'm wondering if anyone knows some good references regarding this type of problem in a dynamic or on-the-fly context. Note also that graph edges will only ever be added to the 'right-hand edge' of the graph, as we construct 'A' and compose it with 'B'.

Finally, in practice the idea is that each time we add an arc to 'A', this should result in an incremental update to the list of potential paths through 'C', and an update to the total weight associated with it. The list will most likely never have more than 10 or 15 unique output candidate paths, but this might correspond to 10x or more input paths through 'A'.

That turned out really long.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.