Using symbol clustering to improve probabilistic automaton inference

In this paper we show that clustering alphabet symbols before PDFA inference is performed reduces perplexity on new data. This result is especially important in real tasks, such as spoken language interfaces, in which data sparseness is a s ignificant issue. We describe the application of the ALERGIA algorithm combined with an independent clustering technique to the Air Travel Information System (A TIS) task. A 25 % reduction in perplexity was obtained. This result outperforms a trigram model under the same simple smoothing scheme