2012/10/16 by Saeed Amizadeh, Amizadeh, Saeed, Bo Thiesson +3 · 1 citation
Physics and Astronomy · Computer Science · #Electromagnetic Scattering and Analysis #Matrix Theory and Algorithms #Model Reduction and Neural Networks
paper · pdf · doi:10.48550/arxiv.1210.4846
In recent years, non-parametric methods utilizing random walks on graphs have\nbeen used to solve a wide range of machine learning problems, but in their\nsimplest form they do not scale well due to the quadratic complexity. In this\npaper, a new dual-tree based variational approach for approximating the\ntransition matrix and efficiently performing the random walk is proposed. The\napproach exploits a connection between kernel density estimation, mixture\nmodeling, and random walk on graphs in an optimization of the transition matrix\nfor the data graph that ties together edge transitions probabilities that are\nsimilar. Compared to the de facto standard approximation method based on\nk-nearestneighbors, we demonstrate order of magnitudes speedup without\nsacrificing accuracy for Label Propagation tasks on benchmark data sets in\nsemi-supervised learning.\n