Aggregation of multiple metric descriptions from distances between unlabeled objects

A. I. Maysuradze   ; M. A. Suvorov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 2, pp. 350-361

Résumé

The situation when there are several different semimetrics on the set of objects in the recognition problem is considered. The problem of aggregating distances based on an unlabeled sample is stated and investigated. In other words, the problem of unsupervised reduction of the dimension of multiple metric descriptions is considered. This problem is reduced to the approximation of the original distances in the form of optimal matrix factorization subject to additional metric constraints. It is proposed to solve this problem exactly using the metric nonnegative matrix factorization. In terms of the problem statement and solution procedure, the metric data method is an analog of the principal component method for feature-oriented descriptions. It is proved that the addition of metric requirements does not decrease the quality of approximation. The operation of the method is demonstrated using toy and real-life examples.

Bibliographie

[1] Cover T. M., Hart P. E., “Nearest neighbor pattern classification”, IEEE Transactions on Information Theory, 13:1 (1967), 21–27 | DOI | MR | Zbl

[2] Parzen E., “On Estimation of a probability density function and mode”, The Annals of Math. Statistics, 33:3 (1962), 1065–1076 | DOI | MR | Zbl

[3] Aizerman M. A., Braverman E. M., Rozonoer L. I., “Teoreticheskie osnovy metoda potentsialnykh funktsii v zadache ob obuchenii avtomatov razdeleniyu vkhodnykh situatsii na klassy”, Avtomatika i telemekhan., 1964, no. 25, 917–936

[4] Zhuravlev Yu. I., “Korrektnye algebry nad mnozhestvami nekorrektnykh (evristicheskikh) algoritmov. Chast I”, Kibernetika, 1977, no. 4, 5–17

[5] Zhuravlev Yu. I., “Korrektnye algebry nad mnozhestvami nekorrektnykh (evristicheskikh) algoritmov. Chast II”, Kibernetika, 1977, no. 6, 21–27

[6] Zhuravlev Yu. I., “Korrektnye algebry nad mnozhestvami nekorrektnykh (evristicheskikh) algoritmov. Chast III”, Kibernetika, 1978, no. 2, 35–43

[7] Zhuravlev Yu. I., Rudakov K. V., “Ob algebraicheskoi korrektsii protsedur obrabotki (preobrazovaniya) informatsii”, Probl. prikl. matem. i informatiki, 1987, 187–198

[8] Zhang Y., Zhang H., Nasrabadi N. M., Huang T. S., “Multi-metric learning for multi-sensor fusion based classification”, Informat. Fusion, 14:4 (2013), 431–440 | DOI

[9] Al-Wassai F. A., Kalyankar N. V., “The classification accuracy of multiple-metric learning algorithm on multi-sensor fusion”, Internat. J. Soft Comput. Engng., 3:4 (2013), 124–131

[10] Jolliffe I. T., Principal component analysis, Springer series in statistics, 2nd ed., Springer, New York, 2002 | MR | Zbl

[11] Lee D. D., Seung H. S., “Learning the parts of objects by non-negative matrix factorization”, Nature, 401:6755 (1999), 788–791 | DOI

[12] Naidenov N. A., “Issledovaniya metricheskogo analoga metoda glavnykh komponent”, Sb. statei molodykh uchenykh fakulteta VMK MGU, 7, 2010, 60–69 | Zbl

[13] Maisuradze A. I., Suvorov M. A., “Obuchenie lineinoi kombinatsii metrik na konechnoi vyborke”, Problemy teoreticheskoi kibernetiki, 2014, no. 17, 186–189

[14] Goldberger J., Roweis S., Hinton G., Salakhutdinov R., “Neighbourhood component analysis”, Advances in Neural Informat. Proc. Systems, 17 (2005), 513–520

[15] Weinberger K. Q., Blitzer J., Saul L. K., “Distance metric learning for large margin nearest neighbor classification”, Advances in Neural Informat. Proc. Systems, 18 (2005), 1473–1480

[16] Zheng H., Wang M., Li Z., “Audio-visual speaker identification with multi-view distance metric learning”, Proc. IEEE 17th Internat. Conference on Image Proc., 2010, 4561–4564

[17] Wang B., Jiang J., Wang W. W., Zhou Z.-H., Tu Z., “Unsupervised metric fusion by cross diffusion”, IEEE Conference on Computer Vision and Pattern Recognit, 2012, 2997–3004 | Zbl

[18] Zhai D., Chang H., Shan S., Chen X., Gao W., “Multiview metric learning with global consistency and local smoothness”, ACM Trans. Intell. Syst. Technol., 3:3 (2012), 1–22 | DOI | Zbl

[19] Bai X., Wang B., Wang X., Liu W., Tu Z., “Co-transduction for shape retrieval”, Proc. 11th European conference on Computer vision, ECCV'10, v. III, 2010, 328–341 | MR

[20] Gönen M., Alpaydin E., “Multiple Kernel Learning Algorithms”, J. Machine Learning Research, 12 (2011), 2211–2268 | MR | Zbl

[21] Buhmann M. D., Radial basis functions: theory and implementations, Cambridge University Press, New York, 2003 | MR | Zbl

[22] Belanche L., Vazquez J. L., Vazquez M., “Distance-based kernels for real-valued data”, Data Analys. Machine Learning and Applicat., 2007, 3–10

[23] Bekka B., de la Harpe P., Valette A., Kazhdan's property (T), Cambridge University Press, New York, 2008 | MR

[24] Schoenberg I. J., “Metric spaces and positive definite functions”, Transactions of the American Math. Soc., 44:3 (1938), 522–536 | DOI | MR

[25] Maisuradze A. I., “Ob optimalnykh razlozheniyakh konechnykh metricheskikh konfiguratsii v zadachakh raspoznavaniya obrazov”, Zh. vychisl. matem. i matem. fiz., 44:9 (2004), 1697–1707 | Zbl

[26] Cichocki A., Zdunek R., Phan A. H., Amari S.-I., Nonnegative matrix and tensor factorizations, John Wiley Sons Inc, Chichester, 2009

[27] Maisuradze A. I., “Gomogennye i rangovye bazisy v prostranstvakh metricheskikh konfiguratsii”, Zh. vychisl. matem. i matem. fiz., 46:92 (2006), 344–360 | Zbl

[28] Meyer C., Matrix analysis and applied linear algebra, SIAM, Philadelphia, 2000 | MR | Zbl

[29] Mestetskiy L., “Shape comparison of flexible objects — similarity of palm silhouettes”, Proc. second internat. conference on computer vision theory and applicat., VISAPP 2007, 2007, 390–393

[30] Bakina I., Kurakin A., Mestetskiy L., “Hand geometry analysis by continuous skeletons”, Lecture Notes in Comp. Sci., 6753, 2011, 130–139 | MR