Maximum Variance Correction with Application to A* Search
Wenlin Chen, Kilian Q. Weinberger, Yixin Chen · 2013
In this paper we introduce Maximum Vari-ance Correction (MVC), which finds large-scale feasible solutions to Maximum Variance Unfolding (MVU) by post-processing embed-dings from any manifold learning algorithm. It increases the scale of MVU embeddings by several orders of magnitude and is nat-urally parallel. This unprecedented scala-bility opens up new avenues of applications for manifold learning, in particular the use of MVU embeddings as effective heuristics to speed-up A ∗ search. We demonstrate un-matched reductions in search time across sev-eral non-trivial A ∗ benchmark search prob-lems and bridge the gap between the man-ifold learning literature and one of its most promising high impact applications. 1.