2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why are there two votes to close? The question might get more and better attention on cstheory.se, but I don't see why it is off topic for MO. $\endgroup$ – Paul Siegel Nov 4 '15 at 0:24
  • $\begingroup$ Yes, I feel the problem is very mathematical in nature. In fact, the back-propagation algorithm and the RTRL algorithm were both discovered in optimization research first, and then later popularized in the computer science community :) $\endgroup$ – YKY Nov 4 '15 at 0:35
2
$\begingroup$

Perhaps you could start with the "easiest" approach, so called Echo State Networks, in which one is really just using the recurrence for feature generation and then using least squares (or Lasso et cetera) to fit to data.

Another idea would be to treat time as just another observation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.