4.2 Recall algorithm

The goal of the recall is to complete a pattern $\bf p$ whose components are only partially given (Hoffmann and Möller, 2003). The resulting pattern $\bf z$ shares the components of $\bf p$ that are defined as input.

After learning, the data distribution is represented by a collection of hyper-ellipsoids; each has a center $\bf c_{j}^{}$, direction vectors $\bf w_{j}^{l}$ (principal axes), semi-axes lengths $\sqrt{{\lambda _j^l}}$, and a residual variance $\sigma^{2}_{j}$ (in any direction orthogonal to the span of the principal axes). The $\bf w_{j}^{l}$ are the eigenvectors of a local principal component analysis, and the $\lambda_{j}^{l}$ are the corresponding eigenvalues. The hyper-ellipsoids are iso-potential surfaces of the normalized Mahalanobis distance plus reconstruction error (see section 3.2.1),

$$\bf z \bf y_{j}^{T} \Lambda \bf y_{j}^{} {\frac{{1}}{{\sigma^2_j}}} \xi \xi \bf y_{j}^{T} \bf y_{j}^{} \Lambda \sigma^{2}_{j}$$ (4.1)

The dimensionality of the pattern space is d, and q is the number of principal components. $\xi$_j is the displacement from the center, $\xi$_j = $\bf z$ - $\bf c_{j}^{}$. Its representation in the local coordinate system of the ellipsoid is $\bf y_{j}^{}$ = $\bf W_{j}^{T}$$\xi$_j. The eigenvectors $\bf w_{j}^{l}$ are the columns of $\bf W_{j}^{}$. $\Lambda$_j is a diagonal matrix containing the eigenvalues $\lambda_{j}^{l}$.

An input to the network (one part of the components of $\bf p$) defines the offset of a constrained space $\bf z$($\eta$) spanning the space of all possible output values:

$$\bf z \eta \bf M \eta \bf p$$ (4.2)

$\eta$ is a collection of s free parameters (s being the dimension of the network output). $\bf M$ is a d×s matrix, which is chosen such that the constrained space is aligned with the coordinate axes.

The recall of the complete pattern happens in two steps. First, for each unit j, determine the point $\hat{{{\bf z}}}_{j}^{}$ that yields the smallest potential value (4.1) on the constrained subspace. Second, choose the unit j^* that gives the smallest of these minimal potential values {E_j($\hat{{{\bf z}}}_{j}^{}$)}. The corresponding $\hat{{{\bf z}}}_{{j^*}}^{}$ yields the desired output values (figure 4.2).

Figure 4.2: Pattern recall. The ellipses are iso-potential curves of the error measure E_j for each unit j. The input x defines the constraint's offset from zero. In this subspace, the unit j^* and the point (circle) that result in the smallest error E_j^* are chosen. This point's y value is the desired output.

The error E_j as a function of the free parameters $\eta$ can be written as:

$$\bf z \eta \bf M \eta \pi \bf W_{j}^{} \Lambda \bf W_{j}^{T} {\frac{{1}}{{\sigma^2_j}}} \bf I \bf W_{j}^{} \bf W_{j}^{T} \bf M \eta \pi$$ =

$$\Lambda \sigma^{2}_{j}$$ + (4.3)

with $\pi$_j = $\bf p$ - $\bf c_{j}^{}$. We derive with respect to $\eta$:

$${\frac{{\partial{E_j}}}{{\partial\boldsymbol{\eta}}}} \bf M^{T}_{} \bf D_{j}^{} \bf M \eta \bf M^{T}_{} \bf D_{j}^{} \pi$$ (4.4)

with

$$\bf D_{j}^{} \bf W_{j}^{} \Lambda \bf W_{j}^{T} {\frac{{1}}{{\sigma^2_j}}} \left(\vphantom{{\bf I}- {\bf W}_j {\bf W}_j^T }\right. \bf I \bf W_{j}^{} \bf W_{j}^{T} \left.\vphantom{{\bf I}- {\bf W}_j {\bf W}_j^T }\right)$$ (4.5)

Setting the derivative equal to zero yields,

$$\hat{{\boldsymbol{\eta}}}_{j}^{} \bf A_{j}^{} \bf p \bf c_{j}^{}$$ (4.6)

with

$$\bf A_{j}^{} \bf M^{T}_{} \bf D_{j}^{} \bf M \bf M^{T}_{} \bf D_{j}^{}$$ (4.7)

After the input and output dimensions have been selected, $\bf A_{j}^{}$ needs to be computed only once for each unit.

The function E($\eta$) is convex. Therefore, $\hat{{\boldsymbol{\eta}}}_{j}^{}$ is the only minimum. Thus, $\hat{{{\bf z}}}_{j}^{}$ = $\bf M$$\hat{{\boldsymbol{\eta}}}_{j}^{}$ + $\bf p$ is the point with the smallest potential on the constraint. Next, j^* can be chosen, and the resulting $\hat{{\bf z}}_{{j^*}}^{}$ concludes the algorithm. For each input a unique output is given, and local minima as described in section 4.1.2 are avoided.