Dimensionality Reduction for Non-vectorial Data

Abstract

Dimensionality Reduction (DR) is an important step in many advanced applications such as exploratory data analysis and manifold learning. Its main goal is to discover the mappings of the input data in a much lower dimensional space or the so-called latent space without incurring unnecessary information loss. In most existing DR algorithms, the main objective is to preserve relational structure among objects of the input space in the latent space by minimizing the inconsistency between two similarity/dissimilarity measures, one for the input data and the other for the embedded data, via a separate matching objective function. Based on this observation, a new dimensionality reduction method called Twin Kernel Embedding (TKE) is proposed. TKE addresses the problem of embedding non-vectorial data that is difficult for conventional methods in practice due to the lack of efficient vectorial representation. TKE solves this problem by minimizing the inconsistency between the similarity measures captured respectively by their kernel Gram matrices in the two spaces. This algorithm is proven to be effective on some real world data sets and has been successfully applied to protein visualization, kernel learning, fingerprint classification etc. TKE is further extended to novel samples by introducing the backward mapping which is incorporated into the objective function as either substitution of all embeddings or regularization terms which generate BCTKE and RCTKE algorithms respectively. Intuitively, the mapping function can be integrated into any other host DR algorithms as a solution to the so-called out-of-sample problem. This thesis starts with the analysis of the existing DR methods. Based on the understanding of their common features, we will show the development of the TKE algorithms and the details on their behaviors at length. We present not only a series of new algorithms, but also the aspects of the design including the origin of the ideas, observations and implementation. This research provides a stepping stone for new algorithmic design in Dimensionality Reduction.