A graph optimization method for dimensionality reduction with pairwise constraints
- PDF / 320,014 Bytes
- 7 Pages / 595.276 x 790.866 pts Page_size
- 46 Downloads / 228 Views
ORIGINAL ARTICLE
A graph optimization method for dimensionality reduction with pairwise constraints Limei Zhang • Lishan Qiao
Received: 5 December 2013 / Accepted: 9 December 2014 Ó Springer-Verlag Berlin Heidelberg 2015
Abstract Graph is at the heart of many dimensionality reduction (DR) methods. Despite its importance, how to establish a high-quality graph is currently a pursued problem. Recently, a new DR algorithm called graphoptimized locality preserving projections (GoLPP) was proposed to perform graph construction with DR simultaneously in a unified objective function, resulting in an automatically optimized graph rather than pre-specified one as involved in typical LPP. However, GoLPP is unsupervised and can not naturally incorporate supervised information due to a strong sum-to-one constraint of weights of graph in its model. To address this problem, in this paper we give an improved GoLPP model by relaxing the constraint, and then develop a semi-supervised GoLPP (S-GoLPP) algorithm by incorporating pairwise constraint information into its modeling. Interestingly, we obtain a semi-supervised closed-form graph-updating formulation with natural possibility explanation. The feasibility and effectiveness of the proposed method is verified on several publicly available UCI and face data sets. Keywords Dimensionality reduction Semi-supervised learning Graph construction Pairwise constraints Locality preserving projections
1 Introduction In the recent years, graph-based methods have become more and more popular, and involved in many machine L. Zhang L. Qiao (&) Department of Mathematics Science, Liaocheng University, Liaocheng 252000, People’s Republic of China e-mail: [email protected]
learning problems including dimensionality reduction (DR) [1–8], clustering [9, 10] and semi-supervised learning [11], etc. Despite its importance, how to establish a high-quality graph is still an actively-pursued problem [12]. Many existing graph-based methods [1, 2, 4, 9, 11, 13] mainly rely on an artificially predefined neighborhood graph, which inevitably incurs the difficulty of parameter selection. Although several adaptive graph construction methods were presented recently [14–16], their common property is that the building graph process is independent of the subsequent learning tasks such as DR, clustering and (semi-supervised) classification. Different from such constructions, Zhang et al. [17] recently proposed a DR algorithm called graph-optimized locality preserving projections (GoLPP) based on a task-dependent or task-oriented strategy, which performs graph construction/ optimization together with the projection learning simultaneously in one single objective function, thus resulting in an automatically optimized graph (see Sect. 2 for more details). Despite demonstrated superior performance to original LPP [17] on some data sets, GoLPP only works under completely unsupervised case, and can not naturally incorporate supervised information like LPP and other DR methods with predefined graphs, which
Data Loading...
