\documentstyle[jair,11pt,theapa]{article}

\jairheading{3}{1995}{223-248}{6/94}{10/95}
\ShortHeadings{Improving Connectionist Energy Minimization} 
{Pinkas and Dechter}
\firstpageno{223}

\newcommand{\shrink}[1]{}
\newtheorem{theo}{{\sc Theorem}}[section]

\begin{document}

\title{ 
Improving Connectionist Energy Minimization}
\author{\name Gadi Pinkas \email pinkas@cs.wustl.edu  \\
\addr Center for Optimization and Semantic Control,
Washington University\\ AMDOCS Inc, 1611 Des Peres Rd., St Louis, MO 63131 USA
\AND
\name Rina Dechter \email dechter@ics.uci.edu \\
\addr{Department of Information and Computer Science \\
University of California, Irvine, CA 92717, USA}
}

\maketitle

%\def\texdir{/home/cics/pinkas/tex}
%\documentstyle[/home/cics/pinkas/tex/report]{article}
%\documentstyle[12pt]{article}
%
%\begin{document}
%\pagestyle{myheadings}
%\thispagestyle{empty}
%\markboth{ 
%Optimizing Connectionist Energy Minimization Tree-Like Networks
%}{}
%\Trnumber{92-2}
%\Address{
%Department of Computer Science\\
%Washington University\\
%509 Bryan, Campus Box 1045 \\
%One Brookings Drive\\
%St. Louis, Missouri 63130\\
%pinkas@cics.wustl.edu\\
%Tel:(314) 935-7526
%}
%\thanks{Supported by NSF grant number: 22-1321-57136}
%\Titlepage
%{\baselineskip 0.30in
%\input{/home/cics/pinkas/ploff/newcommands.tex}
%\begin{center}
%{\LARGE {\bf {
%A Connectionist Energy Minimization Algorithm that Optimizes Tree-like
%Subnetworks in Linear Time
%}}}
%\end{center}
%}
%\begin{center}
%{ {\bf {
%Abstract
%}}}\\
%\end{center}
\begin{abstract}
%\Abstract
{
Symmetric networks designed for energy minimization such as Boltzman
machines and Hopfield nets %and local repair
 %techniques 
are frequently investigated  for use in optimization, constraint satisfaction and approximation
of NP-hard problems. Nevertheless, finding a { global\/} solution (i.e., 
a global minimum for the energy
function) is not guaranteed
and even a local solution may take an exponential number of steps.
We propose an improvement to the standard local activation function used for such
networks. The improved algorithm guarantees that a {\em global} minimum is found in
{\em linear} time for tree-like subnetworks. The algorithm,
called {\em activate}, is uniform 
and {\em does not} assume that the network is tree-like. 
It can identify tree-like subnetworks even in cyclic topologies (arbitrary
networks) and avoid local minima along these trees.
For acyclic networks, the algorithm is guaranteed to converge
to a global minimum from any initial state of the system (self-stabilization)
and remains correct under various types of 
schedulers. 
On the negative side, we show that in the presence of cycles,
no uniform algorithm  exists that
guarantees optimality
even under a sequential asynchronous  scheduler. 
An asynchronous scheduler can activate only
one unit at a time while a synchronous scheduler can activate any
number of units in a single time step.
In addition, no uniform algorithm exists to optimize even {\em acyclic} networks 
when the scheduler is synchronous.
% redundant
%An asynchronous scheduler can activate only
%one unit at each time while a synchronous scheduler can activate any
%number of units at the same time. 
Finally, we show how the algorithm can be improved
using the cycle-cutset scheme.
The general algorithm, called {\em activate-with-cutset}
improves over {\em activate} %since it optimizes over l still 
%optimizes tree-like subnetworks 
and has some performance guarantees that are related to the size of the
network's cycle-cutset.
}
\end{abstract}

%\setcounter{page}{1}
\newcommand{\noi}{\noindent} 
\newcommand{\xvec}{\mbox{\svec{x}{n}}} 
\newcommand{\xik}{\mbox{$x_{i_{1}},\ldots,x_{i_{k}}$}} 
\newcommand{\Xbar}{\mbox{${\bar{X}}$}}
\newcommand{\Xvector}{\mbox{${\vec{X}}$}}
\newcommand{\xbar}{\mbox{${\bar{x}}$}}
\newcommand{\zbar}{\mbox{${\bar{z}}$}}
\newcommand{\xvector}{\mbox{${\vec{x}}$}}
\newcommand{\xvectort}{\mbox{${\vec{x}'}$}}
\newcommand{\xbart}{\mbox{${\bar{x}'}$}}
\newcommand{\yvector}{\mbox{${\vec{y}}$}}
\newcommand{\zvector}{\mbox{${\vec{z}}$}}
\newcommand{\ybar}{\mbox{${\bar{y}}$}}
\newcommand{\yvectort}{\mbox{${\vec{y}'}$}}
\newcommand{\ybart}{\mbox{${\bar{y}'}$}}
\newcommand{\Xhat}{\mbox{${\hat{X}}$}}
\newcommand{\tvector}{\mbox{${\vec{t}}$}}
\newcommand{\tbar}{\mbox{${\bar{t}}$}}
\newcommand{\tvectort}{\mbox{${\vec{t}'}$}}
\newcommand{\tbart}{\mbox{${\bar{t}'}$}}
\newcommand{\IFF}{\mbox{${\Longleftrightarrow}$}}
\newcommand{\LRA}{\mbox{${\leftrightarrow}$}}
\newcommand{\Rif}{\mbox{${\Rightarrow}$}}
\newcommand{\entails}{\mbox{${\rightarrow}$}}
\newcommand{\NRif}{\mbox{${\not \Rightarrow}$}}
\newcommand{\bets}{\mbox{${\beta_{S}}$}}
\newcommand{\betst}{\mbox{${\beta_{S'}}$}}
\newcommand{\ts}{\mbox{${t_{S}}$}}
\newcommand{\Lsj}{\mbox{${L_{S}^{j}}$}}
\newcommand{\Xj}{\mbox{${X_{j}}$}}
\newcommand{\Xij}{\mbox{${X_{_{j}}}$}}
\newcommand{\EA}{\mbox{${E_{1}}$}}
\newcommand{\EB}{\mbox{${E_{2}}$}}
\newcommand{\minea}{\mbox{$min_{E_{1}}$}}
\newcommand{\mineb}{\mbox{$min_{E_{2}}$}}
\newcommand{\HE}{\mbox{${H_{E}}$}}
\newcommand{\rhddag}{\mbox{${\rhd^{\dag}}$}}
\newcommand{\Rdag}{\mbox{${R^{\dag}}$}}
\newcommand{\bexmp}{\begin{exampl}}
\newcommand{\eexmp}{\end{exampl}}
\newcommand{\nhsp}{\mbox{\hspace{0in}}}
\newcommand{\hsp}{\mbox{\hspace{.20in}}}
\newcommand{\hspa}{\mbox{\hspace{.40in}}}
\newcommand{\hspb}{\mbox{\hspace{.60in}}}
\newcommand{\hspd}{\mbox{\hspace{.80in}}}


\newcommand{\ek}{\mbox{ $E_{k}$ }}
\newcommand{\kth}{\mbox{ $k ^{th} $}}

\newcommand{\svec}[2]{\mbox{$({#1}_{1}, \ldots,{#1}_{#2})$}}
\newcommand{\Eexp}[1]{\mbox{$ E_{#1}$}}
\newcommand{\sphi}[1]{\mbox{$ \varphi _{#1}$}}
\newcommand{\sbar}[1]{\mbox{$ \vec{#1}$}}
\newcommand{\Tbar}{\mbox{$ \vec{T}$}}
\newcommand{\Ephi}{\mbox{$ E_{\varphi}$}}
\newcommand{\Aphi}{\mbox{$ \varphi_{1}$}}
\newcommand{\Bphi}{\mbox{$ \varphi_{2}$}}
\newcommand{\notM}{\mbox{$\tilde{\cal M }$}}
\newcommand{\kpspi}{\mbox{$\stackrel{k'}{\models }$}}
\newcommand{\kspi}{\mbox{$\stackrel{k}{ \models}$}}
\newcommand{\krhd}{\mbox{$\stackrel{k}{ \rhd}$}}
\newcommand{\cspi}{\mbox{$\Diamond$}}
\newcommand{\nspi}{\mbox{$ \models $}}
\newcommand{\mspi}{\mbox{$ \stackrel{>.5}{ \models}$}}
\newcommand{\wspi}{\mbox{$\stackrel{w}{ \models}$}}
\newcommand{\notspi}{\mbox{$ \not{\models}$}}
\newcommand{\spi}{\mbox{$ \models$}}
\newcommand{\msti}{\mbox{$ \stackrel{m}{\vdash}$}}
\newcommand{\csti}{\mbox{$ \stackrel{c}{\vdash}$}}
\newcommand{\sti}{\mbox{$ \vdash$}}
\newcommand{\wsti}{\mbox{$\stackrel{w}{ \vdash}$}}
\newcommand{\wequiv}{\mbox{$\stackrel{w}{ \approx}$}}
\newcommand{\pequiv}{\mbox{$\stackrel{p}{ \approx}$}}
\newcommand{\sequiv}{\mbox{$\stackrel{s}{ \approx}$}}
\newcommand{\caP}{\mbox{${\cal P}$}}
\newcommand{\caL}{\mbox{${\cal L}$}}
\newcommand{\caRp}{\mbox{${\cal R}^+$}}
\newcommand{\Oma}{\mbox{$ \Omega_1$}}
\newcommand{\Omb}{\mbox{$ \Omega_2$}}
\newcommand{\pphi}{\mbox{$ \varphi$}}
\newcommand{\Ephix}{\mbox{$E_{\varphi} \svec{x}{n}$}}
\newcommand{\bproof}[1]{{\em  Proof:} {\small {#1}\\}}
\newcommand{\eproof}{\qed }
\newenvironment{prove}{\begin{quote}  }
			{\end{quote}}
% \newenvironment{proof}{\begin{trivlist} \item[\hskip \labelsep 
%	{\sc Proof}\enskip]}
% {\unskip\nobreak\hskip 2em plus 1fil\nobreak
% \fbox{\rule[-0.5mm]{0mm}{2mm}}
	% \fbox{\rule{0ex}{0.5ex}\hspace{0.5ex}
	%\rule{0ex}{0.5ex}}
% \parfillskip=0pt \end{trivlist}}





\newenvironment{ddfn} {\begin{defn}\em}{\end{defn}}
\newenvironment{defin}{\begin{defn}\em \bf }{\end{defn}}
\newenvironment{exampl}{\begin{examp}\em}{\end{examp}}



\newtheorem{conj}{{\sc Conjecture}}[section]
\newtheorem{defn}{{\sc Definition}}[section]
\newtheorem{examp}{{\sc Example}}[section]

%\newtheorem{theorem}{{\sc Theorem}}[chapter]
%\newtheorem{theo}{{\sc Theorem}}[section]
\newtheorem{lemm}{{\sc Lemma}}[section]
\newtheorem{prop}{{\sc Proposition}}[section]
\newtheorem{coro}{{\sc Corollary}}[section]
\newtheorem{observ}{{\sc Observation}}[section]
\newtheorem{construct}{{\sc Construction }}[section]

\newcommand{\remarks}{\noindent {\sc Remarks:\ }}
\newcommand{\observation}{\noindent {\sc Observation:\ }}
\newcommand{\observations}{\noindent {\sc Observations:\ }}
\newcommand{\notation}{\noindent {\sc Notation:\ }}

% \newcommand{\qed}{\ \fbox{\rule[-0.5mm]{0mm}{2mm}}}

%\baselineskip 0.2in

\section{Introduction}
Symmetric networks such as  Hopfield networks, Boltzmann machines,
 mean-field  and Harmony networks are 
frequently
investigated for use in
 optimization,
constraint satisfaction and approximation of NP-hard problems 
\cite{Hopfielda,Hopfieldb,Boltzmann,Meanfield,Harmony,Brandt}. 
These models are characterized by a symmetric matrix of weights
and a quadratic energy function that should be minimized.
 Usually, each unit computes the gradient of the energy function
 and updates its own
activation value  so that the free  energy decreases gradually.
Convergence to a {\em local}
 minimum is guaranteed although in the worst case it is
 exponential in the number of units \cite{Kasif,Papa}.

In many cases the problem at 
hand is formulated as a minimization
problem and the best solutions (sometimes the 
{\em only} solutions) are the global minima \cite{Tank,Ballarda,PinkasNC}. 
The desired  algorithm is therefore one that manages to
reduce the  impact of shallow local minima, thus improving the  
chances of finding a global minimum.
Some models such as  Boltzmann machines and Harmony nets use
simulated annealing to escape from local minima. These models
 asymptotically converge to a global minimum,  meaning
that if the annealing schedule is slow enough, a global minimum is
 found. Nevertheless, such a schedule is hard to find
and therefore, in practice,  these networks  are not guaranteed
to find a global minimum even in exponential time. 

In this paper we look  at the {\em topology} of
symmetric neural networks.
We present an 
algorithm that finds a global minimum for acyclic networks
and otherwise optimizes tree-like subnetworks in linear time.  
We then extend it to
general topologies by dividing the network into fictitious tree-like 
subnetworks using the cycle-cutset scheme. 

The algorithm  is based on the method of
nonserial dynamic programming methods \cite{Bertele}, which was 
also used for constraint optimization \cite{Dechterc}.
There 
the task was divided between a precompilation into a tree structure
via a tree-clustering algorithm and a run-time optimization
over the tree.

Our adaptation is connectionist in style; i.e., the algorithm can
be stated as a simple,  uniform activation function
\cite{pdp2,Feldman}
and it can be executed in parallel architectures
using synchronous or asynchronous scheduling policies. 
It does  not assume   the desired topology (acyclic) and  performs
no  worse than the standard local
algorithms for all topologies.
 In fact, it may be integrated with many of the
standard algorithms in such a way that  
 the new algorithm  out-performs the standard 
algorithms by avoiding a certain class of local minima 
(along tree-like subnetworks).

Our algorithm is also applicable to  an emerging
class of greedy algorithms called {\em local repair algorithms}.
In local repair techniques, the problem
at hand is usually formulated as a minimization of a function
that measures the distance between the current
state and the goal state (the solution). The algorithm picks a setting for the
variables and then repeatedly changes those variables that cause the maximal 
decrease in the distance function. For example, a commonly used
distance function for constraint satisfaction problems
is the number of violated constraints. 
A local
repair algorithm may be viewed as an energy minimization network
%problem variables are the nodes, whereas,  a node is connected to 
%variables whose values are needed to determine the effect of changing
%the node's value on the distance function. 
where the distance function plays the role of the energy. 
Local repair algorithms are sequential though, and they use
a greedy scheduling policy; the next node to be activated
is the one leading to the largest change in the distance (i.e.,
energy).
Recently, such local repair algorithms were successfully used 
on various large-scale hard problems such as 3-SAT, n-queen, 
scheduling and constraint satisfaction \cite{Minton,Selman}. 
Since local repair algorithms may be viewed as sequential
variations on the energy minimization paradigm,
it is reasonable to assume that 
improvements in energy minimization will  also
be applicable to local-repair algorithms.

On the negative side, we show that in the presence of cycles,
no uniform algorithm  exists that
guarantees optimality
even under a sequential asynchronous  scheduler. 
An asynchronous scheduler can activate only
one unit at a time while a synchronous scheduler can activate any
number of units in a single time step.
In addition, no uniform algorithm exists to optimize even {\em acyclic} networks 
when the scheduler is synchronous.
Those negative results involve conditions on the
parallel model of execution and therefore are applicable only
to the parallel versions of local repair. 

The paper is organized as follows: Section 2 discusses connectionist
energy minimization.
Section 3 presents the new algorithm {\em activate} and
gives an example where it out-performs the standard local algorithms. 
Section 4  
discusses negative results, convergence under various 
schedulers and self-stabilization.
Section 5 extends the approach to general topologies through
algorithm {\em activate-with-cutset} and
suggests future research. Section 6 summarizes and
discusses applications.

\section{Connectionist Energy Minimization}
\label{standard}
Given a quadratic energy function of the form:
\[E(X_1,...,X_n)=-\sum_{i<j}^n w_{i,j}X_i X_j -\sum_i^n +\theta_i X_i.\]
Each of the variables $X_i\/$ may have a value of  zero or one
called the activation value, and the task is to find a zero/one assignment to 
the variables $X_1,...X_n\/$ that minimizes the energy function.
To avoid confusion with signs, we will consider the equivalent
problem of maximizing
the goodness function:
\begin{equation} \label{eq:goodness}
G(X_1,...,X_n)=-E(X_1,...,X_n)=
\sum_{i<j}w_{i,j}X_i X_j +\sum_i \theta_i X_i
\end{equation}

In  connectionist approaches, 
we look at the network that is generated by assigning a node ($i)\/$ for every
 variable
$(X_i)\/$ in the function, and by creating a weighted arc 
(with weight $w_{i,j}$) between node $i\/$
and node $j\/$, for every term $w_{i,j}X_i X_j\/$.
Similarly, a bias $\theta_i\/$ is given to unit $i\/$, if the term 
$\theta_i X_i\/$ is in the  function.  For example, Figure
\ref{fig0} shows the network that corresponds to the goodness function
$E(X_1,...,X_5)=3X_2 X_3-X_1 X_3+2X_3 X_4-2X_4 X_5-3X_3-X_2+2X_1$. 
Each of the nodes is assigned a processing unit and
the network collectively searches for an assignment that 
maximizes the goodness. 
The algorithm that is repeatedly executed in each unit/node is called the 
 {\em activation function}.
  An algorithm is {\em uniform} if it is executed by all the units.
%all the units execute it.
\begin{figure}[h t b]
\input{psfig}
%\psfig{figure=0_of_6.ps,height=2in,width=5.5in}
\psfig{figure=fig0.eps,height=2in,width=4.5in}
\caption{An example network}
\label{fig0}
\end{figure}

We give  examples for two of the most popular activation functions for
connectionist energy minimization: the discrete Hopfield network
\cite{Hopfielda} and the Boltzmann machine \cite{Boltzmann}.
In  the discrete Hopfield model, each unit computes its
 activation value using the formula:
\[X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j w_{i,j}X_j \geq - \theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right.  \]

In Boltzmann machines the determination of the activation value is
stochastic and the probability to set the activation value of a unit to one is:
\[
P(X_{i}=1)=1/({1+e^{-(\sum_j w_{i,j}X_j +\theta_i)/{T}}}),
\]
where $T\/$ is the annealing temperature.
Both approaches may be integrated with our topology-based algorithm; 
i.e., nodes that cannot be identified as parts of a  tree-like 
topology use one of the standard local algorithms. 


\section{The Algorithm}
% \subsection{Key idea}
We  assume
that the model of communication between neighboring nodes
is  a shared memory, multi-reader,
single-writer 
model.
 We also assume
 (for now) 
that scheduling is 
done with a central scheduler (asynchronous)
 and that execution
is fair.
In a {\em shared memory, multi-reader, single-writer} each unit has a shared
register
called the activation register.
A unit may read the content of the registers of all its 
neighbors but write only its own.
 {\em Central} 
scheduler 
means that the units are activated one at a time
in an arbitrary order.\footnote{
Standard algorithms need to assume the same condition 
in order to guarantee convergence to a 
{\em local} minimum \cite{Hopfielda}.
This condition can be relaxed by  restricting that only adjacent nodes
are not  activated at the same time (mutual exclusion).}
An execution is said to be {\em fair} 
if every unit is activated infinitely often. 
We do not require
{\em self-stabilization} initially. Namely, algorithms may have
an initialization step and can rely on initial values. Later we will
 relax some of the assumptions above and
examine the conditions under which the algorithm is also 
self-stabilized.

The algorithm identifies parts of the network that have no cycles (tree-like
subnetworks),
and optimizes the free energy on these subnetworks. Once a tree is
identified, it is  optimized using a dynamic programming method that
propagates values from leaves to a root and back.


Let us assume first that the network is acyclic;
 any such network may be
directed  into a rooted tree.
The algorithm is based on the observation that given an 
activation value (0/1) for a node in a tree, the optimal assignments
for 
all its adjacent nodes are independent of each other.
In particular,
the optimal assignment to the node's descendants are independent of 
the assignments for its
ancestors.
Therefore, each node $i\/$ in the tree
may compute two values:
$G^1_i\/$ is the maximal goodness contribution 
of the subtree rooted at $i$, including
the connection to $i$'s parent whose activation is {\em one}.
Similarly, 
$G^0_i\/$ is the maximal goodness of the subtree, 
including the connection to $i$'s parent whose activation value is {\em zero}.
The acyclicity property will allow us to compute
each node's $G^1_i\/$ and $G^0_i\/$  as a
simple function of its children's  values,
 implemented as a propagation algorithm initiated by the leaves. 

Knowing the activation value of its parent and the values $G^0_j,G^1_j\/$ of
all its children, a node can compute the maximal goodness of its subtree.
 When the information reaches the root, it can 
assign a value (0/1) that maximizes the  goodness of the whole network.
The assignment information propagates now toward the leaves. 
Knowing the activation value of its parent, a node
can compute the preferred activation value for itself.
At termination (at stable state), the tree is optimized.
The algorithm  has 3 basic steps:\\
\begin{enumerate}
\item {\bf Directing a  tree:} knowledge is propagated from  leaves 
toward the center so that after a linear number of steps,
every unit in the tree knows  its parent and children.
\item 
 {\bf Propagation  of goodness values:} 
the values ($G^1_i\/$ and $G^0_i\/$), are
propagated from leaves to the root.
At termination, every node knows  the maximal goodness of its subtree
and the appropriate activation value it should 
assign given that  of its parent.
In particular, the root can now decide
its own activation value so as to maximize the whole tree.
\item
{\bf Propagation of activation values:}  starting with the root,
each node in turn determines its activation value.
After O(depth of tree) steps,  the units are in a stable  state
which globally maximizes the goodness.
\end{enumerate}

 Each unit's {\em activation register\/} consists of the
following fields:
 $X_i\/$: the activation value;
$G^0_i\/$ and $G^1_i\/$: the maximal goodness values;
and $(P^1_i,..,P^j_i)$: a bit for each of the $j\/$ neighbors of $i\/$
that indicates $i$'s  parent.

\subsection{Directing a tree}
The goal of this algorithm is to inform every node of
its role in the network and its child-parent relationships.
Nodes
with a single neighbor identify themselves as leaves first 
and then identify their neighbor as a parent (point to it). 
%A node  all
%%hhhhh
%all of whose
%%hhhhh
 %neighbors point toward it,
%identifies itself as a root. 
%A node 
%all of whose
 %neighbors  but one point toward it, 
%selects the one  as a parent. 
A node identifies itself as a root when all neighbors point toward it.
When a node's neighbors but one point toward it, the node selects
the one as a parent.
Finally, a node that 
has at least two  neighbors {\em not} pointing toward it, 
identifies itself as being outside the tree.

The problem of directing a tree is related to 
the problem of selecting a leader in a distributed network,
and of selecting a center in a tree \cite{korach}.
Our problem differs (from general leader selection problems)
in that the network is a tree.
In addition, we require our algorithms to be self-stabilized.
A related self-stabilizing algorithm appeared earlier 
 \cite{Collin}. 
That algorithm is based on finding
a center of the tree as the root node and therefore creates
more balanced trees. The advantage of the algorithm presented here
is that it is space efficient requiring  only $O(log d)$ space,
when $d$ is the maximum number of neighbors each node has.
In contrast, the algorithm in Collin et al. requires $O(log n )$,
$n$ being the network size.

In the algorithm we present,
each unit uses one bit per neighbor to keep the pointing information:
 $P^j_i=1\/$ indicates  that node $i\/$ sees its  $j$th   neighbor
as its parent. By looking at $P^i_j\/$, node $i\/$ knows whether $j\/$
is pointing to it.

Identifying tree-like subnetworks in a general network
may be done by the algorithm in Figure \ref{alg1}.

\begin{figure}
\fbox{ \parbox[b]{5.9in}{
 {\bf Tree Directing  (for unit $i$):}
\begin{enumerate}
\item Initialization: If first time, then for all neighbors $j\/$: $P^j_i=0$; 
/*  Start with clear pointers (step is not needed in acyclic nets or 
with almost uniform versions)
\item If there is only a single  neighbor ($j$) and $P^i_j=0$, then 
$P^j_i=1\/$;
 /* A leaf selects its neighbor as parent if that neighbor doesn't point to it
*/
\item else, if  one and only one neighbor ($k$) does not point to $i\/$ 
($P^i_k=0\/$), then \\
$P^k_i=1\/$, and for the rest of the neighbors: $P^j_i=0$. /* $k\/$ is the 
parent */
\item else, for all neighbors $j$: $P_i^j=0$. /* Node is either a root or
outside the tree */
\end{enumerate}
} }

\caption{Tree directing algorithm}
\label{alg1}
\end{figure}
In Figure \ref{fig1}a, we see an acyclic network  after the tree
directing phase. 
The numbers on the edges represent
the values of the $P^j_i\/$ bits. In Figure \ref{fig1}b, a tree-like
subnetwork is
identified inside a cyclic network.  Note that node 5 is not a root
since not all its neighbors are pointing toward it.
%KEEP IN 5/15
\begin{figure}[h t b]
\input{psfig}
\psfig{figure=1_of_6.ps,height=1.75in,width=5.5in}
\caption{Directing a tree: a) A tree b) A cyclic network with a tree-like subnetwork. }
\label{fig1}
\end{figure}
\subsection{Propagation of goodness values}
In this phase  every node $i\/$ computes its goodness values
$G^1_i\/$ and $G^0_i\/$, by
propagating these two values from the
leaves to the root (see Figure \ref{fig2}).
%KEEP 5/15
\begin{figure}[h t b]
\input{psfig}
\psfig{figure=2_of_6.ps,height=2in,width=5.5in}
\caption{a) Propagating goodness values. b) Propagating activation 
values.}
\label{fig2}
\end{figure}

Given a node $X_i$, its parent $X_k$ and its children,
$children(i)$ in the tree, it can be shown, based on the
energy function (\ref{eq:goodness}), that the goodness values 
obey the following recurrence:
\[
G_i^{X_k} = max_{X_i \in \{0,1\}} \{ \sum_{j \in children(i)}
G^{X_i}_j+w_{i,k}X_i X_k +\theta_iX_i \}
\]
Consequently a nonleaf node $i\/$ computes its goodness 
values using the goodness values of its children as follows: 
If $X_k=0$, then  $i\/$ must decide between  setting $X_i=0$, obtaining a 
goodness of $\sum_j G^0_j\/$, or setting $X_i=1\/$, obtaining
 a goodness of 
$\sum_j G^1_j + \theta_i $.
This yields:
\[G^0_i=max\{\sum_{j \in children(i)} G^0_j,  \sum_{j \in children(i)} 
G^1_j+\theta_i \} \]
Similarly, when $X_k=1\/$,  the choice between 
 $X_i=0\/$ and $X_i=1$, yields:
\[G^1_i=max\{\sum_{j \in children(i)}
 G^0_j, \sum_{j \in children(i)} G^1_j+w_{i,k}+\theta_i \} \]
The initial goodness values for leaf nodes can be obtained from the above
(no children). Thus, $G^0_i=max\{ 0,\theta_i \}\/$,
$G^1_i=max \{0, w_{ik}+\theta_i \}$.

For example, if unit 3 in Figure \ref{fig2} is zero then the 
maximal goodness  contributed by node 1 
is $G^0_1=max_{X_1\in \{0,1\} } \{2X_1\}=2\/$ and is obtained
at $X_1=1$. Unit 2 (when $X_3=0$) contributes 
 $G^0_2=max_{X_2 \in \{0,1 \} }\{-X_2\}=0\/$ 
obtained at $X_2=0$, while  
$G^1_2=max_{X_2 \in \{ 0,1\} } \{3 X_2-X_2\}= 2$
is obtained at  
 $X_2=1\/$. 
As for nonleaf nodes, 
if $X_4=0\/$, then when $X_3=0\/$, the goodness contribution 
will be $\sum_k G^0_k=2+0=2$, while if $X_3=1\/$, the contribution will be
$-3+\sum_k G^1_k=-3+1+2=0$. The maximal contribution 
$G^0_3=2\/$ is achieved at $X_3=0\/$.

Goodness values may  be computed once for every node when its children's
goodness values are ready; however, for self-stabilization (to be discussed 
later) and for simplicity, nodes may compute their goodness values repeatedly
and without synchronization with their children.

%\fbox{ \parbox[b]{6.2in} {
%\noi{\bf Propagating Energy Alternatives (unit $i$):}
%\begin{enumerate}
%\item If node $i\/$ is a leaf and $k\/$ is its parent: 
%$G^0_i=max \{ \theta_i,0 \}$; 
%$G^1_i=max \{w_{i,k}+\theta_i,0\}$
%\item If node $i\/$ is not a leaf and has a parent $k\/$ and children $j$: \\
%$G^0_i=max \{ \sum_{j \in children(i)} G^0_j, 
% \sum_{j \in children(i)} G^1_j + \theta_i\}\/$;\\
%$G^1_i=max\{\sum_{j \in children(i)} G^0_j, 
%\sum_{j\in children(i)} G^1_j +w_{i,k}+\theta_i \}$;
%\end{enumerate}
%}
%}

\subsection{Propagation of activation values}
Once a node  is assigned an activation value, all its children 
can activate themselves so as to maximize the goodness of the subtrees
they control. When such value is chosen for a node, its children can evaluate  
{\em their}
activation values, and the process continues until the whole tree 
is assigned.

There are two kinds of nodes that may start the process: a root which will 
choose an activation value to optimize the entire tree,
and a non-tree node
which uses a standard activation function.

When a root $X_i$ is identified, 
if the maximal goodness is $\sum_j G^0_j\/$, 
it chooses the value ``0.''
If the maximal goodness is $\sum_j G^1_j +\theta_i$, 
it chooses ``1.'' 
In summary, the root  chooses its value according to:
\[X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j G^1_j+\theta_i\geq \sum_j G^0_j$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. \]
In Figure \ref{fig2} for example, $G^1_5 + G^1_3+0=2< G^0_5+G^0_3=3\/$
and therefore $X_4=0$.

An internal node  whose parent is $k$  chooses
an activation value  that maximizes $\sum_j G^{x_i}_j+w_{i,k}X_i X_k
+\theta_iX_i$. The choice  therefore, is between 
$\sum_j G^0_j\/$ (when $X_i=0$) and $\sum_j G^1_j+w_{i,k}X_k +\theta_i\/$ 
(when $X_i=1$), yielding:
\[X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j G^1_j+w_{i,k}X_k+\theta_i\geq \sum_j G^0_j$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. \]
As a special case, a leaf $i$
  chooses $X_i=1\/$ if $w_{i,k}X_k \geq -\theta_i\/$,
which is exactly the discrete Hopfield activation function for a node with
a single neighbor. For example, in Figure \ref{fig2}, $X_5=1\/$ since 
$w_{4,5}X_4=0>-\theta_5=-1$, and $X_3=0\/$ since $G^1_1+G^1_2+2X_4+\theta_3
=1+2+0-3=0<G^0_2+G^0_1=2$. Figure \ref{fig2}b shows the activation
values obtained by propagating them from the root to the leaves.
%\\
%\fbox{ \parbox[b]{6.2in} {
%{\bf Propagation of Activation Values (unit $i$):}
%\begin{enumerate}
%\item If for all neighbors ($j$), $P^i_j=1$, then /* a root */
%\[ X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j (G^1_j - G^0_j)\geq -\theta_i$}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. \]
%\item else, if there exist one and only one neighbor ($k$) such that
%$P^i_k=0\/$, and the rest of the neighbors (if exist) have $P^i_j=1$, then
%\hsp /* A non-root node in the tree */
%\[X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j (G^1_j - G^0_j)+ w_{i,k}X_k\geq -\theta_i$}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. \]
%\item else,  $X_i=$ $<$standard-activation-function$>$.\hsp /* 
%Not part of a tree */
%\end{enumerate}
%}}

\subsection{A complete activation function} \label{complete}
Interleaving the three algorithms described earlier achieves the
goal of identifying tree-like subnetworks and maximizes their goodness.
In this subsection we present the complete algorithm, combining the three
phases while simplifying the computation.
The algorithm is integrated with
the discrete Hopfield activation function  demonstrating
 how similar the formulas are. 

The steps of the algorithm can be interleaved freely; i.e., a scheduler
might execute each step for all the nodes or all steps for any given node
(or combinations). These steps are computed repeatedly with no synchronization
with the node's neighbors.\footnote{ As we will see later, the amount of
parallelism will have to be limited somewhat, as from time to time two 
neighboring nodes should not execute the tree-directing step at the same time.}
Algorithm {\em activate} executed by
unit $i\/$ (when $j\/$ denotes  a non-parent neighbor of $i\/$ 
and  $k\/$  denotes the  parent of $i$) is given in Figure \ref{alg2}.
Algorithm {\em activate} improves on an arbitrary local
search connectionist algorithm in the following sense:

\begin{theo}
If $a_1$ is a local minimum generated by ``activate'' and $a_2$ is a
local minimum generated by a local-search
method (e.g., Hopfield), and if $a_1$ and $a_2$ have the same 
activation values on 
non-tree nodes,
then $G(a_1) \leq G(a_2)$. 
\end{theo}

\noindent
{\em Proof:\/}
Follows immediately from the fact that {\em activate} generates
a global minimum on tree-subnetworks.
$\Box$
    
Additional properties of the algorithm will be discussed in Section 4.

\begin{figure}

 \fbox{ \parbox[b]{5.9in} {
{\bf Algorithm activate: Optimizing on Tree-like Subnetworks (unit $i$):}
\begin{enumerate}
\item Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$; 
/*Clear pointers (cyclic nets)*/
\item Tree directing: If there exists a single neighbor $k\/$, such that $P^i_k=0$, \\
\hsp then
$P^k_i=1\/$ and for all other neighbors $j\/$, $P_i^j=0$; \\
\hsp else, for all neighbors $P^j_i=0$;
\item Computing goodness values:\\
$G^0_i=max\{\sum_{j\in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} G_j^1 P^i_j+\theta_i\}$;\\
 $G^1_i=max\{\sum_{j \in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} (G_j^1 P^i_j+w_{i,j}P^j_i)
+\theta_i\};$
\item Assigning activation values:\\
If at least two neighbors are not pointing to $i$, then  /*Not in tree: use  
Hopfield*/
\\ \hsp $
X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j w_{i,j}X_j \geq -\theta_i $}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $\\
 else, \hsp /* Node in a tree (including root and leaves) */\\
\hsp $ X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j ((G^1_j - G^0_j)P^i_j+ w_{i,j}X_j P^j_i)\geq 
-\theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $
\end{enumerate}
}}
\caption{Algorithm activate for unit $i$}
\label{alg2}
\end{figure}


\shrink{
\subsection{Goodness computation  without tree-directing} \label{complete1}
When restricted to acyclic networks,
the tree-directing procedure
is not needed for computing the goodness values, 
but merely for assigning activation
after the goodness values had converged.
The idea is that each node compute for each of its neighbors a
pair of goodness values 
as if each neighbor is its ``parent.''
Figure \ref{alg3} presents algorithm {\em activate1} for
unit $i\/$ where $j\/$  is an arbitrary neighbor of $i\/$ 
and  $k\/$ is the neighbor to which the goodness
values are directed.

\begin{figure}
 \fbox{ \parbox[b]{5.9in} {
{\bf Algorithm activate1: Optimizing goodness on Tree-like subnetworks (unit $i$):}
\begin{enumerate}
%\item Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$; 
%/*Clear pointers (cyclic nets)*/
%\item Tree directing: If there exists a single neighbor $k\/$, such that $P^i_k=0$, \\
%\hsp then
%$P^k_i=1\/$ and for all other neighbors $j\/$, $P_i^j=0$; \\
%\hsp else, for all neighbors $P^j_i=0$;
 \item Computing goodness values for neighbor $k$:\\
$G^0_{k,i}=max\{\sum_{j\in neighbors(i), j \neq  k} G^0_{k,j}, 
\sum_{j \in neighbors(i);j\neq k} G_{k,j}^1 +\theta_i\}$;\\
 $G^1_{k,i}=max\{\sum_{j \in neighbors(i);j \neq k} G^0_{k,j} , 
\sum_{j \in neighbors(i);j \neq k} (G_{k,j}^1) +w_{i,k}
+\theta_i\};$
%%\item Assigning activation values:\\
%If at least two neighbors are not pointing to $i$, then  /*Not in tree: use  Hopfield*/
%\\ \hsp $
%X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j w_{i,j}X_j \geq -\theta_i $}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. $\\
% else, \hsp /* Node in a tree (including root and leaves) */\\
%%\hsp $ X_i =\left\{ \begin{array}{ll}
%%	1 & \mbox{ if  $\sum_{j \in neighbors(i)} ((G^1_j - G^0_j))\geq 
%%-\theta_i$}\\
%%	0 & \mbox{ otherwise }
%%	\end{array}
%%	\right. $
 \end{enumerate}
}}
\caption{Algorithm activate1}
\label{alg3}
\end{figure}
It is easy to show that
the goodness values are guaranteed to 
converge to their correct values.

The task of ``assigning activation value'' 
still needs to be done in a coordinated
manner using the structure of the tree.
Each node will be assigned a value relative to the value
that its parent has, as before.
%101010
}
\subsection{An example}
The example illustrated in Figure \ref{fig3} demonstrates a case where a local
minimum of the standard algorithms is avoided. Standard algorithms may enter
such local minimum and stay in a stable state that is clearly wrong.

The example is a variation on a Harmony network example   \cite{Harmony}
 (page 259), and \cite{pdp1} (page 22).
%KEEP IN 5/15
\begin{figure}[h t b]
\input{psfig}
\psfig{figure=3_of_6.ps,height=3in,width=5.5in}
\caption{A Harmony network for recognizing words: local minima along the 
subtrees are avoided.}
\label{fig3}
\end{figure}
The task of the network is to identify words from low-level line segments.
Certain patterns of line segments excite units that represent characters,
and certain patterns of characters excite units that represent words.
 The line strokes used to draw the characters are the input units:
L1,..., L5. The units
 ``N,'' ``S,'' ``A'' and  ``T'' represent characters.  The units
``able,'' ``nose,'' ``time'' and  ``cart'' represent words, and  
Hn, Hs, Ha, Ht, H1,... H4 are hidden units required by the Harmony model.
For example, given the line segments
of the character S,  unit L4 is activated (input), and this causes units 
Hs and ``S''
to be activated. Since ``NOSE'' is the only word that contains the character 
``S,'' both H2 and the unit ``nose'' are also activated and the word ``NOSE''
is identified.

The network  has feedback cycles (symmetric weights) so that ambiguity among
characters or line-segments may be resolved as a result of identifying
a word.
For example, assume that  the line segments required to recognize the word 
``NOSE'' appear,  but the character ``N'' in the input is blurred and therefore
the setting of unit L2 is ambiguous.
Given the rest of the line segments (e.g., those of the character
 ``S''), the network identifies the word ``NOSE'' and activates units ``nose''
and H2. This will cause unit ``N'' and all of its line 
segments to be activated. 
Thus, the ambiguity of L2 is resolved.

 The network is designed to have a global minimum  when L2, Hn, ``N,'' 
H2 and  ``nose'' are all activated. 
However, standard connectionist  algorithms may fall 
into a local minimum when  all these units are zero, generating goodness
of $5-4=1$. 
The correct
setting (global minimum) is found by our tree-optimization algorithm
(with goodness: 3-1+3-1+3-1+5-1-4+3-1+5=13). The thick arcs in the 
upper network of Figure \ref{fig3} mark the arcs of a tree-like subnetwork.
This tree-like subnetwork is drawn with pointers and weights  
 in the lower part of the figure. Node ``S'' is
not part of the tree and its activation value is set to one because
the line-segments of ``S'' are activated. Once ``S'' is set, the units
along the tree are optimized (by setting them all to one) and the 
 local minimum is avoided.

\section{Feasibility, Convergence, and Self-Stabilization}
So far we have shown how
to enhance the performance of connectionist energy
minimization networks without losing much of the
simplicity of the standard approaches. 
The simple algorithm presented is limited in three ways, however. First,
it assumes unrealistically that a central scheduler is used; i.e., 
 a scheduler that
activates the units one after the other asynchronously. 
The same results are obtained if the steps of the algorithm executes as one
 atomic operation or if neighbors
are mutually excluded.
 We would like the network to work correctly 
under a {\em 
distributed  (synchronous)
scheduler}, where  any subset of units may be
activated  for  execution at the same time synchronously. Second, the algorithm guarantees
convergence to global optima only for tree-like subnetworks. We would like to find an algorithm 
that converges to correct solutions even if cycles are introduced.
 Finally,
we would like the algorithm to be {\em self-stabilizing}. It should converge 
to a legal, stable state  given enough time, even after  noisy fluctuations
that cause the units to execute arbitrary program states and the registers
to have arbitrary content. 
Formally, an algorithm is {\em self-stabilizing\/} 
if in any fair execution, starting from any
input configuration and any program state (of the units), the system reaches a
valid stable configuration. 

In this section, we illustrate two negative results regarding the first two
problems; i.e., that it is not feasible to build uniform algorithms 
for trees under a 
distributed
 scheduler, and  that 
such an algorithm is not feasible 
for cyclic networks
even under a central scheduler. We then show how to weaken the
conditions so that convergence is guaranteed (for tree-like subnetworks)
in realistic environments
 and self-stabilization is obtained.



A scheduler can generate any specific 
schedule consistent with its definition. Thus, the central scheduler
can be viewed as a specific case of the 
 distributed 
scheduler.
We say that a problem is {\em impossible} for a scheduler if for every
possible algorithm there exists a fair execution generated by such a
scheduler that does not find a solution to the problem.
Since all the specific schedules generated by a central scheduler
can also be generated by a 
 distributed 
scheduler,
what is impossible for a central scheduler is also impossible for a
distributed scheduler.

\subsection{Negative results for uniform algorithms}

Following  Dijkstra (1974), negative results were presented regarding the
feasibility of distributed constraint satisfaction \cite{Collin}.
Since constraint satisfaction problems can be formulated
as energy minimization problems, these feasibility 
results apply also for computing the 
global minimum of energy functions. 
For completeness we now  adapt those results
for a connectionist computation of energy minimization.
\begin{theo} 
 No 
deterministic\footnote{ The proof of this theorem assumes determinism and 
does not apply to 
stochastic activation functions.}
uniform
 algorithm  exists that  guarantees
a  global minimum under a distributed scheduler,
even for simple chain-like trees,
assuming that the algorithm needs to be insensitive to initial 
conditions.
\end{theo}
{\em Proof\/}
(By counter example):
 Consider the network of Figure \ref{figtree:neg}. There are two global
minima possible : $(11...1101...1)\/$ and $(11...1011...1)$
(when the four centered digits are assigned to units, $i-1,i,i+1,i+2$). If the
network is initialized such that all units have the same register values,
and all units start with the same program state,
then there exists a fair execution under a distributed scheduler such that in
every step all units are activated.
The units left of the center ($1,2,3,...i$) ``see''  the same input as those
units right of the center ($2i,2i-1,2i-2,...,i+1$) respectively. Because
of the uniformity and the determinism,
the units in each pair ($i,i+1),(i-1,i+2),...,(1,2i$) must
transfer to the same program state and produce the same output on the activation
register.
%\footnote{We assume that when execution begins, all units are
%initialized with the same values and  that all of them start in the 
% same program state.}
Thus, after every step of that execution,
units $i\/$ and $i+1\/$ will always have the same 
 activation value and
a global minimum (where the two units have different values) will never be
obtained. $\Box$
%\eproof

%KEEP 5/15
\begin{figure}[h t b]
\input{psfig}
\psfig{figure=4_of_6.ps,height=1.75in,width=5.5in}
\caption{No uniform algorithm exists to optimize chains under distributed 
schedulers.}
\label{figtree:neg}
\end{figure}

This negative result should not discourage us in practice since it relies 
on an obscure infinite sequence of executions which is unlikely to 
occur under a random  scheduler. Despite this negative result, 
one can show that
algorithm  {\em activate}
will optimize the energy of tree-like
subnetworks
under a  distributed scheduler if at least one of the following cases holds
(see the next section for details):
\begin{enumerate}
\item
 If step 2 of 
algorithm {\em activate} in Section \ref{complete} is atomic;
i.e., no other neighbor may execute step 2 at the same time.
\item  if for every node $i\/$ and
every neighbor $j\/$, node $i\/$ is executed without $j\/$ infinitely often
(fair exclusion);
\item if one node is unique  and acts as a root, that is, 
does not execute step 2 (an almost uniform algorithm); 
\item  if the network 
is cyclic (one node will be acting as a root).\footnote{Global solutions 
are not guaranteed to be found but all tree-like subnetworks will be optimized.}
\end{enumerate}

Another negative result similar to \cite{Collin} is given in the following
theorem.
\begin{theo} 
If the network is cyclic, no 
deterministic 
uniform algorithm exists that guarantees
a  global minimum, even under a { central} scheduler,
assuming that the algorithm needs to be insensitive to 
initial conditions.

\end{theo}
{\em Proof\/} 
(by counter example):
This may be proved even for
cyclic networks as simple as rings.
 In Figure \ref{figtree:ring} we see a ring-like
network whose global minima are $(010101)\/$ and $(101010$).
Consider a fair execution under a central scheduler that activates the  units
1,4,2,5,3,6 in order and repeats this order  indefinitely. Starting
with the same program state and same inputs, the two units in every pair
of  (1,4), (2,5), (3,6)  ``see''  the same input, therefore they have 
the same output and transfer to the same program state. 
As a result, these units  never output different values and a global minimum
is not obtained.
$\Box$

Note that any tree-like subnetwork of a cyclic network will be optimized even 
under a distributed scheduler (since nodes that are part
of a cycle are identified as roots
 and the algorithm acts as an almost uniform algorithm).
%KEEP 5/15
\begin{figure}[h t b]
\input{psfig}
\psfig{figure=5_of_6.ps,height=2.15in,width=5.5in}
\caption{ No uniform algorithm exists that
guarantees to optimize rings even under a central
scheduler.}
\label{figtree:ring}
\end{figure}




\subsection{Convergence and self-stabilization} \label{selfstab}
In the previous subsection we proved that under a pure distributed
scheduler  there is no hope for a uniform network algorithm.
In addition, we can easily show that the algorithm is not self-stabilizing
when cycles are  introduced. For example, consider the configuration of
the pointers in the ring of Figure \ref{figtree:ringb}. 
It is in a stable state although
clearly not a valid tree.\footnote{Such configuration will never occur if all
units start at the starting point; i.e., clearing the bits of $P_i$.
It may only happen due to some noise or hardware fluctuations.}

%KEEP 5/15
\begin{figure}[h t b]
\input{psfig}
\hspace{2.5in}
\psfig{figure=6_of_6.ps,height=1.in,width=1.in}
\caption{ The uniform algorithm is not self-stabilizing in cyclic networks.}
\label{figtree:ringb}
\end{figure}

In this subsection we  weaken the requirements allowing
our algorithm to converge to correct solutions and to be self-stabilizing
under realistically weaker distributed schedulers.
We will not use the notion of a {\em pure\/} distributed scheduler; instead,
we will ask our distributed scheduler to have the {\em fair exclusion}
property.
\begin{ddfn}
A scheduler has the {\em  fair exclusion} property if
for every two neighbors, one is executed without the other  infinitely
often.
\end{ddfn}
Intuitively, a distributed scheduler with fair exclusion will no longer
generate infinite sequences of the pathological execution schedules used
in the previous subsection to prove the negative results. Instead,
it is guaranteed that from time to time, every two neighboring units
will not execute together.

As an alternative, we might weaken the requirement on the uniformity of the
algorithm (that all nodes execute the same procedure). An {\em almost
uniform} algorithm is when all the nodes perform the same procedure
except one node that is marked  unique. In the almost uniform version
of algorithm {\em activate}, the root of the tree is marked and
executes the procedure of Section \ref{complete} as if all its 
neighbors are pointing to it; i.e., it constantly sets $P_i^j\/$ to
zero.

\begin{theo} \label{bigtheo}
Algorithm {\em activate} of Section \ref{complete} has the following
properties: 
1. It converges to a global minimum
and is self-stabilizing\footnote{
The initialization step of
the algorithm is omitted in the self-stabilizing version.}
 in
networks with tree-like topologies under a 
distributed 
scheduler with fair exclusion.
2. The algorithm also converges in tree-like subnetworks
(but is not self-stabilizing) 
when the network has cycles.
3. It is self-stabilizing for any topology if an
{\em almost\/}  uniform algorithm is applied, 
even under a {\em pure\/} distributed scheduler.
\end{theo}
 For proof see appendix.

%In addition to the above, it is possible to obtain self-stabilization
%with the algorithm even for general cyclic networks by adapting
%the self-stabilizing tree-directing
%protocol of \cite{Collin}. The adaptation of \cite{Collin} however, will
%cost us more in memory and complexity and will be a greater diversion
%from the simple connectionist-style activation function we aspired.

%\input{extensions2}

\section{Extensions to Arbitrary Networks}

The algorithm we presented in Section 3 is limited
in that it is
restricted to nodes of
tree-like subnetworks only.
Nodes that are part of a cycle execute the traditional  activation
function which may lead to the known 
drawbacks of
local  energy minima
  and slow convergence.
In this section we discuss  
generalizations of our
algorithm 
to nodes that are part of cycles,
that will work well for near-tree networks.
A full account of this extension is deferred for future work.

A well known scheme for extending tree
algorithms to non-tree networks, is 
 {\em cycle-cutset decomposition} \cite{DechterEnhancement},
used  in Bayes networks and constraint networks.
%In tree clustering
%the idea is to combine subsets of variables into higher level 
%{\em meta} variables
%until the interaction between the meta level variables is tree-like.
Cycle-cutset decomposition 
is based on  the fact that an instantiated variable cuts
the flow of information on any path on which it lies and therefore it
changes the effective connectivity of the network.
Consequently, when the group of instantiated variables
cuts all cycles in the graph, (e.g., a cycle-cutset),
the remaining network
can be viewed as cycle-free and can be solved by a tree algorithm.
The complexity of the cycle-cutset method can be bounded
exponentially in the size of the cutset in each connected component
of the graph \cite{reference-survey}.
We next
show how to improve our energy 
minimization algorithm, {\em activate}
%ddd eliminated footnote
%\footnote{By ``tree-algorithm'' we refer to
%algorithm {\em activate} when applied to an 
%acyclic 
%network},
using the cycle-cutset idea.

Recall that the energy minimization task is to  find a zero/one
assignment to the variables $ X = \{ X_1 ,..., X_n \}$ that maximizes the 
goodness function. Define 
$Gmax(X_1 ,..., X_n) = max_{X_1 ,..., X_n } G(X_1,..., X_n)$.
The task is to find an activation level $X_1, ..., X_n$
satisfying
\begin{equation} \label{eq:goodnessB}
Gmax (X_1 ,...X_n ) = max_{X_1 ,..., X_n} (\sum_{i<j}w_{i,j}X_i X_j +\sum_i \theta_i X_i ).
\end{equation}
Let $Y = \{ Y_1 ,..., Y_k \}$ be a subset of the  variables $X= \{X_1 ,..., X_n \}$.
The maximum can be computed in two steps.
First compute the maximum goodness conditioned on a fixed assignment
$Y=y$, then maximize the resulting function
over all possible assignments to $Y$.
Let $Gmax(X | Y = y)$, be the maximum goodness value of G
conditioned on $Y=y$. 
Clearly,
\[
Gmax(X) = max_{Y=y} Gmax(X|Y=y)= max_{Y=y}max_{\{X = x | x_Y = y\}}\{ G( X )\},
\]
where, $x_Y$ is the zero/one value assignments in the instantiation
$x$ that are restricted to the variable subset $Y$.
If the variables in $Y$ form a cycle-cutset, then the conditional
maxima $Gmax(X|Y =y )$ can be computed efficiently
using a tree algorithm. The overall maxima
may be  achieved subsequently by
enumerating over all possible assignments to $Y$.
% eliminating footnote
%\footnote{As a matter of 
%fact, enumeration can be
%restricted to each nonseparable component and to each of its own
%cutset size, since the hyper structure between components
%is tree-like \cite{reference-survey}, \cite{Even}.}
Obviously, this scheme is effective only when the cycle-cutset
is small.
We next discuss  some steps towards implementing this idea
in a distributed environment. 

Given a network with a set of nodes $X = \{X_1 ,..., X_n \}$, 
and a subset of 
cutset variables 
$Y = \{ Y_1 ,..., Y_k \}$,
presumably a cycle-cutset, and assuming 
a fixed, unchangeable assignment $Y=y$, 
the cutset variables behave like leaf nodes, namely,
they select each of their neighbors as a parent if that neighbor
does not point to them. %(i.e., for every neighbor $(j)$
%if $P^i_j = 0$, then $P^j_i =1$;).
%(2) that each node knows whether or not it is designated as a cutset 
%node, and (3) that a cutset node has already have 
%an assigned activation value of `0' or `1'.\footnote{
%Later we'll see that the assumptions above need not hold. We can
%design a uniform algorithm which obtains a cutset using randomization and
%determines the cutset values using a local algorithm. 
%In addition, we can design 
%an algorithm (with exponential complexity) that computes a global solution
%($GMAX$) by enumerating all possible cutset values.
 %}
%We denote the cutset node assignments, $Y=y$.
%Under these assumptions
%we show that the network can compute the conditional
%maxima energy, $Gmax(X|Y=y)$, using a simple modification to the tree
%algorithm {\em activate}.
%The modified procedure, called {\em activate-with-cycle}
%is given next.
%
%Algorithm {\em activate-with-cutset-values}  is guaranteed to
%compute the maximum energy of the network conditioned to $Y=y$.\\
%\\
%\fbox{ \parbox[b]{6.2in} {
%{\bf Algorithm activate-with-cutset-values: Optimizing with cycle-cutset,\\
%Assumptions: 1) The cutset ($Y$), removes all cycles. 2)
% The values of the cutset nodes ($y$) are known a priori.}
%
%\begin{enumerate}
%\item Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$; 
%/*Clear pointers (cyclic nets)*/
%\item Tree directing:\\
%	If $i\/$ is a cutset node, then  for every neighbor ($j$)
%If $P_j^i = 0$, then 
%$P^j_i=1\/$;
%\hsp (A cutset variable selects each of its neighbors as a parent 
%if that neighbor doesn't point to it.)\\
%else (regular node),
%if there exists a single neighbor $k\/$, such that $P^i_k=0$, \\
%\hsp then $P^k_i=1\/$ and for all other neighbors $j\/$, $P_i^j=0$; \\
%%\hsp 
%else, for all neighbors $P^j_i=0$;
%
%\item Assigning activation values:\\
%If $i\/$ is a cutset node, then $X_i=y_i$, where $y_i\/$ is the cutset (known)
%value.  \\
%else (regular tree nodes)\\
%\hsp $ X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j ((G^1_j - G^0_j)P^i_j+ w_{i,j}X_j P^j_i)\geq 
%-\theta_i$}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. $
%
%\item Computing goodness values: \\
%If (cutset node)  \\
%\hsp (For each neighbor ($j$),  $G^0_i,G^{j1}_i$ are goodness
%values for neighbor ($j$) ). \\
%\hsp $G^0_i=y_i(\theta_i)$,\\
%\hsp $G^{j1}_i=y_i(\theta_i ) + w_{ij}$\\
%else (a regular tree node),\\
%\hsp $G^0_i=max\{\sum_{j\in children(i)} G^0_j P^i_j, 
%\sum_{j \in children(i)} G_j^1 P^i_j+\theta_i \}$;\\
%\hsp $G^1_i=max\{\sum_{j \in children(i)} G^0_j P^i_j, 
%\sum_{j \in children(i)} (G_j^1 P^i_j+w_{i,j}P^j_i)
%+\theta_i \};$ \\
%\hsp (note that, if ($j$) is a cutset node,  then $G^1_j = G^{i1}_j$)
%
%\end{enumerate}
%}}
%The basic idea is to let each cutset node behave as a leaf node.
%One can view a cutset node
%as if it duplicates itself
%per each neighbor. 
%In the above algorithm we assume that all the  nodes are on the tree, some
%of which are cutset nodes that act as leaves.
%The change to the tree-directing part is in that a cutset
%variable, makes each one of its neighbors
%(for whom it is not a parent),
%its own parent. 
Thus, a cutset variable may have several parents and zero or more 
child nodes.% part-of-a-tree neighbors (which point to it).

Considering again the example network in Figure \ref{fig1}b and assuming
node (7) is a cutset variable, a tree-directing may now
change so that node (7) points both to (5) and to (6), (6) points to (5)
and (5) remains the root. Note that with this modification
all arcs are directed and the resulting graph is an acyclic 
directed graph.
Once the graph is directed, each regular non-cutset node
has exactly the same view as before. 
It has one parent (or no parent) and perhaps a set of child nodes, some of 
which may be cutset nodes.
It then computes goodness values and activation values
almost as before.

An algorithm along these lines
will compute the maximum energy conditioned on $Y=y$,
if $Y$ is a cycle-cutset.
%A cutset variable will compute its goodness
%values for each of its neighbors separately, based on the
%weighted arc with the parent (The $G^0_i$'s are identical for all 
%parents
%but the $G^1_i$ may differ for each parent). As well, 
%if one of the children of node $i$ is a cutset variable,
%$i$ should be using the goodness values of that child 
%that is designated to it, when computing its own goodness values.
%The reader should note  that a solution found in this method is indeed
%a  global energy minimum (goodness maximum)
%conditioned on the values of the cutset variables.
% end-changes
Note however that such an assignment is not guaranteed to converge 
to a {\em local  }
maxima of the original (Hopfield) activation function.
Some of the cutset nodes  may be unstable relative to this function. 
%and may flip their value if they use 
%relative to the Hopfield activation function.

Enumerating all the conditional maxima to get a global maxima cannot 
be done distributedly, 
unless the cutset size is small. 
When the cutset is small,
 the computation can be done in parallel, yielding a practical 
distributed solution
for 
%semi-connectionist 
networks, as follows.
%One obvious use of this algorithm
%for computing {\em unconditional minima } is by
%%we have to address the issue of enumerating 
%enumeration of all conditional
%energy minimizations over all instantiations of $Y$.  
%%One option we propose, is to use
%% the brute-force approach of computing all conditional
%%goodness values in parallel as follows.
%This algorithm is exponential (definitely not connectionist) but may be
%computed in parallel as follows:
Once the tree-directing part is accomplished, a node
computes a collection of goodness values, each indexed by a 
conditioning assignment $Y=y$.
%\footnote{In actuality, a node will only 
%condition its values
%on a subset of the cutset variables that reside
%in the directed subtree for which it is the root.}
%Nodes will compute goodness values associated with each
%assignment to the cutset variable.
%In step (4) of the algorithm 
The goodness values of a node
that are associated with the cutset assignment $Y=y$ 
will be computed
using the goodness values of child nodes that are  also
associated with the same assignment $Y=y$.
The maximum number of goodness values each node
may need to carry is exponential in the cutset size.
%\footnote{A 
%careful implementation can assure that the maximum
%number of goodness values that must be carried by each node is
%exponential only in the cutset size of its own nonseparable
%component.}
Upon convergence, the roots of the trees %obtained from the cutset
will
%compare the goodness value associated with all its indices,
select an assignment $Y=y$ that will maximize the overall goodness
value % and then choose a corresponding activation
 %value. Subsequently, it will 
and
propagate this information down the tree 
so that nodes
 will switch values accordingly.
%Nodes will compute their activation using those 
%goodness values that are associated with the maximizing
%assignment.
%Cutset variables will switch
%to the activation value associated with the selected assignment.
%All the above steps can be executed using one activation
%function.
%One can envision a hybrid algorithm that 
%combines a heuristic
%centralized method for finding a small cutset \cite{geiger},
The above algorithm is certainly not in the connectionist spirit and is 
practically limited to small cutsets. Its advantage is  that it finds a
true global optimum. 
%our %activate-with-cutset-values 
%algorithm, together  with the parallel
%enumeration mentioned above.
%The main issue that still must be addressed  in this approach,
%is where do the cutset variable come from? How
%will they be selected. It is known that computing the minimal cutset is
%NP-hard. We will therefore, settle for any heuristic method that
%tries to compute a small cutset.
%One simple answer is that the determination of the cutset variable,
%is performed centrally and announced to each node. 
%This enumeration idea clearly violate the spirit of connectionist 
%computation, 
%but may nevertheless be a practical solution for real, 
%semi-connectionist networks.
%Alternatively, we should be looking for a 

%uniform algorithm for finding  a cycle-cutset.
%Clearly the problem is unsolvable for completely uniform
%networks.
% For an almost uniform network, when just one node
%is allowed to execute a different algorithm, one can envision
%a algorithm that may simulate one of the 
%approximation algorithms for cycle-cutset \cite{geiger}.
%This is one of the open issues that we leave for 
%future work.

In the following subsection, we will modify the cutset approach 
more towards the connectionist spirit 
%in two directions. 
%The first is to compute an {\em unconditioned} global solutions by enumerating
%all possible cutset values. The  second direction is to combine a 
%standard local 
%activation algorithm with the cutset technique.
%This combination produces a
by integrating the cutset scheme with a standard energy minimizing
activation function.
This yields a connectionist-style algorithm 
with a simple activation function and limited memory requirements
%ddd
once the identity of the cycle-cutset nodes is known.
We can determine the cutset variables 
initially
using a centralized algorithm 
for computing a small cutset \cite{geiger}. 
Although not guaranteed 
to find a global solution,  
the new activation function is 
more powerful than standard approaches
on cyclic topologies.
%both standard and cutset methods alone.

\subsection{Local search with cycle cutset}

%In this
%approach we to use the cutset method to improve {\em local}
%search (without
%trying to enumerate all possible   cutset values), %while keeping the 
%%activation function simple. 
%We first 
Algorithm {\em activate-with-cutset} in Figure \ref{alg4}
assumes that the cutset nodes are 
known a priori; %or randomly selected 
this time however,
their values are  changing using standard local techniques 
(e.g., Hopfield).
The algorithm is well-defined also when the cutset
nodes do not cut all cycles or when the cutset is not minimal.
However, it is likely to work best when the cutset is small and when
it cuts all cycles.

\begin{figure}
\noi \fbox{ \parbox[b]{5.9in} {
{\bf Algorithm activate-with-cutset (unit i)  \\
%Optimizing with cycle-cutset when values are not given,\\
Assumption: The cutset nodes are given a priori.
%hhhh Assumption2:All cycles are eliminated as a result of the cutset.\\
%(unit $i$):
}

\begin{enumerate}
\item Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$; 
\item Tree directing:\\
If $i$ is a cutset node,
	for every neighbor ($j$),
if $P_j^i=0$, then $P^j_i=1\/$;\\
\hsp (neighbors become parents unless they already point to it) \\ 
else (not a cutset node),
if there exists a single neighbor $k\/$, such that $P^i_k=0$, \\
\hsp then (part of a tree but not a root) $P^k_i=1\/$ and for all other neighbors $j\/$, $P_i^j=0$; \\
else (root or non-tree node), for all neighbors $P^j_i=0$;

\item Assigning activation values:\\
If all neighbors of $i\/$ point to it except maybe one (i.e., it is
part of a tree) then,\\
\hsp $ X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j ((G^1_j - G^0_j)P^i_j+ w_{i,j}X_j P^j_i)\geq 
-\theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $\\
else (a cutset node or a node that is not yet part of any tree), 
Compute Hopfield:\\
\hsp $ X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j  w_{i,j}X_j\geq -\theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $\\

\item Computing goodness values: (only nodes in trees need goodness values)  \\
If $i\/$ is a cutset node, then 
For each neighbor $j$,  \\
\hsp $G^0_i=X_i \theta_i$,\\
\hsp $G^{j1}_i=X_i (\theta_i  + w_{ij})$
\hsp  ($G^0_i,G^{j1}_i$ are goodness values for neighbor $j$ ). \\
else (a regular tree node),\\
\hsp $G^0_i=max\{\sum_{j\in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} G_j^1 P^i_j+\theta_i \}$;\\
\hsp $G^1_i=max\{\sum_{j \in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} (G_j^1 P^i_j+w_{i,j}P^j_i)
+\theta_i \};$ 

\end{enumerate}
}}

\caption{Algorithm activate-with-cutset}
\label{alg4}
\end{figure}
%\noi \fbox{ \parbox[b]{6.2in} {
%{\bf Algorithm activate-with-cutset: 
%Optimizing with cycle-cutset when values are not given,\\
%Assumption: The cutset nodes are given a priori.
%% Assumption2:All cycles are eliminated as a result of the cutset.\\
%(unit $i$):
%}
%
%\begin{enumerate}
%\item As in activate-with-cutset-values.
%%Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$; 
%\item As in activate-with-cutset-values.
%%\item Tree directing:\\
%%	If $i\/$ is a cutset node, then  for every neighbor ($j$),
%%if $P_j^i=0$, then $P^j_i=1\/$;\\
%%\hsp (neighbors become parents unless they already point to it) \\ 
%%else (regular tree node),
%%if there exists a single neighbor $k\/$, such that $P^i_k=0$, \\
%%\hsp then $P^k_i=1\/$ and for all other neighbors $j\/$, $P_i^j=0$; \\
%%else (root or non-tree node), for all neighbors $P^j_i=0$;
%
%\item Assigning activation values:\\
%If all neighbors of $i\/$ point to it except maybe one (i.e., it is
%part of a tree) then,\\
%\hsp $ X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j ((G^1_j - G^0_j)P^i_j+ w_{i,j}X_j P^j_i)\geq 
%-\theta_i$}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. $\\
%else (a cutset node or a node that is not yet part of any tree), 
%Compute Hopfield:\\
%\hsp $ X_i =\left\{ \begin{array}{ll}
%	1 & \mbox{ if  $\sum_j  w_{i,j}X_j\geq -\theta_i$}\\
%	0 & \mbox{ otherwise }
%	\end{array}
%	\right. $\\
%
%\item As in activate-with-cutset-values.
%%\item Computing goodness values:  \\
%%If $i\/$ is a cutset node, then 
%%for each neighbor $j$,  \\
%%\hsp $G^0_i=X_i(\theta_i)$,\\
%%\hsp $G^{j1}_i=X_i(\theta_i ) + w_{ij}$
%%\hsp  ($G^0_i,G^{j1}_i$ are goodness values for neighbor $j$ ). \\
%%else (a regular tree node),\\
%%\hsp $G^0_i=max\{\sum_{j\in children(i)} G^0_j P^i_j, 
%%\sum_{j \in children(i)} G_j^1 P^i_j+\theta_i \}$;\\
%%\hsp $G^1_i=max\{\sum_{j \in children(i)} G^0_j P^i_j, 
%%\sum_{j \in children(i)} (G_j^1 P^i_j+w_{i,j}P^j_i)
%%+\theta_i \};$ 
%
%\end{enumerate}
%}}

%The new activate-with-cutset differs from the previous one only in step 3.
%As before, the network computes a minimum of the energy, conditioned on
%the values of the cutset variables. This time, however, the cutset values
%%are not given a priori and instead, 
%are computed constantly using a
%standard local algorithm such as Hopfield. In addition, nodes that are 
%not yet  part of a tree  or nodes that are still part of a cycle (if the cutset
%is not perfect),
%use  Hopfield as well.

Note that the goodness value computation of cutset nodes (step 4)
is not performing the maximization operation over
the two possible activation values of the cutset variables
since the activation value of cutset nodes
is fixed as far as the tree algorithm is concerned.
Intuitively, if performed sequentially the algorithm would iterate
between the following two steps: 1. finding a local maximum using
Hopfield activation function for the cutset variables;
2. finding a global maximum conditioned on 
the cutset values determined in the previous step via 
the tree algorithm.
In the connectionist framework these two steps are not synchronized.
Nevertheless, the algorithm will converge to
%Consequently, the algorithm converge to a  solution that
%is both 
a local maxima relative to Hopfield algorithm
as well as a conditional global maxima relative to the cutset variables.
Convergence follows from the fact that the tree directing algorithm
is guaranteed to converge  given fixed cutset variables.
Once it does, 
a node flips its value either as a result of a Hopfield step 
or in order to optimize a tree.  In both steps the energy does 
not increase.\footnote{
Fluctuations that  temporarily increase the energy may occur from time to time
before the tree propagation has completely stabilized. For example, a node may
use the goodness values of its children before their goodness values are ready
(but after they point to the node).}

\begin{exampl}
The following example demonstrates how the 
algorithm finds a  better minimum than what is found by the standard Hopfield 
algorithm 
when there are cycles.
Consider the energy function: $energy= 50AB-200BC-100AC-3AD-3DE-3AE+0.1A+0.1B+0.1C
+4E+4D$. The associated network consists of two cycles: $A,B,C\/$ and
$A,D,E$. If we select node $A\/$ as a cutset node, the network would then be
cut into two acyclic (tree-like) subnetworks. Assume that the network 
starts with a setting of zeros ($A,B,C,D,E=0$). This is a local 
minimum (energy = 0) 
of the Hopfield algorithm. Our activate-with-cutset algorithm breaks out of
this local minimum by optimizing the acyclic subnetwork $A,B,C\/$ conditioned on
 $A=0$.
The result of the optimization is the assignment $A=0,B=1,C=1,D=0, E=0\/$ with 
$energy =-199.7$. It is not a stable state because $A\/$ obtains an excitatory
sum of inputs (50) and therefore flips its value to $A=1\/$ using its Hopfield
activation algorithm. The new state $A,B,C=1,D,E=0\/$ is  also a local
minimum of the Hopfield paradigm ($energy=-249.7)$. However, since nodes 
$A,D,E\/$ form a tree, the activate-with-cutset algorithm also manages to break 
out of this local minimum. It finds a global solution conditioned on $A=1\/$
which happens to be the global minimum $A,B,C,D,E=1\/$ with 
$energy =-250.97$. The new algorithm was capable of finding 
the only global minimum
of the energy function and managed to escape two of the local minima 
that  trapped the Hopfield algorithm. 
\end{exampl}


It is easy to see that algorithm {\em activate-with-cutset} improves
on {\em activate} in the following sense:

\begin{theo}
If $a_1$ is a local minimum generated by {\em activate}
and $a_2$ is a local minimum generated by 
{\em activate-with-cutset}, then if
$a_1$ and $a_2$ have the same activation value on all non-tree nodes 
then, $G(a_2) \leq G(a_1)$.
\end{theo}

\subsection{Local search with changing cutset variables}


We can imagine a further extension of the cutset scheme idea that will
improve the resulting energy level further
by conditioning and optimizing
relative to many cutsets. 
In a sequential implementation the algorithm will move 
>from one cutset to the next,
until there is no improvement. This process is guaranteed to
monotonically reduce the energy.
It is unclear however how this tour among cutsets
can be implemented in a connectionist environment.
It is not clear even how to identify one cutset distributedly.
Since finding a minimal cycle-cutset is NP-complete
a distributed algorithm
for the problem is unlikely to exist.
Nevertheless, there
could be many brute-force distributed algorithms
that may find a good cutset in practice.
Alternatively, cutset nodes may be selected
by a process that randomly designates a node to be
a cutset node.

In the following paragraphs we outline some ideas for
a uniform connectionist algorithm that  allows 
exploration of the cutset space.
We propose the use of a random function to control the identity
of the cutset nodes.
The random process by which a node becomes a cutset node
or switch from a cutset node to a
regular node
may be
governed by a random heuristic function $f()$.
%In algorithm activate-with-random-cutset %does not assume known cutset nodes.
A non-tree node may turn into a cutset node  with
probability $P=f()$.
A cutset node may turn into
a non-cutset node if it becomes part of a tree or by the random process
with probability $P=g()$. %For the sake of simplicity we will
%assume here that $g()=1-f()$.  
The function $f()\/$ should be designed in a way
that it will assign high 
probabilities to nodes with potential to become ``good'' cutset nodes. 
The probability of de-selecting a cutset node may be 
defined as $g()= 1-f()\/$.


%$g()\/$ is defined as $1-f()\/$ for simplicity; i.e., for the sake of 
%expressing both probabilities using one heuristics. In practice, two
%independent functions may be used for selection and de-selection.}

Algorithm {\em activate-with-cutset} can be augmented with 
a cutset selection function that will be running in parallel
with the three procedures (tree-directing, assigning activation 
values and goodness computing). 
Thus, we may add a forth procedure that selects (or de-selects) the node
as a cutset node with probability $P= f()$.
Note that the randomly selected cutset is not 
perfect and that there might be too many  or too few cutset nodes.  
%Fewer
%cutset nodes will leave some cycles around, while too many cutset nodes may cause
%the solution to be conditioned on more nodes than necessary. 
%Cutset nodes that haven't been identified yet as parts of trees and nodes that
%are parts of cycles
% compute the standard
%Hopfield activation function.\footnote{Boltzmann, (with 
%simulated annealing) or Mean-field (deterministic approximation to simulated
%annealing) activation functions may be used instead of Hopfield for the cutset 
%nodes, thus increasing the chances of finding  the ``right'' value.}
%Redundant cutset nodes %that are not needed,
%will be de-selected over time, and  become parts of trees.

%The augmented algorithm would need to distinguish between three types of nodes:
%1) Nodes that are currently selected as cutset nodes;
% 2) nodes that are parts of  trees (relative to the current
%cutset variables) and 3) nodes that are neither cutset nodes 
%nor are they parts of trees. %(have  potential to become cutset nodes or to 
%become part of a tree).
%A node marks itself as a cutset node by setting 
%($CUTSET_i$$=1$). 
%A node is considered to be part of a tree if all its neighbors
%(except maybe one) point to it.  The rest of the nodes  may
%become cutset nodes using the randomization. 
%Cutset nodes may be de-selected and 
%transformed back into non-cutset nodes. 
%The dynamic and randomized
%selection/de-selection process allows 
%the search for best cutset nodes to continue with non-increasing 
%energy.
As long as there are cycles, cutset nodes should be selected. At the same time,
nodes functioning too long as cutset nodes should be de-selected thus reducing
the chances for redundant cutset nodes while continuously exploring  the 
space of  possible cutsets.

One way to implement a heuristic  function $f\/$  is to base it 
on the following ideas: 
%probability  of a node based on  the following guidelines: %\footnote{ 
%Obviously,
%one can use different functions ($f1,f2$) for the 
%selection/de-selection. The
%choice of one function was done for simplicity.}
%\begin{enumerate}
%\item 
1. Increase probability to non-tree nodes that have not been cutset nodes for
 a long time. 
% This will cause   a node that has been
%a cutset node long enough to have higher probability to become a non
%cutset node.  %Similarly, a node that has only recently been selected should 
%stay in the cutset for a while (to give chances for the propagation to 
%occur).
%\item 
2. Increase probability to nodes that have not flipped their value for a 
long time. %The more time has passed, the more chances a node has to become
%a good cutset candidate. %Also, more time gives more opportunities for
%the node to become part of a tree, thus avoiding premature decision. 
%\item 
3. Increase the probability to nodes  with
 high connectivity. %the more connections a
%node has, the more  effective cutset node it may become (since it
%may cut several cycles at once).
%\item Increase probability to nodes with larger absolute value of  weighted
%inputs ($net_i=\sum_j w_{ij}X_j + \theta_i\/$)
% i.e., get more support from their 
%neighbors for their current activation value. The larger the support, the 
%better are the chances that the value will not  be flipped later, and therefore
%is likely to become a good cutset node.
%\end{enumerate}

Note that a de-selected cutset node may cause a chain reaction of undirecting nodes.
Nodes that lost their tree-pointers become not-part-of-tree and thus have
a potential to become cutset nodes. 
%The energy of the network is not affected
%by the de-selection process. 
The network may 
continue the tour in the cutset space indefinitely and 
may
never become static. 
The selection-de-selection process may never converge. %We are 
%guaranteed, however,  
Nevertheless, if a function $f$ is designed to
allow enough time for convergence in between
cutset changes than  during the whole
process, the energy
tends to decrease. Temporary fluctuations may sometimes cause an energy
increase when a node relies on its not yet stable neighbors.\footnote{
For example, temporarily relying on old goodness values of a de-selected node.}
We conjecture that such a heuristic function $f\/$ can 
be constructed so as to 
allow
trees to be stabilized before they are
distroyed by de-selection.
% never decreases, thus, an energy local maximum
%is guaranteed.
Formalizing the algorithm's properties and further investigation 
and experimentation 
are left for future research.

\shrink{
\begin{figure}
\noi  \fbox{ \parbox[b]{5.9in} {
{\bf Algorithm activate-with-random-cutset: \\
Optimizing with cycle-cutset that is selected randomly with heuristics.
%(unit $i$):
}

\begin{enumerate}
\item Initialization: If first time, then $(\forall j)\/$ $P^j_i=0$;
 $CUTSET_i=0$;
\item Cutset setting:\\
If all its neighbors except maybe one, point to it (part of a tree), then\\
\hsp $CUTSET_i=0;$ \\
else (not part of tree), if $CUTSET_i=0 \/$
(not yet a cutset node), then \\
%\hsp (decide whether to  make it a cutset node)\\
 \hsp with probability $P=f()\/$
make $i\/$ a cutset node: $CUTSET_i=1$.\\
else (a previously selected cutset node)
\\ \hsp with probability $P=1-f()\/$ de-select node $i\/$ \\
\hsp and make it  a non-cutset node: $CUTSET_i=0$.
\item Tree directing:\\
If $CUTSET_i=1\/$ (a cutset node), then  
 for every neighbor ($j$),\\
\hsp  if $p_j^i=0\/$ then, $P^j_i=1\/$; \\ 
else (not a cutset node)
 if there exists a single neighbor $k\/$, such that $P_k^i=0\/$ then,\\
\hsp \hsp (part of a tree but not a root)
 $P^k_i=1\/$; for all other neighbors $j\/$, $P_i^j=0$; \\
else, for all neighbors $P^j_i=0$;

\item Assigning activation values:\\
If all neighbors of $i\/$ point to it except maybe one then (part of a tree),\\
\hsp $ X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j ((G^1_j - G^0_j)P^i_j+ w_{i,j}X_j P^j_i)\geq 
-\theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $\\
else (a cutset node or a node that is not part of any tree), 
Compute Hopfield:\\
\hsp $ X_i =\left\{ \begin{array}{ll}
	1 & \mbox{ if  $\sum_j  w_{i,j}X_j \geq -\theta_i$}\\
	0 & \mbox{ otherwise }
	\end{array}
	\right. $

\item Computing goodness values: (only nodes in trees need goodness values) \\
If $i\/$ is a cutset node, then 
for each neighbor $j$,  \\
\hsp $G^0_i=X_i(\theta_i)$,\\
\hsp $G^{j1}_i=X_i(\theta_i ) + w_{ij}$\\
else (a regular node),\\
\hsp $G^0_i=max\{\sum_{j\in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} G_j^1 P^i_j+\theta_i \}$;\\
\hsp $G^1_i=max\{\sum_{j \in neighbors(i)} G^0_j P^i_j, 
\sum_{j \in neighbors(i)} (G_j^1 P^i_j+w_{i,j}P^j_i)
+\theta_i \};$ 
\end{enumerate}
}}

\caption{Algorithm activate-with-random-cutset}
\label{alg5}
\end{figure}
}

\section{Conclusions}

\shrink{
We have shown a uniform self-stabilizing connectionist activation 
function that 
is guaranteed to find a global minimum of acyclic symmetric networks
in linear time under a realistically weakened distributed scheduler.
The algorithm optimizes tree-like
subnetworks within general  networks but is not self-stabilizing
when used in cyclic topologies. 
We extending the algorithm to general
networks using cycle-cutset nodes that
force a network to become a collection of tree-like subnetworks.
}

The main contributions of the paper are:
\begin{enumerate}
\item We provide a connectionist activation function (algorithm 
activate, Figure \ref{alg2}), 
that is self-stabilizing and is guaranteed to converge to a global
minima in linear time for tree-like networks. On general networks 
the algorithm will generate a global minima on all tree subnetworks
and on the rest of the network it will coincide with regular
local gradient activation functions (e.g., Hopfield). 
%In contrast, regular hopfield like energy function
%converge to a local minima only, and it can take exponential
%time in the worst-case (although it is quite efficient in practice).
The algorithm dominates an arbitrary local
search connectionist algorithm in the following sense: 
If $a_1$ is a local minimum generated by {\em activate} and $a_2$ is a
local minimum generated by a corresponding local-search
method, then if $a_1$ and $a_2$ have the same activation values on 
all non-tree nodes (if it is a tree then the set is empty), 
then the energy of $a_1$ is 
smaller or equal to the energy of $a_2$.

\item We showed that {\em activate} can be further extended 
using the cycle-cutset idea.
The extended algorithm called {\em activate-with-cutset} (Figure
\ref{alg4}) is guaranteed
to converge and generate solutions that are
at least as good and normally better than algorithm
{\em activate}. 
The algorithm converges to conditional global minima relative
to the values of the cutset variables. 
If $a_1$ is a local minima generated by {\em activate} and $a_2$ is the
local minima generated by {\em activate-with-cutset}
then if $a_1$ and $a_2$ have the same activation values on all the 
cutset variables (if it is a tree, the cutset is empty)
than the energy of $a_2$ is 
smaller or equal to the energy of $a_1$.
Therefore {\em activate-with-cutset} is better than {\em activate}
which in turn is better than a  regular energy-minimization
connectionist algorithm in the above sense.
A third variation of the algorithm is sketched for future
investigation. The idea is that the cutset nodes are randomly
and continuously selected, thus allowing exploration of the cutset
space.

\item We stated two negative results: 1) Under a pure distributed 
scheduler 
no {\em uniform} algorithm exists 
to globally optimize  even simple chain-like networks.
2) No uniform algorithm exists to globally 
optimize simple cyclic networks (rings)
even under a central scheduler. 
We conjecture that these negative results are not of significant practical
importance since in  realistic schedulers the probability of having
infinite  pathological scheduling scenarios approaches zero. We showed that
our algorithm converges  correctly (on tree-like subnetworks)
  when the demand for pure distributed
schedulers is somewhat relaxed; i.e., 
adding either fair exclusion, almost uniformity or 
cycles. 
Similarly,  self-stabilization is obtained in acyclic networks or when
the requirement for a uniform algorithm is relaxed (almost uniformity).
\end{enumerate}

The negative results apply to connectionist algorithms as well as to parallel
versions of local repair search techniques.
The positive results suggest improvements both to connectionist activation 
functions and to local repair techniques. 
%They appear to be optimal
%when uniformity and realistic parallel scheduling are required.
%Clearly, our improved algorithm will work better than the 
%standard methods
%in networks that have large tree-like subnetworks
%or have only a few cycles.

We conclude with a discussion of two domains that are 
likely to produce sparse, near-tree  networks and thus benefit
>from the algorithms we presented: inheritance networks
and diagnosis.
% Assumptions and conditions are mentioned that  cause the 
%relevant networks to be mostly cycle free.
         
%\subsection{Inheritance Networks}
Inheritance is a straightforward example of an
application where translations of symbolic rules into
energy terms form networks that are mostly cycle free.
Each arc of an inheritance network, such as $A\/$ ISA $B\/$ or $A\/$ HAS
$B\/$ is modeled
by the energy term $A-AB$.  The connectionist network that represents
the complete inheritance graph is obtained by summing the energy 
terms that correspond to all the ISA and HAS relationships in the graph.
Nonmonotonicity can be expressed if we add
penalties to arcs and use the semantics discussed by Pinkas
(1991b, 1995).
%\cite{PinkasAIJ,PinkasIJCAI}.
Nonmonotonic relationships
may cause cycles both in the inheritance graph and the 
connectionist network
(e.g. Penguin ISA Bird; Bird ISA FlyingAnimal; Penguin ISA 
not(FlyingAnimal)). 
Multiple inheritance may cause cycles as well,
even when the rules are monotonic
(e.g., Dolphin ISA Fish; Dolphin ISA Mammal; Fish ISA Animal; Mammal ISA 
Animal).
Arbitrary constraints on the nodes of the graph may be introduced in 
this model.
Constraints may be represented as proposition logic formulas and then 
translated into energy terms \cite{PinkasNC} potentially causing
cycles.
In a ``pure''  inheritance network that has no multiple inherited nodes and
no nonmonotonic relationships, the 
network
is cycle-free 
and can be processed efficiently by various algorithms.
  If we allow multiple inheritance, nonmonotonicity,
or arbitrary propositional constraints, we may introduce
cycles into the network that are generated.
Nevertheless, it is 
reasonable to assume that in large practical inheritance domains
%and taxonometric domains, the majority of the network is based on
% pure inheritance. 
cycles (multiple inheritance, nonmonotonicity and
arbitrary constraints) are only scarcely introduced 
and the few that exist
may be handled by our extension using the cycle-cutset idea.
%\subsection{Diagnosis}

Another potential application that will generate mostly  cycle-free
subnetworks is diagnosis.
% \subsubsection{Formalism}
Here is a possible formulation of a diagnosis framework.
Let $X_1,X_2,...X_n\/$ be True(1)/false(0) propositions that 
represent symptoms and 
hypotheses. 
 In a diagnosis application we may have diagnosis rules 
of the form: 
%of rules (formal semantics is discussed later):
%\begin{itemize}
%\item {
 $(\alpha _1 X1, \alpha_2 X_2,...,\alpha_m X_m\rightarrow
\beta X$).
These rules announce that   the symptoms $X_1,...,X_m \/$
	with importance factors $\alpha_1,...,\alpha_m$, suggest the 
hypothesis $X\/$ with sensitivity $\beta$.
A subset  of the symptoms  may be enough to suggest the hypothesis if the
sum of the importance factors of the active symptoms is larger than the
sensitivity $\beta$.
 Intuitively, the larger the sum of the factors, the larger
the support for the hypothesis.
%In addition to its role in 
%By determining the support needed, 
%the sensitivity $\beta\/$, encourages parsimonious explanations of the 
%symptoms.
The corresponding energy function  for a diagnosis rule
is  $\sum_i^m -\alpha_i X_i X+\sum_i^m 
\alpha_i X_i + \beta X$.
%}
In addition, arbitrary propositional constraints may also be added, like
%\item { $(\alpha \pphi$) where $\pphi\/$ is a constraint expressed as a
%well formed propositional formula, and $\alpha\/$ is  the importance of the
%constraint. 
%Examples of such constraints are:
%\begin{itemize}
%\item
 $(X \rightarrow X_i$) i.e., if the hypothesis $X\/$ 
holds, so does the symptom $X_i$.
%\item 
{ $(X_1  \rightarrow (\neg X_2 \wedge \neg X_3) \wedge
 X_2  \rightarrow (\neg X_1 \wedge \neg X_3) \wedge
X_3  \rightarrow (\neg X_1 \wedge \neg X_2)$) i.e., only one of the propositions
$X_1,X_2,X_3\/$ can be true (mutual exclusion). }
%\end{itemize}
Any propositional logic formula is  allowed and nonmonotonicity may be expressed 
using  conflicting constraints (augmented with importance factors). 
Quadratic energy functions may be generated from arbitrary propositional 
constraints by introducing hidden variables \cite{PinkasNC}. 

%Note that any variable $X\/$ may be used as a symptom in some rules and as
%a hypothesis in  other rules. This observation will be used later in our
%discussion of independence.
%
%\subsubsection{Semantics}
%We can use a formal logic and semantics called penalty logic \cite{PinkasAIJ},
%\cite{PinkasIJCAI} that is based on ranked models \cite{Shoham},
%\cite{Pearl}, \cite{Lehman}. In this semantics, models are ranked according to 
%a score computed by summing the penalties associated with violating the rules.
%Propositions that are held in all the models of minimal penalty are
%concluded.
%
%For a diagnosis rule $(\alpha_1 X_1,...,\alpha_k X_k \rightarrow \beta X$), 
%a model is penalized by adding $(\sum_{j=1}^k \alpha_{i_j}$) if 
%the symptoms $X_{i_1},...,X_{i_k}\/$ are active and the hypothesis $X\/$ 
%inactive. In addition, to encourage parsimonious explanations, $\beta\/$ is
%alway added when the corresponding hypothesis $(X$) is activated.
%For violating a constraint $\alpha \pphi\/$, a model is penalized by adding
%an extra $\alpha$. 

%A set of rules such as the above, can be translated into an energy function 
%and be  implemented as a connectionist network. Penalty logic, its semantics
%and the algorithms for translating formulas into energy functions are
%discussed in \cite{PinkasAIJ}, \cite{PinkasIJCAI}.

%\subsubsection{Cycles, Trees and Independence Assumption}

Sparseness of such 
networks 
emerges as a result
of assuming conditional independency of symptoms relative to 
their hypothesis. %The symptoms of 
%a hypothesis
%$X\/$ are {\em independent\/} of each other,
%when all
%its
%direct symptoms (neighbors)  (of $X$), given the a value for $X$,
%are not affected by the value of any other direct symptom of $X$.
Independency assumptions of this kind (that makes computation tractable)
 are quite common in actual implementations of Bayes networks, influence 
diagrams \cite{PearlBook}, %\cite{BayesDiagnosis} %causal networks  
%\cite{CausalNet}, 
and certainty propagation of rule-based expert systems \cite{Mycin}.
%In general networks, where arbitrary constraints appear together with
%diagnosis rules, the notion of symptoms becomes misleading.  In this case,
%we will require that all nodes that are neighbors of any $X\/$ will be
%independent of each other, given the value of $X$.}
When  our knowledge base consists  only of diagnosis rules (and maybe the 
corresponding $X \rightarrow X_i\/$ rules) and the symptoms 
are all independent of each other, there are no cycles in the network, and
the tree algorithm converges to a global maximum in linear time.
When we add 
dependent
symptoms which affect a hypothesis through more than one
 path; e.g., $X_1 \rightarrow X\/$, and $X_1 \rightarrow X_2 \rightarrow ...
\rightarrow X$, or when we start adding arbitrary constraints, 
cycles are added. When dependent symptoms and arbitrary constraints are only
scarcely added, the network generated will most likely lend itself efficiently
to the activate-with-cutset algorithm.

Abandonment of efficient algorithms exists for both 
inheritance and diagnosis in 
their tractable forms.  Our algorithm offers  
both to solve efficiently 
tractable versions  of the problem and to
 approximate intractable versions of it
 in massively parallel, simple to implement methods. 
The efficiency
of the suggested process depends on the ``closeness'' of the problem to an
ideal, tractable form.




%\appendix
\section*{A. Appendix}
\noindent
{\em Proof sketch\/} of theorem \ref{bigtheo}:
The second and third phases of the algorithm are  adaptations of
an existing dynamic programming algorithm \cite{Bertele}, and  their correctness
is therefore  not proved here.
The self-stabilization of these steps is  obvious
because no variables are  initialized.  The proof is therefore 
% concentrates on
dependent on the convergence of
the tree directing phase.

Let us first assume that the scheduler is  distributed  with fair
exclusion and that the network is a tree. 
% We now prove 
The first part of the theorem
is proved by points 1-4.
We want to show that the 
tree-directing
algorithm  converges, that it is self-stabilizing and that 
the final stable result is that the pointers $P_i^j\/$ represent a tree. 
Points 5 and 6 prove parts 2 and 3 of the theorem.
A node  is called {\em legal\/} if it is either  a root (i.e., all its neighbors are 
legal, point to it and it doesn't point to any of them), or an intermediate
node (i.e., it points to one of the neighbors and  the rest of its neighbors
are all legal and point  back).
A node is called  a {\em candidate} if it is an illegal node and 
has all its neighbors but one pointing to it.
We would like to show that:


\begin{enumerate}
\item The property of being  legal is stable; i.e., once a node becomes legal it
will stay legal.
\item A state where the number of illegal nodes is $k>0\/$, leads to a state
where the  number of illegal nodes is less than $k$; i.e., the number of
illegal nodes decreases and  eventually all nodes turn legal.
\item If all the nodes are legal then the graph is marked as a tree.
\item The algorithm is self-stabilizing for trees.
\item
 The algorithm converges even if the graph has cycles (part 2 of the theorem).
\item The algorithm is self-stabilizing in arbitrary networks if an almost
uniform version is used, even under a  distributed scheduler (part 3  of
the theorem).
\end{enumerate}
We will now prove each of the above points.
\begin{enumerate}
\item Show that a legal state is stable.
 Assume a legal  node $i\/$ becomes  illegal. It is either a root node
and  one of its children became illegal, or an intermediate node whose
one of its children became illegal (it cannot be that its parent suddenly
points to $i\/$ or that one of the children stopped pointing and still
is legal). Therefore, there must be a chain of $i_1,i_2,..., i_k\/$ of
nodes that became illegal.
Since there are no cycles, there must be
a leaf that was legal and turned illegal. This cannot occur since
a leaf does not have children; leading to a contradiction. 
 \item Show that if there are illegal nodes, their number is reduced.
To prove this claim we need three steps:
\shrink{
\begin{enumerate}
\item Eventually, a state is
 reached such that
if there is at least one illegal node then there is 
also a candidate node among the illegal nodes.
\item This candidacy is stable, unless the nodes turn legal.
\item eventually,
the candidate will become legal (therefore the number of illegal nodes
is reduced).
\end{enumerate}
}
\begin{enumerate}
\item Show that eventually, if there are illegals, then there are also candidates.\\
Because of the fair 
exclusion,
eventually a state is  reached
 where each node has been executed at least once. Assume that at least one
node is illegal, and  all the illegal nodes are not candidates. 
If a node is illegal
and not a candidate,  then either it is a root-type  (all point to it) but at least
one of
its children is illegal, or there are at least two of its neighbors that
are illegal. Suppose there are no  root-type illegal nodes. Then all
illegal nodes have at least two illegal neighbors. Therefore there must be 
a cycle that connects illegal nodes (contradiction).  Therefore, one of the 
illegal nodes must be root-type. Suppose
$i\/$ is  a root-type illegal node.  It must have a neighbor $j\/$ which
is illegal. Consider the subtree of $j\/$ 
that does not include $i\/$: it must contain illegal nodes. 
If there are no root-type illegal nodes we get a contradiction again. 
However, if there is a root-type
node, we eliminate it and look at the  subtree of some illegal 
$j'\/$ that does not include $j$.
Eventually, since the network is finite, we obtain a subtree with no
root-like illegal nodes but which includes other illegal nodes. This leads to
a contradiction. The conclusion is
that there must be candidates if there are illegal nodes.
\item Show that a  candidate is stable unless it becomes legal.
\\
If a  node $i\/$ is a candidate, all its legal children remain legal.  There
are three types of candidate nodes (node $j\/$ is an illegal neighbor of
$i$):
\begin{enumerate}
\item node $j\/$ points to $i\/$; 
\item the pointer goes in both
directions; 
\item there is no pointer from $i\/$ to $j\/$ or vice-versa. 
\end{enumerate}
All possible changes in the pointers $P_i^j\/$ or $P_j^i\/$  will cause $i\/$
to remain a candidate or to turn legal (the rest of the pointers will not
be changed).
%\end{enumerate}
\item  Show that every candidate node will eventually turn legal: Assume $j\/$
is the illegal neighbor of the candidate $i\/$. In the next execution
of $i\/$ without $j\/$ (fair exclusion), if $P_j^i=0\/$ then $i\/$ becomes legal by pointing
to $j$; otherwise, $i\/$ becomes a root-type candidate (all its neighbors
point to it) but $j\/$ is illegal. We will prove now that if an illegal node
$j\/$ points to $i\/$ then eventually a state is reached where either
$j\/$ is legal or $P_j^i=0\/$, and that this proposition is stable once 
it holds.
If this statement is true then when $i\/$ is executed eventually, if $j\/$
is legal then all of $i's\/$ neighbors are legal and therefore $i\/$ turns
legal. If $j\/$ is illegal then $P_j^i=0\/$, and $i\/$ will
point to it ($P_i^j=1\/$) making itself legal.

We next prove that if $j\/$ is an illegal node pointing to $i\/$ then there will
be a state where either $j\/$ is legal or $P_j^i=0\/$, and this
state is stable.
We prove it by induction on the size of the subtree of $j\/$ 
that does not include $i\/$.\\
Base step: If $j\/$ is a leaf and $j\/$ points to $i\/$ then if at the time $j\/$
is executed (without $i$) 
 $P_i^j=0\/$, then node $j\/$ points to $i\/$ and becomes legal; otherwise,
$j\/$ updates $P_j^i=0$. This status is stable because the legal state
is stable
and since a leaf will point to a node only if it turns legal.\\
Induction step: Assume hypothesis is True for trees of size less than $n$.
Suppose $j\/$ is the illegal neighbor if $i\/$. Node $j\/$ points to $i\/$
and it has $j_1,...,j_k\/$ other neighbors. Because we assume that all
nodes were executed at least one time, since $j\/$ points to $i\/$ we
assume that at the last execution of $j\/$ all the other neighbors $j_1,...
,j_k\/$ pointed to $j\/$. The subtrees rooted by $j_l\/$ (not including $j\/$)
are of size less than $n\/$ and therefore by the hypothesis there will be a state
where all the nodes $j_1,...,j_k\/$  are either legal or $P_{j_l}^j=0$.
This state is stable, so when eventually $j\/$ is executed, it will
either point to $i\/$ turning legal (if all $j_1,...,j_k\/$ are 
pointing to it), or it will make $P_j^i=0\/$ (if some of its neighbors
do not
point to it). Since the status of $j_1,...,j_k\/$
is stable at that point, whenever $j\/$ is
executed it will either become legal or its pointers become zero.
\end{enumerate}
\item Show that if all the nodes are legal then the graph is marked as a tree:
If a node is legal, then all its children are legal and point to it. 
Therefore each node represents a subtree (if not a leaf) and has one parent at
the most. To show that there is only one root we make the following
argument.  If several roots exist, then because of connectivity, 
there is one node that is shared between at least two
subtrees and therefore has two parents (contradiction).
\item The algorithm is self-stabilizing for cycle-free networks since no
initialization is needed (in the proof 
we haven't use  the first initialization step; i.e.,  $P_i^j=0$).
In the case where no cycles exist we do not need this step. The pointers
can get any initial values and the algorithm still converges.
\item The algorithm (with $P_i^j=0 \/$ initialization) 
converges even if the graph has cycles. Since all
the nodes start with zero pointers, 
a (pseudo) root of a tree-like subnetwork will never point toward
any of its neighbors (since it is part of a cycle and all of its neighbors
but one  must be legal).
\item Show that the algorithm is self-stabilizing in arbitrary networks if an
 almost
uniform version is used, even under a distributed scheduler. We need to show
that a candidate will eventually turn legal even if its neighbors are
executed in the same time. \\
Suppose node $i\/$ is a candidate and node $j\/$ is
its illegal neighbor:
\begin{enumerate}
\item If $j\/$ is a root, then it will never point to $i\/$,
and therefore $i\/$ will eventually turn legal by pointing to $j$.
\item  If $i\/$ is
the root, then $P_i^j=0\/$, and if $j\/$ becomes legal it will point to $i\/$
making $i\/$ legal. Node $j\/$ will turn eventually legal using the following
induction (on the size of the subtree of $j$):\\
Hypothesis: In a subtree without a node that acts as a root, all illegal
nodes will eventually  turn legal.\\
Base step: If $j\/$ is a leaf, it will point eventually to its neighbor $i\/$
which in its turn will make $j\/$ legal by $P_i^j=0$.\\
Induction step: If $j_1,...,j_k\/$ are other neighbors of $j\/$, then they
will eventually turn legal (induction hypothesis) while pointing to $j\/$. Eventually $j\/$ is
executed and also turns legal.
\item Suppose neither $i\/$ nor $j\/$ are roots, but one of them 
is not part of a cycle (and therefore is part of a subtree that does
not include a node marked as a root). Using the above induction, all the
nodes in the subtree will eventually turn legal. As a result either $i\/$
or $j\/$ eventually turns legal, and therefore $i\/$ will eventually
  turn legal as well.
\end{enumerate} 
\end{enumerate}
$\Box$ 
%\input{/home/cics/pinkas/bibl/bibl6.tex}

\section{Acknowledgement}
This work was supported in part by NSF grant IRI-9157636, by Air 
Force Office of Scientific Research, AFOSR 900136,
by Toshiba of America and by a Xerox grant. 
We would also like to thank  Kalev Kask for commenting
on the latest version of this manuscript, Kaoru Mulvihill for
drawing the figures, for Lynn Haris for editing and 
the anonymous reviewers 
who helped improve the final version of this paper. 
A shorter version of this paper appears earlier
\cite{Pinkasj}.
\shrink{

\bibliography{jair}
\bibliographystyle{theapa}
\end{document}

\begin{thebibliography}{WmWm99}

\bibitem[Ballard et al. 1986]{Ballarda} D.~H.~Ballard, P.~C.~Gardner, 
M.~A.~Srinivas, ``Graph problems and connectionist architectures,'' University
of Rochester, Technical Report 167, 1986.
 \bibitem[Becker \& Geiger, 1994]{geiger} A. Becker and D. Geiger,
``Approximation algorithms for loop cutset problems''
{\em Proceedings of the 10th conference on  Uncertainty in Artificial 
Intelligence (UAI-94)}, pp. 60--68, Seattle Washington, August, 1994.

\bibitem [Bertel\'{e} \& Brioschi 1972]{Bertele} U.~Bertel\'{e}, F.~Brioschi, 
``Nonserial dynamic programming,'' Academic Press, 1972.
\bibitem [Brandt et al. 1988]{Brandt} R.~D.~Brandt, Y.~Wang, A.~J.~Laub,
S.~K.~Mitra, ``Alternative networks for solving the traveling salesman 
problem and the list-matching problem,''
in {\em IEEE International Conference on Neural Networks, } Vol 2,pp.~333--340,
1988.
 \bibitem[Collin et al. 1991]{Collin}
Z. Collin, R. Dechter, S. Katz, 
``On the feasibility of distributed
constraint satisfaction,''   
{\em  Proceedings of IJCAI}, Sydney, 1991.
%hhhh the next citation does not appear in the tex:
%\bibitem[Dechter, Pearl 88]{Dechter}R. Dechter, J. 
%Pearl, ``Network-based heuristics
%for constraint-satisfaction problems,'' {\em Artificial Intelligence 34},  
%pp.~1--38, 1988.

\bibitem[Dechter, 1990a]{DechterEnhancement}
Dechter, R., ``Enhancement schemes for constraint
processing: Backjumping, learning and cutset
decomposition,''  {\it Artificial Intelligence}, 
{\it Vol. 41(3)}, pp. 273--312, January 1990.

\bibitem[Dechter, 1990b]{reference-survey}
Dechter, R., ``Constraint networks.'' In {\it Encyclopedia 
of Artificial Intelligence}, 2nd ed., John Wiley \& Sons, 
Inc., pp 276--285, 1992.

\bibitem[Dechter \& Pearl, 1990]{Dechterc}R.~Dechter, A.~Dechter, J.~Pearl,
``Optimization in constraint networks,''  in R.M.~Oliver, J.Q.~Smith,
{ Influence diagrams, belief nets and decision analysis,} John Wiley and Sons,
1990.
\bibitem[Dijkstra, 1974]{Dijkstra} E.W.~Dijkstra, ``Self-stabilizing systems in
spite of distributed control,'' {\em Communications of the ACM 17,} no.~11,
pp. 643--644, 1974.
\bibitem[Even, 1979]{Even} S. Even {\em Graph Algorithms }, Computer
Science Press, 1979.

\bibitem[Feldman \& Ballard 1982]{Feldman} J.A Feldman, D.H. Ballard,
 ``Connectionist models and their properties,'' {\em Cognitive Science} 6,
1982.
\bibitem[Hinton \& Sejnowski 1986]{Boltzmann}
	~G.E Hinton and T.J.  Sejnowski, (1986)
{\em Learning and re-learning in
 	Boltzmann Machines},
        in  J. L. McClelland and D. E. Rumelhart,
	{\em
Parallel Distributed Processing: Explorations in The Microstructure of
	Cognition I, }   
  pp.~282--317,
	MIT Press,  1986.




\bibitem[Hopfield, 1982]{Hopfielda} J. J. Hopfield 
``Neural networks and physical systems with emergent collective computational 
abilities,'' {\em Proceedings of the National Academy of Sciences 79,} 
 pp. 2554--2558, 1982.
\bibitem[Hopfield, 1984]{Hopfieldb}
	J. J. Hopfield
	``Neurons with graded response have collective computational
	properties like those of two-state neurons,''
	{\em Proceedings of the National Academy of Sciences 81},
	  pp. 3088--3092, 1984.

\bibitem[Hopfield \& Tank 1985]{Tank}
	J.J. Hopfield, D.W. Tank
``Neural Computation of Decisions in Optimization Problems,''
	{\em Biological Cybernetics  52}, pp.~144--152.
\bibitem[Kasif et al. 1989]{Kasif} S.~Kasif, S.~Banerjee, A.~Delcher, G.~Sullivan
``Some results on the computational complexity of symmetric connectionist
networks,'' 
Department of Computer Science, The John Hopkins University, Technical Report
JHU/CS-89/10, 1989.

\bibitem[Korach et al. 1984]{korach} K. Korach, D. Rotem, and N. Santoro
``Distributed algorithms for finding centers and medians in
networks'' {\em ACM transaction on Programming Languages and 
Systems} 6(3):380--401, July 1984.

\bibitem[Lehmann \& Magidor 1988]{Lehman} D. Lehmann, M.~Magidor, ``Rational
logics and their models: A study in cumulative logic'', Technical Report,
TR-86-16, Leibnitz Center for Computer Science, Hebrew University, Jerusalem,
1988.
\bibitem[McClelland et al. 1986]{pdp1}J.~L.~McClelland, 
D.~E.~Rumelhart, G.E Hinton,
 ``The appeal of PDP,'' in  
J.~L.~McClelland and D.~E.~Rumelhart, {\em Parallel Distributed Processing: 
Explorations in The Microstructure of Cognition I}, MIT Press,  1986.

\bibitem[Minton et al. 1990]{Minton}S.~Minton, M.~D.~Johnson, A.~B.~Phillips,
``Solving large scale constraint satisfaction and scheduling problems using a
heuristic repair method,'', {\em Proceedings of the Eighth Conference on 
Artificial Intelligence}, pp.~17--24, 1990.
\bibitem[Papadimitriou et al. 1990]{Papa} C.~Papadimitriou, A.~Shaffer, M.~Yannakakis,
 ``On the complexity of local search,'' {\em ACM Symposium on the Theory
of Computation,} pp.~438--445, 1990.
\bibitem[Pearl, 1988]{PearlBook} J.~Pearl {\em Probabilistic
Reasoning in Intelligent Systems: Networks of Plausible Inference}
Morgan Kaufmann Publishers, San Mateo, California, 1988.

\bibitem[Pearl, 1990]{Pearl} J.~Pearl, ``System Z: A natural ordering of defaults 
with tractable applications to nonmonotonic reasoning,'' in {\em Proceedings
of the Workshop on Theoretical aspects of Knowledge Representation \/}
(TARC), M.~Vardi (ed.), pp.~121--135, Morgan Kaufmann, 1990.

\bibitem[Peterson \& Hartman 1989]{Meanfield}C. Peterson, E. Hartman,
``Explorations of mean field theory
learning algorithm,'' {\em Neural Networks 2,} no.~6, 1989.
\bibitem[Pinkas, 1990b]{PinkasNC} G. Pinkas, ``Energy minimization and the 
satisfiability of propositional calculus,''
  {\em Neural Computation 3,}   no.~2, 1991.
\bibitem[Pinkas, 1991]{PinkasIJCAI} G. Pinkas, ``Propositional non-monotonic
reasoning and inconsistency in symmetric neural networks,'' {\em Proceedings
of the 12th International Joint Conference on Artificial Intelligence},
pp. 525--530, Sydney, 1991.
\bibitem[Pinkas \& Dechter 1992]{Pinkasj} G. Pinkas, R. Dechter, ``A new improved
activation function for energy minimization,'' {\em Proceedings of the Tenth
National Conference on Artificial Intelligence (AAAI),} 
pp. 434--439, San Jose, 1992.
\bibitem[Pinkas, 1994]{PinkasAIJ} G. Pinkas, ``Reasoning, nonmonotonicity and
learning in connectionist networks that capture propositional knowledge,''
to appear in {\em Artificial Intelligence Journal}, May 1995.

\bibitem[Rumelhart et. al. 1986]{pdp2}D.E. Rumelhart, G.E Hinton, J.L. McClelland,
``A general framework for parallel distributed processing,'' in  
J.~L.~McClelland and D.~E.~Rumelhart, {\em Parallel Distributed Processing: 
Explorations in The Microstructure of Cognition I}, MIT Press,  1986.

\bibitem[Selman et. al. 1992]{Selman} B.~Selman, H.~Levesque, D.~Mitchell,
``A new method for solving hard satisfiability problems,'' {\em Proceedings
of the Tenth National Conference on Artificial Intelligence,} pp.~440--446,
1992.
\bibitem[Shoham, 1988]{Shoham} Y.~Shoham, {\em Reasoning about Change,} MIT Press,
Cambridge, 1988.
\bibitem[Shortliffe, 1976]{Mycin} E.~H.~Shortliffe, {\em Computer-based medical
consultation, Mycin}, Elsevier, New York, 1976.
 
\bibitem[Smolensky, 1986]{Harmony}  P. Smolensky, ``Information processing in
dynamical systems: Foundations of harmony theory,''
        in  J.L.McClelland and D.E.Rumelhart,
	{\em
Parallel Distributed Processing: Explorations in The Microstructure of
	Cognition I },
	MIT Press,  1986.



\end{thebibliography}
}

\bibliography{jair}
\bibliographystyle{theapa}
\end{document}





