Input pattern x

Pattern associator Output pattern y

Figure 1: Operation of pattern associator.

1 Brain-State-in-a-Box (BSB) Models

1.1 Associative Memories

In this section, we analyze a class of neural network models that can be used to construct the so called associative memories. We distinguish between two types of association: autoassociation and heteroassociation. In autoassociation, after storing a set of patterns by a neural network, where patterns are usually represented as vectors, a distorted (noisy) pattern of a stored pattern is subsequently presented to the network. The task of the neural network is to retrieve (recall) the original stored pattern from the noisy pattern. In heteroassociation an arbitrary set of input patterns is paired with another arbitrary set of output patterns. Operation of an associative memory is characterized by two stages: storage phase, where patterns are being stored by the neural network, and recall phase, where memorized patterns are being retrieved in response to a noisy pattern presented to the network. Figure 1 illustrates the recall phase. In this figure, the input pattern represents a noisy version of stored pattern x_{j}. The pattern associator produces the output pattern y in response to the input pattern x. For perfect recall in an autoassociative memory, we should have y = x_{j}. When y ≠ x_{j}, the associative memory is said to have made a recall error (error in recall). A neural network that can be used as an associative memory is the Brain-State-in-a-Box (BSB) neural model, which was proposed by Anderson, Silverstein, Ritz, and Jones in 1977 [2]. It can recognize a pattern from its given noisy version. For this reason the BSB neural model is often referred to as an associative memory. The BSB neural model is a discrete dynamical system whose dynamics are described by the difference equation,

x(k + 1) = g (x(k) + αW x(k))  (1)

subject to the initial condition

x(0) = x_{0},

where x(k) ∈ ℝ^{n} is the state of the BSB network at time k, α > 0 is the step size, and W ∈ ℝ^{n×n} is a symmetric weight matrix determined during the training procedure. The function g : ℝ^{n} → ℝ^{n} is a vector valued function whose i-th component (g)_{i} is defined as:

(g(x))_{i} = \{ \begin{matrix}1 & if & x_{i} ≥ 1 \\ x_{i} & if & −1 < x_{i} < 1 \\ −1 & if & x_{i} ≤ −1. \end{matrix}

The above nonlinear activation function is sometimes referred to as the linear saturating nonlinearity. A plot of such a function is shown in Figure 2. The BSB model gets its name from the fact that the state of the network trajectories are constrained to be in the hypercube H_{n} = [ −1 1 ]^{n}. In Figure 3, we show a state plane portrait of the BSB model (1) with the weight matrix

W = [ \begin{matrix}7 & −3 \\ −3 & 10 \end{matrix} ]  (2)

and the step size is α = 0.1. The state space of this two-dimensional neural net is the square H_{2} = [ −1 1 ]^{2}. Each vertex of the square has its basin of attraction. In this example all four vertices are asymptotically stable equilibrium states of the BSB neural net. In Figure 4, we show a state plane portrait of the BSB model (1) with the weight matrix

W = [ \begin{matrix}5 & −3 \\ −3 & 2 \end{matrix} ]  (3)

Figure 2: A plot of linear saturating nonlinearity used in the BSB model as an activation function.

Figure 3: Trajectories of the BSB model with the weight matrix W given by (2).

Figure 4: Trajectories of the BSB model with the weight matrix W given by (3).

and the step size α = 0.1. In this example only two vertices are asymptotically stable equilibrium states of the BSB neural net. When the BSB model is used as an associative memory, asymptotically stable equilibrium points of the model represent stored patterns. Noisy patterns are represented by points in the basins of attraction of the stable equilibrium points. Thus, suppose we are given a noisy, or imperfect, pattern represented by an initial condition x_{0} that is located in a basin of attraction of a stable equilibrium point corresponding to the correct pattern. Then, the corresponding trajectory of the BSB model evolves in time to this stable equilibrium point representing the correct stored pattern. Hence, in this case, the process of association and information retrieval is modeled by the BSB model—a nonlinear discrete dynamical system. An associative memory is able to recall all the information stored in the memory when it is excited with a sufficient large portion of that memory’s information. This is in contrast to the address addressable memory (AAM) used in digital computers. In this type of memory, a desired set of information is recalled only when the entire correct address of the information is given. For this reason, we can view associative memories as content addressable memories (CAM).

In summary, realization of associative memories with neural networks requires storage of a set of given patterns as asymptotically stable equilibrium points of the network. The points in basins of attraction about each stable equilibrium point correspond to noisy versions of the stored patterns. When a noisy version of a stored pattern is sufficiently close to it, the network trajectory should converge to the equilibrium point corresponding to the correct pattern. Neural network associative memories should possess the following useful properties:

1. Each given pattern to be stored should be stored as an asymptotically stable equilibrium point of the network;

2. The number of asymptotically stable equilibrium points of the network that do not correspond to the given stored patterns (that is, spurious states) is minimal;

3. A nonsymmetric interconnection structure, which eases difficulties in implementing associative memory using neural networks;

4. The ability to control the extent of the basin of attraction about the equilibrium point corresponding to each stored pattern;

5. Learning capability, that is, the ability to add patterns to be stored as asymptotically stable equilibrium points to an existing set of stored patterns without affecting the existing equilibria;

6. Forgetting capability, that is, the ability to delete specified equilibria from a given set of stored equilibria without affecting the rest of the equilibria;

7. A high storage and retrieval efficiency, that is, the ability to efficiently store and retrieve a large number, compared to the order n of the network, of patterns.

1.2 Analysis of BSB Models

The BSB neural net has a symmetric weight matrix, which is not a desirable property of a neural associative memory. Hui and Żak [16] modified the BSB model to allow for nonsymmetric weight matrix as well as to better control the extent of basins of attraction.

A modified form of the BSB neural model, which we refer to as the generalized Brain-State-in-a-Box (gBSB) neural model, is well suited for implementing associative memories. Its dynamics are described by the equation

x(k + 1) = g((I_{n} + αW)x(k) + αb),  (4)

where I_{n} is the n×n identity matrix, b ∈ ℝ^{n}, and the weight matrix W ∈ ℝ^{n×n} need not be symmetric as in the BSB model. Thus, the original BSB model can be viewed as a special case of the gBSB model when the interconnection matrix W is symmetric and b = 0. We add that the analysis of the BSB model behavior on the boundary regions of the hypercube H_{n} can be reduced to the study of the reduced order gBSB type models rather than that of the BSB type.

We now describe an algorithm for computing the weight matrix W and the vector b that result in the given patterns being stored as asymptotically stable vertices of the hypercube H_{n}. In further discussion, we use the following notation and definitions. Let

L(x) = (I_{n} + αW) x + αb,

and

T (x) = g(L(x)).

Definition 1 A point x ∈ H_{n} is an equilibrium point of x(k + 1) = T (x(k)) if x = T (x).

Note that an equilibrium point is a constant solution to the system x(k + 1) = T (x(k)).

Let (L(x))_{i} be the i-th component of L(x) and v_{i}^{(j)} be the i-the component of the vector v^{(j)}. Let v = [ v_{1} ⋯ v_{n} ]^{T} ∈ {−1, 1}^{n}. Then, obviously v is a vertex of H_{n} because for i = 1, 2, …, n, we have v_{i} = ±1. For a vertex v of H_{n} to be an equilibrium point of the gBSB, we have to have

v_{i} = (g (L(v)))_{i} i = 1, 2, …, n,

that is, if v_{i} = 1, then we should have

(L(v))_{i} ≥ 1,  (5)

and for v_{1} = −1, we should have

(L(v))_{i} ≤ −1.  (6)

Combining (5) and (6), we obtain the following necessary and sufficient conditions for the vertex v to be an equilibrium point.

Theorem 1 A vertex v of the hypercube H_{n} is an equilibrium point of the gBSB neural model if and only if

(L(v))_{i}v_{i} ≥ 1, i = 1, 2, …, n.

Equivalently, a vertex v of the hypercube H_{n} is not an equilibrium point of the gBSB neural model if and only if

(L(v))_{i}v_{i} < 1, for some i = 1, 2, …, n.

Example 1 We verify that the vertex v^{(1)} = [ 1 1 ]^{T} of H_{2} is not an equilibrium point of the BSB model with the weight matrix given by (3) and the step size α = 0.1. Note that for the BSB model,

L(x) = (I_{n} + αW)x.

We first compute L (v^{(1)}) to get

L (v^{(1)}) = (I_{2} + αW) v^{(1)} = [ \begin{matrix}1.2 \\ −0.1 \end{matrix} ] .

Note that because

(L (v^{(1)}))_{2} v_{2}^{(1)} = −0.1 < 0,

the vertex v^{(1)} is not an equilibrium point of the above BSB model.

On the other hand, the vertex v^{(2)} = [ 1 −1 ]^{T} is an equilibrium point of this BSB model because

(L (v^{(2)}))_{1} v_{1}^{(2)} = 1.8 ≥ 0 and (L (v^{(2)}))_{2} v_{2}^{(2)} = 0.5 ≥ 0,

that is, the necessary and sufficient conditions of Theorem 1 are satisfied.

In our analysis we use stability definitions in the sense of Lyapunov, which we now recall.

Definition 2 An equilibrium point x^{∗} of x(k + 1) = T (x(k)) is stable if for every ε > 0 there is a δ = δ(ε) > 0 such that if ∥x(0) − x^{∗}∥ < δ then ∥x(k) − x^{∗}∥ < ε for all k ≥ 0, where ∥ · ∥ may be any p-norm of a vector, for example the Euclidean norm ∥ · ∥_{2}.

The above definition says that if an equilibrium is stable then if a trajectory starts sufficiently close to the equilibrium, it stays close to the equilibrium for all future times. If the equilibrium is not stable, then it is called unstable.

Definition 3 The equilibrium solution x^{∗} is asymptotically stable if it is stable and if there exists an η > 0 such that if ∥x(0) − x^{∗}∥ < η then lim_{k→∞} x(k) = x^{∗}.

The following theorem gives us a sufficient condition for a vertex of H_{n} to be an asymptotically stable equilibrium point.

Theorem 2 Let v be a vertex of the hypercube H_{n}. If

(L(v))_{i}v_{i} > 1, i = 1, 2, …, n,

then v is an asymptotically stable equilibrium point of the gBSB neural model.

Proof Because (L(x))_{i}x_{i} is a continuous function, there exists a neighborhood N(v) about v such that

(L(x))_{i}x_{i} > 1 for all i = 1, 2, …, n and x ∈ N(v).

Therefore, for any x ∈ N(v), we have

g(L(x)) = v,

which means that v is indeed asymptotically stable equilibrium point.

□

In our further discussion, we use a special class of matrices that are characterized in the following definition.

Definition 4 A matrix D ∈ ℝ^{n×n} is said to be row diagonal dominant if

d_{ii} ≥ ∑_{{j=1 \atop j≠i}}^{n} |d_{ij}|, i = 1, 2, …, n.

It is strongly row diagonal dominant if

d_{ii} > ∑_{{j=1 \atop j≠i}}^{n} |d_{ij}|, i = 1, 2, …, n.

Now, suppose we are given a matrix V ∈ ℝ^{n×r}. Its pseudo-inverse, or the Moore-Penrose inverse, is defined as follows. Definition 5 Given V ∈ ℝ^{n×r}, a matrix V^{†} ∈ ℝ^{r×n} is called a pseudo-inverse of V if

1. V V^{†}V = V ;

2. V^{†}V V^{†} = V^{†};

3. (V V^{†})^{T} = V V^{†};

4. (V^{†}V )^{T} = V^{†}V . The pseudo-inverse has the following useful properties:

• (V^{T})^{†} = (V^{†})^{T};

• (V^{†})^{†} = V .

1.3 Synthesis of Neural Associative Memory

We now present an expression for constructing the weight matrix W ensuring that the given patterns are stored as asymptotically stable equilibrium points of the hypercube H_{n}. Let d_{ij} be the ij-th element of the matrix D, b_{i} be the i-th element of the vector b, and v_{i}^{(j)} be the i-the component of the vector v^{(j)}. Recall that we denote the i-th component of a vector L(v) as (L(v))_{i}.

Theorem 3 Let V = [v^{(1)}, v^{(2)}, …, v^{(r)}] ∈ {−1, 1}^{n×r} be the matrix of patterns that we wish to have stored as asymptotically stable points of the gBSB net. Let B = [b, b, …, b] ∈ ℝ^{n×r} be the matrix consisting of the column vector b repeated r times, Λ ∈ ℝ^{n×n}, β_{j} = ∑_{i=1}^{r} (V^{†}v^{(j)})_{i}, and β = − max_{j} |β_{j}|, where j = 1, 2, …, r. Suppose

d_{ii} > ∑_{{k=1 \atop k≠i}}^{n} |d_{ik}| + |b_{i}(1 − β)| i = 1, 2, …, n.

If in the gBSB model its weight matrix

W = (DV − B)V^{†} + Λ (I_{n} − V V^{†}) ,  (7)

then all the patterns v^{(j)}, j = 1, 2, …, r, will be stored as asymptotically stable equilibrium points of the gBSB model.

Proof Using the first property of the More-Penrose inverse of V , we obtain

W V = (DV − B)V^{†}V + Λ (I_{n} − V V^{†}) V
= DV − BV^{†}V
= DV − [ BV^{†}v^{(1)} BV^{†}v^{(2)} ⋯ BV^{†}v^{(r)} ]
= DV − [ bβ_{1} bβ_{2} ⋯ bβ_{r} ] .

The j-th column of the above is

W v^{(j)} = Dv^{(j)} − bβ_{j} j = 1, 2, …, r.

We now show that a sufficient condition for a pattern v^{(j)} to be an asymptotically stable equilibrium of x(k + 1) = T (x(k)) is satisfied. Performing simple manipulations and taking into account the assumptions we obtain for j = 1, 2, …, r:

(L (v^{(j)}))_{i} v_{i}^{(j)} = ((I_{n} + αW)v^{(j)} + αb)_{i} v_{i}^{(j)}
= (v^{(j)} + αDv^{(j)} − αβ_{j}b + αb)_{i} v_{i}^{(j)}
= 1 + α (d_{ii} + ∑_{{k=1 \atop k≠i}}^{n} d_{ik}v_{k}^{(j)}v_{i}^{(j)} + b_{i}(1 − β_{j})v_{i}^{(j)})

≥ 1 + α (d_{ii} − [∑_{{k=1 \atop k≠i}}^{n} |d_{ik}| + |b_{i} (1 − (− max_{j} |β_{j}|))|])
= 1 + α (d_{ii} − [∑_{{k=1 \atop k≠i}}^{n} |d_{ik}| + |b_{i}(1 − β)|])
> 1,

where the last inequality follows from the assumption on the matrix D. Hence, the given patterns are asymptotically stable equilibrium points of the gBSB model.

□

If the patterns are linearly independent and r < n, then rankV = r and therefore V^{†}V = I_{r}. In this case β_{j} = 1 for all j and

W v^{(j)} = Dv^{(j)} − b j = 1, 2, …, r,

Thus in this case, a sufficient condition for the patterns v^{(j)}, j = 1, 2, …, r, to be stored as asymptotically stable equilibrium points of the gBSB model is that for i = 1, 2, …, n,

d_{ii} > ∑_{{k=1 \atop k≠i}}^{n} |d_{ik}|.

The above condition indeed guarantees that all the desired patterns are stored as asymptotically stable equilibria. However, if d_{ii}’s are too large, then we may end up storing many other vertices of H_{n} in addition to the given patterns to be stored. To avoid this scenario, we impose the constraints of the form

d_{ii} < ∑_{{k=1 \atop k≠i}}^{n} |d_{ik}| + |b_{i}|, i = 1, 2, …, n,

on the matrix D while synthesizing the weight matrix W.

We now discuss the role of the different terms in the expression (7) on the weight matrix in storing the desired patterns and minimizing the number of spurious states. First, the term (DV − B)V^{†} is responsible for the given patterns to be stored as asymptotically stable equilibrium points of the gBSB model. This is because for a given pattern, say v^{(j)}, we have Λ(I_{n} − V V^{†})v^{(j)} = 0, where 0 is a vector of zeros. The role of the term Λ(I_{n} − V V^{†}) is to destabilize patterns that are not in Span [v^{(1)}, v^{(2)}, …, v^{(r)}]. Specifically, if a pattern y is orthogonal to Span [v^{(1)}, v^{(2)}, …, v^{(r)}], then the term Λ(I_{n} −V V^{†}) will not only destabilize the vertex of H_{n} corresponding to the pattern y, if it is an equilibrium point of the gBSB model, it will make this point a non-equilibrium point of the gBSB model. To see this, consider the expression

W y = (DV − B)V^{†}y + Λ(I_{n} − V V^{†})y.

Because

y ⊥ Span [v^{(1)}, v^{(2)}, …, v^{(r)}] ,

we have

W y = Λ(I_{n} − V V^{†})y
= Λy.

Therefore,

(L(y))_{i}y_{i} = ((I_{n} + αW)y + αb)_{i}y_{i}
= (y + α(Λy + b))_{i}y_{i}
= 1 + α(λ_{ii} + ∑_{{j=1 \atop j≠i}}^{n} λ_{ij}y_{j}y_{i} + b_{i}y_{i}).

Hence, if we choose Λ such that for some i = 1, 2, …, n,

λ_{ii} < − ∑_{{j=1 \atop j≠i}}^{n} |λ_{ij}| − |b_{i}|,

then

(L(y))_{i}y_{i} < 1 for some i = 1, 2, …, n.

Therefore, by Theorem 1, the point y cannot be an equilibrium point. The inclusion of the matrix B in the synthesis formula for the weight matrix W was to prevent an automatic storage of the negatives of the given patterns as well as to somehow help to direct the gBSB model trajectories towards the given patterns. For this reason, we select b to be in Span{V }. We recommend making b a weighted sum of v^{(i)}, i = 1, 2, …, r, with positive weight coefficients. The above results can be used as guides for selecting the components of the matrices D, Λ, the vector b, and consequently the matrix B. We summarize the above considerations in the form of an algorithm for synthesizing the weight matrix W.

The Weight Matrix Construction Algorithm

Given: v^{(j)}, j = 1, 2, …, r.

• Form B = [b, b, …, b], where

b = ∑_{j=1}^{r} ϵ_{j}v^{(j)}, ϵ_{j} > 0, j = 1, 2, …, r.

• Form D such that

d_{ii} > ∑_{{k=1 \atop k≠i}}^{n} |d_{ik}|, and
d_{ii} < ∑_{{k=1 \atop k≠i}}^{n} |d_{ik}| + |b_{i}|,  i = 1, 2, …, n.

• Form Λ such that for i = 1, 2, …, n,

λ_{ii} < − ∑_{{j=1 \atop j≠i}}^{n} |λ_{ij}| − |b_{i}|.

• Compute

W = (DV − B)V^{†} + Λ(I_{n} − V V^{†}).

• Apply the condition (L(v))_{i}v_{i} ≥ 1 to all vertices of H_{n} to identify spurious equilibrium patterns.

When the set of patterns to be stored is not linearly independent, we of course can still use the above algorithm to compute the weight matrix W. However, the second constraint on the matrix D may lead to a violation of the condition on D in Theorem 3. In such a case we cannot guarantee that all the given patterns will be stored, nor we will have any control on the number of spurious states. We may then relax this condition. If attempts in synthesizing associative memory for a set of linearly dependent patterns result in unacceptable designs, we may try a different approach. We can start by picking a maximal set of patterns that are linearly independent from the given set of patterns. Let us assume that are s patterns to be stored and r of them form a maximal linearly independent subset. Suppose, for notational simplicity, that the patterns v^{(q)}, q = 1, …, r, form a linearly independent set. We then apply the above algorithm to generate the weight matrix W based on the linearly independent patterns v^{(q)}, q = 1, …, r. After that, we modify the obtained weight matrix and the vector b to ensure that the remaining patterns v^{(j)}, j = r + 1, r + 2, …, s will also be stored. We will focus our attention on ensuring that the pattern v^{(r+1)} is stored as an asymptotically stable point. The remaining patterns v^{(j)}, j = r + 2, r + 3, …, s, can be stored using the same procedure. Because

v^{(r+1)} ∈ Span {v^{(1)}, v^{(2)}, …, v^{(r)}} ,

that is, v^{(r+1)} is a linear combination of v^{(i)}, i = 1, 2, …, r, it can be represented as

v^{(r+1)} = ∑_{q=1}^{r} γ_{q}v^{(q)} = V γ,

where γ = [ γ_{1} ⋯ γ_{r} ]^{T} ∈ ℝ^{n}. Then, using (7), we obtain

W v^{(r+1)} = DV γ − Bγ
= Dv^{(r+1)} − (∑_{q=1}^{r} γ_{q}) b.

Recall that L(v) = (I_{n} + αW)v + αb. Hence,

L (v^{(r+1)}) = v^{(r+1)} + α(W v^{(r+1)} + b)
= v^{(r+1)} + α (Dv^{(r+1)} − [∑_{q=1}^{r} γ_{q} − 1] b) .

Recall now that the conditions for the asymptotic stability of v^{(r+1)} are

(L (v^{(r+1)}))_{i} v_{i}^{(r+1)} > 1 i = 1, 2, …, n,

or equivalently, since α > 0,

(Dv^{(r+1)} − [∑_{q=1}^{r} γ_{q} − 1] b)_{i} v_{i}^{(r+1)} > 0, i = 1, 2, …, n.

Observe that because of the assumptions on the matrix D, we have

sign (Dv^{(r+1)})_{i} = signv_{i}^{(r+1)}.

With the above in mind, we obtain stronger sufficient conditions for v^{(r+1)} to be asymptotically stable. They are:

sign [(1 − ∑_{q=1}^{r} γ_{q}) b]_{i} = sign (v_{i}^{(r+1)}) i = 1, 2, …, n.

We can represent the above conditions as

sign b_{i} = sign (v_{i}^{(r+1)}) sign (1 − ∑_{q=1}^{r} γ_{q}) i = 1, 2, …, n.

Thus, if we adjust the components of b so that the above conditions are satisfied, then we are guaranteed that v^{(r+1)} is stored as an asymptotically stable equilibrium point. We may try to further adjust the components of b, if possible, to store the remaining patterns. Then, using the same matrices D, Λ, and V used to compute the original weight matrix W, we can choose an appropriate b to generate a new weight matrix W.

If b cannot be adjusted in the above way to accommodate all the patterns, then we may have to use the following procedure. First, recall the stability conditions that the patterns v^{(r+1)}, …, v^{(s)} should satisfy,

(Dv^{(k)} − [∑_{j=q}^{r} γ_{q} − 1] b)_{i} v_{i}^{(k)} > 0, i = 1, 2, …, n, k = r + 1, r + 2, …, s.

Using the requirement for the matrix D to be diagonally dominant, we arrive at stronger conditions of the form

(d_{ii} − ∑_{{j=1 \atop j≠i}}^{n} |d_{ij}|) + (1 − ∑_{j=q}^{r} γ_{q}) b_{i}v_{i}^{(k)} > 0, i = 1, …, n, k = r + 1, …, s.

Thus, we may use the above conditions and try to decrease the magnitude of the b_{i}’s until the conditions are met for all k = r + 1, …, s. However, we are not guaranteed to always satisfy the above conditions. If the conditions are satisfied, then using the same matrices D, Λ, and V used to compute the original weight matrix W, we choose an appropriate b to generate a new weight matrix W.

Example 2 We synthesize a gBSB based associative memory that is supposed to store the following three patterns:

v^{(1)} = [ \begin{matrix}−1 \\ −1 \\ 1 \\ 1 \\ 1 \end{matrix} ] , v^{(2)} = [ \begin{matrix}1 \\ 1 \\ −1 \\ −1 \\ −1 \end{matrix} ] , and v^{(3)} = [ \begin{matrix}1 \\ −1 \\ 1 \\ −1 \\ 1 \end{matrix} ] .

We first choose matrices D and Λ. Let

D = [ \begin{matrix}1 & 0 & 0 & 0 & −0.5 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & −0.2 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ] , Λ = −2I_{5}.

Set V = [ v^{(1)} v^{(2)} v^{(3)} ] and B = [ b b b ], where

b = [ 0.6 −0.5 0.7 −0.4 0.8 ]^{T} .

Note that rankV = 2 and the step size α = 0.9. Using the above we compute the weight matrix W to get

W = [ \begin{matrix}−0.6500 & 0.2667 & −0.2667 & −1.3500 & −0.2667 \\ 0.1250 & −1.0833 & −0.9167 & −0.1250 & −0.9167 \\ −0.1750 & −0.9500 & −1.0500 & 0.1750 & 0.9500 \\ −1.4000 & −0.0667 & 0.0667 & −0.6000 & 0.0667 \\ −0.2000 & −0.8667 & 0.8667 & 0.2000 & −1.1333 \end{matrix} ] .

We then check which vertices of H_{n} satisfy the sufficiency condition of Theorem 2 for asymptotic stability. In other words, we wish to identify the spurious states. In this example only the given patterns satisfy the condition of Theorem 2.

1.4 Learning

A pattern is learned by a memory if its noisy or an incomplete version presented to the memory is mapped back to this pattern. In our discussion of the proposed iterative learning, we will use the following theorem which allows one to iteratively compute the pseudo-inverse of a given matrix. The theorem can be found in Campbell and Meyer [4, page 54].

Theorem 4 Let U ∈ ℝ^{n×(r+1)} be partitioned by slicing off its last column, so that

U = [V ⋮y] .

Let

k = V^{†}y,
u = (I_{n} − V V^{†}) y,
z = \{ \begin{matrix}u^{†} & if u ≠ 0 \\ \frac{k^{T}V^{†}}{1+k^{T}k} & if u = 0. \end{matrix}

Then,

U^{†} = [ \begin{matrix}V^{†} − kz \\ z \end{matrix} ] .

Learning a new pattern requires updating the weight matrix W. This in turn involves augmenting the matrices V and B, and recomputing V^{†}. Augmenting V and B is straightforward, and updating V^{†} can be performed recursively using the above theorem. The above procedure guarantees that the new pattern will be stored as an asymptotically stable equilibrium point if it is linearly independent of the learned patterns. If, however, the pattern to be learned is a linear combination of the stored patterns, then we do not update the matrix V but rather modify the vector b as described at the end of the previous subsection. After that we update the weight matrix W. We now illustrate the iterative learning process on a numerical example.

Example 3 Consider Example 2. Suppose that we wish to add

v^{(4)} = [ −1 −1 −1 −1 1 ]^{T}

to the previously designed memory. We augment the pattern matrix to include v^{(4)} in it. Thus, we get V = [ v^{(1)} v^{(2)} v^{(3)} v^{(4)} ]. We also augment the matrix B by adding extra b column to it. We then update V^{†} using Theorem 4 and recompute the weight matrix W to obtain

W = [ \begin{matrix}0.1714 & 0.8143 & 0.8286 & −0.5286 & −0.8143 \\ 0.4643 & −0.8571 & −0.4643 & 0.2143 & −1.1429 \\ 0.7786 & −0.3143 & 0.2214 & 1.1286 & 0.3143 \\ −0.8286 & 0.3143 & 0.8286 & −0.0286 & −0.3143 \\ −0.4857 & −1.0571 & 0.4857 & −0.0857 & −0.9429 \end{matrix} ] .

Next, we check which vertices of H_{n} satisfy the condition of Theorem 2 for asymptotic stability. We found that only the given four patterns satisfy the condition of Theorem 2.

1.5 Forgetting

A pattern, previously stored, is forgotten or deleted from the memory if a stimulus that is a perturbed version of that pattern, when presented to the memory is not mapped back to this pattern. We now discuss the situation when we would like to update the weight matrix in such a way that the specified patterns are removed from memory. We refer to the process of removing patterns from the associative memory as forgetting. Our discussion uses the following theorem which can be considered as the inverse of Theorem 4. A general version of the theorem appears in Boullion and Odell [3, page 14].

Theorem 5 Let U ∈ ℝ^{n×(r+1)} be partitioned by slicing off its last column, so that

U = [V ⋮y] ,

and let its pseudoinverse U^{†} ∈ ℝ^{(r+1)×n} be partitioned by slicing off its last row, so that

U^{†} = [ \begin{matrix}S \\ z \end{matrix} ] .

Then,

V^{†} = \{ \begin{matrix}S + S \frac{yz}{1−zy} & if zy ≠ 1 \\ S − Sz^{†}z & if zy = 1. \end{matrix}

Proof Referring to Theorem 4, we first show that u = 0 if and only if zy ≠ 1, or equivalently u ≠ 0 if and only if zy = 1. Indeed, if u = 0, then

z = \frac{k^{T} V^{†}}{1 + k^{T} k}.

Hence,

zy = \frac{k^{T} V^{†}y}{1 + k^{T} k} = \frac{k^{T} k}{1 + k^{T} k} < 1.

On the other hand, if u ≠ 0, then

z = u^{†} = {(I_{n} − V V^{†})y}^{†} .

Taking into account the fact that u ≠ 0 and that u ∈ ℝ^{n}, its pseudoinverse is

u^{†} = (u^{T} u)^{−1}u^{T} = (y^{T} (I_{n} − V V^{†}) y)^{−1} y^{T} (I_{n} − V V^{†}) ,

since (I_{n} − V V^{†}) is an orthogonal projector. Hence,

zy = u^{†}y = 1.

We now prove the expressions for V^{†}. We start with the case when zy ≠ 1. It follows from Theorem 4 that

S = V^{†} − V^{†}yz = V^{†} (I_{n} − yz) .  (8)

Since zy ≠ 1, the matrix (I_{n} − yz) is invertible. Using the matrix inversion formula (??), from Chapter ??, gives

(I_{n} − yz)^{−1} = I_{n} + \frac{yz}{1 − zy} .  (9)

Applying formula (9) to (8) gives

V^{†} = S + S \frac{yz}{1 − zy} .

We now prove the expression for V^{†} for the case when zy = 1. From Theorem 4 we have

S = V^{†} − kz,  (10)

and hence, because z ≠ 0,

Sz^{†} = V^{†}z^{†} − k.  (11)

But in this case, u ≠ 0, and therefore

z^{†} = (u^{†})^{†} = u = (I_{n} − V V^{†}) y.

Substituting the above expression for z^{†} into (11), we get

Sz^{†} = V^{†} (I_{n} − V V^{†}) y − k
= (V^{†} − V^{†}) y − k
= −k.

We now substitute the above into (10) to obtain

V^{†} = S − Sz^{†}z,

which completes the proof of the theorem.

□

We can delete a pattern from the memory by first removing it from V , then updating V^{†} using Theorem 5, removing one column from B, and recomputing the weight matrix W. We illustrate the iterative forgetting process on the following numerical example.

Example 4 We consider Example 3. Suppose that we wish to delete

v^{(3)} = [ 1 −1 1 −1 1 ]^{T}

from the previously designed memory. We can use Theorem 5 to update V^{†}, that is to find the pseudoinverse of V = [ v^{(1)} v^{(2)} v^{(4)} ]. We also update the matrix B by deleting from it one column. We leave the remaining data unchanged. We recompute the weight matrix W to obtain

W = [ \begin{matrix}−0.7333 & 1.2667 & 0.1500 & 0.1500 & −1.2667 \\ 0.9167 & −1.0833 & −0.1250 & −0.1250 & −0.9167 \\ 0.0500 & 0.0500 & −0.3250 & 1.6750 & −0.0500 \\ −0.0667 & −0.0667 & 1.4000 & −0.6000 & 0.0667 \\ −0.8667 & −0.8667 & 0.2000 & 0.2000 & −1.1333 \end{matrix} ] .

We then check which vertices of H_{n} satisfy the condition of Theorem 2 for asymptotic stability. We found that only v^{(1)}, v^{(2)}, and v^{(4)}, satisfy the condition of Theorem 2 as desired.

The dynamics of the BSB model and its variants were further analyzed by Greenberg [9], Golden [7, 8], Grossberg[10], Hui and Żak [16], Hakl [11], Hui, Lillo, and Żak [15], Schultz [26], Lillo et al. [18], Anderson [1], Perfetti [23], Hassoun [12], Żak, Lillo, and Hui [28], Chan and Żak [5, 6], Park, Cho, and Park [22]. A continuous counterpart of the BSB model referred to as the linear system operating in a saturated mode was analyzed in Li, Michel, and Porod [17].

One of the first techniques used to design neural network associative memories is the outer product method. This method was first used by Hopfield in [13] and in [14]. The outer product method gives a network with a symmetric interconnection structure that does not necessarily store the desired patterns as equilibrium points of the network. The network designed using this method can efficiently store up to 0.15n arbitrary patterns and has learning capabilities.

The projection learning rule proposed by Personnaz, Guyon, and Dreyfus in [24] and in [25] gives a network with a symmetric interconnection structure that always stores the desired patterns as equilibrium points although not necessarily asymptotically stable. The network designed with this method can effectively store up to 0.5n desired patterns and has learning capabilities.

The eigenstructure method used by Li et al. [17] yields a neural network associative memory capable of storing any given pattern as an asymptotically stable equilibrium point. The network designed with this method is capable of effectively storing a number of patterns that may exceed the order of the network. However, the resulting network will have a symmetric interconnection structure. Furthermore, there are no provisions for learning for networks designed by the eigenstructure method.

In a series of papers, Michel, Farrell, and Porod [20], Michel and Farrell [19], Michel, Farrell, and Sun [21], and Yen and Michel [27] modified the eigenstructure method. The modified method can be used to design networks capable of storing on order of 0.5n patterns as asymptotically stable equilibrium points. Networks designed by this method need not have a symmetric interconnecting structures. Furthermore, learning is also incorporated into the method. Networks designed by the previous methods use energy functions techniques. A benefit of using energy functions is that the resulting networks are globally stable, that is, the networks’ trajectories always tend to some equilibrium points. On the other hand, if the modified method yields a nonsymmetric interconnecting structure, the resulting network is not guaranteed to be globally stable.

References

[1] J. A. Anderson. An Introduction to Neural Networks. A Bradford Book, The MIT Press, Cambridge, Massachusetts, 1995.

[2] J. A. Anderson, J. W. Silverstein, S. A. Ritz, and R. S. Jones. Distinctive features, categorical perception, probability learning: Some applications of a neural model. In J. A. Anderson and E. Rosenfeld, editors, Neurocomputing; Foundations of Research, chapter 22, pages 283–325. The MIT Press, Cambridge, MA, 1989. reprint from Psychological Review 1977, vol. 84, pp. 413–451.

[3] T. L. Boullion and P. L. Odell. Generalized Inverse Matrices. Wiley-Interscience, New York, 1971.

[4] S. L. Campbell and C. D. Meyer, Jr. Generalized Inverses of Linear Transformations. Dover Publications, Inc., New York, 1991.

[5] H. Y. Chan and S. H. Żak. On neural networks that design neural associative memories. IEEE Transactions on Neural Networks, 8(2):360–372, March 1997.

[6] H. Y. Chan and S. H. Żak. Real-time synthesis of sparsely interconnected neural associative memories. Neural Networks, 11(4):749–759, June 1998.

[7] R. M. Golden. The ”Brain-State-in-a-Box” neural model as a gradient descent algorithm. Journal of Mathematical Psychology, 30(1):73–80, 1986.

[8] R. M. Golden. Stability and optimization analyses of the generalized Brain-State-in-a-Box neural network model. Journal of Mathematical Psychology, 37(2):282–298, 1993.

[9] H. J. Greenberg. Equilibria of the Brain-State-in-a-Box (BSB) neural model. Neural Networks, 1(4):323–324, 1988.

[10] S. Grossberg. Nonlinear neural networks: Principles, mechanisms, and architectures. Neural Networks, 1(1):17–61, 1988.

[11] F. Hakl. Recall strategy of B-S-B neural network. Neural Network World, (1):59–82, 1992.

[12] M. H. Hassoun. Fundamentals of Artificial Neural Networks. A Bradford Book, The MIT Press, Cambridge, MA, 1995.

[13] J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA, Biophysics, 79:2554–2558, April 1982.

[14] J. J. Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Natl. Acad. Sci. USA, Biophysics, 81:3088–3092, May 1984.

[15] S. Hui, W. E. Lillo, and S. H. Żak. Dynamics and stability of the Brain-State-in-a-Box (BSB) neural models. In M. H. Hassoun, editor, Associative Neural Memories; Theory and Implementation, chapter 11, pages 212–224. Oxford University Press, New York, 1993.

[16] S. Hui and S. H. Żak. Dynamical analysis of the Brain-State-in-a-Box (BSB) neural models. IEEE Transactions on Neural Networks, 3(1):86–94, January 1992.

[17] J.-H. Li, A. N. Michel, and W. Porod. Analysis and synthesis of a class of neural networks: Linear systems operating on a closed hypercube. IEEE Transactions on Circuits and Systems, 36(11):1405–1422, 1989.

[18] W. E. Lillo, D. C. Miller, S. Hui, and S. H. Żak. Synthesis of Brain-State-in-a-Box (BSB) based associative memories. IEEE Transactions on Neural Networks, 5(5):730– 737, 1994.

[19] A. N. Michel and J. A. Farrell. Associative memories via artificial neural networks. IEEE Control Systems Magazine, 10(3):6–17, 1990.

[20] A. N. Michel, J. A. Farrell, and W. Porod. Qualitative analysis of neural networks. IEEE Transactions on Circuits and Systems, 36(2):229–243, February 1989.

[21] A. N. Michel, J. A. Farrell, and H.-F. Sun. Analysis and synthesis technique for Hopfield type synchronous discrete time neural networks with application to associative memory. IEEE Transactions on Circuits and Systems, 37(11):1356–1366, 1990.

[22] J. Park, H. Cho, and D. Park. Design of GBSB neural associative memories using semidefinite programming. IEEE Transactions on Neural Networks, 10(4):946–950, July 1999.

[23] R. Perfetti. A synthesis procedure for Brain-State-in-a-Box neural networks. IEEE Transactions on Neural Networks, 6(5):1071–1080, September 1995.

[24] L. Personnaz, I. Guyon, and G. Dreyfus. Information storage and retrieval in spin-glass like neural networks. Le Journal de Physique-Letters, 46(8):L–359–L–365, 1985.

[25] L. Personnaz, I. Guyon, and G. Dreyfus. Collective computational properties of neural networks: New learning mechnisms. Physical Review A, 34(5):4217–4228, 1986.

[26] A. Schultz. Collective recall via the Brain-State-in-a-Box network. IEEE Transactions on Neural Networks, 4(4):580–587, July 1993.

[27] G. Yen and A. N. Michel. A learning and forgetting algorithm in associative memories: Results involving pseudo-inverses. IEEE Transactions on Circuits and Systems, 38(10):1193–1205, 1991.

[28] S. H. Żak, W. E. Lillo, and S. Hui. Learning and forgetting in generalized Brain-State-in-a-Box (BSB) neural associative memories. Neural Networks, 9(5):845–854, July 1996.