Two dimensional embedding of handwritten digits by Laplacian Eigenmap, LPP, and PCA
In many information processing tasks, one is confronted with high-dimensional data. However, the data points are probably sampled from a low-dimensional sub-manifold embedded in the ambient space. I am interested in the general problem: How to learn such a data manifold? Especially, I am interested in the interaction between learning theory and differential geometry.
Working with Prof. Partha Niyogi, we have proposed a novel linear manifold learning algorithm, called Locality Preserving Projections (LPP). LPP is obtained by finding the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the manifold. LPP should be seen as an alternative to Principal Component Analysis (PCA) --- a classical linear technique that projects the data along the directions of maximal variance. When the high dimensional data lies on a low dimensional manifold embedded in the ambient space, the LPPs are obtained by finding the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the manifold. LPP may be conducted in the original space or in the reproducing kernel Hilbert space into which data points are mapped. This gives rise to kernel LPP.
The Eigenfaces (first row), Fisherfaces (second row) and Laplacianfaces (third row) calculated from the face images in the Yale database.
My main contribution to this subject is that I have proposed the Laplacianface approach to model the manifolds of face images. Different from Eigenface which is optimal for representation and Fisherface which is optimal for discrimination, Laplacianface respects both geometric and discriminative structure of the face manifolds. Our theoretical analysis shows that these three methods arise from the same principle applied to different choices of the graph structure. I am also interested in image segmentation which is intrinsically a graph partitioning problem.
The hypergraph model which captures the relationship among various types of multimedia objects.
I use information in the broad sense to include text, image, audio, and video. In particular, my research work in this direction contains two parts: social media recommendation and image retrieval. By using a mathematical model called hypergraph, we have developed a recommender system which can accurately capture the semantic relationships among various types of media objects. Comparing to traditional recommender systems based on collaborative filtering, our system can better satisfy the user's information need. For image retrieval, I consider two central questions: how to represent an image and how to judge similarity. I use techniques from statistics and differential geometry to solve these two problems.
|Design of our WWW image search system. [more]||The block-to-page link structure. The red arrows denote the links from image block to web pages.|
The central question that I ask in my research along this direction is: How to organize the world's information and make it universally accessible and useful? Specifically, I consider the question: how does a computer see the Internet and web pages?
The Internet can be naturally represented as a huge graph such that its nodes represent the web pages and its edges represent the hyperlinks. Based on this model, a lot of link analysis algorithms have been proposed to improve the performance of web search. One problem of this model is that the web pages are actually not the smallest information units. In fact, in most cases, a web page can contain various topics and hence the web page might not be considered as the atomic unit. Based on this observation, we have proposed a new link analysis algorithm, called Block Level Link Analysis. The new algorithm partitions the web pages into blocks. By extracting the page-to-block, block-to-page relationships from link structure and page layout analysis, we can construct a semantic graph over the WWW such that each node exactly represents a single semantic topic. We further developed two ranking algorithms, block level PageRank and block level HITS. You can find a lot of comments on this work on the web. Click here!