Yesterday’s Topics:
Basics of neural networks in old and new schools TensorFlow: creating graphs and running them TensorFlow code practice on Colab to run a model on MNIST Link to updated Colab shared for everyone to make a new copy

Colab Introduction:
Website connecting to a machine with GPU access for training models Allows users to run code and train their own models

Simple Model Overview:
Created a simple model with one hidden and one output layer for MNIST digit classification Various optimizers were tested on this model, showing good performance Two layers worked well, but more layers caused training issues Changes to nonlinearities (tanh and sigmoid) worked effectively Tuning was done in a distributed fashion, with results shared in a document

Task Overview:
Input given as an image represented by a vector or tensor Tensor shape convention: [batch size, height, width, channels/depth]

Introduction:
In this discussion, Lukasz Kaiser explores the concept of generating complex objects like sentences, images, videos, and music using neural networks. He presents the task of generating sequences of bits or digits as a starting point for understanding the challenges involved.

Sequence Generation with Neural Networks:
A neural network can be used to generate a sequence of items by stacking multiple layers, each generating one or more outputs. The network is trained on input-output pairs, learning to map input sequences to corresponding output sequences.

Patterns in Sequences:
Given a set of sequences, it can be challenging to identify a definitive pattern, as multiple interpretations may exist. For example, a sequence of numbers could represent a binary number written in little-endian format, indicating a multiplication operation, but other interpretations are also possible.

Kolmogorov Complexity:
Kolmogorov complexity measures the complexity of a pattern by finding the shortest computer program that can generate the output sequence from the input sequence. It provides a theoretical framework for defining the “correct” pattern when multiple interpretations exist.

Practical Considerations:
While Kolmogorov complexity offers a theoretical basis for pattern identification, it may not be practical in real-world applications. Practical solutions often involve finding patterns that minimize errors or fit within certain constraints, such as polynomial time complexity.

Neural Networks and Computational Complexity:
Neural networks are tasked with mapping inputs to outputs, with the goal of finding a suitable program, often represented as a neural network, to perform this task. The complexity of a neural network is determined by its number of layers and the computational complexity of each layer. A single-layer neural network performs vector summations and multiplications with a non-linearity applied, which falls into a computational complexity class.

Polynomial Time Computability:
A neural network with n inputs and three layers can be computed in polynomial time. It multiplies by weights, adds, and applies ReLU (the rectified linear unit) activation function. This operation is parallelizable as each layer operates independently, making it more efficient than sequential computation.

Threshold Circuits:
Threshold circuits, denoted as TC0, involve summing and thresholding instead of computing and/or. This complexity class is considered weaker than polynomial time but relevant to neural networks. Neural networks can be seen as threshold circuits with continuous non-linearities that can be reduced to threshold circuits by adding layers.

AC0 Class:
AC0 is a computational complexity class involving circuits with OR, AND, or XOR gates. Threshold circuits are similar to AC0, with the addition of summation and thresholding instead of the send and OR operations. The thresholding function is irrelevant, and the circuits operate on bits with weights and sums expressed as 0’s and 1’s.

Neural Networks and Bits:
Neural networks can train with activations and weights represented as 3 or 5 bits. Modern neural networks are essentially close to bitwise circuits. TC0 serves as an abstraction with a real threshold, resulting in a 0 if the value is below and a 1 if it’s above the threshold.

Threshold Circuits and Parity:
Threshold circuits are a more powerful class than AC circuits because they lack the parity problem that AC circuits face. Threshold circuits do not have an equivalent concept of parity, making them a more general class.

Separating Results:
Few separation results are known for threshold circuits. For AC circuits, a hierarchy can be proven, but for threshold circuits, the depth hierarchy remains open. All related questions are essentially unsolved.

Uniformity of Circuits:
Circuits have an input of fixed size, so the question arises of how to handle variable-sized inputs. Circuits are typically constructed in a uniform way, with a polynomial-time program generating the circuit or formula for each input length.

Network Complexity with Standard Connections:
In standard connections like residual connections, the overall network complexity remains relatively unchanged, even with multiple layers. Recurrence, however, significantly alters the complexity landscape.

Recurrence Changes Complexity:
With recurrence, the complexity increases rapidly, particularly if it is executed numerous times (n times or 2 to the n times). Recurrent networks can potentially simulate Turing machines, as they can manipulate information left, right, and internally.

Fixed Number of Layers:
Networks with a limited number of layers (e.g., three layers) may be unable to compute specific tasks. Although not mathematically proven, this limitation is widely accepted.

Long Multiplication Task:
A task requiring the network to perform long multiplication illustrates the need for expressiveness and learning capabilities. Gradient descent, the primary training method for neural networks, may be inadequate for finding optimal solutions for such complex tasks.

RNN Cell Structure:
RNNs, a type of neural network with recurrence, have input, state, and output components. Each cell iterates through an input sequence, producing an output at each step based on its state and input. The simplest RNN cell involves a non-linearity applied to a linear combination of the current state and input.

Gradient Propagation Challenges:
Training RNNs becomes increasingly difficult as the sequence length increases due to vanishing gradients. Tricks like adding a residual connection help alleviate this problem, allowing for better gradient propagation.

RNN’s Limited Computational Power:
RNNs’ constant memory size limits their ability to compute complex functions like multiplication. They lack Turing completeness due to their restricted memory complexity. RNNs can be viewed as finite state automata with limited computational power.

Neural Turing Machines:
NTMs address RNNs’ limitations by introducing an external tape for reading and writing. NTMs incorporate a variable-size memory vector, allowing for universal computational capabilities. Attention mechanisms are used to read and write from the tape, enabling soft queries and differentiation.

Challenges in Training NTMs:
Training NTMs is complex due to the need to backpropagate through reads and writes at every step. The variable-size memory and tape require specialized training techniques to ensure meaningful gradients. Long multiplication on NTMs would require a significant number of operations, making training impractical.

Comparison of RNNs and NTMs:
RNNs have constant-size memory and process inputs of arbitrary length but are limited in computational power. NTMs have variable-size memory and processing, making them universal but difficult to train.

Introduction to Neural GPUs:
Neural GPUs employ recurrent convolutions on the input to address the vanishing gradient problem in RNNs.

Vanishing Gradients in Recurrent Neural Networks:
Recurrent neural networks (RNNs) with multiple non-linear layers can suffer from vanishing gradients during backpropagation. This occurs because the gradients of the ReLU activation function, which is commonly used in RNNs, can be 0 for some inputs, causing information to vanish.

Residual Connections:
To address the vanishing gradient problem, residual connections were introduced. Residual connections add the input of a layer to its output, allowing gradients to flow more easily through the network. This helps prevent the vanishing gradient problem and enables the network to learn long-term dependencies more effectively.

Normalization and Gated Mechanisms:
To prevent the accumulation of large values in residual connections, layer normalization or special gates can be used. Layer normalization normalizes the activations of a layer before adding them to the output. Gated mechanisms, such as the Gated Recurrent Unit (GRU), allow the network to control which parts of the information are retained or forgotten at each time step.

Summary:
Vanishing gradients can hinder the training of RNNs with multiple non-linear layers. Residual connections mitigate this problem by adding the input to the output of each layer, ensuring that gradients can flow more easily. Layer normalization or gated mechanisms can be used to prevent the accumulation of large values in residual connections.

Background Information:
Residual layers involve adding the previous output to the current input in deep neural networks. This approach can cause normalization issues and lead to difficulties in determining what information is forgotten or retained in the network.

Introduction to GRU:
The GRU (gated recurrent unit) was introduced to address the forgetting problem in RNNs.

Components of GRU:
The GRU consists of three key elements: a gate, a candidate, and a reset gate. The gate, a sigmoid of some WG XT, determines which information to pass forward from the previous time step. The candidate, a non-linearity of WCTx, represents a potential update to the current hidden state. The reset gate, another sigmoid, controls the amount of information from the previous hidden state to be forgotten.

Comparison to Residual Networks (ResNets):
In a ResNet, the output is calculated by adding the candidate to the previous hidden state. A variant of ResNets called Highway Networks multiplies the candidate by the gate and adds the previous hidden state scaled by 1 minus the gate.

Understanding the Gate Mechanism:
The gate is a sigmoid function that outputs values between 0 and 1 for each dimension of the input vector. A value of 1 indicates that the corresponding information from the candidate will be passed forward, while a value of 0 indicates that the information from the previous hidden state will be retained.

GRU Gating and Reset Mechanism:
The GRU gate determines which parts of the candidate and the previous hidden state are combined to form the new hidden state. The reset gate, or forget gate, controls how much of the previous hidden state is forgotten before calculating the candidate.

Overall Summary:
Residual layers involve adding the previous output to the current input, but can lead to normalization issues. GRUs introduce gated mechanisms to control the flow of information, addressing the forgetting problem in RNNs. The GRU components include a gate, a candidate, and a reset gate, which determine how information is passed forward and forgotten. Highway Networks, a variation of ResNets, use a gating mechanism to selectively combine the candidate and previous hidden state.

GRU vs. Convolutional GRU:
Convolutional GRUs (ConvGRUs) are similar to GRUs but use convolution instead of weight matrices for candidate calculations.

ConvGRUs as Residual Connections:
ConvGRUs share similarities with residual connections but have not been proven to be a direct replacement.

Limited Memory in Basic RNNs:
Basic RNNs, including GRUs, have a fixed-size state vector that limits their memory capacity.

Variable-Sized Memory in ConvGRUs:
ConvGRUs overcome the memory limitation by operating on a variable-sized space, allowing them to process sequences of any length.

Computational Universality of ConvGRUs:
ConvGRUs are computationally universal due to their arbitrary-sized memory and recurrent application. They can simulate a Turing machine by simulating its read, write, and replace operations.

ConvGRUs as Cellular Automata:
ConvGRUs resemble cellular automata, where each position in the sequence considers its neighbors and updates its state accordingly.

Universal Computation with ConvGRUs:
ConvGRUs can perform universal computations by simulating a Turing machine with a tape-like memory.

Potentially Universal Computation:
This neural network architecture appears to exhibit universal computation capabilities, handling sequential and parallel computations.

Long Multiplication Computation:
With n steps of recurrent computation, the network can calculate the result of long multiplication of two binary numbers written in memory.

Parallel Operations:
The computations are highly parallelized, enabling the network to efficiently perform a large number of operations simultaneously.

Memory Storage:
The numbers to be multiplied are stored in the network’s memory, eliminating the need for intermediate storage space.

Limited Computation Steps:
In contrast to traditional multiplication algorithms, which require n squared steps, this approach requires only n steps for multiplication.

Number Length:
The length of the binary numbers involved in the multiplication can be arbitrary, with n representing the length of both numbers.

Parallel Addition:
Although the convolution operation can only access one element to the left and right, addition can be performed in n steps with parallel processing.

Parallel Accumulation:
Efficient accumulation of parallel additions is necessary to avoid requiring n squared space.

Historical Research:
Previous research in the 1980s demonstrated the capacity of parallel models to perform complex computations effectively.

Algorithm Simplicity:
The algorithm’s simplicity allows for efficient computation, unlike traditional methods that require extensive intermediate storage.

Architecture Overview:
The architecture consists of a single column, containing a vector of floats representing the input. Convolutional layers with gating mechanisms (CGRU layers) are applied sequentially to the input vector. The output is the final result of the network.

Long Binary Multiplication:
The network learns to perform long binary multiplication on 20-bit numbers, generalizing to 2,000-bit numbers with no errors.

Proof of Learning:
Proving that the network has learned an algorithm formally is challenging. The network is tested on a set 100 times longer than the training set. While it performs well on this set, it fails on an even larger set, indicating that it has not fully learned the multiplication algorithm.

Visualization:
The state of the network is represented as a 2D grid, with the input on the height axis and the activations on the width axis (channel dimension). In the case of duplication, the network learns to shift down a pattern in the input over time. In the case of reversing, the network learns a “tapey” movement, moving parts of the input up and down to achieve the reversal.

Adding and Multiplying:
The network can also learn to add and multiply binary numbers. In the case of addition, the network spreads out the numbers to align the digits before combining them. In the case of multiplication, the spreading and combining of numbers is more complex and difficult to visualize.

Training Challenges:
Training the network is challenging. Curriculum learning (starting with short numbers and gradually increasing length) and relaxation (starting with different sets of parameters and gradually bringing them together) are used to improve training results. Dropout on the recurrent connection and noise added to gradients are also used to aid training.

Recent Developments:
Recent work by colleagues from Riga has shown that most of the tricks used to train the network are not necessary. With improved neural GPU, their models train successfully almost every time.

Sequence Modeling Tasks:
Convolutional RNNs, such as convolutional GRUs and LSTMs, replace fully connected layers with convolutions.

Neural GPU Improvements:
Using Adamax optimizer is more effective than Adam for algorithmic tasks. Slight modifications to the loss function can help achieve saturation without using additional tricks.

Sequence Repetition Task:
A toy problem of repeating bits at even positions in a sequence is introduced. Convolutional layers should theoretically solve this task easily.

Data Preprocessing:
Data sets are created from Python generators. Tensors are reshaped and converted to one-hot embeddings for integers.

Word Embeddings:
Word embeddings are used in NLP tasks to represent words as dense vectors. In this example, one-hot embeddings are multiplied by a matrix to create word embeddings.

Basic Model Structure:
Input: A one-dimensional vector of binary digits. Convolution Layer: A 2D convolution layer with a 3×1 kernel and padding same. Activation Layer: ReLU activation after the convolution layer. Output Layer: A fully connected layer (equivalent to a 1×1 convolution) for classifying into 10 classes.

Reason for Using 2D Convolutions for 1D Tasks:
Habit and compatibility with standard 2D convolution operations. Reusability of code for image-based tasks.

Training:
Training involves minimizing the cross-entropy loss and maximizing accuracy. Accuracy reached a plateau at around 77-80%.

Troubleshooting:
The initial model output more probabilities than needed, but the network learned to ignore the extra outputs. The model struggled to achieve high accuracy, likely because it couldn’t distinguish between even and odd positions in the input sequence.

Key Concepts Introduced:
Positional information is crucial for achieving high accuracy in sequence-based tasks. Using a learnable vector for each position allows the network to learn positional information. Hard-coded length limits the applicability of the network to sequences of a specific length.

How to Learn Positional Information:
Utilize a learnable vector for each position to learn positional information.

Overcoming Hard-coded Length Limitation:
Explore methods to tell the network about the position without relying on hard-coded length. Consider adding a number representing the position or a normalized position.

Handling Recurrence:
Look into the tf.scan function in TensorFlow for a functional approach to creating loops.

Next Steps:
Address the fixed positional embedding issue by incorporating simple RNNs and recurrence over the input sequence. Attempt to make the network work for the task without a fixed positional embedding.