CVPR 2015
Semi-supervised Learning with Explicit Relationship Regularization

Kwang In Kim James Tompkin Hanspeter Pfister Christian Theobalt
Lancaster University MPI für Informatik Harvard University SEAS

If two data points x1 and x2 are close on the domain M of f, then conventional regularizers enforce that the corresponding function values f1 and f2 in co-domain N of f are similar (fif(xi)). We assume that relationships between pairs of function evaluations fi and fj are represented by smooth functions k(fi, fj), e.g., a similarity measure. Our regularizer explicitly enforces that k(f1, fj) and k(f2, fj) are similar for any j. For instance, if k(f1, f3) is large as f1 and f3 are similar, but k(f1, f4) is small as f1 and f4 are dissimilar (solid arrows), then our algorithm enforces that k(f2, f3) and k(f2, f4) are large and small, respectively (dotted arrows), as x1 and x2 are close in M. The same principle applies to high-order relationships: if k2(f1, f5, f6) represents a ternary relationship, e.g., a third-order correlation, the similarity of k2(f1, f5, f6) and k2(f2, f5, f6) is enforced.

In many learning tasks, the structure of the target space of a function holds rich information about the relationships between evaluations of functions on different data points. Existing approaches attempt to exploit this relationship information implicitly by enforcing smoothness on function evaluations only. However, what happens if we explicitly regularize the relationships between function evaluations? Inspired by homophily, we regularize based on a smooth relationship function, either defined from the data or with labels. In experiments, we demonstrate that this significantly improves the performance of state-of-the-art algorithms in semi-supervised classification and in spectral data embedding for constrained clustering and dimensionality reduction.

author = {Kwang In Kim and James Tompkin and Hanspeter Pfister and Christian Theobalt},
title = {Semi-supervised Learning with Explicit Relationship Regularization},
booktitle = {Proc. IEEE CVPR},
pages = {2188--2196},
year = {2015},
PDF (0.5 MB)

Kwang In Kim thanks EPSRC EP/M00533X/1 and EP/M006255/1, James Tompkin and Hanspeter Pfister thank NSF CGV-1110955, and James Tompkin and Christian Theobalt thank the Intel Visual Computing Institute.