On stochastic tree distances and their training via Expectation-Maximisation
Citation:
Martin Emms, On stochastic tree distances and their training via Expectation-Maximisation, ICPRAM 2012 International Conference on Pattern Recognition Application and Methods, Portugal, 6-8th February, 2012, 144 - 153Download Item:
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.
Sponsor
Grant Number
Science Foundation Ireland (SFI)
07/CE/I1142
Author's Homepage:
http://people.tcd.ie/mtemmsDescription:
PUBLISHEDPortugal
Author: EMMS, MARTIN
Sponsor:
Science Foundation Ireland (SFI)Other Titles:
ICPRAM 2012 International Conference on Pattern Recognition Application and MethodsType of material:
Conference PaperCollections
Availability:
Full text availableKeywords:
Tree matching, Expectation MaximisationSubject (TCD):
Smart & Sustainable PlanetMetadata
Show full item recordLicences: