Composition and Weight Pushing of Monotonic Subsequential Failure Transducers Representing Probabilistic Models

Abstract

We present a construction for the composition of subsequential transducers (representing conditional probabilistic models) with subsequential failure transducers (representing probabilistic models). Under certain conditions, satisfied by the corresponding transduction devices, a more efficient construction is applicable that avoids the creation of unnecessary states. Furthermore, the weights of the resulting failure transducers can be efficiently redistributed via weight pushing in the $⟨{\mathbb{R}}_{+},+,\times ,0,1⟩$ and $⟨{\mathbb{R}}_{+},\max ,\times ,0,1⟩$ semirings.