Incremental partition recombination for efficient tracking of multiple dialog states

For spoken dialog systems, tracking a distribution over multiple dialog states has been shown to add robustness to speech recognition errors. To retain tractability, past work has suggested tracking dialog states in groups called partitions. While promising, current techniques are limited to incorporating a small number of ASR N-Best hypotheses. This paper overcomes this limitation by incrementally recombining partitions during the update. Experiments with a database of 300,000 AT&T staff show better whole-dialog accuracy than existing approaches. In addition, our implementation, which is available to the research community, views partitions as programmatic objects - an accessible formulation for commercial application developers.