Geoscience Reference
In-Depth Information
5.4 HARMONIC FUNCTION
The second graph-based semi-supervised learning algorithm we introduce is the harmonic function.
In our context, a harmonic function is a function that has the same values as given labels on the
labeled data, and satisfies the weighted average property on the unlabeled data:
f(
x
i
)
=
y
i
,i
=
1
...l
l
+
u
k
1
w
jk
f(
x
k
)
l
+
u
k
=
1
w
jk
=
f(
x
j
)
=
,j
=
l
+
1
...l
+
u.
(5.6)
In other words, the value assigned to each unlabeled vertex is the weighted average of its neighbors'
values. The harmonic function is the solution to the same problem in (5.5), except that we relax
f
to produce real values:
l
l
+
u
(y
i
−
f(
x
i
))
2
w
ij
(f (
x
i
)
−
f(
x
j
))
2
.
f
:
f(
x
)
∈
R
∞
min
+
(5.7)
i
=
1
i,j
=
1
This is equivalent to the more natural problem
l
+
u
f(
x
j
))
2
min
f
:
f(
x
)
∈
R
w
ij
(f (
x
i
)
−
i,j
=
1
subject to
f(
x
i
)
=
y
i
for
i
=
1
...l
.
(5.8)
The relaxation has a profound effect. Now there is a closed-form solution for
f
. The solution is
unique (under mild conditions) and globally optimal. The drawback of the relaxation is that in the
solution,
f(
x
)
is now a real value in
that does not directly correspond to a label. This can
however be addressed by thresholding
f(
x
)
at zero to produce discrete label predictions (i.e., if
f(
x
)>
=
0, predict
y
=
1, and if
f(
x
)<
0, predict
y
=−
1).
The harmonic function
f
has many interesting interpretations. For example, one can view the
graph as an electric network. Each edge is a resistor with resistance 1
/w
ij
, or equivalently conductance
w
ij
. The labeled vertices are connected to a 1-volt battery, so that the positive vertices connect to
the positive side, and the negative vertices connect to the ground. Then the voltage established at
each node is the harmonic function,
1
see Figure 5.3(a).
The harmonic function
f
can also be interpreted by a random walk on the graph. Imagine a
particle at vertex
i
. In the next time step, the particle will randomly move to another vertex
j
with
probability proportional to
w
ij
:
[−
1
,
1
]
w
ij
k
w
ik
.
P(j
|
i)
=
(5.9)
The random walk continues in this fashion until the particle reaches one of the labeled vertices. This
is known as an absorbing random walk, where the labeled vertices are absorbing states. Then the
1
This, and the random walk interpretation below, is true when the labels
y
∈{
0
,
1
}
. When the labels
y
∈{−
1
,
1
}
, the voltages
correspond to a shifted and scaled harmonic function.
