Expectation Semirings: Flexible EM for Learning Finite-State Transducers
Jason M. Eisner · 2001
Most recent work on finite-state transducers (FSTs) falls into two camps according to how the transducers are constructed. The algebraic camp employs experts who write (possibly weighted) regular expressions by hand, using an ever-growing language of powerful algebraic operators. The statistical camp, which prefers to extract expertise automatically from data, builds transducers with much simpler toopology so that their arc probabilities can be easily trained. This paper offers a clean way to combine the two traditions: an Expectation-Maximation (EM) algorithm for training arbitrary FSTs. First human experts use domain knowledge to specify the topology and parameterization of the transducer in any convenient way. Then the EM algorithm automatically chooses parameter values that (locally) maximize the joint likelihood of fully or partly observed data.