Geoscience Reference
In-Depth Information
where we define
∞·
0
=
0. This loss function is zero if f( x i )
=
y i , and infinity otherwise. To
minimize the regularized risk, f( x i ) will then have to equal y i
on labeled vertices. The regularizer
corresponds to the cut size. Recall we require f( x )
∈{−
1 , 1
}
for all unlabeled vertices x . Therefore,
the cut size can be re-written as
l + u
w ij (f ( x i ) f( x j )) 2 / 4 ,
(f) =
(5.4)
i,j = 1
Note the sum is now over all pairs of vertices. If x i
0 by
definition; if the edge exists and is not cut, then f( x i ) f( x j ) = 0. Thus, the cut size is well-defined
even when we sum over all vertex pairs. In (5.4) we could have equivalently used
and x j
are not connected, then w ij
=
| f( x i ) f( x j ) | / 2,
but the squared term is consistent with other approaches discussed later in this chapter. The Mincut
regularized risk problem is then
l
l + u
(y i f( x i )) 2
w ij (f ( x i ) f( x j )) 2 ,
f : f( x ) ∈{− 1 , 1 }
min
+
(5.5)
i = 1
i,j = 1
where we scaled up both terms to remove the 1 / 4. This is an integer programming problem because
f is constrained to produce discrete values -1 or 1. However, efficient polynomial-time algorithms
exist to solve the Mincut problem. It is clear that Mincut is a transductive learning algorithm, because
the solution f is defined only on the vertices, not on the ambient feature space.
The formulation of Mincut has a curious “flaw” in that there could be multiple equally good
solutions. For example, Figure 5.2 shows a graph with the shape of a chain. There are two labeled
vertices: a positive vertex on one end, and a negative vertex on the other end. The edges have the
same weight. There are six Mincut solutions: removing any single edge separates the two labels,
and the cut size is minimized. What is wrong with six solutions? The label of the middle vertex
is positive in three of the solutions, and negative in the other three. This label variability exists for
other unlabeled vertices to a lesser extent. Intuitively, it seems to reflect the confidence of the labels.
As we will see next, there are better ways to compute such confidence.
+
Figure 5.2: On this unweighted chain graph with one labeled vertex on each end, any single-edge cut is
an equally good solution for Mincut.
 
Search WWH ::




Custom Search