8.2.3
Highest Confidence First (HCF) [Chou and Brown 1990,Chou et al. 1993] is a serial,
deterministic algorithm for combinatorial minimization in which the
label set is discrete, 
. Its feature is the
introduction of a special uncommitted label and the strategy for
``committing'' a site.
Denote the uncommitted label by 0. The original label set is
augmented by this label into 
. A label 
is
said to be uncommitted if 
or committed if 
.
Initially, all label are set uncommitted, 
. A rule is
that once a site is committed, its label cannot go back to 0 but can
change to another value in 
.
The commitment and label changes are based on a stability measure defined in the following. The two assumptions made in ICM are also made in HCF. Therefore we have the conditional posterior potential
where 
means any clique c containing site i. After
augmenting the label set, we define the conditional potential for a
committed label 
as
where
Therefore, a site has no effect on its neighbors unless it has committed. When no neighbor is active, the local energy measure reduces to the likelihood of the label. A remark is that the uncommitted label is different from the NULL label described in Chapter 5 for object recognition because any clique involving a site labeled NULL incurs a non-zero penalty.
The stability of i with respect to f is defined as
where 
. The stability S of an
uncommitted site is the negative difference between the lowest and the
second lowest local energies (conditional potentials). The stability S
of a committed site is the difference between the current local energy
and the lowest possible energy due to any other label. Note
the range of a stability is 
. A negative stability
means there is room to improve. All uncommitted sites have non-positive
. The magnitude of 
is equal to the change in energy due to
the change in the label 
. A lower value of 
indicates a
more stable configuration and a negative value with larger magnitude
gives us more confidence to change f to a new configuration.
Figure 8.4: The highest confidence first algorithm.
The following rule is imposed for deciding the order of update: At each
step, only the least stable site is allowed to change its label or to
make its commitment. Suppose that 
is the least
stable site. Then if 
, change 
to
otherwise, change 
to
Therefore, the first committed label 
is that yields the maximum
local likelihood 
. The HCF algorithm is described in
Fig.8.4. Create_Heap creates a heap in which the S-values
are sorted, the least stable site is placed at the top.
Change_State(k) changes 
to 
according to the rule
described earlier. Update_S(k) updates the stability value of k
using the current f. Adjust_Heap(k) adjusts the heap according to
the current S-values.
A parallel version of HCF, called ``local HCF'', is described in [Chou et al. 1993]. In local HCF, the updating on each iteration is performed according to the following rule: For each site in parallel, change the state of the site if its stability is negative and lower than the stabilities of its neighbors.
Some results are given in Chou et al.
's paper in which HCF is compared
with other algorithms including simulated annealing and ICM. The results
show that HCF is, on the whole, better in terms of the remaining energy
. The initialization is not a problem for HCF because it is
always set to 0's.
