\documentstyle[12pt,eclepsf]{article}

\textheight 238mm
\textwidth 165mm
\topmargin -10mm
\oddsidemargin -3mm

%\pagestyle{empty}
%\thispagestyle{empty}

\begin{document}

\title{Error Correcting Capability of a Morphological Associative Memory}
       
\author{Akira Imada\\
        \hspace*{.1in}\\
        Department of Electrical and Electronics Engineering\\
        Anadolu University\\
        Eskisehir, Turkey\\
        E-mail: akira@mmf.mm.anadolu.edu.tr}
\date{}
\maketitle

\begin{abstract}
\noindent
Morphological associative memory is a neural 
network model of associative memory whose storage 
capacity is $2^N$ while the traditional Hopfield 
scheme can store $2N$ patterns at most, where $N$ 
is the number of neurons. However, how about the 
error correcting capability? The error correcting 
capability of the morphological associative memory 
model has not been studied extensively. In this paper, 
we explore this issue by comparing it with the 
Hopfield model. 
\end{abstract}

\noindent
{\bf keywords:} morphological associative memory, Hopfield model, storage capacity,
                error correcting capability (basin of attraction). \\

\section{Introduction}
Associative memory is a dynamical system which has 
a number of stable states with each state having 
a domain of attraction \cite{koml}.
If the system starts at any state in a domain, 
it will converge to the stable state.

The associative memory has been realized mainly 
with a fully connected neural network model.
%-----------------------
Provided the synaptic strengths among neurons
are determined appropriately, network stores 
a number of patterns as attractors.
%-----------------------
An initial network state which is possively a noisy 
and/or partial input of one of these stored patterns
is updated repeatedly and preferably converges to 
the corresponding pattern.
%-----------------------
If an initial input in the vicinity of one of 
the memory converges to the memory, the memory is 
said to be recalled with the error being corrected. 

In 1982, Hopfield \cite{hopf} proposed a model
in which he used the so-called Hebb's \cite{hebb} 
rule to determine the synaptic strengths, and 
an asynchronous rule to update network state. 
Since then, a lot of other schemes of determining 
weights and updating state have been proposed.
In these schemes, storage capacity is traded off  
against error correcting capability, and
Gardner \cite{gard} analytically proved that
the error correcting capability shrinks to zero 
when the number of stored patterns approaches 
the number twice as much as the number of neurons.

Morphological associative memory is proposed by 
Ritter, Susner, and Diaz-de-Leon \cite{sus1,sus2},
partly to overcome the limit of this storage capacity, 
as they described ``it has an unlimited storage capacity.''
As cited in \cite{sus1,sus2}, the idea of 
morphological neural networks grew out of 
the theory of image algebra \cite{ritt}, 
and the operations are based on the 
mathematical morphology \cite{serr}.

Since the error correcting capability of 
the morphological associative memory 
was not described in \cite{sus1,sus2} 
in detail, we study it in its simplest
form by comparing it empirically
with the Hopfield model.

\section{Hopfield's versus Morphological}
The neural network model of associative memory, in general,  
consists of $N$ neurons and $N^2$ synapses.
Each neuron state is either active (+1) or quiescent ($-1$).
When an arbitrary $N$-bit {\it bipolar pattern}, 
\begin{equation} \label{eq:pattern}
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), \hspace{.2in}{\nu} = 1, \cdots, p,
\end{equation}
a sequence of $+1$ and $-1$, is given to the network as an initial state,
the dynamical behavior of neurons' states afterwards 
are characterized by the strengths of the $N^2$ synapses.
The synaptic strengths are called {\it weights}, 
and the weight from neuron $j$ to neuron $i$ is denoted 
as $w_{ij}$ in this paper.\\

\noindent
{\bf Hopfield Model.}
In order to store $p$ patterns described in equation (\ref{eq:pattern}),
Hopfield used the so-called Hebb's rule to determine weight values, as follows,
\begin{equation}\label{eq:hopf1}
w_{ij} = \frac{1}{N} \sum _{ \nu = 1}^{p} {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}
\hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{equation}
Further, an instantaneous state of a neuron is updated asynchronously (one neuron at a time) as:
\begin{equation} \label{eq:hopf2}
s_{i}\hspace{.02in} (t+1) = sgn \hspace{.02in} 
\left( \hspace{.04in} \sum_{j \ne i}^N { w_{ij} s_{j}(t)} 
     \hspace{.04in} \right),
\end{equation}
where $s_{i}(t)$ is a state of the $i$-th neuron at time $t$.
Then the $p$ patterns are stored as fixed point attractors, if $p$ is sufficiently small.\\

\noindent
{\bf Morphological Model.}
As mentioned earlier, associative memory should be robust for input noises. 
That is, small errors given to an input of the stored patterns
should be corrected when the network converged to the stable state.
In the morphological associative memory, noises are devided into two categories:
``{\it erosive errors}'' and ``{\it dilative errors}''.
Erosive error changes some of $+1$ of the input pattern into $-1$,
and dilative error changes some of $-1$ into $+1$.
Each of these two noises is processed by different module.
For the sake of simplicity, however, our focus will be only on erosive errors in this paper. 
To store the same patterns (\ref{eq:pattern}),
the weight values are determined by the following way.
\begin{equation}\label{eq:morp1}
w_{ij} = \mbox{\bf min}_{\nu = 1}^{p} ({\xi}_{i}^{\nu} - {\xi}_{j}^{\nu}),
\end{equation}
and update of neurons' state is as follows.
\begin{equation}\label{eq:morp2}
s_{i}\hspace{.02in} (t+1) = sgn \hspace{.02in} 
\left( \hspace{.04in} \mbox{\bf max}_{j = 1}^N {( w_{ij} + s_{j}(t))} 
     \hspace{.04in} \right).
\end{equation}
As described in \cite{sus1,sus2}, it is interesting to compare 
(\ref{eq:morp1}) and (\ref{eq:morp2}) 
with (\ref{eq:hopf1}) and (\ref{eq:hopf2}), respectively, 
and to notice its duality.

In their paper, Ritter et al.\ \cite{sus1,sus2} proved 
that ``the memories converge in one step for any input pattern,''
which is very different from the Hopfield model,
where we sometimes have to wait for a long time 
until an initial state converges to a stable state. 

\section{Results and Discussion}
Comparisons are made using networks with 49 neurons.
By ``noise'' in this section we mean dilative noise, i.e.,
noises are given to some of ``$+1$'' bits and turn them into ``$-1$'' bits. \\

\noindent
{\bf Storage as fixed points.}
Associative memory stores a number of patterns as fixed point attractors.
That is, any input of the stored patterns remains unchanged.
However, when the number of patterns to be stored increases (over-loaded),
this capability will be corrupted, in general.
Some of the over-loaded stored patterns result in transition of neurons' states
and the initial state converges to some other point close to the pattern or diverges. 
So, first of all, we compare the storage capacity 
as fixed point attractors of the two models,
by observing an average correct bit ratio of 
recalled patterns when one of stored patterns 
is given without any noise. 

The results are shown in Figure 1.
As Ritter et al.\ \cite{sus1,sus2} described the morphological associative memory
stored patterns perfectly as fixed points. We observed it even if the number
of storage exceeds 140, while the Hopfield associative memory
fails it for more than 16 patterns.\\

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=fp-storage.eps,width=16cm,height=8cm}
   \label{fixed}
   \caption{Average correct bit ratio of recalled patterns  
            when stored patterns are given without noise.}
 \end{center}
\end{figure}

\noindent
{\bf Basin size of attraction.}
Then comparisons are made with noisy inputs.
Figure 2 shows the recovery ratio as a function
of number of noisy bit of input patterns,
that is, size of basin of attraction.
We observed it when the number of storage is 1, 2, 4, and 8.

When the number of patterns to be stored is only one, the task is
easy, and the both models recalled the patterns perfectly even for the 20 eluded bits.
As the number of storage increases, 
the degree of precise recorrection becomes worse for both models.
The performance is slightly better in morphological model though,
the difference is not so significant.\\

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=hopf-storage-cap.eps,width=16cm,height=8cm}
   \epsfile{file=sus-storage-cap.eps,width=16cm,height=8cm}
   \label{storage}
   \caption{Recovery ratio of recalled patterns vs. number of noisy bits 
            when the number of stored patterns is 1, 2, 4, and 8.}
 \end{center}
\end{figure}

\noindent
{\bf Basin size dependency on storage.}
The comparisons are also made for the recovery ratio versus
number of storage.
As Figure 3 shows, the morphological associative memory also begins to fail to
recall a stored pattern as the number of storage increases.
However, we found that ratio of correct bit in morphological model 
is far better than in the Hopfield model.
Furthermore, the ratio does not decrease any more after reaching some level of failure,
while in the Hopfield model, the ratio keeps decreasing. 
  

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=hopf-noisy.eps,width=16cm,height=8cm}
   \epsfile{file=susner-noisy.eps,width=16cm,height=8cm}
   \label{noisy}
   \caption{Recovery from 1, 2, 4, and 8 bit noisy input of the stored patterns}
 \end{center}
\end{figure}


\section{Conclusion}
The error correcting capability of the morphological associative memory
has empirically studied by comparing it with the Hopfield model.
We found that although the morphological associative memory has a large storage capacity
as Ritter et al.\ \cite{sus1,sus2} said in their paper,
the error correcting capability, on the other hand, 
is only slightly better than the one of the Hopfield model.
However the robustness of the morphological model
for a large number of storage concerning the recovery ratio of a noisy input
is significantly higher in morphological associative memory than the Hopfield model.

As Ritter et al.\ \cite{sus1,sus2} also pointed out, 
the morphological associative memory model has not been studied so extensively,
especially concerning error correcting capability.
Due to its large storage capacity, the model can be applied more practically
to real world problems.
For the purpose, however, analysis of error collecting capability is important.
As a near future work, the behaviors of basin size of attractors
will be studied analitycally. 

\subsection*{Acknowledgments}
We thank Peter Susner for the discussion of the morphological associative memory
at the conference cite of Neural Computations 1999 (NC'99) held at Vienna, and 
also for answering us several questions via e-mail afterwards.

\begin{thebibliography}{99}

\bibitem{koml}J.~Koml\'{o}s, and R.\ Paturi (1988)
{\em Convergence Results in an Associative Memory Model.}
Neural Networks, 1, pp.239--250.

\bibitem{hopf}J.\ J.\ Hopfield (1982) 
{\em Neural Networks and Physical Systems with Emergent Collective Computational Abilities.}
Proceedings of the National Academy of Sciences, USA, 79,  pp.2554-2558.

\bibitem{hebb}D.~O.~Hebb (1949)
{\em The Organization of Behavior. Wiley.}

\bibitem{gard}E.\ Gardner (1988)
{\em The Phase Space of Interactions in Neural Network Models.}
Journal of Physics, 21A, pp.257--270.

\bibitem{sus1} G. X. Ritter, P. Sussner, and J. L. Diaz de Leon (1988)
{\em Morphological Associative Memories,}
IEEE Transactions on Neural Networks, Vol. 9, No. 2, pp.281--293.

\bibitem{sus2} P. Sussner
{\em Kernels for Morphological Associative Memories.}
Proceedings of the International ICSC/IFAC Symposium on Neural
Computation, pp.79--85.

\bibitem{ritt} G. X. Ritter, J. N. Wilson, and J. L. Davidson (1990)
{\em Image Algebra: An Overview.}
Computer Vision, Graphics, and Image Processing, Vol.49, No.3, pp.297--331.

\bibitem{serr} J. Serra (1982)
{\em Image Analysis and Mathematical Morphology.}
Academic Press.

\end{thebibliography}

\end{document}

