Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition

Abstract

A model for channels in which an input sequence can produce output sequences of varying length is described. An efficient computational procedure for calculating Pr <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\{Y\mid X\}</tex> is devised, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X = x_1,x_2,\cdots,x_M</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Y = y_1,y_2,\cdots,y_N</tex> are the input and output of the channel. A stack decoding algorithm for decoding on such channels is presented. The appropriate likelihood function is derived. Channels with memory are considered. Some applications to speech and character recognition are discussed.