Large-Scale Algorithms
Olivier Delalleau, Yoshua Bengio, Nicolas Le Roux · The MIT Press eBooks · 2006
In Chapter 11, it is shown how a number of graph-based semi-supervised learning algorithms can be seen as the minimization of a specific cost function, leading to a linear system with n equations and unknowns (with n the total number of labeled and unlabeled examples). Solving such a linear system will in general require on the order of O(kn2) time and O(kn) memory (for a sparse graph where each data point has k neighbors), which can be prohibitive on large datasets (especially if k = n, i.e. the graph is dense). We present in this chapter a subset selection method that can be used to reduce the original system to one of size m