Sequence Problems

Why order matters for speech, text, and control

12.1 What You Will Learn

Everything we have built so far treats each input as if it exists in isolation. An MLP takes a fixed-size vector, multiplies it through some weight matrices, and produces an output with no notion of what the previous input was or what the next one will be. A CNN slides a kernel across the input and detects local patterns, but each window position is computed independently and the order of the windows does not matter. If you shuffled the positions in a feature map, the CNN would not know anything had changed.

For many problems, that independence is fine. Classifying a single image or deciding whether a point is inside a circle does not require knowing what happened before. But there is a large and important class of problems where the order of the inputs carries most of the meaning. Speech is a sequence of sounds where the same syllable means different things depending on what came before it. Text is a sequence of tokens where every word is shaped by the words around it. A control system reading sensor data over time needs to know whether a temperature is rising or falling, not just its current value. In all of these cases, the relationship between consecutive inputs is the signal, and an architecture that processes each input independently is throwing that signal away. In this chapter we will look at why MLPs and CNNs fail at these problems and build the motivation for the recurrent architectures we construct in Chapters 13 through 17.

12.2 The Problem

Three tasks make the shape of the difficulty clear, and none of them is exotic.

The first is predicting the next character in a stream of text. Given “hel” the answer is “l”, and given “hell” the answer is “o”, which means the prediction turns on everything that arrived before rather than on the character currently under the cursor. Feed the same letter “l” to the model twice and it must answer differently each time, purely on the strength of what preceded it.

The second is counting ones in a bit stream. Given 1, 0, 1, 1, 0, 1 the answer is 4, and there is no way to reach that number without accumulating a running total across the whole sequence. No single bit tells you anything about the total, and no fixed window over three or four bits does either.

The third is robot control, where an arm receives sensor readings over time and has to decide what the motors should do next. A ball moving left calls for one action and a ball that was moving left but has just reversed calls for another, yet at the instant you sample them the two situations can report an identical position. The correct command depends on the trajectory rather than the coordinate.

What all three share is a requirement for memory that persists across time steps. The network has to take inputs one at a time and carry an internal state forward, and that state has to summarize what it has already seen well enough to shape what it does next.

12.3 Why MLPs Fail

Let us try to solve a sequence problem with the architecture we already have and watch exactly where it gives out. The task is counting the number of 1s in a binary sequence of length 4, which gives 16 possible inputs and an output somewhere between 0 and 4.

/* 067_Failing_MLP.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* The MLP approach, treating the 4-bit sequence
   as 4 independent inputs */

static float sigmoid(float z)
{
    return 1.0f / (1.0f + expf(-z));
}
static float randf(void)
{
    return (float)rand() / RAND_MAX;
}

#define N_HID 8
#define N_IN 4
#define N_PARAMS (N_IN*N_HID + N_HID + N_HID + 1)

static float forward(const float *p, const float *x, 
                     float *h)
{
    int i, j;
    for (i = 0; i < N_HID; i++) {
        float z = p[N_IN * N_HID + i];
        for (j = 0; j < N_IN; j++)
            z += p[i * N_IN + j] * x[j];
        h[i] = sigmoid(z);
    }
    { int bw = N_IN*N_HID + N_HID;
      float z = p[bw + N_HID];
      for (i = 0; i < N_HID; i++)
          z += p[bw + i] * h[i];
      return z; /* linear output for regression */
    }
}

int main(void)
{
    /* Generate all 16 possible 4-bit sequences */
    float X[16][N_IN];
    float T[16];
    int s, b;

    for (s = 0; s < 16; s++) {
        int count = 0;
        for (b = 0; b < N_IN; b++) {
            X[s][b] = (s >> b) & 1 ? 1.0f : 0.0f;
            count += (int)X[s][b];
        }
        T[s] = (float)count;
    }

    printf("The bit-counting problem (length 4):\n\n");
    printf("  Input       Target\n");
    for (s = 0; s < 16; s++) {
        printf("  %.0f%.0f%.0f%.0f      %.0f\n",
               X[s][0], X[s][1], X[s][2], 
                   X[s][3], T[s]);
    }

    printf("\nAn MLP can solve this because ALL "
           "inputs are visible\n");
    printf("at once. It sees the full 4-bit vector "
           "as a fixed input.\n");
    printf("\nBut what if the sequence length "
           "varies? What if it is\n");
    printf("100 bits? 1000 bits? The MLP input "
           "size is fixed.\n");
    printf("You would need a different MLP for "
           "each length.\n");

    printf("\nFor length 4: %d parameters\n", N_PARAMS);
    printf("For length 100: %d parameters "
           "(100*8+8+8+1)\n",
           100 * N_HID + N_HID + N_HID + 1);
    printf("For length 1000: %d parameters\n",
           1000 * N_HID + N_HID + N_HID + 1);

    printf("\nThe parameter count grows linearly "
           "with sequence length.\n");
    printf("And a model trained on length 100 "
           "cannot handle length 101.\n");

    return 0;
}
Figure 12-1. Every four bit pattern counted

Figure 12-1 counts every four bit pattern and then works out what the same MLP would cost at length 1000. Look at the enumeration first, because the MLP does succeed at the stated task and it is important to be honest about that. All 16 patterns are listed with their targets, and 1010 maps to 2 while 1110 maps to 3, exactly as they should. An MLP with 49 parameters can memorize this table without difficulty, since every bit of the input is visible simultaneously and the network only has to learn a fixed function of a fixed vector.

The failure arrives in the parameter counts at the bottom of the output. Length 4 costs 49 parameters. Length 100 costs 817, which the program breaks out as 100*8 + 8 + 8 + 1 so you can see where the growth comes from, and length 1000 costs 8017. Every extra position in the sequence buys another eight weights in the first layer, so the model grows in direct proportion to the longest input you ever intend to handle.

The deeper problem is not the size, though, and the two should be kept apart. A model trained on length 100 cannot process length 101 at all. Not badly, not with degraded accuracy, but not at all, because the input layer has exactly 100 slots and a 101 bit sequence does not fit in them. You would train a separate network for every length you expect to encounter, and each one would learn the counting rule again from scratch with no benefit from the others having already learned it.

12.4 The Sequential Approach

Suppose the network never sees the whole sequence at once. It reads one bit, updates something it remembers, reads the next bit, updates again, and keeps going until the input runs out. Whatever it is holding at the end is the answer. Before reaching for a neural network, write that loop in plain C, because the structure we need is easier to see when nothing else is in the way.

/* 068_Sequence_Modes.c */
#include <stdio.h>

int main(void)
{
    /* Process a sequence one element at a time */
    int sequence[] = { 1, 0, 1, 1, 0, 
                       1, 0, 1, 1, 0 };
    int length = 10;
    int state = 0;  /* the "memory" */
    int t;

    printf("Sequential processing with state:\n\n");
    printf("  step  input  state\n");
    for (t = 0; t < length; t++) {
        state = state + sequence[t];   /* update rule */
        printf("  %3d     %d      %d\n", t,
               sequence[t], state);
    }
    printf("\n  Final state (count of 1s): "
           "%d\n", state);

    printf("\nThe key properties:\n");
    printf("  1. Process one input at a time\n");
    printf("  2. Maintain a state (memory) across "
           "steps\n");
    printf("  3. The update rule is the SAME at "
           "every step\n");
    printf("  4. Works for ANY sequence length\n");
    printf("\nThis is exactly what a recurrent "
           "neural network does.\n");
    printf("Replace the fixed update rule with "
           "a learned one.\n");

    return 0;
}
Figure 12-2. A hand written state update counting ones, one step at a time

Figure 12-2 counts ones with a hand written state update, one step at a time. Follow the state column down the output and the mechanism is completely visible. Step 0 reads a 1 and the state goes to 1. Step 1 reads a 0 and the state stays at 1, because adding zero changes nothing. By step 5 the state is 4, by step 9 it is 6, and 6 is the count of ones in the sequence. There is no training and no learning anywhere in the program, just one line of arithmetic run ten times.

The four properties the program prints are the ones that matter, and each of them survives into the recurrent networks we build later. Inputs arrive one at a time rather than all at once. A state persists between steps and carries information forward. The update rule is identical at every step, so there is one rule rather than ten. Because the rule does not depend on position, the same loop handles a sequence of any length without modification.

That last property is the one the MLP could not manage at any parameter count. Change length from 10 to 10000 and this program still works, still uses one integer of memory, and still contains exactly one update rule. Compare that against the 8017 parameters the MLP needed for length 1000 and the trade being offered becomes clear. We give up seeing everything at once, and in exchange the cost of the model stops depending on how long the input is.

Everything that follows in this chapter, and everything in Chapters 13 through 17, comes from taking state = state + sequence[t] and replacing that fixed rule with a learned one.

12.5 A Learned Update Rule

So let us make that replacement. At each time step the network receives the current input and the previous state, and it produces a new state. The state is no longer a single integer but a vector of floats, and the update is a function with weights in it rather than an addition we chose by hand.

/* 069_Learned_State.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static float sigmoid(float z)
{
    return 1.0f / (1.0f + expf(-z));
}
static float randf(void)
{
    return (float)rand() / RAND_MAX;
}

/* A simple recurrent cell:
   new_state = sigmoid(W_x * input
                       + W_h * old_state + bias) */

#define STATE_SIZE 4

typedef struct {
    float w_x[STATE_SIZE];      /* input weight */
    /* state-to-state weight */
    float w_h[STATE_SIZE][STATE_SIZE];
    float b[STATE_SIZE];        /* bias */
    float w_out[STATE_SIZE];    /* output weight */
    float b_out;                /* output bias */
}
RNNCell;

static void rnn_step(const RNNCell *cell, float input, 
                      const float state_in[STATE_SIZE], 
                      float state_out[STATE_SIZE])
{
    int i, j;
    for (i = 0; i < STATE_SIZE; i++) {
        float z = cell->b[i] + cell->w_x[i] * input;
        for (j = 0; j < STATE_SIZE; j++)
            z += cell->w_h[i][j] * state_in[j];
        state_out[i] = sigmoid(z);
    }
}

static float rnn_output(const RNNCell *cell, 
                         const float state[STATE_SIZE])
{
    float z = cell->b_out;
    int i;
    for (i = 0; i < STATE_SIZE; i++)
        z += cell->w_out[i] * state[i];
    return z;  /* linear output */
}

int main(void)
{
    RNNCell cell;
    float state[STATE_SIZE];
    int i, j;

    srand(42);

    /* Random initialization */
    for (i = 0; i < STATE_SIZE; i++) {
        cell.w_x[i] = randf() * 2 - 1;
        cell.b[i] = 0;
        cell.w_out[i] = randf() * 2 - 1;
        for (j = 0; j < STATE_SIZE; j++)
            cell.w_h[i][j] = randf() * 2 - 1;
    }
    cell.b_out = 0;

    /* Process a sequence */
    float sequence[] = { 1, 0, 1, 1, 0, 1, 0, 1 };
    int length = 8;

    /* Initialize state to zeros */
    for (i = 0; i < STATE_SIZE; i++)
        state[i] = 0.0f;

    printf("Processing sequence through untrained "
           "RNN cell:\n\n");
    printf("  step  input  state                "
           "        output\n");
    for (int t = 0; t < length; t++) {
        float new_state[STATE_SIZE];
        rnn_step(&cell, sequence[t], state, new_state);

        float out = rnn_output(&cell, new_state);

        printf("  %3d     %.0f    [", t, sequence[t]);
        for (i = 0; i < STATE_SIZE; i++)
            printf("%.3f%s", new_state[i],
                   i < STATE_SIZE - 1 ? ", " : "");
        printf("]  %.3f\n", out);

        /* Copy new state for next step */
        for (i = 0; i < STATE_SIZE; i++)
            state[i] = new_state[i];
    }

    printf("\nThe state vector changes at every "
           "step.\n");
    printf("It encodes information about all "
           "past inputs.\n");
    printf("With training, the output would learn "
           "to count 1s.\n");
    printf("The SAME cell is used at every time "
           "step.\n");
    printf("\nParameters: %d (independent of "
           "sequence length)\n",
           STATE_SIZE + STATE_SIZE*STATE_SIZE
               + STATE_SIZE +
           STATE_SIZE + 1);

    return 0;
}
Figure 12-3. An untrained cell moving its state vector at every step

Figure 12-3 has an untrained cell moving its state vector at every step. The numbers in the state column are meaningless and that is expected, because this cell has never been trained. What matters is the movement. At step 0 the state reads [0.282, 0.568, 0.410, 0.532] and at step 1, after a 0 arrives, it becomes [0.381, 0.382, 0.447, 0.484]. Every component moved, and none of them moved the same distance.

Now compare step 1 with step 4, where the input is also 0. The states are [0.381, 0.382, 0.447, 0.484] and [0.382, 0.408, 0.458, 0.475], close to each other but not equal. The same input produced a different state, which can only be because the histories leading into those two steps were different. That difference is the memory, and it is already present in an untrained network purely as a consequence of the architecture.

The last line of the output is the one to hold onto. Twenty nine parameters, independent of sequence length. Not 817 for a hundred inputs and not 8017 for a thousand, but 29 for any length whatsoever, because the same weights are reused at every time step instead of each position owning its own. This is weight sharing in time, and it is the direct counterpart to the way convolution in Chapter 8 shared one kernel across every spatial position.

12.6 Why Order Matters

Everything so far shows that a state accumulates, but accumulation alone would be satisfied by a bag of inputs summed in any order. The property that actually separates a sequence model from a bag of words is sensitivity to arrangement, so let us feed four sequences containing exactly the same inputs in four different orders and see whether the final states differ.

/* 070_Order_Matters.c */
#include <stdio.h>
#include <math.h>

static float sigmoid(float z)
{
    return 1.0f / (1.0f + expf(-z));
}

/* A simple 2-state RNN cell with fixed weights
   chosen to make order effects visible */

static void step(float input, float state[2], 
                 float new_state[2])
{
    new_state[0] = sigmoid(2.0f * input
                           + 1.5f * state[0]
                           - 0.5f * state[1] - 1.0f);
    new_state[1] = sigmoid(-1.0f * input
                           + 0.5f * state[0]
                           + 1.5f * state[1] - 0.5f);
}

static void run_sequence(const float *seq, int len, 
                         const char *label)
{
    float state[2] = { 0, 0 };
    float new_state[2];
    int t;

    printf("  %s: ", label);
    for (t = 0; t < len; t++) {
        step(seq[t], state, new_state);
        state[0] = new_state[0];
        state[1] = new_state[1];
    }
    printf("final state = [%.4f, %.4f]\n",
           state[0], state[1]);
}

int main(void)
{
    float seq_a[] = { 1, 1, 0, 0 };
    float seq_b[] = { 0, 0, 1, 1 };
    float seq_c[] = { 1, 0, 1, 0 };
    float seq_d[] = { 0, 1, 0, 1 };

    printf("Same inputs, different order -> "
           "different final state:\n\n");

    run_sequence(seq_a, 4, "1,1,0,0");
    run_sequence(seq_b, 4, "0,0,1,1");
    run_sequence(seq_c, 4, "1,0,1,0");
    run_sequence(seq_d, 4, "0,1,0,1");

    printf("\nAll four sequences have the same "
           "two 1s and two 0s.\n");
    printf("An MLP treating them as a bag of "
           "inputs would produce\n");
    printf("the same output for all four. The RNN "
           "distinguishes them\n");
    printf("because it processes inputs in order "
           "and the state at\n");
    printf("each step depends on the history.\n");

    return 0;
}
Figure 12-4. Four sequences ending in four different states

Figure 12-4 feeds in four sequences with the same ones and zeros. All four end somewhere different. Rising then falling, which is 1,1,0,0, lands at [0.3816, 0.6603]. Falling then rising, which is 0,0,1,1, lands at [0.8770, 0.3644]. Those two are not slight variations on each other, since the first component more than doubles between them and the second nearly halves.

The alternating pairs are worth reading as well. Sequence 1,0,1,0 ends at [0.5070, 0.6207] and sequence 0,1,0,1 ends at [0.8111, 0.4086], so even two orderings that share the same alternating rhythm and differ only in phase produce clearly separated states. An MLP fed the sum of these inputs would see the number two in all four cases and would have no way to tell them apart.

This is not a curiosity, it is the whole reason the architecture exists. The same phonemes in a different order are a different word, the same words in a different order are a different sentence, and the same positions in a different order describe motion in the opposite direction. A network that cannot distinguish [0.3816, 0.6603] from [0.8770, 0.3644] cannot do any of those jobs.

12.7 Sequence-to-Sequence vs Sequence-to-One

A sequence model can be read in two places, and which one you choose depends on what the task wants back. Reading only the final state gives you sequence-to-one, which suits bit counting, sentiment analysis, and any classification where the whole input maps to a single answer. Reading the state at every step gives you sequence-to-sequence, which suits language modeling, speech recognition, and part of speech tagging, where each position needs its own output.

The distinction is entirely about where you attach the output layer. The recurrence underneath is identical in both cases, so the same cell serves both patterns without modification.

/* 071_Sequence_Modes.c */
#include <stdio.h>
#include <math.h>

static float sigmoid(float z)
{
    return 1.0f / (1.0f + expf(-z));
}

int main(void)
{
    float seq[] = { 1, 0, 1, 1, 0, 1 };
    int len = 6;

    /* Simulate a counting RNN, hand-tuned
       rather than trained */
    float state = 0.0f;
    int t;

    printf("Sequence-to-sequence (output at "
           "every step):\n\n");
    printf("  step  input  running_count\n");
    for (t = 0; t < len; t++) {
        state += seq[t];
        printf("  %3d     %.0f       %.0f\n", t,
               seq[t], state);
    }

    printf("\nSequence-to-one (output only at "
           "the end):\n");
    printf("  Final count: %.0f\n", state);

    printf("\nSequence-to-sequence tasks:\n");
    printf("  - Language modeling (predict next "
           "word at each position)\n");
    printf("  - Speech recognition (output a "
           "letter per frame)\n");
    printf("  - Part-of-speech tagging (label "
           "each word)\n");

    printf("\nSequence-to-one tasks:\n");
    printf("  - Sentiment analysis (is this "
           "review positive?)\n");
    printf("  - Counting (how many 1s in this "
           "bit stream?)\n");
    printf("  - Classification (what language "
           "is this text?)\n");

    return 0;
}
Figure 12-5. Sequence to sequence and sequence to one

Figure 12-5 reads the same run two ways. The top table is the sequence-to-sequence reading. Every one of the six steps emits a running count, so the output is a sequence the same length as the input, and you can watch the count climb from 1 at step 0 to 4 at step 5. Notice that steps 1 and 4 both emit no change, because both read a 0, and a model producing one output per position has to be comfortable emitting the same value twice in a row.

Underneath it, the sequence-to-one reading discards all of that and reports only the final count of 4. Nothing about the network changed between the two readings and no second pass was made over the input. The same run produced both, and the only difference is which state we chose to look at.

Two lists follow, and they are worth reading as a rough guide to which pattern a new problem calls for. If the answer has one part, take the final state. If the answer has as many parts as the input has positions, take every state. Chapter 18 handles the harder middle case where the output is a sequence of a different length than the input, which needs both patterns joined together.

12.8 What Comes Next

We now have the problem stated properly. Sequential data needs a network that carries memory across time steps, and the update rule that maintains that memory has to be learned rather than chosen by hand. Chapter 13 builds exactly that, the recurrent neural network, and gets it training on the counting task from this chapter.

The basic RNN has a flaw serious enough to need its own chapter. It forgets, and it forgets faster than you would guess, which Chapter 14 makes visible in real gradient measurements before Chapters 15 and 16 build the LSTM and the GRU to repair it. If you want to read ahead in a working implementation, KANN provides all three as kann_layer_rnn, kann_layer_lstm, and kann_layer_gru.

12.9 Key Takeaways

12.10 Exercises