Vector Fields Based Machine Learning

In many machine learning problems, one is often confronted with very high dimensional da-ta. There is a strong intuition that the data may have a lower dimensional intrinsic representation. Various researchers have considered the case when the data is sampled from a submanifold embed-ded in the ambient Euclidean space. Consequently, learning with the low dimensional manifold structure, or specifically the intrinsic topological and geometrical properties of the data manifold, becomes a crucial problem. Many of the existing work use the graph Laplacian to ensure the smoothness of the prediction function on the data manifold. However, beyond smoothness, we should ensure second order smoothness in semi-supervised learning and unsupervised learning. In this thesis, we show that the second order smoothness measures the linearity of the function, and the gradient field of a linear function has to be a parallel vector field. To address these key issues, this thesis presents a systematic study on several important aspects of learning with vector fields, including theoretical analysis, discretization and optimization. In summary, the major novel contributions are as follows:1. To separate different connected components, this thesis proposes a linear manifold learning method. We provide theoretical analysis on both the objective functional and the constraint, which shows the affine hulls of the manifold and the connected components are essential to the linear manifold learning problem. In some sense, each connected component with the overlapping affine hull will be collapsed by the optimal projection. To faithfully recover the manifold structure, we propose a novel local isometry based dimensionality reduction method from the perspective of vector fields. We give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector fields and isometry. The problem of finding an isometry turns out to be equivalent to finding parallel vector fields on the data manifold. Theoretical results show that our method can precisely recover the manifold if it is isometric to a connected open subset of Euclidean space.2. To incorporate the manifold structure in semi-supervised learning, this thesis proposes vector fields regularization methods for semi-supervised regression and multi-task learning. In semi-supervised regression, it is suggested by recent theoretical work that we should ensure second order smoothness for achieving faster rates of convergence. To achieve this goal, we show that the second order smoothness measures the linearity of the function, and the gradient field of a linear function has to be a parallel vector field. Consequently, we propose to find a function which minimizes the empirical error, and simultaneously requires its gradient field to be as parallel as possible. We give a continuous objective function on the manifold and discuss how to discretize it by using random points. The discretized optimization problem turns out to be a sparse linear system which can be solved very efficiently. For multi-task learning, in this thesis, we develop multi-task vector field learning (MTVFL) which learns the predictor functions and the vector fields simultaneously. MTVFL has the following key properties:(1) The vector fields we learned are close to the gradient fields of the predictor functions.(2) Within each task, the vector field is required to be as parallel as possible, which is expected to span a low dimensional subspace.(3) The vector fields from all tasks share a low dimensional subspace. We formalize our idea in a regularization framework and also provide a convex relaxation method to solve the original non-convex problem.3. To learn the geodesic distance function on the manifold, this thesis proposes a novel method from the vector field perspective. The simplest way to compute the geodesic distance is to compute the shortest path distance between two points. However, it is well known that computing the pair-wise shortest path distance is time consuming and it cannot handle the case when the manifold is non-convex. In this thesis, we study the geodesic distance function d(p, x), by fixing one point p. As long as one can compute a distance function for a fixed point p, then one can obtain the distance function d(·,·)by varying p. We provide two theorems to exactly characterize the geodesic distance function. We show that if a function fp(x) is a Euclidean distance function around p in exponential coordinates and the gradient field of fp(x) has unit norm almost everywhere, then fp(x) must be the unique geodesic distance function d(p.x). Based on our theoretical analysis, a novel approach from the vector field perspective is proposed to learn the geodesic distance function. Specifically, we propose to find a function which is a Euclidean distance function in the neighborhood of the fixed point, and simultaneously require its gradient field to have unit norm everywhere.