Timezone: »

Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering
Lei Wu · Rong Jin · Steven Chu-Hong Hoi · Jianke Zhu · Nenghai Yu

Tue Dec 08 07:00 PM -- 11:59 PM (PST) @ None #None

Learning distance functions with side information plays a key role in many machine learning and data mining applications. Conventional approaches often assume a Mahalanobis distance function. These approaches are limited in two aspects: (i) they are computationally expensive (even infeasible) for high dimensional data because the size of the metric is in the square of dimensionality; (ii) they assume a fixed metric for the entire input space and therefore are unable to handle heterogeneous data. In this paper, we propose a novel scheme that learns nonlinear Bregman distance functions from side information using a non-parametric approach that is similar to support vector machines. The proposed scheme avoids the assumption of fixed metric because its local distance metric is implicitly derived from the Hessian matrix of a convex function that is used to generate the Bregman distance function. We present an efficient learning algorithm for the proposed scheme for distance function learning. The extensive experiments with semi-supervised clustering show the proposed technique (i) outperforms the state-of-the-art approaches for distance function learning, and (ii) is computationally efficient for high dimensional data.

Author Information

Lei Wu (GE Global Research)
Rong Jin (Michigan State University (MSU))
Steven Chu-Hong Hoi (Nanyang Technological University)
Jianke Zhu (ETH Zurich)
Nenghai Yu (University of Science and Technology of China)

More from the Same Authors