×

Ricci flow embedding for rectifying non-Euclidean dissimilarity data. (English) Zbl 1373.68359

Summary: Pairwise dissimilarity representations are frequently used as an alternative to feature vectors in pattern recognition. One of the problems encountered in the analysis of such data is that the dissimilarities are rarely Euclidean, while statistical learning algorithms often rely on Euclidean dissimilarities. Such non-Euclidean dissimilarities are often corrected or a consistent Euclidean geometry is imposed on them via embedding. This paper commences by reviewing the available algorithms for analysing non-Euclidean dissimilarity data. The novel contribution is to show how the Ricci flow can be used to embed and rectify non-Euclidean dissimilarity data. According to our representation, the data is distributed over a manifold consisting of patches. Each patch has a locally uniform curvature, and this curvature is iteratively modified by the Ricci flow. The raw dissimilarities are the geodesic distances on the manifold. Rectified Euclidean dissimilarities are obtained using the Ricci flow to flatten the curved manifold by modifying the individual patch curvatures. We use two algorithmic components to implement this idea. Firstly, we apply the Ricci flow independently to a set of surface patches that cover the manifold. Second, we use curvature regularisation to impose consistency on the curvatures of the arrangement of different surface patches. We perform experiments on three real world datasets, and use these to determine the importance of the different algorithmic components, i.e. Ricci flow and curvature regularisation. We conclude that curvature regularisation is an essential step needed to control the stability of the piecewise arrangement of patches under the Ricci flow.

MSC:

68T10 Pattern recognition, speech recognition
53C44 Geometric evolution equations (mean curvature flow, Ricci flow, etc.) (MSC2010)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

Python; Scikit
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Biederman, I., Recognition-by-componentsa theory of human image understanding, Psychol. Rev., 94, 2, 115-147 (1987)
[2] Bishop, C. M., Neural Networks for Pattern Recognition (1995), Oxford University Press: Oxford University Press USA
[3] Bunke, H.; Sanfeliu, A., Syntactic and Structural Pattern Recognition: Theory and Applications (1990), World Scientific · Zbl 0744.68017
[4] Chow, B.; Luo, F., Combinatorial Ricci flows on surfaces, J. Differential Geom., 63, 1, 97-129 (2003) · Zbl 1070.53040
[5] Chung, F. R.K., Spectral Graph Theory (1996), American Mathematical Society
[7] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification (2001), Wiley: Wiley New York · Zbl 0968.68140
[10] Filippone, Maurizio, Dealing with non-metric dissimilarities in fuzzy central clustering algorithms, Int. J. Approx. Reason., 50, 2, 363-384 (2009) · Zbl 1191.68570
[11] Gold, S.; Rangarajan, A., A graduated assignment algorithm for graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 18, 377-388 (1996)
[12] Gower, J. C., Properties of Euclidean and non-Euclidean distance matrices, Linear Algebra Appl., 67, 81-97 (1985) · Zbl 0569.15016
[13] Gower, J. C.; Legendre, P., Metric and Euclidean properties of dissimilarity coefficients, J. Classif., 3, 1, 5-48 (1986) · Zbl 0592.62048
[14] Gu, X.; He, Y.; Jin, M.; Luo, F.; Qin, H.; Yau, S. T., Manifold splines with a single extraordinary point, Comput.-Aided Des., 40, 6, 676-690 (2008) · Zbl 1206.65031
[16] Hamilton, R. S., Three-manifolds with positive Ricci curvature, J. Differ. Geom., 17, 2, 255-306 (1982) · Zbl 0504.53034
[17] Hamilton, R. S., The Ricci flow on surfaces, Contemp. Math., 71, 237-262 (1988)
[19] Jin, M.; Kim, J.; Gu, X., Discrete surface Ricci flowtheory and applications, Math. Surf., XII, 209-232 (2007) · Zbl 1163.68351
[24] Laub, J.; Roth, V.; Buhmann, J. M.; Müller, K. R., On the information and representation of Non-Euclidean pairwise data, Pattern Recognit., 39, 10, 1815-1826 (2006) · Zbl 1096.68721
[25] Lindman, Harold; Caelli, Terry, Constant curvature Riemannian scaling, J. Math. Psychol., 17, 89-109 (1978) · Zbl 0391.92020
[26] Mitchell, T., Machine Learning (1997), McGraw-Hill · Zbl 0913.68167
[27] Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learnmachine learning in Python, J. Mach. Learn. Res., 12, 2825-2830 (2011) · Zbl 1280.68189
[28] Pekalska, E.; Duin, R. P.W., The Dissimilarity Representation for Pattern RecognitionFoundations and Applications (2005), World Scientific Publishing Co Pte Ltd · Zbl 1095.68105
[29] Pekalska, E.; Duin, R. P.W., Beyond traditional kernelsclassification in two dissimilarity-based representation spaces, IEEE Trans. Syst. Man Cybern.—Part C, 38, November (6), 23 (2008)
[31] Pekalska, E.; Harol, A.; Duin, R.; Spillmann, B.; Bunke, H., Non-Euclidean or non-metric measures can be informative, Struct. Syntact. Stat. Pattern Recognit., 871-880 (2006)
[32] Pekalska, E.; Paclik, P.; Duin, R. P.W., A generalized kernel approach to dissimilarity-based classification, J. Mach. Learn. Res., 2, 175-211 (2001) · Zbl 1037.68127
[33] Perelman, G.; Perelman, G.; Perelman, G., Finite extinction time for the solutions to the Ricci flow on certain three-manifolds, PLoS Biol., 4, 5, e8 (2006)
[34] Poole, D., Linear AlgebraA Modern Introduction (2005), Cengage Learning
[35] Robles-Kelly, A.; Hancock, E. R., A Riemannian approach to graph embedding, Pattern Recognit., 40, 3, 1042-1056 (2007) · Zbl 1119.68210
[36] Roth, V.; Laub, J.; Buhmann, J. M.; Müller, K. R., Going metricdenoising pairwise data, Adv. Neural Inf. Process. Syst., 15, 817-824 (2002)
[37] Sanfeliu, A.; Fu, K. S., A distance measure between attributed relational graphs for pattern recognition, IEEE Trans. Syst. Man Cybern., 13, 3, 353-362 (1983) · Zbl 0511.68060
[39] Saucan, E.; Appleboim, E.; Wolansky, E. G.; Zeevi, Y. Y., Combinatorial Ricci curvature and Laplacians for image processing (2009), CISR
[40] Shapiro, L. G.; Haralick, R. M., A metric for comparing relational descriptions, IEEE Trans. Pattern Anal. Mach. Intell., 7, 1, 90-94 (1985)
[42] Tenenbaum, J. B.; Silva, V.; Langford, J. C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319-2323 (2000)
[45] Xiao, B.; Hancock, E. R.; Wilson, R. C., Geometric characterization and clustering of graphs using heat kernel embeddings, Image Vis. Comput., 28, 6, 1003-1021 (2010)
[49] Zeng, W.; Samaras, D.; Gu, D., Ricci flow for 3d shape analysis, IEEE Trans. Pattern Anal. Mach. Intell., 32, 4, 662-677 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.