On stochastic tree distances and their training via Expectation-Maximisation

Abstract

Continuing a line of work initiated in (Boyer et al., 2007), a generalisation of stochastic string distance to a stochastic tree distance is considered. Hitheto overlooked modifications to the Zhang/Shasha tree-distance algorithm for all-paths and viterbi variants of this stochastic tree distance are described. A strategy towards an EM cost-adaptation algorithm for the all-paths distance which was suggested by (Boyer et al., 2007) is shown to overlook necessary ancestry preservation constraints, and an alternative EM cost-adaptation algorithm for the Viterbi variant is proposed. Experiments are reported on in which a distance-weighted kNN categorisation algorithm is applied to a corpus of categorised tree structures. We show that a 67.7% base-line using standard unit-costs can be improved to 72.5% by the EM cost adaptation algorithm.