Abstract
This paper focuses on how to perform the unsupervised clustering of tree structures in an information theoretic setting. We pose the problem of clustering as that of locating a series of archetypes that can be used to represent the variations in tree structure present in the training sample. The archetypes are tree-unions that are formed by merging sets of sample trees, and are attributed with probabilities that measure the node frequency or weight in the training sample. The approach is designed to operate when the correspondences between nodes are unknown and must be inferred as part of the learning process. We show how the tree merging process can be posed as the minimisation of an information theoretic minimum descriptor length criterion. We illustrate the utility of the resulting algorithm on the problem of classifying 2D shapes using a shock graph representation.
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Cyr, C., Kimia, B.: 3D Object Recognition Using Shape Similarity-Based Aspect Graph. In: ICCV (2001)
Dickinson, S.J., Pentland, A.P., Rosenfeld, A.: 3-D shape recovery using distributed aspect matching. PAMI 14(2), 174–198 (1992)
Friedman, N., Koller, D.: Being Bayesian about Network Structure. Machine Learning (2002) (to appear)
Getoor, L., et al.: Learning Probabilistic models of relational structure. In: 8th Int. Conf. on Machine Learning (2001)
Heckerman, D., Geiger, D., Chickering, D.M.: Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning 20(3), 197–243 (1995)
Heap, T., Hogg, D.: Wormholes in shape space: tracking through discontinuous changes in shape. In: ICCV, pp. 344-349 (1998)
Hjaltason, G.R., Samet, H.: Properties of embedding methods for similarity searching in metric spaces. PAMI (25), 530–549 (2003)
Ioffe, S., Forsyth, D.A.: Human Tracking with Mixtures of Trees. In: ICCV, vol. I, pp. 690–695 (2001)
Keselman, Y., Shokoufandeh, A., Demirci, M.F., Dickinson, S.: Many-to-many graph matching via metric embedding. In: CVPR 2003, vol. I, pp. 850–857 (2003)
Kimia, B.B., Tannenbaum, A.R., Zucker, S.W.: Shapes, shocks, and deformations I. International Journal of Computer Vision 15, 189–224 (1995)
Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its applications. In: 35th Anual Symposium on Foundations of Computer Science, pp. 169–175 (1994)
Meilă, M.: Learning with Mixtures of Trees. PhD thesis, MIT (1999)
Rissanen, J.: Stochastic complexity and modeling. Annals of Statistics 14, 1080–1100 (1986)
Robles-Kelly, A., Hancock, E.R.: A maximum likelihood framework for iterative eigendecomposition. In: ICCV, vol. I, pp. 654–661 (2001)
Shokoufandeh, A., Dickinson, S.J., Siddiqi, K., Zucker, S.W.: Indexing using a spectral encoding of topological structure. In: CVPR (1999)
Sebastian, T., Klein, P., Kimia, B.: Recognition of shapes by editing shock graphs. In: ICCV, vol. I, pp. 755–762 (2001)
Torsello, A., Hancock, E.R.: Efficiently computing weighted tree edit distance using relaxation labeling. In: Figueiredo, M., Zerubia, J., Jain, A.K. (eds.) EMMCVPR 2001. LNCS, vol. 2134, pp. 438–453. Springer, Heidelberg (2001)
Torsello, A., Hancock, E.R.: Matching and embedding through edit-union of trees. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002. LNCS, vol. 2352, pp. 822–836. Springer, Heidelberg (2002)
Zhu, S.C., Yuille, A.L.: FORMS: A Flexible Object Recognition and Modelling System. IJCV 20(3), 187–212 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Torsello, A., Hancock, E.R. (2004). Learning Mixtures of Weighted Tree-Unions by Minimizing Description Length. In: Pajdla, T., Matas, J. (eds) Computer Vision - ECCV 2004. ECCV 2004. Lecture Notes in Computer Science, vol 3023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24672-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-24672-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21982-8
Online ISBN: 978-3-540-24672-5
eBook Packages: Springer Book Archive