Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation

  • Saeed Amizadeh | University of Pittsburgh

In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this work, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearest-neighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning

Speaker Details

Saeed Amizadeh is a PhD student advised by Milos Hauskrecht in Intelligent Systems Program at University of Pittsburgh. He has completed his second master’s in Intelligent Systems at University of Pittsburgh. His first master’s and bachelor’s degrees are in Artificial Intelligence and Computer Science both from University of Tehran, Iran. Saeed’s areas of research mainly involve Machine Learning and Data Mining for large-scale problems. In particular, he works on approximate graph-based methods for unsupervised and semi-supervised learning in large-scale datasets. Saeed is also a former intern in Machine Learning and Applied Statistics (MLAS) group at Microsoft Research. His mentor at MSR was Bo Thiesson

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks