Summary: I want to train a recurrent network to output some answers, but the recurrent network is allowed to re-iterate through itself a flexible number of times for each input-output pair.
Why this is important:
In traditional neural network learning, we are given pairs of input-outputs, the network is trained to recognize or approximate such a map (with extrapolation or generalization, so to speak).
In this new setting, the input can be mapped to the output via:
- 1 iteration of the network, OR
- 2 iterations of the network, OR
- 3 iterations... etc etc
So there is potentially many more input-output relations that can be recognized by a network of the same size.
For example, the new type of network can recognize the digits of $22 / 7=3.\dot{1}\dot{4}\dot{2}\dot{8}\dot{5}\dot{7}....$ via periodic iterations, but a traditional network can only memorize a limited part of the sequence. In short, this is a much more powerful kind of learning machine.
Details:
Define $F$ as the standard multi-layer feed-forward perceptron: \begin{equation} F(\mathbf{x}) = \Theta( W_1 \circ \Theta( W_2 \circ .... W_L(\mathbf{x}))) \end{equation} where $\Theta$ is the sigmoid function and $W_i$ is the weight matrix for layer $i$, with a total of $L$ layers.
The weights $W_i$ can be learned by standard back-propagation if a set of inputs and expected outputs are given.
Now connect the (last-stage) output of $F$ back to its input layer (assuming they are of the same dimension). Then we have a special recurrent network, call it $R$.
In other words, if we let the network $R$ iterate $n$ times, its output would be: $$ R^n(x) = F \circ F \circ ... (x) \quad n \mbox{ times}$$ One iteration means the input passing through the $L$ layers of $F$ once.
The RTRL (real-time recurrent learning) algorithm proposed by Williams and Zipser in 1989 can be used to train $R$ to approximate a sequence of output values (the output of $R$ is just the vector at the last layer, and is the same vector fed back to the input layer; the first element of the sequence is the initial input).
So far so good.
But now I relax the requirement that the sequence has to respect the time index strictly: it is OK for the network to output some values that are not the expected answer, until $n$ iterations later, and $n$ can be variable from 1 to $N$.
When the network outputs something that is not the answer, it can set a component of the output vector to 1.0 to distinguish it from an attempted answer.
Put it another way, the expected output sequence can be interlaced with "dummy" values for arbitrary numbers of times, as long as the order is respected.
In other words, the goal of learning is to learn the weights of $R$ to satisfy the set of equations: \begin{equation} R^n (d_j) = \hat{d_j} \quad , \quad j \in \mbox{data set} \end{equation} where $\{d_j, \hat{d_j}\}$ are pairs of input and expected output. The catch is that each $n$ in the above equations are unknown variables.
The standard practice is to apply gradient descent by differentiating the error: $$ \epsilon = \frac{1}{2} \sum_j (\hat{d_j} - R^n(d_j))^2 $$ as partial derivative w.r.t. the $W$'s. But since $n$ is variable (and possibly dependent on $W$), I don't know how to calculate the gradient.
A theorem by Lo (1993) states that under mild regularity conditions, a dynamical system can be approximated to any accuracy with respect to an $L_p$ criterion by a recurrent neural network. So, it is reasonable to believe that given enough neurons in the network, the desired operator $R$ should exist. But I cannot formulate a learning algorithm to find it.
Any suggestions on how to tackle this problem? Just some general ideas would be greatly appreciated.
PS: I am thinking about using Hebbian learning which is unsupervised, but this is just a hunch without any specific details.
