8.3.3
The graded Hopfield neural network (HNN) [Hopfield 1984] provides another way of applying penalty functions. Let us use the constrained minimization in RL as an example to illustrate this point. There, the feasibility (8.19) must be satisfied by the labeling assignment at any time and the unambiguity (8.22) should be satisfied by the final labeling assignment. The unambiguity constraint can be imposed by the following term
where 
is the inverse of a function 
to be
illustrated below. A local state 
is related to an
internal variable 
by
where 
is usually a sigmoid function
controlled by the parameter T. In very high gain when 
,
is forced to be 0 or 1 depending on whether 
is
positive or negative [Hopfield 1984]. The term 
reaches the
minimum of zero only when all 
's are either 0 or 1. This means
that minimizing this term with 
in effect leads to
unambiguous labeling.
On the other hand, The feasibility can be imposed by
This term has its minimum value of zero when the feasibility is satisfied. Now the constrained optimization minimizes the following functional
where a and b are weights. A minimal solution which is feasible and unambiguous is given by
To derive a dynamic system for the minimization, introduce a time
variable into f such that 
. The energy change due to state
change 
is
where
is a gradient component. The following dynamics minimizes the three
term energy 
:
where capacitance C>0 controls the convergence of the system. With the above dynamics, the energy change
is non-positive since 
is a monotonically increasing
function and C is positive. This updating rule will lead to a minimal
solution which is both feasible and unambiguous when 
,
and 
.
To solve combinatorial optimization, Wacholder et al. (1989) develop an algorithm which combines the HNN of [Hopfield 1984] and the Lagrange multiplier dynamics of [Platt and Barr 1988]. Good convergence to feasible solutions is reported. In Section 8.3.4, we will describe a method which combines the HNN and the augmented Lagrangian function to perform relaxation labeling.
The HNN approach has been used to convert binary-valued line process variables to real ones for low level process [Koch et al. 1986,Yuille 1987] ( cf. Section sec:DA.LP). It has also been used as an alternative to relaxation labeling for matching; this is seen as symbolic image labeling [Jamison and Schalkoff 1988], subgraph isomorphism for object recognition [Nasrabadi et al. 1990 ], and matching to multiple view models [Lin et al, 1991].
Comparing RL and HNN for combinatorial minimization like object matching, our experience is that the former performs better. Due to the influence of the extra penalty function added in the HNN approach, the modified energy may no longer solve the original matching problem [Horn 1988]. Moreover, it easily leads to unfavorable local solutions. The RL algorithm is much more careful in this regard. It uses gradient projection to choose the best direction and magnitude for the state to evolve. In other words, the problem of local optima is more significant in the HNN approach. Computationally, the RL needs a smaller number of iterations before convergence.