## Joint Harmonic Functions and Their Supervised Connections

*Mark Vere Culp, Kenneth Joseph Ryan*; 14(Dec):3721−3752, 2013.

### Abstract

The cluster assumption had a significant impact on the reasoning
behind semi-supervised classification methods in graph-based
learning. The literature includes numerous applications where
harmonic functions provided estimates that conformed to data
satisfying this well-known assumption, but the relationship
between this assumption and harmonic functions is not as well-
understood theoretically. We investigate these matters from the
perspective of supervised kernel classification and provide
concrete answers to two fundamental questions. (i) Under what
conditions do semi-supervised harmonic approaches satisfy this
assumption? (ii) If such an assumption is satisfied then why
precisely would an observation sacrifice its own supervised
estimate in favor of the cluster? First, a harmonic function is
guaranteed to assign labels to data in harmony with the cluster
assumption if a specific condition on the boundary of the
harmonic function is satisfied. Second, it is shown that any
harmonic function estimate within the interior is a probability
weighted average of supervised estimates, where the weight is
focused on supervised kernel estimates near labeled cases. We
demonstrate that the uniqueness criterion for harmonic
estimators is sensitive when the graph is sparse or the size of
the boundary is relatively small. This sets the stage for a
third contribution, a new regularized joint harmonic function
for semi-supervised learning based on a joint optimization
criterion. Mathematical properties of this estimator, such as
its uniqueness even when the graph is sparse or the size of the
boundary is relatively small, are proven. A main selling point
is its ability to operate in circumstances where the cluster
assumption may not be fully satisfied on real data by
compromising between the purely harmonic and purely supervised
estimators. The competitive stature of the new regularized joint
harmonic approach is established.

[abs][pdf][bib]