Abstract
Manifold learning plays a central role in many Machine Learning (ML) methods where it assumes information lies on a low-dimensional manifold, but the presence of high dimensional noise may defect their performance. In this contribution, we propose a novel (swarm) algorithm to suppress the noise of manifolds of potentially varying dimensionalities. Inspired by colonial insects this method employs multiple agents with different strategies moving through the data space in parallel. During this process, they use local information to reconstruct the manifolds and then move data objects close to them. Moreover, principles of evolutionary game theory are used to encourage agents to select better strategies and hence optimize the hyper-parameters automatically. While other denoising techniques can be seen as single-agent approaches, the new algorithm is a multi-agent approach which makes it more flexible and suitable for scenarios including multiple manifolds. In the experiments, we simulate several situations from a simple manifold with a specific noise level, to more complex manifolds where there are variations on the density, noise level or dimensionalities. Furthermore, we demonstrate the improvement of the proposed algorithm for the performance of the Parzen Window (PW) density estimator.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Code and supplementary material: https://git.lwp.rug.nl/m.mohammadi/em3a.
References
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
Blum, C., Roli, A., Dorigo, M.: Hc-aco: The hyper-cube framework for ant colony optimization. Proceedings of MIC, vol. 2, pp. 399–403 (2001)
Chu, Shu-Chuan., Roddick, John F., Su, Che-Jen, Pan, Jeng-Shyang: Constrained ant colony optimization for data clustering. In: Zhang, Chengqi, W. Guesgen, Hans, Yeap, Wai-Kiang (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 534–543. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28633-2_57
Deneubourg, J.L., Goss, S., Franks, N., Sendova-Franks, A., Detrain, C., Chrétien, L.: The dynamics of collective sorting robot-like ants and ant-like robots. In: Proceedings of the First International Conference on Simulation of Adaptive Behavior on from Animals to Animats, pp. 356–363 (1991)
Dorigo, M., Maniezzo, V., Colorni, A.: Positive feedback as a search strategy. Technical Report. 91–016, Politecnico di Milano, Italy (1991)
Dorigo, M., Maniezzo, V., Colorni, A., et al.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B: Cybern 26(1), 29–41 (1996)
Golub, G.H., Van Loan, C.F.: Matrix computations, vol. 3. JHU press (2012)
Gong, D., Sha, F., Medioni, G.: Locally linear denoising on image manifolds. In: Proceedings of the 13th International Conference on AI and Stats, pp. 265–272 (2010)
Hein, M., Maier, M.: Manifold denoising. In: Advances in Neural Information Processing Systems, pp. 561–568 (2007)
Hofbauer, J., Sigmund, K., et al.: Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge (1998)
Kaslovsky, D.N., Meyer, F.G.: Non-asymptotic analysis of tangent space perturbation. Inf. Infer. J. IMA 3(2), 134–187 (2014)
Little, A.V., Maggioni, M., Rosasco, L.: Multiscale geometric methods for estimating intrinsic dimension. Proc. SampTA, 4(2) (2011)
Lumer, E.D., Faieta, B.: Diversity and adaptation in populations of clustering ants. In: Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior: from Animals to Animats 3, pp. 501–508. MIT Press (1994)
Mordohai, P., Medioni, G.G.: Unsupervised dimensionality estimation and manifold learning in high-dimensional spaces by tensor voting. In: IJCAI, pp. 798–803 (2005)
Runkler, T.A.: Ant colony optimization of clustering models. Int. J. Intell. Syst. 20(12), 1233–1251 (2005)
Shelokar, P., Jayaraman, V.K., Kulkarni, B.D.: An ant colony approach for clustering. Anal. Chim. Acta 509(2), 187–195 (2004)
Stützle, T., Hoos, H.H.: Max-min ant system. Future Gen. Comput. Syst. 16(8), 889–914 (2000)
Taubin, G.: A signal processing approach to fair surface design. In: Proceedings of the 22nd Conference on Computer graphics and interactive techniques, pp. 351–358 (1995)
Tsai, C.F., Tsai, C.W., Wu, H.C., Yang, T.: ACODF: a novel data clustering approach for data mining in large databases. J. SS 73(1), 133–145 (2004)
Wang, W., Carreira-Perpinán, M.A.: Manifold blurring mean shift algorithms for manifold denoising. In: 2010 IEEE CVPR, pp. 1759–1766. IEEE (2010)
Wang, X., Tiňo, P., Fardal, M.A.: Multiple manifolds learning framework based on hierarchical mixture density model. In: ECML PKDD, pp. 566–581 (2008)
Wang, X., Tino, P., Fardal, M.A., Raychaudhury, S., Babul, A.: Fast parzen window density estimator. In: 2009 IJCNN, pp. 3267–3274. IEEE (2009)
Xiang, Y., Chen, Y.C.: Statistical inference using mean shift denoising (2016). arXiv preprint arXiv:1610.03927
Acknowledgments
This project has received financial support from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No. 721463 to the SUNDIAL network.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Mohammadi, M., Bunte, K. (2020). Multi-agent Based Manifold Denoising. In: Analide, C., Novais, P., Camacho, D., Yin, H. (eds) Intelligent Data Engineering and Automated Learning – IDEAL 2020. IDEAL 2020. Lecture Notes in Computer Science(), vol 12490. Springer, Cham. https://doi.org/10.1007/978-3-030-62365-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-62365-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62364-7
Online ISBN: 978-3-030-62365-4
eBook Packages: Computer ScienceComputer Science (R0)