Geoscience Reference
In-Depth Information
x1
x3
x2
Figure 5.1: A graph constructed from labeled instances x 1 , x 2 and unlabeled instances. The label of
unlabeled instance x 3 will be affected more by the label of x 1 , which is closer in the graph, than by the
label of x 2 , which is farther in the graph, even though x 2 is closer in Euclidean distance.
regularization. In the following sections, we introduce several different graph-based semi-supervised
learning algorithms. They differ in the choice of the loss function and the regularizer. For simplicity,
we will assume binary labels y
∈{−
1 , 1
}
.
5.3 MINCUT
The first graph-based semi-supervised learning algorithm we introduce is formulated as a graph cut
problem. We treat the positive labeled instances as “source” vertices, as if some fluid is flowing out
of them and through the edges. Similarly, the negative labeled instances are “sink” vertices, where
the fluid would disappear. The objective is to find a minimum set of edges whose removal blocks all
flow from the sources to the sinks. This defines a “cut,” or a partition of the graph into two sets of
vertices. The “cut size” is measured by the sum of the weights on the edges defining the cut. Once
the graph is split, the vertices connecting to the sources are labeled positive, and those to the sinks
are labeled negative.
Mathematically, we want to find a function f( x )
∈{−
1 , 1
}
on the vertices, such that f( x i )
=
y i
for labeled instances, and the cut size is minimized:
w ij .
(5.2)
i,j : f( x i ) = f( x j )
is removed, it must be true that f( x i ) =
The above quantity is the cut size because if an edge w ij
f( x j ) .
We will now cast Mincut as a regularized risk minimization problem, with an appropriate loss
function and regularizer. On any labeled vertex x i , f( x i ) is clamped at the given label: f( x i ) = y i .
This can be enforced by a loss function of the form
c( x ,y,f( x )) =∞· (y f( x )) 2 ,
(5.3)
 
Search WWH ::




Custom Search