Tree matching for evaluation of speech interpretation systems

Common data-driven evaluation metrics for speech understanding systems are based on automatically comparing sequences of slot-value pairs by dynamic programming (DP) matching. However, for complex hierarchical language models, sequence matching based metrics do not seem appropriate as they cannot fully capture structural similarities. For this task, we propose a novel evaluation metric, the tree node accuracy. Our approach is founded on a DP-style algorithm that computes the minimum edit distance between pairs of ordered labeled trees and includes the sequence matching problem as a special case. We also extended the basic scheme for our task to support trees consisting of different categories of tree nodes. Experiments carried out on several semantic models confirm that the tree matching based approach displays greater flexibility than conventional sequence matching based metrics; and is especially suited for complex hierarchical models.