Supervised, Unsupervised, Semi-Supervised, Self-Supervised, Reinforcement Learning#

Machine learning systems can be classified according to the amount and type of supervision they get during training. The main categories are

• Supervised learning: the training set we feed to the algorithm includes the desired solutions, called labels. A typical supervised learning task is classification, such as spam detector in email
• Unsupervised learning: the training data is unlabeled. Clustering and 2D/3D Visualization are examples.
• Semi-supervised learning: when labeling data is time-consuming and we end up having some labeled instances and some unlabeled, simi-supervised learning can deal with this situation.
• Self-supervised learning: generate a fully labeled dataset from a fully unlabeled one
• Reinforcement learning: the learning system, called an agent in this context, can observe the environment, select and perform actions, and get rewards or penalties in return. It must then learn by itself what is the best strategy, called a policy, to get the most reward over time. A policy defines what action the agent should choose when it is in a given situation.

Online v.s. Batch Learning#

Instance-Based v.s. Model-Based Learning#

One more way to categorize machine learning systems is by how they generalize. Most machine learning tasks are about making predictions. This means that given a number of training examples, the system needs to be able to make good predictions for (generalize to) examples it has never seen before. Having a good performance measure on the training data is good, but insufficient; the true goal is to perform well on new instances.

There are 2 main approaches to generalization:

1. instance-based learning, and
2. model-based learning

Insufficient Quantity of Training Data#

It takes a lot of data for most machine learning algorithms to work properly. Even for very simple problems we typically need thousands of examples, and for complex problems such as image or speech recognition we may need millions of examples.

The Unreasonable Effectiveness of Data

In a famous paper published in 2001, Microsoft researchers Michele Banko and Eric Brill showed that very different machine learning algorithms, including fairly simple ones, performed almost identically well on a complex problem of natural language disambiguation once they were given enough data

As the authors put it, “these results suggest that we may want to reconsider the trade-off between spending time and money on algorithm development versus spending it on corpus development”.

The idea that data matters more than algorithms for complex problems was further popularized by Peter Norvig et al. in a paper titled “The Unreasonable Effectiveness of Data”, published in 2009.

Nonrepresentative Training Data#

Explore in Colab Explore in Kaggle

In order to generalize well, it is crucial that our training data be representative of the new cases we want to generalize to. This is true whether we use instance-based learning or model-based learning and is often harder than it sounds: if the sample is too small, we will have sampling noise (i.e., non-representative data as a result of chance), but even very large samples can be non-representative if the sampling method is flawed. This is called sampling bias.

Overfitting the Training Data#

Explore in Colab Explore in Kaggle

Say we are visiting a foreign country and the taxi driver rips us off. We might be tempted to say that all taxi drivers in that country are thieves. Overgeneralizing is something that we humans do all too often, and unfortunately machines can fall into the same trap if we are not careful. In machine learning this is called overfitting: it means that the model performs well on the training data, but it does not generalize well. See an accompanying Jupyter notebook example that illustrate such phenomenon and its possible solutions

Underfitting the Training Data#

Underfitting is the opposite of overfitting: it occurs when our model is too simple to learn the underlying structure of the data. For example, a linear model of life satisfaction is prone to underfit; reality is just more complex than the model, so its predictions are bound to be inaccurate, even on the training examples.

Here are the main options for fixing this problem:

• Select a more powerful model, with more parameters.
• Feed better features to the learning algorithm (Feature Engineering).
• Reduce the constraints on the model

Biological Motivation and Connections#

Historically, digital computers such as the von Neumann model operate via the execution of explicit instructions with access to memory by a number of processors. Some neural networks, on the other hand, originated from efforts to model information processing in biological systems through the framework of connectionism. Unlike the von Neumann model, connectionist computing does not separate memory and processing.

Basic Principles of Connectionism

The central connectionist principle is that mental phenomena can be described by interconnected networks of simple and often uniform units. The form of the connections and the units can vary from model to model. For example, units in the network could represent neurons and the connections could represent synapses, as in the human brain.

• Activation function: Internal states of any network change over time due to neurons sending a signal to a succeeding layer of neurons in the case of a feedforward network, or to a previous layer in the case of a recurrent network. The activation function defines under what circumstances will a neuron send a signal outward to other neurons. This can be, for example, a function of probability whose range describes the probability of the neuron firing the signal

• Memory and learning: Neural networks follow two basic principles:

  1. Any mental state can be described as a $n$-dimensional vector of numeric activation values over neural units in a network.
  2. Memory and learning are created by modifying the ‘weights’ of the connections between neural units, generally represented as an $(n \times m)$ matrix. The weights are adjusted according to some learning rule or algorithm

The basic computational unit of the brain is a neuron. Approximately 86 billion neurons can be found in the human nervous system and they are connected with approximately $10^{14}$ - $10^{15}$ synapses. The diagram below shows a cartoon drawing of a biological neuron (left) and a common mathematical model (right).

Each neuron receives input signals from its dendrites and produces output signals along its (single) axon. The axon eventually branches out and connects via synapses to dendrites of other neurons.

In the computational model of a neuron, the signals that travel along the axons (e.g. $x_0$) interact multiplicatively (e.g. $w_0x_0$) with the dendrites of the other neuron based on the synaptic strength at that synapse (e.g. $w_0$). The idea is that the synaptic strengths (the weights $w$) are learnable and control the strength of influence (and its direction: excitory (positive weight) or inhibitory (negative weight)) of one neuron on another. In the basic model, the dendrites carry the signal to the cell body where they all get summed. If the final sum is above a certain threshold, the neuron can fire, sending a spike along its axon. In the computational model, we assume that the precise timings of the spikes do not matter, and that only the frequency of the firing communicates information. Based on this rate code interpretation, we model the firing rate of the neuron with an activation function $f$, which represents the frequency of the spikes along the axon. Historically, a common choice of activation function is the sigmoid function $σ$, since it takes a real-valued input (the signal strength after the sum) and squashes it to range between 0 and 1. An example code for forward-propagating a single neuron might look as follows:

1
class Neuron(object):
2
    # ...
3
    def forward(self, inputs):
4
        """ assume inputs and weights are 1-D numpy arrays and bias is a number """
5
        cell_body_sum = np.sum(inputs * self.weights) + self.bias
6
        firing_rate = 1.0 / (1.0 + math.exp(-cell_body_sum)) # sigmoid activation function
7
        return firing_rate

In other words, each neuron performs a dot product with the input and its weights, adds the bias and applies the non-linearity (or activation function), in this case the sigmoid

Coarse model

It’s important to stress that this model of a biological neuron is very coarse. For example, there are many different types of neurons, each with different properties. The dendrites in biological neurons perform complex nonlinear computations. The synapses are not just a single weight, they are a complex non-linear dynamical system. The exact timing of the output spikes in many systems is known to be important, suggesting that the rate code approximation may not hold. Due to all these and many other simplifications, be prepared to hear groaning sounds from anyone with some neuroscience background if we draw analogies between Neural Networks and real brains. See this review if people are interested.

Neural Networks are modeled as collections of neurons that are connected in an acyclic graph. In other words, the outputs of some neurons can become inputs to other neurons. Cycles are not allowed since that would imply an infinite loop in the forward pass of a network. Instead of an amorphous blobs of connected neurons, Neural Network models are often organized into distinct layers of neurons.

Convolutional Neural Networks (CNNs)#

Convolutional Neural Networks (ConvNets or CNNs) are a category of Neural Networks that have proven very effective in areas such as image recognition and classification. ConvNets have been successful in identifying faces, objects and traffic signs apart from powering vision in robots and self-driving cars.

In the figure above, a ConvNet is able to recognize scenes and the system is able to suggest relevant captions (“a soccer player is kicking a soccer ball”) while figure below shows an example of ConvNets being used for recognizing everyday objects, humans and animals. Lately, ConvNets have been effective in several Natural Language Processing tasks (such as sentence classification) as well.

Essentially, every image can be represented as a matrix of pixel values.

Channel is a conventional term used to refer to a certain component of an image. An image from a standard digital camera will have three channels - red, green and blue - we can imagine those as three 2d-matrices stacked over each other (one for each color), each having pixel values in the range 0 to 255. A grayscale image, on the other hand, has just one channel. We will only consider grayscale images, so we will have a single 2d matrix representing an image. The value of each pixel in the matrix will range from 0 to 255 - zero indicating black and 255 indicating white.

Introduction#

We all heard of this buz word “LLM” (Large Language Model). But let’s put that aside for just a second and look at a much simpler one called “character-level language model” where, for example, we input a prefix of a word such as “hell” and the model outputs a complete word “hello”. That is, this language model predicts the next character of a character sequence. This is like a Math function where we have:

where we call inputs like “hell” a sequence.

How do we obtain a function like this? One approach is to have 4 black boxes, each of which takes a single character as input and calculates an output:

But one might have noticed that if the 3rd function (box) produces $f('l') = 'l'$, then why would the 4th function (box), given the same input, gives a different output of ‘o’? This suggest that we should take the history into account. Instead of having $f$ depend on 1 parameter, we now have it take 2 parameters.

1. a character;
2. a variable that summarizes the previous calculations:

Now it makes much more sense with:

But what if we want to predict a longer or shorter word? For example, how about predicting “cat” by “ca”? That’s simple, we will have 2 black boxes to do the work.

What if the function $f$ is not smart enough to produce the correct output everytime? We will simply collect a lot of examples such as “cat” and “hello”, and feed them into the boxes to train them until they can output correct vocabulary like “cat” and “hello”.

This is the idea behind RNN. It’s recurrent because the boxed function gets invoked repeatedly for each element of the sequence. In the case of our character-level language model, element is a character such as “e” and sequence is a string like “hell”

Each function $f$ is a network unit containing 2 perceptrons. One perceptron computes the “history” like $h_1$, $h_2$, $h_3$.

One great thing about the RNNs is that they offer a lot of flexibility on how we wire up the neural network architecture. Normally when we are working with neural networks, we are given a fixed sized input vector (red boxes below), then we process it with some hidden layers (green), and we produce a fixed sized output vector (blue). The left-most model in figure below is the Vanilla Neural Networks, which receives a single input and produce one output (The green box in between actually represents layers of neurons). The rest of the models on the right are all Recurrent Neural Networks that allow us to operate over sequences of input, output, or both at the same time:

• An example of one-to-many model is image captioning where we are given a fixed sized image and produce a sequence of words that describe the content of that image through RNN
• An example of many-to-one task is sentiment classification in NLP where we are given a sequence of words of a
• sentence and then classify what sentiment (e.g. positive or negative) that sentence is.
• An example of many-to-many task is machine translation in NLP, where we can have an RNN that takes a sequence of words of a sentence in English, and then this RNN is asked to produce a sequence of words of a sentence in German.
• There is also a variation of many-to-many task as shown in the last model in figure below, where the model generates an output at every timestep. An example of this many-to-many task is video classification on a frame level where the model classifies every single frame of video with some number of classes. We should note that we don’t want this prediction to only be a function of the current timestep (current frame of the video), but also all the timesteps (frames) that have come before this video.

TIP

A CNN learns to recognize patterns across space. So a CNN will learn to recognize components of an image (e.g., lines, curves, etc.) and then learn to combine these components to recognize larger structures (e.g., faces, objects, etc.)

A RNN will similarly learn to recognize patterns across time. So a RNN that is trained to translate text might learn that “dog” should be translated differently if preceded by the word “hot”.

The mechanism by which the two kinds of NNs represent these patterns is different, however. In the case of a CNN, we are looking for the same patterns on all the different subfields of the image. In the case of a RNN we are (in the simplest case) feeding the hidden layers from the previous step as an additional input into the next step. While the RNN builds up memory in this process, it is not looking for the same patterns over different slices of time in the same way that a CNN is looking for the same patterns over different regions of space.

It should be noted that “time” and “space” here shouldn’t be taken too literally. We could run a RNN on a single image for image captioning, for instance, and the meaning of “time” would simply be the order in which different parts of the image are processed. So objects initially processed will inform the captioning of later objects processed.

The sequence regime of operation is much more powerful compared to fixed networks that are doomed from the get-go by a fixed number of computational steps. Moreover, as we’ll see in a bit, RNNs combine the input vector with their state vector with a fixed (but learned) function to produce a new state vector. This can in programming terms be interpreted as running a fixed program with certain inputs and some internal variables. Viewed this way, RNNs essentially describe programs. In fact, it is known that RNNs are Turing-Complete in the sense that they can simulate arbitrary programs (with proper weights).

Space → Time v.s. Function → Program

If training vanilla neural nets is optimization over functions, training recurrent nets is optimization over programs.

If our data is not in form of sequences, we can still formulate and train powerful models that learn to process it sequentially. We’re learning stateful programs that process our fixed-sized data.

At the core, RNNs accept an input vector x and give us an output vector y. This output vector’s contents are influenced not only by the input we just fed in, but also on the entire history of inputs we’ve fed in from the past. The RNN’s API consists of a single step function:

1
rnn = RNN()
2
y = rnn.step(x) # x is an input vector, y is the RNN's output vector

This is where RNN starts to model the notion of “memory”: The RNN class has some internal state that is updated every time step() is called. In the simplest case this state consists of a single hidden vector h:

1
class RNN:
2
    # ...
3
    def step(self, x):
4
        # update the hidden state
5
        self.h = np.tanh(np.dot(self.W_hh, self.h) + np.dot(self.W_xh, x))
6
        # compute the output vector
7
        y = np.dot(self.W_hy, self.h)
8
        return y

The step function above specifies the forward pass of RNN. There are 3 parameters $W_hh$, $W_xh$, and $W_hy$. The hidden vector, or more generally the hidden state, is defined by

where $t$ is the index of the “black boxes” shown earlier. In our example of “hell”, $t \in \{ 1, 2, 3, 4 \}$. The hidden state $h$ is usually initialized with zero vector (simulating “no memory at all”). There are 2 terms inside the $g_1$:

1. one term based on the previous hidden state $W_{hh}h^{(t - 1)}$, and
2. the other term based on the current input $W_{xh}x^{(t)}$

In the program above we use numpy np.dot which is a matrix multiplication. The 2 terms interact with addition.

We initialize matrices $W_hh$, $W_xh$, and $W_hy$ with random numbers and the bulk of work during training goes into finding the matrices that gives rise to the desirable behavior, as measured with some loss function that expresses our preferences to what kind of output y we would like to see in response to our input sequence x

The value $y$ is given by

What are $g_1$ and $g_2$?

They are activation functions which are used to change the linear function in a perceptron to a non-linear function. Please refer to Machine Learning by Mitchell, Tom M. (1997), Paperback (page 96) for why we bump it to non-linear

A typical activation function for $g_1$ is $tanh$:

$$tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$$

which squashes the activations to the range $[0, 1]$

In practice, $g_2$ is constance, i.e. $g_2 = 1$

We get RNNs as neural networks if we stack up as follows:

1
y1 = rnn1.step(x)
2
y = rnn2.step(y1)

In other words we have two separate RNNs: One RNN is receiving the input vectors and the second RNN is receiving the output of the first RNN as its input. Except neither of these RNNs know or care - it’s all just vectors coming in and going out, and some gradients flowing through each module during backpropagation.

Forward Propagation Equations for RNN#

We now develop the forward propagation equations for the RNN. We assume the hyperbolic tangent activation function, i.e. $tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$ and that the output is discrete, as if the RNN is used to predict words or characters. A natural way to represent discrete variables is to regard the output $\boldsymbol{o}$ as giving the unnormalized log probabilities of each possible value of the discrete variable. We can then apply the softmax (discussed shortly) operation as a post-processing step to obtain a vector $\boldsymbol{\hat{y}^{(t)}}$ of normalized probabilities over the output.

Forward propagation begins with a specification of the initial state $\boldsymbol{h}^{(0)}$. The dimension of the hidden state $\boldsymbol{h}$, in contract to our previous overview, is independent of the dimension of the input or output sequences. In fact, $\boldsymbol{h}$ is a 3D array, whose 1st-dimensional size is exactly the number of RNN parameters.

Then, for each time step from $t = 1$ to $t = \tau$, we apply the following update equations:

where

• $\boldsymbol{h}^{(t)}$ is the hidden state vector of size $(\tau + 1)$
• $\boldsymbol{o}^{(t)}$ is the output produced by the model at step $t$ where $t \in \{1, 2, \cdots, \tau\}$
• $\boldsymbol{\hat{y}^{(t)}}$ is the normalized probability of $\boldsymbol{o}^{(t)}$ at $\tau = t$
• $\boldsymbol{b_h}$ is the hidden bias vector of size $\tau$
• $\boldsymbol{b_o}$ is the output bias vector of size $\tau$
• the size of $\boldsymbol{W_{xh}}$ is $(\tau - 1) \times \tau$
• the size of $\boldsymbol{W_{hh}}$ is $(\tau - 1) \times (\tau - 1)$
• the size of $\boldsymbol{W_{xh}}$ is $\tau \times (\tau - 1)$

Note that this recurrent network maps an input sequence to an output sequence of the same length.

Loss Function of RNN#

According to the discussion of Machine Learning by Mitchell, Tom M. (1997), the key for training RNN or any neural network is through “specifying a measure for the training error”. We call this measure a loss function.

In RNN, the total loss for a given sequence of input $\boldsymbol{x}$ paired with a sequence of expected $\boldsymbol{y}$ is the sum of the losses over all the time steps, i.e.

Knowing the exact form of $\mathcal{L}^{(t)}$ requires our intuitive understanding of cross-entropy

Deriving Gradient Descent Weight Update Rule#

Training a RNN model of is the same thing as searching for the optimal values for the following parameters of the Forward Progagation Equations:

1. $W_{xh}$
2. $W_{hh}$
3. $W_{yh}$
4. $b_h$
5. $b_o$

By the Gradient Descent discussed in Machine Learning by Mitchell, Tom M. (1997), Paperback, we should derive the weight update rule by taking partial derivatives with respect to all of the variables above. Let’s start with $W_{yh}$

Machine Learning by Mitchell, Tom M. (1997), Paperback has also mentioned gradients and partial derivatives as being important for an optimization algorithm to update, say, the model weights of a neural network to reach an optimal set of weights. The use of partial derivatives permits each weight to be updated independently of the others, by calculating the gradient of the error curve with respect to each weight in turn.

Many of the functions that we usually work with in machine learning are multivariate, vector-valued functions, which means that they map multiple real inputs $n$ to multiple real outputs $m$:

In training a neural network, the backpropagation algorithm is responsible for sharing back the error calculated at the output layer among the neurons comprising the different hidden layers of the neural network, until it reaches the input.

If our RNN contains only 1 perceptron unit, the error is propagated back by, using the Chain Rule of $\frac{dz}{dx} = \frac{dz}{dy}\frac{dy}{dx}$:

Note that in the RNN mode, $\mathcal{L}$ is not a direct function of $W$. Thus its first order derivative cannot be computed unless we connect the $\mathcal{L}$ to $o$ first and then to $W$, because both the first order derivatives of $\frac{\partial \mathcal{L}}{\partial o}$ and $\frac{\partial o}{\partial W}$ are defined by the model presented earlier above

It is more often the case that we’d have many connected perceptrons populating the network, each attributed a different weight. Since this is the case for RNN, we can generalise multiple inputs and multiple outputs using the Generalized Chain Rule:

Generalized Chain Rule

Consider the case where $x \in \mathbb{R}^m$ and $u \in \mathbb{R}^n$; an inner function, $f$, maps $m$ inputs to $n$ outputs, while an outer function, $g$, receives $n$ inputs to produce an output, $h \in \mathbb{R}^k$. For $i = 1, \dots, m$ the generalized chain rule states:

$$\frac{\partial h}{\partial x_i} = \frac{\partial h}{\partial u_1} \frac{\partial u_1}{\partial x_i} + \frac{\partial h}{\partial u_2} \frac{\partial u_2}{\partial x_i} + \dots + \frac{\partial h}{\partial u_n} \frac{\partial u_n}{\partial x_i} = \sum_{j = 1}^n \frac{\partial h}{\partial u_j} \frac{\partial u_j}{\partial x_i}$$

Therefore, the error propagation of Gradient Descent in RNN is

where $n$ is the length of a RNN sequence and $t$ the index of timestep

On $\sum_{t = 1}^\tau$

We assume the error is the sum of all errors of each timestep, which is why we include the $\sum_{t = 1}^\tau$ term

Let’s look at $\frac{\partial \mathcal{L}}{W_{yh}}$ first

Since $o_i = \left( W_{yh}h_i + b_o \right)$

For the $\frac{\partial \mathcal{L}}{\partial o_i}$ we shall recall from the earlier discussion on softmax derivative that we CANNOT simply have

because we need to

1. specify which component (output element) we’re seeking to find the derivative of
2. with respect to which input element the partial derivative is computed

Therefore:

where $n$ is the number of timesteps (or the length of a sequence such as “hell”)

Applying the chain rule again:

Recall we have already derived that

Observing that

We have at this point derived backpropagating rule for $W_{yh}$ and $b_o$:

1. $W_{xh}$
2. $W_{hh}$
3. ✅ $W_{yh}$
4. $b_h$
5. ✅ $b_o$

Now let’s look at $\frac{\partial \mathcal{L}}{\partial W_{hh}}$:

Recall from Deep Learning, section 6.5.2, p. 207 that the vector notation of $\frac{\partial z}{\partial x_i} = \sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i}$ is

This gives us a start with:

The equation above leaves us with a term $\nabla_{\boldsymbol{h}^{(t)}}\mathcal{L}$, which we calculate next. Note that the back propagation on $\boldsymbol{h}^{(t)}$ has source from both $\boldsymbol{o}^{(t)}$ and $\boldsymbol{h}^{(t + 1)}$. It’s gradient, therefore, is given by

Note that the 2nd term $\boldsymbol{W_{xh}}^\intercal \nabla_{\boldsymbol{h}^{(t + 1)}}\mathcal{L} \left( diag\left[ 1 - (\boldsymbol{h}^{(t + 1)})^2 \right] \right)$ is zero at first iteration propagating back because for the last-layer (unrolled) of RNN , there’s no gradient update flow from the next hidden state.

So far we have derived backpropagating rule for $W_{hh}$

1. $W_{xh}$
2. ✅ $W_{hh}$
3. ✅ $W_{yh}$
4. $b_h$
5. ✅ $b_o$

Let’s tackle the remaining $\frac{\partial \mathcal{L}}{\partial W_{xh}}$ and $b_h$:

This concludes our propagation rules for training RNN:

According to page 91 of Machine Learning by Mitchell, Tom M. (1997), Paperback, the amount of updates in direction $i$ is given by

The update rules for training RNN with a learning rate of $\eta$, therefore, are: